Элементы дискретной математики
Покупка
Тематика:
Дискретная математика
Издательство:
ФЛИНТА
Год издания: 2017
Кол-во страниц: 108
Дополнительно
Вид издания:
Учебное пособие
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-9765-3021-8
Артикул: 677479.01.99
В учебном пособии рассматриваются элементы дискретной математики:
логические исчисления, предикаты, булевы функции, комбинаторика, теория
графов, автоматы и алгоритмы. Приведено решение типовых задач.
Предназначается для студентов всех форм обучения всех специальностей.
Тематика:
ББК:
УДК:
ОКСО:
- 01.00.00: МАТЕМАТИКА И МЕХАНИКА
- ВО - Бакалавриат
- 01.03.01: Математика
- ВО - Магистратура
- 01.04.01: Математика
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Министерство образования и науки Российской Федерации Уральский федеральный университет имени первого Президента России Б. Н. Ельцина Элементы дискретной математики Рекомендовано методическим советом УрФУ в качестве учебного пособия для студентов, обучающихся по направлениям подготовки 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 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 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
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
Ь
=
м
нп
оп|
| |
|
— это эквивалентность.
Вектор — множество всех соноправленных отрезков одинаковой длины.
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
йл щыН йл щыЮ йл щы= йл щы — противоречие.