Дискретная математика: модулярная алгебра, криптография, кодирование

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

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

Москва, 2017

УДК 519.7
ББК 22.176 

А18

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

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

Авдошин С. М., Набебин А. А.
А18 
Дискретная математика. Модулярная алгебра, криптография, кодирова-
ние. – М.: ДМК Пресс, 2017. – 352 с.: ил. 

ISBN 978-5-94074-408-3

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

УДК 519.7
ББК 22.176 

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

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

Содержание

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

Введение.......................................................................13
1. Множество .................................................................................................................................13
2. Функция .....................................................................................................................................14
3. Отношение .................................................................................................................................16
4. Отношение эквивалентности ..............................................................................................17
5. Каноническое разложение функции .................................................................................18
6. Мощность множества. Счетные и несчетные множества ..........................................19
7. Мощность континуума ..........................................................................................................20
8. Кардинальные числа. Сравнение мощностей ................................................................21

Часть.I..МОДУЛЯРНАЯ.АЛГЕБРА.........................................25

Глава.1..Делимость..........................................................26
1.1. Позиционная система счисления ...................................................................................26
1.2. Простые числа .......................................................................................................................28
1.3. Факторизация целых чисел ..............................................................................................29
1.4. Наибольший общий делитель ..........................................................................................30
1.4.1. Алгоритм Евклида вычисления наибольшего общего делителя .................31
1.4.2. Расширенный алгоритм Евклида вычисления наибольшего общего  
делителя .....................................................................................................................................34
1.5. Наименьшее общее кратное ..............................................................................................35
1.6. Непрерывные (цепные) и подходящие дроби ............................................................37
1.6.1. Вычисление подходящих дробей............................................................................38
1.6.2. Алгоритм вычисления подходящих дробей .......................................................39

Глава.2..Функции.Мебиуса.и.Эйлера...................................41
2.1. Функции x, |x|, {x} для вещественного x ....................................................................41
2.2. Мультипликативные функции ........................................................................................42
2.3. Функция и формула обращения Мебиуса ..................................................................43
2.4. Функция Эйлера ..................................................................................................................47

Глава.3..Сравнения..........................................................49
3.1. Сравнение целых чисел ......................................................................................................49
3.2. Свойства сравнений ............................................................................................................49
3.3. Полная система вычетов ....................................................................................................51

 Содержание

Операции над классами ........................................................................................................51
3.4. Приведенная система вычетов .........................................................................................53
3.5. Теоремы Эйлера и Ферма ..................................................................................................54
3.6. Классы целых чисел по модулю m, взаимно простых с модулем m....................54
3.7. Модулярные арифметические операции .....................................................................55
3.7.1. Алгоритм вычисления мультипликативно обратного элемента  
a–1 (mod n) в n .........................................................................................................................56
3.7.2. Алгоритм вычисления модулярной степени в n .............................................56
3.7.3. Алгоритм вычисления генератора мультипликативной циклической 
группы 
 при простом p (перебор) ..................................................................................57

Глава.4..Сравнения.с.одной.переменной..............................58
4.1. Решение сравнения с переменными ..............................................................................58
4.2. Сравнения первой степени ...............................................................................................60
4.3. Система сравнений первой степени ...............................................................................61
4.3.1. Попарно взаимно простые модули ........................................................................61
4.3.2. Алгоритм Гаусса для системы сравнений x ≡ c1 (mod m1), ...,  
x ≡ ck (mod mk) с попарно взаимно простыми модулями ............................................62
4.3.3. Произвольные модули ...............................................................................................63
4.4. Сравнения любой степени с простым модулем .........................................................64
4.5. Сравнения произвольной степени по составному модулю ...................................65
Алгоритм решения сравнения f(x) ≡ 0(mod pa) ............................................................68

