И.А. Пушкарёв

ВВЕДЕНИЕ В МАТЕМАТИЧЕСКУЮ ЛОГИКУ

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

Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

Вятский государственный университет

Факультет прикладной математики и телекоммуникаций

Кафедра «Прикладная математика и информатика»

И.А. Пушкарёв

Введение в математическую логику

Рекомендовано Ученым советом Вятского государственного университета в качестве учебного пособия

Киров 2008

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

УДК 519.116

П91

Рецензент: к.ф.-м.н. доцент кафедры алгебры и геометрии Вятского государственного гуманитарного университета О.С. Руденко.

Пушкарёв И.А. Введение в математическую логику: учебное пособие. – Киров: Изд-во ВятГУ, 2007. – 73 с.

Учебное пособие «Введение в математическую логику» ляляляляляляляляляляляляляляляляллялялялялялялялялля.

Редактор Е.Г. Козвонина

Подписано в печать Усл.печ.л. 4,6

Бумага офсетная Печать копир Aficio 1022

Заказ № Тираж 33 Бесплатно.

Текст напечатан с оригинала-макета, представленного автором

____________________________________________________________

610000, г. Киров, ул. Московская, 36.

Оформление обложки, изготовление – ПРИП ВятГУ

© И.А.Пушкарёв, 2008

© Вятский государственный университет, 2008

Оглавление

Введение 4

Глава 1. Пропозициональная логика 10

§1. Пропозициональная теория 10

§2. Исчисление высказываний 18

§3. Полнота исчисления высказываний 28

§4. Исчисление секвенций 41

§5. Интуиционистская пропозициональная логика 45

Глава 2. Предикаты и выразимость 55

§6. Формулы языка логики предикатов. Интерпретации 55

§7. Выразимость предикатов 64

Введение

История математической логики начинается с Лейбница. Он, предположительно, основываясь на личном опыте, который мог подсказать ему, что в занятиях математикой многое происходит формально-автоматически, и на успехах современного ему механистического взгляда на вещи, поставил задачу построения «логической машины», которая смогла бы заниматься рассуждениями, в частности – математикой, без участия человека. Как ни странно, на сегодняшний день эта задача (в значительной степени) решена. Этот факт остался незамеченным широкими слоями общественности из-за присущих ему ограничений и сопутствующих неприятностей, делающих эту машину предельно непрактичной даже в тех случаях, когда её работоспособность доказана, но тем не менее – это так. Наука, появившаяся в процессе этих изысканий, и называется математической логикой.

Есть несколько различных взглядов на то, чем занимается математическая логика. Во-первых, её можно воспринимать как науку о строгости рассуждений, то есть – о формальных способах сделать рассуждения безошибочными, а их результаты – безупречно достоверными. Фундаментальная идея Лейбница состояла в том, чтобы записывать утверждения в виде формул и получать новые утверждения из старых при помощи некоторого недвусмысленно описанного и не вызывающего сомнений набора правил. В определённом смысле это стало определением строгого рассуждения. С этой точки зрения математическая логика может рассматриваться как основание, на котором строится вся математика. Но, во-первых, упомянутый набор правил в действительности оказался устроенным сложнее, чем это казалось Лейбницу; во-вторых, этот набор оказался не единственно возможным, что привело к появлению разных взглядов на математическую строгость; в третьих, это ещё не всё.

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

Построение искусственного аналога мышления было необходимо не только как элемент программы Лейбница по «обесчеловечиванию» математики. Без него нельзя обойтись и по другой, более глубокой причине. Дело в том, что чисто математически изучать мышление как таковое невозможно. Этот феномен слишком сложен и имеет не только математический, но и ряд других аспектов: медицинский, философский и т.д. Для того чтобы абстрагироваться от прочих аспектов, подобно многим другим схожим ситуациям (например – в теории вероятностей), в качестве объекта исследования была выбрана некоторая формально описанная модель, кажущаяся адекватной исследуемому феномену. Она и стала предметом изучения. При этом сама модель достаточно проста, а вопрос о её адекватности сравнительно сложен. Однако именно это направление деятельности привело к изобретению теории алгоритмов и открытию настоящего математического сокровища – нескольких теорем, принадлежащих преимущественно Курту Гёделю, доказывающих невозможность достижения очень многих естественных целей, каковое казалось абсолютно необходимым для легитимизации всей математической деятельности в целом. Эта коллекция изящнейших результатов стала прообразом целой науки (любители которой, между прочим, организовали свой клуб даже на популярном интернет-сайте «в контакте» ).

