Тема 2 Формулы алгебры логики

2.1 Равносильные формулы алгебры логики

2.2 Законы алгебры логики

Как и в элементарной математике из «элементарных» булевых функций с помощью логических операций можно строить формулы. В настоящем разделе изучаются формулы алгебры логики.

2.1 Равносильные формулы алгебры логики. Приведем определение формулы алгебры логики.

1) каждая «элементарная» булева функция – формула;

2) если некоторое выражение N есть формула, то тоже формула;

3) если некоторые выражения M и N есть формулы, то выражения , , , тоже формулы;

4) других формул, кроме построенных по п. п.1), 2), 3), нет.

Формулы алгебры логики мы будет обозначать большими N, M, … Например, следующие выражения являются формулами алгебры логики:

, .

С целью упрощения формул, условимся, что операция конъюнкции «сильнее» операции дизъюнкции, импликации и эквивалентности, т. е. если нет скобок, то вначале выполняется операция конъюнкции.

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

Две формулы N и M называются Равносильными, если они определяют одну и ту же булеву функцию (запись N=M будет означать, что формулы N и M равносильны).

Пример 1. Формулы и равносильны, т. е. .

Действительно, построим таблицы истинности для данных формул.

0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

Из таблицы видно, что формулы и определяют одну и ту же булеву функцию и, следовательно, являются равносильными.

Очевидно, что отношение равносильности формул алгебры логики является:

1. рефлексивным, т. е. N=N для любой формулы N;

2. симметричным, т. е. если N=M, то M=N для любых формул N и M;

3. транзитивным, т. е. если N=M и M=J, то N=J для любых формул N, M,J.

Таким образом, отношение равносильности является отношением эквивалентности.

Если какую-нибудь формулу N1, являющуюся частью формулы N заменить формулой N2, равносильной N1, то полученная формула окажется равносильной N. Это свойство лежит в основе преобразования формул с целью их упрощения или приведения к определенной форме.

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

2.2 Законы алгебры логики. Приведем перечень важнейших равносильностей (законов) алгебры логики. Эти равносильности выражают свойства логических операций.

1. - закон тождества;

2. - закон противоречия;

3. - закон исключительного третьего;

4. - закон двойного отрицания;

5. , - законы идемпотентности;

6. , - законы коммутативности;

7. , - законы дистрибутивности;

8. , - законы ассоциативности;

9. , - законы де Моргана;

10. ,

11. ,

12. , - законы поглощения;

13. , - законы склеивания.

Перечисленные законы алгебры логики доказываются с помощью таблицы истинности. В качестве примера докажем справедливость закона .

0	0	0	0	0	0	0	0
0	0	1	0	0	0	1	0
0	1	0	0	0	1	0	0
0	1	1	1	1	1	1	1
1	0	0	0	1	1	1	1
1	0	1	0	1	1	1	1
1	1	0	0	1	1	1	1
1	1	1	1	1	1	1	1

Из таблицы видно, что формулы и определяют одну и ту же булеву функцию. Следовательно, они равносильны.

Логические операции – конъюнкция, дизъюнкция, импликация и эквивалентность, вообще говоря, не являются независимыми друг от друга. В самом деле,

,

,

Первые две равносильности легко доказываются с помощью таблиц истинности. Две последние равносильности докажем с помощью законов де Моргана и двойного отрицания:

; .

Итак, справедливы следующие утверждения:

1) импликацию и эквивалентность можно выразить через конъюнкцию, дизъюнкцию и отрицание;

2) конъюнкцию можно выразить через дизъюнкцию и отрицание;

3) дизъюнкцию можно выразить через конъюнкцию и отрицание;

4) все операции посредством равносильных выражений можно заменить двумя: конъюнкцией и отрицанием или дизъюнкцией и отрицанием.

Естественно возникает следующий вопрос. Для чего вводить пять логических операций, когда можно обойтись двумя? Использование лишь двух операций существенным образом усложнило бы запись, что привело бы к громоздким формулам. Однако в некоторых приложениях математической логики удобно ограничиться двумя операциями. Аналогичная ситуация имеет место в арифметике. Всякое натуральное число можно записать с помощью цифр 0 и 1. Однако записи чисел и выкладки в двоичной системе громоздки. К этой системе прибегают лишь в некоторых случаях.

Множество булевых функций, рассматриваемое вместе с операциями отрицания, конъюнкции и дизъюнкции, называют Булевой алгеброй. Законы 1-13 являются Основными законами булевой алгебры.

Обратим внимание на характер соответствий между равносильностями, объединенными в пару под номерами (5-13). В этих соответствиях проявляется так называемый закон двойственности.

Назовем формулу алгебры логики Двойственной к формуле , если =.

Будем говорить, что операция конъюнкции двойственна операции дизъюнкции и наоборот.

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

Например, формула двойственная к формуле , а формула двойственная к формуле .

Теперь сформулируем закон двойственности.

Теорема 2. Если формулы алгебры логики N и M равносильны, то и двойственные им формулы N* и M* равносильны.

Докажем данный закон. Пусть N(X1,X2,…,XN) = M(X1,X2,…,XN). Согласно определению двойственной формулы

и .

Так как N(X1,X2,…,XN) и M(X1,X2,…,XN) принимают одинаковые значения при любых значениях переменных X1,X2,…,XN, то

=.

Отсюда следует, что

.

Так как формулы и равносильны соответственно формулам и , то они равносильны между собой.

Принцип двойственности позволяет сократить усилие на вывод равносильностей.

Пример 2. Из равносильности вытекает равносильность . Из равносильности вытекает равносильность .

< Предыдущая		Следующая >