Контрольная работа: Логика высказываний
Аналогичным образом убеждаемся, что функция рÙ`p тоже выражается логический закон: закон непротиворечия:
| р | `p | рÙ` | рÙ`p |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
С помощью таблиц истинности можно убедится, что нижеприведенные функции выражают логические законы:
Закон тождества: рºр (1)
Закон отрицания:
для конъюнкции: рÙ`p (2) (закон непротиворечия)
для дизъюнкции: рÚ`p (21 ) (закон исключенного третьего)
Закон идемпотентности:
для конъюнкции: рÙр º р (3)
для дизъюнкции: рÚ р º р (31 )
Закон коммутативности:
для конъюнкции: рÙ q º qÙр (4)
для дизъюнкции: рÚ q º qÚр (41 )
Ассоциативный закон:
для конъюнкции: (рÙq) ÙrºpÙ (qÙr ) ºpÙ qÙr (5)
для дизъюнкции: (рÚq) ÚrºpÚ (qÚr ) ºpÚ qÚr (51 )
Дистрибутивный закон:
для конъюнкции дизъюнкций: рÙ( q Úr) º (pÙq) Ú (рÙr ) (6)
для дизъюнкции конъюнкций: рÚ(qÙr) º (pÚ q) Ù (рÚr) (61 )
Закон поглощения:
для конъюнкции дизъюнкций: рÙ( q Úр) ºp (7)
для дизъюнкции конъюнкций: рÚ(qÙ р) ºp (71 )
Закон двойственности (теорема де Моргана):
для конъюнкции: рÙqº`р Ú`q (8)
для дизъюнкции: рÚqº`р Ù`q (81 )
 |
Закон двойного отрицания: `р º р (9)
Уже из внешнего вида формул (1) – (9) отчетливо виден двойственный характер этих законов относительно операций конъюнкции и дизъюнкции: если дана некоторая тождественно истинная функция высказывания, в выражении которой не входит знак «®», то при замене всех входящих в нее знаков «Ú» на «Ù» и «Ù» на «Ú», 1 на 0 и 0 на 1, она остается тождественно истинной. Запишем, например закон противоречия в формуле p Ù`p≡0 применяя к этому выражению закон двойственности, получим закон исключенного третьего p Ú`p≡1 (91 )
3 РАВНОСИЛЬНОСТЬ ФОРМУЛ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ. КОНЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА
Формулы φ и ψ называются равносильными, если формула φ ≡ ψ тождественно истина. Например, формула (p Ù`p) Ú q равносильна q, потому что формула (p Ù`p) Ú q ≡ q тождественно истина (проверку с помощью таблиц истинности предоставляем читателю). Формулы p Ú`p и qÚ`q также равносильны, потому что тождественно истинна формулы p Ú`p ≡ qÚ`q.
Равносильность формул может быть использована для упрощения формул, т.е. для замены какой-то формулы другой формулой, ей равносильной, (эквивалентной), но содержащей либо меньшее число связок, либо меньшее число переменных, либо другие переменные, либо и то, и другое, и третье вместе взятой.