Дискретная математика. Формально-логические системы и языки

С. М. Авдошин, А. А. Набебин

Дискретная математика.  
Формально-логические системы 
и языки

Москва, 2018

УДК 510.6
ББК 22.12 
А18

Р е ц е н з е н т ы:
Калягин В. А. — доктор физико-математических наук, профессор НИУ ВШЭ
Петренко А. К. — доктор технических наук, профессор,  
заведующий отделом «Технологии программирования»  
Института системного программирования РАН

Н а у ч н ы й  р е д а к т о р:
Захаров В. А. — доктор физико-математических наук,  
профессор МГУ им. М. В. Ломоносова 

Авдошин С. М., Набебин А. А.
А18 
Дискретная математика. Формально-логические системы и языки. – М.: 
ДМК Пресс, 2018. – 390 с.: ил. 

ISBN 978-5-97060-622-3

Книга содержит основные сведения из формально-логических систем. Это функции алгебры логики (булевы функции), теорема Поста о функциональной полноте, k-значные логики, 
производные булевых функций, аксиоматические исчисления высказываний, предикатов, 
секвенций, резолюций и язык программирования Пролог. Рассматриваются монадическая 
логика, конечные автоматы и представимые ими языки, темпоральная логика, аксиоматический язык программирования OBJ3.
В основу книги положен многолетний опыт преподавания авторами дисциплины «Дискретная математика» на факультете бизнес-информатики, на факультете компьютерных наук 
Национального исследовательского университета Высшая школа экономики и на факультете 
автоматики и вычислительной техники Национального исследовательского университета 
Московский энергетический институт. 
Книга предназначена для студентов бакалавриата, обучающихся по направлениям 09.03.01 
«Информатика и вычислительная техника», 09.03.02 «Информационные системы и технологии», 09.03.03 «Прикладная информатика», 09.03.04 «Программная инженерия», а также для 
ИТ-специалистов и разработчиков программных продуктов.

УДК 510.6
ББК 22.12 

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

 
© Авдошин С. М., Набебин А. А., 2018 
ISBN 978-5-97060-622-3 
© Оформление, издание, ДМК Пресс, 2018

Содержание

Предисловие ..........................................................................................................................................9

Введение .................................................................................................................................................13

Часть I. АЛГЕБРА ЛОГИКИ И ПРЕДИКАТЫ ..................................................................27

Глава 1. Алгебра логики .................................................................................................................28
1.1. Функции алгебры логики ...........................................................................................................28
1.2. Формулы. Реализация функций формулами ......................................................................29
1.3. Равносильные преобразования формул .............................................................................31
1.4. Нормальные формы. Совершенные нормальные формы ............................................33

Совершенные нормальные формы ..........................................................................................34

1.5. Минимизация нормальных форм ...........................................................................................36

1.5.1. Алгоритм Куайна построения сокращенной ДНФ ..................................................38
1.5.2. Алгоритм построения сокращенной ДНФ с помощью КНФ ...............................39
1.5.3. Построение всех тупиковых ДНФ ..................................................................................41
1.5.4. Алгоритм минимизации функций в классе ДНФ .....................................................42
1.5.5. Алгоритм минимизации функций в классе КНФ .....................................................43
1.5.6. Алгоритм минимизации функций в классе нормальных форм .........................43

1.6. Минимизация частично определенных функций ............................................................45

1.6.1. Алгоритм минимизации частично определенных функций  
в классе ДНФ .....................................................................................................................................46
1.6.2. Алгоритм минимизации частично определенных функций  
в классе КНФ .....................................................................................................................................46

1.7. Двойственные функции. Принцип двойственности .........................................................49
1.8. Линейные функции .......................................................................................................................50
1.9. Монотонные функции ..................................................................................................................53
1.10. Теорема Поста о функциональной полноте .....................................................................55
1.11. Предполные классы ...................................................................................................................58

Глава 2. Функции k-значной логики .......................................................................................60
2.1. Функции и отношения .................................................................................................................60
2.2. Самодвойственные функции ....................................................................................................63
2.3. Монотонные функции ..................................................................................................................63
2.4. Линейные функции .......................................................................................................................64
2.5. Функции, сохраняющие разбиение .......................................................................................64
2.6. Классы типа ℂ .................................................................................................................................64

 Содержание

2.7. Классы типа 𝔹 .................................................................................................................................65
2.8. Сравнение функций двузначной и многозначной логик ..............................................66

Глава 3. Производные булевой функции в синтезе логических схем ...............67
3.1. Производная булевой функции ...............................................................................................67
3.2. Синтез логических схем методом каскадов .......................................................................70
3.3. Разложение булевой функции в ряд .....................................................................................77

