«Прикладная логика Учебное пособие Рекомендовано Государственным комитетом Российской Федерации по высшему образованию в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальностям ...»

Н. Н. Непейвода

Прикладная логика

Учебное пособие

Рекомендовано Государственным комитетом Российской Федерации по

высшему образованию в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальностям “Математика”, “Прикладная математика”, “Лингвистика”, “Философия” и “Психология”.

ISBN 5-7029-0074-X

c Непейвода Н.Н., 1997–2002. Все права защищены

Оглавление

Введение 0.1. Что такое современная логика?............

ix 0.2. Методологические принципы, на которых основано... ix данное изложение...................

0.3. Как работать с данной книгой?............

... xviii 0.4. Введение ко второму изданию............

... xxv... xxix ЧастьI. Язык математики 1. Необходимость точного языка в математике 1.1. Как и почему появился язык математической логики?..

1.2. Зачем изучать формальный язык математики?......

2. Простейшие высказывания 2.1. Что такое высказывание?............

2.2. Математическая интерпретация высказываний...... 2.3. Предметы и универс. Термы..........

...... 2.4. Предикаты и элементарные формулы.....

...... 2.5. Некоторые обозначения.............

............ 3. Запись высказываний. Логические формулы 3.1. Связка ‘и’...................

3.2. Связка ‘или’.............. ...

........ 3.3. Связка ‘следует’...............

........ 3.4. Связка ‘тогда и только тогда’........

........ 3.5. Связка ‘не’..................

........ 3.6. Таблицы истинности............

........ 3.7. ‘Для всех’...................

................ iii

ОГЛАВЛЕНИЕ

iv 3.9. Ограниченные кванторы..................

3.8. ‘Существует’......................... 4. Методы перевода с естественного языка на математический и обратно 4.1. Кванторы. Области действия. Свободные и связанные переменные..........................

4.2. “Многоэтажные” кванторы. Дополнительные 4.3. «Если на клетке слона увидишь надпись “буйвол”, не верь 4.4. Равенство. Единственность и неединственность.....

4.5. Таблицы истинности и формулировка отрицаний....

4.6. Простейшие преобразования классических формул...

5. Базовые математические понятия 5.1. Множества. Диаграммы Эйлера и Венна.........

5.2. Кортежи, n-ки, наборы, прямые произведения, прямые 6. Индукция и определения 6.2. Об индуктивных определениях........... ....

6.3. Трансфинитная индукция и ординалы...........

6.3.1. Построение начального отрезка ординалов....

6.3.2. Свойства вполне упорядоченных множеств....

6.3.3. Представления ординалов. Действия над 6.3.4. Построение функций рекурсией по определению 7. Введение в синтаксис 7.1. Синтаксис логического языка................ 7.2. Корректность синтаксических определений........ 7.3. Свободные и связанные переменные. Подстановка.... 8. Семантика классической логики 8.1. Интерпретация языка конечных типов....

8.2. Теория, модель, логическое следствие....

8.3. Теорема о замене эквивалентных.......

8.4. Булевы алгебры и алгебраическая семантика 8.5. Языки высших порядков...........

9. Семантические таблицы для классической логики 9.1. От таблиц истинностик семантическим таблицам...

9.2. Правила разбиения формул в семантических таблицах 9.3. Семантические таблицы с кванторами..........

9.4. Сокращенные семантические таблицы.........

9.5. Исчисления традиционного типа.............

9.6. Секвенции и формализация семантических таблиц...

9.7. Семантические таблицы с равенствоми для теорий...

10. Элементы нестандартного анализа 10.1. Историческое введение..............

10.2. Нестандартная модель...............

10.3. Нестандартная действительная ось.......

10.4. Нестандартные переформулировки.......

10.5. Суперструктуры и теорема Лося.........

10.5.1. Аксиома выбора, некоторые ее следствия 10.5.2. Ультрафильтры и структуры.......

11. Естественный вывод в классической логике 11.1. О структуре математических доказательств......

11.2. Правила естественного вывода.............

11.2.1. Общая структура. Импликация и конъюнкция

ОГЛАВЛЕНИЕ

11.2.3. Отрицание. Приведение к абсурду 11.4. Правила формулировки отрицаний и согласованность 11.7. Метод резолюций и его сравнение с методом 15. Корни неклассических логик 15.1. Корни неклассических логик в традиционной логике 15.1.3. Закон исключенного третьего.........

15.1.4. Закон достаточного основания.........

15.1.5. Алгебраические законы логики........

15.2. Сила и недостатки классической логики........

15.3. Использование доказательств..............

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

15.3.2. Выявление условий, при которых можно 15.3.3. Получение построения,дающего 15.3.4. Произнесение заклинания, дабы освятить 16. Интуиционистская логика 16.1. Создание интуиционистской логики............

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

16.1.2. Интуиционизм и программа Гильберта......

16.1.3. Формализация и первые интерпретации.....

16.1.6. Вторая героическая эпоха: математические 16.2. Интерпретация Колмогорова................

16.3. Формализация Гейтинга...................

16.4. Первые математические модели 16.6. Семантические таблицы для интуиционистской логики.

16.7. Полнота семантических таблиц..............

16.8. Фундаментальные результаты теории доказательств...

16.9. Реализуемости и вариации интуиционистских принципов 16.10.Интуиционистская логика и категории..........

16.11.О формализации незнания.................

ОГЛАВЛЕНИЕ

viii 17. Семантики Крипке и базирующиеся на них логики 17.2. Модальные логики и их модели Крипке..........

17.2.1. Язык и общая конструкция модели........

17.2.2. Свойства отношения достижимости и конкретные 17.3. Вариации на тему модальностей и Крипке........

17.3.1. Временные, динамические и 18. Проблема отрицания 18.1. Три стороны классического отрицания и четвертая — 18.3. Логика с сильным отрицанием.............

18.4. Логика неполной информации.............

18.5. Основы логики противодействия............

18.6. Паранепротиворечивая логика.............

19. Доказательства и программы 19.1. Изоморфизм Карри-Ховарда..............

19.3. Призраки и классификация выводов..........

19.5. Проблема совместимости операторовна примере exit Введение

ЧТО ТАКОЕ СОВРЕМЕННАЯ ЛОГИКА?

§ 0.1.

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

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

Проверяли ли они на самом деле — другой вопрос. Критический анализ историВВЕДЕНИЕ Математику неприлично заниматься тем, что не допускает точной формулировки, и самому формулировать утверждения, которые могут быть поняты двояко. Ему неприлично выдавать правдоподобное утверждение за доказанное, он имеет право утверждать лишь то, для чего он имеет полное доказательство. Ему нельзя утаивать открытое им доказательство, он обязан предоставить его на максимально широкое обсуждение для проверки всеми заинтересованными лицами. Если кто-то нашел ошибку в его доказательстве, математик не имеет права настаивать на своем, а обязан поблагодарить за помощь и публично объявить о своей ошибке, пересмотрев доказательство либо формулировку теоремы.

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

Далее, если каноны ремесла не требуют иного обоснования, кроме традиции, и имеют тенденцию превращаться в обязательные стандарты, нарушение которых карается, каноны науки должны быть обоснованы и ческих трудов выявляет, в частности, что многие работы по хронологии ссылаются в конечном итоге на одну и ту же работу Жана Скалигера, где была принята масса произвольных допущений.Первым обратил внимание на недостоверность традиционной хронологии Исаак Ньютон, за что его сразу же обвинили в том, что он стал к старости выживать из ума (в то же самое время он блестяще провел реформу английского монетного двора, что отнюдь не является признаком безумия; нам бы столь безумных министров!). В наше время эту традицию (называемую гиперкритицизмом) продолжает, в частности, академик А. Т. Фоменко [31]. Читая труды гиперкритиков, можно заметить, насколько озлобляет и заставляет зарываться тупое сопротивление со стороны специалистов всякой критике того, что считается незыблемыми устоями науки. Как правило, гиперкритики приходят к тому, что начинают брать под сомнение все и вырабатывают фантастическую концепцию ничуть не лучше критикуемой, тем самым выходя за границы и науки, и здравого смысла. Всегда сохраняйте чувство меры! Беда России в том, что в ней слова ‘оппортунист’ и ‘либерал’ всегда были презрительными, а ‘консерватор’ понимался как тупой защитник существующих властей.