Глава.5..Сравнения.второй.степени....................................69
5.1. Квадратичные вычеты по простому модулю ..............................................................69
5.2. Символ Лежандра ................................................................................................................70
5.3. Символ Якоби........................................................................................................................74
Алгоритм вычисления символа Якоби (и символа Лежандра)  
JACOBI(a, n) .............................................................................................................................76
5.4. Квадратичные вычеты по составному модулю ..........................................................77

Глава.6..Примитивные.корни.и.индексы...............................80
6.1. Экспонента, примитивные корни, индексы ................................................................80
6.1.1. Число классов вычетов данной экспоненты .......................................................82
6.1.2. Индексы (дискретные логарифмы) .......................................................................83
6.2. Примитивные корни по модулям p α и 2p α ..................................................................83
6.3. Вычисление примитивных корней по модулям pα и 2pα ........................................87
6.4. Индексы по модулям pα и 2pα ..........................................................................................88
6.5. Индексы и вычеты ...............................................................................................................88
6.6. Индексы по модулю 2α ........................................................................................................89
6.7. Индексы по любому составному модулю ....................................................................91

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

Глава.7..Универсальные.алгебры........................................93
7.1. Алгебры, подалгебры, гомоморфизм алгебр ...............................................................93
7.2. Конгруэнции ..........................................................................................................................96

Глава.8..Абстрактная.алгебра............................................99
8.1. Полугруппы ............................................................................................................................99
8.2. Циклические полугруппы .............................................................................................. 101
8.3. Группы ................................................................................................................................... 103
8.3.1. Циклические группы ............................................................................................... 107
8.3.2. Смежные классы. Разложение группы по подгруппе .................................. 107
8.3.3. Конечные группы и теорема Лагранжа ............................................................. 109
8.3.4. Конечные циклические группы ........................................................................... 109
8.3.5. Алгоритм вычисления всех подгрупп конечной циклической  
группы ...................................................................................................................................... 111
8.4. Нормальные подгруппы, фактор-группы, теорема о гомоморфизме  
групп .............................................................................................................................................. 111
8.5. Кольцо ................................................................................................................................... 114
8.6. Поле ........................................................................................................................................ 117
8.7. Полиномиальные кольца ................................................................................................ 120
8.8. Идеал кольца ....................................................................................................................... 121
8.8.1. Главный идеал ............................................................................................................ 122
8.8.2. Разностное кольцо (кольцо классов вычетов). Сравнения ........................ 122
8.9. Линейное векторное пространство ............................................................................. 124
8.10. Булева алгебра ................................................................................................................. 126
8.11. Решетка ............................................................................................................................... 126

Глава.9..Конечные.поля..................................................128
9.1. Представленние конечного поля множеством классов вычетов  
по модулю неприводимого полинома ................................................................................ 128
9.2. Поле разложения полинома 
 ............................................................................. 130
9.3. Цикличность мультипликативной группы поля .................................................... 130
9.4. Задание поля корнем неприводимого полинома ................................................... 131
9.5. Строение конечных полей .............................................................................................. 133
9.5.1. Минимальный полином ......................................................................................... 136
9.5.2. Вычисление минимального полинома .............................................................. 137
9.5.3. Подполя конечного поля ........................................................................................ 139
9.5.4. Круговые полиномы ................................................................................................. 142
9.5.5. Алгоритм факторизации полинома 
 – 1 на круговые  
полиномы из GF(q) ............................................................................................................. 144
9.6. Изоморфизм полей Галуа ............................................................................................... 145
9.7. Автоморфизмы поля Галуа ............................................................................................ 146

 Содержание

9.8. Основные алгоритмы для конечных полей .............................................................. 147
9.8.1. Алгоритм Евклида для полиномов из p[x] ..................................................... 149
9.8.2. Расширенный алгоритм Евклида для полиномов из p[x] ......................... 150
9.8.3. Мультипликативный обратный элемент в 
................................................. 153
9.8.4. Модулярная степень в 
 ....................................................................................... 153
