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

Оглавление

Введение. 4

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

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

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

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

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

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

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

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пропозициональная теория

Не нашли, что искали? Воспользуйтесь поиском по сайту: