Дискретная математика

 
 
 
 
 
 
А. И. Канарейкин 
 
 
 
 
 
 
 
ДИСКРЕТНАЯ МАТЕМАТИКА 
 
 
Учебное пособие 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Москва    Вологда 
«Инфра-Инженерия» 
2024 
1 
 

УДК 51 
ББК 22.144 
К19 
 
 
 
Рецензенты: 
кандидат физико-математических наук, доцент кафедры систем автоматического  
управления Калужского филиала МГТУ им. Н. Э. Баумана Серегина Елена Владимировна; 
кандидат физико-математических наук, доцент кафедры физики и математики  
ФГБОУ ВО «Калужский государственный университет им. К. Э. Циолковского»  
Савоськина Ирина Ивановна 
 
 
 
 
 
 
 
 
 
 
Канарейкин, А. И.  
К19   
Дискретная математика : учебное пособие / А. И. Канарейкин. – Москва ; 
Вологда : Инфра-Инженерия, 2024. – 100 с. : ил., табл.   
ISBN 978-5-9729-1739-6 
 
Изложены основные понятия теории множеств, общие свойства построенных 
на ее базе дискретных алгебраических структур. Рассмотрены конкретные примеры 
структур Галуа (групп, колец и полей), в том числе булевой алгебры, наиболее часто используемые в приложениях дискретной математики (конечной геометрии, теории кодирования, сетей и конечных автоматов). 
Для студентов всех направлений и специальностей по дисциплине «Дискретная 
математика». 
 
 УДК 51 
 ББК 22.144 
 
 
 
 
 
 
ISBN 978-5-9729-1739-6 
” Канарейкин А. И., 2024 
 
” Издательство «Инфра-Инженерия», 2024 
 
” Оформление. Издательство «Инфра-Инженерия», 2024 
2 
 

ʝʒʚʏʑʚʔʜʗʔ 
 
ВВЕДЕНИЕ 
................................................................................................................. 4 
 
РАЗДЕЛ I. МНОЖЕСТВА, ФУНКЦИИ, ОТНОШЕНИЯ 
................................. 6 
Лекция № 1. Множества и операции над ними 
..................................................... 6 
Лекция № 2. Соответствия и функции ................................................................. 13 
Лекция № 3. Отношения и их свойства ............................................................... 18 
Лекция № 4. Основные виды отношений ............................................................ 21 
 
РАЗДЕЛ II. ВВЕДЕНИЕ В ОБЩУЮ АЛГЕБРУ .............................................. 25 
Лекция № 5. Элементы общей алгебры ............................................................... 25 
Лекция № 6. Различные виды алгебраических структур ................................... 29 
 
РАЗДЕЛ III. ВВЕДЕНИЕ В ЛОГИКУ 
................................................................. 35 
Лекция № 7. Элементы математической логики ................................................ 35 
Лекция № 8. Логические функции ....................................................................... 39 
Лекция № 9. Булевы алгебры 
................................................................................ 44 
Лекция № 10. Булевы алгебры и теория множеств ............................................ 50 
Лекция № 11. Полнота и замкнутость 
.................................................................. 54 
Лекция № 12. Язык логики предикатов ............................................................... 60 
Лекция № 13. Комбинаторика 
............................................................................... 65 
 
РАЗДЕЛ IV. ТЕОРИЯ ГРАФОВ 
........................................................................... 71 
Лекция № 14. Графы: основные понятия и операции ........................................ 71 
Лекция № 15. Маршруты, цепи и циклы ............................................................. 78 
Лекция № 16. Некоторые классы графов и их частей ........................................ 84 
 
ПРАКТИЧЕСКИЕ ЗАДАНИЯ ДЛЯ САМОКОНТРОЛЯ ............................... 89 
 
СПИСОК ЛИТЕРАТУРЫ ..................................................................................... 97 
 
3 
 

ʑʑʔʓʔʜʗʔ 
 
