Специальные главы математики. Дискретная математика

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

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

высшего профессионального образования

«Воронежская государственная лесотехническая академия»

И. В. Сапронов П. Н. Зюкин 

С. С. Веневитина Е. О.Уточкина

СПЕЦИАЛЬНЫЕ ГЛАВЫ МАТЕМАТИКИ 

ДИСКРЕТНАЯ МАТЕМАТИКА

Учебное пособие для магистров

по направлению  09.04.02  Информационные системы и технологии

Воронеж 2014

УДК 519.1

Специальные главы математики. Дискретная математика [Электронный ресурс]: 
учебное пособие для магистров по направлению 09.04.02 Информационные 
системы и технологии / И.В. Сапронов, П.Н. Зюкин, С.С. Веневитина, 
Е.О.Уточкина; М-во образования и науки РФ, ФГБОУ ВПО «ВГЛТА», –
Воронеж, 2014.  – 118 с.

Учебное пособие включает в себя краткое изложение основных разделов 

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

Учебное пособие предназначено для магистров   по направлению
09.04.02

Информационные системы и технологии

УДК 519.1

© Сапронов И.В., Зюкин П.Н., 
Веневитина С.С., Уточкина Е.О., 2014
© ФГБОУ ВПО «Воронежская государственная 

лесотехническая», 2014

ВВЕДЕНИЕ

Полвека назад практически все электронные устройства были аналоговые, 

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

Теперь трудно найти человека, который не сталкивался бы с устройствами, 

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

Дискретная математика в последние годы быстро развивалась и в настоящее 

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

Данное пособие предназначено не для математиков, оно ориентировано на 

студентов, обучающихся в технических вузах.

При подготовке данного пособия авторы стремились в основном к 

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

Рассмотрены вопросы семи разделов, изучаемых в курсе дискретной 

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

1. Теория множеств

Цель: познакомить с основными понятиями теории множеств, операциями над 

множествами, отображением множеств; научить использовать эти понятия и 
операции при решении задач.

1.1. Теоретическая часть

1.1.1. Множества, их элементы и подмножества

Под множеством понимают совокупность различимых объектов любой 

природы, объединенных по какому –
либо признаку, которые называют 

элементами множества.

Множества принято обозначать прописными буквами А, В, С, . . . , а их 

элементы – малыми буквами а, b, с, . . . .

Запись а 
A означает, что объект а является элементом множества A (а 

принадлежит множеству А). Если объект b не принадлежит множеству B, то 
пишут b
В.

Стандартные обозначения важных числовых множеств:

– множество натуральных чисел;
– множество целых чисел;
– множество рациональных чисел;
– множество действительных (вещественных) чисел;
– множество комплексных чисел.

Множество можно обозначить также, записав внутри фигурных скобок все его 

элементы или записав их свойства. Например, {2, 4, 6, . . . } – множество всех
четных
положительных
чисел,
{x

нечетных чисел.

x
2k
1для k
}
–
множество
всех

Множество, число элементов которого конечно, называют конечным. В 

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

Бесконечные множества делятся на счетные и несчетные. Если элементы 

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

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

конечные и счетные множества.

Если каждый элемент множества А есть элемент множества В, то А   называют

подмножеством множества В и пишут А 
В.

Если А 
В и В 
А, то множества А и В называют равными и пишут А = В, 

иначе пишут А  
В. Если А 
В, А  
В, то пишут А 
В.

Множество, не содержащее ни одного элемента, называется пустым и 

обозначается Ø или V. Пустое множество считается конечным множеством и 
подмножеством любого множества.

Если
А
В,
А
Ø,
то
множество
А
называется
собственным

подмножеством множества В.

Пустое
множество
и
множество
А
называются
несобственными

подмножествами множества А.

Множество, содержащее все элементы, находящиеся в рассмотрении, 

называется универсальным и обозначается U.

Число всех подмножеств любого конечного множества, содержащего n

элементов, равно 2n. Так, например, для множества {a1, a2, a3} всеми его 
подмножествами    являются    V,    {a1},    {a2},    {a3},    {a1, a2},    {a1, a3}, {a2, a3},
{a1, a2, a3} = U.

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

Объединением   (суммой)  множеств  A и  B
называется множество
A
B,

состоящее из всех элементов, принадлежащих хотя бы одному из множеств А, В:

В частности, A
Ø = А,

A
B
{x 

A 
U U.

x 
A или x 
B}.

