Теорема о представлении любой булевой функции в виде СКНФ

Теорема о представлении булевой функции в виде конъюнктивной нормальной формы.

Определение.

Двойственной к функции называют функцию .

Например, двойственной к конъюнкции является

дизъюнкция, и наоборот, двойственной к дизъюнкции является конъюнкция.

0 0 0 0

0 1 0 1

1 0 0 1

1 1 1 1

Утверждение. Двойственной к двойственной функции есть сама функция, т.е.

КНФ называют логическое произведение некоторых сомножителей, где каждый сомножитель есть элементарная дизъюнкция. КНФ от переменных {x₁…x_n} называется СКНФ, если каждая дизъюнкция полного ранга, то есть в каждую дизъюнкцию входят все n переменных.

Пример: { x₁ x₂ x₃ }

КНФ:

СКНФ:

Пример:

x1	x2	f
0
1
1

Доказательство: рассмотрим произвольный набор значений переменных . Либо , либо .

1) Левая часть равенства равна 1. Покажем, что и правая часть равна единице. Рассмотрим произвольный множитель правой части . Значение этого множителя на наборе равно т.к. существует i такое, что , что верно в силу того, что a - набор, на котором значение f (a) = 1, а s - набор, на котором значение f(s)= 0, то есть a и s - два различных набора, а поэтому есть компонента, в которой они отличаются.

Поэтому ; т.к. , .

2) Пусть . Покажем, что и правая часть равна 0. Для этого достаточно показать, что существует множитель, который равен 0 на наборе a. Действительно, рассмотрим множитель соответствующий набору правой части , который совпадает с набором .

В силу того, что есть ноль функции, набор существует. Тогда значение рассматриваемого множителя на наборе a равно

(т. к. для всех i: ). А так как существует множитель, равный 0, то и значение всей СКНФ = 0.

Дата добавления: 2017-01-13