Основу классической математики (например, дифференциального и интегрального исчисления) составляют понятия непрерывности и бесконечности 
(Декарт, Ньютон, Лейбниц). Эти понятия определяют основное свойство числовой прямой: множество точек любого отрезка прямой всюду плотно, то есть 
любая окрестность любой точки этой прямой содержит бесконечное несчетное 
множество точек этой прямой. Далее следуют определения предела числовой 
последовательности и функции, непрерывности и дифференцируемости – основных атрибутов классической математики. Альтернативой непрерывности и бесконечности являются представления о дискретном (разъединенном) и конечном. Интуитивно дискретное множество элементов должно быть счетным, то 
есть между элементами дискретного множества и множества натуральных чисел должно существовать взаимнооднозначное соответствие такое, что элементы дискретного множества могут быть пронумерованы. Если существует конечный номер последнего элемента некоторого дискретного множества, то оно 
конечно (содержит конечное число элементов), если такой номер не существует, то множество бесконечное, но счетное. 
Дискретная математика (ДМ) – математика, основанная на понятиях дискретности и конечности. ДМ изучает свойства функциональных отношений, 
определенных на дискретных и конечных множествах. Хотя в ДМ допустим 
предельный переход к счетным бесконечным множествам, многие привычные 
результаты, полученные в классической математике (арифметике, алгебре, геометрии) приобретают в ДМ совершенно иной вид и смысл (операции на множествах чисел, векторов, матриц). 
Соотношение между классической и дискретной математикой такое же, 
как между классической и квантовой механикой в физике: первая описывает 
свойства плотных макроструктур, вторая – микроструктур. Дискретность и конечность являются первичными понятиями в познавательной деятельности человека и характеризуют микроструктуру его мышления. Непрерывность и бесконечность проявляются как результат игнорирования прерывистости реального мира. Например, интеграл в классической математике определяется как предел конечной, но непрерывной интегральной суммы. Исторически процесс познания окружающего мира начинался в представлениях о его дискретности и 
конечности (Зенон, Демокрит, Пифагор, Аристотель). Начиная с эпохи Возрождения (Декарт, Ньютон, Лейбниц), понятие дискретности отступило на второй 
план, а на первое место претендовали непрерывные, декартовы переменные, 
функции и процессы. 
4 
 

Бурный интерес к ДМ обозначился в конце XX века и стимулировался созданием ЭЦВМ, новыми точками зрения и новыми открытиями, среди которых 
на первое место следует поставить выяснение чисто дискретной структуры 
наследственного вещества (Крик, Уотсон), расшифровку генетического кода 
(имеющего дискретную структуру), дискретный характер обмена информацией 
между нейронами головного мозга. Моделирование этих процессов в цифровых системах восприятия, хранения, переработки и использования информации 
в машинах, живых организмах и их объединениях породило целый ряд новых 
научных дисциплин (теория информации, кодирования, кибернетики и т. п.), 
основу изучения которых составляет ДМ. В настоящее время ДМ включает в себя такие мощные инструменты как математическая логика, теория математических структур, графов и сетей, алгоритмов, комбинаторика. Роль и значение ДМ 
в развитии современного естествознания и гуманитарных наук трудно переоценить: большинство качественно новых открытий XXI века связано с адекватным представлением объектов окружающего мира – объектов ДМ. 
Основной упор при этом делается на геометрические представления и ассоциации основных понятий и результатов теоретического анализа. Соответственно, каждое вновь вводимое понятие и получаемый теоретический результат сопровождается примером решения конкретной задачи. По возможности 
с целью более успешного усвоения и запоминания материала основные понятия определения, теоремы и выводы по каждому разделу нумеруются и выделяются относительно основного текста. 
Первая глава пособия посвящена изложению классической теории множеств, основанной на двух так называемых интуитивных принципах Кантора: 
объемности и абстракции. Здесь особое внимание уделяется различию в понятиях отношения принадлежности и включения, часто отождествляемых студентами. В этой же главе подробно рассмотрены специальные виды отношений на дискретных множествах, являющихся основным инструментом анализа 
дискретных алгебраических структур: эквивалентности и порядка. 
Во второй главе пособия рассмотрен ряд примеров алгебраических структур, построенных на конечных множествах и показано их отличие от аналогичных структур на множестве действительных чисел и хорошо знакомым студентам из курса высшей математики. 
Наконец, в заключительной третьей главе первой части пособия рассмотрен классический образец дискретной алгебраической структуры: булевой алгебры и определенных в ней булевых функций. Эта алгебра и функции получили широкое применение в симодической логике и вычислительной технике, особенно при синтезе современных цифровых устройств и систем. 
5 
 

 ʟʏʖʓʔʚ 
 
