Элементы дискретной математики

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

Федеральное государственное бюджетное

образовательное учреждение высшего образования

«Казанский национальный исследовательский

технологический университет»

О. М. Дегтярева, Р. Н. Хузиахметова, 

Р. Ф. Ахвердиев

ЭЛЕМЕНТЫ ДИСКРЕТНОЙ 

МАТЕМАТИКИ

Учебно-методическое пособие

Казань

Издательство КНИТУ

2020

УДК 519.7(075)
ББК 22.174я7

Д26

Печатается по решению редакционно-издательского совета 

Казанского национального исследовательского технологического университета

Рецензенты:

д-р техн. наук, проф. Е. К. Вачагина

канд. физ.-мат. наук, доц. О. Е. Тихонов

Д26

Дегтярева О. М.
Элементы дискретной математики : учебно-методическое пособие / 
О. М. Дегтярева, Р. Н. Хузиахметова, Р. Ф. Ахвердиев; Минобрнауки 
России, Казан. нац. исслед. технол. ун-т. – Казань : Изд-во КНИТУ, 
2020. – 84 с.

ISBN 978-5-7882-2963-8

Рассмотрены такие разделы дискретной математики, как элементы теории 

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

Предназначено для обучающихся всех направлений подготовки. 
Подготовлено на кафедре высшей математики.

ISBN 978-5-7882-2963-8
© Дегтярева О. М., Хузиахметова Р. Н., 

Ахвердиев Р. Ф., 2020

© Казанский национальный исследовательский 

технологический университет, 2020

УДК 519.7(075)
ББК 22.174я7

В в е д е н и е

Современные образовательные стандарты высшего образования 

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

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

Основными разделами дискретной математики являются теория 

множеств, общая алгебра, комбинаторное исчисление, математическая 
логика, теория графов, теория алгоритмов, теория автоматов, теория кодирования, сетевое планирование.

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

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

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

1 . 1 . О с н о в н ы е  п о н я т и я

Теоретико-множественные представления – это описание иссле
дуемого процесса (системы) средствами теории множеств как множества некоторых взаимосвязанных частей (элементов). Связи между элементами множества задаются через соответствия (отношения).

Первичным понятием для теории множеств является понятие 

множества, на котором строятся все дальнейшие математические конструкции.

Множеством называется совокупность объектов произвольной 

природы, объединенных по одному или нескольким заданным признакам. Множество считается определенным (заданным), если о произвольном объекте можно сказать, принадлежит он данному множеству 
или нет. Множества принято обозначать заглавными буквами латинского или русского алфавита X, Y, A, B. Объекты, образующие множества, называются элементами множества и обозначаются соответствующими малыми буквами x, y, a, b. Элементы множества должны быть 
различными.

Напомним некоторые используемые обозначения теории множеств. 
АВ – множество А состоит из части элементов множества В, 

или множество А является подмножеством множества В. Принадлежность элемента а множеству А обозначают аА, аА – элемент а не 
принадлежит множеству А.

Множество, состоящее из конечного числа элементов, называется 

конечным, в противном случае множество называется бесконечным. 

Например, N – множество натуральных чисел, R – множество 

действительных чисел, Z – множество целых чисел, Q – множество рациональных чисел, C – множество комплексных чисел. Перечисленные 
множества бесконечны.

Число элементов, входящих в конечное множество М, называ
ется мощностью этого множества и обозначается |M|.  – обозначение 
пустого множества, мощность его равна 0.

Множества можно задать либо перечислением всех его элемен
тов внутри скобок {…} (например, А={2, 4, 6, 8} – множество четных 
натуральных чисел, принимающих значение меньшее 10), либо описанием свойств, которыми должны обладать элементы этого множества 
(например, то же множество А можно задать в следующем виде А={m|
m=2n, где n – целое, 1n4}). Второй способ называют также аналитическим описанием множества, используя его характеристические свойства. Если каждому элементу множества можно поставить в соответствие единственным образом порядковый номер (пронумеровать), то 
такое множество называется счетным.

1 . 2 . О п е р а ц и и  н а д  м н о ж е с т в а м и

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

Множества А и В равны (А = В), если АВ и ВА. Другими сло
вами, равные множества состоят из одних и тех же элементов.

АВ – объединение (сумма) множеств А и В – это новое множе
ство, состоящее из элементов, входящих или в множество А, или в множество В (


C
A
B
x
C/x
A  èëè  x
B
=

=



); АВ – пересечение

(произведение) множеств А и В – множество, состоящее из элементов, 
входящих 
и 
в 
множество 
А 
и 
в 
множество 
В