Глава 4. Синтез схем из функциональных элементов .................................................80
4.1. Схема из функциональных элементов .................................................................................80
4.2. Функции Шеннона ........................................................................................................................82
4.3. Элементарные методы синтеза схем ....................................................................................82
4.4. Синтез мультиплексоров ............................................................................................................84
4.5. Элементы функциональной декомпозиции .......................................................................86
4.6. Обнаружение неисправностей в схемах .............................................................................91

Глава 5. Аксиоматическое исчисление высказываний ...............................................94
5.1. Определение исчисления высказываний ...........................................................................94
5.2. Теорема дедукции  в исчислении высказываний ............................................................98
5.3. Производные правила вывода .............................................................................................100
5.4. Тождественно истинные и доказуемые формулы .........................................................105
5.5. Разрешимость, непротиворечивость, полнота, независимость аксиом ................108
5.6. Формулировка исчисления высказываний с единственным правилом  
вывода – правилом заключения ..................................................................................................111

Глава 6. Логика предикатов ......................................................................................................113
6.1. Предикаты, кванторы ................................................................................................................113
6.2. Общезначимость, выполнимость, невыполнимость, опровержимость  
формул логики предикатов ............................................................................................................115
6.3. Равносильность формул ..........................................................................................................119
6.4. Нормальные формы ..................................................................................................................121

6.4.1. Префиксная нормальная форма .................................................................................121
6.4.2. Стандартная форма Сколема ........................................................................................122

6.5. Проблема разрешимости в логике предикатов .............................................................125

6.5.1. Проблема разрешимости $-формул ..........................................................................126
6.5.2. Проблема разрешимости ∀-формул ......................................................................... 127
6.5.3. Проблема разрешимости монадической логики  ................................................128

6.6. Отношения ....................................................................................................................................130
6.7. Суперпозиция функций ............................................................................................................132
6.8. Операции Мальцева над функциями .................................................................................133
6.9. Алгебра отношений (реляционная алгебра) ....................................................................133
6.10. Алгебра отношений k-значной логики ............................................................................135

Содержание  5

Глава 7. Аксиоматическое исчисление предикатов ...................................................136
7.1. Определение исчисления предикатов ...............................................................................136
7.2. Теорема дедукции в исчислении предикатов .................................................................138
7.3. Непротиворечивость исчисления предикатов ................................................................141
7.4. Семантическая полнота исчисления предикатов относительно класса  
общезначимых формул ....................................................................................................................142

7.4.1. Непротиворечивые расширения исчисления предикатов ...............................143
7.4.2. Формализмы G и Gk ...............................................................................................................................................................................................145

Глава 8. Исчисление секвенций .............................................................................................151
8.1. О правилах вывода в секвенциальном исчислении высказываний .....................151
8.2. Секвенциальное исчисление высказываний ..................................................................155
8.3. Секвенциальное исчисление предикатов  .......................................................................158

Глава 9. Метод резолюций в логике предикатов и Пролог ..................................161
9.1. Метод резолюций в логике высказываний .....................................................................161

9.1.1. Семантическое дерево ....................................................................................................162
9.1.2. Правило резолюции .........................................................................................................164

9.2. Эрбрановы универсум, базис, интерпретация ............................................................... 167
9.3. Семантические деревья. Теорема Эрбрана .....................................................................170
9.4. Унификация ...................................................................................................................................174
9.5. Метод резолюций в логике предикатов ........................................................................... 177
9.6. Основы Пролога ..........................................................................................................................182

9.6.1. Унификация в Прологе ....................................................................................................189
9.6.2. Декларативный и операторный смысл Пролог-программы ............................191
9.6.3. Бэктрекинг и оператор отсечения ..............................................................................193
9.6.4. Объявление операторов .................................................................................................194

9.7. Примеры программ и вычислений в Прологе ................................................................196

9.7.1. Принадлежность элемента списку ..............................................................................196
9.7.2. Первый элемент в списке ...............................................................................................199
9.7.3. Последний элемент в списке ........................................................................................200
9.7.4. Следующий элемент в списке .......................................................................................201
9.7.5. Соединение списков .........................................................................................................204
9.7.6. Обращение списка ............................................................................................................205
9.7.7. Выравнивание списка.......................................................................................................206
9.7.8. Добавление элемента в начало списка ....................................................................206
9.7.9. Удаление первого вхождения данного элемента из списка ............................ 207
9.7.10. Удаление всех вхождений данного элемента из списка ................................ 207
9.7.11. Замена элемента в списке ...........................................................................................210
9.7.12. Быть подсписком в списке ...........................................................................................210
9.7.13. Включение множеств .....................................................................................................212

 Содержание

