Схемы доказательств.

Доказательства тех или иных утверждений в математике строятся на основании определенных правил, сущность которых выражают тавтологические импликации логики высказываний. Они схематично отражают шаги построения доказательств, поэтому их называют схемами или правилами доказательств (см., например, ниже правило заключения, правило контрапозиции и т. д.). Приведем правила, которые соответствуют первым 15 тавтологическим импликациям теоремы 1.3:

Часто при записи этих правил помещают посылки над горизонтальной линией, а заключение — под ней.

При такой записи приведенные выше схемы доказательств принимает вид:

Косвенное доказательство (доказательство от противного). Совокупность формул логики высказываний называется противоречивой, если при любом распределении истинностных значений входящих в них атомов хотя бы одна из формул получает значение A. Легко видеть, что совокупность формул противоречива тогда и только тогда, когда формула есть противоречие, т. е. является тождественно ложной формулой.

ТЕОРЕМА 2.5. Если из совокупности формул логически следует противоречие, то эта совокупность формул противоречива.

Доказательство. Предположим,что , где F — тождественно ложная формула. Тогда по теореме 2.3

В силу таблицы истинности для импликации отсюда следует, что формула тождественно ложна. Следовательно, совокупность формул противоречива.

Тождественно ложные формулы (противоречия) играют существенную роль в методе косвенного доказательства, называемого также методом доказательства от противного. Основой такого рода доказательств является следующая теорема.

ТЕОРЕМА 2.6. Если из формул логически следует противоречие, то

Доказательство. Предположим, что где F — противоречие. Тогда по теореме 2.5 совокупность формул противоречива. Поэтому если для какого-либо распределения истинностных значений атомов, входящих в формулы все формулы получают значение И, то формула получает значение A, а значит, В получает значение И. Следовательно,

Таким образом, если нужно доказать, что некоторое высказывание В логически следует из данных посылок, мы присоединяем к этим посылкам и показываем, что из посылок следует противоречие (обычно оно имеет вид ). После этого можно заключить, что высказывание В есть логическое следствие исходных посылок. Частным является случай, когда т. е. не задаются никакие посылки. Если, допустив истинность , выведем противоречие , то можем утверждать истинность В. Это рассуждение основывается на правиле доказательства, от противного: .

Очень распространенным является способ доказательства разбором случаев, который заключается в следующем. Пусть требуется доказать истинность высказывания С.

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

На основании правила силлогизма можно утверждать истинность высказывания если можно построить такую цепочку импликаций

каждая из которых истинна.

Упражнения

1. Обоснуйте следующие схемы доказательств:

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

3. Докажите, что