Есть ещё одно обстоятельство, требующее обсуждения. Любое мышление требует языка, на котором оно происходит. Следовательно, при изучении мышления, даже в виде модели, потребуется обсуждать и язык. В свою очередь, любое обсуждение также должно происходить на некотором языке. Это не может быть тот же самый язык, что и язык модели. Однако в рассматриваемой ситуации оба эти языка совпадают с языком обычной математики, поэтому потребуются некоторые специальные ухищрения, чтобы их разделить.

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

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

Наконец, следует сказать несколько слов об имеющейся литературе. Существует довольно много учебников как по математической логике, так и по теории алгоритмов. Появление ещё одного, к тому же – написанного не специалистом, требует некоторого объяснения .

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

Однако ситуация не совсем плоха. Существует несколько очень талантливо написанных текстов, от которых автор настоящего пособия находится под глубочайшим впечатлением. Во-первых, это замечательная, хотя и совсем небольшая по объёму, книга Р.Линдона [1]. Во-вторых, сравнительно недавно появилась великолепная серия книг Н.К.Верещагина и А.Шеня [2, 3, 4], являющаяся, по-видимому, итогом многолетней работы большой группы специалистов, направленной в значительной степени и на совершенствование изложения материала (стоит отметить также более раннюю книжку В.А.Успенского [5]). Следует отметить также три замечательные книги одного из крупнейших специалистов в этой области – Р. Смаллиана (в специальной литературе его фамилию обычно пишут по-другому: Шмульян ) [6, 7, 8]. Конечно же, эти книги отнюдь не исчерпывают список хороших книг по математической логике, однако с (небесспорной, вообще-то) точки зрения автора, книг [1], [3] и [4], при дополнительном знакомстве с трилогией Смаллиана, достаточно для первоначального, но сравнительно качественного проникновения в предмет.

Однако книга [1] всё-таки написана местами довольно сурово и «невкусно», а местами – не вполне строго; характерно словосочетание «должно быть ясно из соображений общего характера» применительно к вопросу об арифметической выразимости основных понятий. Это словосочетание, возможно, есть реакция Линдона на то прискорбное обстоятельство, что «конкретные» арифметические выражения для этих понятий слишком сложны и зависят от слишком большого количества обстоятельств, которые тоже очень трудно явно оговорить, чтобы их «прямо так» привести (складывается впечатление, что этих выражений вообще никто никогда не видел в завершённом виде), и требуются какие-то довольно замысловатые косвенные соображения для того, чтобы всё-таки убедиться в существовании таковых. Эти соображения потом вкратце приводятся, их даже можно понять, но это совсем непросто сделать! Характерная особенность действительно сложных рассуждений: в тот момент, когда ты их понимаешь, ты перестаёшь понимать, как их можно коротко объяснить другому . К тому же Линдон (естественно) не придерживается многих наших отечественных традиций, касающихся изложения предмета (не все эти традиции хороши собой, но это не означает, что их можно просто проигнорировать ).

С другой стороны, более подробные и современные книги Верещагина и Шеня, при всём их блеске и изяществе, заметно уступают изложению Линдона в отношении ясности изложения общей картины и основных целей изучения предмета. Можно с сожалением констатировать, что это тоже отечественная традиция – при изложении данного предмета избегать обсуждения мотивов его появления и не согласовывать с ними порядок изложения .

Настоящее пособие есть слабая попытка «гибридизировать» эти два замечательных первоисточника, сохранив их достоинства и по возможности избежав влияния недостатков. Хотя, возможно, получилось как раз наоборот .

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