Дизъюнктивные нормальные формы

Тема Дизъюнктивные нормальные формы

Понятие ДНФ

Пусть задан алфавит переменных {x₁, …, x_n}.

Выражение вида

& & … & ()

называется элементарной конъюнкцией. Здесь у_j = {0, 1} и переменная xi_j входит в конъюнкцию с отрицанием, если у_j = 0, и без отрицания, если у_j = 1.

Число r называется рангом элементарной конъюнкции. По определению считаем константу 1 элементарной конъюнкцией ранга 0.

Выражение вида

()

где K_i (i = 1, …, s) — элементарная конъюнкция ранга r_i, называется дизъюнктивной нормальной формой (д.н.ф.).

Пример.

D₁ = (a) V (a & c) V (b & c) — это днф

D₂ = (x₁ & x₂ & x₃) V (x₁ & x₂ & x₃) V (x₁ & x₂ & x₃) V (x₁ & x₂ & x₃) — это днф

Контрпример:

X = (a V b)&(b V c) — это не днф

Представление булевой функции в виде дизъюнктивной нормальной формы бывает крайне удобным для доказательства некоторых теорем, а также для исследования функции и её визуализации.

Отметим, что любая функция может быть представлена в виде ДНФ, вообще говоря, не единственным образом. Пример:

D₁ = (a&b) V (a&b).

Простым перебором убеждаемся, что данная ДНФ может быть записана как

D₂ = a.

Отыскание наиболее простой формы представления заданной функции в виде ДНФ является одной из важнейших задач дискретной математики. Позже мы рассмотрим несколько способов решения этой задачи.

Построение ДНФ

Алгоритм построения ДНФ путём замены операций в выражении.

Пусть требуется привести произвольную формулу к виду днф. Алгоритм состоит в следующем:

1) Выразить все логические операции в формуле через конъюнкции, дизъюнкции и отрицания. Это можно сделать, используя равносильные формулы

2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул

3) Избавиться от знаков двойного отрицания.

4) Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства дистрибутивности и формулы поглощения.

Таким образом, для функции, заданной аналитически, можно построить ДНФ, превратив её в дизъюнкцию простых конъюнкций. Полученная формула будет удовлетворять определению дизъюнктивной нормальной формы.

Пример.

Приведем к ДНФ формулу

F = ((X -> Y) v (Y -> Z))

1) F = ((X V Y) v (Y V Z)) = ((X V Y) V (Y V Z))

2) В полученной формуле перенесем отрицание к переменным:

F = ((X V Y) V (Y V Z)) = (X & Y) & (Y V Z)

3) сократим двойные отрицания

F = (X & Y) & (Y V Z)

4) Используя закон дистрибутивности, приводим формулу к ДНФ

F = (X & Y) V (X & Y & Z)

Алгоритм построения СДНФ по таблице истинности

Пусть имеется таблица истинности для функции n переменных.

Для каждого набора {у₁, …, у_n}, такого, что f (у₁, …, у_n) = 1, выписать элементарную конъюнкцию, в которую переменная x_i входит со знаком отрицания, если у_i = 0, и без него, если у_i = 1. Дизъюнкция всех таких элементарных конъюнкций и будет СДНФ, реализующей данную функцию.

Пример.

Пусть дана таблица истинности для функции трёх переменных.

Здесь f (0,0,1) = 1, значит, в ДНФ включаем конъюнкцию x₁ & x₂ & x₃

Аналогично, включаем x₁ & x₂ & x₃, x₁ & x₂ & x₃ и x₁ & x₂ & x₃.

Получаем: f (x₁, x₂, x₃) = (x₁ & x₂ & x₃) V (x₁ & x₂ & x₃) V (x₁ & x₂ & x₃) V (x₁ & x₂ & x₃).