(


C
A
B
x
C/x
A  è  x
B
=

=



; А\В – разность множеств А и В –

подмножество множества А, состоящее из элементов множества А, не 
входящих в множество В (


C
A \ B
x
C/x
A  è  x
B
=
=



). 

Симметрической разностью множеств A и B называется новое 

множество, которое состоит из всех элементов множеств A\B или B\A, 
A
B
(A \ B)
(B\ A)
+
=

.

Множество U называется универсальным, если все рассматривае
мые множества являются его подмножествами. 

Перечисленные операции над множествами графически можно 

изобразить с помощью диаграмм Эйлера–Венна (рис. 1.1). Построение 
диаграммы Эйлера–Венна заключается в изображении прямоугольника, 

представляющего универсальное множество, круги внутри этого универсального множества представляют его подмножества.

Если AU, то множествоA=U\A называется дополнением мно
жества А до множества U.

Декартовым произведением множеств А и В называют множе
ство всех упорядоченных пар (
)
,a b , где аА, bВ. Обозначение декар
това произведения множеств А и В: 
(
)


A B
A,
B

=


a,b a
b
.

Декартовым квадратом множества А называют декартово про
изведение: 
(
)



2
A
A A
A,
A
=

=


a,b a
b
.

Декартовым (прямым) произведением множеств А1, А2, …, Аn

называется множество А1хА2х…хАn
составленное из элементов 

(
)
1
2
,
,...,
n
a a
a
, где аi – всевозможные элементы из Ai.

Рис. 1.1

Отображением множества А в множество В называется некоторое 

правило, которое любому элементу аА ставит в соответствие единственный элемент bВ. Обозначение отображения множества А в множество В: 

f: A→B (f – наименование отображения). Элемент b=f(a) – это значение 
отображения f в точке а или образ элемента а, а – прообраз элемента b.

Замечание. Слова отображение и функция – синонимы, множе
ство А – область определения функции f, множество значений функции 
f называют образом отображения f.

Запишем основные свойства операций над множествами.

1 . 3 . О с н о в н ы е  т о ж д е с т в а  а л г е б р ы  м н о ж е с т в

1. Коммутативность  операций , :    

АВ=ВА, АВ=ВА.

2. Ассоциативность операций , : 

А(ВС)= (А)ВС;  А(ВС)= (А)ВС.

3. Дистрибутивность  относительно : 

А(ВС)=(АВ) (АС).

Дистрибутивность  относительно : 

А (ВС)=(АВ) (АС).

4. Законы поглощения: 

А (ВА)=А;  А (АВ)=А.

5. АA=U, АA=.

6. A=U, A=.

7. AU=A, AU=U.

8. AA=A, AA=A.

9. Закон двойственности (закон де Моргана):

A
B
A
B,  A
B
A
B

=


=

.

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

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

1 . 4 . Б и н а р н ы е  о т н о ш е н и я

Отношения – это один из способов задания взаимосвязей между 

элементами множества. Математическое отношение – правило, связывающее два или более объекта.

Бинарные отношения (операции, отображения) – отношения, 

связывающие пары математических объектов с результатами операций
над этими объектами. Бинарное отношение на множестве А – это подмножество множества АхА. 

Обозначение бинарного отношения . АхА. Если элементы х, 

уА связаны отношением,  пишут (х,у) или используют запись 
ху. Бинарные (двухместные) отношения применяются для определения некоторых взаимосвязей, которыми характеризуются пары элементов в некотором множестве А. Например, на множестве А – множество 
людей может быть задано отношение σ – работать в одной организации. 

Бинарное отношение  называется:
– рефлексивным, если для любого элемента аА имеет место 

(а,а); 

– симметричным, если для любых элементов а, bA из (а,b)

следует (b,а); 

– антисимметричным, если ни при каких элементах а, bA, аb

не возможно одновременное выполнение условий (а,b) и (b,а); 

– транзитивным, если для любых элементов а, b, сА из условий 

(a,b); (b,c) следует (a,c). 

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

Бинарной (алгебраической) операцией на множестве А называ
ется отображение АхА→А. Каждой упорядоченной паре элементов 
множества (а,b) а, bA, ставится в соответствие единственный элемент 
сA – произведение а и b (с=ab). Термин «произведение» здесь носит 
условный характер. Он может означать сумму, разность и другие 

действия. Обозначают бинарные операции: аb, a*b, a+b… Множество 
А, на котором задана операция *, обозначают {A,*}.

Свойства алгебраических операций. Пусть на множестве А опре
делены две алгебраические операции:  * и ┴.

Алгебраическая операция *, определенная на множестве А,

называется:

– коммутативной, если для любых элементов х, у А справед
ливо равенство: х*у = у*х;

– ассоциативной, если для любых элементов х, у, z А справед
ливо равенство (x*y)*z=x*(y*);

– дистрибутивной относительно операции ┴, если для любых 

элементов x, y, z

A
справедливы
следующие равенства:

x*(y┴z)=(x*y)┴(x*z) и (x┴y)*z=(x*z)┴(y*z).

1 . 5 . П р и м е р ы

1. Пусть множество A состоит из натуральных чисел, меньших 

170. Задать множество A аналитически с помощью характеристического свойства.

Решение. Свойство, которым обладает любой элемент данного 

множества, – «быть натуральным числом, меньшим 170». Таким образом, 
можно записать: 


A
x
x
N, x
170
=


, где х – элемент множества.

2. Пусть F – множество сотрудников фирмы, А – множество со
трудников старше 40 лет; В – множество сотрудников со стажем работы 
более 10 лет; С – множество менеджеров фирмы. Охарактеризовать
множества B, 
(
)
A
B
C


, В\С. 

Решение. B – множество сотрудников со стажем работы, не пре
вышающим 10 лет. 

(
)
A
B
C


– множество сотрудников старше 40 лет, не являю
щихся менеджерами, со стажем более 10 лет.

В\С – множество сотрудников со стажем работы более 10 лет, не 

работающих менеджерами.