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

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

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

• Пример

Применим первую эвристику к формуле закон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.

В данной схеме из числа исключающих посылки правил вывода имеется только правило введения импликации, что характеризует данный вывод в качестве прямого. Вывод, в котором при выборе посылок использовалась только первая эвристика (т. е. не применялось правило введения отрицания), называется прямым выводом.

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

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

• Пример

Рассмотрим в качестве ещё одного примера использования второй эвристики доказательство закона обратной контрапозиции ((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.

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

• Пример

Докажем, что формула (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.