2015-01-07
449
Для любых формул A, B, C справедливы следующие равносильности:
1. Коммутативность.
а) A & B º B & A (для конъюнкции);
б) A V B º B V A (для дизъюнкции).
2. Ассоциативность.
а) A &(B & C) º (A & C)& C (для конъюнкции);
б) A V(B V C) º (A V B)V C (для дизъюнкции).
3. Дистрибутивность.
а) A &(B V C) º A & B V A & C (для конъюнкции относительно дизъюнкции);
б) A V(B & C) º (A V B)&(A V C) (для дизъюнкции относительно конъюнкции).
4. Закон де Моргана.
а) Ø(A & B) ºØ A VØ B (отрицание конъюнкции есть дизъюнкция отрицаний);
б) Ø(A V B) º Ø A &Ø B (отрицание дизъюнкции есть конъюнкция отрицаний).
5. Идемпотентность.
а) A & A º A (для конъюнкции);
б) A V A º A (для дизъюнкции).
6. Поглощение.
а) A &(A V B) º A (1– ый закон поглощения);
б) A V A & B º A (2– ой закон поглощения).
7. Расщепление (склеивание).
а) A & B V A &(Ø B) º A (1–ый закон расщепления);
б) (A V B) & (A VØ B) º A (2–ой закон расщепления).
8. Двойное отрицание.
Ø(Ø A) º A.
9. Свойства констант.
а) A &1 º A; б) A &0 º 0; в) A V1 º 1; г) A V0 º A; д) Ø0 º 1; е) Ø1 º 0.
10. Закон противоречия.
A &Ø A º 0.
11. Закон “исключенного третьего”.
A VØ A º 1.
Каждая из перечисленных равносильностей может быть доказана с помощью таблиц значений функций, составленных для выражений, стоящих слева и справа от символа “º”. Докажем, например, равносильность 4а. Для этого составим таблицу 4.5.
Таблица 4.5
| A | B | A & B | Ø(A & B) | Ø A | Ø B | Ø A VØ B |
Из таблицы 4.5 видно, что Ø(A & B) º Ø A VØ B, что и требовалось доказать.
Следующие важные равносильности показывают, что все логические операции могут быть выражены через операции конъюнкции, дизъюнкции и отрицания:
12. A É B ºØ A V B º Ø(A &Ø B).
13. A ~ B º (A É B)&(B É A) º (A & B) V (Ø A &Ø B) º (АVØ B)&(Ø A V B).
14. A ÅB º (A VØ B) V (Ø A & B).
15. A ¯ B º Ø(A V B) º Ø A &Ø B.
16. A ï B º Ø(A & B) º Ø A VØ B.
Используя равносильности 3а и 3б и метод математической индукции, нетрудно получить также следующие равносильности (обобщенные законы дистрибутивности):
17. (A 1V A 2V...V An)&(B 1V B 2V...V Bm) º
A 1& B 1V A 1& B 2V...V A 1& Bm V...V An & B 1V An & B 2V...V An & Bm.
18. (A 1& A 2&...& An)V(B 1& B 2&...& Bm) º
(A 1V B 1)&(A 1V B 2)&...&(A 1V Bm)&...&(An V B 1)&(An V B 2)&...&(An V Bm).
Используя равносильности 4а и 4б и метод математической индукции, можно получить также следующие равносильности (обобщенные законы де Моргана):
19. Ø(A 1& A 2&...& An) º Ø A 1VØ A 2V...VØ An.
20. Ø(A 1V A 2V...V An) ºØ A 1&Ø A 2&...&Ø An
В равносильностях 1 – 20 в качестве A, B, Ai, Bi могут быть подставлены любые формулы и, в частности, переменные. Приведем правило, с помощью которого можно переходить от одних равносильностей к другим.