9.7.14. Равенство множеств .......................................................................................................213
9.7.15. Объединение множеств ................................................................................................213
9.7.16. Пересечение множеств .................................................................................................215
9.7.17. Разность множеств ...........................................................................................................215
9.7.18. Декартово произведение множеств ........................................................................215
9.7.19. Множество всех подмножеств данного множества ..........................................216
9.7.20. Удаление всех повторов элементов в списке ......................................................216
9.7.21. Принадлежность множества списку подмножеств ............................................216
9.7.22. Удаление всех повторов подмножеств в данном списке множеств ...........216
9.7.23. Удаление повторов атомов в списке списков атомов ...................................... 217
9.7.24. Последовательное порождение нумерованных атомов ................................. 217
9.7.25. Программа построения сокращенной ДНФ по конъюнктивной  
нормальной форме ...................................................................................................................... 217
9.7.26. Программа построения сокращенной ДНФ по конъюнктивной  
нормальной форме без отрицаний .......................................................................................219

9.8. Некоторые встроенные предикаты Пролога ..................................................................220

9.8.1. Средства управления .......................................................................................................220
9.8.2. Классификация термов ...................................................................................................221
9.8.3. Унификация термов ..........................................................................................................221
9.8.4. Сравнение термов .............................................................................................................221
9.8.5. Арифметические функции .............................................................................................222
9.8.6. Арифметические предикаты .........................................................................................222
9.8.7. Обработка термов ..............................................................................................................223
9.8.8. Работа со стрингами .........................................................................................................223
9.8.9. Составление списков .......................................................................................................223
9.8.10. Взаимодействие с базой данных .............................................................................224
9.8.11. Стандартные ввод и вывод .........................................................................................225
9.8.12. Доступ к файлам ..............................................................................................................226
9.8.13. Стандартный доступ к файлам в Прологе .............................................................226
9.8.14. Движение в файле .......................................................................................................... 227
9.8.15. Исполнение системных функций ............................................................................. 227
9.8.16. Отладчик (Debugger) ...................................................................................................... 227

Часть II. МОНАДИЧЕСКАЯ ЛОГИКА И КОНЕЧНЫЕ АВТОМАТЫ ...........................230

Глава 10. Конечные автоматы ................................................................................................231
10.1. Автоматы Мили и Мура .........................................................................................................231
10.2. Источники ...................................................................................................................................235
10.3. Регулярные языки и регулярные выражения ...............................................................240

10.3.1. Операции Клини и регулярные языки ...................................................................240
10.3.2. Алгебра регулярных выражений Клини ................................................................242

10.4. Теоремы замкнутости для класса автоматно представимых языков .................243

Содержание  7

10.5. Минимизация числа состояний автомата с выходом ...............................................248

10.5.1. Склеивание неразличимых состояний ...................................................................250
10.5.2. Алгоритм минимизации автомата ............................................................................250
10.5.3. Алгоритм разбиения множества состояний на классы  
неотличимых состояний .............................................................................................................254
10.5.4. Алгоритм проверки эквивалентности автоматов ..............................................255

Глава 11. Автоматы и сверхъязыки .....................................................................................257
11.1. Макроавтоматы......................................................................................................................... 257
11.2. Конкатенация языка и сверхъязыка ................................................................................259
11.3. Сверхитерация автоматных языков .................................................................................261
11.4. Детерминизация макроисточника ....................................................................................264

Глава 12. Проблема униформизации .................................................................................267
12.1. Языки и операторы ................................................................................................................. 267
12.2. Игры...............................................................................................................................................270
12.3. Стратегии .....................................................................................................................................273
12.4. Униформизация конечноавтоматных языков ..............................................................276

12.4.1. Порядковые векторы и порядковые стратегии ..................................................276
12.4.2. Теоремы о порядковых стратегиях ..........................................................................278
12.4.3. Пример построения выигрывающего автомата .................................................282

Глава 13. Монадическая логика натуральных чисел ................................................285
13.1. Монадическая логика ............................................................................................................285
13.2. Выразимость в монадической логике ............................................................................. 287

13.2.1. Макроисточники и монадическая логика  ............................................................289
13.2.2. Регулярные языки и монадическая логика ..........................................................289
13.2.3. Общерегулярные языки и монадическая логика ..............................................290

13.3. Специальная префиксная форма ......................................................................................290
13.4. Синтез автомата по формуле монадической логики ................................................292
13.5. Алгоритмическая разрешимость монадической логики ..........................................294

Глава 14. Темпоральная логика ..............................................................................................296
14.1. Пропозициональная темпоральная логика ...................................................................296
14.2. Интерпретация формул ......................................................................................................... 297
14.3. Общезначимость, выполнимость, опровержимость, невыполнимость ..............299
14.4. Другие темпоральные операторы .....................................................................................302
14.5. Аксиоматическая система ....................................................................................................304
14.6. Спецификация свойств формулами .................................................................................305
14.7. Спецификация взаимодействия и параллелизма .......................................................306

 Содержание