Пересечением (произведением) множеств A и В называется множество  A
B ,

состоящее из всех элементов, принадлежащих как множеству А, так и множеству 
В:

A
B {x x
A и x
B}.

В частности, A
Ø = Ø,  A
U = A.

Дополнением
множества  A называется  множество   A ,  состоящее из всех

элементов универсального множества U, не принадлежащих множествуА:

A {x x
U и x
A}.

Заметим, что A
A
U,
A
A
Ø.

Разностью множеств A и В называется множество A \ B, состоящее из всех 

элементов множества А, не принадлежащих множеству В:

A \ B
{x x
A и x
B}.

Перечисленные  операции  проиллюстрируем  диаграммами  Эйлера  –
Венна

(рис. 1.1).

A 
B
A
B
A
A \ B

Рис. 1.1. Диаграммы Эйлера – Венна

Отметим порядок выполнения операций над множествами: 1) дополнение (
),

2) пересечение ( 
), 3) объединение ( 
),  разность ( \ ).

Укажем основные свойства операций объединения, пересечения и дополнения:
1. Ассоциативность операций объединения ипересечения:

A
(B
C)
(A
B)
C,
A
(B
C)
(A
B)
C.

2.
Коммутативность
операций объединения и пересечения:

A 
B B 
A,

3. Законы идемпотентности:

A 
A A,

4. Законы дистрибутивности:

A 
B B 
A.

A 
A A.

A 
(B 
C) (A 
B) 
(A 
C),

A 
(B 
C) (A 
B) 
(A 
C).

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

A 
(A
B) A,

6. Законы де Моргана:

A 
(A 
B) A.

A 
B A
B,
A 
B A 
B.

7. Закон двойного дополнения: A
A.

Отметим
еще
две
важные
операции
над
множествами
–
декартово 

произведение и симметрическую разность.

Декартовым (прямым) произведением множеств A и B называется множество

A B, состоящее из всех упорядоченных пар (x, y), где x
A, y
B :

A
B
{(x, y) x
A и y
B}.

Аналогично вводятся понятия декартова произведения n сомножителей и 

декартовой степени множества:

A1 A2 
...
An
{(a1, a2 , . . ., an ) a1 
A1, a2 
A2 , . . ., an 
An},

A A
...
A An (для n сомножителей).

В частности,
2 =
,
3 =
.

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

состоящее из всех элементов, принадлежащих хотя бы одному из множеств A\В, 
В\А:

A
B = (A\B) 
(B\A).

Проиллюстрируем последнюю операцию диаграммой Эйлера – Венна (рис. 1.2).

А 
В

Рис. 1.2 Диаграмма Эйлера – Венна для симметрической разности множеств

1.1.3. Отображение множеств

Отображением   f множества X
в   множество   Y называют правило, по

которому каждому элементу x множества X поставлен в соответствие  некоторый

единственный  элемент  y множества Y. Для
обозначения
отображения
f

множества X в множество Y пользуются записью f : X
Y.

Если x – элемент множества X, то соответствующий ему при отображении        

f : X
Y элемент y множества Y называют образом элемента x при данном 

отображении, обозначают f(x) и пишут y = f(x). Совокупность всех тех элементов 
x множества X, образом которых при отображении f : X
Y является данный 

элемент   y множества   Y,   называют   прообразом   элемента   y при   данном

отображении и обозначают f
1(y).

Если А 
X, то совокупность всех элементов множества Y, которые при 

отображении f : X
Y являются образами хотя бы одного элемента множества  

А, называют образом множества А при данном отображении и обозначают f (A). 
Если В 
Y, то совокупность всех тех элементов множества X, образы которых 

при отображении f : X
Y принадлежат множеству В, называют прообразом

множества В при данном отображении и обозначают f
1(B).

Отображение  f :  X
Y называют  инъективным,  если  для  любых   двух

различных элементов x1  и x2  множества  X их  образы
f(x1) и  f (x2 ) также

различны, и сюръективным, если для каждого элемента y множества Y
существует элемент x множества X такой, что y = f(x). Отображение f : X
Y

называется биективным (взаимно однозначным), если оно инъективно и 
сюръективно.

Два множества называются изоморфными (эквивалентными), если существует 

биективное отображение одного из них в другое.

Для сокращения записей будем пользоваться следующими специальными 

символами:

– «следует», «если …, то»;
– «равносильно», «тогда и только тогда, когда».