Эти достаточно точные и строгие критерии показывают, почему именно в среде математиков устойчивей всего сохраняются понятия научной этики и чести ученого. А без этих понятий любая наука мертва. В последнее время в связи с внедрением в науку квазиконкурентной системы грантов и культа успеха вместо культа Истины пошел целый шлейф скандалов в связи с разоблачением множества фальсификаций данных и опытов в естественных науках. Впрочем, понятия этики и чести начали стремительно исчезать из науки сразу после того как она стала средством создания орудий массового убийства. Но научная этика, даже сохраненная в полном объеме, отнюдь не исчерпывает человеческой; безупречно честный в науке человек может быть подонком в жизни.

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

Если рассмотреть соотношение ремесла, искусства и науки с другой стороны, со стороны используемого языка, то отличие науки в том, что она не останавливается на стадияx ощущений, образов и представлений, как ремесло либо искусство, но требует развития понятий и терминов. Понятие — это языковая единица, имеющая достаточно четко определенный смысл; термин — слово, смысл которого фиксирован.

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

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

Логика как наука имеет уникальную историю. Она была создана на заре европейской цивилизации, в классической Греции, практически одним человеком — Аристотелем. В те времена впервые высказывания и рассуждения стали проверяться не на соответствие авторитету, а на убедительность для равных тебе граждан. Естественно, что в обстановке переоценки ценностей появилась орда софистов и демагогов, нагло надувавшиx не только народ, но и достаточно образованных людей тонкой подменой понятий, некорректными переходами в благопристойно выглядящих рассужденияx, и т. п. Например, приведем следующее в высДанной метафорой автор обязан О. M. Аншакову.

ВВЕДЕНИЕ

xii шей мере “логичное” рассуждение.

Значит, удмурты владели большей частью мира.

Это потребовало противоядия, создания канона доказательных рассуждений, создания, как выразился Кант, «цензуры мысли». Аристотель дал инструмент в столь совершенной форме, что более двух тысяч лет его оставалось лишь комментировать и шлифовать. Он воспользовался высшими достижениями тогдашней научной мысли, в частности, широко применяя буквенные обозначения для переменных, незадолго перед тем изобретенные математиками.

Аристотелева логика часто называется философской либо формальной. Она стала неотъемлемым компонентом образования европейских философов, юристов, теологов, т. е. людей, длительное время составлявших подавляющую и самую влиятельную часть образованного слоя общества.

Можно считать, что отношение к логике явилось одним из межевых камней между западной и восточной культурами. Аверроэс (Ибн-Рушд, мавританский ученый XII века, традиционные даты жизни 1126–1198) поставил вопрос:

Христиане разных толков, иудеи и мусульмане восприняли этот вопрос серьезно4 и ответили на него по-разному. Католики решили, что, конечно же, подчиняется, поскольку Он — благая сила и соблюдает те законы, которые Сам установил. Мусульмане столь же ясно и недвусмысленно заявили, что требовать, чтобы Аллах чему-то подчинялся, — оскорбление Аллаха. Православные и иудеи заняли промежуточную позицию.

Заметим, что уже сама по себе постановка такого вопроса подчеркивает исключительную роль логики. Скажем, вопрос:

очевидно глуп. Тем не менее многие физики и люди, привыкшие считать физику основой научного взгляда на мир, втайне чувствуют себя уязвленными некорректностью предыдущего вопроса и изо всей силы стремятся создать физическую теорию творения (см., например, [25] как глубокое исследование с данной целью и [27] как работу, открыто высвечивающую цели данного направления).

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

которых было достаточно юристам и теологам5.

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

Пирс в XIX веке заметил, что выводы герменевтики являются частным случаем необходимых для практики выводов частных случаев из других частных. Логику такого вывода он назвал абдуктивной логикой7.

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

Формальная наука отличается тем, что она проверяет прежде всего форму и поэтому может рассуждать про глокую куздру из знаменитого предложения академика Щербы «Глокая куздра штеко быдланула бокра и кудрячит бокренка» столь же уверенно, как про сивую кобылу.

Слово ‘герменевтика’ произошло от имени Гермеса Трисмегиста, не то бога, не то жреца бога Гермеса, которому приписывался тайный трактат по магии и алхимии. Мало того, что этот трактат не подлежал передаче непосвященным, он и написан был таким темным и уклончивым языком, что истолковать хоть что-нибудь из него было почти невозможно. Вот поэтому искусство толкования и назвали его именем.

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

1. Получение общего закона по множеству частных случаев.

2. Получение из общего утверждения другого общего либо частного.

ВВЕДЕНИЕ

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

Математики заметили, что логика могла бы стать математической наукой, но таковой еще не являлась8.

Предвестники нового этапа появились в работах Лейбница, когда традиционная задача математики: “заменить вычисления рассуждениями” была инвертирована и превратилась в задачу математической логики: “заменить рассуждения вычислениями”. Аппарат для этого начал возникать в трудах логиков XIX века, прежде всего английской школы — де Моргана, Буля, и американского логика Пирса... А развитие по-настоящему пошло лишь в XX веке, когда математика доросла до того, чтобы применять свои методы для анализа своей собственной структуры, и, таким образом, первой из наук перешла со стадии экстенсивного роста на стадию рефлексии9. Появилась новая наука — математическая логика, унаследовавшая задачи философской логики, но использовавшая для их решения математический аппарат. Как сформулировал А. А. Марков: «Математическая логика — логика по предмету, математика по методу».

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

Естествоиспытатели, евреи и математики, конечно же, не члены деления в смысле традиционной логики. Один и тот же человек может входить во все эти группы, и более того, иногда вхождение в пересечение групп помогало первопроходцам. Например, германский еврей-математик Г. Кантор создал теорию множеств, вдохновленный, в значительной степени, проблемой истолкования многих положений Талмуда и Каббалы, касающихся таких бесконечных сущностей, как Бог и Высшие Силы.

Рефлексия — самоанализ, в науке — применение методов данной науки к ней самой.

Традиционное изложение традиционной логики, в частности, не выдерживает проверки рефлексией.

следующие:

1. Выписываются те предположения, при которых делаются выводы (например, что субъективная привлекательность суммы денег прямо пропорциональна количеству денег).

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

3. Можно проверить, действительно ли сделанный вывод строго следует из принятой модели или же автор выдвигает лишь правдоподобную гипотезу.

4. Резко облегчается переход к структурам, приспособленным для интерпретации на компьютере.

Соответственно, недостатки точной науки следующие:

1. Помимо выписанных предположений, очень многие, и зачастую самые критичные для рассматриваемой ситуации, прячутся в общий применяемый аппарат. Эти неявные предположения, как правило, не осознают даже специалисты. Например, когда в XX веке наконец-то занялись вопросом, что же можно измерять действительными числами, выросла целая теория измерений, пользуясь которой можно, в частности, практически всегда отвергнуть предположение, сделанное в соответствующем пункте достоинств.

2. Поскольку термин — монумент понятия, он полностью теряет гибкость и зачастую в конкретной ситуации он начинает означать вовсе не то, что имелось в виду первоначально. Например, способность решать задачи из тестового набора может не иметь никакого отношения к способности гибкого реагирования на изменяющуюся реальную ситуацию.

3. Поскольку строгое доказательство может содержать много шагов и вовлекать многие утверждения, которые, как стыдливо говорят ученые, «выполнены в реальной ситуации лишь приближенно», в ходе такого обоснования соответствие реальности может потеряться, так что строго доказанный результат требует содержательной перепроверки при применениях.

ВВЕДЕНИЕ

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

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

Первым широко прозвучавшим рефлексивным результатом математической логики была серия теорем Гёделя, появившихся в 1930–1931 гг.

До этого было общепринято10 считать, что математика может быть уточнена таким образом, чтобы в принципе любое истинное математическое утверждение могло быть доказано, и конечно же, такое уточнение является непротиворечивым. Таким образом, предполагалось, что математическая теория должна быть полной и непротиворечивой. Естественно, не исключалось, что существующая теория неполна, но ставилась задача ее пополнения. Гёдель доказал, что полна и непротиворечива лишь чистая логика. Любая достаточно сильная конкретная теория неполна, в ней есть утверждение, которое нельзя ни доказать, ни опровергнуть средствами этой теории. Более того, непротиворечивость никакой математической теории, включающей понятие (по крайней мере) натуральных чисел, не может быть доказана внутри этой теории11.

