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

УДК 510.7
ББК 22.12
У 77

Ус п е н с к и й В. А.,
В е р е щ а г и н Н. К.,
П л и с к о В. Е. Вводный
курс математической логики. — 2-е изд. — М.: ФИЗМАТЛИТ, 2007. —
128 с. — ISBN 978-5-9221-0278-0.

В учебном пособии содержится материал основного курса «Введение
в математическую логику», читаемого на механико-математическом факультете МГУ. Излагаются элементы теории множеств, основные понятия, относящиеся к семантике формализованных логико-математических языков первого
порядка, исчисление предикатов и теорема о его полноте, дается введение в
теорию алгоритмов и вычислимых функций.
Для студентов математических факультетов университетов, педагогических
институтов, а также других вузов с углубленным изучением информатики и
кибернетики.
Библиогр. 15 назв.

ISBN 978-5-9221-0278-0
c⃝ ФИЗМАТЛИТ, 2002, 2004, 2007

ОГЛАВЛЕНИЕ

Введение........................................................................................................................................... 
5

Г Л А В А  1

Э Л Е М Е Н Т Ы  Т Е О Р И И  М Н О Ж Е С Т В

§ 1. 
Основные понятия теории м нож еств..................................................................... 
6

§ 2. 
Бинарные отношения и ф у н к ц и и ........................................................................... 
6

§ 3. 
Взаимно однозначные соответствия и эквивалентные м нож ества........ 
9

§ 4. 
Счетные м нож ества.......................................................................................................  
10

§ 5. 
Канторовский диагональный м етод....................................................................... 
14

§ 6. 
Кардинальные числа, или мощ ности................................................................... 
14

§ 7. 
Теорема К ан то р а...........................................................................................................  
15

§ 8. 
Парадоксы теории м н ож еств................................................................................... 
16

§ 9. 
Аксиоматическая теория множ еств....................................................................... 
17

Г Л А В А  2

Я З Ы К И  П Е Р В О Г О  П О Р Я Д К А

§ 1. 
Высказывания и высказывательные ф о р м ы ..................................................... 
19

§ 2. 
Логические операции...................................................................................................  
21

§ 3. 
Л огика вы сказы вани й.................................................................................................  
23

§ 4. 
К ван торы ............................................................................................................................ 
24

§ 5. 
Субъектно-предикатная структура предлож ений............................................ 
26

§ 6. 
Я зы ки первого п оряд ка...............................................................................................  
27

§ 7. 
Примеры язы ков первого п о р яд ка......................................................................... 
32

§ 8. 
Определение интерпретации..................................................................................... 
33

§ 9. 
Формальное определение истинности................................................................... 
35

§ 10. Общезначимые формулы, выполнимые формулы, равносильные формулы ......................................................................................................................................  
37

§ 11. Предваренные ф о р м у л ы .............................................................................................  
42

§ 12. Истинность в конечных и н терпретациях........................................................... 
44

§ 13. Изоморфизмы и элементарная эквивалентность............................................ 
46

§ 14. Выразимость. Д оказательство невыразимости с помощью автоморфизмов ..................................................................................................................................  
50

Г Л А В А  3

Э Л Е М Е Н Т Ы  Т Е О Р И И  Д О К А З А Т Е Л Ь С Т В

§ 1. 
Аксиоматический м ето д .............................................................................................  
54

§ 2. 
Логическое следование...............................................................................................  
57

§ 3. 
Тавтологическое следствие....................................................................................... 
61

§ 4. 
Исчисление предикатов...............................................................................................  
62

§ 5. 
Вывод из ги п о тез...........................................................................................................  
69

§ 6. 
Теории первого п о р я д к а............................................................................................. 
72

Оглавление

§ 7. 
Ф ормальная ари ф м ети ка............................................................................................ 
76

Г Л А В А  4

Т Е О Р Е М А  Г Ё Д Е Л Я  О П О Л Н О Т Е

§ 1. Расширение тео р и и ......................................................................................................... 
79

§ 2. К аноническая интерпретация теории....................................................................  
81

§ 3. Д оказательство теоремы о полноте........................................................................  
84

§ 4. Некоторые следствия теоремы Гёделя о полноте............................................  
87

§ 5. М атематические применения теоремы о полноте и ее следствий...........  
88

§ 6. К атегоричность.................................................................................................................  
92

