§4. Типы теорем. О некоторых методах доказательств теорем

n1. Понятие теоремы. Разновидности теорем. Необходимые и достатачные условия

Определение 7. Если А(х) и В(х) – некоторые предикаты с одной и той же переменной х, определенные на одном и том же множестве D, то высказывание хD (А(х)В(х)) называется теоремой с посылкой (или условием) А(х) и заключением (или следствием) В(х). Если же А(х)В(х), то есть Е_АЕ_В (См. n°1 §3), иначе теорема хD (А(х)В(х)) истинна, то предикат А(х) (В(х)) называют достаточным условием для В(х) (необходимым условием для А(х)).

Замечание. Теорему разрешается записывать в виде х (А(х)В(х)), если из текста ясна природа общей области определения D предикатов А(х) и В(х).

План доказательства теоремы хD (А(х)В(х)), то есть доказательство истинности данного высказывания:

1. Фиксируется произвольное значение х₀ переменной х из Е_А, то есть предполагается, что предикат А(х) является истинным при некотором значении х = х₀.

2. Логическим путем убеждаемся, что из сделанного предположения следует истинность предиката В(х) при х=х₀, то есть убеждаемся, что х₀Е_Q.

План опровержения теоремы хD (А(х)В(х)), то есть доказательство ложности данного высказывания:

находится конкретное значение х₀ переменной х из D, при котором импликация А(х)В(х) ложна, то есть |А(х₀)|=И, а |В(х₀)|=Л.

Определение 8. Если хD (А(х)В(х)) – данная теорема, то теоремы хD (В(х) А(х)) и хD (А(х) В(х)) называются соответственно обратной и противоположной для данной. Теорема хD (В(х)А(х)) называется теоремой, обратной для противоположной (или противоположной для обратной) к данной.

Из равносильностей логических формул: ХY  YX и XY  YХ, установленных в n°2 §2, сразу же следуют следующие равносильности теорем:

хD (А(х)В(х))  хD (В(х)А(х)), (1)

хD (А(х)В(х))  хD (В(х)А(х)), (2)

то есть данная теорема и теорема, противоположная для обратной к данной (теорема, обратная для данной, и теорема противоположная для данной), равносильны. Ниже убедимся, что данная теорема не обязана быть равносильной обратной для нее теореме.

Из сказанного следуют утверждения:

1. Доказательство данной теоремы (теоремы, обратной для данной), можно заменить доказательством теоремы, противоположной для обратной к данной (теоремой, противоположной для данной).

2. Нельзя заменять доказательство данной теоремы доказательством теоремы, обратной для нее.

Равносильность (1) называют законом контрапозиции)

Примеры. Данное утверждение Т переформулировать в виде хD (А(х)В(х)). Построить предложения: хD (В(х)А(х)), хD (А(х)В(х)), хD  (В(х)А(х)). Оцените истинные значения построенных предложений, и полученную информацию сформулируйте на языке «необходимых и достаточных условий».

1. Т = «Если натуральное число делится на 3, то сумма цифр этого числа делится на 3»;

2. Т = «Если диагонали четырехугольника равны по длине, то он является прямоугольником;

3. Т = «Если действительное число больше 1, то и квадрат этого числа больше 1.

Решение.

1) Данное высказывание можно переформулировать в виде: Т = «Для любого натурального n, если n3, то сумма цифр числа n делиться на 3», то есть nN (А(n)В(n)), где А(n) = «n3», В(n) = «сумма цифр числа n делиться на 3», D=D_A=D_B=N. Построенная теорема, как известно, истинна.

nN  (В(n)А(n))«Для любого натурального n, если сумма цифр числа n делиться на 3, то n 3» – теорема обратная для данной. И эта теорема, как известно, истинна.

nN (А(n)В(n))«Для любого натурального n, если (n3), то сумма цифр числа n не делиться на 3» – теорема, противоположная для данной, истинная хотя бы в силу (2).

nN (В(n)А(n))«Для любого натурального n, если сумма цифр числа n не делиться на 3, то (n 3)» – теорема противоположная к обратной для данной, истинная, хотя бы в силу (1).

