Логика высказываний
Так, пользуясь указанным алгоритмом можно легко вычислить истинностное значение формулы:
((p→q)Ù(q→r))→(p→r)
|
p |
q |
r |
p→q | lign=top >
q→r |
p→r |
(p→q)Ù(q→r) |
((p→q)Ù(q→r) )→(p→r) |
|
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
|
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
|
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
|
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
|
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
|
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Итак, каждой формуле исчисления высказываний соответствует определенная функция, аргументы которой принимают значение из множества {0,1} и сама она принимает значение из этого множества. Эту функцию называют функцией исчисления высказываний. Проблема разрешимости в алгебре высказываний заключается в решении вопроса, является ли сложная формула тождественно истинной, т.е. истинной при всех значениях входящих в нее переменных, выполнимой, т.е. истинной лишь для некоторого набора значений переменных, или тождественно ложной, т.е. ложной при всех значениях переменных. Это проблема полностью решается посредствам вычисления значения функции, представленной данной формулой, с помощью таблиц истинности.
Функция исчисления высказываний выражает логический закон, если является тождественно истинной при всех возможных значениях переменных. Так, с помощью таблицы убеждаемся, что функция рÚ`p выражается логический закон: закон исключенного третьего:
|
р |
`р |
рÚ`p |
|
0 |
1 |
1 |
|
1 |
0 |
1 |
Аналогичным образом убеждаемся, что функция рÙ`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.
Скачать реферат