Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Теорема: Пусть функция 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 Ú 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)).
Дата публикования: 2014-10-20; Прочитано: 355 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!