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

Тема

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

Понятие ДНФ

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

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

& & … & ()

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

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

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

()

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

Пример.

D1 = (a) V (¬a & c) V (¬b & c) - это днф2 = (¬x1 & ¬x2 & x3) V (x1 & ¬x2 & x3) V (x1 & x2 & ¬x3) V (x1 & x2 & x3) - это днф

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

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

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

Отметим, что любая функция может быть представлена в виде ДНФ, вообще говоря, не единственным образом. Пример:1 = (a&b) V (a&¬b).

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

D2 = a.

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

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

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

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

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

A->B¬A V BA<->B(A & B) V (¬A & ¬B)A+B(¬A & B) V (A & ¬B)A|B¬A V ¬BA?B¬A & ¬B

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

¬(A V B)¬A & ¬B¬(A & B)¬A V ¬B

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

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

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

Пример.

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

F = ((X -> Y) ? ¬ (Y -> Z))

1)F = ((¬X V Y) ? ¬(¬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)

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

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

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

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

x1…xnf0…0?10…1?2…………1…0?(2^n)-11…1?2^n

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

Пример.

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

x1x2x3f00000011010001101000101111011111

Здесь f(0,0,1) = 1, значит, в ДНФ включаем конъюнкцию ¬x1 & ¬x2 & x3

Аналогично, включаем x1 & ¬x2 & x3, x1 & x2 & ¬x3 и x1 & x2 & x3.

Получаем: f(x1, x2, x3) = (¬x1 & ¬x2 & x3) V (x1 & ¬x2 & x3) V (x1 & x2 & ¬x3) V (x1 & x2 & x3).

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

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

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

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

)Построим все ДНФ над переменными x1, x2, … , xn:

D1, D2, … ,

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

D1, D2, … ,

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

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

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

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

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

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

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

) Пусть выбрана конъюнкция Ki. Проверяем её на возможность обобщённого склеивания с предшествующими конъюнкциями. При этом для очередной Ki, Kj, 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.

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

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

Пример.

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

x1x2x3f00000011010001101000101111011111

Соответствующая ей СДНФ: (¬x1 & ¬x2 & x3) V (x1 & ¬x2 & x3) V (x1 & x2 & ¬x3) V (x1 & x2 & x3).

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

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

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

Первая (верхняя) строка будет соответствовать тем конъюнкциям, в которые x1 входит с отрицанием, нижняя - без. Аналогично, левая половина поля отвечает тем конъюнкциям, где x3 входит без отрицания, правая - с отрицанием. Несложно убедиться, что при таком разбиении присутствуют клетки для каждой возможной элементарной конъюнкции.

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

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

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

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

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

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

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

·С точки зрения минимальности ДНФ <#"justify">В нашем случае, можно выделить две области 1x2 и 2x1

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

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

(¬x1 & ¬x2 & x3) V (x1 & ¬x2 & x3) V (x1 & x2 & ¬x3) V (x1 & x2 & x3) = (x1&x2) V (¬x2&x3)

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

Вносим единицы в соответствующие клетки

Объединяем их в одну область

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

f(a, b) = a

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

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

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

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

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

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

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

i1 i2 … ir n. Множество всех вершин (1, 2, …, n,) куба En таких, что

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

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

Пусть f(x1, x2, …, xn) - произвольная функция алгебры логики. Сопоставим ей подмножество Nf вершин куба En так, что

(1, 2, …, n,) Nf тогда и только тогда, когда когда f(1, 2, …, n,) = 1.

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

Пример.

f = (¬x1 & ¬x2 & ¬x3) V (x1 & ¬x2 & ¬x3) V (x1 & ¬x2 & x3) V (x1 & x2 & ¬x3) V (x1 & x2 & x3)

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

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

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

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

& & … &

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

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

В нашем примере, конъюнкции K1 = (¬x1 & ¬x2 & ¬x3) соответствует множество NK1 = (0, 0, 0) ранга 3 и куб размерности 3 - 3 = 0 (точка);

конъюнкции K2 = (x1 & ¬x2) соответствует множество NK2 = {(1, 0, 0), (1, 0, 1)} ранга 2 и куб размерности 3 - 2 = 1 (ребро);

конъюнкции K3 = (x1) соответствует множество NK3 = {(1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)} ранга 1 и куб размерности 3 - 1 = 2 (квадратная грань); И так далее.

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

r = ,

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

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

Nf = NK1 U NK2 U … U NKs,

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

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

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

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

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

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