На самом деле рефлексивные результаты появились лет на 20 раньше, но шведского логика Лёвенгейма, доказавшего, что ни одна математическая теория не может, в частности, однозначно определить множество натуральных либо действительных чисел, постигла судьба многих первооткрывателей: он угодил в психлечебницу, оставшись непонятым, а его результаты вспомнили тогда, когда сообщество до них дозрело.

Слабые возражения о том, что теоремы Гёделя не имеют никакого отношения к утверждениям, реально используемым математиками, Слово ‘общепринято’ означает мнение подавляющего большинства специалистов;

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

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

“Учение всесильно, потому что оно верно”. Ученый не может глаголить истины, он должен проверять то, что претендует на статус истины.

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

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

Например, если мы в качестве базовой теории возьмем математический анализ, то у нас появятся действительные числа вместе со всеми операциями; если возьмем графы, у нас появятся пути, циклы, топологические преобразования графов и т. п. Далее в выбранной теории дается представление исследуемых понятий. Например, принимается решение считать плотность материала действительным числом, а не функцией от точки пространства, считать зависимость одной характеристики от другой непрерывной, либо просто записываются графы в случае более привычного для нынешней информатики способа описания. Пишутся уравнения, связывающие характеристики элементов, либо другие соотношения между представлениями понятий, и на этом построение модели завершается, чтобы сразу же начаться снова, потому что, как правило, модель оказывается неадекватной12. Так что подбор формализации столь же важен для задачи, как выбор супруга для человека, и часто делается столь же безответственно, что превращает работу в мазохистское самоистязание либо в шарлатанство высшего класса, прикрытое весьма умными терминами, но начисто забывшее о реальной цели, для которой все делалось. Именно здесь очень полезен логический анализ, позволяющий быстро вскрывать глубинные корни недостатков в формализации и выявлять неадекватность патентованных и широко рекламируемых средств.

Слово адекватный является практически синонимом слова подходящий, но мы предпочитаем данный, более “ученый” термин русскому слову потому, что адекватность модели порою настолько далека от здравого смысла, что лучше уж избежать всякой ссылки на обыденное сознание, содержащейся в слове ‘подходящий’.

ВВЕДЕНИЕ

xviii

МЕТОДОЛОГИЧЕСКИЕ ПРИНЦИПЫ,

НА КОТОРЫХ ОСНОВАНО ДАННОЕ ИЗЛОЖЕНИЕ

§ 0.2.

Автор осознает, что данное пособие написано не в стиле, привычном для русской научной литературы, что оно также не подходит ни под стиль научно-популярных работ, ни под становящийся в последнее время модным общепринятый американский стиль легкого, зато профанирующего13, изложения. Тяжелый выбор — идти практически непроторенным путем14 — был сделан сознательно. Логика отличается от других наук фундаментальностью рассматриваемых проблем, а математическая логика — сочетанием весьма сложного аппарата с сохранением философской глубины и с полностью неординарным взглядом на математический мир. Видимо, современная логика — лишь зачаток первой из наук нового поколения, призванных сочетать аналитичность научного метода с синтетическим восприятием гуманитарного взгляда. Цивилизация, даже высшие слои которой несут в себе по крайней мере две практически невзаимодействующие культуры, обречена.

Автор начнет с того, что он абсолютно не разделяет системы взглядов “религии прогресса”15, de facto сделавшейся основой современноВ древней Греции профан — человек, не посвященный в некоторые таинства. В таком смысле нехристь — профан для христиан. Профанация — в Греции так называлось преступление, связанное с раскрытием священных тайн непосвященным, а в наше время так называют представление сложных вопросов в форме, где опускаются “излишние” тонкости в целях увеличения объема продаж соответствующей книги путем создания у невежд иллюзии, что они все понимают. Профанация ведет к взрывообразному расширению слоя полуобразованных людей, которые являются страшнейшим злом: у них нет сомнений в том, что они все знают; они зачастую принимают за знания самые дикие предрассудки либо перемешивают их с предрассудками; и, наконец, если они что-то, как считают, поняли, они готовы свернуть шею любому, кто понимает данный вопрос иначе.

За свои убеждения люди порою шли на костер, но гораздо охотнее посылали на костер других.

(Станислав Ежи Лец) Здесь примерами могли служить лишь, пожалуй, лучшие образцы элитной американской популярной литературы, прежде всего книги Р. Смальяна. Так что вопрос не в том, где брать образец для подражания, а в том, как его выбирать.

Известно, что религия занимает важное место в системе человеческих взглядов, служа основой морали и мировоззрения. Она дает общую позицию в отношении Человека и Мира, Добра и Зла. Когда религия ослабевает или разрушается, появляются псевдорелигии и тоталитарные секты, пытающиеся решить главнейшие вопросы самыми го научного мировоззрения. Каждое достижение человечества требует жертв. Познавая, мы заодно забываем, уничтожаем старые знания и умения, которые через один этап, возможно, оказались бы вновь весьма ценны. Умножая наше знание, мы в еще б льшей степени умножаем незнао ние. Это — первая и важная причина, по которой не годятся ни традиционный научный стиль, ни другие, перечисленные выше: все они ориентированы на выпячивание успехов и замалчивание трудностей и недостатков16, на декларирование прогресса, а мы хотели бы создать условия для него, а не объявить его декларативно.

Вторая причина уже звучит по-разному для научного и популярных стилей. Большим достоинством научного стиля, особенно до тех пор, пока он не оказался под разлагающим влиянием современной системы грантов, требующей популярного объяснения сложных вещей профалигия прогресса”, менее примитивны и тоталитарны, хотя и носят на себе печать того же первородного греха — самопереоценки человеческих возможностей и недооценки Мирового Порядка.

В частности, религией прогресса называют никогда полностью не формулировавшуюся явно систему взглядов, берущую начало в мировоззрении французского Просвещения XVIII в. и воспринятую естествоиспытателями в XIX в., а математиками, философами, гуманитариями и обыденным сознанием — в XX веке. В этой системе взглядов на роль высочайшего Добра претендует идол Прогресса. Считается, что научное мировоззрение и научные критерии истинности единственно правильны, что наука приносит благо, а выявившиеся отрицательные последствия — результаты ошибок и извращений.

Смотрите, в частности, труды В. И. Вернадского [10], П. Тейяр де Шардена [30], И. Пригожина [25].

Заметим, что религия прогресса не обязательно сопровождается материализмом и атеизмом, хотя весьма часто и хорошо сочетается с ними. В частности, П. Тейяр де Шарден был убежденным католиком, хотя Ватикан и осудил его взгляды как подозрительные с точки зрения ереси.

Заметим здесь скрытое противоречие. Как известно, ориентация на успех любой ценой и на замалчивание поражений ведет вовсе не к прогрессу, а к застою. Так что мировоззрение, декларирующее поклонение прогрессу, на самом деле делает многое для того, чтобы его затормозить. Такие скрытые (концептуальные) противоречия являются непременным элементом любой квазирелигии. Настоящая религия отважно смотрит им в глаза и пытается, в силу человеческих возможностей, преодолеть, а там, где пока что не удается, хотя бы поставить предупредительные флажки. Одним из таких предупредительных флажков является обострение концептуального противоречия и перевод его в то, что на обычном уровне интерпретации становится прямым противоречием. Так, например, поступили христиане, постулировав триединство Бога. Так же должно поступать и любое другое настоящее мировоззрение, в том числе и наука. Пока она так не поступает, все претензии науки на Истину остаются беспочвенными и вредными.

ВВЕДЕНИЕ

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

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

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

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

Поскольку считается, что задача науки — поиск истины, то обучение, как правило, строится так, как будто Истина уже найдена. Не принято, чтобы преподаватель сомневался, а тем более высказывал свои сомнения письменно. Учить, дескать, надо тому, что бесспорно. Но бесспорно только бесполезное. Слишком многие общепризнанные истины напоминают Неуловимого Джо из анекдота18. Как только их кто-то начинает ловить, в них образуется большая дыра. Например, упрямство оказывается признаком слабости характера, а не его силы. Профессиональные военные оказываются более слабыми офицерами в сражениях против партизан, чем вчерашние выпускники лучших вузов, привыкшие сами искать решения в нестандартных ситуациях. Повышение налогов оказывается самым прямым путем к разорению государства ввиду уменьшения поступающих сумм и т. п.

