Непейвода Н.Н. Прикладная логика

Подождите немного. Документ загружается.

15.3. ИСПОЛЬЗОВАНИЕ ДОКАЗАТЕЛЬСТВ

411

зрения, а развитием понятий.

Положение 8. Классическая логика может подвести нас тогда, когда

мы стремимся использовать доказанные утверждения вида ∃x A(x) как

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

Положение 9. Классическая логика практически бессильна, когда

нужно формализовывать незнание.

Положение 10. Классическая логика может подвести в любой мо-

мент, если мы работаем с квазивысказываниями.

Положение 11. Выражаясь несколько метафорически, классическая

логика —логика конкретного знания и веры, а неклассическая —логика

построения, изменения знания и сомнения.

§ 15.3. ИСПОЛЬЗОВАНИЕ ДОКАЗАТЕЛЬСТВ

Центральным понятием, введенным математикой, явилось доказатель-

ство. Само его появление коренным образом видоизменило стиль мыш-

ления значительной части людей и положило начало тому, что сейчас

называют рациональным научным мышлением. Не зря на дверях плато-

новской Академии, по слухам, была надпись: «Не знающим геометрии

вход запрещен»

Как определил Аристотель:

Доказательство — речь, в которой из положенно-

го с необходимостью вытекает нечто, отличное от

положенного.

(15.15)

Это содержательное определение до сих пор остается лучшим, если от-

влечься от того, что ныне доказательство отнюдь не всегда связывают

со словами

Мы употребили здесь модальность ‘по слухам’, поскольку книга Диогена Лаэртско-

го, служащая почти единственным источником сведений о жизни античных филосо-

фов, отличается стилем, больше всего похожим на нынешние сборники низкопробных

анекдотов,и, соответственно, степень достоверности излагаемого в ней кажется весьма

средней (‘Хоть верь, хоть не верь’, как говорят в таком случае китайцы; под эту катего-

рию у них подходят и ответ дамы легкого поведения на вопрос, сколько ей лет, и доне-

сение полководца с далекой границы о победе). Хорошо знающие китайскую культуру

могут заметить, что в одном месте здесь понятие видоизменено, это сделано, поскольку

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

туры.

Даже расширение класса слов выражениями формализованного языка не всегда до-

статочно, см., например, диаграммы Венна в § 5.2.

412

ГЛАВА 15. КОРНИ НЕКЛАССИЧЕСКИХ ЛОГИК

Другое содержательное определение доказательства было дано на-

ми в первой части книги:

Доказательство — конструкция, синтаксическая

правильность которой гарантирует семантиче-

скую.

(15.16)

Естественно, что столь общее и гибкое понятие, как доказательство,

должно быть приложимо самыми разными способами.

Первое приходящее в голову применение доказательства — обеспе-

чение истинности некоторых утверждений. Но вопрос

Что есть истина?

(15.17)

столь труден, что на него не стал отвечать скептику Понтию Пилату да-

же сам Иисус Христос. Хорошо было тогда, когда считалось, что ма-

тематические утверждения истинны в некотором неоспоримом смысле.

Но даже в те времена глубочайшие мыслители, высказывавшие сужде-

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

нятий, сопровождали их оговорками, которые можно было понять лишь

на следующем уровне.

Пример 15.3.1.

Иммануил Кант, в частности, утверждал, что геометри-

ческие истины носят

априорный

характер, то есть предшествуют всяко-

му человеческому опыту и не зависят от него. Но обосновывал он это

следующим образом. Вещи мы можем мыслить себе лишь во времени и

в пространстве, и поэтому разум в некотором смысле навязывает законы

Природе. Поднявшись на следующий уровень, мы видим, что априор-

ность геометрии означает лишь ее предшествование

опыту, основанно-

му на классическом европейском рациональном мышлении

Тем не менее обоснование остается одной из основных функций до-

казательства. Другой вопрос — что обосновывает доказательство?

Ответ, на который скатываются даже многие математики, удручен-