ʛʜʝʕʔʠʡʑʏǡʣʢʜʙʥʗʗǡʝʡʜʝʧʔʜʗʮ 
 
ཙ ʚˈˍ˙ˋˢ͒ͳǤ ʛːˑˉˈ˔˕˅˃ˋˑ˒ˈ˓˃˙ˋˋː˃ˇːˋˏˋ 
 
1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ МНОЖЕСТВ 
 
Определение. Множеством М называется объединение в единое целое 
определенных различимых однотипных объектов а, которые называются элементами множества. 
 
а  М. 
 
Множество можно описать, указав какое-то свойство, присущее всем элементам этого множества. 
Замечание. Вообще говоря, понятие множества считается первичным (исходным) понятием, и, как таковое, не определяется. Приведенное выше определение следует, скорее, считать уточнением понятия множества. 
Множество, все элементы которого являются числами, называется числовым. В дальнейшем мы будем, прежде всего, рассматривать именно такие множества. Множество, элементами которого являются другие множества, называется классом или семейством. 
Множество, содержащее конечное число элементов, называется конечным. 
При подсчете количества элементов учитываются только различные (неповторяющиеся) элементы. 
Множество, не содержащее элементов, называется пустым и обозначается символом ‡. 
Множество может быть задано перечислением (списком) своих элементов, порождающей процедурой или описанием характеристических свойств (предикатом), которым должны обладать его элементы. Причем в последнем случае 
необходимо формулировать описание характеристических свойств элементов 
множества достаточно корректно, для того, чтобы множество было определено 
вполне однозначно. Добавим, что многие числовые множества могут быть заданы всеми тремя указанными способами (например, множество четных однозначных чисел).  
 
6 
 

Пример 1. Некоторые примеры множеств, заданных различными способами. 
а) 
^
`
4
;
3
;
2
;
1
1  
M
; 
б) 
^
`
9
4
,
2




 
x
Z
x
x
M
; 
в) 
3
M
^
`
N
n
n
x
x


 
 
,
1
2
. 
Мощностью конечного множества М называется количество его элементов. Обозначается M . Если 
B
A  
, то множества А и В называются равномощными. 
Определение. Если все элементы множества А являются также элементами множества В, то говорят, что множество А включается (содержится) 
в множестве В.  
 
 
  
 
 
 
          
  
 
 
 
          А 
 
  
 
 
 
 
       В 
 
А  В 
 
Определение. Если А Ž В, то множество А называется подмножеством 
множества В (также говорят, что В покрывает А). Если при этом А z В, то 
множество А называется собственным подмножеством множества В и обозначается А  В.  
Замечание. Не следует считать равносильными отношения принадлежности 
)
(  и вхождения одного множества в другое 
)
( . Можно привести следующий пример. Пусть А – множество всех студентов данной группы, а В – 
множество всех учебных групп данного института. Здесь 
B
A
, но 
B
A Œ
, поскольку элементы этих множеств разнородны. Этот пример показывает также, 
что элементами множеств могут являться другие множества. 
Парадокс Рассела. Задание множеств характеристическим предикатом может привести к противоречиям. Рассмотрим множество всех множеств, не содержащих себя в качестве элемента: 
^
`
X
X
X
Y

 
. Если такое множество существует, то можно ответить на следующий вопрос: принадлежит ли оно само 
себе. С одной стороны, если 
Y
Y 
, то 
Y
Y 
. С другой стороны, если 
Y
Y 
, то 
Y
Y 
 Это противоречие можно разрешить различными способами, в целом 
сводящимся к тому, что Y  не является множеством. 
 
7 
 

Для трех множеств А, В, С справедливы следующие соотношения: 
 
;
;
A
A
A
A
Œ
Ž
 
;
C
A
C
B
B
A
Ž
o
Ž
š
Ž
 
;
C
A
C
B
B
A

o

š
Ž
 
 
Связь между включением и равенством множеств устанавливается следующим соотношением: 
 
.
A
B
B
A
B
A
Ž
š
Ž
l
 
 
 