Информацию об истинности теорем nN (А(n)В(n)) и nN (В(n)А(n)), то есть наличие логических следствий А(n)В(n) и В(n)А(n), можно сформулировать одним из следующих способов: «А(n) – достаточное условие для В(n) и А(n) – необходимое условие для В(n)», или «А(n) – необходимое и достаточное условие для В(n)», иначе «для В(n) необходимо и достаточно А(n)».

2) Переформулируем данное высказывание в виде: Т = «Для любого четырехугольника Q, если длины диагоналей равны, то четырехугольник Q – прямоугольник», то есть Т = Q (А(Q)В(Q)), где А(Q) = «длины диагоналей равны», B(Q) = «четырехугольник Q – прямоугольник», D=D_A=D_B – семейство всех четырехугольников. Данное утверждение ложно, так как очевидно существование четырехугольника, длины диагоналей которого равны, но который не является прямоугольником.

Q (В(Q)А(Q)) «Для любого четырехугольника, если четырехугольник Q – прямоугольник, то длины диагоналей четырехугольника Q равны» – теорема, обратная данной является истинной, как одно из свойств прямоугольника.

Но тогда согласно (1) и (2) теорема Q (А(Q)В(Q)) – истинна, а Q (В(Q)А(Q)) – ложна.

Информацию об истинности теоремы Q (В(Q)А(Q)) и ложность теоремы Q (А(Q)В(Q)) можно сформулировать, например, в виде «А(Q) необходимо, но не достаточно для В(Q)», то есть «Равенство длин диагоналей четырехугольника Q является необходимым, но не достаточным условием для того, чтобы четырехугольник Q являлся прямоугольником».

3) Переформулируем высказывание в виде: Т=«Для любого действительного числа х, если х>1, то х²>1», то есть хR (А(х)В(х)), где А(х) = «х>1», В(х) = «х²>1» и D=D_A=D_B=R. По свойству числовых неравенств эта теорема истинна.

хR (В(х)А(х))=«Для любого действительного х, если х²>1, то х>1» – теорема обратная для данной. Эта теорема ложна, так как импликация предикатов х²>1х>1 например, при х = –2 ложна.

Но тогда теорема хR (В(х)А(х))«Для любого действительного х, если х²1, то х1» является истинной, а теорема хR (А(х)В(х))«Для любого действительного х, если х1, то х²1» ложна.

Информацию об истинности данной теоремы и ложности обратной для нее теоремы можно сформулировать, например, в виде: «х>1 – достаточно, не необходимо для х²>1».

n2. Метод доказательство теоремы «от противного»

Из равносильностей логических формул:

(XY)  (XYX),

(XY)  (XYY),

(XY)  (XYZZ),

установленных в n°2 §2, следует, что теорема хD (А(х)В(х)) равносильна каждой из теорем:

хD (А(х)В(х)А(х)), (3)

хD (А(х)В(х)В(х)), (4)

хD (А(х)В(х)С(х)С(х)), (5)

где С(х) – какой-либо предикат, определенный на D.

Если доказательство теоремы хD (А(х)В(х)) заменяется одной из теорем (3) – (5), то говорят, что первоначальная теорема доказывается методом «от противного».

n3. Общения понятия теоремы

Высказывания вида хD (А(х)В(х)) так же называют теоремами.

Из равносильности логических формул (XY)  ((XY)(YX)), установленной в n°2 §2, следует равносильность

хD (А(х)В(х))  хD (А(х)В(х)  В(х)А(х)), то есть

хD (А(х)В(х))  (хD (А(х)В(х))  (хD (В(х)А(х)).

Таким образом доказательство истинности теоремы хD (А(х)В(х)) сводится к доказательству истинности теорем хD (А(х)В(х)) и хD (В(х)А(х)). Заметим, что истинность теоремы хD (А(х)В(х)) означает достаточность и необходимость условия А(х) для В(х).

Определение 9. Если А(х₁, х₂, … х_n) и В(х₁, х₂, … х_n) – некоторые n-местные предикаты, определенные на одном и том же множестве D, то высказывания (х₁; х₂; … ; х_n)D (А(х₁, х₂, … х_n)В(х₁, х₂, … х_n)) и

(х₁; х₂; … ; х_n)D (А(х₁, х₂, … х_n)В(х₁, х₂, … х_n))

называются теоремами.