Рівносильність формул. Властивості логічних операцій

Означення 5.1.13. Формули алгебри висловлень f (p₁ , ¼, p_n) і g ( p₁ , ¼, p_n) називають рівносильнимиабологіч­но еквівалентними, якщо їх функції істин­ності |f| і |g| тотожно рівні, тобто, якщо їх значення на всіх 2ⁿ наборах збігаються.

Рівносильність формул f і g позначатимемо fºg Символ “º” не є символом операції алгебри висловлень, а означає певне відношення між формулами.

Основні рівносильності (закони) алгебри висловлень:

1. pÙqºqÙp – комутативність кон’юнкції.
2. pÚqºqÚp – комутативність диз’юнкції.
3. pÙ(qÙr)º(pÙq)Ùr – асоціативність кон’юнкції.
4. pÚ(qÚr)º(pÚq)Úr – асоціативність диз’юнкції.
5. pÙ(qÚr)ºpÙqÚpÙr – перший дистрибутивний закон.
6. pÚ(qÙr)º(pÚq)Ù(pÚr) – другий дистрибутивний закон.
7. (pÙq)º Ú закони
8. (pÚq)º Ù де Моргана.
9. p®qº Úq.
10. p«qº(p®q)Ù(q®p).
11. ºp – закон подвійного заперечення.
12. pÙpºp. закони
13. pÚpºp. ідемподентності.
14. p®qº ® .
15. pÚpÙqºp. закони
16. pÙ(pÚq)ºp. поглинання.
17. uÙ1ºu. правила
18. uÙ0º0. співвідно-
19. uÚ1º1. шення
20. uÚ0ºu. констант
21. pÚ º1 – закон виключення третього.
22. pÙ º0 – закон протиріччя.

Формули 1-8, 11-13, 15-22 – називають аксіомами булевої алгебри або властивостями операцій кон’юнкція, диз’юнкція і заперечення.

Наступні властивості називають аксіомами алгебри Жегалкіна.

1ж. pÙ(qÙr)º(pÙq)Ùr – асоціативність кон’юнкції.

2ж. pÅ(qÅr)º(pÅq)År – асоціативність строгої диз’юнкції.

3ж. pÙqºqÙp – комутативність кон’юнкції.

4ж. pÙqºqÙp – комутативність кон’юнкції.

Тема 5.4. БУЛЕВІ ФУНКЦІЇ