9.8.5. Тестирование полинома из p[x] на неприводимость .................................. 153
9.8.6. Порождение случайного неприводимого полинома над p........................ 153
9.8.7. Тестирование неприводимого полинома на примитивность ..................... 154
9.8.8. Порождение случайного нормированного примитивного полинома  
над p ........................................................................................................................................ 154
9.8.9. Вычисление порядка элемента конечной группы (метод Гаусса) ........... 154
9.8.10. Вычисление генератора конечной циклической группы  
(метод Гаусса) ........................................................................................................................ 154

Часть.II..КРИПТОГРАФИЯ.................................................156

Глава.10..Модулярная.алгебра.в.криптографии...................157
10.1. Криптография и ее цели ............................................................................................... 157
10.1.1. Хэш-функция ........................................................................................................... 160
10.1.2. Алгоритм MASH-1 ................................................................................................. 161
10.2. Проблема факторизации целых чисел ..................................................................... 162
10.2.1. ρ-алгоритм Полларда факторизации целых чисел ..................................... 162
10.2.2. (p – 1)-алгоритм Полларда факторизации целых чисел .......................... 163
10.2.3. Алгоритм квадрат-решета факторизации целых чисел ............................. 164
10.3. Проблема RSA .................................................................................................................. 165
10.4. Проблема квадратичного вычета ............................................................................... 166
10.4.1. Алгоритм вычисления дискретного квадратного корня  
по простому модулю p ........................................................................................................ 166
10.4.2. Алгоритм вычисления дискретного квадратного корня  
по простому модулю p, где p ≡ 3 (mod 4) ...................................................................... 167
10.4.3. Алгоритм вычисления дискретного квадратного корня  
по простому модулю p, где p ≡ 5 (mod 8) ...................................................................... 167
10.4.4. Алгоритм вычисления дискретного квадратного корня  
по простому модулю p при большом s .......................................................................... 167
10.4.5. Алгоритм вычисления дискретного квадратного корня  
по модулю n = p·q, где p и q есть простые числа ........................................................ 167
10.5. Проблема дискретного логарифма ........................................................................... 168
10.5.1. Алгоритм «малый шаг – большой шаг» вычисления дискретного  
логарифма ............................................................................................................................... 168
10.5.2. ρ-алгоритм Полларда вычисления дискретного логарифма ................... 169
10.5.3. Алгоритм Полига-Хеллмана вычисления дискретного логарифма ..... 171

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

10.6. Проблема подмножества суммы ................................................................................ 172
10.6.1. Наивный (переборный) алгоритм решения проблемы суммы ............... 172
10.6.2. Алгоритм «встреча посередине» решения проблемы  
подмножества суммы .......................................................................................................... 172
10.7. Проблема факторизации полиномов над конечным полем ............................. 173
10.7.1. Бесквадратная факторизация ............................................................................. 173
10.7.2. Q-матричный алгоритм Берлекампа ............................................................... 174
10.8. Криптосистема RSA ....................................................................................................... 175
10.8.1. Шифросистема RSA .............................................................................................. 175
10.8.2. Электронная цифровая подпись RSA с использованием  
хэш-функции ......................................................................................................................... 177
10.8.3. Электронная цифровая подпись RSA с извлечением сообщения ......... 179
10.9. Криптосистема Эль-Гамаля ......................................................................................... 180
10.9.1. Шифросистема Эль-Гамаля над числовым полем Галуа GF(p) ............. 180
10.9.2. Электронная цифровая подпись Эль-Гамаля над числовым полем  
Галуа GF(p) ............................................................................................................................ 182
10.9.3. Шифросистема Эль-Гамаля над полиномиальным полем Галуа  
GF(pm) ...................................................................................................................................... 184
10.9.4. Электронная цифровая подпись Эль-Гамаля над полиномиальным  
полем Галуа GF(pm) ............................................................................................................. 187
10.10. Электронная цифровая подпись DSA ................................................................... 189
10.11. Криптографическая система Рабина ..................................................................... 192
10.11.1. Шифросистема Рабина....................................................................................... 192
10.11.2. Электронная цифровая подпись Рабина с извлечением  
сообщения ............................................................................................................................... 194
10.11.3. Модифицированная цифровая подпись Рабина с извлечением  
сообщения ............................................................................................................................... 195
10.12. Рюкзачная схема шифрования Меркле–Хеллмана .......................................... 198
10.13. Рюкзачная схема шифрования Хора–Ривеста ................................................... 199
10.14. Вероятностные схемы шифрования с открытым ключом .............................. 203
10.14.1. Вероятностная схема шифрования Голдвассер–Микали ...................... 204
10.14.2. Вероятностная схема шифрования Блюма–Голдвассер ......................... 206
10.15. Электронная цифровая подпись Фейге–Фиат–Шамира .............................. 208
10.16. Электронная цифровая подпись GQ ..................................................................... 210
10.17. Электронная цифровая подпись Шнорра с хэш-функцией .......................... 211
10.18. Электронная цифровая подпись Ниберга–Рюппеля с извлечением  
сообщения .................................................................................................................................... 213

