Нормальные формы. Многочлены Жегалкина

Решение задач

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

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

Определение. Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция простых конъюнкций.

Например, выражение xy ∨ yz является ДНФ.

Определение. Совершенной дизъюнктивной нормальной формой (СДНФ) называется такая дизъюнктивная нормальная форма, у которой в каждую конъюнкцию входят все переменные данного списка (либо сами, либо их отрицания), причём в одном и том же порядке.

Например, выражение x y y является ДНФ, но не СДНФ, а выражение

x y z ∨ x⋅ y ⋅ z ∨ x y z является СДНФ.
Определение. Простой дизъюнкцией называется дизъюнкция одной или нескольких переменных, при этом каждая переменная (либо сама, либо её отрицание) входит в дизъюнкцию не более одного раза.

Например, выражение x ∨ y ∨ z является простой дизъюнкцией.

Определение. Конъюнктивной нормальной формой (КНФ) называется конъюнкция простых дизъюнкций.

Например, выражение (x ∨ y ∨ z ) ( x ∨ z ) ( y ∨ z ) является КНФ.

Определение. Совершенной конъюнктивной нормальной формой (СКНФ) называется такая КНФ, у которой в каждую простую дизъюнкцию входят все переменные данного списка (либо сами, либо их отрицания) причём в одном и том же порядке.

Например, выражение (x ∨ y ∨ z ) ( x ∨ y ∨ z ) ( x ∨ y ∨ z ) является СКНФ.

Теорема 2.1. Всякая булева функция (кроме 0) имеет единственную СДНФ.

Следствие. Всякая булева функция может быть выражена через дизъюнкцию, конъюнкцию и отрицание. В частности, x ∧ x = 0 .

Теорема 2.2. Всякая булева функция (кроме 1) может быть единственным образом представлена в виде СКНФ.

Алгоритм построения СДНФ булевой функции по заданной таблице истинности

Берём только те наборы переменных (x1 , x2 ,..., xn ) , для которых f (x1 , x2 ,..., xn) = 1 и составляем простую конъюнкцию для этого набора так: если xi = 0 , то берём в этой конъюнкции xi , если xi = 1, то берём xi . Составляя дизъюнкцию этих простых конъюнкций, придём к СДНФ.

По аналогии с представлением любой функции (не равной 0) в виде СДНФ можно любую функцию (не равную 1), представить в виде СКНФ. А именно, простые дизъюнкции составляются для тех наборов переменных

(x1 , x2 ,..., xn), для которых f ( x1 , x2 ,..., xn ) = 0, причём если в наборе xi = 1, то в простую дизъюнкцию включаем xi , если же xi = 0 , то в неё включаем xi .

Задача 2.1. Составим СДНФ и СКНФ для импликации и сложения по модулю два.

Решение.

СДНФ для этих функций имеет вид x → y = x ⋅ y ∨ x y ∨ x y; x ⊕ y = x y ∨ x y.

СКНФ для этих функций будет иметь вид x → y = x ∨ y; x ⊕ y = (x ∨ y ) ( x ∨ y ).

Определение. Разложением булевой функции f ( x1 , x2 ,..., xn ) по переменной x1 называется её представление в виде

f x1 f ( 0, x2, x3, . . . , xn) ∨ x1 f (1, x2, x3, . . . , xn).

Определение. Разложением булевой функции f ( x1 , x2 ,..., xn ) по двум переменным x1 и x2 называется её представление в виде

f = x1 ⋅ x2 f (0,0, x3 ,..., xn ) ∨ x1 ⋅ x2 f (0, 1, x3 ,..., xn ) ∨ x1 ⋅ x2 f (1, 0, x3 ,..., xn ) ∨ x1 ⋅ x2 ⋅ f (1, 1, x3 ,..., xn )

Определение. Полиномом (многочленом) Жегалкина от n переменных называется функция вида

f ( x1, x2 , . . . , xn) = a0 ⊕ a1x1 ⊕ a2x2 ⊕ ... ⊕ anxn ⊕ an+1x1x2 ⊕ . . . ⊕ an+C2n xn-1 xn ⊕ . . . ⊕ a 2n-1x1x2. . . xn

Всего здесь 2n слагаемых, коэффициенты a0 a1, . . . , a2n-1 являются константами (равными нулю или единице), «» означает сложение по модулю 2, каждый одночлен представляет собой конъюнкцию входящих в него переменных и констант.

Теорема 2.3. Любой многочлен Жегалкина может быть приведён к каноническому виду.

Доказательство теоремы опирается на:

  1. дистрибутивный закон a ⋅ ( b ⊕ c ) = a ⋅ c + b ⋅ c ;
  2. правило приведения подобных
  3. закон идемпотентности

Теорема 2.4. Любая булева функция n переменных может быть един-

ственным образом представлена полиномом Жегалкина.
Доказательство проводится с помощью формул: a = a ⊕ 1, a ∨ b = a ⊕ b ⊕ ab .


Способы построения полинома Жегалкина:

а) Пусть логическая функция f (x1 , x2 ,..., xn ) задана своей таблицей истинности.

Представляем нашу функцию в виде полинома Жегалкина с неопределёнными коэффициентами. По очереди подставляем всевозможные наборы переменных и находим коэффициенты полинома из получающихся уравнений. Так как чис- ло наборов равно числу коэффициентов (и равно 2n ), то последние определяются однозначно.

б) Этот способ основан на том, что x ⊕ 1 = x и применяется для функций, заданных в виде ДНФ. А именно, если функция задана в виде ДНФ, то сначала убираем дизъюнкцию, используя одно из правил де Моргана, а все отрицания заменяем сложением по модулю 2 с единицей. После этого раскрываем скобки по обычным правилам, при этом учитываем, что чётное число одинаковых слагаемых равно нулю (так как x ⊕ x = 0 ), а нечётное число одинаковых слагаемых равно одному такому слагаемому.

Задача2.2. Найти полином Жегалкина функции f ( x, y, z ) = xy ∨ xy ∨ yz.

Решение.

1 способ.

Составим таблицу истинности данной функции.

Разложим полученную функцию по переменной x . Из последнего столбца таблицы истинности получим

Последнее выражение и есть полином Жегалкина данной функции.

2 способ.

 

Задачи для самостоятельного решения

Заданы булевы функции fi ( x, y, z ):

  1. f1 ( x, y, z ) = (( x| y) ↓ z) ↔ (x ⊕ y );
  2. f2 ( x, y, z ) = ( x + y ) | ( x ↔ yz )
  3. f3 ( x, y, z ) = (x ∨ y ) ∨ xz ↓ ( x ↔ y );
  4. f4 ( x, y, z ) = (( x ↔ z ) ⊕ y ) ⋅ ( x | yz );
  5. f5 ( x, y, z ) = ( x ∨ y ) z → ( x ⊕y );
  6. f6 ( x, y, z ) = (x → y ) ∨ (x → zy ) ;
  7. f7 ( x, y, z ) = (( x → y) → z)|(x ⊕ y);
  8. f8 ( x, y, z ) = x → ( z ↔ ( y ⊕ xz)) ;
  9. f9 ( x, y, z ) = ( x ∨ y ∨ z ) → x|y ;
  10. f10 ( x, y, z ) = (x ∨ y ) z → (( x ↓ y) | z ).

Для заданных булевых функций требуется:
а) составить таблицу истинности;
б) написать СДНФ и СКНФ (если это возможно);
в) найти по таблице истинности полином Жегалкина.