Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Принцип двойственности. Теорема:Пусть функция h(x1, , xn) реализована формулой h(x1, , xn) = =g(G1, , Gm) = g(f1(x1



Теорема: Пусть функция h (x 1,..., xn) реализована формулой h (x 1,..., xn) = = g (G 1,..., Gm) = g (f 1(x 1,..., xn),..., fm (x 1,..., xn)), где какие-то переменные могут быть фиктивными. Тогда h *(x 1,..., xn) = g *(f 1*(x 1,..., xn),..., fm *(x 1, …, xn)), это означает, что если функция задана некоторой формулой, то чтобы получить двойственную функцию, надо в этой формуле все знаки функций заменить на двойственные, 0 на 1, 1 на 0.

Доказательство. h *(x 1,..., xn) = ( 1,..., n) = (f 1( 1,..., n),..., fm ( 1,..., n)) = ( 1( 1,..., n),..., ( 1,..., n)) = ((),..., (() = g *(f 1*(x 1,..., xn),..., fm *(x 1,..., xn)), что и требовалось доказать.

Если функция h (x 1,..., xn) реализуется формулой N [ f 1,..., fn ], то формулу, полученную из N заменой fi, входящих в нее, на fi * и реализующую функцию h *(x 1,..., xn), будем называть двойственной и обозначать N *(x 1,..., 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)).





Дата публикования: 2014-10-20; Прочитано: 355 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.008 с)...