Глава.11..Криптография.на.эллиптических.кривых..
над.конечными.полями...................................................215
11.1. Эллиптические кривые ................................................................................................. 215

 Содержание

11.2. Эллиптические кривые над полем вещественных чисел .................................. 216
11.3. Эллиптические кривые в конечных полях ............................................................. 218
11.4. Сложение точек эллиптический кривой E(F) y2 = x3 + ax + b  
над полем F характеристики char(F) > 3 .......................................................................... 219
11.5. Сложение точек эллиптической кривой E(F) y2 = x3 + ax2 + bx +  
c над полем F характеристики char(F) = 3 ....................................................................... 220
11.6. Сложение точек суперсингулярной эллиптической кривой E(F)  
y2 + cy = x3 + ax + b над полем F характеристики char(F) = 2 .................................... 222
11.7. Сложение точек несуперсингулярной эллиптической кривой E(F)  
y2 + xy = x3 + ax2 + b над полем F характеристики char(F) = 2 .................................. 224
11.8. Вычисление k · P ............................................................................................................... 226
11.9. Порядок группы точек эллиптической кривой .................................................... 226
11.9.1. Алгоритм вычисления порядка элемента группы точек  
эллиптической кривой (метод Гаусса) ......................................................................... 228
11.9.2. Алгоритм вычисления генератора циклической группы точек  
эллиптической кривой (метод Гаусса) ......................................................................... 228
11.10. Криптосистемы на эллиптических кривых над числовым конечным  
полем ............................................................................................................................................. 229
11.10.1. Шифросистема Эль-Гамаля на эллиптических кривых  
над числовым конечным полем ....................................................................................... 229
11.10.2. Электронная цифровая подпись (ЭЦП) Эль-Гамаля  
на эллиптических кривых над числовым конечным полем .................................. 232

Глава.12..Шифросистема.NTRU.на.конечных..
полиномиальных.кольцах...............................................235
12.1. Проблема кратчайшего вектора в целочисленной решетке ............................. 235
12.2. Шифросистема NTRU .................................................................................................. 236

Глава.13..Блоковые.и.потоковые.шифры............................241
13.1. Блоковый шифр RC5-S ................................................................................................. 241
13.2. Потоковые шифры .......................................................................................................... 245
13.2.1. Линейный регистр сдвига с обратной связью............................................... 245
13.2.2. Расшифровка линейного регистра сдвига ..................................................... 247

Часть.III..КОДИРОВАНИЕ.................................................250

Глава.14..Линейные.коды................................................251
14.1. Линейные пространства над полями Галуа ............................................................ 251
14.2. Расстояние Хэмминга .................................................................................................... 252
14.3. Порождающая и проверочная матрицы .................................................................. 253
14.4. Декодирование в ближайшее кодовое слово ......................................................... 255

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

