Сложным суждением называется суждение, какая-либо часть которого является суждением.
Структура сложных суждений определяется выделением в качестве элементов простых суждений и логических связок.
9.1. Логические связки:
/\ - конъюнкция (заменяет союзы "и", "а", "но", перечисление)
\/ - слабая дизъюнкция (союз "или")
•
\/ - строгая дизъюнкция (союз "либо - либо")
→ - импликация (союзы, вводные слова, "если, то", "значит", "следовательно", "потому что", "тогда, когда", "поскольку, постольку" и т.д.).
Импликация указывает на причинно-следственную связь между простыми суждениями в составе сложного и между суждениями вообще.
Причина называется антецедентом импликации, а следствие – консеквентом.
↔ - эквиваленция (союзы "тогда и только тогда, когда", "если и только если, то"). Это однозначная причинно-следственная связь.
Эквиваленцию еще называют равносильностью.
Ā – логическое отрицание (неверно, что А; не – А).
|
|
↓ - стрелка Пирса (обозначает конъюнкцию двух отрицаний)
| - штрих Шеффера (обозначает дизъюнкцию двух отрицаний).
9.2 Понятие формализации суждения
При решении задач со сложными суждениями необходимо научиться формализовать тексты. Для этого необходимо:
1. Выделить в качестве элементов простые суждения и обозначить их переменными.
2. Расставить между переменными логические связки, соответствующие союзам, и записать в виде формулы.
Примеры:
а в
1.(Жарко), и (идет дождь). (а /\ в)
ā в
2. (Дождь не идет), но (жарко). (ā /\ в)
а в
3. (Подальше положишь), (поближе возьмешь). (а → в)
а в а в
4. Если (лает), то (кусает).(Лает). Следовательно,(кусает).
((а → в) /\ а) → в
9.3. Таблица истинности
Для определения истинности или ложности сложных суждений необходимо пользоваться таблицей истинности.
а | в | ā | а /\ в | а \/ в | • а \/ в | а → в | а ↔ в |
И И Л Л | И Л И Л | Л Л И И | И Л Л Л | И И И Л | Л И И Л | И Л И И | И Л Л И |
1. Количество строк в таблице истинности определяется по формуле 2 n , где n – количество переменных.
2. Количество столбиков равно количеству переменных плюс количество подформул, входящих в исходную формулу.
3. Комбинации "И" и "Л" задаются формулами:
1 столбик (2 n : 2)
2 столбик ((2 n : 2): 2)
3 столбик: и т.д.
последний столбик всегда содержит чередование "И" и "Л".
При формализации текстов могут получиться разного рода формулы:
1. Тождественно - истинная формула получается при условии, если при всех любых значениях входящих в нее переменных, она получает значение "И".
2. Тождественно – ложная формула, - если при всех любых значениях входящих в нее переменных, она получает значение "Л".
|
|
3. Логически – нейтральная – это не тождественно – истинная и не тождественно – ложная формула, т.е. в результате есть "И" и "Л".
4. Тождественно – истинные и тождественно – ложные формулы называются выполнимыми.
5. Формулы называются равносильными, если при каждой определенной комбинации "И" и "Л" значений входящих в них переменных значения формул совпадают.
Пример. Если слово ставится в начале предложения, то оно пишется с большой буквы. Неверно, что слово ставится в начале предложения и при этом не пишется с большой буквы.
Задание: установить, являются ли данные суждения равносильными?
1. Формализуем текст.
_ _
(а → в) ↔ (а /\ в)
2. Составляем таблицу истинности.
а | в | _ в | (а → в) | _ (а /\ в) | _ (а /\ в) |
И И Л Л | И Л И Л | Л И Л И | И Л И И | Л И Л Л | И Л И И |
3. Сравниваем четвертый и шестой столбик построчно: I строка – "И" – "И", II строка – "Л" – "Л", III строка – "И" – "И", IV строка – "И" – "И".
1. Делаем вывод: Формула логически нейтральна, выполнима. Суждения равносильны.
9.4.Метод доказательства «от противного».
Если в тексте для формализации и доказательства более чем две или три переменные, то часто применяют более эффективный метод доказательства – "от противного".
Возьмем текст.
"Наполеон либо укреплял свою власть, либо заботился об интересах государства. Известно, что Наполеон заботился об интересах государства. Следовательно, он не укреплял свою власть".
1. Формализуем текст:
((а \/ в) /\ в) → ā
Метод доказательства "от противного" заключается в предположении "ложности" всей формулы.
•((а \/ в) /\ в) → ā - "Л"
2. Ключевой знак в формуле – импликация, это значит, что
((а \/ в) /\ в) → ā - должна быть – "И", а (ā) – "Л" – по таблице истинности.
3. Если (ā) – "Л", значит (а) – "И".
4. Рассмотрим антецедент импликации. Здесь ключевой знак – конъюнкция, состоящая из двух конъюнктов.
5. По таблице истинности (а \/ в) и (в) должны принимать истинное значение.
6. Последняя подформула - (а \/ в) – "И" при условии, что одна из переменных принимает значение "И", а другая – "Л".
Мы знаем, что "а" – "И" и "в" – "И", следовательно (а \/ в) – "Л".
7. Итак, возникло противоречие. Нужно было получить "И", а мы получили "Л", следовательно наше предположение о ложности неверно, а формула истина.
Попробуем проверить правильность решения табличным методом.
а | в | ā | • (а \/ в) | • (а \/ в) /\ в | • ((а \/ в) /\ в) → ā |
И И Л Л | И Л И Л | Л Л И И | Л И И Л | Л Л И Л | И И И И |
Итак, у нас получились все истинные значения. Это значит, что формула тождественно – истинна, суждение верно.
9.5. Проблема разрешимости. Нормальные формы.
В логике существует эффективная процедура, позволяющая определить, является ли некая формула тождественно-истинной, тождественно-ложной или нейтральной. Эта задача носит название проблемы разрешимости.
Для формул языка логики высказываний в качестве такой эффективной разрешающей процедуры можно использовать построение таблицы истинности. Но при большом количестве переменных построение таблицы затруднительно и не рационально. Например, если формула содержит десять переменных, то таблица будет содержать 210 = 1024 строки.
Метод приведения формулы к нормальной форме и дальнейшие преобразования (подстановка, КНФ, ДНФ) позволяют рационально определить, к какому классу принадлежит формула.
Рассмотрим подробнее эту процедуру.
Формула имеет нормальную форму, если в качестве связок в ней присутствуют только конъюнкции или дизъюнкции, а отрицания относятся только к переменным.
|
|
Для приведения формулы к нормальной форме необходимо пользоваться основными логическими равносильностями:
1. А ≡ А
=
2. А ≡ А –закон двойного отрицания
3. (А /\ В) ≡ (В /\ А) - закон коммуникативности /
4. (А \/ В) ≡ (В \/ А) – закон коммуникативности
5. (А /\ (В /\ С)) ≡ ((А /\ В) /\ С) – закон ассоциативности
6. (А \/ (В \/ С)) ≡ ((А \/ В) \/ С) – закон ассоциативности
7. (А /\ (В \/ С)) ≡ ((А /\ В) \/ (А /\ С)) – закон дистрибутивности
8. (А \/ (В /\ С)) ≡ ((А \/ В) /\ (А \/ С)) – закон дистрибутивности
9. (А /\ А) ≡А - закон идемпотентности
10. (А \/ А) ≡ А – закон идемпотентности
____ _ _
11. (А /\ В) ≡ (А \/ В) – закон де Моргана
_____ _ _
12. (А \/ В) ≡ (А /\ В) – закон де Моргана
_____
13. (А → В) ≡ (А /\ В)
_
14. (А → В) ≡ (А \/ В)
____
15. (А /\ В) ≡ (А → В)
_ _
16. (А /\ В) ≡ (А \/ В)
_ _
17. (А \/ В) ≡ (А /\ В)
18. (А \/ (А /\ В)) ≡ А -закон поглощения
19. (А /\ (А \/ В)) ≡ А -закон поглощения
20. (А ↔ В) ≡ ((А → В) /\ (В → А))
_ _
21. (А ↔ В) ≡ ((А \/ В) /\ (В \/ А))
____
22. (А ↔ В) ≡ (А \/ В)
_ _
23. (А \/ В) ≡ ((А \/ В) /\ (А \/ В))
_ _
24. (А → В) ≡ (В → А)
_ _
25. (А ↔ В) ≡ ((А → В) /\ (А → В))
26. (А /\ И) ≡ А
27. (А /\ Л) ≡ Л
28. (А \/ И) ≡ И
29. (А \/ Л) ≡ А
_ _
30. (А ↓ В) ≡ (А /\ В) ↓ - стрелка Пирса
_ _
31. (А | В) ≡ (А \/ В) | - штрих Шеффера
Алгоритм разрешения суждений с помощью нормальной формы и подстановок.
1.Формализовать текст.
2. Привести формулу к нормальной форме алгебраическими преобразованиями с помощью равносильностей «14», «21», «23».
1. При помощи равносильностей «11» и «12» уменьшить область действия знака отрицания. Он должен находиться только при переменных.
2. Выявить нерегулярные переменные (то есть те, которые в формуле либо с отрицанием, либо только без него).
3. Подставить вместо нерегулярной переменной значение «ложь» и с помощью равносильностей «26», «27», «28» и «29» сократить формулу. Повторять операцию до тех пор, пока все нерегулярные переменные не исчезнут.
4. Вместо одной из регулярных переменных подставить вначале значение «ложь» и сократить формулу, затем – «истину» и также сократить формулу.
|
|
5. Если все конечные значения формулы истинны, то формула является логическим законом.
6. Если хотя бы одно конечное значение формулы получилось ложное, то формула не является истинной, исходное рассуждение опровергнуто, а дальнейший анализ формулы не имеет смысла.