§3. Методы доказательства

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

Теоремой называется высказывание, которое можно доказать. Формально большинство теорем могут быть представлены в форме импликации А ? В. Посылка А называется условием теоремы, а следствие В –– заключением. Теорема верна, если выражающая ее импликация является тавтологией, т.е. тождественно истинна.

Рассмотрим наиболее известные методы доказательства.

1. Метод цепочек импликаций. Этот метод доказательства заключается в том, что из посылки А выстраивается цепочка из n импликаций (А ? А1 ? А2 ?… ? Аn–1 ? В), последним высказыванием в которой будет заключение теоремы В. В основе этого метода лежит закон силлогизма.

2. Метод доказательства от противного. Вместо истинности высказывания А мы доказываем истинность высказывания . Обоснованием этого является следующая теорема.

Теорема. При любых высказываниях А и С высказывания А и эквивалентны.

Доказательство. Если А истинно, то ложно, и истинно (при ложной посылке импликация всегда истинна). Наоборот, если истинно, но так как ложно (закон противоречия), может быть лишь ложным. Значит, А истинно.

3. Метод необходимого и достаточно. Пусть теорема формулируется так: «Чтобы имело место А, необходимо и достаточно выполнение В». Доказательство такого вида теоремы распадается на две части:

а) доказывается, что если имеет место А, то справедливо В (В необходимо для А);

б) если имеет место В, то имеет место и А (В достаточно для А).

Доказательство таким методом базируется на законе тавтологии (теорема 3 §1): .