Г Л А В А  5

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

§ 1. 
Вычислимые функции.................................................................................................  
93

§ 2. 
Разрешимые множества................................................................................................  
95

§ 3. 
Полуразрешимые множества....................................................................................  
96

§ 4. 
Свойство пошагового выполнения алгоритма и его следствия................... 
99

§ 5. 
Универсальная вычислимая ф ункция................................................................. 104

§ 6. 
Перечислимость множества, теорем....................................................................... 107

§ 7. 
Машины Тьюринга......................................................................................................... 109

§ 8. 
Универсальная вычислимая по Тьюрингу функция......................................  119

§ 9. 
Тезис Ч ёрч а...................................................................................................................... 121

Список рекомендуемой литературы.................................................................................. 122

Предметный указатель............................................................................................................ 123

ВВЕДЕНИЕ

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

Конечно, можно рассуждать и без науки о правильных рассуждениях. Однако в некоторых случаях потребность в такой науке 
все же возникает. В частности, такая ситуация сложилась в математике в конце XIX — начале XX вв., когда были обнаружены 
парадоксы в теории абстрактных множеств, разработанной Г. Кантором. Анализ парадоксов потребовал внимательного исследования 
рассуждений, применяемых в математике, и тем самым вызвал необходимость в развитии науки о рассуждениях, т. е. логики.

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

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

ГЛАВА 1

ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ

§ 1. Основные понятия теории множеств

В начальный период развития теории множеств пользовались интуитивным понятием множества. Согласно Кантору, множество — 
это любое объединение в одно целое определенных объектов, которые называются элементами этого множества. Тот факт, что х 
есть элемент множества А, записывается так: х £ А. Если х £ А, 
то говорят, что А содержит х или что х принадлежит А. Если же х 
не является элементом множества А, пишут х ^ А.

Два множества А и В считаются равными, если они состоят из одних и тех же элементов, т. е. каждый элемент множества А принадлежит множеству В и каждый элемент множества В принадлежит 
множеству А. Запись А = В означает, что А и В равны, а Аф  В — 
что А и В не равны. Запись А С В означает, что каждый элемент 
множества А является также элементом множества В; в этом случае говорят, что А является подмножеством множества В или что 
А включено в В. Если .1 С  /? и .1 /  В, то А называется собственным подмножеством В, и в этом случае пишут А С В. Множество, не содержащее элементов, называется пустым и обозначается
0. Семейство всех подмножеств данного множества А обозначается
П А).

Множество, элементами которого являются данные объекты а±, 
, обозначается {а\, а2, ... }. Например, {а, Ь} есть множество 
с элементами а и Ъ. Если при этом а ф Ь, то {а,Ь} называется 
неупорядоченной парой объектов а и Ъ. Множество {а, а} можно 
обозначить также {а}. Это одноэлементное множество с элементом 
а. Через {х | Ф(ж)} обозначается множество таких элементов х, для 
которых выполняется условие Ф(ж).

Множество А и В = {х | х £ А или х £ В} называется объединением множеств А и В. Пересечением множеств А и В называется 
множество А п В  = {х | х £ А и х £ В}. Разностью множеств А и В 
называется множество А \ В = {х \ х £ А н х ^ В}.

2. Бинарные отношения и функции
7

§ 2. Бинарные отношения и функции

Через {а, 6) обозначается упорядоченная пара двух объектов а и Ъ. 
Основное свойство упорядоченных пар таково: каковы бы ни были 
объекты 01,02, 61, 62, равенство (оі,6і) = (02,62) имеет место тогда 
и только тогда, когда оі = 02 и 6і = 62. Вообще, для любого натурального числа п можно образовать кортежи длины п (или, как 
иногда говорят, упорядоченные п-ки) объектов (аі,... ,ап) с тем 
свойством, что {аі,... , ап) = (6і , ... , Ъп) тогда и только тогда, когда 
аі = Ьі (г = 1,... ,п).

Прямым (или декартовым) произведением множеств А ж В называется множество А х В, состоящее из всех таких упорядоченных 
пар (а, 6), что а £ А и 6 £ В. Аналогично определяется прямое произведение множеств А і,... ,А п как множество, состоящее из всех 
таких кортежей (аі,... , ап), что оі ё 
,ап 6 -4П.

