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

Министерство образования и науки Российской Федерации
Уральский федеральный университет
имени первого Президента России Б. Н. Ельцина

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

Рекомендовано 
методическим советом УрФУ 
в качестве учебного пособия для студентов, 
обучающихся по направлениям подготовки
231300 — Прикладная математика
141100 — Энергетическое машиностроение
140400 — Электроэнергетика и электротехника
140100 — Теплоэнергетика и теплотехника
141403 — Атомные станции: проектирование, 
эксплуатация и инжиниринг
280700 — Техносферная безопасность

2-е издание, стереотипное

Москва
Издательство «ФЛИНТА»
Издательство Уральского университета
2017

УДК 519.1(075.8)
ББК 22.176я73
          Э45

Рецензенты:
кафедра высшей и прикладной математики Уральского государственного университета путей сообщения (завкафедрой, д-р физ.-мат. наук проф. 
Г. А. Тимофеева);
д-р физ.-мат. наук, зам. директора ИММ УрО РАН В. Т. Шевалдин

Научный редактор — д-р физ.-мат. наук проф. А. Н. Сесекин

Э45

    Элементы дискретной математики [Электронный ресурс] : учебное 
пособие / Д. С. Ананичев, И. Ю. Андреева, Н. В. Гредасова, К. В. Костоусов.
– 2-е изд., стер. – М. : ФЛИНТА : Изд-во Урал. ун-та, 2017. — 108 с.

ISBN 978-5-9765-3021-8 (ФЛИНТА)
ISBN 978-5-7996-1387-7 (Изд-во Урал. ун-та)

В учебном пособии рассматриваются элементы дискретной математики:

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

УДК 519.1(075.8)
ББК 22.176я73

ISBN 978-5-9765-3021-8 (ФЛИНТА)
ISBN 978-5-7996-1387-7 (Изд-во Урал. ун-та)

© Уральский федеральный
     университет, 2015

1. логические исчисления

множество, отношения, функции

множества

Множество — совокупность объектов (элементов).
Множества A, B, …
Элементы a, b, c, ...
а О А
а — элемент А (а принадлежит А).
а П А
а — не элемент А (а не принадлежит А).

Основное свойство множеств

Для любых а и А выполняется ровно одно из двух условий: а О А, а П А.

Способы задания множеств

1. Перечисление элементов:
А = {0, 1, 2, 3, …, 9}.
B = {красный, синий, зеленый}.
C = {борода, шляпа, очки}.
Можно задать лишь конечные множества.

2. Определяющие свойства:
А = {x | x — десятичная цифра}.
N = {x | x — натуральное число}.
Z = {x | x — целое}.
N0 ={x | x О Z, x ≥ 0}.

Q = { m

n | m О Z, n О N}.

R ={x | x — действительное число}.
C ={x | x — комплексное число}.
(2,3) = {x | x О R, x
x
2
5
6
0
+
<
}.

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

Пример
1
1 2 3
О{ , , } — верно.

1
1
2
3
О{{ },{ },{ }} — не верно.
Элементы множества {{ },{ },{ }}
1
2
3
– это множества (а не числа).

Пример
Рассмотрим S
X X
X
=
П
{
|
} .
Допустим, что SПS, тогда элемент S удовлетворяет определяющему свойству множества S, следовательно, SОS. Противоречие. Допустим, что SОS, 
тогда элемент S не удовлетворяет определяющему свойству множества S, следовательно, SОS. Опять противоречие. Таким образом, S не удовлетворяет 
основному свойству множества.
Проблема записи определяющим свойством — это чрезмерная сила.
Ж =
№
{ |
}
x x
x
— пустое множество — множество без элементов. "a

U — универсальное множество — множество, содержащее все интересующие нас в данный момент элементы. "a а О U.

A
B
Н
— А подмножество В; В надмножество А, если "a

A
B
Н
$a a
A
О
 и a
B
П
.

Лемма 1
"A 1) Ж Н A .

2) A
A
Н
.

3) A
U
Н
.
Доказательство:
1) от противного (о/п).
Ж Н
® $
A
a aОЖ , a
A
П
.

2) очевидно.
3) по определению U.

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

Замечание

A
B
=
Ы
A
B
B
A

Н
Н
м
н
о

1. логические исчисления

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

А, В — множества.
A
B
x x
A x
B

=
О
О
{ |
,
} — пересечение множеств А и В.

A
B
x x
A

=
О
{ |
 или x
B
О
} — объединение множеств А и В.

x
A
О
 или x
B
О
 означает, что выполняется хотя бы одно из двух.

A
B
x x
A
\
{ |
=
О
 и x
B
П
} — разность множеств А и В.

A
U
A
x x
A
=
=
П
\
{ |
} — дополнение до А.

Свойства " А, В, С

Коммутативности
1) A
B
B
A


=
1') A
B
B
A


=

Ассоциативности
2) (
)
(
)
A
B
C
A
B
C




=
2') (
)
(
)
A
B
C
A
B
C




=