Глава 15. Аксиоматический язык программирования OBJ3 .................................310
15.1. Описание языка ........................................................................................................................310
15.2. Спецификация объекта..........................................................................................................311
15.3. Сорта и подсорта ......................................................................................................................312
15.4. Импорт модулей .......................................................................................................................312
15.5. Встроенные сорта ....................................................................................................................314
15.6. Декларация атрибутов ...........................................................................................................314
15.7. Приоритет ...................................................................................................................................315
15.8. Параметризованное программирование ......................................................................315
15.9. Теории ...........................................................................................................................................316

15.9.1. Программная спецификация FIELD алгебраического поля ..........................316
15.9.2. Программная спецификация PROPC пропозиционального  
исчисления ....................................................................................................................................... 317
15.9.3. Программная спецификация SET-NAT множества натуральных  
чисел ...................................................................................................................................................318
15.9.4. Программная спецификация obj WORDTREE дерева слов ............................319
15.9.5. Программная спецификация WORDSTACK словарого стека .........................320
15.9.6. View .......................................................................................................................................321
15.9.7. Инстанциация ...................................................................................................................321
15.9.8. Параметризованная теория линейного векторного пространства ............321
15.9.9. Параметризованный модуль obj ORD-PAIR пар вида  
(натуральное число, слово) .......................................................................................................322
15.9.10. Параметризованный модуль SEQUENCE[X :: ELEMS] списков  
натуральных чисел и списков слов........................................................................................323

Приложение 1. Логика высказываний и предикатов. Пролог .............................325

Приложение 2. Конечные автоматы ...................................................................................357

Приложение 3. Анализ конечных автоматов ................................................................364

Приложение 4. Синтез конечных автоматов .................................................................380

Литература ..........................................................................................................................................383

Обозначения ......................................................................................................................................386

Предисловие

Философская логика есть наука о законах и формах отражения в мышлении развития объективного мира, о закономерностях познания истины.
Основная задача философской логики есть формулировка законов и принципов, соблюдение которых является необходимым условием получения истинных умозаключений.
Формальная логика есть наука, изучающая формы мысли (понятия, суждения, умозаключения, доказательства) со стороны их логической структуры, то 
есть отвлекаясь от конкретного содержания мыслей и вычленяя лишь общий 
способ связи частей этого содержания.
Начало формальной логики положил Аристотель.
Математическая логика есть область знания, в которой формальная логика 
изучается математическими методами.
Основные задачи математической логики есть: 1) построение формальнологических (аксиоматических) исчислений; 2) изучение связи логических исчислений с теми содержательными областями знаний, которые служат их интерпретациями и моделями.
Одно из крупнейших достижений математики первой половины XX века – 
оформление математической логики и теории алгоритмов в самостоятельные 
дисциплины. Три крупных результата определили характер всех последующих 
исследований этого направления: теорема Геделя о полноте аксиоматического исчисления предикатов относительно всех тождественно истинных формул 
такого исчисления (полнота относительно интерпретации); существование 
алгоритмически неразрешимых проблем, в частности теорема Черча об алгоритмической неразрешимости исчисления предикатов; теорема Геделя о неполноте аксиоматической арифметики относительно множества ее истинных 
формул.
Уже в древности предпринимались попытки строго изложить математические факты, которые стремились вывести из немногочисленных исходных посылок – аксиом. Замечательным примером такого подхода к изложению математических сведений были «Начала» древнегреческого математика Евклида, 
в особенности его геометрия. Изучались и законы правильного вывода следствий из исходных посылок (логика Аристотеля).
Первые попытки создать строгие математические теории восходят к работам Буля, Фреге, Пеано, других математиков. Исследователи руководствовались целью заложить такие основания математики, выделить такие аксиомы 
и правила вывода, с помощью которых можно было бы формально доказать 
любое содержательно истинное математическое утверждение. Подобные 
утверж дения можно было бы доказывать автоматически. Эта связываемая 
с именем Гильберта программа в полной мере не удалась: австрийский мате

 Предисловие

