Главная | Обратная связь
МегаЛекции

Теорема о замене подформул на эквивалентные





 

Пусть NÎ<M> и имеет вид: N(x1, ..., xn) = g(G1, ...Gi, ...,Gm). Пусть подформула Gi~Gi¢, тогда формула N(x1, ..., xn) = g(G1, ...,Gi,...,Gm) эквивалентна формуле N¢(x1, ..., xn) = g(G1¢, ..., Gi¢, ...,G¢m).

Доказательство. Формулы N и N¢ эквивалентны, если реализуют одну и ту же функцию. Согласно построению функции, реализующей формулу имеем:

N(x1, ..., xn) = g(f1(x1, ..., xn ), ..., fi(x1, ..., xn), ..., fm(x1, ..., xn)),

N¢ (x1, ..., xn)= g(f1¢ (x1, ..., xn ), ..., fi¢(x1, ..., xn), ..., fm¢ (x1, ..., xn)).

По условию Gi~Gi¢, следовательно на наборе (a1, ..., an) имеем fi (a1, ..., an) = = fi¢(a1, ..., an) следовательно, на любом наборе (a1, ..., an)значения функции g(f1, ...,fi, ...,fm) и g(f1¢, ...,fi¢, ...,fm¢) совпадают. Получим N~N¢.

Некоторые свойства элементарных функций

 

1. Идемпотентность & и Ú: х&x=x , xÚx=x.

2. Коммутативность &,Ú,Å,|,~, .

3. Ассоциативность &,Ú,Å,~, поэтому в формулах вида xyz можно не ставить никаких скобок.

4. Дистрибутивность:

а) & по отношению к Ú: x&(yÚz)=xyÚxz ,

б) Ú по отношению к &: xÚ(y&z)=(xÚy)&(xÚz) ,

в) & по отношению к Å: x(yÅz)=xyÅxz .

5. Инволюция : =х .

6. Правило де Моргана: = & и = Ú .

7. Законы действия с 0 и 1:

xÚ0=x , xÚ1=1 , xÚ =1 , x&0=0 , x&1=x , x& =0 , xÅ1= , xÅ0=x.

8. Самодистрибутивность импликации: x (y z)=(x y) (x z).

Равенство всех этих формул доказывается по определению, т.е. по равенству функций, которые они реализуют.

 

 

Проверим для примера самодистрибутивность импликации : x (y z)=(x y) (x z).

x y z y z x (y z) x y x z

 

 

Принцип двойственности

Определение 1. Функции f*(x1, ..., xn) называется двойственной к функции f(x1, ..., xn), если f*(x1, ..., xn) = ( 1, ..., n).

Пример 1. Покажем с помощью таблицы истинности, что константа 0 двойственна к 1:

x f f*

 

Функции f(x) = x и g(x) = двойственны сами себе:

x f f* g g*

так как 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*

Если 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

 

Теорема о двойственных функциях

 

Если 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

Из таблиц видно, что

(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)).

 





Рекомендуемые страницы:

Воспользуйтесь поиском по сайту:
©2015- 2020 megalektsii.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.