Элементы теории доказательств в курсе математической логики



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

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

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

Таким образом, изучение теории доказательств целесообразно начать с методов алгебры высказываний.

В алгебре высказываний обычно приходится доказывать, что некоторое высказывание B является логическим следствием некоторых высказываний A₁, A₂, …, A_n(в символической записи A₁, A₂, …, A_n |= B). Для этого применяют две схемы доказательств: прямое доказательство и косвенное.

Прямое доказательство того, что A₁, A₂, …, A_n |= B проводят по следующей схеме:

1. Формулы A₁,A₂, …,A_nсчитают входящими в доказательство.
2. К доказательству присоединяют ранее доказанные формулы, в частности тавтологии.
3. К доказательству присоединяют новые формулы, полученные по правилам вывода.
4. Доказательство закончено, если последняя формула есть B.

Эта схема обосновывается теоремой [5] о представлении доказательства в виде цепочки формул. Для доказательства этой теоремы требуется две леммы.

Лемма 1. A₁, A₂, …, A_n |=A_i, i = 1, 2, …, n.

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

Лемма 2. Если A₁, A₂, …, A_n |= B_j, j = 1, 2, …, m, и если B₁, B₂, …, B_m |= C, то

A₁, A₂, …, A_n |= C.

Доказательство.

Доказательство проведем с помощью таблицы истинности высказываний A_i, B_j, C, построенной по переменным, входящим хотя бы в одну из формул A_i, B_j, C.

Рассмотрим строки таблицы, в которых все A_i принимают значение T (истина). Из определения логического следствия получаем, что все B_j в этих строках также получают значения T, следовательно, и C в этих строках принимает значение T, а это и означает, что A₁, A₂, …, A_n |= C.

Теорема о представлении доказательства в виде цепочки формул.

A₁, A₂, …, A_n |= B, если можно составить цепочку формул E₁, E₂, …, E_m= B, в которой либо E_k = A_j, либо в этой цепочке есть предшествующие формулы такие, что.

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

Доказательство.

Пусть такая цепочка построена, E_k удовлетворяют условию теоремы, т. е. либо E_k= A_j, либо существуют предшествующие формулы такие, что.

Докажем, что A₁, A₂, …, A_n|= E_k для k = 1…, m (E_m = B). Доказательство проведем методом математической индукции.

При k = 1 имеем: предшествующих формул нет, значит E_{1 —} одна из посылок, т. е. E₁ = A_i для некоторого i= 1, 2, …, n. По лемме 1 имеем: A₁, A₂, …, A_n |= A_i= E₁, i = 1, …, n.

Пусть это справедливо для E₁, E₂, …, E_k–1, т. е. A₁, A₂, …, A_n |= E_i, i= 1, …, k — 1.

Докажем, что это справедливо и для E_k.

Если E_{k —} посылка, то применима лемма 1. Если E_kпосылкой не является, то из условия теоремы следует, что и так, как , то по предположению индукции A₁, A₂, …, A_n |= , j = 1, …, s и по лемме 2 имеем:

A₁, A₂ …, A_n |= E_k.

Тогда A₁, A₂, …, A_n |= E_k для любого k = 1, …, m.

Замечание. Очевидно, что в цепочку можно включать любую тавтологию. Если |=D (D — тавтология), то для любой формулы A имеем |=A→D. В качестве формулы A можно взять любую посылку A_i, тогда |=A_i→ D или A_i |=D.

Косвенное доказательство (или доказательство от противного) того, что

A₁, A₂, …, A_n |= B проводят по следующей схеме:

1. Формулы A₁,A₂, …,A_nсчитают входящими в доказательство.
2. К доказательству присоединяют формулу .
3. К доказательству присоединяют ранее доказанные формулы, в частности тавтологии.
4. К доказательству присоединяют новые формулы, полученные по правилам вывода.
5. Доказательство закончено, если в нем имеются две формулы и .

Для обоснования этой схемы нами была доказана следующая теорема.

Теорема (обоснование метода доказательства от противного).

A₁, A₂ …, A_n |= B, если из A₁, A₂, …, A_n, A_n+1 = можно составить цепочку формул E₁, E₂, …, E_m в которую входят две формулы и , и в которой либо E_k = A_j, либо в этой цепочке есть предшествующие формулы такие, что.

Доказательство.

Пусть такая цепочка построена.

После формул и вставим в цепочку тавтологию и применим правило отделения: Применим еще раз правило отделения .

Таким образом, в цепочке появилась формула . По теореме о представлении доказательства в виде цепочки формул имеем

A₁, A₂ …, A_n, |= . Отсюда получаем: A₁, A₂, …, A_n |= [5, с. 95].

Рассмотрим такой набор переменных, входящих во все формулы, что все A_iпринимают значение T, тогда и = T.

Так, как = F, то и = F, а следовательно B = T, а это означает, что

A₁, A₂, …, A_n |= B.

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

1. (правило отделения, правило заключения, modus ponens).
2. (правило отрицания, modus tollens).
3. (правило введения конъюнкции).
4. (правило удаления конъюнкции).
5. (правило введения дизъюнкции).
6. (правило удаления дизъюнкции).
7. (правило введения эквиваленции).
8. (правило удаления эквиваленции).
9. (правило контрапозиции).
10. (правило цепного заключения, правило силлогизма).
11. (правило перестановки посылок).
12. , (правило объединения и разъединения посылок).

Литература:

1. Успенский В. А., Верещагин Н. К., Плиско В. Е. Вводный курс математической логики. — М.: Физматлит, 2007. — 128 с.
2. Игошин В. И. Математическая логика и теория алгоритмов. М.: Издательский центр «Академия», 2010. — 448 с.
3. Колмогоров А. Н., Драгалин А. Г. Введение в математическую логику. М.: Издательство Московского университета, 1982. — 120 с.
4. Мендельсон Э. Введение в математическую логику. — М.: Наука, 1976. — 320 с.
5. Столл Р. Р. Множества. Логика. Аксиоматические теории. М.: Просвещение, 1968. — 232 с.