14.5. Расстояние и корректирующая способность кода ............................................... 256
14.6. Каноническая форма базисных матриц систематического кода .................... 256
14.6.1. Каноническая проверочная матрица ............................................................... 256
14.6.2. Каноническая кодирующая матрица ............................................................... 257
14.6.3. Алгоритм систематизации несистематического линейного  
кода ............................................................................................................................................ 260
14.7. Декодирование линейного кода (декодер)............................................................. 261
14.8. Бинарный код Хэмминга .............................................................................................. 263

Глава.15..Циклические.коды............................................266
15.1. Порождающая и проверочная матрицы циклического кода ........................... 266
15.2. Канонические порождающая и проверочная матрицы  
циклического кода .................................................................................................................... 268
15.3. Систематический кодер циклического кода .......................................................... 270

Глава.16..Коды.Боуза–Чоудхури–Хоквингема..
(коды.БЧХ)...................................................................271
16.1. Построение кодов БЧХ ................................................................................................. 271
16.2. Декодер Питерсона–Горенстейна–Цирлера ......................................................... 276
16.3. Алгоритм Питерсона–Горенстейна–Цирлера БЧХ-кода  
с исправлением t и менее ошибок ....................................................................................... 281

Глава.17..Коды.сжатия.информации.................................298
17.1. Алфавитное кодирование ............................................................................................. 298
17.2. Кодирование с минимальной избыточностью ...................................................... 299
17.3. Алгоритм Фано построения разделимой префиксной схемы  
алфавитного кодирования, близкого к оптимальному ................................................ 300
17.4. Оптимальное кодирование .......................................................................................... 301
17.5. Алгоритм Хаффмана оптимальной разделимой префиксной схемы  
алфавитного кодирования ..................................................................................................... 303
17.6. Кодер и декодер Прюфера для деревьев ................................................................. 309

Глава.18..Основы.теории.информации..............................311
18.1. Количество информации и энтропия ...................................................................... 311
18.1.1. Равновероятность знаков алфавита ................................................................. 311
18.1.2. Разновероятность знаков алфавита. Формулы Шеннона  ....................... 313
18.2. Свойства энтропии ......................................................................................................... 313
18.3. Энтропия при непрерывном сообщении ................................................................ 316
18.4. Условная энтропия ......................................................................................................... 319
18.5. Взаимная энтропия ........................................................................................................ 326

 Содержание

Приложения.................................................................327
1. Множества, функции, отношения .................................................................................. 327
2. Модулярная алгебра ............................................................................................................ 334
3. Криптография ........................................................................................................................ 341
4. Кодирование ........................................................................................................................... 342
5. Информация и энтропия.................................................................................................... 345

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

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

Предисловие

Дискретная математика является фундаментом для всего компьютинга, включая 
программную инженерию. Она столь же важна для компьютерных дисциплин, как 
и математический анализ для остальных инженерных специальностей.
Дискретная математика есть область науки, посвященная изучению дискретных 
объектов и структур. В широком смысле она включает в себя: теорию множеств, 
отношения и функции, теорию чисел, абстрактную алгебру, математическую логику, 
булеву алгебру, логику высказываний, цифровую логику, логику предикатов, 
методы доказательства, комбинаторный анализ, рекуррентные соотношения, теорию 
графов и сетей, основы алгоритмизации, теорию автоматов и формальных 
языков, теорию алгоритмов, вычислимость и вычислительную сложность, дис-
кретную вероятность, целочисленную оптимизацию, криптографию, теорию ин-
формации и кодирования.
Дискретная математика стала важным звеном математического образования 
инженера.
Настоящая книга является первой в серии задуманных авторским коллективом 
книг по дискретной математике. Она предназначается студентам бакалавриата, 
изучающим академический курс «Дискретная математика» для формирования у 
студентов следующих компетенций:
1)  способность к самоорганизации и самообразованию в области дискретных 
математических моделей;
2)  готовность применить аппарат дискретной математики для решения постав-
ленных практических задач;
3)  способность применить соответствующую задаче математическую модель с 
проверкой ее адекватности;
4)  способность провести анализ результатов моделирования для принятия ре-
шений на основе полученных результатов.
В предлагаемой книге авторы сосредоточились на изложении математических 
основ современной теории кодирования и криптографии, доступных для понима-
ния студентов первых лет обучения.
Основные теоретические и практические положения, изложение и анализ прак-
тических алгоритмов, иллюстрируемые большим числом примеров, позволят 
сформировать прочную теоретическую базу, необходимую для дальнейшей рабо-
ты практикующих программистов и ИТ-специалистов. 
В приложении предлагаются задачи, которые могут быть использованы как для 
проведения практических занятий, так и для самостоятельной работы.
Авторы выражают глубокую благодарность рецензентам Калягину В. А., Улья-
нову М. В. и научному редактору книги Захарову В. А. за замечания, позволившие 
существенно улучшить качество книги. Мы также благодарны преподавателям 

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

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

