Математическая логика и теория алгоритмов

Министерство образования и науки Российской Федерации

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

В. М. Зюзьков

МАТЕМАТИЧЕСКАЯ ЛОГИКА

И ТЕОРИЯ АЛГОРИТМОВ

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

Томск
«Эль Контент»
2015

УДК
[510.6 + 510.5](075.8)
ББК
22.12я73
З-981

Рецензенты:

Крылов П. А., докт. физ.-мат. наук, профессор, зав. кафедрой алгебры
Томского государственного университета;

Карпов А. Г., канд. техн. наук, доцент кафедры компьютерных систем
в управлении и проектировании ТУСУРа.

Зюзьков В. М.
З-981
Математическая логика и теория алгоритмов : учебное пособие /
В. М. Зюзьков. — Томск : Эль Контент, 2015. — 236 с.

ISBN 978-5-4332-0197-2

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

УДК
[510.6 + 510.5](075.8)
ББК
22.12я73

ISBN 978-5-4332-0197-2
Зюзьков В. М., 2015

Оформление.
ООО «Эль Контент», 2015

ОГЛАВЛЕНИЕ

Введение
5

1
Миссия математической логики
7

1.1
Логика . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7

1.2
Математика . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12

1.3
Софизмы и парадоксы . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16

1.4
Математическая логика . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23

2
Краткая история логики
29

2.1
Становление логики . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29

2.2
Начало математической логики
. . . . . . . . . . . . . . . . . . . . . . .
34

2.3
Математическая логика в своем блеске и великолепии . . . . . . . . .
38

3
Основы теории множеств
44

3.1
Интуитивная теория множеств . . . . . . . . . . . . . . . . . . . . . . . .
44

3.2
Операции над множествами. Диаграммы Эйлера—Венна . . . . . . . .
48

3.3
Отношения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53

3.4
Эквивалентность и порядок . . . . . . . . . . . . . . . . . . . . . . . . . .
58

3.5
Функции
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
62

3.6
Мощность множеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68

4
Пропозициональная логика
78

4.1
Высказывания и высказывательные формы . . . . . . . . . . . . . . . .
78

4.2
Язык логики высказываний . . . . . . . . . . . . . . . . . . . . . . . . . .
88

4.3
Тавтологии и равносильности . . . . . . . . . . . . . . . . . . . . . . . .
95

4.4
Логическое следствие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

5
Языки первого порядка
105

5.1
Предикаты и кванторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

5.2
Термы и формулы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

5.3
Интерпретация формул
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

5.4
Формулы общезначимые, выполнимые, логически эквивалентные . . 117

5.5
Перевод с естественного языка на логический и обратно
. . . . . . . 124

6
Аксиоматический метод
131

6.1
Предварительные понятия и простые примеры . . . . . . . . . . . . . . 131

6.2
Формальные аксиоматические теории . . . . . . . . . . . . . . . . . . . 136

6.3
Исчисление высказываний . . . . . . . . . . . . . . . . . . . . . . . . . . 143

Оглавление

6.4
Аксиоматизация геометрии . . . . . . . . . . . . . . . . . . . . . . . . . . 147

6.5
Теории первого порядка . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

6.6
Аксиоматика Пеано . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

6.7
Аксиоматика Цермело—Френкеля . . . . . . . . . . . . . . . . . . . . . . 157

7
Математическое доказательство
164

7.1
Индукция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164

7.2
Математическая индукция
. . . . . . . . . . . . . . . . . . . . . . . . . . 168

7.3
Различные виды доказательств в математике . . . . . . . . . . . . . . . 181

7.4
Компьютерные доказательства . . . . . . . . . . . . . . . . . . . . . . . . 189

8
Алгоритмы и вычислимые функции
199

8.1
Понятие алгоритма и неформальная вычислимость . . . . . . . . . . . 199

8.2
Частично рекурсивные функции . . . . . . . . . . . . . . . . . . . . . . . 201

8.3
Машины Тьюринга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206

8.4
Тезис Ч¨eрча
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209

8.5
Некоторые алгоритмически неразрешимые проблемы
. . . . . . . . . 210

9
Сложность вычислений
214

9.1
Асимптотические обозначения . . . . . . . . . . . . . . . . . . . . . . . . 214

9.2
Алгоритмы и их сложность . . . . . . . . . . . . . . . . . . . . . . . . . . 220

9.3
Сложность задач
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222

Заключение
226

Глоссарий
227

Предметный и персональный указатель
231

ВВЕДЕНИЕ

Знания достигаются не быстрым бегом,
а медленной ходьбой.
Томас Бабингтон Маколей (1800–1859 гг.)

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

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

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

Соглашения, принятые в книге

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Эта пиктограмма означает определение или новое понятие.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Введение

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Эта пиктограмма означает цитату.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Эта пиктограмма означает теорему.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Эта пиктограмма означает лемму.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . .. . . . . . . . . . . . . . . . . . . . . .
Пример
. . .. . . . . . . . . . . . . . . . . . . . . .

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

. . .. . . . . . . . . . . . . . . . . . . . . .
Выводы
. . .. . . . . . . . . . . . . . . . . . . . . .

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Контрольные вопросы по главе
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Рекомендуемая литература к главе
. . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Глава 1

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

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

Яавилем ван де Ватеринг. Пустое зеркало

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

