Доказательство под микроскопом

В статье обсуждаются вопросы: что такое математическое доказатель­ство и как оно устроено (какова его логическая структура)? Вводится на интуитивном уровне понятие математического доказательства в виде дере­ва. Выявлены преимущества подхода к уточнению понятия доказательства в виде дерева по сравнению с традиционным линейным доказательством.

Введение

В математике мы постоянно имеем дело с доказательствами. Однако редко за­даём себе следующие вопросы (и ещё реже пытаемся ответить на них): Что такое математическое доказательство? В чём его сущность? Как устроено математическое доказательство? Как выявить его структуру?

Представьте себе следующую ситуацию. На письменном экзамене по геометрии учащийся должен был доказать теорему Пифагора. Написав работу, ученик сдал её преподавателю. Преподаватель, прочитав работу, возвратил её с комментари­ем: «Это не доказательство!». На что ученик возразил: «Почему Вы считаете, что написанное мною —— не доказательство? Что такое доказательство? Вы на уро­ках геометрии давали определения многих понятий, но среди них не было понятия доказательства. На каком основании Вы можете утверждать, будто то, что я на­ писал, —— не доказательство? Как Вы можете доказать, что моё доказательство не является доказательством?!». У этой истории возможны два финала. Если преподаватель обладает широтой взглядов и не лишен творческого начала, то он может повысить на балл оценку ученику, у которого возникают столь неординарные во­просы. Если преподаватель —— педант, лишённый чувства юмора, то он, скорее всего, снизит оценку за непочтительность.

Эта весьма правдоподобная и поучительная история рассказана замечательным американским логиком Раймондом Смаллианом в одной из его великолепных, пол­ных юмора популярных книг по математической логике .

Я прочитала её много лет назад и с тех пор всегда пересказываю эту историю своим студентам на математическом факультете МПГУ в самом начале курса математической логики. Мне кажется, она блестяще объясняет, что будущему учителю математики изучать математическую логику совершенно необходимо хотя бы для того, чтобы прояснить для себя, что такое доказательство. (И. Л. Тимофеева)

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

Уточнение понятия «математическое доказатель­ство»

Сначала надо договориться, что понимать под математическим доказатель­ством на интуитивном уровне. Для краткости в дальнейшем будем говорить про­сто доказательство вместо слов математическое доказательство .

Прежде всего, под доказательством будем понимать не процесс обоснования какого-либо математического утверждения, а его результат, представленный в виде некоторого текста. Итак, доказательство представляет собой некоторый текст, состоящий из отдельных предложений. Особенность этого текста заключается в том, что составляющие его предложения логически взаимосвязаны друг с другом. Обычно эта связь выражается словами «предложение такое-то логически следует из предшествующих предложений таких-то». При кратком изложении доказатель­ства используется лишь слово «следовательно» (или равнозначное слово), а из каких именно посылок следует данное предложение (делается вывод) часто явно не ука­зано, да и сами посылки даже не всегда сформулированы. А что значит, логически следует? Обычно это никак не уточняется. При уточнении этого словосочетания предложение «Из ${\mathcal {A}}_{1},\,\ldots ,\,{\mathcal {A}}_{n}$ логически следует ${\mathcal {B}}$» можно понимать следующим образом: переход от предложений ${\mathcal {A}}_{1},\,\ldots ,\,{\mathcal {A}}_{n}$ к предложению ${\mathcal {B}}$ происходит по некоторому правилу вывода (логическому правилу), разумеется, если восстановле­ны все пропущенные шаги. Однако на практике, в неформальном доказательстве обычно не уточняется, в соответствии с каким логическим правилом делается тот или иной вывод.

В доказательстве должны быть исходные предложения, которые не являются следствиями предыдущих предложений (ведь текст конечен!). Такими исходными предложениями могут служить аксиомы той математической теории, в рамках которой проводится доказательство. Исходными могут быть и предложения, име­ющие место в силу определения. В некотором смысле такие предложения добавляются к аксиомам. В качестве исходных предложений могут также выступать вспомогательные допущения. В самом деле, в доказательствах очень часто встре­чаются слова «допустим, что . . . » .

Отношение логического следования, как бы мы ни уточняли это понятие, опре­делённым образом упорядочивает члены доказательства. Более того, этот порядок древовиден (имеет вид дерева с корнем — наименьшим элементом), поскольку на каждом шаге рассуждения происходит переход от некоторых предложений ${\mathcal {A}}_{1},\,\ldots ,\,{\mathcal {A}}_{n}$ к некоторому единственному предложению ${\mathcal {B}}$, непосредственно следующему из них по какому-либо правилу логики.

Доказательство в виде дерева

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

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

Заметим, что на практике только для самых простых утверждений приводится доказательство в указанном (уточненном) выше смысле. Обычные математиче­ские доказательства, как правило, носят относительный характер, когда наряду с аксиомами используются также утверждения, доказанные ранее или про которые известно, что они доказуемы. Для каждого такого предложения теоретически можно вставить в текст его собственное доказательство, устранив тем самым относительный характер доказательства, т. е. сведя всё к аксиомам.

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

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

Рассмотрение примера

