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

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. Перечисленные свойства называются свойствами совершенства.