матик Курт Гедель показал, что всякая достаточно богатая формальная система 
(например, аксиоматическая арифметика) не полна, т. е. в ней найдутся содержательно истинные утверждения, недоказуемые в системе. Пессимист угрюмо 
заметил бы: «Я же говорил вам, что из этой затеи Гильберта ничего хорошего 
не выйдет. Пойду наколю себе дров. Хотя я хорошо знаю заранее, что из этой 
моей затеи тоже ничего не выйдет». Оптимист скажет другое: «Мы надеялись 
на чудо. Его не произошло. Всевышний не дает нам того, чего мы очень хотим. 
Зато мы узнали много интересного, нам открылись огромные просторы для 
деятельности. О, сколько задач у нас впереди! За дело, коллеги!»
Аксиоматическая арифметика не полна. Тем не менее интерес к математической логике не убывает, исследования формально-логических систем 
продолжаются. Успешно описываются довольно большие фрагменты математических дисциплин. Использование алгебраического языка при проектировании узлов компьютера общеизвестно. В последнее время аппарат 
математической логики стал широко применяться в современных системах 
представления знаний.
Самое удивительное применение математическая логика нашла в вычислительной математике: формализм логического вывода в логике предикатов 
первого порядка был взят за основу при построении универсального языка 
программирования Пролог (акроним от PROgramming in LOGic). С появлением 
Пролог-подобных языков программирования математическая логика, которая 
совсем недавно была логикой сугубо теоретической, стала логикой вычисляющей. Классическая гильбертова логика доказательств истинных формул логики предикатов первого порядка для этой практической цели оказалась неподходящей. В 1965 г. Дж. А. Робинсон в качестве формализма, удобного для 
исполнения на компьютере, предложил использовать разработанный им метод резолюций. Замечательное открытие Робинсона оказалось необычайно 
плодотворным и уже в 70-х годах привело к построению универсального языка 
программирования Пролог и трансляторов для него. Это списковый язык для 
теоретико-множественных вычислений. Иногда его называют языком искусственного интеллекта. Задуманный как универсальный язык программирования для перевода с одного естественного языка на другой, Пролог оказался 
удобным инструментом при построении вычислительных моделей, возникающих при решении задач на графах, проектировании конечных автоматов, построении баз данных, баз знаний, экспертных систем, в задачах лингвистики 
при работе с естественными и искусственными языками (причем в числе последних могут выступать и языки программирования), в символьных преобразованиях, теории игр, системах представления знаний и т. д. 
Несколько необычным в Прологе может показаться отсутствие привычного 
в традиционных языках программирования оператора присваивания. Вместо 
него в Прологе реализован более общий алгоритм унификации, построенный 
на основе операции сравнения с образцом. Необычен в Прологе также и отсутствующий в традиционных языках бэктрекинг, позволяющий обходить де

Предисловие  11