Дистрибутивности
3) (
)
(
)
(
)
A
B
C
A
C
B
C
U
I
I
U
I
=
3') (
)
(
)
(
)
A
B
C
A
C
B
C
I
U
U
I
U
=

Идемпотентности
4) A
A
A

=
4') A
A
A

=

Свойства нуля
5) A
A
Ж =
5') A
A
Ж =

Свойства единицы
6) A
U
U

=
6') A
U
A

=

Свойства дополнения
7) A
A
U

=
7') A
A

= Ж

Свойство двойного дополнения

8) A
A
=

Тождества поглощения
9) A
A
B
A
U
I
(
) =
9') A
A
B
A
I
U
(
) =

Законы де Моргана
10) A
B
А
В

=
З
10') A
B
А
В
З
=
И

Доказательство 2':

Докажем Н : "x x
A
B
C
О(
)



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

(по определению  ) ®
x
A
B
x
C
О
О
м
н
о



(по определению  ) ®

x
A
x
B
x
C

О
О
О

м

нп

оп

(по определению  ) ®
x
A
x
B
C
О
О
м
н
о


(по определению  ) ® x
A
B
C
О


(
) .

Докажем К : нужно развернуть стрелки.

Лемма 2
"A B
,
 и A
B
A
A
B
I
U
Н
Н
.

Доказательство: непосредственно следует из определения.

Лемма 3
1) A
B
Н
.

2) A
B
A

=
.

3) A
B
B

=
.
Данные условия эквивалентны.
Доказательство:
1
2
)
)
®
:

докажем Н : по Лемме 2,

докажем К : "a a
A

A
B

О
Н
ь
э
ю

®
О
®
О
a
B
a
A
B

.

2
1
)
)
®
: A
A
B
=

 (по Лемме 2) Н B  (по свойству 1’).

Лемма 4

"A B C
, ,
 и A
B
A
C
B
C

A
C
B
C
Н
Ю
Н
Н
м
н
о

I
I
U
U
 (стабильностьН относительно и ).

Доказательство:
"x x
A
C
О

 (по определению  )

®
О
Н ®
О
О
м
н
о
®
О

О

м

нп

оп

x
A
x
B
x
C
x
B
C

x
C

(
)
по определению


1. логические исчисления

"x x
A
C
О

x
A
A
B
x
B
B
С
О
®
Н
®
О
Н
(
)
по Лемме2

 или

x
C
B
С
О
Н
(
)
по Лемме 2

.

Следствие из Леммы 4

A
B
C
D

Н
Н
м
н
о

®
Н
Н
м
н
о

A
C
B
D

A
C
B
D
I
I
U
U

Доказательство:
A
C
B
C
B
D



(
)
(
)
по Лемме 4
по Лемме 4
Н
Н
.

Доказательство свойства 4:
По Лемме 1 A
A
Н
 вместе с Леммой 3 получаем A
A
A

=
.
Доказательство свойства 6:
По Лемме 1 Ж Н A  вместе с Леммой 3 получаем A
A
Ж =
.
Доказательство свойства 9':
По Лемме 2 A
A
B
Н

 вместе с Леммой 3 A
A
B
A
I
U
(
) =
.

Доказательство свойства 3:
Сначала докажем К :
A
C
С

 по Лемме2  
(
) Н
.

B
C
C

Н

(
)
(
)(
)
(
)
A
C
B
C
С
С
С
I
U
I
U
последствиюиз Леммы
посвойству 4
4 Н
=
.

A
C
A
A
B
I
U
(
)
(
)
по Лемме2
по Лемме2
Н
Н
.

B
C
B
A
B
I
U
(
)
(
)
по Лемме2
по Лемме2
Н
Н
.

(
)
(
)(
)
(
)
(
)

(
A
C
B
C
A
B
A
B
I
U
I
U
U
U
по следствиюиз Леммы

посвойст

4 Н

ву 4)
(
).
= A
B
U

Z
A
C
B
C
= (
)
(
)
I
U
I
.

Z
C
Z
A
B
Z
Z
Z
Н
Н
ь
э
ю

Ю
=
ў
(
)
(
)

(

U
I
посвойству 4

последствиюиз Леммы

4)
(
)
.
Н A
B
C
U
I

Теперь докажем Н :

"x x
A
B
C
x
A
B
x
C
О
Ю
О
О
м
н
о

(
)
U
I
U

x
A
x
C
x
A
C
Z
О
О
м
н
о
®
О
Н

.

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

Или

x
B
x
C
x
B
C
Z
О
О
м
н
о

®
О
Н

.

Булеан B (A) множества A — это множество всех его подмножеств.

отношения

Упорядоченная пара элементов x y
x y
x y
x
,
:
,
,
,
(
) = {
} { }
{
}.

Основное свойство

x y
z t
x
z
y
t
,
,
(
) = (
) Ы
=
=
м
н
о

Доказательство
1-й случай:
x
y
=

x y
x x
x
z t
z
z t
,
,
, ,
,
(
) = (
) = { }
{
} = {
} { }
{
}®{
} —