Что даже хуже, чем научные противники.

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

— Кто это?

— Неуловимый Джо.

— А его действительно никто не может поймать?

— Действительно. На коего черта это кому-то нужно?

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

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

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

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

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

В частности, формализмами являются и применяемые логики. Поэтому нужно подбирать лучшую для нашей задачи логику, а не пользоваться без оглядки общепринятой классической системой, либо, еще хуже, Прологом21. За последние десятилетия неклассические логики исслеИ конечно же, результатом больших усилий, направленных на то, чтобы использовать стороны, считающиеся слабостью, как силу.

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

Пролог — язык программирования, рекламируемый как язык логического программирования. На самом деле от логики в нем остались лишь неправильно интерпретиВВЕДЕНИЕ xxii дованы настолько основательно, что по удобству техники и богатству идей уже не уступают классической логике. Поэтому претензии классической логики на практически монопольное положение резко отвергаются. Более того, способ изложения классической логики, избранный в данной книге, можно охарактеризовать как “классическая логика с точки зрения неклассической”. При таком взгляде яснее становятся причины, по которым классическая логика играет и будет играть важнейшую роль в совокупности логик, и основания, необходимые для того, чтобы применять либо, соответственно, не применять классическую логику.

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

Мы не стремимся его ни скрывать, ни навязывать читателю. В частности, то, что обосновывается ссылкой на данное мировоззрение, всегда помечается словами типа ‘по мнению автора’22. Если нам известно какое-то другое обоснованное мнение, являющееся альтернативой нашему, оно приводится тут же.

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

‘реальный мир’, почему и вскрывают самые глубинные свойства этого и других возможных миров. В этом причина непостижимой эффективности математики в приложениях. Но несовершенство человека проявляется в том, что Идеи могут быть реализованы в математике разными способами, противоречащими друг другу, это касается и тех фундаментальнейших Идей, которые лежат в основе логики23.

рованные обрывки внешней формы; позднее мы рассмотрим данный язык подробнее.

Вообще, широко рекламируемое и модное средство, как правило, делает вовсе не то, что обещается, либо далеко не с тем качеством. См., например, о продукции фирмы «Гербалайф».

Если этих слов нет, то, как уже было сказано, не предполагается, что изрекается независимая объективная истина. В частности, все оценочные высказывания по необходимости субъективны и поэтому никогда не помечаются такими словами.

В данном пункте мы резко и принципиально расходимся с т. н. “математическим платонизмом”, предполагающим, что математика вводит нас в сам мир Абсолютных Наиболее часто используемой альтернативной точкой зрения является умеренно оптимистический и умеренно материалистический системный взгляд на мир. Система базируется на фундаментальных структурах и не может существовать без порядка, обеспечиваемого этими структурами. Математика позволяет нам сделать шаг к выявлению фундаментального порядка, на котором базируется Вселенная. Но поскольку человек является несравненно более простой структурой, чем Мир, а никакая система не может познать даже саму себя, не говоря уже о более сложных системах, то человек не может полностью выявить данные структуры и вынужден ограничиваться приближениями. Поэтому математика весьма эффективна, но математические выводы нуждаются в перепроверке. По этой же причине математика не может быть полностью унифицирована, так как для разных целей нужны разные приближения.

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

Узколобые неумеренно оптимистичные либо неумеренно пессимистичные точки зрения нашим уважением не пользуются. Первым критерием здесь является утверждение некоторым “учением” собственной истинности, которое, как выяснила современная логика, является симптомом либо крайней примитивности, либо внутренней противоречивости данной точки зрения. Самый страшный человек — тот, кто уверен, что он познал Истину. На втором месте — циник, считающий, что истины нет вообще.

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

1. Выше всего ценится решение задачи, давно поставленной знаменитым ученым и остававшейся без ответа.

2. Далее, ответ на вопрос, поставленный авторитетом.

Идей, что математические понятия реально существуют в Высшем Мире. Мы считаем данное воззрение профанацией платоновского взгляда и самопереоценкой человека и его научного мышления.

ВВЕДЕНИЕ

xxiv 3. Далее, усиление либо переформулировка результата, доказанного авторитетом, лучше всего — одобренная авторитетами.

4. И на последнем месте — задача, формулировку которой дал сам молодой математик; чаще всего такая работа признается лишь после положительной оценки авторитета).

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

Многие из творцов современной логики кончили трагически. Коекто говорил автору, что не стоит акцентировать внимание на печальных фактах. Здесь стоит посмотреть в лицо явлению, о котором не принято говорить. У братьев Стругацких есть повесть24 «За миллиард лет до конца света». Ее идея состоит в том, что некая почти стихийная страшная сила начинает активно противодействовать ученым, приблизившимся к краю того знания, которое в принципе может изменить (либо, еще более вероятно, разрушить) наш мир. Действительно, приближаясь к Идеям и пытаясь перевести на язык других людей то, что узнал, в некоторый момент начинаешь чувствовать противодействие. Поскольку современная логика затрагивает наиболее фундаментальные вопросы организации Разума и Знания и поскольку ее достижения резко подняли людей над тем уровнем идей, которые считались максимально абстрактными (и максимально глубокими) раньше, ее творцы неизбежно попадали под контрудары. Пожалуй, лишь Гёдель сумел противостоять им, и поэтому закономерно, что работой последних лет его жизни было логическое доказательство существования Бога, и столь же закономерно, что публиковать свое доказательство он не стал.

Автору говорили, что его примечания кое-что напоминают. Да, пожалуй, стоит сослаться на двух классиков русской мысли: великого теоретика Козьму Пруткова и великого прикладника Христофора Бонифатьевича Врунгеля25, некоторым особенностям изречений которых автор по мере сил старался подражать.

Пожалуй, одно из наиболее слабых с литературной точки зрения их произведений:

привыкнув фантазировать, трудно излагать правду...

Прежде всего его «Толковый морской словарь для бестолковых сухопутных читателей».

КАК РАБОТАТЬ С ДАННОЙ КНИГОЙ?

§ 0.3.

Начнем с общих педагогических принципов, на которых основана данная книга.

Задачей преподавания математических дисциплин26 является введение ученика в мир фундаментальных идей данной науки и показ тех Идей, которые лежат за научными формулировками. Логика является той наукой, где путь к Идеям наиболее близок (вспомните вопрос Аверроэса). Поэтому именно в ней данную цель можно ставить наиболее явно. Конечно же, эта цель не отменяет цели овладения навыками и методами, разработанными данной наукой, и суммой наиболее важных сведений, установленных в ней, но в данном контексте это овладение является, прежде всего, средством (правда, нет ничего плохого в том, если оно становится конечным пунктом для большинства учащихся, если они хотя бы увидят на примере других, что есть и более высокие ступени знания и понимания).

Автор уверен, что к Идеям ведет бесконечно много дорог, и высшая задача учителя — помочь ученику выбрать ту из них, которая ему больше всего подходит. Таким образом, сама идея наставления на путь истинный автору чужда. То, что являлось истинным путем для учителя, вполне может заводить в тупик его ученика. То, что хорошо для одних студентов, плохо для других. Но, конечно же, эти дороги содержат много общего. Пройти к вершинам можно, лишь овладевая по дороге техникой подъема, и поэтому необходимо уделять большое внимание отработке технических навыков. Большое количество задач, собранных в данном пособии, дает возможность индивидуализировать техническую тренировку.

Накопление большого количества тренировочных задач позволяет изменить качество курса еще в одном отношении. Каждый научный цикл базируется на некоторой дисциплине, которая, как считается, наиболее ярко высвечивает основные идеи данной науки и позволяет ввести в ее мир. Такой дисциплиной в математическом цикле в большинстве университетов мира и в России является математический анализ. Он действительно вводит в курс математических идей, сформировавшихся к середине XIX века. С тех пор математика принципиально обогатилась и изменила свое мировоззрение. Поэтому ныне анализ является не единДа и других наук высшего уровня.