Прежде чем перейти к этому описанию, сначала рассмотрим в качестве примера обычное несложное доказательство следующего утверждения: если натуральное число не делится на 6 и делится на 9, то оно нечётно.
Запишем это утверждение, используя логическую символику:

$6\nmid n\;\And \;9\mid n\longrightarrow 2\nmid n.$

В дальнейшем, при символической записи содержательных (неформальных) пред­ложений, будем использовать символы $\And$ (и), $\lor$ (или), $\longrightarrow$ (если то), $\lnot$ (не). Если $m$ не делится на $n$, наряду с записью $\lnot \;\left(m\mid n\right)$ будем использовать запись $m\nmid n$.

В кратком виде традиционное доказательство этого утверждения представляет собой следующее рассуждение: «Согласно условию, $n$ не делится на 6 и делится на 9. Поскольку $n$ делится на 9, то $n$ делится и на 3. Кроме того, $n$ не делится на 6, а значит, $n$ не делится на 2 или на 3. Следовательно, $n$ не делится на 2».

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

$6\nmid n\;\And \;9\mid n;\quad 9\mid n;\quad 3\mid n;\quad 6\nmid n;\quad 2\nmid n\lor 3\nmid n;\quad 2\nmid n.$

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

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

Если предложение ${\mathcal {B}}$ непосредственно следует из предложений ${\mathcal {A}}_{1},\,\ldots ,\,{\mathcal {A}}_{n}$ по какому-либо правилу логики, будем привычным образом записывать это так:

${\dfrac {{\mathcal {A}}_{1}\,\ldots \,{\mathcal {A}}_{n}}{\mathcal {B}}}.$

Если же на каком-то шаге рассуждения сделан сокращенный переход от предло­жений ${\mathcal {A}}_{1},\,\ldots ,\,{\mathcal {A}}_{n}$ к предложению ${\mathcal {B}}$, который не является результатом применения какого-то логического правила, записывать это будем с помощью двойной черты следующим образом:

${\begin{matrix}{\underline {\underline {{\mathcal {A}}_{1}\,\ldots \,{\mathcal {A}}_{n}}}}\\{\mathcal {B}}\end{matrix}}.$

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

Краткое рассуждение, приведённое выше, если его представить в виде дерева, имеет следующий вид (справа изображён граф, отражающий структуру дерева как частично упорядоченного множества):

${\dfrac {\begin{matrix}{\begin{matrix}{\underline {\underline {\dfrac {6\nmid n\;\And \;9\mid n}{6\nmid n}}}}\\2\nmid n\lor 3\nmid n\end{matrix}}&&{\begin{matrix}{\underline {\underline {\dfrac {6\nmid n\;\And \;9\mid n}{9\mid n}}}}\\3\mid n\end{matrix}}\end{matrix}}{2\nmid n}}.\qquad {\begin{matrix}\left(1\right)\\\;\\\;\\\;\end{matrix}}$

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

Два первых (верхних) шага осуществлены согласно двум правилам, которые называются правилами удаления конъюнкции:

${\dfrac {{\mathcal {A}}\;\And \;{\mathcal {B}}}{\mathcal {A}}}\quad {\text{и}}\quad {\dfrac {{\mathcal {A}}\;\And \;{\mathcal {B}}}{\mathcal {B}}}.$

Последний шаг, соответствующий самой нижней черте, осуществлён согласно следующему логическому правилу, являющемуся вариантом правила исключения возможных случаев:

${\dfrac {\begin{matrix}{\begin{matrix}\lnot {\mathcal {A}}\;\lor \,\lnot {\mathcal {B}}\end{matrix}}&&{\begin{matrix}{\mathcal {B}}\end{matrix}}\end{matrix}}{\lnot {\mathcal {A}}}}.$

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

Рассмотрим сначала сокращенный переход, отраженный следующим образом:

${\begin{matrix}{\underline {\underline {\qquad 6\nmid n\qquad }}}\\2\nmid n\lor 3\nmid n\end{matrix}}.$

Восстановив подразумеваемую посылку $2\mid n\;\And \;3\mid n\longrightarrow 6\mid n$, а также пропущен­ные логические переходы (умозаключения), получим более подробный вариант рассуждения. Представив восстановленную часть рассуждения в виде дерева (1), получим следующую картину:

${\dfrac {\begin{matrix}{\begin{matrix}\lnot {\mathcal {A}}\;\lor \,\lnot {\mathcal {B}}\end{matrix}}&&{\begin{matrix}{\mathcal {B}}\end{matrix}}\end{matrix}}{\dfrac {\lnot \left(2\mid n\;\And \;3\mid n\right)}{2\nmid n\lor 3\nmid n}}}.$

${\dfrac {\begin{matrix}{\begin{matrix}{\underline {\underline {\dfrac {6\nmid n\;\And \;9\mid n}{6\nmid n}}}}\\2\nmid n\lor 3\nmid n\end{matrix}}&&{\begin{matrix}{\underline {\underline {\dfrac {6\nmid n\;\And \;9\mid n}{9\mid n}}}}\\3\mid n\end{matrix}}\end{matrix}}{\dfrac {\lnot \left(2\mid n\;\And \;3\mid n\right)}{2\nmid n\lor 3\nmid n}}}.$