Формулы равносильности.

1) Коммутативность

АVВ º ВVА А&В º В&А

 

2) Ассоциативность

АV(ВVС) º (АVВ)VС А&(В&С) º (А&В) &С

 

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

АV(В&С) º (АVВ)&(АVС) А&(ВVС) º (А&В)V(А&С)

 

4) Идемпотентность

АVА º А А&А º А

 

5) Поглощение

АV(А&В) º А А&(АVВ) º А

 

6) Закон де Моргана

º & º V

 

7) Закон исключающий третьего

АV1 º 1 А&1 º A

8) Закон противоречия

AVÆ º A A&Æ º Æ

 

9) Закон двойного отрицания

º A

 

10) º 1 , º 0

11) A®B ºVB

12) A«B º (A®B)&(B®A)

13) AÅB º A& V &B

14) A | B º º V

15) A¯B º º &

 

ПРИМЕР

 

Доказать:

Представление произвольной функции алгебры логики в виде формулы алгебры логики

Пусть - произвольная функция алгебры логики переменных.

Рассмотрим формулу

(2.1)

которая составлена следующим образом: каждое слагаемое этой логической суммы представляет собой конъюнкцию, в которой первый член является значением функции при некоторых определенных значениях переменных , остальные же члены конъюнкции представляют собой переменные или их отрицания. При этом под знаком отрицания находятся те и только те переменные, которые в первом члене конъюнкции имеют значение 0..

Вместе с тем формула (2.1) содержит в виде логических слагаемых всевозможные конъюнкции указанного вида.

Ясно, что формула (2.1)полностью определяет функцию . Иначе говоря, значения функции и формулы (2.1) совпадают на всех наборах значений переменных . То есть функция

Составление формул по таблице истинности. может быть представлена в виде:

(2.2)

 

ПРИМЕР Пусть функция имеет следующую таблицу истинности:

 

Тогда функция может быть определена в следующем виде:

Нетрудно заметить, что для определении функции берутся только те наборы переменных , при которых функция принимает значения 1, что значительно упрощает процедуру определения функции .

 

Формула (2.1) обладает свойствами:

1. Каждое логическое слагаемое формулы содержит все переменные , входящие в функцию .

2. Все логические слагаемые формулы различны.

3. Ни одно логическое слагаемое формулы не содержит одновременно переменную и ее отрицание.

4. Ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды.

5. Перечисленные свойства называются свойствами совершенства.