ВВЕДЕНИЕ

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

Логический анализ естественных языков.

Логическая семантика и формальный синтаксис.

Представление знаний в интеллектуальных системах.

Автоматическое доказательство теорем.

Конструктивные логики и логическое программирование.

Теория возможных миров, контекстов и установок.

Индуктивные выводы, формирование понятий и Неточные, немонотонные, нечеткие выводы.

Теория взаимодействующих процессов.

Теория рефлексивных рассуждений.

Теория неформализуемых понятий.

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

Стоит сказать об отношении к ошибкам. Человеку свойственно ошибаться. Не ошибается он, лишь пока ничего не делает. В современной теории творческого мышления обосновано, что в процессе решения трудных творческих задач неизбежен проход через ошибки. Поэтому одна из самых вредных особенностей традиционного подхода к обучению — рассмотрение ошибки как криминала27. На занятиях первое, к чему приходится приучать первокурсников, — не стесняться ошибок. Более того, отличить глубокое понимание от формального запоминания гораздо легче, когда имеешь дело с ошибками: качество ошибок просто несравнимо. Поэтому многие упражнения ориентированы на выработку навыков исправления неточностей в доказательствах и формулировках без полного отвержения частично неправильных построений.

С этим же связано то, что мы не любим ставить задачи в форме «Доказать, что... » Готовая истина не способствует развитию творческого мышления. Далее, при таких формулировках возникает громадный соблазн действовать по принципу: «Вы скажите нам, что нужно доказать, а мы уж докажем»28. Тем не менее порою приходится формулировать и задачи на доказательство.

ПРЕДУПРЕЖДЕНИЕ

Для борьбы с указанной выше болезнью несколько задач на доказательство являются задачами-ловушками. Это необходимо для приучения учащихся к дисциплине ума: проверяй доказываемое! Не все части данного пособия одинаково фундаментальны. В частности, могут быть опущены некоторые параграфы из первой части (ее последней главы). Глава, посвященная нестандартному анализу, полностью независима от последующего материала и также может быть опущена. Возможны и многие другие варианты компоновки курса в зависимости от вкусов и уровня подготовки преподавателя30. Скажем, хотя глава о семантических таблицах является центральной во второй части, в ней можно опустить последний параграф, посвященный устранению сечений. Минимальный вариант изучения второй части — главы, Впрочем, если мы стремимся наставлять на Единственно Истинный Путь, ничего другого не остается.

Формулировка данного принципа принадлежит студентам Высшего Юридического колледжа УдГУ.

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

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

ВВЕДЕНИЕ

xxviii посвященные синтаксису и семантическим таблицам. К ним могут независимо добавляться главы, посвященные естественному выводу, теории определений, теореме Гёделя, нестандартному анализу. Что брать из третьей части — дело вкуса и конкретных потребностей преподавателя и учебного плана.

Если преподаватель имеет возможность провести хотя бы несколько занятий в дисплейном классе Macintosh либо IBM PC и обучающие программы высокого уровня Tarski’s World, Hyperproof, Deductio или Semtab, то это стоит сделать. Кое-где в тексте есть прямые указания на то, как можно воспользоваться данными программами для практических занятий.

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

Три вида кавычек “ ”, ‘ ’, « » употребляются как модальности. Первый из них (общеупотребительный в англоязычной литературе) означает, что слова употреблены в переносном смысле, а если они окружают слова, идея которых приписана другим, то формулировка (дабы подчеркнуть смысл) преобразована автором. Второй — что данное слово, например, ‘кавычки’, в данном контексте используется как имя понятия, а не как понятие, обозначаемое данным именем. Третий вид — цитата либо слова, взятые автором из фольклора и не преобразовывавшиеся.

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

Выделение рубленым шрифтом означает чисто формальное имя, встретившееся в нашем тексте. Например, так мы обозначаем идентификатор из программы, о котором говорится вне текста данной программы. Математические символы, написанные прозрачным шрифтом, скажем, Z, означают фиксированные математические понятия, чаще всего — общеупотребительные множества. Остальные типы выделений используются прежде всего для привлечения внимания и фиксированного смысла не имеют.

И в заключение автор должен поблагодарить свою жену Людмилу, неоднократно читавшую рукопись в процессе создания и немало способствовавшую улучшению изложения; дочь Тоню и В. В. Пупышева, выловивших кучу опечаток; рецензентов и профессора А. П. Бельтюкова, сделавших ряд ценных замечаний. Некоторые примечания А. П. Бельтюкова вошли в текст книги, они помечены буквами (АПБ).

ВВЕДЕНИЕ КО ВТОРОМУ ИЗДАНИЮ

§ 0.4.

Неклассические логики получили большие и важные применения в последние десятилетия. Это связано с несколькими принципиальными моментами.

Классическая логика является весьма мощным средством описания и дедукции. Но она, конечно же, имеет ограничения, явные и неявные предположения, заложенные в ее основу. Явные предположения (типа того, что логическими значениями являются лишь 0 и 1) легко нарушаются столь же явно. Неявные же (самое важное из них то, что логика описывает состояние вполне определенной совокупности понятий в некоторый момент и для достижения фиксированной цели), как всегда, гораздо важнее и гораздо труднее преодолеваются.

В неклассических логиках особенно четко прослеживается беда современной прикладной науки, основанной в большинстве случаев на плоском одноуровневом мышлении: соблазн воспользоваться “царскими путями”31 : соблазнительным возможностями прямого приложения мощных теоретических результатов, изредка открывающимися в ходе развития науки.

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

У Цзы заметил [18, гл. 1, ч. 3]:

Мало таких, кто овладел Поднебесной частыми победами, но много таких, кто от таких побед погибал.

Мы основываемся на точке зрения, что наш Мир имеет единую Мировую Идею, заложенную в его начале32.

По легенде, Евклид ответил на вопрос одного из Птолемеев: «Нельзя ли полегче научиться геометрии?» — словами: «В геометрии нет царских путей!»

Во избежание недоразумений заметим следующее.

1. Понятие Мировой Идеи не зависит от понятия Бога. Она следует из системности наблюдаемого строения Вселенной и логичности происходящего в ней. Так что в данном случае мы не опираемся на гипотезу, что Мир сотворен.

2. (Для креационистов и деистов) Отождествление Мировой Идеи с Богом — недопустимое упрощение. Это — Слово, которым Бог сотворил Мир. Оно, конечно, уже не является Высшей Сущностью, но оно неизмеримо выше по природе своей всех других сущностей тварного мира.

ВВЕДЕНИЕ

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

Далее, избежать лобового столкновения можно несколькими путями. Во-первых, можно перепрыгнуть через трудности, воспользовавшись идеальными понятиями высокого уровня и затем конкретизировав их в новой обстановке. Во-вторых, можно обойти заминированные места, рассмотрев другие аспекты проблемы и уже от них вернувшись к нашей непосредственной цели. И то, и другое решение требует владения двумя умениями: многоуровневым подходом к выбору средств и к оценке результатов; искусством перевода как между различными формализмами, так и между формализмами и естественным языком.

Введение в такое использование современных логических средств — цель данного пособия.

3. (Для агностиков и умеренных атеистов) Отождествление Мировой Идеи и Мира — также недопустимое упрощение. Мир — постепенно развившаяся реализация данной Идеи. А, как правило, реализация беднее исходной спецификации и уж во всяком случае искажает ее.

Язык математики Глава 1. Необходимость точного языка в математике

КАК И ПОЧЕМУ ПОЯВИЛСЯ ЯЗЫК

МАТЕМАТИЧЕСКОЙ ЛОГИКИ?

§ 1.1.

Математика изучает объекты, свойства которых точно сформулированы.

Это описание поля деятельности современной математики не претендует на полноту. Оно, скорее, достаточно широко и отбрасывает лишь те случаи, когда говорить о применении математики еще рано1. В частности, оно включает и традиционные разделы, такие как геометрия и алгебра, и новые, такие как математическая лингвистика либо теория генетического кода.

Хотя само описание говорит о точных формулировках, в нем требуют разъяснения в первую очередь последние слова: «точно сформулированы». Очевидно, что их уточнение влечет за собой уточнение и других понятий, в частности ‘объекта’ и ‘свойства’. Какие формулировки можно считать точными, мы будем стремиться разобраться дальше.