Аналогично строится КНФ: для каждого набора {у₁, …, у_n}, такого, что f (у₁, …, у_n) = 0, выписать элементарную дизъюнкцию, в которую переменная x_i входит со знаком отрицания, если у_i = 0, и без него, если у_i = 1. Конъюнкция всех таких дизъюнкций образует КНФ — выражение вида

(V V … V) & (V V … V) & … & (V V … V).

Упрощение ДНФ

Рассмотрим задачу упрощения ДНФ — сокращения количества слагаемых, входящих в формулу, а также количества переменных, входящих в каждое слагаемое. Эта задача называется проблемой минимизации булевых функций. Заметим сразу, что эта проблема допускает тривиальное решение: поскольку количество всех возможных ДНФ от n переменных конечно (их), можно построить их все, и выбирать среди них подходящие.

1) Построим все ДНФ над переменными x₁, x₂, …, x_n:

D₁, D₂, … ,

2) Выберем среди них те, которые реализуют заданную функцию f:

D₁, D₂, … ,

3) Наконец, выберем среди них минимальные.

Данный алгоритм весьма трудоёмок с точки зрения реализации, так как он основан на переборе всех днф. Им нельзя воспользоваться на практике начиная уже с n=3, а для более высоких n алгоритм вовсе неприменим. В связи с этим появилась необходимость искать другие пути решения этой задачи. Далее будет рассказано о некоторых практических алгоритмах минимизации.

Алгоритм Блейка

Идея алгоритма в том, чтобы получить сокращенную ДНФ из произвольной путём выполнения операций обобщённого склеивания и поглощения конъюнкций.

Закон поглощения: x&y V x = x.

Закон обобщенного склеивания: x&y V y&z = x&y V y&z V x&z

Рассмотрим конъюнкции заданной ДНФ слева направо:

1) Пусть выбрана конъюнкция K_i. Проверяем её на возможность обобщённого склеивания с предшествующими конъюнкциями. При этом для очередной K_i, K_j, j < i возможны следующие ситуации:

а) результат обобщенного склеивания поглощается рассматриваемой ДНФ. Тогда и переходим к шагу 2.

б) результат обобщенного склеивания не поглощается ни одной из конъюнкций ДНФ. Тогда его приписывают в конец формулы. Поглощенные приписанной конъюнкцией другие конъюнкции вычеркиваются из ДНФ.

2) Увеличиваем j. Если i j переходим к шагу 1, увеличивая i и полагая j = 1, иначе увеличиваем j.

Разберём этот алгоритм на примере.

Пример. Пусть дана произвольная ДНФ:

D = x&y V x&z V y&z.

К первой и второй конъюнкции можно применить закон обобщённого склеивания:

x&y V x&z = x&y V x&z V y&z

Слагаемое y&z не поглощается ни одной из конъюнкций ДНФ, значит, приписываем его в конец формулы.

D = x&y V x&z V y&z V y&z.

Применим закон обобщённого склеивания к первой и третьей конъюнкции, припишем полученную конъюнкцию справа:

D = x&y V x&z V y&z V y&z V x&z

Применим закон обобщённого склеивания к третьему и четвёртому слагаемому:

y&z V y&z = y&z V y&z V z

Припишем z в конец выражения:

D = x&y V x&z V y&z V y&z V x&z V z

Легко заметить, что z поглощает все конъюнкции, содержащие переменную z, то есть все кроме первого:

D = x&y V z.

Минимальная ДНФ построена.

Карты Карно

Карты Карном — графический способ минимизации переключательных (булевых) функций, обеспечивающий относительную простоту работы с большими выражениями. Представляет собой операции попарного неполного склеивания и элементарного поглощения. Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции. Карты Карно можно рассматривать как определенную плоскую развертку n-мерного булева куба.

Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы.

Возможность поглощения следует из очевидных равенств:

A V A = 1; A&(A) = 0.

Таким образом, главной задачей при минимизации СДНФ и СКНФ является поиск термов, пригодных к склейке с последующим поглощением, что для больших форм может оказаться достаточно сложной задачей. Карты Карно предоставляют наглядный способ отыскания таких термов.