Бинарным отношением между элементами множеств А и В называется любое подмножество В множества А х В. Часто вместо 
(ж, у) € Б пишут жЯу. Областью определения бинарного отношения Я называется множество 6д, состоящее из всех таких ж, что 
(ж, у) € Б хотя бы для одного у. Множеством значений рд бинарного отношения Б называется множество всех таких у, что (ж, у) £ Б 
хотя бы для одного ж. Обратным отношением для бинарного отношения Б называется множество Я-1, состоящее из всех таких упорядоченных пар (ж,у), что (у,ж)бЯ. Заметим, что 6д-і=ря ; ря_і = 6д. 
Если Б\ — отношение между элементами множеств А и Я, а Яг — 
отношение между элементами множеств Я и С, то можно образовать произведение (композицию) отношений Яі и Яг- Произведением Яі о Я2 отношений Яі и Яг называется отношение между элементами множеств А и С, состоящее из всех пар (ж, г), для которых 
найдется такой элемент у £ В, что (ж, у)£В\ и (у. г) 6 Я?. Например, 
если М — множество всех живущих или когда-либо живших мужчин 
на Земле, а отношение Я С М  х М состоит из таких пар (ж, у), что ж 
является отцом у, то Я-1 — это отношение, состоящее из таких пар 
(ж, у), что ж является сыном у, а Я о Я — отношение, состоящее из 
всех таких пар (ж, у), что ж является дедушкой у по отцовской линии.

Отношение /  называется функцией, если из (ж, у) £ /  и (ж, г) £ /  
следует у = г. Функция /  называется функцией из А в Я, если 
6/ С А, ру С Я; если при этом бу = А, то пишут /  : А —> Я. 
Если /  — функция и (ж, у) € /, то обычно пишут у = /(ж) и называют у значением функции /  при значении аргумента ж. Если 
не существует такое у, что (ж, у) € /, то выражение /(ж) считается 
неопределенным.

Гл. 1. Элементы теории множеств

Среди функций из А в А выделим так называемую тождественную функцию іс іа  =  { { ж ,ж) | ж £ А}. Очевидно, что гф Д ж ) =  %■, 
каков бы ни был элемент х £ А.

Функция /  называется последовательностью, если ее область 
определения — это множество натуральных чисел N = {0,1,2,...}.

В случае, когда множества А и В совпадают, бинарное отношение Л между элементами множеств А и В называется бинарным 
отношением на множестве А. Бинарное отношение В на множестве А называется:

рефлексивным, если (х , х) £ К для всех х £ А;
иррефлексивным., если (х, х) ^ К для любого х £ А;
симметричным, если из (х, у) £ Л следует (у, х) £ Л:
антисимметричным, если из {х,у) £ Л и (у,х) £ Л следует х = у;

транзитивным, если из (ж, у) £ Л и (у, г) £ Л следует (ж, г) £ Л.
Бинарное отношение на множестве А называется частичным упорядочением (или частичным порядком), если это отношение рефлексивно, антисимметрично и транзитивно. Частичное упорядочение обычно обозначается символом 
Множество А с заданным 
на нем частичным порядком ^ называется частично упорядоченным, и обозначается (А, ^).

Бинарное отношение на множестве А называется строгим частичным упорядочением (или строгим частичным порядком), если 
это отношение иррефлексивно и транзитивно. Строгое частичное 
упорядочение обычно обозначается символом <. Множество А с заданным на нем строгим частичным порядком < называется строго 
частично упорядоченным и обозначается (А, <).

Бинарное отношение на множестве А называется отношением 
эквивалентности, если это отношение рефлексивно, симметрично 
и транзитивно.

У пражнения.
1. Пусть А и В — конечные множества, состоящие из ш и п 
элементов соответственно.

а) Сколько существует бинарных отношений между элементами 
множеств А и В ?

б) Сколько имеется функций из А и В ?
2. Образуют ли бинарные отношения на множестве А группу 
относительно операций о и _1?

3. Доказать, что для любых функций / :  А —> В и д : В —>Сих 
композиция /  о д является функцией из А в С, причем (/ о д)(х) =
= 0(/(ж))·

§ 3. Взаимно однозначные соответствия и эквивалентные множества 
9

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

5. Пусть (А, 4.) — частично упорядоченное множество. Доказать, что бинарное отношение В =  {(х, у) | х ^ у и х ф у} является 
строгим частичным порядком на множестве А.

