5.3 Основные равносильности алгебры логики
Пусть A, B, C – некоторые логические переменные. Приведем основные равносильности (законы) алгебры логики, называемые также законами теории множеств или свойствами операций над множествами:
законы (свойства) коммутативности:
, 
;
законы (свойства) ассоциативности:
, 
;
законы (свойства) дистрибутивности:
, 
;
законы де Моргана:
, 
;
свойства отрицания:
, 
;
свойство двойного отрицания:
;
свойства операций с одной переменной:
, 
;
свойства операций с логическими константами:
, 
,
,
.
Эти
свойства легко доказать, используя
таблицы истинности. Докажем, например,
первый из законов де Моргана. Для этого
составим таблицу истинности для левой
и правой частей формулы
(см. таблицу 5.5).
Таблица 5.5 – Таблица истинности для доказательства закона де Моргана
|
A |
B |
A & B |
|
|
|
|
|
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 |
Видно,
что таблицы истинности для формул
и
оказались одинаковыми. Значит, они
эквивалентны.
Часто применяются также следующие равносильности, которые можно также доказать с помощью таблиц истинности или вывести из основных равносильностей, указанных выше:
законы (свойства) поглощения:
, 
;
операция склеивания:
, 
;
операция неполного склеивания:
,
.
Докажем,
например, первое свойство поглощения.
Так как, по определению операции
конъюнкции, A
& 1 = A
(где A
– логическая переменная), выражение
можно записать так:
.
Затем следует воспользоваться законом дистрибутивности (или, проще говоря, вынести переменную A за скобки):
.
Так
как 1
B
= 1, значит,
=A
& 1 = A.
Таким образом, доказано, что
=A.
Кроме того, часто применяются формулы для перехода к операциям дизъюнкции, конъюнкции и отрицания от других операций:
A
→ B
=
B
A
~ B
= (A
& B)
(
&
)
A
B
= (
&B)
(A
&
)
A
← B
= A
&
A
↓ B
=
&
A
| B
=
.
Все эти формулы можно доказать на основе таблиц истинности.
Из этих формул видно, что все логические операции можно выразить через дизъюнкцию, конъюнкцию и отрицание. Другими словами, дизъюнкция, конъюнкция и отрицание образуют функционально полную систему операций.
5.4 Функционально полные системы операций
Функционально полные системы операций – наборы логических операций (функций), через которые можно выразить все остальные операции. Основные функционально полные системы операций следующие:
дизъюнкция, конъюнкция и отрицание;
дизъюнкция и отрицание;
конъюнкция и отрицание;
стрелка Пирса;
штрих Шеффера.
Формулы для перехода к операциям дизъюнкции, конъюнкции и отрицания приведены в разделе 5.3. Чтобы перейти от операции дизъюнкции к операциям конъюнкции и отрицания, используется закон де Моргана в следующей форме:
A
B
=
.
Если требуется, наоборот, переход от операции конъюнкции к операциям дизъюнкции и отрицания, то применяется закон де Моргана в следующей форме:
A
& B
=
.
5.5 Совершенные дизъюнктивные и конъюнктивные нормальные формы
Совершенные дизъюнктивные нормальные формы (СДНФ) и совершенные конъюнктивные нормальные формы (СКНФ) – стандартные формы записи формул алгебры логики.