Введение

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}, разность множеств А и В;

 

= 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 есть множество D(f) = {a∈A : $b ∈ B(f(a) = 
= b)}.
Область значений функции f: A → B есть множество R(f) = {b∈B: $a ∈ A(f(a) = b)}.
Образ Im(f) = {f(x): x∈A} функции f: A → B есть множество f(A) всех значений 
функций f.
Заметим, что Imf = R(f) = f(A).

Функция  15

Если f(a) = b, то элемент b есть образ элемента а, а элемент а есть прообраз эле-
мента b.
Полный прообраз элемента 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. Отношение

Пусть А1, А2, …, Аn есть произвольные множества, вообще говоря, разнородные.
Определение. п-арное отношение рn на множествах А1, А2, ..., Ап есть подмно-

жество рn декартова произведения A1 × A2 × … × An.
Замечание. n-арное отношение рп на множестве А есть подмножество рп нату-
ральной степени множества Ап, п > 0. Индекс п-арности (местности) отношения р 
иногда опускается.
Возможна множественная (суффиксная) (х1, …, хп) ∈ ρ и предикатная (префикс-
ная) ρ(x1, ..., хn) формы записи отношений. В последнем случае отношение ρ на-
зывают также предикатом. Для бинарного отношения используется инфиксная 
запись х ρ у. Унарное отношение ρ ⊆ E есть подмножество множества Е. Предикат 
ρ(х), соответствующий унарному отношению, называется свойством.

Отношение эквивалентности  17

Набор а = (а1, a2, …, аn) ∈ ρ (допустима запись ρ(а1, a2, …, аn)) называется элемен-
том отношения.
Определение. Отношение конечно, если оно состоит из конечного числа эле-
ментов.

4. Отношение эквивалентности
Пусть А есть произвольное множество.
Определение. Бинарное  отношение σ ⊆ A × A есть отношение эквивалентности 
(обозначение a ~ b), если оно удовлетворяет следующим аксиомам:
1) а ~ а, рефлексивность;
2) а ~ b → b ~ a, симметричность;
3)  а ~ b & b ~ с → a ~ c,  транзитивность.
Обозначение. a ~  b, σ(a, b), (a, b) ∈ σ, a σ b.
Определение. Разбиение I множества А есть семейство попарно непересекающих-

ся непустых подмножеств множества A, таких, что: А =
 
, ∀i ≠ j (
).
 
Подмножества Ai называются смежными классами разбиения I.
Пример. А = {0, 1, 2, 3, 4, 5} = {0, 1, 5}  {2}  {3, 4}.
Теорема. 1. Каждому отношению эквивалентности, определенному на мно-

