книги / Математическая логика и теория алгоритмов. Логика предикатов

ОГЛАВЛЕНИЕ

Введение

Математики — как французы: всё, что вы им го­ ворите, они переводят на свой язык, и это тот­ час же становится чем-то совершенно иным.

И. В.ГЕТЕ

Одна из основных черт, характеризующих развитие математики, — совершенствование системы обозначений. До введения знаков арифмети­ ческих операций приходилось описывать все арифметические выкладки словами: например, когда-то вместо х2 —2х + 1 = 0 писали нечто вро­ де «неизвестная величина, взятая в квадрате, будучи уменьшенной на ту же самую неизвестную величину, взятую дважды, и увеличенной на единицу, даёт в результате нулевую величину». Современному человеку такая громоздкость формулировок представляется не только смешной, но и крайне неразумной, но не стоит забывать, что плодотворность но­ вой идеи становится очевидной лишь после того, как она уже получает свое воплощение. Все гениальное просто. Иногда появление нового обо­ значения оказывалось столь удачным, что определяло рождение нового раздела науки. Так, введение Ф. Виетом (XVI век) буквенных обозначе­ ний не только для неизвестных величин, но и для данных, обусловило появление классической алгебры.

Аналогичное событие произошло во второй половине XIX века. К то­ му историческому моменту математики ощутили необходимость обра­ титься к изучению используемых в профессиональной деятельности спо­ собов рассуждения. Это означало исследование математическими мето­ дами принципов и законов мышления. А когда математики берутся изу­ чать что-либо своими методами, они в первую очередь стремятся создать адекватное средство описания объекта изучения — специальный язык. Естественный язык — русский или какой-либо другой — для этой цели подходит лишь отчасти: такие языки выполняют широкий спектр функ­ ций, что затрудняет описание математических объектов, для которого из всего богатства языковых средств требуется лишь одно — предель­ но возможная точность. С другой стороны, если, представляя результа­ ты математических исследований, ограничиться специальными обозна­ чениями и совсем отказаться от «обычных» слов, вряд ли это хорошо

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

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

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

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

*В случае «казнить нельзя помиловать» помогает запятая, но не всякая языковая

проблема так просто разрешима.

2Типичные представители класса формальных языков — современные языки про­ граммирования.

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

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

В процессе изложения рассматривается большое количество приме­ ров конкретных логико-математических рассуждений. Каждая глава со­ провождается набором задач, которые для хорошего овладения теорети­ ческим материалом рекомендуется решить самостоятельно. Ответы ко всем задачам, а также решения или указания к решениям приводятся в конце книги. Для приобретения хороших практических умений и на­ выков необходим специальный задачник (например, [4]).

В сносках приводятся сведения, имеющие к основному тексту прямое отношение, но для его понимания не требующиеся.

Для обозначения некоторых стандартных словесных оборотов ис­ пользуются специальные символы:

=*►— «влечёт»,

— «тогда и только тогда, когда»,

^— «есть по определению».

Глава I. Множества и предикаты

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

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

Предметы, составляющие данное множество, называются его элементами. Мы будем обозначать множества заглавными латинскими бук­ вами: А, В, С, ... ; элементы множеств — строчными: Û, Ь, с , ... Тот факт, что предмет а является элементом множества Д будем передавать сло­ вами «а принадлежит множеству Аь и записью а 6 Д если объект b не является элементом множества 5 , то будем говорить «Ь не принадле­ жит множеству Б» и писать b £ В.

Если существует натуральное число, являющееся числом элементов данного множества (даже если неизвестен способ, как это число устано­ вить), то множество называется конечным. В противном случае сколько бы элементов множества ни было взято, оно содержит и другие элемен­ ты — и тогда оно называется бесконечным. Например, множество рыб, живущих в данный момент в Мировом океане, есть конечное множество (хотя точное количество его элементов неизвестно), а множество нату­ ральных чисел — бесконечное. Элементов данного множества не обяза­ тельно должно быть «много»: в частности, оно может содержать только один элемент или даже не содержать ни одного. Роль множества, не со­ держащего элементов, в алгебре множеств столь же важна, как роль

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

Рассмотрим два произвольных утверждения, которые мы обозначим символами Р и Q. Сложное утверждение «Для того чтобы Р, необходи­ мо, чтобы Q» означает, что Р может оказаться верным только в том случае, когда верно Q. Иными словами, если верно Р, то верно и Q. Утверждение «Для того чтобы Р, достаточно, чтобы Q» имеет обрат­ ный смысл: если верно Ç, то верно и Р. Таким образом, утверждение «Для того чтобы Р, необходимо и достаточно, чтобы Q» означает, что верны два взаимно обратных утверждения: «Если Р, то Q» и «Если Q, то Р». Смысл перечисленных утверждений, содержащих слова «необхо­ димо» и «достаточно», передаётся также с помощью других штампов ма­ тематического языка, например: «Р влечёт Q», «из Р следует Q», «Р то­ гда и только тогда, когда <2», «Р если и только если Q». Часто исполь­ зуются сокращения этих штампов специальными символами: Р =Ф- Q, P <= Ç, Р Q.

Приведённое выше рассуждение начиналось словами: «Рассмотрим два произвольных утверждения... » Использование произвольных объ­ ектов, удовлетворяющим некоторым условиям, — стандартный ход при выполнении логических рассуждений.

Пример 1.2. Докажем, что если A С В и В Ç С, то А С С. Для этого рассмотрим произвольный элемент х множества А. По определе­ нию 1.2 из х G А и A Ç В следует, что х е В. Аналогично, из х е В и B Q C следует, что х е С, Таким образом, если х € А, то х € С. Этот факт верен для любого х 6 Л, следовательно, также по определению 1.2,

АС С.

Упражнение 1.1. Сформулируйте разобранное выше условие ра­ венства двух множеств, используя символы = и С и начиная словами: «Для любых множеств Л и В . , . » ,

1.1. Определение множества

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

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

определить (или задать).

Самый простой способ определить множество — перечислить все со­ ставляющие его предметы, то есть представить полный список всех его элементов. Например, множество, которое составляют студенты данной группы, можно определить списком в экзаменационной ведомости; мно­ жество, элементами которого являются страны земного шара, — списком в географическом атласе (такое определение может расходиться с при­ нятым в ООН, но разрешение подобных проблем не входит в содержание нашего курса). Определяя множество списком его элементов, мы будем перечислять их в фигурных скобках через запятую: например, желая сказать, что элементами множества А являются числа 1, 2 и 3, а ника­ кие другие предметы не являются, будем писать: А = {1, 2,3}. Очевидно, что описанный способ определения применим только к конечным множе­ ствам, причём далеко не ко всем: например, вряд ли удастся практически применить его ко множеству всех рыб в Мировом океане. А определить списком элементов бесконечное множество невозможно и теоретически.

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

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

S = {х | х есть студент ПГТУ}

обозначает буквой S множество всех студентов ПГТУ. Читается эта за­ пись следующим образом: «S есть множество таких х>что х есть студент