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

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

Формально каждая теорема может быть выражена в форме импликации A B, где посылка A называется условием теоремы, а следствие B - заключением. Теорема верна, если выражающая ее импликация тождественно истинна, т.е. является тавтологией. Тавтологии рассматривают как некоторые логически истинные схемы рассуждений. В этой связи тавтологии играют роль законов, определяющих построение правильных умозаключений. Существует бесконечное множество тавтологий. Некоторые из них легли в основу методов доказательства.

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

Метод цепочек импликаций состоит в том, что из посылки A выстраивается цепочка из n импликаций, последним высказыванием в которой является заключение теоремы B, т.е.

A A₁ A₂ ... A_n-1 B

В основе этого метода лежит закон цепного высказывания или закон силлогизма (A B) (B C) (A C)

Метод от противного. Используя этот метод, вместо доказательства прямого следствия " из A следует B" доказывают, что из " не B" следует " не A". Этот метод основан на законе контрапозиций, имеющим следующий вид: (A B) (ù B ù A).

Метод необходимого и достаточного. Теорема формулируется так: " Чтобы имело место A, необходимо и достаточно выполнение B". Доказательство такого вида теоремы распадается на две части:

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

б) Если имеет место B, то имеет место и A (B достаточно для A).

Доказательство таким методом базируется на законе тавтологии.

(P Q) ((P Q) (Q P))

В дальнейшем мы часто будем использовать эти методы доказательств теорем.