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

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