Принцип двойственности
Теорема: Пусть функция h(x1, ..., xn) реализована формулой h(x1, ..., xn) = =g(G1, ..., Gm) = g(f1(x1, ..., xn), ..., fm(x1, ..., xn)), где какие-то переменные могут быть фиктивными. Тогда h*( x1, ..., xn) = g*(f1*( x1, ..., xn), ..., fm*(x1, …, xn)), это означает, что если функция задана некоторой формулой, то чтобы получить двойственную функцию, надо в этой формуле все знаки функций заменить на двойственные, 0 на 1, 1 на 0.
Доказательство. h*(x1, ..., xn) = 
(
1, ..., n) = 
(f1(1, ..., n), ..., fm(1, ..., n)) = 
(
1(1, ..., n), ..., 
(1, ..., n)) = g((
), ..., ((
) = g*(f1*( x1, ..., xn), ..., fm*( x1, ..., xn)), что и требовалось доказать.
Если функция h(x1, ..., xn) реализуется формулой N[f1, ..., fn], то формулу, полученную из N заменой fi, входящих в нее, на fi* и реализующую функцию h*(x1, ..., xn), будем называть двойственной и обозначать N*(x1, ..., xn).
Пример 4. Построить формулу, реализующую f*, если f = ((x
y) Ú z) (y
(xÅyz)). Покажем, что она эквивалентна формуле N = z(xÅy).
Найдем (xÅy)* и (xy)*.
| x y | xÅy | (xÅy)* | x y
| (xy)*
|
| 0 0 0 1 1 0 1 1 |
Из таблиц видно, что
(x
y)* = x ~ y = 
= xy1, xy =
yx
,
(xy)* =
y xy =
y.
По принципу двойственности:
f* = 
yz(
(x(yz)1)) = 
yz
z(x(yz)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)).