ные выявившейся относительностью математических знаний: матема-

тическое доказательство устанавливает лишь то, что утверждение вы-

ведено по общепринятым и закрепленным традицией правилам игры

из утверждений, ранее признанных в соответствии с этими правилами

доказанными. Но тогда остается необъяснимой ‘порою фантастическая

эффективность математики в других науках’

. На самом деле здесь де-

Эта характеристика принадлежит Н. Бурбаки.

15.3. ИСПОЛЬЗОВАНИЕ ДОКАЗАТЕЛЬСТВ

413

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

тельств, причем выхолащивается его суть в угоду форме

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

15.3.1. Сведение новой задачи к уже решенным

Чистые математики занимаются тем, что решают задачи. Откуда берут-

ся задачи, уже немного рассматривалось в первой части (§23). А вот что

значит решить задачу — важный вопрос.

Никакое математическое доказательство не ведется с самого начала

(за исключением нескольких примитивных теорем в учебниках логики

и алгебры). Оно заканчивается ссылками на уже известные теоремы, ко-

торые когда-то тоже были математическими задачами. Таким образом,

как говорят в математическом фольклоре,

Решить задачу — значит свести ее к уже решен-

ным.

(15.18)

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

Пример 15.3.2.

Одна из простейших геометрических теорем — утвер-

ждение о возможности деления отрезка пополам. Разберем доказатель-

ство этого утверждения.Вначале из каждой из вершин отрезка радиусом

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

ся две точки пересечения этих двух окружностей. Через эти две точки

проводится прямая, пересечение которой с исходным отрезком дает его

середину.

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

решенными:

Через данную точку данным радиусом провести

окружность;

(15.19)

Найти две точки пересечения двух пересекающихся

окружностей;

(15.20)

Найти точку пересечения двух прямых.

(15.21)

Пренебрежение содержанием в пользу формы — один из мощнейших и, соответ-

ственно, обоюдоострых методов математической (да и любой другой, в частности, юри-

дической) формализации. Он настолько органически присущ ей, что вошел в сам тер-

мин формализация. Вопрос здесь в мере и вкусе. Сделаешь один лишний шаг, и содер-

жание пропадет,сделаешь в меру —подчеркнутся те особенности содержания, которые

оставались скрытыми.

414

ГЛАВА 15. КОРНИ НЕКЛАССИЧЕСКИХ ЛОГИК

Первая из данных задач является

постулатом

Евклида

. Вторая — вы-

водится из аксиом Евклида,но для применения данного построения тре-

буется предусловие

Расстояние между центрами окружностей мень-

ше суммы их радиусов и больше их разности.

(15.22)

Далее, по двум полученным точкам пересечения можно провести пря-

мую (опять постулат Евклида, опять исходное построение). Эта прямая

пересекается с исходным отрезком, и мы опять-таки ссылаемся на ре-

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

ника совпадают, тем самым обосновав корректность проведенного по-

строения.

Эта привычка сводить новые задачи к уже решенным послужила да-

же основанием для шутки, которая на самом деле достаточно точно от-

ражает суть математического метода:

Математику задали вопрос:

— Как приготовить чай?

—Элементарно.Берем чайник, наливаем в него воду, зажигаем газ,

ставим чайник на огонь, ждем, пока закипит, выключаем газ, кладем

заварку в соответствующий сосуд, заливаем ее кипятком, ждем еще 5

минут, и чай готов.

— А если у нас уже есть чайник с кипятком?

— Выливаем из него кипяток и сводим задачу к предыдущей.

Именно так и действует хороший математик, решая задачу.

15.3.2. Выявление условий, при которых

можно пользоваться данным утверждением

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

нее важное. Когда говорят, что некоторое утверждение строго доказано,

возникает иллюзия, что теперь-то им можно пользоваться вовсю. Как

бы не так!

Пример 15.3.3.

Допустим, мы знаем, что некоторая характеристика

λx f(x)

физического процесса непрерывно изменяется на отрезке