Очевидно, что не все то, что сказано на естественном языке, точно.

Иногда эта неточность лежит на поверхности, как, например, в фразах:

«Хочется чего-то, а чего — неясно» или «Оно, конечно, ежели что как...

Тем не менее и там вовсю пытаются применять математическую символику, используя, как остроумно выразился Леви-Стросс, «формулы как узор, украшающий текст».

В частности, таковы многие современные работы по культурологии, философии и т. п.

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

ГЛАВА 1. НЕОБХОДИМОСТЬ ТОЧНОГО ЯЗЫКА

А ежели что не так?» Иногда смысл фразы явно зависит от контекста, например: «Сейчас я намылю ему шею». Богатство любого естественного языка неразрывно связано с его многозначностью. Зависимость от контекста не всегда отрицательный фактор, лишь бы в любой данной ситуации предложение уточнялось однозначно.

Но, например, полное и достаточно безобидное на вид предложение имеет три различных истолкования. Вот от такой неоднозначности хотелось бы раз и навсегда застраховаться в математике. Поэтому математики с самого начала стремились формулировать доказательства и теоремы на как можно более четком, хотя и бедном, диалекте естественного языка. Хотя словарный запас этого диалекта постоянно расширяется, основные формы предложений, связки, союзы остаются практически теми же, что были выработаны еще в античные времена. Следует заметить, что способы выражения, допустимые в математике, нигде не описывались явно, ими овладевали на примерах, в процессе обучения и чтения классических трудов, в первую очередь «Элементов» Евклида.

Долгое время считалось, что ‘математический диалект’ состоит из строго сформулированных предложений, да и сейчас он верно служит математикам, почти никогда их не подводя. В геометрии и до сих пор его достаточно. Но уже в средние века развитие алгебры привело к тому, что формулировки теорем зачастую становились все длиннее, необозримее и неудобнее. Соответственно, выкладки становились все более и более трудными. В самом деле, даже для того чтобы просто понять фразу «Квадрат первого, сложенный с квадратом второго и с удвоенным произведением первого на второе, есть квадрат первого, сложенного со вторым», требуется значительное усилие. Таким образом, математическая строгость и удобство начали противоречить друг другу.

Выход был найден, когда заметили, что использованная в (1.2) часть математического языка может быть сведена к нескольким условным знакам, и сейчас (1.2) записывается кратко и ясно:

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

К XVIII в. математические формулы записывались почти в том же виде, что и сейчас.

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

Рассмотрим один из самых ярких и элементарных примеров.

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

«Наименьшее простое число, большее миллиона».

В русском языке 33 буквы, и предложений, состоящих не более чем из ста букв, конечное число (грубо говоря, не более 33101 ). Натуральных чисел же бесконечно много. Значит, среди них должны быть такие, которые нельзя назвать фразой, состоящей менее чем из ста букв. Но тогда есть и наименьшее такое число. Его можно определить как ‘Наименьшее натуральное число, которое нельзя определить предложением русского языка, содержащим менее ста букв’.

Это предложение содержит 96 букв. Следовательно, определение (1.6) противоречит самому себе. (Парадокс Берри. 1906 г.) Казалось бы, рассуждение из парадокса Берри явно нематематическое. Однако уже в те времена подобные конструкции встречались в теории множеств, а сейчас рассуждения такого рода обычны в разделах математической логики и теории алгоритмов, исследующих сложность описания математических объектов. В частности, подобная идея лежит в основе знаменитой теоремы Гёделя2 о неполноте любой достаточно сильной формальной теории.

Эта теорема является одной из целей нашего курса

ГЛАВА 1. НЕОБХОДИМОСТЬ ТОЧНОГО ЯЗЫКА

Если парадокс Берри возник на границе между математикой и естественным языком, то парадокс Рассела возник внутри самой математики — в теории множеств.

Пусть z — множество тех множеств, которые не являются собственными элементами. То есть x z тогда и только тогда, когда неверно, что x x.

Подставляя z вместо x в определение z, получаем, Появление первых парадоксов ошеломило математический мир и послужило поводом, чтобы предпринять систематическое построение современной логики. А причиной ее появления было то, что математический диалект естественного языка опять-таки, как и в средние века, перестал удовлетворять требованиям компактности и удобства при записи формулировок теорем, и в особенности при манипуляциях с этими формулировками. Например, вот одно из элементарных определений математического анализа:

Функция f, определенная на множестве M, непрерывна на M, если для каждого x из M и для любого сколь угодно малого положительного найдется такое положительное, зависящее от, что, когда x1 лежит в M и отличается от x меньше, чем на, f (x1 ) отличается от f (x) меньше, чем на Построить, скажем, отрицание понятия непрерывности, содержательно вдаваясь в смысл фразы (1.8), не менее трудно, чем преобразовывать алгебраические тождества, записанные в виде (1.2). А на современном символизме «f непрерывна на M » записывается компактно и изящно:

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

Вместе с тем впервые появилась возможность строго ответить на вопрос: а что значит ‘точно сформулированное высказывание’? Это высказывание, которое может быть однозначно переведено на символический язык математики.

Формализация математики привела к более ясному осознанию природы самой математики, к триумфальному применению ее к нечисловым и непространственным объектам, таким как, например, гены, естественные и искусственные языки, программы для ЭВМ и т. д. Вместе с тем стало ясно и то, когда мы не должны применять математику. До тех пор, пока наши знания о некоторой конкретной области не могут быть переведены на формальный математический язык единообразным методом, мы еще не осознали исходные понятия и их свойства настолько, чтобы применять математические методы, и “математизация” превращается в род шаманства, призванного придать наукообразие тексту. А как только мы сможем точно сформулировать свойства ясно выделенных нами исходных понятий, мы сможем и применять математику для извлечения следствий из этих свойств.

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

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

1. на него возможно перевести математические 2. он допускал бы сравнительно легкий перевод 3. записи на нем были бы компактны и удобны в Первая часть нашего пособия посвящена показу используемого в современной математике решения этой проблемы. Мы стремимся осветить с

ГЛАВА 1. НЕОБХОДИМОСТЬ ТОЧНОГО ЯЗЫКА

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

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

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

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

Труднее всего поддается уточнению само понятие точности.

Математическая логика — наука, изучающая саму математику математическими средствами.

Математическая логика изучает формальную структуру рассуждений математическими средствами.

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

Формальный язык позволяет значительно эффективнее преобразовывать выражения, чем содержательный.

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

Формальный язык должен полностью исключать неоднозначности.

Смысл предложений формального языка должен быть строго и до конца определен.

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

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

Упражнения к § 1. 1.1.1. (Л. С. Выготский) Сколько различных смыслов имеет предложение Предложение рабочих бригад вызвало осуждение 1.1.2. (Х. Б. Карри) Докажите, что из существования множества всех таких множеств x, что если x является своим элементом, то выполнено A, следует, что A истинно.

1.1.3. Какое из предложений (1.4), (1.5) неоднозначно? Как его переформулировать, чтобы оно стало однозначным?

ЗАЧЕМ ИЗУЧАТЬ ФОРМАЛЬНЫЙ ЯЗЫК МАТЕМАТИКИ?

§ 1.2.

Ну допустим, мне удалось убедить Вас, что для математики необходимо создавать точный формальный язык. Но остается второй вопрос: а так ли необходимо его изучать, если Вы не собираетесь быть специалистом именно в области математической логики. Ведь столько лет без него обходились, почему бы не обойтись и Вам?

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

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

В нынешние времена люди все равно вынуждены изучать искусственные, формальные языки. В частности, имея дело с вычислительной машиной, Вы не обойдетесь без знакомства (хотя бы шапочного) по крайней мере с 2–3 искусственными языками. А уж если Вы собираетесь быть математиком-прикладником, для которых в первую очередь Артамонов — мастер-самоучка, в царствование Николая I приехавший с Урала в Питер на самодельном велосипеде.

ГЛАВА 1. НЕОБХОДИМОСТЬ ТОЧНОГО ЯЗЫКА

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

