Дизъюнктивные нормальные формы
Тема
Дизъюнктивные
нормальные формы
Понятие ДНФ
Пусть задан алфавит переменных {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 B
|
A<->B
|
(A & B) V (¬A & ¬B)
|
A+B
|
(¬A & B) V (A & ¬B)
|
A|B
|
¬A V ¬B
|
A↓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
|
…
|
xn
|
f
|
0
|
…
|
0
|
μ1
|
0
|
…
|
1
|
μ2
|
…
|
…
|
…
|
…
|
1
|
…
|
0
|
μ(2^n)-1
|
1
|
…
|
μ2^n
|
Для каждого набора {σ1, …, σn}, такого, что f(σ1, …, σn) = 1, выписать элементарную
конъюнкцию, в которую переменная xi входит со знаком отрицания, если σi = 0, и без него, если σi = 1. Дизъюнкция всех таких
элементарных конъюнкций и будет СДНФ, реализующей данную функцию.
Пример.
Пусть дана таблица истинности для функции трёх переменных.
x1
|
x2
|
x3
|
f
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
Здесь 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
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.
Таким образом, главной задачей при минимизации СДНФ и СКНФ является поиск
термов, пригодных к склейке с последующим поглощением, что для больших форм
может оказаться достаточно сложной задачей. Карты Карно предоставляют наглядный
способ отыскания таких термов.
Разберём минимизацию СДНФ с помощью карт Карно на примере.
Пример.
Пусть дана таблица истинности для функции трёх переменных.
x1
|
x2
|
x3
|
f
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
Соответствующая ей СДНФ: (¬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. Если во всех четырёх угловых ячейках стоят
единицы, они могут быть объединены в квадрат.
· Все единицы (нули) должны попасть в
какую-либо область.
· С
точки зрения минимальности ДНФ
<#"662433.files/image016.gif">
Затем, выписываем конъюнкции, соответствующие данным областям.
Левая область отвечает конъюнкции, куда входит переменная 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