Принцип двойственности. Теорема:Пусть функция h(x1, , xn) реализована формулой h(x1, , xn) = =g(G1, , Gm) = g(f1(x1
Теорема:Пусть функция 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)* и (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)).
Дата добавления: 2016-03-27; просмотров: 719;