[0, 1]

Евклид строго различал аксиомы (истинные утверждения) и постулаты (исходные

построения, исходные задачи, предполагающиеся решенными).

15.3. ИСПОЛЬЗОВАНИЕ ДОКАЗАТЕЛЬСТВ

415

и принимает на его концах значения разных знаков. Тогда имеется сле-

дующий алгоритм нахождения точки, в которой она имеет значение

Обозначим текущий отрезок

(т. е. вначале

X = [0, 1]

На его кон-

цах функция f принимает значения разных знаков.

Выделенное утвер-

ждение сделаем инвариантом построения. Выпишем его явно:

Функция f непрерывна на отрезке X и принима-

ет на его концах значения разных знаков.

(15.23)

Разделим

пополам. В его середине

могут оказаться три возможно-

сти.

f(a) = 0

. Тогда мы точно нашли корень.

f(a)

имеет тот же знак, что и

f(X.low)

, где

X.low

— нижняя гра-

ница отрезка

. Тогда возьмем в качестве нового значения

от-

резок

[a, X.up]

, где

X.up

— верхняя граница отрезка

f(a)

имеет тот же знак, что и

f(X.up)

. Тогда в качестве нового

значения

берем

[X.low, a]

Таким образом, мы либо на некотором шаге останавливаемся и выдаем

точное значение корня, либо вдвое уменьшаем интервал, на котором он

заключен. Получившаяся последовательность стягивающихся сегмен-

тов дает искомый корень.

Казалось бы (как и утверждается в большинстве учебников по про-

граммированию), мы получили построение корня с любой наперед за-

данной точностью. Но рассмотрим чуть подробнее имеющийся у нас

разбор случаев. Любая самая маленькая ошибка в вычислении

f(a)

мо-

жет повлечь за собой выбор неправильной половины интервала и боль-

шие ошибки в вычислении корня. Итак, на самом деле

корень мы не вы-

числяем

. А что же нам гарантирует данное доказательство? Не так уж

мало. Если мы достаточно потрудимся, мы с гарантией найдем такую

точку

, что

f(x

) ∼ 0

в пределах точности вычислений

. Итак, мы

находим не корень, а точку, где значение достаточно мало.

В рассмотренном примере наличие разбора случаев позволило вы-

делить неявное предположение, что f вычисляется абсолютно точно,

выяснить существенность данного предположения для дальнейшего по-

строения и установить, что же остается, если данное предположение не

выполнено

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

416

ГЛАВА 15. КОРНИ НЕКЛАССИЧЕСКИХ ЛОГИК

15.3.3. Получение построения,

дающего некоторый результат

Вернемся к примеру 15.3.3. Посмотрим, что на самом деле использо-

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

деления пополам.

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

получается либо конкретное число, либо последовательность, его опре-

деляющая. Но эта фраза неалгоритмична, поскольку проверить за ко-

нечное число шагов, остановится ли наш алгоритм деления пополам,

невозможно. Таким образом, на самом деле алгоритм извлекается не из

доказательства теоремы о существовании нуля функции, а из доказа-

тельства следующей, приближающей ее, теоремы.

Предложение 15.3.1. Если функция

f непрерывна и меняет знаки на

концах отрезка [a, b], где a < b, то для любого ε > 0 имеется отрезок

, b

] ⊂ [a, b] длины не больше ε, в котором есть корень f .

А теперь запишем то, что у нас получилось в результате доказатель-

ства, в виде паскалеподобной процедуры:

function DivHalfe(f:function(x:real):real,

a,b:real):real;

var a1,b1,c: real; begin

a1:=a; b1:=b;

DivHalfe:=lim a1 from

c := (a1 + b1)/2;

if f(c) = 0 then

a1:=c; a2:=c;

ﬁ;

if (f(c) ∙ f(a1) < 0) then

a2:=c;

ﬁ;

if (f(c) ∙ f(a2) < 0) then

a1:=c;

ﬁ;

