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



Мы поможем в написании ваших работ!


Мы поможем в написании ваших работ!



Мы поможем в написании ваших работ!


ЗНАЕТЕ ЛИ ВЫ?

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



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) (табл.2.12).

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

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

 

Таблица 2.12

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

 

Следствия из свойств элементарных функций

1. Законы склеивания:

xyÚx =x(yÚ )=x 1=x (дистрибутивность & относительно Ú);

(xÚy)&(x )=x y =xÚ 0=x (дистрибутивность Ú относительно &).

2. Законы поглощения:

xÚxy=x(1Úy)=x 1=x; x&(xÚy)=xÚxy=x.

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

 

Пример 2.7

Упростим формулы:

1. x2x3Úx1 2x3 = x3(x2Úx1 2) = x3((x2Úx1)&(x2Ú 2)) = (x1Úx2)x3.

2. x1Ú 1x2Ú 1 2x3Ú 1 2x3x4=x1Ú 1(x2Ú 2 3x4)=x1Ú 1

(x2Úx3Ú 2 3x4)=(x1Ú 1)(x1Úx2Úx3Ú 2 3х4)=x1Ú(x2Úx3)Ú( )x4= =x1Ú(x2Úх3Ú( ))(x2Úx3Úx4) = x1Úx2Úx3Úx4.

 

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

 

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

Пример 2.8. Покажем с помощью таблицы истинности

(табл. 2.13) что константа 0 двойственна к 1.

 

Таблица 2.13

x f f*

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

так как f*(0)= (1).

Таблица 2.14

x f f* g g*

Определение 2.8. Если f*(x1, ..., xn) = f(x1, ..., xn), то f(x1, ..., xn) называется самодвойственной.

Если f*– самодвойственна, то ( 1, ..., n) = f(x1, ..., xn), т.е. на противоположных наборах функция принимает противоположные значения.

 

Пример 2.9.Покажем, что f(x1,x2,x3)=x1Åx2Åx3 – самодвойственна (табл. 2.15).

Таблица 2.15

x1 x2 x3 f f*

 

 

Пример 2.10. Покажем, что функция х1Úх2 двойственна к x1&x2, функция х1 х2 двойственна к функции x1|x2 (табл. 2.16).

 

 

Таблица 2.16

x1 x2 f=х1Úх2 f* g=x1|x2 g*=x1 x2
0 0 0 1 1 0 1 1

 

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

Если f* двойственна к f, то f двойственна к f*.

Доказательство. f*(x1, ..., xn) = ( 1, ..., n). Найдем двойственную функцию к f*, т.е. (f*( x1, ..., xn))* = ( ( 1, ..., n))* = ( 1, ..., n) = f(x1, .., xn).

Предположим, что функция задана формулой. Можно ли найти по этой формуле двойственную функцию? Ответ на этот вопрос дает следующая теорема.

 

 

Теорема 2.2.О принципе двойственности

Пусть функция 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*(f1*( x1, ..., xn), ..., fm*

( x1, ..., xn)), что и требовалось доказать.

Если функция h(x1, ..., xn) реализуется формулой N[f1, ..., fn], то формулу, полученную из N заменой fi, входящих в нее, на fi* и реализующую функцию h*(x1, ..., xn), будем называть двойственной и обозначать N*(x1, ..., xn).

Пример 2.11. Построить формулу, реализующую f*, если f = =((x y) Ú z) (y (xÅyz)). Покажем, что она эквивалентна формуле N=z(xÅy).

Найдем (xÅy)* и (x y)*.

Таблица 2.17

x y xÅy (xÅy)* x y (x y)*
0 0 0 1 1 0 1 1

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

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

 

Разложение булевой функции по переменным

Обозначим xs=

Посмотрим, чему равно xs при разных значениях x и s (табл. 2.18).

 

Таблица 2.18

x\s

 

Из табл. 2.18 следует: xs=1 тогда и только тогда, когда x=s.



Последнее изменение этой страницы: 2016-07-14; просмотров: 96; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.81.89.248 (0.007 с.)