1.2. Практическая часть

Пример 1.1. Пусть A = {1, 3, 5, 8}, B = {2, 3, 8, 10}, C = {3, 9, 10}. Перечислить 

все элементы следующих множеств:

a) A
B
B
C
D,
b) (A
C) \ (B
A) 
E.

Решение. Из определений операций над множествами и порядка выполнения 

этих операций имеем:

a) A 
B
{3,8},
B
C
{3, 10} 
D  {3, 8, 10};

b) A 
C
{1, 3, 5, 8, 9,10},
B 
A
{3, 8}  
E
{1, 5, 9, 10}.

Пример  1.2.  Пусть  множество  A состоит  из  точек  M(x,  y)  плоскости,  для

которых
x
3  и
y
5, множество  B – из  точек  плоскости,  для   которых

x2  
y2
25, множество С – из точек плоскости, для которых x < 0. Требуется

изобразить множество A
B \ C.

Решение. По условию множество A представляет собой прямоугольник с 

центром симметрии в начале системы координат, множество B – круг радиуса 5 с 
центром тоже в начале системы координат, множество C – левую  полуплоскость

координатной
плоскости
xOy.
Тогда  A
B – «обрезанный» прямоугольник

KLST, A
B \ C – множество  точек,  полученное  удалением  из  A
B
точек

полуплоскости x < 0. Искомое множество затонировано на рис. 1. 3.

Рис. 1.3.

Пример 1.3. Доказать, что A\B = A
B.

Решение.
Произвольный
элемент
x 
A \ B
x 
A и x 
B 
x
A
и

x
B
x
A
B. Доказательство завершено.

Пример 1.4. Упростить выражение A
B
A
B
C.

Решение. A
B
A
B
C = (по законам де Моргана) = A
B
A
B
C =

(снова  дважды  применяем  законы  де  Моргана,  закон  двойного  отрицания   и

другие законы) = A
B
A
B
C = A 
B 
(A 
B 
C) =

= A 
B 
A 
A 
B 
B 
A 
B 
C = A 
A 
B 
A 
B 
A 
B 
C  

= Ø
A 
B A 
B.

Итак, A
B
A
B
C = A 
B.

Пример 1.5. Пусть А = {1, 2}, B = {3, 4}. Перечислить все элементы  множеств

А В, В А, A2.

Решение. А В = {(1, 3), (1, 4), (2, 3), (2, 4)}, В А = {(3, 1), (3, 2), (4, 1), (4,  2)},

A2 = A A = {(1, 1), (1, 2), (2, 1), (2, 2)}.

Пример 1.6. Пусть A = {x x
[0, 1]}. Требуется изобразить множество A2.

Решение.
A2 
{(x, y) 0 x
1, 0 y
1}.
Этому
множеству
соответствует

множество точек на плоскости, имеющих неотрицательные координаты, не 
превосходящие единицы (рис. 1. 4).

Рис. 1.4.

1

1

1
2

2

2

2

Пример 1.7. Пусть X = {a, b, c, d}, Y =  {1,  4,  8}.  Рассмотрим     отображения

f1 : X
Y,
f2 : X
Y :

f1  :  a
1,
f2  :  1 
b,

b
4,
4 
c,

c
8,
8 
d.

d
8

Определить, являются ли эти отображения инъективными и сюръективными.

Решение. Имеем

f1 (a) =1,

f1 (b) =4,

f 1(1) {a},

f 1(4) {b},

f2 (1) b,

f2(4)
c,

1(b) {1},
1(c) {4},

f1 (c)= f1 (d) =8,
f 1(8)
{c, d},
f2 (8) d,
1(d) {8}, f 1(a)
Ø.

Образы f1(c), f1 (d) элементов c, d совпадают, поэтомуотображение f1  : X
Y не

является инъективным. Для каждого элемента множества Y существует   элемент
множества  X,  образом  которого  при отображении
f1   :  X
Y является этот

элемент множества Y, поэтому отображение f1  : X
Y является сюръективным.

Так как образы любых двух различных элементов множества Y при отображении
f2  : Y
X различны, то это отображение является инъективным. В множестве  Y

не  существует  элемента,  образом  которого  при   отображении
f2   :  Y
X

является элемент a множества X, поэтому последнее отображение не является 
сюръективным.

1.3. Индивидуальные задания