6. Пусть (Л, <) — строго частично упорядоченное множество. 
Доказать, что бинарное отношение В = {(ж,у) | х < у или х = у} 
является частичным порядком на множестве А.

7. Пусть (Л, <) — строго частично упорядоченное множество. 
Элемент а € А называется максимальным, если в Л не существует такой элемент Ь, что а < Ъ. Доказать, что если множество Л 
конечно, то в нем существует максимальный элемент.

8. Пусть В — отношение эквивалентности на множестве Л. Классом эквивалентности элемента а € А называется множество

[а] = {х | (а, х) £ В}.

Доказать, что для любых элементов а,Ъ £ А их классы эквивалентности [а] и [Ь] либо совпадают, либо не имеют общих элементов.

§ 3. Взаимно однозначные соответствия и эквивалентные 
множества

Функция /  называется взаимно однозначной функцией (или 
1-1-функцией), если из f(x ) = f(y) следует х = у (выражение 
f(x) = f(y) означает, что f(x) и f(y) определены и их значения совпадают). Например, іс іа является взаимно однозначной функцией. 
Вообще, функция /  взаимно однозначна тогда и только тогда, когда 
отношение / -1 является функцией. Если /  : Л —^ В и g : В —> С 
суть взаимно однозначные функции, то их композиция /  о g также 
есть взаимно однозначная функция.

Взаимно однозначным соответствием между множествами Л 
и В называется такая взаимно однозначная функция /  : Л —> В, 
что р/ = В.

Множества Л и В называются равномощными, если существует 
взаимно однозначное соответствие между Л и В. Чтобы выразить, 
что Л и В равномощны, пишут Л ~ В.

Т еорем а 1. Каковы бы ни были множества А, В, С,
1) Л ~ А;
2) если А ~ В, то В ~ Л;
3) если А ~ В и В ~ С, то А ~ С.

Гл. 1. Элементы теории множеств

Д о к а за те л ь с т в о . Легко проверяется справедливость следующих утверждений.

1) Функция І(1а  является взаимно однозначным соответствием между А и А.

2) Если /  — взаимно однозначное соответствие между А и В, то 
/ -1 есть взаимно однозначное соответствие между В и А.

3) Если /  — взаимно однозначное соответствие между А и В, 
ад — взаимно однозначное соответствие между В и С, то их композиция /о д  есть взаимно однозначное соответствие между А и С.

Отсюда немедленно следует утверждение теоремы.
Теорема 1 доказана.

Равномощные множества называются также эквивалентными.

§ 4. Счетные множества

Непустое множество называется счетным, если оно есть множество значений какой-либо последовательности. Пустое множество 
по определению относится к счетным.

Пример 1. Любое конечное множество является счетным. Действительно, пусть М  = {ао,... , ап-\ }. Рассмотрим последовательность /  : N —> М  такую, что /( х) = а/, где I есть остаток от деления 
ж на п. Очевидно, что р/ = М.

Пример 2. Натуральный ряд N — счетное множество, поскольку он является множеством значений функции ісіц : N —У N.

Пример 3. Пусть дан некоторый алфавит, т.е. набор элементарных знаков, называемых буквами. Конечный ряд букв, написанных друг за другом, называется словом в данном алфавите. Иногда 
бывает удобно рассматривать также пустое слово, совсем не содержащее букв и обычно обозначаемое Л. Если алфавит А конечен, то 
множество А* всех слов в алфавите А счетно.

Действительно, пусть А = {б'і,... , Бр-\ } (р 
2). Определим последовательность /  : N —> А* следующим образом: /(0) = Л; если 
же х > 0, то рассмотрим запись числа х в р-ичной системе счисления, выпишем в порядке вхождения в нее все ненулевые «цифры» 
кі, ■ ■ ■ ,кт(1 ^ кі ^ р — 1) и положим /(ж) = 5^ ■ ■ ■ $ит ■ Очевидно, что р/ = А*. А именно, произвольное слово 5$0 .. ■ 31п является 
значением функции /  при значении аргумента іоРп + ЧРп~1Н-----Ип.

§ 4. Счетные множества
11