Разберём минимизацию СДНФ с помощью карт Карно на примере.

Пример.

Пусть дана таблица истинности для функции трёх переменных.

Соответствующая ей СДНФ: (x₁ & x₂ & x₃) V (x₁ & x₂ & x₃) V (x₁ & x₂ & x₃) V (x₁ & x₂ & x₃).

Сначала необходимо построить прямоугольное поле с количеством клеток 2ⁿ. В этом случае стороны прямоугольника также будут степенью двойки (0, 1, 2, 4, …). Для трёх переменных количество клеток будет 2³ = 8.

Построим поле 2x4

Каждой клетки этого поля будет соответствовать возможная элементарная конъюнкция формулы. Чтобы это обеспечить, необходимо обозначить для каждой переменной области, где она входит со знаком отрицания и без него. Сделать это можно, например, следующим образом Первая (верхняя) строка будет соответствовать тем конъюнкциям, в которые x₁ входит с отрицанием, нижняя — без. Аналогично, левая половина поля отвечает тем конъюнкциям, где x₃ входит без отрицания, правая — с отрицанием. Несложно убедиться, что при таком разбиении присутствуют клетки для каждой возможной элементарной конъюнкции.

Далее, нужно пометить единицей клетки, соответствующие конъюнкции которых присутствуют в формуле: f (у₁, у₂, у₃) = 1. В нашем случае таких конъюнкций четыре. Им соответствуют клетки:

Далее, необходимо выделить области по следующим правилам:

· Склейку клеток карты Карно можно осуществлять по единицам.

· Склеивать можно только прямоугольные области с числом единиц (нулей) 2ⁿ, где n — целое число. Для карт Карно с числом переменных более четырёх могут получаться более сложные области, о чём будет сказано в следующих разделах.

· Область, которая подвергается склейке, должна содержать только единицы.

· Крайние клетки каждой горизонтали и каждой вертикали также граничат между собой (топологически карта Карно для четырёх переменных представляет собой тор) и могут объединяться в прямоугольники. Следствием этого правила является смежность всех четырёх угловых ячеек карты Карно для N=4. Если во всех четырёх угловых ячейках стоят единицы, они могут быть объединены в квадрат.

· Все единицы (нули) должны попасть в какую-либо область.

· С точки зрения минимальности ДНФ число областей должно быть как можно меньше (каждая область представляет собой терм), а число клеток в области должно быть как можно больше (чем больше клеток в области, тем меньше переменных содержит терм. Терм размером 2ⁿ ячеек содержит N-n переменных).

· Одна ячейка карты Карно может входить сразу в несколько областей. Это следует из очевидного свойства булевых функций: повторение уже существующего слагаемого (сомножителя) не влияет на функцию: A V A = A, A&A = A.

В нашем случае, можно выделить две области 1×2 и 2x1

Затем, выписываем конъюнкции, соответствующие данным областям.

Левая область отвечает конъюнкции, куда входит переменная x₃ и x₂, а от переменной x₁ эта область не зависит (не меняется от замены x₁ на x₁), поэтому её туда не включаем. Получаем: x₂&x₃. Аналогично получаем вторую конъюнкцию: x₁&x₂. В итоге, ДНФ упростилась до дизъюнкции двух конъюнкций:

(x₁ & x₂ & x₃) V (x₁ & x₂ & x₃) V (x₁ & x₂ & x₃) V (x₁ & x₂ & x₃) = (x₁&x₂) V (x₂&x₃)

Ещё один, более простой пример. Пусть дана ДНФ: (a&b) V (a&b). Соответствующая карта Карно будет полем 2х2

Вносим единицы в соответствующие клетки Объединяем их в одну область Выписываем конъюнкцию, соответствующую данной области:

f (a, b) = a

