И.А. Пушкарев логика

4

делать и люди(или некоторый другой прототип) – но совсем по-другому

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

тот случай. Построение логической машины было осуществлено имитационно.

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

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

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

Без него нельзя обойтись и по другой, более глубокой причине. Дело в том, что

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

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

теории вероятностей), в качестве объекта исследования была выбрана

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

казалось абсолютно необходимым для легитимизации всей математической

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

прообразом целой науки (любители которой, между прочим, организовали свой клуб даже на популярном интернет-сайте «в контакте» J).

должен быть исчерпывающе формально описан и во всех деталях отличаться от

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

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

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

6

Наконец, следует сказать несколько слов об имеющейся литературе.

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

литературе его фамилию обычно пишут по-другому: Шмульян J) [6, 7, 8].

Конечно же, эти книги отнюдь не исчерпывают список хороших книг по

7

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

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

соображения для того, чтобы всё-таки убедиться в существовании таковых. Эти соображения потом вкратце приводятся, их даже можно понять, но это совсем

непросто сделать! Характерная особенность действительно сложных

рассуждений: в тот момент, когда ты их понимаешь, ты перестаёшь понимать,

как их можно коротко объяснить другомуJ. К тому же Линдон(естественно)

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

что их можно просто проигнорировать L).

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

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

8

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

1. Высказывания, простые и составные

Любое рассуждение состоит из высказываний. Высказывание удобно

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

безусловно ложным. При этом возможно, что неизвестно – истинно или ложно в действительности (в данный момент или в принципе навсегда) некоторое конкретное высказывание. Таковы, например, высказывания «Бог существует» и «В десятичной записи числа π содержится бесконечно много девяток».

Абстрагируясь от «особенностей текста», высказывание можно воспринимать как логическую константу с известным или неизвестным значением. Напротив,

в силу отчётливо выраженного условного характера, высказываниями не являются, например, фразы «бог существует» (написание с маленькой буквы

уничтожает недвусмысленную ссылку на христианского творца и требует уточнения – какой именно бог имеется в виду) и «x делится на 5» (истинность

этого утверждения зависит от значения, принимаемого переменной x).

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

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

из высказываний «Сборная России по футболу– действующий чемпион мира» и «Ныне здравствующий Папа Римский по национальности– индеец сиу» можно построить ещё несколько высказываний: «Сборная России по футболу –

действующий чемпион мира и ныне здравствующий Папа Римский п национальности – индеец сиу», «Если сборная России по футболу– действующий чемпион мира, то ныне здравствующий Папа Римский по национальности – индеец сиу», «Либо сборная России по футболу– действующий чемпион мира, либо ныне здравствующий Папа Римский по национальности – индеец сиу». Заметим, что одно из этих высказываний даже является истинным J.

9

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

булевым функциям, рассмотренным в курсе дискретной математики. Многие

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

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

который обычно называютпропозициональной логикой. При этом обычная

2. Алфавит

Во-первых, рассмотрим множество Ω всех высказываний. Переменные,

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

«множество всех пропозициональных переменных» (так же, собственно, как и

«множество всех высказываний»), строго говоря, математически некорректен,

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

пропозициональные переменные.

Вместе с некоторым наборомсимволов логических связок множество V

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

(сигнатура) может быть принят любым. Для простоты на начальный период этого обсуждения примем его равным{Ù, Ú, Ø, 0, 1} (этот набор полон, что

10

следует из существования СДНФ, поэтому он может быть модифицирован в любой другой).

3. Формальный язык

Во-вторых, определим формальный язык L, по существу – совпадающий с множеством формул (в данном случае– в базисе {Ù, Ú, Ø, 0, 1}). При этом придётся, конечно, задать другие обозначения для стандартных логических связок, так как приведённые выше являются стандартными ,исоответственно,

входят в метаязык. Именно, будет использован набор символов {C, D, N , O, I}

(соответствие между наборами очевидно).

Определение1.1. Множество (слов) L называется (а множество слов принято обычно называтьформальным языком) множеством формул пропозициональной логики, если оно удовлетворяет условиям:

(1)однобуквенные слова O и I принадлежат языку L;

(2)любое однобуквенное слово видаx, где x ÎV , принадлежит языку L

(можно не вполне точно прописать: V Í L );

(3)если u Î L , то N u Î L ;

(4)если u Î L и v Î L , то C uv Î L и D uv Î L ;

(5) если W – формальный язык, удовлетворяющий условиям (1) – (4), то

L Í W .

Замечания. (1) Определения, аналогичные приведённому выше,

называются индуктивными, а аксиомы, подобные (5) – аксиомами индукции.

(2) Само существование языка L – не такой уж тривиальный вопрос

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

друг другу!).

(3) В действительности L – (универсальная) алгебра, в рассматриваемом

случае – с пятью операциями(двумя нульарными, одной унарной и двумя