Существует простой способ дать аналитическое представление функции в виде формулы, содержащей конъюнкции, дизъюнкции и отрицания, используя ее табличное задание. Например, пусть функция от трех переменных задана следующей таблицей:
x y z f(x,y,z)
--------------------------------
0 0 0 1
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1
Тогда
f(x,y,z) = x’y’z’∨xy’z’∨xyz.
Каждый из трех дизъюнктивных членов (слагаемых) записанной формулы соответствует набору значений аргументов, для которого функция принимает значение 1. Каждое слагаемое содержит все три аргумента функции; отрицанием снабжены те из них, которые имеют значение 0 в соответствующем наборе. Так, набору (0,0,0) соответствует слагаемое x’y’z’, набору (1,0,0) – слагаемое xy’z’, набору (1,1,1) – слагаемое xyz. Каждый из дизъюнктивных членов принимает значение 1 на своем наборе значений переменных и значение 0 – на всех остальных. Дизъюнкция этих трех слагаемых принимает значение 1 лишь тогда, когда значение 1 принимает хотя бы одно из слагаемых. Таким образом, функция в правой части записанного равенства принимает значение 1 на тех же трех наборах значений аргументов, что и функция f (на остальных наборах обе эти функции принимают значение 0). Тем самым справедливость равенства установлена.
Легко видеть, что описанный способ построения формулы по таблице применим к любой функции, не равной тождественно нулю. Получаемые при этом формулы называются совершенными дизъюнктивными нормальными формами, сокращенно СДНФ. Считается, что СДНФ тождественного нуля – это «пустая» дизъюнкция, не содержащая ни одного дизъюнктивного слагаемого.
Двойственная конструкция приводит к представлению функции в так называемой совершенной конъюнктивной нормальной форме, сокращенно СКНФ. СКНФ рассмотренной ранее функции имеет следующий вид:
Каждый из пяти конъюнктивных членов (множителей) соответствует набору значений аргументов, для которого функция принимает значение 0. Каждый множитель содержит все три аргумента функции; отрицанием снабжены те из них, которые имеют значение 1 в соответствующем наборе. Так, набору (0,0,1) соответствует множитель xyz’, набору (0,1,0) – множитель xy’z, и т. д. Каждый из конъюнктивных членов принимает значение 0 на своем наборе значений переменных и значение 1 – на всех остальных. Конъюнкция этих трех множителей принимает значение 0 лишь тогда, когда значение 0 принимает хотя бы один из множителей. Таким образом, функция в правой части записанного равенства принимает значение 0 на тех же трех наборах значений аргументов, что и функция f.
Описанный выше способ построения СДНФ и СКНФ опирается на следующую теорему о разложении функции по переменной.
Теорема.Пусть f(x1,x2,…,xn) – произвольная булева функция. Тогда
Доказательство. Докажем первую формулу. Чтобы не загромождать выкладки индексами и многоточиями, ограничимся случаем функции от двух переменных. Доказываемая формула принимает следующий вид:
f(x,y) = x⋅f(1,y) ∨ x’⋅f(0,y).
При любом y подстановка в правую часть x=1 и x=0 дает соответственно
Таким образом, левая и правая части доказываемого равенства совпадают на любом наборе значений аргументов. Следовательно, функции слева и справа от знака равенства равны. На общий случай доказательство распространяется практически без изменений. Достаточно считать, что y обозначает не одну переменную, а набор переменных. Второе равенство из формулировки теоремы доказывается аналогично (впрочем, его справедливость следует из принципа двойственности).
Последовательно применяя несколько раз (по числу переменных) разложение из предыдущей теоремы, можно получить СДНФ булевой функции. Например,
Функция f(x,y) представлена в виде дизъюнкции четырех дизъюнктивных членов. Те из них, для которых коэффициент f(α,β) равен нулю, можно отбросить. В результате получится СДНФ. Например, для функции f(x,y)=x⊕y имеем f(0,0)=f(1,1)=0 и f(0,1)=f(1,0)=1, поэтому
x⊕y=x⋅y’ ∨ x’⋅y.
Элементарной конъюнкцией (конъюнктом) называют конъюнкцию переменных и/или их отрицаний, в которой каждая переменная встречается не более одного раза.
Например, x’yz, x’y – конъюнкты. Пустой конъюнкт (в который не входит ни одна переменная) считается равным 1. Дизъюнктивной нормальной формой (сокращенно ДНФ) называется дизъюнкция конечного числа конъюнктов. Ясно, что любая СДНФ является ДНФ. Характеристический признак СДНФ – в каждый из ее конъюнктов входят все переменные. Например, x’yz∨y’ – это ДНФ, не являющаяся совершенной. Представление булевой функции в виде СДНФ с точностью до порядка конъюнктов однозначно. При отказе от совершенности формы однозначность представления пропадает. Вообще говоря, одну и ту же булеву функцию можно представить разными способами в виде ДНФ.
Двойственным образом определяются конъюнктивные нормальные формы (КНФ). Элементарной дизъюнкцией (дизъюнктом) называют дизъюнкцию переменных и/или их отрицаний, в которой каждая переменная встречается не более одного раза. Пустой дизъюнкт считается равным 0. Конъюнктивной нормальной формой называется конъюнкция конечного числа дизъюнктов.