жестве А, соответствует некоторое разбиение множества А.
2. Каждому разбиению множества А соответствует некоторое отношение экви-
валентности, определенное на множестве A.
Коротко: между классом всех определенных на множестве A эквивалентностей и 
классом всех разбиений множества А существует взаимно-однозначное соответствие.
Доказательство. 1. Пусть σ есть отношение эквивалентности, определенное на 
множестве А и а ∈ А. Построим множество Ка = {х ∈ А: х ~ а} всех элементов х, 
эквивалентных а. Оно обозначается также через [а]σ. Множества Ка называются 
смежными классами А по σ, или классами эквивалентности.
Заметим, что если b ∈ Ка, то b ~ а. Покажем, что а ~ b ↔ Ка = Кb. В самом деле, 
пусть а ~ b. Пусть произвольный элемент с ∈ Ка. Тогда с ~ а, а ~ b, с ~ b, с ∈ Кb, и по-
тому Ка ⊆ Кb. Аналогично показываем, что Кb ⊆ Ка.  Тогда Ка = Кb.  Пусть теперь  
Ка = Кb. Тогда а ∈ Кb и а ~ b. Утверждение доказано.
Если два класса Ка и Кb имеют общий элемент с, то они совпадают. В самом деле, 
если с ∈ Ка, с ∈ Кb, то b ~ с, с ~ а и b ~ а, откуда Ка = Кb. Поэтому всякие два класса 
эквивалентности либо не пересекаются, либо (в случае непустого пересечения) 
совпадают. Всякий элемент с попадает в класс эквивалентности Кс. Поэтому система 
смежных классов есть разбиение множества А.
2. Пусть задано некоторое разбиение множества А. Определим на А отношение 
~, положив а ~ b ↔ элементы a и b принадлежат одному и тому же классу разбиения. 
Отношение ~ удовлетворяет аксиомам 1) а ~ а, 2) а ~ b → b ~ а, 3) а ~ b & b ~ с, 
и потому оно есть отношение эквивалентности.
Замечание. 1. Разбиение множества А на одноэлементные подмножества 

 и разбиение А, состоящее из одного только множества А, называются 

тривиальными (несобственными) разбиениями.

 Введение

2. Разбиение А на одноэлементные подмножества соответствует отношению 
эквивалентности, которое есть равенство.
3. Разбиение множества А, состоящее из одного только множества А, соответствует 
отношению эквивалентности, содержащему все множество А×А.
4. a σ b ↔ [a]σ = [b]σ.
Определение. Совокупность классов эквивалентности множества А называется 
фактор-множеством А/σ множества А по эквивалентности σ.
Определение. Отображение р: А → А/σ, при котором р(а) = [а]σ, называется 
каноническим (естественным).

5. Каноническое разложение функции

Пусть f: A → B есть некоторая функция. Определим на A отношение σ ∈ A×A, положив ↔ 
a ∈ A ↔ b ∈ A (a ~ b ↔ f(a) = f(b)). Отношение σ есть отношение эквивалентности, 
так как выполняются следующие свойства:
1) a ~ a, ибо f(a) = f(a);
2) a ~ b → b ~ a, ибо f(a) = f(b) → f(b) = f(a);
3) a ~ b & b ~ c → a ~ c, ибо f(a) = f(b) & f(b) = f(c) → f(a) = f(c).
Введенное отношение σ называется ядерной эквивалентностью для отображения 
f. Классы эквивалентности A/σ есть полные прообразы элементов множества 
B при отображении f, то есть Ab = f–1(b).
Отображение f можно разложить в композицию двух отображений, согласно 
следующему рисунку:

Kf(a)
f(a)
q
p
a

Имеет место равенство f = q ◦ p, то есть f(a) = q(p(a)).
Представление f = q ◦ p называется каноническим разложением (представлением) 
функции f.
Пример. Получить каноническое разложение функции

f: E10 → E10, f = 0112105533 = 
.

Область определения D(f) = E10. Область значений Im(f) = {0, 1, 2, 3, 5}. Классы 
эквивалентности:

K0 = [0]σ = f–1(0) = {0, 5}, q(K0) = 0; 
K1 = [1]σ = f–1(1) = {1, 2, 4}, q(K1) = 1; 
K2 = [2]σ = f–1(2) = {3}, q(K2) = 2; 
K3 = [3]σ = f–1(3) = {8, 9}, q(K3) = 3; 
K5 = [5]σ = f–1(5) = {6, 7}, q(K5) = 5.

Функции p и q задаются следующим образом: