Эвристики натурального исчисления высказываний

Построение выводов и доказательств является творческой задачей, например, при поиске посылок в доказательстве при условии, что хотя в качестве посылок можно брать любые формулы, но в ходе вывода все они должны быть исключены. Выбор нужных для вывода посылок может быть случайным и иметь характер простого перебора различных возможностей. Во избежание последнего в логике были выработаны и применяются особые методологические приёмы эвристики, позволяющие предельно сократить число переборов. Натуральное исчисление высказываний опирается на 3-и основных эвристики. 1-я эвристика применяется тогда, когда являющаяся целью вывода формула импликативна; в таком случае антецедент этой формулы берётся в качестве дополнительной посылки, а целью выведения становится консеквент формулы.

V Пример

Применим 1-ю эвристику к формуле законa введения конъюнкции: (pÉq)É(pÙq)). Получим следующую схему вывода:

_______ ______________

1. p — пос. 2. q — пос. 3. p Ù q — Ùв, 1, 2. 4. q É (p Ù q) — Éв, 2, 3. 5. p É (q É (p Ù q)) — Éв, 1, 4.

В данной схеме из числа исключающих посылки правил вывода имеется только правило введения импликации, что характеризует данный вывод в качестве прямого. Вывод, в котором при выборе посылок использовалась только 1-я эвристика (т. е. не применялось правило введения отрицания), называется прямым выводом. В предыдущих же схемах доказательств имелось правило введения отрицания, что характеризует эти выводы в качестве косвенных (от противного) и свидетельствует об использовании 2-й эвристики. При этом фундаментальным является прямой вывод, и всё то, что обосновывается посредством прямого вывода, может быть обосновано и посредством вывода косвенного. 2-я эвристика применяется после исчерпания возможностей первой, когда целью вывода не является импликативная формула; в таком случае в качестве дополнительной посылки берётся отрицание этой формулы, а целью вывода становится получение в ходе рассуждения противоречия. Если это удаётся сделать, то, применяя правило введения отрицания, можно получить в выводе формулу отрицания дополнительной посылки, а используя правило исключения отрицания, получить итоговую формулу.

V Пример

Рассмотрим в качестве ещё одного примера использования 2-й эвристики доказательство закона обратной контрапозиции ((Øq É Øp) É (p É q)):

_______ ____________________ ____________________________

1. Øq É Øp — пос. 2. p — пос. 3. Øq — пос. 4. Øp — Éи, 1, 3. 5. ØØq — Øв, 2, 4. 6. q — Øи, 5. 7. p É q — Éв, 2, 6. 8. (Øq É Øp) É (p É q) — Éв, 1, 7.

3-я эвристика применяется после исчерпания возможностей первой и второй, когда в выводе имеется дизъюнктивная формула, а целью вывода остаётся получение противоречия.

V Пример

Докажем, что формула (pÚq)É(qÚp) является теоремой:

___________ _______________________ _________________________________________

1. pÚq — пос. 2. Ø(qÚp) — пос. 3. Øp — пос. 4. q — Úи, 1, 3. 5. qÚp — Úв, 1, 3. 6. ØØp — Øв, 2, 5. 7. p — Øи, 6. 8. qÚp — Úв, 7. 9. ØØ(qÚp) — Øв, 2, 8. 10. qÚp — Øи, 9. 11. (pÚq)É(qÚp) — Éв, 10.

Очевидно, что в ходе вышеприведённого вывода были изъяты из дальнейших его шагов: 1) формулы с третьей (Øp) по шестую (ØØp), явившуюся результатом применения правила введения отрицания, 2) формулы со второй (Ø(qÚp)) по девятую (ØØ(qÚp)), также появившуюся в результате очередного применения правила введения отрицания, 3) 10 формула (qÚp), к которой было применено правило введения материальной импликации, вместе с первой формулой (pÚq) – последней остававшейся посылкой рассуждений. Значит, был получен вывод из пустого множества неисключённых посылок, т. е. доказательство того, что формула ((pÚq)É(qÚp)) – теорема.

Тема девятая

ЯЗЫК И ИСЧИСЛЕНИЕ КЛАССИЧЕСКОЙ ЛОГИКИ ПРЕДИКАТОВ