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

Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...

Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...

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

2017-09-26 374
Свойства элементарных функций 0.00 из 5.00 0 оценок
Заказать работу

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. – коммутативность связки *, где символ * является общим обозначением для связок (операций) &, Ú, Å, ~, |, ¯.

2. – ассоциативность связки *, где *– общее обозначение для связок &,Ú,Å,~.

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

а) – дистрибутивность конъюнкции относительно дизъюнкции;

б) – дистрибутивность дизъюнкции относительно конъюнкции;

в) – дистрибутивность конъюнкции относительно сложения по mod 2 (по модулю два).

4. а) ; б) суть правила де Моргана;

5. а) ; б) суть правила поглощения;

6. а) ; б) ;

7. а) ; б) ;

в) ; г) ; д) ;

8. а) ;

б) ; в) ;

9. а) ; б) .

 

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

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.

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

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

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.

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

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

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

x f f *
     

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

x f f * g g *
         

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

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

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

x 1 x 2 x 3 f f *
         

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

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

 

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        

 

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

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


Поделиться с друзьями:

Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...

Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...

Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...

Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.014 с.