Следующий параграф посвящен математике. Для чего нужно изучать математику? Чем занимаются математики? Какая практическая польза от математики?

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

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

1.1 Логика

Что такое математическая логика? Прежде чем выяснить это, необходимо ответить на вопрос — что есть логика? Перечислим несколько различных определений,
серьезных и не очень.

Джон Локк (John Locke; 1632–1704 гг., английский философ): «Логика есть
анатомия мышления».

Джон Стюарт Милль (John Stuart Mill; 1806–1873 гг., английский философ):
«Логика не тождественна знанию, хотя область ее и совпадает с областью знания. Логика есть общий ценитель и судья всех частных исследований. Она не
задается целью находить очевидность; она только определяет, найдена очевидность или нет. Логика не наблюдает, не изобретает, не открывает — она судит.

Глава 1. Миссия математической логики

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

Льюис Кэрролл (Lewis Carroll, настоящее имя Charles Lutwidge Dodgson; 1832–
1898 гг., английский писатель, математик, логик, философ): «Траляля: «Если бы
это было так, это бы еще ничего, а если бы ничего, оно бы так и было, но так
как это не так, так оно и не этак! Такова логика вещей!».

Из книги «Алиса в Зазеркалье», перевод Н. Демуровой.
Джеймс Тёрбер (James Thurber; 1894–1961 гг., американский художник газетных сатирических комиксов, писатель и юморист): «If you can touch the clocks and
never start them, then you can start the clocks and never touch them1. That’s logic,
as I know and use it» [2].

Амброз Бирс (Ambrose Bierce; 1842–1913 гг., американский писатель, журналист, автор юмористических и «страшных» рассказов) [3]: «Логика (сущ.). Искусство размышлять и излагать мысли в неукоснительном соответствии с людской
ограниченностью и неспособностью к пониманию. Основа логики — силлогизм, состоящий из большой и меньшей посылок и вывода. Например:

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

Меньшая посылка: Один человек может выкопать яму под столб за 60 секунд.
Вывод: Шестьдесят людей могут выкопать яму под столб за 1 секунду.
Это можно назвать арифметическим силлогизмом, где логика соединена с математикой, что дает нам двойную уверенность в правильности вывода».

Бертран Рассел (Bertrand Russell; 1872–1970 гг., британский философ, общественный деятель и математик) [4]: «Логика. Деятельность может обеспечить
только одну половину мудрости; другая половина зависит от воспринимающей
бездеятельности. В конечном счете, спор между теми, кто основывает логику
на «истине», и теми, кто основывает ее на «исследовании», происходит из различия в ценностях и на определенном этапе становится бессмысленным.

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

Хотя мы больше не можем довольствоваться определением логических высказываний как вытекающих из закона противоречия, мы можем и должны все же
признать, что они образуют класс высказываний, полностью отличный от тех,
к знанию которых мы приходим эмпирически. Все они обладают свойством, которое <. . .> мы договорились называть «тавтологией». Это, в сочетании с тем
фактом, что они могут быть выражены исключительно в терминах переменных
и логических констант (где логическая константа — это то, что остается постоянным в высказывании, даже когда все его составляющие изменяются), даст
определение логики или чистой математики».

1Если вы можете трогать часы и никогда не завести их, то вы можете завести часы, их не трогая
(перевод мой — В. З.).

1.1 Логика
9

Непейвода Н. Н. (Непейвода Николай Николаевич; род. 1949 г., советский
и российский математик, учёный в области теоретической информатики и математической логики) [5]: «Логика — наука, изучающая с формальной точки зрения
понятия, методы их определения и преобразования, суждения о них и структуры
доказательных рассуждений».

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

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

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

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

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

В этом отношении логика сходна с грамматикой, которую мы изучали в школе.
Грамматика тоже исследует и описывает формы языковых выражений, отвлекаясь
от их содержания. Известное стихотворение «Бармаглот» из «Алисы в Зазеркалье»
Льюиса Кэрролла начинается со следующих строк:

Варкалось. Хливкие шорьки
Пырялись по наве.
И хрюкотали зелюки,
Как мюмзики в мове. . .

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

Глава 1. Миссия математической логики

соответствующие слова. Более того, как говорит Алиса об этих строках: они «наводят на всякие мысли, хоть и неясно — на какие». Аналогичное знание о формах
мысли дает нам логика.

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

Вот как, например, Марк Твен обыгрывает особенности словообразования
в немецком языке [6, с. 59]: «В одной немецкой газете, — уверяет он, — я сам читал
такую весьма занятную историю:

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

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

Однажды в тех местах, в городе Шраттертроттэле, был схвачен негодяй,
убивший готтентотку, мать двоих детей.

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

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

— Я поймал этого. . . Бейтельратте? Кенгуру? — в волнении вскричал он.
— Кенгуру? Какого? — сердито спросил потревоженный начальник.
— Как какого? Этого самого! Латтенгиттерветтеркоттэрбейтельратте.
— Яснее! Таких у нас много. . . Непонятно, чему ты так радуешься?
— Ах ты, несчастье какое! — возмутился негр, положил на землю лук и стрелы,
набрал в грудь воздуха и выпалил:

— Я поймал щраттертроттэльхоттентотенмуттэраттэнтэтэрлаттенгиттерветтеркоттэрбейтельратте! Вот кого!

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

Все марсиане имеют деревянные ноги.
Геракл — марсианин.
Следовательно, у Геракла — деревянные ноги.