Реферат: Исчисление высказываний
Свойства эквивалентности.
Основные, часто используемые свойства эквивалентности приведены в таблице 5.8.
Таблица 5.8.
Свойства эквивалентности
| I. | Коммутативность | II. | Ассоциативность |
| 1. | pÙq º qÙp | 1. | pÙ(qÙr) º (pÙq)Ùr |
| 2. | pÚq º qÚp | 2. | pÚ(qÚr) º (pÚq)Úr |
| III. | Дистрибутивность | IV. | Закон Де Моргана |
| 1. | pÙ(qÚr) º (pÙq)Ú(pÙr) | 1. | Ø(pÚq) ºØpÙØq |
| 2. | pÚ(qÙr) º (pÚq)Ù(pÚr) | 2. | Ø(pÙq) ºØpÚØq |
| V. | Закон импликации | VI. | Закон прямого и обратного условий |
| 1. | pÞq ºØpÚq | 1. | pÛq º (pÞq)Ù(qÞp) |
| VII. | Cвойство отрицания | VIII. | Закон идентичности |
| 1. | Ø(Øp) º p | 1. | p º p |
| IX. | Закон исключения третьего | X. | Закон противоречия |
| 1. | pÚØp ºТ | 1. | pÙØp º F |
| XI. | Свойства дизъюнкции | XII. | Коньюнкция |
| 1. | pÚpºp | 1. | pÙp º p |
| 2. | pÚÒ ºТ | 2. | pÙÒ º p |
| 3. | pÚF º p | 3. | pÙF º F |
| 4. | pÚ(pÙq) º p | 4. | pÙ(pÚq) º p |
Нетрудно углядеть сходство многих свойств эквивалентности в исчислении высказываний с аналогичными свойствами операций в арифметике. Например, законы ассоциативности, дистрибутивности и коммутативности, позволяющие упрощать арифметические операции и аналогичные законы из таблицы 5.8., позволяющие упрощать высказывания.
Мы будем использовать эти свойства в разных целях. Коммутативность, например, позволяет нам менять местами элементы высказывания , в целях его упрощения. Ассоциативность позволяет снимать скобки. Например, т.к. pÙ(qÙr) º (pÙq)Ùr , то мы можем просто писать pÙqÙr. Дистрибутивность позволяет собирать подобные члены, подобно тому как мы это делаем в арифметическом выражении. Закон импликации позволяет уходить от операции Þ , используя только операции Ø, Ú, Ù. Для того, чтобы убедиться в правильности этих свойств, достаточно построить их таблицы истиности. Например, в таблице 5.9. показана корректность закона импликации. Остальные свойства читателю предлагается доказать в качестве упражнения.
Таблица 5.9.
Доказательство корректности закона импликации
| p | q | pÞq | ØpÚ q |
| T | T | T | T |
| T | F | F | F |
| F | T | T | T |
| F | T | T | T |
Теперь сосредоточимся на упрощении выскзываний, используя свойства эквивалентности. Под упрощением мы будем понимать такое преобразование высказывания, которое принимает форму, удобную для нас в каком-то смысле. Например, содержит меньше переменных, операций Ú или Ù.
Рассмотрим несколько примеров.
(pÚØq)ÙrÙ(ØpÚq)
(pÚØq)Ù(ØpÚq)Ùr I.1
(ØqÚp)Ù(ØpÚq)Ùr I.2
(qÞp)Ù(pÞq)Ùr V.1
(pÛq)Ùr VI.1
Таким образом
(pÚØq)ÙrÙ(ØpÚq) º (pÛq)Ùr
Другой пример, упростить
pÚ(ØqÞp)ÚØq
pÚ(Ø(ØqÚp)ÚØq V.1
pÚ(qÚp)ÚØq VII.1
pÚ(qÚp)ÚØq I.2
(pÚp)Ú(qÚØq) II.2
pÚ(qÚØq) XI.1
pÚT IX.1
TXI.2
Тем самым, мы доказали, что
pÚ(ØqÞp)ÚØqº Т - тавтология.
Упростить