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

Теорема: Пусть функция 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, 1 на 0.

Доказательство. h *(x ₁,..., x_n) = ( ₁,..., _n) = (f ₁( ₁,..., _n),..., f_m ( ₁,..., _n)) = ( ₁( ₁,..., _n),..., ( ₁,..., _n)) = g ((),..., (() = 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).

Пример 4. Построить формулу, реализующую f *, если f = ((x y) Ú z) (y (x Å yz)). Покажем, что она эквивалентна формуле N = z (x Å y).

Найдем (x Å y)* и (x y)*.

x y	x Å y	(x Å y)*	x y	(x y)*
0 0 0 1 1 0 1 1

Из таблиц видно, что

(x y)* = x ~ y = = x y 1, x y = y x ,

(x y)* = y x y = y.

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

f * = yz ( (x (y z) 1)) = yz z (x (y z) 1) = z ( y Ú ( x Å z Å )) = z ( y Ú (x Å z Å 1)) = z ( y Ú (x Å )) = z y Ú (z x Å z ) = z ( y Ú x ) = z (x Å y).

Тогда f = (f *)* = [ z (x Å y)]* = z Ú (x ~ y).

Пример 5. Найти формулу для f* и показать, что она эквивалентна формуле N = (x Ú (z Å t)) , если f = (xyz ~(t Ú x ))Ú t.

f * = ((x Ú y Ú z)Å t ( Ú y))( Ú t) = ( t ( Ú y)Ú (x Ú y Ú z) )( Ú t) =

= ( t Ú (x Ú y Ú z)( Ú x ))( Ú t) = t Ú (x Ú y Ú z)( Ú x Ú tx ) =

= t Ú (x Ú y Ú z)( Ú x ) = ( x Ú t Ú z Ú x Ú xz) = ( t Ú x Ú z Ú xz)

= (x Ú (z Å t)).