Язык математической логики — исторически первый точно определенный формальный язык. Он появился в конце XIX века в трудах итальянского математика Пеано и его учеников, современная форма придана ему Расселом и Гильбертом в начале XX века, и этот язык доказал на практике свою жизнеспособность и устойчивость. Во множестве формальных языков программирования, математической лингвистики и искусственного интеллекта, сменяющихся каждые десять лет, он является своего рода скалой среди айсбергов. В нем в гораздо более последовательной и красивой форме проведены многие концепции, а позднее перенятые в языках программирования и искусственного интеллекта. Так что знать его целесообразно хотя бы для того, чтобы видеть, что к чему в этом бурлящем море неустойчивых частных формальных языков.

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

В прикладной математике исследователь должен все время заниматься переводами с содержательного языка на математический, с математического языка на язык численных методов и алгоритмов, с языка алгоритмов на конкретный язык программирования и обратно. Такая многоязыковость неизбежна: она вызвана необходимостью находить точные и реализуемые решения задач, возникающих на практике. Например, услышав о проблеме, связанной с тем, что нагрев сырья в печи недостаточно равномерен, исследователь должен сообразить, что передача тепла описывается параболическими дифференциальными уравнениями в частных производных5, что в данном случае граничные условия имеют такой-то вид, а тогда задача нахождения решений этих уравнений некорректна*, что для устранения некорректности можно воспользоваться такими-то моделями и численными методами, что для того чтоЕсли уважаемый читатель не знает, что это такое, пусть не расстраивается: это должен знать специалист, и даже многие известные автору блестящие математики-прикладники этого не знают. Другое дело, что нужно развивать свою внутреннюю “базу знаний” и включать в нее и то, что сам не знаешь как следует. Тут нужно лишь понимать, к какой области это относится, к какому специалисту нужно обратиться, если Вы столкнетесь с данным понятием, и как, хотя бы самым грубым образом, перепроверить предложенное специалистом решение. Ведь никто не может знать всего, а нынче никто не может знать всего даже в одной отдельно взятой отрасли.

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

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

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

Об истории возникновения логического языка В середине XIX века в математике самым передовым и бурно развивающимся разделом была абстрактная алгебра. Впервые математики стали изучать не те структуры, которые, как казалось, были даны свыше:

числа и геометрические фигуры, а любые структуры, в которых можно найти порядок и меру6. Были созданы новые числовые системы, новые геометрии, и возникло большое желание перенести алгебраические методы на другие области. Это с успехом проделала английская школа, родоначальником которой можно считать де Моргана, а наибольшую Еще в XVII веке выдающийся французский мыслитель Рене Декарт, хорошо знавший и математику (хотя основным своим делом он считал философию и богословие; в частности, ему в значительной степени западный мир обязан обузданием ордена иезуитов и дискредитацией гибельного для любой страны и любой системы принципа: цель оправдывает средства), дал определение математики как «Наука о порядке и мере».

Как говорится, здесь ни прибавить, ни убавить...

ГЛАВА 1. НЕОБХОДИМОСТЬ ТОЧНОГО ЯЗЫКА

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

Естественно, они провели аналогию между объединением и сложением, пересечением и умножением, пустым классом и нулем, самым большим классом (универсом) и единицей... Нашлась и операция, очень похожая на вычитание, а вот аналогию делению никак не удавалось подобрать, и из-за этого английские алгебраисты-логики чувствовали себя несколько ущербно: что же за алгебра без деления! Весь остаток XIX века все квалифицированные математики, занимавшиеся алгеброй классов, пытались изобрести для них деление, но так ничего путного и не придумали. Зато появилась алгебра булевских значений 0 и 1, которую сам Буль рассматривал как какую-то патологию, хотя и приводил в качестве примера.

К концу XIX века сразу несколько выдающихся математиков занялись теорией многоместных отношений, и эта теория естественно превратилась в математический язык логики предикатов, который у нас рассматривается. Одни из них, пожалуй, самые образованные и глубокие, записывали все как алгебру отношений и упустили случай перевода на новый язык других математических понятий. Впрочем, сами они на первый план выносили в значительной степени ту же псевдопроблему, связанную с удобными на первых порах, но в дальнейшем все больше и больше приводившими к путанице, обозначениями логических операций как сложения и умножения: определить деление. Другие, одновременно в Германии (Г. Фреге) и Италии (Пеано с учениками), попытались записывать именно математические высказывания.

Фреге подошел к созданию нового языка как ученый, и причем основательный ученый немецкого стиля времен его расцвета. Он построил теорию, впервые в математике формализовывавшую незадолго до этого введенное в математический обиход понятие бесконечного множества и всю систему теории множеств. Оказалось, что все известные математические понятия выражаются через понятие множества и отношение принадлежности «x является элементом множества X». Это был первый случай, когда всю математику свели к одному исходному понятию дающих данным свойством.

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

• Понятие функции вместе с операциями:

1. определения по выражению t(x) функции x. t(x), вычисляющей его значения;

2. применения функции к аргументу7 f (x).

• Понятие имени вместе с операцией именования понятия и отношением ‘имя N именует объект x’.

• Понятие системы, которое делает осмысленным, в частности, отношение ‘часть — целое’. Фундаментальное отношение здесь — отношение связи.

Второе из представлений используется в -исчислении, оно стало одним из главных инструментов, в частности, в современной математической теории программирования, последним из них пока что повезло меньше: логики знают о них, но толком еще использовать не смогли8.

Перед Пеано и его учениками стояла другая задача. В то время Италия быстро развивалась и требовались новые учебники для вузов. Традиция практически не давила, поскольку итальянских учебников хорошего уровня в области математики долго (после XVII века) просто не было, образованные люди пользовались французскими и немецкими.

Чтобы подчеркнуть двойственность функции и аргумента в данном выражении, сейчас в логике часто пишут просто (f x). Такое представление функции с аргументами как единого списка стало одной из основ широко применяемого для моделирования систем со сложной логикой языка ЛИСП.

Интересно, что судьба первооткрывателей трех исходных понятий была трагична.

Фреге получил умственное расстройство (после периода признания и успеха), когда выяснилось, что созданная им теория содержит противоречия (когда появился парадокс Рассела). Шейнфинкеля (российского математика, создавшего -исчисление), наоборот, не признали на Родине и не выпустили за рубеж, где его сравнительно быстро признали. А у нас его заморили голодом в сумасшедшем доме... (Документов, подтверждающих такой конец Шейнфинкеля, найти не удалось. Если они и были, то сгинули во время блокады Ленинграда. Но петербургские логики единогласно говорят, что дело было именно так.) Поляки Хвистек и Лесьневский, создатели теории именования, погибли во время второй мировой войны.

ГЛАВА 1. НЕОБХОДИМОСТЬ ТОЧНОГО ЯЗЫКА

Именно как педагог и подошел Пеано9 к созданию символического языка, и неудивительно, что его система обозначений оказалась самой удачной. Впоследствии ее лишь подправляли.

В частности, в те времена математики очень не любили нагромождений скобок (сейчас вычислительные машины к этому уже приучили). Старшее поколение еще помнит, как внимательно следили учителя, чтобы скобки первого уровня были круглыми, второго — квадратными, а третьего — фигурными. Пеано избежал психологической опасности, заменяя скобки точками у логических связок: чем сильнее связывает связка, тем меньше у нее точек, и, соответственно, чем она главнее, тем их больше. Он решительно отказался от обозначений операций ‘и’ и ‘или’ как умножения и сложения: раз это — другие операции, то и значки для них должны быть другими; нечего путать числа и высказывания!

И после этого проблема ввести деление логических значений как-то сама собой отпала.

Пеано ввел кванторы всеобщности x и существования x10, да и само слово ‘квантор’. Впрочем, кванторы вводил и Г. Фреге, но его обозначения для кванторов были крайне неудобны, так же как и его обозначения для логических формул: он их рисовал в виде двумерного дерева.

Дж. Уайтхед и его ученик Б. Рассел в Англии повторили и углубили труд Фреге на новом уровне. Они педантично проследили, чтобы все известные источники противоречий были изгнаны. При этом они воспользовались языком, изобретенным Пеано, и тем самым ввели данный язык в употребление во всем мире.

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

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

Глава 2. ПРОСТЕЙШИЕ

ВЫСКАЗЫВАНИЯ

ЧТО ТАКОЕ ВЫСКАЗЫВАНИЕ?

§ 2.1.

