1.3 Представление функции в виде совершенной дизъюнктивной и совершенной конъюнктивной формах. Разложение функции по начальному множеству переменных.

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

x1	x2	x3	f
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	0

Доказательство:

Свойства

1)

2)

Чтобы доказать теорему покажем выполнение данного равенства на любом двоичном наборе ,то есть что левые и правые части совпадают для любого двоиного набора:

.

. То есть левая часть равенства равна 1. Покажем,что и правая часть равенства также равна 1 на данном наборе. Для этого достаточно показать,что хотя бы одно слагаемое правой части равно 1.

Таким слагаемым будет слагаемое, которое соответствует единичному набору , совпадающего с набором .

.

Значение этого слагаемого на наборе есть

в силу того ,что значение каждого множителя равно 1. Последнее справедливо в силу свойства символа .

. То есть левая часть равна 0. Покажем, что и правая часть также равна 0. Для этого нужно показать, что значение всех слагаемых равно 0. Рассмотрим произвольное слагаемое правой части, которое соответствует некоторому двоичному набору , тогда в силу, того, что наборы  и  различны, т.к.  - набор, на котором значение функции равно 0, а  - набор, на котором значение функции равно 1. Так как наборы различны, то существует множитель i: , а поэтому и все произведение равно 0.Таким образом каждое слагаемое равно 0, следовательно и вся сумма равна 0, значит правая часть равна 0.

Теорема полностью доказана.

x1	x2	x3	f
0	0	0	0	0	0	0	0
0	0	1	0	0	0	0	0
0	1	0	1	1	0	0	1
0	1	1	0	0	0	0	0
1	0	0	1	0	1	0	1
1	0	1	1	0	0	1	1
1	1	0	0	0	0	0	0
1	1	1	0	0	0	0	0

Теорема о разложении булевой функции по первым k-переменным.

Доказательство:

Рассмотрим произвольный набор значений переменных , и покажем, что левая и правая часть равны. Левая часть - .

В правой части рассмотрим слагаемое, в котором значение набора  совпадает с первыми k-компонентами набора : .

Значение этого слагаемого на наборе равно .

В силу того, что набор  и первые k-компонент набора  совпадают, рассматриваемые множители равны 1, все слагаемое равно . Все остальные слагаемые равны 0 в силу того, что среди множителей обязательно найдется множитель, в котором  и  различаются, а это нулевой множитель. Поэтому правая часть равна (все слагаемые, кроме быть может одного, равны 0).

Теорема доказана.

Нетрудно убедиться в справедливости следующих тождеств:

1. 6)

2. 7)

3. 8)

4. 9)

5. 10)

Доказательство предлагается в качестве домашних упражнений.

Последние два тождества называются правилами Де-Моргана.

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

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

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

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

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	0	0
0	1	1
1	0	0
1	1	0

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

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

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

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

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

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

Теорема о разложении булевой функции по первым k переменным .

Для любой булевой функции f(x₁…x_n) тождественно выполнено :

Доказательство. Рассмотрим произвольный набор . Значение левой части есть .

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

Тогда все произведение есть . Что и требовалось доказать.

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

Определение : Полиномом Жегалкина называется сумма по модулю 2 (+) некоторого количества слагаемых, где каждое слагаемое есть элементарная конъюнкция переменных без отрицания.

Пример:

1+x₁x₂+x₃+x₁x₄x₅

Полином Жегалкина, не содержащий ни одного слагаемого, равен 0.

Далее будем рассматривать так называемые приведенные полиномы Жегалкина, т.е. полиномы, в которых все слагаемые различные конъюнкции.

Например 1+x₁x₂+x₃+x₁x₄x₅ (нет двух одинаковых слагаемых).

Если некоторые слагаемые повторяются, то используя правило x+x=0, нетрудно привести любой полином к приведенному виду.

Н апример x₁x₂+x₃+x₁x₂+x₁x₄x₅+x₃=x₁x₄x₅

Если слагаемое повторяется нечетное количество раз, то оставляем его в единственном экземпляре.