Если F1,F2,F3,…, Fm|¾ Ф, то F1,F2,F3,…, Fm-1 |¾ (FmÉФ), и наоборот.

Эта теорема говорит о возможности переноса формул логики высказываний через знак выводимости |¾.

Замечание: m-кратное применение теоремы дедукции приведет к утверждению выводимости формулы

Применение логики высказываний к анализу математических

доказательств

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

Аппарат логики высказываний позволяет нам прояснить структуру доказательств многих математических утверждений.

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

1. Доказательство с помощью построения цепочки импликаций.

Этим методом пользуются при доказательстве теорем, выраженных в форме импликации: "Если высказывание A истинно, то и высказывание B истинно", то есть AÉB.

Доказательство строится как последовательность тождественно-истинных импликаций вида: AÉA1, A1ÉA2, … , An-1ÉAn, AnÉB, где A1, A2, A3, … , An- некоторые вспомогательные высказывания.

Отсюда делается вывод (в силу транзитивности импликации) о справедливости теоремы AÉB.

Такое доказательство называется прямым доказательством.

Прежде, чем рассмотреть другие типы доказательств напомним классификацию теорем из средней школы, которую иллюстрирует рис.2.1

Как легко проверить, используя метод истинностных таблиц, прямая теорема оказывается равносильной обратной противоположной, а обратная теорема - противоположной. И в то же время, таких равносильностей в общем случае не существует между прямой и обратной теоремами, между прямой и противоположной, между обратной и обратной противоположной, между противоположной и обратной противоположной.

Из указанных равносильностей вытекает следующий метод доказательства.

2. Доказательство от противного.

Этот метод используется при доказательстве теорем вида AÉB и основывается на законе контрапозиции XÉYºØYÉØX, который фактически гласит, что доказательство теоремы AÉB может быть заменено доказательством эквивалентной ей теоремы, которая формулируется как ØBÉØA . Последняя теорема называется обратная противоположной (или противоположная обратной).

Доказательство теоремы ØBÉØA осуществляется прямым путем, то есть как цепочка импликаций: ØBÉB1, B1ÉB2, …, Bn-1ÉBn, BnÉØA, из которой делается вывод (в силу транзитивности импликации) о справедливости теоремы ØBÉØA. А в силу закона контрапозиции заключается о справедливости теоремы AÉB.

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

Пусть требуется доказать истинность некоторого утверждения A. Предположим, что A ложно, тогда ØA - истинно, поскольку закон противоречия (X&ØXºЛ), имеющий место в логике высказываний, означает, что одновременно не могут быть истинными утверждение и его отрицание.

После этого показывается, что тогда имеется некоторое утверждение B такое, что истинными являются одновременно два утверждения: ØAÉB и ØAÉØB.[4] ) Это и есть то, что называют абсурдом.

В логике высказываний тождественно-истинной является формула: (ØAÉB)&(ØAÉØB) ÉA (проверку чего мы предоставляем читателю).

Из этой формулы и (ØAÉB)&(ØAÉØB) по правилу вывода modus ponens следует, что имеет место утверждение A.

4. Доказательство необходимых и достаточных условий.

В математике часто встречаются теоремы вида: "Условие A равносильно условию В", что также выражается словами: "Для того, чтобы имело место условие А, необходимо и достаточно, чтобы выполнялось условие В". В виде формулы логики высказываний такая теорема может быть записана в виде: А~В. Доказательство ее обычно сводится к доказательству двух утверждений:

1. АÉВ (Если имеет место условие А, то выполняется и условие В)

2. ВÉА (Если имеет место условие В, то выполняется и условие А).[5] )

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

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

Существует и другой способ доказательства теорем вида: "Условие A равносильно условию В", когда одновременно доказывается необходимость и достаточность условия В для А. Для этого находится последовательность тождественно-истинных эквиваленций вида: A~A1, A1~A2,…,An-1~An, An~B, где A1,A2,A3,…,An - некоторые вспомогательные высказывания.