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


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



ЗНАЕТЕ ЛИ ВЫ?

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



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. x 2 x 3Ú x 1 2 x 3 = x 3(x 2Ú x 1 2) = x 3((x 2Ú x 1)&(x 2Ú 2)) = (x 1Ú x 2) x 3.

2. x 1Ú 1 x 2Ú 1 2 x 3Ú 1 2 x 3 x 4= x 1Ú 1(x 2Ú 2 3 x 4)= x 1Ú 1

(x 2Ú x 3Ú 2 3 x 4)=(x 1Ú 1)(x 1Ú x 2Ú x 3Ú 2 3 х 4)= x 1Ú(x 2Ú x 3)Ú() x 4= = x 1Ú(x 2Ú х 3Ú())(x 2Ú x 3Ú x 4) = x 1Ú x 2Ú x 3Ú x 4.

 

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

 

Определение 2.7. Функция f *(x 1,..., xn) называется двойственной к функции f (x 1,..., xn), если f *(x 1,..., 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 *(x 1,..., xn) = f (x 1,..., xn), то f (x 1,..., xn) называется самодвойственной.

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

 

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

Таблица 2.15

x 1 x 2 x 3 f f *
         

 

 

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

 

 

Таблица 2.16

x 1 x 2 f = х 1Ú х 2 f * g = x 1| x 2 g *= x 1 x 2
0 0 0 1 1 0 1 1        

 

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

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

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

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

 

 

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

Пусть функция 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).

Пример 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; просмотров: 176; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

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