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

Теорема. Пусть функция h (x ₁,..., x_n) реализована формулой h (x ₁,..., x_n) = g (G ₁,..., G_m) = g (f ₁(x ₁,..., x_n),..., f_m (x ₁,..., x_n)), где какие-то переменные могут быть фиктивными. Тогда

h *(x ₁,..., x_n) = g *(f ₁*(x ₁,..., x_n),..., f_m *(x ₁, …, x_n)), это означает, что если функция задана некоторой формулой, то, чтобы получить двойственную функцию, надо в этой формуле все знаки функций заменить на двойственные: на и наоборот, на ~ и наоборот, | на и наоборот, 0 на 1 и наоборот. Двойственная к находится следующим образом: .

Доказательство теоремы. h *(x ₁,..., x_n) = (,..., ) =

= (f ₁(,..., ),..., f_m (,..., )) =

= ( (,..., ),..., f_m (,..., )) =

= ((),...,(() =

= g *(f ₁*(x ₁,..., x_n),..., f_m *(x ₁,..., x_n)),

что и требовалось доказать.

Если функция h (x ₁,..., x_n) реализуется формулой N [ f ₁,..., f_n ], то формулу, полученную из N заменой f_i , входящих в нее, на f_i *, и реализующую функцию h *(x ₁,..., x_n), будем называть двойственной и обозначать N *(x ₁,..., x_n).

Пример 11. Найти двойственную функцию к .

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

.