рево вывода и собирать все возможные решения задачи. Реализация рекурсии 
в Прологе практически не отличается от общепринятой. В остальном Пролог 
довольно удобен, особенно в задачах, где основными обрабатываемыми объектами являются символ и список символов (множество).
Существует несколько версий трансляторов с Пролога: MicroProlog, DECSystem/Prolog, C-Prolog, IC-Prolog, M-Prolog, Sigma-Prolog, Chalcedony-Prolog, 
FF-Prolog, UNSW/Prolog, Prolog-6, Prolog-1 и Prolog-2 фирмы Expert Systems 
International, Quintus-Pro log, Turbo-Prolog, Arity-Prolog, SWI-Prolog, VisualProlog и другие. При написании программ мы ориентировались на версию 
языка SWI-Prolog (http://www.swi-prolog.org/).
Другое интересное направление применения математической логики есть 
разработка языков формальных спецификаций преобразований в алгебраических объектах и в анализе работы компьютерных программ.
Современный арсенал языков и инструментов, использующихся в данной 
области, известен как формальные методы разработки программ. Классическими методами и нотациями здесь являются VDM и Z. Если говорить о формальных моделях, то наиболее популярными являются Alloy, B и TLA. Среди 
средств моделирования и анализа программ на обычных языках программирования лидерами являются Isabelle (http://isabelle.in.tum.de/) и Frama-C (http://
frama-c.com/jessie.html).
Для спецификаций преобразований в аксиоматически заданных алгебраических объектах, таких как полугруппы, группы, кольца, поля, линейные пространства и т. д., разработан функциональный язык программирования OBJ3. 
Сравнивая, например, OBJ3-программу для вычислений в полях, можно увидеть, что OBJ3-программа есть запись аксиом поля в терминах языка OBJ3. Вычисление преобразований в поле осуществляется в соответствии с аксиомами 
поля. OBJ3-программа моделирует эти преобразования. Иногда OBJ3 называют аксиоматическим языком программирования. Аксиоматический подход 
в языках программирования значительно облегчает задачу верификации программ. Предложенные в аксиоматических языках программирования подходы 
могут использоваться при создании других языков. Например, развитая в OBJ3 
модульная система программ внедрена в языках программирования Ada, ML, 
C++, LOTOS (Language Of Temporal Oredering Specification). Параметризация из 
OBJ3 имплементирована в C#. Для решения аналогичных задач алгебраических спецификаций можно использовать родственный к OBJ3 язык программирования CafeOBJ из семейства OBJ (https://cafeobj.org/).
Книга написана по материалам лекций авторов по дисциплинам «Дискретная математика» и «Математическая логика и теория алгоритмов», читаемых 
на факультете бизнес-информатики, на факультете компьютерных наук Национального исследовательского университета Высшая школа экономики и на 
факультете автоматики и вычислительной техники Национального исследовательского университета Московский энергетический институт. Эти курсы (или 
им аналогичные) начинали в МЭИ Д. А. Поспелов, В. Н. Вагин, В. П. Кутепов, 

 Предисловие

А. А. Болотов, А. Б. Фролов, Е. А. Щегольков, повлиявшие на выбор и характер 
излагаемого авторами материала.
Настоящая книга является второй в серии задуманных авторским коллективом книг по дискретной математике. Она предназначается студентам бакалавриата, изучающим академический курс «Дискретная математика».
В предлагаемой книге авторы сосредоточились на изложении основ математической логики и связанных с ней формальных языков, представимых конечными автоматами.
Основные теоретические и практические положения, изложение и анализ 
практических алгоритмов, иллюстрируемых большим числом примеров, позволят сформировать прочную теоретическую базу, необходимую для дальнейшей работы практикующих программистов и ИТ-специалистов.
В приложении предлагаются задачи, которые могут быть использованы как 
для проведения практических занятий, так и для самостоятельной работы.
Авторы выражают глубокую благодарность рецензентам Калягину В. А., 
Петренко А. К. и научному редактору книги Захарову В. А. за замечания, позволяющие существенно улучшить качество книги. Мы также благодарны преподавателям департамента программной инженерии НИУ ВШЭ Ахметсафиной Р. З., Бересневой Е. Н., Горденко М. К., Гринкругу Е. М., Дворянскому Л. В., 
Дегтяреву К. Ю., Каленковой А. А., Ломазовой И. А., Подбельскому В. В., Шилову В. В., а также Амосову А. А., Вагину В. Н., Дубинскому Ю. А., Куликовой Н. Л., 
Фролову А. Б. из НИУ МЭИ за стимулирующие беседы. Авторы благодарят студентов Сапожкова Е. Д., Тимофееву Е. Э., Чичилеву Н. И. за активное участие 
в составлении и апробации задач и упражнений приложения. Авторы благодарны также корректору Синяевой Г. И. за внимательное прочтение рукописи 
и устранение ошибок.

Введение

1. Множество

Понятие множества неопределимо. Это простейшее исходное понятие человечество сформировало из опыта всего своего исторического развития. То же 
можно сказать о смысле простейшего отношения принадлежности: элемент 
а принадлежит множеству А (обозначение а ∈ А) – и о смысле отношения тождества (совпадения, равенства) двух элементов а и b из некоторого множества 
(обозначение а = b). Другими словами, предполагается, что читатель умеет распознавать совпадение или несовпадение двух элементов и устанавливать факт 
принадлежности или непринадлежности элемента множеству.
Пусть U есть некоторое множество. A есть подмножество множества U, если 
всякий элемент из множества A принадлежит множеству U. Множество U универсально (универсум), если все рассматриваемые множества есть подмножества множества U.
Пусть А, В, С есть произвольные подмножества множества U; а, b, с есть элементы множества U. Обозначим символом ∅ пустое множество, то есть множество без элементов.
Основными неопределяемыми отношениями в теории множеств являются 
следующие отношения:
 
 а = b, элементы а и b равны (совпадают);
 
 а ∈ А, элемент а принадлежит множеству А.
Пусть знак ↔ означает «если и только если»; а знаки &, Ú, ¬, →, ∀, $ есть логические знаки конъюнкции, дизъюнкции, отрицания, импликации, квантора 
общности и квантора существования. Используем их в общепринятом содержательном смысле. Знак $! означает квантор существования единственного 
элемента.
Обозначим через а ∉ А отношение «элемент а не принадлежит множеству А» 
и через a ≠ b отношение «элементы а и b не равны (не совпадают)».
Введем далее следующие отношения.
 
 A ⊆ B ↔ ∀a (a ∈ A → a ∈ B), отношение включения множеств, при этом 
множество A называется подмножеством множества B, а множество B 
называется надмножеством множества A;
 
 A ⊇ B ↔ B ⊆ A;
 
 A = B ↔ A ⊆ B & A ⊇ B, отношение равенства множеств;
 
 A ⊂ B ↔ A ⊆ B & A ≠ B, отношение строгого включения множеств;
 
 A ⊃ B ↔ B ⊂ A.
Обозначим через Р(A) (или 2A) множество всех подмножеств множества А. 
Введем следующие операции над множествами.

 Введение

 
 A ∪ B = {x ∈ U : x ∈ A Ú x ∈ B}, объединение множеств А и В;
 
 A ∩ B = {x ∈ U : x ∈ A & x ∈ B}, пересечение множеств А и В;
 
 A – B = {x ∈ U : x ∈ A & x ∉ B}, разность множеств А и В;
  A
_
 = U – A, дополнение ко множеству A;
 
 A ÷ B = (A ∪ B) – (A ∩ B), симметрическая разность множеств А и В;
 
 A × B = {(a, b) : a ∈ A & b ∈ B}, декартово произведение множеств А и В.
Под натуральным числом понимаем количество элементов конечного множества. Количество элементов пустого множества есть 0.
Распространим декартово произведение на несколько сомножителей: 

А1 × А2 × … × Ап = {(а1, а2, …, аn) : a1 ∈ A1 , a2 ∈ A2, …, ап ∈ Аn}.

Определим декартову степень множества:

Ап = А × А × … × А (п раз), A0 = ∅.

Множества ∅ и А называются несобственными (тривиальными) подмножествами множества А. Если А ⊂ В & А ≠ ∅, то А есть собственное подмножество множества В.
Иногда пишут А · В или АВ вместо А ∩ В.
Примем следующие обозначения.
Множество натуральных чисел ℕ = {0, 1, 2, …}.
Множество положительных натуральных чисел ℕ+ = {1, 2, …}.
Множество целых чисел ℤ = {…, –2, –1, 0, 1, 2, …}.
Множество ℤn = Еn = {0, 1, 2, …, п – 1}.

Множество рациональных чисел ℚ = {
 : m ∈ ℤ, n ∈ ℕ+}.

Множество вещественных чисел ℝ = (–∞, +∞).
Множество неотрицательных вещественных чисел ℝ+ = [0, +∞).
Множество комплексных чисел ℂ = {x + i y : x ∈ ℝ, y ∈ ℝ}, здесь i2 = –1.

2. Функция

Определение. Пусть А и В есть два множества. Функция f: А → В есть отображение, которое каждому элементу х из A ставит в соответствие некоторый элемент у из В. Это обстоятельство записывается как у = f(x).
Замечание. В этом определении функция f всюду определена. Частично 
определенная функция f : A → B есть отображение, которое каждому элементу 
из множества А сопоставляет не более одного элемента из множества В. Всюду определенная функция является частным случаем частично определенной 
функции.
Если f(a) = b, то элемент b есть образ элемента а, элемент а есть прообраз элемента b. Область определения функции f есть множество D(f) = {a ∈ A : $ b ∈ B 
(f(a) = b)}. Область значений функции f есть множество R(f) = {b∈B : $a ∈ A 
(f(a) = b)}.

Функция  15

Иногда множество R(f) обозначают как Im(f) или f(A). Полный прообраз элемента b ∈ B есть множество f–1(b) = {a ∈ A : f(a) = b}. Полный прообраз множества 
С ⊆ В есть множество f–1(C) = {a ∈ A : f(a) ∈ C}.
Сужение функции f, заданной на множестве A, на подмножество S множества A есть функция g – такая, что ↔ a ∈ S (g(a) = f(a)).
Расширение функции f, заданной на множестве A, на надмножество T множества A есть функция h – такая, что ↔ a ∈ A (h(a) = f(a)).
Функцию с конечной областью определения удобно задавать таблицей. На
пример, пусть множества А = {1, 2, 3, 4}, В = {1, 2, 3, 4, 5}, функция f = 

 
Здесь f(1) = 3, f(2) не определено, f(3) = 1, f(4) = 2. Порядок столбцов несуществен.
Область определения D(f) = {1, 3, 4}, область значений R(f) = Im(f)= f(A) = {1, 2, 3}.
Определение. Функция ϕ: A → B есть взаимно-однозначное отображение 
(1-1-отображение) между множествами А и В, если
1) ∀b∈ B $a ∈ A (f(a)=b), 
2) ∀a ∈ A ∀b ∈ A (a ≠ b → f(a) ≠ f(b)).
Замечание. Последнее условие можно заменить на условие
2′) ∀a ∈ A ∀b ∈ A (f(a) = f(b) → a = b).
Функции f: A → B и g: C → D равны, если А = С, В = D, ∀x ∈ A (f(x) = g(x)).
Функция IA: A → A, для которой ∀x ∈ A (I(x) = x), называется тождественной 
функцией.
Функция f: A → B есть отображение в (инъективная функция, или инъекция), 
если ∀a ∈ A ∀b ∈ A условие a ≠ b влечет f(a) ≠ f(b).
Инъективная функция различные элементы из области определения переводит в различные элементы из области значений.
Функция f : A → B есть отображение на (сюръективная функция, или сюръекция), если область значений B совпадает с образом f(A), то есть если f(A) = B.
Функция f : A → B есть взаимно-однозначная функция (или биекция), если f 
является отображением в и отображением на, то есть является одновременно 
инъективной и сюръективной функцией: 1) a ≠ b → f(a) ≠ f(b), 2) Im(f) = B.
Определение. Композиция g ◦ f функций f: A → B и g: B → С есть функция  
g ◦ f : A → C , для которой ∀x ∈ A ((g ◦ f)(x) = g(f(x))).
Замечание. Символ композиции ◦ иногда опускается.
Утверждение. (h ◦ g) ◦ f = h ◦ (g ◦ f).
Доказательство. Пусть f : A → B, g : B → C, h : C → D. Тогда ((h ◦ g) ◦ f)(x) =  
(hg)f(x) = (h ◦ g)f(x)) = h(g(f(x))) = h((g ◦ f)(x)) = (h ◦ (g ◦ f))(x).
Замечание. Для тождественной функции f ◦ IA = IB ◦ f = f.
Определение. Функция f–1: B → A называется обратной к функции f: A → B, 
если f ◦ f–1 = IB и f–1 ◦ f = IA.
Замечание. 1. g обратна к f ↔ f обратна к g.
2. Функция f: A → B имеет обратную функцию, ↔ функция f есть взаимнооднозначное отображение.

 Введение

