SHPORA.net :: PDA

[ Back ]

1.2.2 Равносильность формул

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

Основные равносильности
Для любых формул А,В,С справедливы следующие равносильности:
1. Коммутативность
А^В=В^А
2. Идемпотентность
А^А=А
3. Ассоциативность
А^(В^С)=(А^В)^С
4. Коммутативность
АvВ=ВvА
5. Идемпотентность
АvА=А
6. Ассоциативность
Аv(ВvС)=(АvВ)vС
7. Дистрибутивность v относительно ^
Аv(В^С)=(АvВ)^(АvС)
8. Дистрибутивность ^ относительно v
А^(ВvС)=(А^В)v(А^С)
9. 1-ый закон поглощения
А^(АvВ)=А
10. 2-ой закон поглощения
Аv(А^В)=А
11. Снятие двойного отрицания
?? А=А
12. 1-ый закон де Моргана
?(А^В)=?Аv?В
13. 2-ой закон де Моргана
?(АvВ)=?А^?В
Выражение одних логических связок через другие:
16. А~В=(АэВ)^(ВэА)=(А^В)v( ?А^?В)
17. АВАВ(АВ)
18. АВАВ(АВ)
19. АВ(АВ)(АВ)
Разделительное ?или?.
20. А+В(АВ)  (АВ)(АВ)
Штрих Шеффера.
21. АВ(АВ)АВ
Стрелка Пирса
22. АВ(АВ)(АВ)
Любая равносильность может быть доказана с помощью таблиц истинности.