Высказывание — утверждение об объектах, имеющее однозначный, точно определенный смысл.

Это определение, конечно же, не математическое. С чисто математической точки зрения понятия высказывания и объекта являются исходными, но содержательно мы все равно должны описать, что же такое высказывание. Ведь и исходные понятия мы должны понимать.

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

Кама впадает в Каспийское море.

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

13 января 1995 г. в 11.35 на перекрестке улиц Пушкинской и Советской автомобилем № CUR2171RUS был сбит гр. Иванов Иван

ГЛАВА 2. ПРОСТЕЙШИЕ ВЫСКАЗЫВАНИЯ

13 января 1995 г. в 11.35 на перекрестке улиц Пушкинской и Советской автомобилем “Тойота”, принадлежащим гр. Хасбулатову, находившемуся в состоянии опьянения средней степени, был сбит гр. Иванов Иван Иванович, который получил тяжкие телесные повреждения.

Не только Иванов, но и Петров прогулял сегодняшнюю лекцию.

По словам Сталина, Троцкий был врагом СССР.

Большинство членов собрания проголосовало за первый вариант решения.

У русалок зеленые волосы.

У нынешнего российского императора красный Рим расположен на реке Тибр, основан, согласно Титу Ливию, Ромулом и находится под особым покровительством Юпитера.

Некоторые высказывания являются истинными, некоторые — ложными. Например, (2.1), (2.3), (2.7) — безусловно истинные высказывания, (2.2), (2.5) — безусловно ложные.

Истинность либо ложность высказывания не всегда легко установить. Например, высказывание (2.7) требует доказательства и называется теоремой Евклида. Как ни странно, могут возникнуть сомнения даже по поводу высказывания (2.4), которое традиционно относится к числу трюизмов, общеизвестных истин. В самом деле, по принятому в географии определению при слиянии двух рек притоком считается та, которая несет меньше воды, а годовой сток Волги при слиянии с Камой почти в два раза меньше. Так что, возможно, правильней было бы считать истинным высказывание (2.6). Нигде так долго, прочно и безнаказанно не могут существовать ошибки, как среди трюизмов. Порой даже кажется, что общепринятая истина всегда ошибочна.

Зачастую высказывания говорят не о единичном факте, а о целом множестве утверждений, например, (2.12), (2.13), (2.14). Такие высказывания часто называют общими.

Далее, порою вопрос об истинности или ложности высказываний переносится из нашего мира в какой-то другой, т. н. ‘возможный’ мир1.

Например, все признают истинным утверждение о Геракле, но ведь на самом деле неизвестно, был ли он и что делал... Просто для нас некоторые возможные миры, например, Библии, сказок, греческих мифов, имеют почти такую же реальность, как и настоящий2 3.

Иногда высказывание относитcя не столько к сообщаемому акту, сколько к его оценке. Например, утверждение (2.11) не зависит от “реальной” истинности данного факта, но может быть строго доказано либо опровергнуто анализом исторических документов, касающихся того, что говорил и делал Сталин.

А в сложном высказывании могут быть перемешаны и реальность, и возможные миры, и оценки; см., например, (2.18).

В естественном языке можно сделать следующие замечания о высказываниях.

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

• Логические связки применяются к высказываниям и в результате дают новое высказывание. Например, это “не только..., но и... ”, или просто конструкция сложносочиненного предложения, как в Даже саму математику можно рассматривать как возможный мир, поскольку ее понятия имеют к “действительности” весьма косвенное отношение. А уж физика вообще занимается невозможными явлениями, поскольку, в частности, ни одной инерциальной системы координат, в которой выполнены три закона Ньютона, в природе нет и быть не может.

А вообще, что такое “настоящий” мир? Реален ли он? Если глубоко разобраться, то ответы могут быть самыми различными. В частности, Платон и буддисты уверены, что этот мир нереален, а реален некий “идеальный” мир, бледным слепком с которого является наш. Те, кто испытывал состояние творческого озарения, зачастую склонны согласиться с ними.

(АПБ) Традиционно настоящий мир считается реальным по определению. На мой взгляд, стоит отличать истинный мир от реального (и оба их отличать от миров наваждений).

ГЛАВА 2. ПРОСТЕЙШИЕ ВЫСКАЗЫВАНИЯ

• Модальности применяются к высказываниям и изменяют наше отношение к ним. Например, модальностью является “По словам • Кванторные конструкции применяются к совокупности однородных (отличающихся лишь значениями некоторых параметров) высказываний либо выражений и дают единое высказывание либо выражение, не зависящие от упомянутых выше параметров. Например, таковы “Большинство... ”, “Все... ” Порою кванторные конструкции подразумеваются, как, например, в (2.16).

К несчастью, во многих естественных языках (особенно в русском) модальности, оценки связаны почти с каждым словом. Например, говоря: “и A, и B”, мы подчеркиваем равноправие двух утверждений, а “не только A, но и B” — наоборот, предпочтительность одного из них.

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

Например, квазивысказываниями являются утверждения о субъективных чувствах, скажем, “Саша любит Машу”. Беда даже не в том, что понятие любви неточно. Оно, прежде всего, неформализуемо, то есть каждая его формализация немедленно вызывает к жизни контрпримеры4. Далее, оно принципиально непроверяемо, поскольку относится к внутреннему миру человека и понимается разными людьми совершенно неодинаково.

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

Это чисто американское вульгарно-рекламное название стало практически термином для обозначения целой отрасли в современной информатике. В дальнейшем мы часто будем пользоваться принятым для него сокращением ИИ.

ниями в наших примерах и упражнениях6. Возникает вопрос: почему же мы, прекрасно осознавая неприменимость, вообще говоря, традиционной математической логики к этому классу предложений, применяем ее? На это есть две причины.

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

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

Во-вторых, квазивысказывания через посредство модальностей завязаны в неразрывный узел с высказываниями. Например, ‘Саша заявил, что он любит Машу’ — уже высказывание, а ‘Мне кажется, что Волга впадает в Каспийское море’ — квазивысказывание.

Упражнения к § 2. Выделите высказывания и квазивысказывания.

2.1.1. У меня одна рука.

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

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

ГЛАВА 2. ПРОСТЕЙШИЕ ВЫСКАЗЫВАНИЯ

2.1.2. У меня расстройство желудка.

2.1.3. У меня повышенное давление.

2.1.4. У меня болит спина.

2.1.5. У меня нет денег.

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

2.1.6. (ШБ1) Каждая программа содержит ошибку.

2.1.7. (ШБ2) Если программа не содержит ошибок, то неверен примененный метод7 8.

2.1.8. По словам преподавателя, у студента Канторовича в каждой программе не менее десяти ошибок.

2.1.9. Завтра взойдет Солнце, если только не будет светопреставления.

2.1.10. Как мне сообщила Маша, наш профессор собирается завалить на экзамене не менее половины группы.

2.1.11. Большинство избирателей проголосовало за Уткина.

2.1.12. Мне кажется, что Иванов думает, что я намерен подложить ему 2.1.13. Мне передали, что Иванов думает, что я намерен подложить ему 2.1.14. Почему высказывание (2.9) уже сложное, в отличие от (2.8)?

Эти два утверждения известны в русском программистском фольклоре как 1-я и 2-я аксиомы Шуры-Буры (М. Р. Шура-Бура — профессор МГУ и один из основоположников русской программистской культуры). Третья аксиома звучит следующим образом:

(ШБ3) Если программа на самом деле полностью и абсолютно правильна, она никому не нужна.

(АПБ) М. Р. Шура-Бура, как он сам подтвердил, никогда не употреблял эти три высказывания вместе, пока не услышал их от автора настоящей книги. Более того, он заявил, что третье высказывание на самом деле — принадлежащее автору следствие из первых двух его утверждений.

МАТЕМАТИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ

ВЫСКАЗЫВАНИЙ

§ 2.2.

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

Истинностными (или логическими) значениями называются такие математические объекты, которые могут быть значениями высказываний.

Истину будем обозначать, ложь —.

Истина и ложь являются единственными общепризнанными истинностными значениями. Как только пытаются предложить другие значения, как, например, “неизвестность”, так сразу натыкаются на возражения типа: степеней неизвестности много и, значит, она сама по себе не является логическим значением9.