Пример 4. Всякое множество, эквивалентное счетному множеству, счетно. 
Действительно, пусть А — счетное множество 
и А ~ В. Пусть /  : N —¥ А — такая последовательность, что р/ = А, 
и пусть д : А —¥ В — взаимно однозначное соответствие между А 
и В. Нетрудно проверить, что их композиция fo g  есть последовательность, причем pfog = В, т.е. В счетно. Отсюда и из примера 2 
получаем, в частности, что всякое множество, эквивалентное натуральному ряду, счетно. Например, счетным является множество 
всех слов в алфавите {0,1,2,... ,9}, являющихся десятичными записями натуральных чисел, поскольку оно, очевидно, эквивалентно 
натуральному ряду.

Т еорем а 2. Любое подмножество счетного множества счетно.

Д о к а за те л ь с т в о . Пусть А — счетное множество, В С А. 
Если В — пустое множество, то оно счетно по определению. Рассмотрим случай, когда В непусто. Тогда А также не пусто, и существует последовательность /  такая, что р/ = А. Зафиксируем некоторый элемент b € В и определим последовательность g : N —і В 
следующим образом:

Г /(ж), если /(ж) € В;
йі) = I , 
,, ч 
„
[ I, 
если /(ж) f  В.

Очевидно, что р/ = В, т. е. В счетно. Теорема 2 доказана.

Из теоремы 2 и примера 3 получается еще одно доказательство 
счетности множества десятичных записей натуральных чисел, поскольку они образуют подмножество множества всех слов в 10- 
буквенном алфавите {0,1,2,... ,9}.

Пример 
5. Множество всех рациональных чисел Q счетно. 
Действительно, всякое рациональное число записывается в виде несократимой дроби вида m/n, где ш — целое число, а п — положительное целое число, т. е. множество Q эквивалентно множеству таких дробей, которое, в свою очередь, является подмножеством всех 
слов в алфавите {0,1,2,... , 9, —, /}. Теперь счетность Q следует из 
примера 3, теоремы 2 и примера 4.

Т еорем а 3. Объединение счетного числа счетных множеств 
счетно.

Д о к а за те л ь с т в о . Пусть дано счетное множество А, элементы которого суть счетные множества. Требуется доказать счетность

Гл. 1. Элементы теории множеств

множества В, состоящего из всех элементов, принадлежащих элементам множества А. Если А пусто, то В также пусто и счетно по 
определению. Пусть А непусто и среди его элементов есть непустые 
множества. Так как А счетно, то существует такая последовательность h : N —1 А, что р/, = А. Обозначим h(n) через Ап (те £ N).

Для любого те, если Ап не пусто, существует такая последовательность / п : N —> Ап, что pfn = Ап. Заметим, что В непусто, 
и зафиксируем некоторый элемент b £ В. Если Ап пусто, определим последовательность / п : N —1 В так, что f n(x) = Ь для любого 
х. Рассмотрим бесконечную таблицу, в строках которой последовательно выписаны значения функций /о, /і

X
0 
1 
2

fo(x)
/о(0) 
/о(1)—і/о(2) 
...

1 
і /

М х )
/і(0) 
/і(1) 
М2) 
...

S  
S  
S

Мх)
МО) 
/ 2(і) 
М2) 
...

i  s  
s  
s

Очевидно, в этой таблице содержатся все элементы множества В 
и только они. Пересчитывая элементы таблицы в порядке, указанном стрелками, мы получим последовательность д : У< —> В. го есть,

9(0) = МО), 
д(1) = МО), 
0(2) = /о(1), 
0(3) = /о(2), 
. . . .

Тем самым доказана счетность множества В. Теорема 3 доказана.

Пример 6. Множество А* всех слов в счетном алфавите А счетно. Действительно, если А — счетный алфавит, то существует такая последовательность /  : N —У А, что р/ = А. Обозначим /(те) 
через ап (те £ П). Пусть Ап = {ао,аі,... ,ап}. Поскольку любое 
слово в алфавите А состоит лишь из конечного числа букв, оно 
является одновременно словом в одном из алфавитов Ап. (А именно, слово 
... аит является словом в конечном алфавите Аь, где 
к = піах(&!,... ,кт)·) Таким образом, множество всех слов в алфавите А есть объединение счетного числа множеств А*а, А1,А%,__
Теперь счетность А* вытекает из примера 3 и теоремы 3.

Т еорем а 4. Множество значений функции, определенной на 
счетном множестве, счетно.