end;

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

15.3. ИСПОЛЬЗОВАНИЕ ДОКАЗАТЕЛЬСТВ

417

Заметим, что здесь мы учли завершение процесса после того, как ко-

рень случайно оказался на середине одного из отрезков, лишь косвен-

ным образом: мы после этого полагаем a1 и b1 равными друг другу, и

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

операцию взятия предела к бесконечному циклу, а если бы мы попы-

тались учесть еще и случаи, когда алгоритм быстро заканчивается, нам

пришлось бы писать цикл два раза: первый раз с выходом, а второй раз

в случае, когда цикл продолжался бесконечно.

В рассмотренном примере ярко проявилась особенность математи-

ческих построений: полное пренебрежение реально требуемыми ресур-

сами, работа с бесконечными процессами и сведение новых построений

к предыдущим (в данном случае — к пределу последовательности).

15.3.4. Произнесение заклинания, дабы освятить свое

либо предложенное заказчиком решение

Казалось бы, в серьезной работе такому использованию доказательства

не стоит уделять внимание, но на практике слишком часто ученые вы-

полняют роль, которая при язычестве отводилась магам, жрецам либо

шаманам, а в мировых религиях порою выполняют за мзду священни-

ки. Мы остановимся на признаках, по которым можно распознать такой

труд.

Во-первых, видно, что сначала писался результат, а затем к нему

приделывалось обоснование. Во-вторых, результат содержательно ком-

ментируется в пользу одного из фирменных решений. В-третьих, эти

комментарии, как правило, самое плоское место писания. И, наконец,

самое важное: отмечаются лишь достоинства предложенного решения,

а его ограничения и недостатки как будто не существуют. Если же для

соблюдения видимости объективности приводятся другие решения, то

здесь делается упор на их недостатки и ограничения, и порою сквозь зу-

бы признаются отдельные достоинства, конечно же, напрочь загублен-

ные недостатками.

Глава 16. Интуиционистская логика

Интуиционистская логика — наиболее близкий во многих отношени-

ях к классической член семейства неклассических логик. Более того,

она — практически единственная неклассическая логика, являющаяся

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

ми, выделенными свойствами. Если классическая логика имеет почти

стандартную и простейшую из возможных семантику в виде таблиц ис-

тинности

, то интуиционистская логика замечательна тем, что для неё

сосуществуют четыре известных разнородных класса семантик для не-

классических логик. Поэтому интуиционистская логика может послу-

жить в качестве полигона для семантик неклассических логик, приме-

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

§ 16.1. СОЗДАНИЕ ИНТУИЦИОНИСТСКОЙ ЛОГИКИ

16.1.1. Брауэр: идея конструктивности

К началу

века математика столкнулась с кризисом оснований, про-

являвшимся как в грубых парадоксах типа противоречий (например,па-

радокс Рассела в ч. 1, § 1.7), так и в том, что понятия, изначально счи-

тавшиеся тождественными, стали заметно расходиться.

Вернемся к парадоксу института математики из § 244 и напомним

его логическую суть.

Предложение 16.1.1. Если классическая теория

неполна и имеются

обозначения для всех элементов универса (эти термы будем называть

конкретными), и мощность универса не меньше 2, то имеется такая

Но вспомните семантику булевых алгебр из первой части.

16.1. СОЗДАНИЕ ИНТУИЦИОНИСТСКОЙ ЛОГИКИ

419

формула A(x), что доказано ∃x A(x), но ни при каком конкретном u не

может быть доказано A(u).

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

G — неразрешимая в Th замкнутая формула.

Пусть 0 и 1 — два различных элемента универса, которые имеются по

определению. В качестве A(x) возьмем

(G & x = 1) ∨ (

G & x = 0).

∃x A(x)

доказывается разбором случаев G и

. Но если бы при каком-

то u было доказано A(u), то заодно была бы разрешена и проблема G,

которая неразрешима по предположению.

Мы видим, что парадокс института математики зависит лишь от те-

