Принцип двойственности.

Если формула U [ f₁,…,f_n ]реализует функцию f, то формула U^*=U [ f₁^*,…,f_n^* ], т.е. формула, имеющая то же строение, что и формула U, но в которой знаки операций f₁,…,f_s заменяются соответственно на знаки двойственных им функций f₁^*,…,f_s,^* соответственно,реализует функцию f^*.

Следствие. Если в формуле булевой функции используются только знаки булевых функций &, Ú, Ø, 1 и 0, то для получения формулы двойственной функции необходимо заменить знак & на знак Ú, Ú на &, 1 на 0 и 0 на 1.

Пример.

Пусть f(x,y,z)=xÚy& . Тогда согласно принципу двойственности справедливо f^*(x,y,z)=x&(yÚ ).

 

Запишем СДНФ для функции f^*(x₁,..,x_n):

.

(2.4)

Из определения функции f^*(x₁,..,x_n) справедливо: .

Рассмотрим функции, двойственные к функциям, стоящим в левой и правой частях равенства (2.4). Согласно следствию из принципа двойственности, в правой части нужно заменить знак Ú на &, & наÚ. Тогда получим

Справедливо .

Переобозначив параметр , получим окончательный вариант равенства:

.

Тем самым теорема доказана.

Пример.

Пусть (табл.2.12). Существует два набора (s₁,s₂) значений переменных, на которых f(x₁,x₂) принимает значение 0. Это наборы (0,1) и (1,0). Отсюда, согласно (2.3), получим – СКНФ функции (x₁ «x₂).

 

Логическим полиномом или полиномом Жегалкина называется формула (выражение), которая содержит только операции , &, возможно, константы 0, 1 и не содержит скобок. Иначе говоря, логический полином – это выражение следующего вида:

, где i {1, 2, …, n}, j {1, 2, …, s},

может принимать значения либо 0, либо 1.

Пример. 1) 1.

Здесь =1, =1, =0, =1.

2) 1.

Здесь =1, =1.

Из определения следует, что полином Жегалкина для функции двух переменных имеет следующий общий вид:

.

Для функции трех переменных полином Жегалкина имеет вид:

.