Принцип двойственности. Теорема:Пусть функция 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Úzt( Ú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; просмотров: 666;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.008 сек.