1. Пусть  U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10},  множества A, B, C, D заданы в табл. 1.

Перечислить все элементы множества D.

Таблица 1

Вариант
Множества

1
A = {1, 4, 5, 7, 8}, B = {2, 3, 4}, C = {1, 9}, 
D ((A 
C) \ (A 
B)) C

2
A = {2, 5, 6}, B = {1, 3, 5, 6, 8}, C = {1, 4}, 
D C ((A 
B) \ (C 
B))

3
A = {1, 3, 4, 6, 7}, B = {1, 2, 4}, C = {1, 8, 10}, 
D ((A 
C) \ (B 
A)) B

4
A = {2, 3, 4, 5, 6, 9, 10}, B = {4, 5, 6, 7, 8, 9, 10}, C = {1, 2, 3}, 
D A ((B 
C) \ (A 
C))

5
A = {2, 5, 6, 8, 9}, B = {3, 4, 5}, C = {2, 10}, 
D ((A 
C) \ (A 
B)) C

6
A = {3, 6, 7}, B = {2, 4, 6, 7, 9}, C = {2, 5}. 
D C ((A 
B) \ (C 
B))

f

f

f

Вариант
Множества

7

A = {2, 4, 5, 7, 8}, B = {2, 3, 5}, C = {1, 2, 9}, 
D ((A 
C) \ (B 
A)) B

8
A = {1, 3, 4, 5, 6, 7, 10}, B = {1, 5, 6, 7, 8, 9, 10}, C = {2, 3, 4}, 
D A ((B 
C) \ (A 
C))

9
A = {3, 6, 7, 9, 10}, B = {4, 5, 6}, C = {1, 3}, 
D ((A 
C) \ (A 
B)) C

10
A = {4, 7, 8}, B = {3, 5, 7, 8, 10}, C = {3, 6}, 
D C ((A 
B) \ (C 
B))

11
A = {3, 5, 6, 8, 9}, B = {3, 4, 6}, C = {2, 3, 10},
D ((A 
C) \ (B 
A)) B

12
A = {1, 2, 4, 5, 6, 7, 8}, B = {1, 2, 6, 7, 8, 9, 10}, C = {3, 4, 5}, 
D A ((B 
C) \ (A 
C))

13
A = {1, 4, 7, 8, 10}, B = {5, 6, 7}, C = {2, 4}, 
D ((A 
C) \ (A 
B)) C

14
A = {5, 8, 9}, B = {1, 4, 6, 8, 9}, C = {4,7}, 
D C ((A 
B) \ (C 
B))

15
A = {4, 6, 7, 9, 10}, B = {4, 5, 7}, C = {1, 3, 4}, 
D ((A 
C) \ (B 
A)) B

16
A = {2, 3, 5, 6, 7, 8, 9}, B = {1, 2, 3, 6, 8, 9, 10}, C = {4, 5, 6}, 
D A ((B 
C) \ (A 
C))

17
A = {1, 2, 5, 8, 9}, B = {6, 7, 8}, C = {3, 5}, 
D ((A 
C) \ (A 
B)) C

18
A = {6, 9, 10}, B = {2, 5, 7, 9, 10}, C = {5, 8}, 
D C ((A 
B) \ (C 
B))

19
A = {1, 5, 7, 8, 10}, B = {5, 6, 8}, C = {2, 4, 5}, 
D ((A 
C) \ (B 
A)) B

.
20
A = {3, 4, 6, 7, 8, 9, 10}, B = {1, 2, 3, 4, 7, 9, 10}, C = {5, 6, 7}, 
D A ((B 
C) \ (A 
C))

21
A = {2, 3, 6, 9, 10}, B = {7, 8, 9}, C = {4, 6}, 
D ((A 
C) \ (A 
B)) C

22
A = {1, 7, 10}, B = {1, 3, 6, 8, 10}, C = {6, 9}, 
D C ((A 
B) \ (C 
B))

23
A = {1, 2, 6, 8, 9}, B = {6, 7, 9}, C = {3, 5, 6}, 
D ((A 
C) \ (B 
A)) B

24
A = {1, 4, 5, 7, 8, 9, 10}, B = {1, 2, 3, 4, 5, 8, 10}, C = {6, 7, 8}, 
D A ((B 
C) \ (A 
C))

25
A = {1, 3, 4, 7, 10}, B = {8, 9, 10}, C = {5, 7}, 
D ((A 
C) \ (A 
B)) C