оремы Гёделя о неполноте и от логического принципа

A ∨

В начале

века теорема Гёделя о неполноте могла лишь приснить-

ся в страшном сне, но математики уже заметили, что понятия ‘суще-

ствовать’ и ‘быть построенным’ стали заметно различаться. Появи-

лось понятие чистых теорем существования, в которых нет постро-

ения объекта, чье существование доказывается

. Козел отпущения, на

которого можно было свалить ответственность за чистые теоремы су-

ществования, нашелся сравнительно быстро: аксиома выбора

(§ 32).

Но молодой голландский ученый Л. Э. Я. Брауэр уже в 1908 г. опу-

бликовал на голландском языке статью под вызывающим названием:

“О недостоверности логических принципов”.

Личность самого Брауэра весьма интересна и необычна. Его первая

книга имела заголовок “Жизнь, искусство и мистика” и была посвяще-

на философии, на него оказали большое влияние идеи Ницше, Бергсона

и Хайдеггера, а также восточная (прежде всего индийская) философия.

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

Упомянутая выше его диссертация также была прежде всего философ-

ским трудом.

Идеей диссертации Брауэра было то, что законы классической ло-

гики не носят ни априорного, ни абсолютного характера. Они выведе-

ны прямым обобщением законов работы с небольшими конечными со-

Любопытно, что в человеческой истории зачастую самые грязные явления называ-

ются чистыми!

И на первый взгляд поделом! Она действительно ответственна в классической мате-

матике за самые грубые формы чистых теорем существования.

420

ГЛАВА 16. ИНТУИЦИОНИСТСКАЯ ЛОГИКА

вокупностями устойчивых во времени объектов. Затем они были неза-

конно перенесены на оперирование с бесконечно большими совокуп-

ностями и стали, соответственно, неадекватны. Эта неадекватность не

осознавалась длительное время и в конце концов завела математику в

громадный тупик, из которого не выберешься пересмотром отдельных

аксиом. Нужно либо полностью отказаться от бесконечных совокупно-

стей объектов, либо перейти к другой логике, либо перестать прида-

вать какой-то содержательный смысл математическим утверждениям,

признав их чисто абстрактными, идеальными. Далее, математика пол-

ностью игнорирует незавершенность человеческого знания и незавер-

шенность, как говорил Брауэр — становящийся характер многих ма-

тематических объектов. В частности, действительное число рассматри-

вается как уже существующая бесконечная десятичная дробь, а не как

процесс получения все более и более точных приближений.

Даже если мы точно определили абстрактный объект, например, чи-

сло

π, мы все равно не знаем его полностью. Например, вычислив 10

знаков данного числа, мы можем так и не узнать, есть ли в его десятич-

ном разложении последовательность 30 семерок.

Чтобы преодолеть рассмотренные выше трудности, предлагалось

разрушить до основания все здание математики и заново построить его

на новых принципах. Но откуда было взять новые принципы, если даже

логика была поставлена под сомнение? Брауэр предложил пользоваться

новой логикой, которая, как он утверждал, гораздо интуитивно понят-

нее, чем классическая, и описывает математические утверждения не как

абстрактные истину и ложь, а как предложения о возможности выпол-

нить некоторое умственное построение, решить некоторую конструк-

тивную задачу

. Математическое доказательство должно дать требуе-

мое построение вместе с его обоснованием. Методы, дающие построе-

ния, Брауэр (и не только он) называл эффективными методами.

Брауэр прекрасно понимал, что математическое построение — сущ-

ность весьма высокого уровня и для его обоснования недостаточно ссыл-

ки на практику, тем более что в те времена точного понятия алгоритма,

которое математически мыслящему человеку соблазнительно взять в ка-

честве формализации расплывчатого понятия вычисления, еще не су-

Здесь не зря мы добавили прилагательное к задаче. Как говорилось в § 15.3.1, мате-

матическая задача отнюдь не обязательно включает построение, вспомните, что значит

ее решить?