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

Для любой булевой функции 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₅

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

1.4 Утверждение о представлении двоичной функции в виде полинома Жегалкина .

Для любой булевой функции существует представление в виде полинома Жегалкина и это представление единственно.

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

Пример 1:

Первая часть теоремы следует из теоремы о представлении булевой функции в виде СДНФ. А именно рассмотрим для булевой функции ее СДНФ. Далее операцию выразим через операцию по правилу Де Моргана .

После чего операцию выразим через операцию и приведем полученную формулу к нормальному виду полинома Жегалкина раскрыв скобки в полученном выражении, используя дистрибутивность конъюнкции по отношению к сумме по модулю два. Для функции из примера1 СДНФ имеет вид :

Покажем, что полученный полином единственен с точностью до перестановки слагаемых и множителей в слагаемых полинома.

Допустим противное : , которая имеет два различных полинома Жегалкина:

Из этих равенств следует,что

прибавим к обеим частям равенства :

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

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

Упражнение: найдите полином Жегалкина следующих функций :

1) 4)

2) 5)

3) 6)