|
Определение 1. Функции F*(X1, ..., Xn) называется двойственной к функции F(X1, ..., Xn), если F*(X1, ..., Xn) =  (  1, ..., N).
Пример 1. Покажем с помощью таблицы истинности, что константа 0 двойственна к 1:
Функции F(X) = X и G(X) =  двойственны сами себе:
|
X
|
F
|
F*
|
G
|
G*
|
|
0
1
|
0
1
|
0
1
|
1
0
|
1
0
|
Так как F*(0)=  (1).
Определение 2. Если F*(X1, ..., Xn) = F(X1, ..., Xn), то F(X1, ..., Xn) называется самодвойственной.
Пример 2. Покажем, что F(X1,X2,X3)=X1ÅX2ÅX3 – самодвойственна:
|
X1
|
X2
|
X3
|
F
|
F*
|
|
0
0
0
0
1
1
1
1
|
0
0
1
1
0
0
1
1
|
0
1
0
1
0
1
0
1
|
0
1
1
0
1
0
0
1
|
0
1
1
0
1
0
0
1
|
Если F*– самодвойственна, то  (  1, ...,  n) = F(X1, ..., Xn), т. е. на противоположных наборах функция принимает противоположные значения.
Пример 3. Покажем, что функция Х1ÚХ2 двойственна к X1&X2, функция Х1 Х2 двойственна к функцииX1|X2.
|
X1 X2
|
F=Х1ÚХ2
|
F*
|
G=X1|X2
|
G*=X1  X2
|
|
0 0
0 1
1 0
1 1
|
0
1
1
1
|
0
0
0
1
|
1
1
1
0
|
1
0
0
0
|
Теорема о двойственных функциях
Если F* двойственна к F, то F двойственна к F*.
Доказательство. F*(X1, ..., Xn) = (  1, ..., N). Найдем двойственную функцию к F*, т. е. (F*( X1, ...,Xn))* = (  (  1, ..., N))* =  (  1, ...,  N) = F(X1, .., Xn).
Предположим, что функция задана формулой. Можно ли найти по этой формуле двойственную функцию? Ответ на этот вопрос дает следующая теорема.
Принцип двойственности
Теорема: Пусть функция 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
|
0
1
1
0
|
1
0
0
1
|
1
1
0
1
|
0
1
0
0
|
Из таблиц видно, что
(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)).
Лемма о несамодвойственной функции
Подстановкой функций  и в несамодвойственную функцию можно получить одну из констант.
Доказательство. Пусть  – несамодвойственная функция. Тогда существует набор  , для которого  . Построим функцию  , заменив единицы в  на  , а нули – на . Так как  , то  . Заметим, что  .
Тогда  , т. е.  . Следовательно, функция есть одна из констант.
Эквивалентность формул и нормальные формы
|
