Исчисление высказываний
Формулы исчисления высказываний Рассмотрим понятие переменной – a, b, c,… x, y,… Будем строить формулы, последовательно вводя операции
над константами И и Л и переменными: Атомарная формула x, И, Л Отрицание (¬F), где F - формула Конъюнкция (F1 ∧ F2), где F1, F2 - формулы Дизъюнкция (F1 ∨ F2), где F1, F2 - формулы Следование (F1 → F2), где F1, F2 - формулы Эквивалентность (F1 ≡ F2), где F1, F2 - формулы Учитывая приоритеты операций и их ассоциативность (слева направо),
будем опускать «лишние» скобки. Примеры формул исчисления высказываний: a ∨ ¬a (a → b) → (a ∨ b) a ∧ ¬a a → b ≡ ¬a ∨ b Для заданной формулы F обозначим Var(F) множество входящих в формулу переменных. Интерпретация формулы – функция на Var(F) I : Var(F) → { И, Л } Если задана интерпретация, то можно вычислить значение формулы Val(F, I) ∈ { И, Л } Тавтология – формула, истинная в любой интерпретации: Val(F, I) = И для любой I Противоречие – формула, ложная в любой интерпретации: Val(F, I) = Л для любой I (1), (4) – примеры тавтологий; (3) – противоречие; (2) – ни тавтология, ни противоречие Логическое следствие и эквивалентность формул Говорят, что формула B является логическим следствием формулы A (запись: A ⇒ B),
если в любой интерпретации, в которой истинна формула A, формула B также истинна. Например: a ⇒ a ∨ b a ∧ b ⇒ a → b Говорят, что формулы A и B эквивалентны, если A ⇒ B и B ⇒ A (запись: A ⇔ B ).
Можно еще сказать, что две формулы эквивалентны, если они в любой интерпретации
одновременно истинны или одновременно ложны. Например: a ∧ a ⇔ a ∨ a ¬a ∨ b ⇔ a → b Три теоремы: Теорема 1 (связь между логическим следствием и операцией логического следования):
A ⇒ B тогда и только тогда, когда формула A → B – тавтология. Теорема 2 (связь между эквивалентностью формул и операцией логической эквивалентности):
A ⇔ B тогда и только тогда, когда формула A ≡ B – тавтология. Теорема 3 (о подстановке): если в некоторой формуле подставить вместо некоторой
подформулы эквивалентную ей подформулу, то получившаяся формула будет
эквивалентна исходной. Доказательство всех трех теорем очевидно.