Утверждение. Если обратная функция для функции f существует, то она 
единственна.
Доказательство. Пусть функции f –1 и g обратны к функции f : A → B. Тогда  
f –1 ◦ IB = f –1 ◦ (f ◦ g) = (f –1 ◦ f ) ◦ g = IA ◦ g = g.
Следствие. Пусть для функций f и g существуют обратные функции f –1 и g–1. 
Тогда справедливы утверждения:
1. (f –1)–1 = f.
2. (f ◦ g)–1 = g–1 ◦ f –1.
Доказательство. 1. Так как f –1 обратна к f, то f обратна к f –1, то есть f = (f –1)–1.
2. (f ◦ g) ◦ (g–1 ◦ f –1) = f ◦ (g ◦ g–1) ◦ f –1 = f ◦ IB ◦ f –1 = f ◦ f –1 = IB.
Аналогично (g–1 ◦ f–1) ◦ (f ◦ g) = IB. Тогда функция g–1 ◦ f –1 обратна к f ◦ g, то есть 
(f ◦ g)–1 = g–1 ◦ f –1.
Теорема. Функция f : A → B имеет обратную функцию тогда и только тогда, 
когда отображение f взаимно-однозначно.
Доказательство. Пусть функция f имеет обратную функцию f –1. Покажем, 
что отображение f взаимно-однозначно, то есть что a ≠ b → f(a) ≠ f(b) и B = Im(f). 
В самом деле, пусть f(a) = f(b). Тогда a = IA(a) = f –1(f(a)) = f –1(f(b)) = IA(b) = b, то есть 
f(a) = f(b) → a = b, откуда a ≠ b → f(a) ≠ f(b).
Пусть b ∈ B. Тогда b = IB(b) = (f ◦ f –1)(b) = f(f –1(b)), то есть всякий b есть образ 
некоторого a = f –1(b) ∈ A. Поэтому B = Im(f).
Пусть теперь f есть взаимно-однозначное отображение. Покажем, что функция f имеет обратную функцию. В самом деле, так как B = Im(f), то каждый элемент b из B есть образ в точности одного элемента a из A: f(a) = b. Пусть g(b) = a. 
Для соответствия g : B → A имеем:

(g ◦ f)(a) = g(f(a)) = g(b) = a = IA, 
(f ◦ g)(b) = f(g(b)) = f(a) = b = IB.

Следовательно, g есть обратная функция для f. Теорема доказана.

3. Унарная функция

Напомним, что функция f : A → B есть правило (отображение), которое каждому элементу из множества A сопоставляет единственный элемент из множества B. Если f(a) = b, то элемент b есть образ элемента a, элемент a есть прообраз 
элемента b. Множество A есть область определения D(f) функции f. Множество 
B есть область значений V(f) функции f.
Образ Im f = {f(x) : x ∈ A} отображения f : A → B есть множество f(A) всех 
значений функции f. Полный прообраз элемента y ∈ B есть множество f –1(y) =  
{x ∈ A : f(x) = y}. Полный прообраз множества C ⊆ B есть множество f–1(C) =  
{x ∈ A : f(x) ∈ C}.
На конечном множестве функцию удобно задавать таблицей. Например, 

пусть множества A = {1, 2, 3, 4},  B = {1, 2, 3, 4, 5}, функция f = 

 
Здесь