Это и будет упрощенная ДНФ данной функции. Таким образом, функция не зависит от переменной b.

Постановка задачи в геометрической форме

Аналогично картам Карно, искать кратчайшие покрытия функции f (x₁, x₂, …, x_n) можно на гранях n-мерного куба (где n — количество входящих в функцию переменных).

Обозначим через Eⁿ множество всех наборов (у₁, …, у_n) из 0 и 1. Его можно рассматривать как множество всех вершин n-мерного куба. Поскольку никаких других, кроме упомянутых, точек мы не рассматриваем, постольку множество Eⁿ будем называть n-мерным кубом, а наборы (у₁, …, у_n) — вершинами куба.

Примеры проекций 3-мерного, 4-мерного, 5-мерного и 6-мерного кубов на плоскость:

На рисунке 4 — не наборы, а соответствующие им натуральные числа.

Определение. Пусть — фиксированная система чисел из 0 и 1 такая, что

1 i₁ i₂ … i_r n. Множество всех вершин (₁, ₂, …, _n,) куба Eⁿ таких, что

,, …,, называется (n — r)-мерной гранью.

Очевидно, что (n — r)-мерная грань является (n — r)-мерным подкубом куба Eⁿ.

Пусть f (x₁, x₂, …, x_n) — произвольная функция алгебры логики. Сопоставим ей подмножество N_f вершин куба Eⁿ так, что

(₁, ₂, …, _n,) N_f тогда и только тогда, когда когда f (₁, ₂, …, _n,) = 1.

Ясно, что по подмножеству N_f функция восстанавливается единственным образом.

Пример.

f = (x₁ & x₂ & x₃) V (x₁ & x₂ & x₃) V (x₁ & x₂ & x₃) V (x₁ & x₂ & x₃) V (x₁ & x₂ & x₃)

Функции f, подмножество N_f которой задаётся как N_f = {(0, 0, 0), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)},

соответствует множество, изображенное на рисунке 5:

Выберем в качестве покрытия следующие два подмножества: x₁ (правая квадратная грань) и x₂ & x₃ (переднее нижнее ребро). Получим: D = x₁ V (x₂ & x₃)

Возьмём в качестве исходной функции элементарную конъюнкцию K ранга r, где

& & … &

Легко видеть, что множество N_k, соответствующие конъюнкции K, образует (n — r)-мерную грань.

Число r будем называть рангом этой грани.

В нашем примере, конъюнкции K₁ = (x₁ & x₂ & x₃) соответствует множество N_K1 = (0, 0, 0) ранга 3 и куб размерности 3 — 3 = 0 (точка);

конъюнкции K₂ = (x₁ & x₂) соответствует множество N_K2 = {(1, 0, 0), (1, 0, 1)} ранга 2 и куб размерности 3 — 2 = 1 (ребро);

конъюнкции K₃ = (x₁) соответствует множество N_K3 = {(1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)} ранга 1 и куб размерности 3 — 1 = 2 (квадратная грань); И так далее.

Итак, пусть r_i обозначает ранг грани N_Ki (он равен рангу конъюнкции K_i). Число r, где

r = ,

будем называть рангом покрытия. Теперь мы можем дать формулировку задачи в геометрической форме, эквивалентной задачи о минимизации булевой функции:

Найти для данного множества N_f такое покрытие гранями, принадлежащими N_f,

N_f = N_K1 U N_K2 U … U N_Ks,

Чтобы его ранг был наименьшим.

Таким образом, можно считать, что задача о минимизации булевой функции имеет две постановки. Одна — аналитическая (исходная), вторая — геометрическая (задача о покрытиях).

булевой функция операция дизъюнктивный

Список источников

· С. В. Яблонский — Введение в дискретную математику (6-е изд, 2010 г.)

· Самофалов, А. М. Романкевич, В. Н. Валуйский — «Прикладная теория цифровых автоматов» Киев «Вища Школа» 1987