одноэлементное множество z
t
z
= = { }
{
} , значит x
z y
t
=
=
,.

2-й случай:
x № y

x y
x
z t
z
x y
z t
,
,
, ,
,
,
{
} { }
{
} = {
} { }
{
}Ю{
}={
}

Отсюда z t,
{
} —

2-элементное множество
Ю{ }№{
}®{ }={ }®
=
№
Ю
=
x
z t
x
z
x
z y
x
y
t
,
;
.
.

Отождествим x
x
x
x x
x
1
2
3
1
2
3
,(
,
)
,
,
(
)
(
)
(
)
 и 
.

Упорядоченная цепочка элементов x x
x
xn
1
2
3
,
,
,...,
— это

x x
x
x
x x
x
x
n
n
n
1
2
3
1
2
1
,
,
,...,
,
,...,
,
(
) = (
)
(
)
.

1. логические исчисления

Прямое произведение A и B

A
B
a b
a
A b
B
ґ
= (
)
О
О
{
}
,
|
,
.

A
A
A
a a
a
i
n a
A
n
n
i
i
1
2
1
2
1
ґ
ґ
ґ
= (
) " О{
}
О
{
}
...
,
,...,
|
...
.

Чтобы задать отношение, достаточно указать все пары объектов, которые оно связывает.
Бинарное отношение ρ на множествах A и B — это r Н
ґ
A
B .

N-арное отношение ρ — это r Н
ґ
ґ
ґ
A
A
An
1
2
...
.

Если 
A
A
A
A
A
A
A
A
A
n
n

n
1
2
3
1
2
=
=
=
=
=
ґ
ґ
ґ
=
...
...
, то 
 и r
r
Н An — 

n-местное отношение на A.
Отношение rна A :

рефлексивное, если " О
x
A x x
r ;

симметричное, если "
О
®
x y
A x y
y x
,
r
r ;

антисимметричное, если "
О
м
н
о
®
=
x y
A
x y
y x
x
y
,
r
r
;

транзитивное, если "
О
м
н
о

®
x y z
A
x y
y z
x z
, ,
r
r
r .

Примеры
1) «=» на Z.
2) «Ј» на Z.
3) « Н » на B (A).
4) ρ соответствует фразе «…учится в одной группе с…» на множестве всех 
студентов университета.
5) ρ соответствует фразе «…одного года рождения с…» на множестве всех 
людей.
6) «|» на Z.
7) «сравнимо по модулю n» на Z.
8) «<» на Z.

r Н A2 — эквивалентность, если ρ — рефлексивно, транзитивно, сим
метрично.
9) А — множество всех направленных отрезков на плоскости.

AB CD
AB
CD

AB
CD

u r
uu u r
uu
u r
uu
u r
uu

u r
uu
u r
uu
r
Ь


=

м
нп

оп|
| |
|

— это эквивалентность.

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

Вектор — множество всех соноправленных отрезков одинаковой длины.
a
AB
xy xy AB

r
u r
uu
u ru
u ru u r
uu

= йл
щы = {
|
}
r
.

r Н A2 — порядок, если ρ — рефлексивно, антисимметрично.

R
A i
I
i
=
О
{
}
|
— разбиение множества A, если:

1)
;
A
A
i
i I
=

О

2)
, ,
.
"
№
®
= Ж
i j i
j
A
A
i
j


a
A
a
x x a
О
йл
щы ={
}
r
r
|
— класс эквивалентности ρ (класс по порядку ρ эле
мента a).

A
a
a
A
/
|
r
r
= йл щы
О
{
} — фактор множества A по порядку ρ.

Теорема (об отношениях эквивалентности)

1) ρ — эквивалентность на A
a
a
A
Ю йл щы
О
{
}
r |
— разбиение A.

2) R
A i
I
i
=
О
{
}
|
— разбиение A Ю
Ы $ О
О
О
йл
щы
r
r
: x y
i
I x
A и y
A
i
i
— эк
вивалентности и A
R
/r =
.

Доказательство
1) 
a
A

a A
йл щы =

О
r

 очевидно " О
йл щы Н
a
A a
A
r
.

a
A
A
x
A

a A
a A
йл щы Н
=
О

О
О
r
r


,
.
рефлексивно

x x
x
x
x
a

a A
r
r
r
Ю
Ойл щы Ю
О
йл щы
О

Разные классы не пересекаются.
a
b
йл щы№ йл щы.

О/П.

a
b
c
a
b
c
a

c
b

c a
c b
йл щы йл щы№ Ж Ю $ Ойл щы йл щы®
Ойл щы®

Ойл щы®

м
нп

оп

®
®


r
r
м
н
о

м
н
о
®
a c
c b
a b
r
r
r .

"
Ойл щы® м
н
о

®
®
Ойл щы
x x
a
x a
a b
x b
x
b
:
r
r
r
, то есть a
b
йл щыН йл щы.

Симметрично b
a
a
b
йл щыН йл щыЮ йл щы= йл щы — противоречие.