Реферат по математической логике и теории алгоритмов на тему Исчисление высказываний

Исчисление высказываний
Каковы бы ни были формулы A,B,C, следующие формулы называют аксиомами исчисления высказываний:
(1) A→ (B → A);
(2) (A→ (B → C))→ ((A→ B)→ (A→ C));
(3) (A ∧B)→ A;
(4) (A ∧B)→ B;
(5) A→ (B → (A ∧B));
(6) A→ (A ∨B);
(7) B → (A ∨B);
(8) (A→ C)→ ((B → C)→ (A ∨B → C));
(9) ¬A→ (A→ B);
(10) (A→ B)→ ((A→ ¬B)→ ¬A);
(11) A ∨ ¬A.
Как говорится, здесь 11 «аксиоматических схем». Из каждой схемы можно вывести различные конкретные аксиомы, заменив буквы пропозициональными формулами.
Единственное правило для вывода исчисления высказываний
Существует правило со средневековым названием modus ponens (MP), позволяющее получить (вывести) выражение B из выражений A и (A → B) по правилу modus ponens.
Вот пример вывода (первая формула закрытая):
Для схемы (1) второй является схема (2), последняя взята из двух предыдущих схем по правилу modus ponens):
(p→ (q → p)),
(p→ (q → p))→ ((p→ q)→ (p→ p)),
((p→ q)→ (p→ p)).
Пропозициональное выражение А называется выводимым с помощью исчисления высказываний или теоремы об исчислении высказываний, если существует вывод, последнее выражение которого равно А. Такой вывод называется выводом формулы А. Я просто зачеркнул. )
Как уже говорилось, в исчислении высказываний выводятся все тавтологии и только те. Это утверждение обычно делится на две части: простую и сложную. Начнем с простого:
Теорема 17 (о корректности ИВ). Всякая теорема исчисления высказываний есть тавтология. Несложно проверить, что все аксиомы — тавтологии. Для примера проделаем это для самой длинной аксиомы (точнее, схемы аксиом) — для второй. В каком случае формула:
(A→ (B → C))→ ((A→ B)→ (A→ C))
(где A,B,C — некоторые формулы) могла бы быть ложной? Для этого посылка A → (B → C) должна быть истинной, а заключение (A → B) → (A → C) — ложным. Чтобы заключение было ложным, формула A → B должна быть истинной, а формула A → C — ложной. Последнее означает, что A истинна, а C ложна. Таким образом, мы знаем, что A, (A→ B) и (A→ (B → C)) истинны. Отсюда следует, что B и (B → C) истинны, и потому C истинна — противоречие. Значит, эта формула не бывает ложной.
Справедливость правила МР также очевидна. Формула (A → B) и A всегда истинно, и по определению импликации выражение B также всегда истинно. Поэтому все выражения, содержащиеся в заключении (все теоремы), являются тавтологиями.
Доказать обратное утверждение гораздо сложнее.