Здесь знак š обозначает конъюнкцию (логическое «и»). 
В заключение добавим, что Г. Кантор предложил использовать понятие 
«универсального множества» (универсум), как бы противоположного понятию 
пустого множества ‡. По мысли Кантора, универсальное множество U  содержит все мыслимые множества, и при этом оно само содержится во множестве 
своих подмножеств в качестве элемента. В дальнейшем смысл и содержание 
понятия универсального множества будут раскрыты более подробно. 
 
2. ОПЕРАЦИИ НАД МНОЖЕСТВАМИ И ИХ СВОЙСТВА 
  
Определение. Объединением множеств А и В называется множество С, 
элементы которого принадлежат  хотя бы одному из множеств А и В. 
Обозначается С = А ‰ В.  
 
 
 
  
 
 
 
            А                 В 
  
 
 
Геометрическое изображение множеств в виде области на плоскости называется диаграммой Эйлера – Вэйна. 
Определение. Пересечением множеств А и В называется множество С, 
элементы которого принадлежат каждому из множеств А и В. 
Обозначение: С = А ˆ В. 
 
 
  
 
 
               А        С         В 
 
 
 
8 
 

Для множеств А, В и С справедливы следующие свойства: 
 
А ˆ А = А ‰ А = А;                  A ‰ B = B ‰ A;                   A ˆ B = B ˆ A; 
 
(A  ˆ B) ˆ C = A ˆ (B ˆ C);                             (A ‰ B) ‰ C = A ‰ (B ‰ C); 
 
A ‰ (B ˆ C) = (A ‰ B) ˆ (A ‰ C);         A ˆ (B ‰ C) = (A ˆ B) ‰ (A ˆ C); 
 
A ‰ (A ˆ B) = A;                                                                  A ˆ (A ‰ B) = A; 
 
‰
A
‡ = А;                                                                                       A ˆ ‡ = ‡. 
 
Определение. Разностью множеств А и В называется множество, состоящее из элементов множества А, не принадлежащих множеству В. 
Обозначается: С = А \ В.  
 
 
 
 
  
 
 
 
        А                 В 
 
 
 
Определение. Симметрической разностью множеств А и В называется 
множество С, элементы которого принадлежат в точности одному из множеств 
А или В. 
Обозначается: А ' В.   
 
А ' В = (A \ B) ‰ (B \ A). 
 
 
 
  
 
 
 
        A 
       B 
 
 
 
 
 
9 
 

Определение. СЕ называется дополнением множества А относительно множества Е, если А Ž Е и CЕ = Е \ A. 
 
 
 
 
  
 
 
 
            A 
 
E 
 
 
 
Для множеств А, В и С справедливы следующие соотношения: 
 
A \ B Ž A;                              A \ A = ‡;                         A \ (A \ B) = A ˆ B; 
 
A ' B = B ' A;                                                     A ' B = (A ‰ B) \ (A ˆ B); 
 
A \ (B ‰ C) = (A \ B) ˆ (A \ C);                   A \ (B ˆ C) = (A \ B) ‰ (A \ C); 
 
(A ‰ B) \ C = (A \ C) ‰ (B \ C);                    (A ˆ B) \ C = (A \ C) ˆ (B \ C); 
 
A \ (B \ C) = (A \ B) ‰ (A ˆ C);                              (A \ B) \ C = A \ (B ‰ C); 
 
(A ' B) ' C = A ' (B ' C);                      A ˆ (B ' C) = (A ˆ B) ' (A ˆ C); 
 
A ‰ CEA = E;     A ˆ CEA = ‡;        CEE = ‡;       CE‡ = E;       CECEA = A; 
 
CE(A ‰ B) = CEA ˆ CEB;                                        CE(A ˆ B) = CEA ‰ CEB. 
 
Пример 2. Исходя из определения равенства множеств и операций над 
множествами, доказать тождество и проверить его с помощью диаграммы Эйлера – Вэйна. 
 
)
(
\
\
B
A
A
B
A
ˆ
 
. 
Из записанных выше соотношений видно, что 
 
 
‰
 
ˆ
)
\
(
)
\
(
)
(
\
B
A
A
A
B
A
A
‡
)
\
(
B
A
‰
= A \ В. 
 
Что и требовалось доказать. 
 
 
10