Файл: Учебное пособие по изучению курса Дискретная математика для студентов направления 230100 Информатика и вычислительная техника.pdf

1.1.6. Диаграммы Эйлера-Венна
Диаграммы Эйлера-Венна позволяют представить множества, как множества точек на плоскости, ограниченные замкнутыми кривыми круглой или овальной формы. Прямоугольная рамка ограничивает универсум.
Обычно, если не требуется иное, рисуют так называемый общий случай:
когда каждое из множеств имеет свои собственные точки и точки, общие с другими множествами.
U
A
B
Рис. 2. Диаграммы Эйлера - Венна
1.2. Операции над множествами
Нужно определить способы, с помощью которых из уж существующих множеств можно будет получать новые множества, т. е. операции над множествами.
Обычно рассматриваются следующие операции над множествами:

10 1) Объединение:
или
На диаграмме Эйлера-Венна эта операция изображается следующим образом:
Рис. 3. Диаграмма Эйлера-Венна для объединения двух множеств
2) Пересечение и
Рис. 4. Диаграмма Эйлера-Венна для пресечения двух множеств
3) Разность и
Рис. 5. Диаграмма Эйлера-Венна для разности двух множеств
4) Симметрическая разность и
или

11
Рис. 6. Диаграмма Эйлера-Венна для симметрической разности двух множеств
5) Дополнение
Операция дополнения подразумевает некоторый универсум.
Рис. 7. Диаграмма Эйлера-Венна для дополнения множества А
Операцию дополнения можно записать, используя операцию разности:
. Тогда разность двух множеств также можно выразить через операцию дополнения:
Примеры.
А={1,2,3,4,5}
B={4,5,6,7}
1.
2.
3.
4.
5.
- все числа, кроме 1,2,3,4,5.
1.3. Алгебра множеств
Для операций справедлив ряд законов. Для упрощения записи,
уменьшения числа скобок, определяющих последовательность операций,
можно использовать соглашение о приоритете операций (в порядке убывания): дополнение, пересечение, объединение.
Остальные операции можно выразить через эти три.

12
Таблица 1. Законы алгебры множеств
Название
1
Коммутативный
2
Ассоциативный
3
Дистрибутивный
4
Поглощения
5
Де Моргана
6
Идемпотентности
7
Исключенного третьего
8
Свойства нуля
9
Свойства единицы
10
Инволюции
В справедливости этих законов можно убедиться разными способами.
1 способ. Можно нарисовать диаграммы Эйлера-Венна для правой и левой части законов и убедиться, что они совпадают.
2 способ. Можно провести формальные рассуждения для каждого равенства.
Пример.
Рассмотрим доказательство дистрибутивного закона.
1 способ.
На рис. 8 показано множество
Рис. 8. Диаграмма Эйлера-Венна левой части дистрибутивного закона
На рис. 9 показано множество

13
Рис. 9. Диаграмма Эйлера-Венна правой части дистрибутивного закона
Множества D и F равны.
2 способ.
1) Докажем, что левая часть включена в правую: A
∪
(B
∩
C)
⊆
(A
∪
B)
∩
(A
∪
C) .
Если
, то или
. Если
, то и
. Следовательно,
Если
, то и
. Отсюда и
, а значит
2)
Теперь докажем,
что правая часть включена в
левую:
. Если
, то и
Следовательно,
или и
, т. е.
. Отсюда
То есть левое и правое множества равны.
1.4. Графики
1.4.1. Понятие графика
Упорядоченная последовательность элементов вида называется кортежем. Кортеж из двух элементов называется парой, из трех –
тройкой, из n – энкой. В кортеже существенны не только элементы, но и порядок, в котором они располагаются. Следовательно, кортеж может содержать одинаковые элементы.
Проекция кортежа на заданные оси - есть кортеж, составленный из соответствующих компонент исходных кортежей. Рассматриваются только проекции на возрастающий (по номеру) список осей.
Пример
B = <2, 5, 6, 4, 2, 6>
пр.B
1,2,4
= <2, 5, 4>
Проекция некоторого множества М на множество осей дает множество проекций кортежей, составляющих множество. Исходное множество должно состоять из кортежей одинаковой длины.
Пример.

14
M={, , , }
пр.M
1,3
={, , , }
Множество пар образуют график.
Примеры:
G
1
= { < a, b >, < c, a >, < d, b > }
G
2
={<1,2>,<2,4>,<3,6>,<4,8>}
x i
y i
G
3
X и Y – множества действительных чисел
X
Y
Рис. 10. Пример графика
Пара <с,d> является инверсией пары, если с=b, d=a.
График р
-1
называется инверсивным, если его элементы являются инверсиями соответствующих пар графика р.
Пример.
p={,}
p
-1
={,}
Диагональным называется график вида
Пример.
p={<1,1>,<2,2>,<3,3>,<4,4>}
Композиция графиков P и Q это график такой, что тогда и только тогда, когда есть элемент z такой, что
Пример.
P = {< a, b >, < 1, r >, < c, 3 >, < a, 4 >}
Q = {< 2, 3 >, < 4, 5 >, < a, c >, < b, d >}
= {< a, d >, < a, 5 >}
Декартово (полное) произведение множеств А и В – это совокупность пар таких, что и
:
,
}.
Пример.
А={1,2}, B={1,2,3}
График является полным, если он совпадает с декартовым произведением.
1.4.2. Свойства графиков
1
. График называется функциональным, если он не содержит пар с одинаковой первой и различными вторыми компонентами.

15 2. График называется инъективным, если он не содержит пар с одинаковой второй и различными первыми компонентами.
3. График называется симметричным, если он равен своей инверсии.
Примеры графиков и их свойств см. таблицу 2.
Таблица 2. Примеры графиков и их свойства
График
Свойства x
1
x
2 1. Функционален, т. к. нет пар с одинаковой первой и различными вторыми компонентами.
2. Не инъективен, т. к.
есть пары с одинаковой второй и
различными первыми компонентами 1
,y
1
>,2
,y
1
>.
x
1 1. Не функционален, т. к.
есть пары с одинаковой первой и
различными вторыми компонентами 1
,y
1
>,1
,y
2
>.
2. Инъективен, т. к. нет пар с одинаковой второй и различными первыми компонентами x
1
y
1
x
2 1. Функционален, т. к. нет пар с одинаковой первой и различными вторыми компонентами.
2. Инъективен, т. к. нет пар с одинаковой второй и различными первыми компонентами.
y
1
y
2
y
1
y
2

16
Продолжение таблицы 2. Примеры графиков и их свойства
График
Свойства x
1
х
2
х
3 1. Не функционален, т. к.
есть пары с одинаковой первой и
различными вторыми компонентами:
,.
2. Не инъективен, т. к.
есть пары с одинаковой второй и
различными первыми компонентами:
,.
3. Симметричен, т. к.
инверсивный график совпадает с исходным.
1.5. Соответствия
1.5.1. Понятие соответствия
Соответствие – это упорядоченная тройка множеств такая,
что
. Первый компонент (G) - график.
Второй компонент (A) - область отправления (определения).
Третий компонент (B) - область прибытия (значений).
Соответствие называется полным, если
1.5.2. Свойства соответствий
1. Соответствие называется функциональным, если его график функционален.
2. Соответствие называется инъективным, если его график инъективен.
3. Соответствие называется всюдуопределенным, если проекция графика на первую ось совпадает с областью отправления. пр.G
1
= A.
4. Соответствие называется сюръективным, если проекция графика на вторую ось совпадает с областью прибытия пр.G
2
= B.
5. Соответствие называется биективным (взаимно-однозначным), если оно функционально, инъективно, всюдуопределено и сюръективно.
Примеры.
1. A={Иванов, Петров, Сидоров, Кузнецов} – студенты, сдающие экзамен.
B={2,3,4,5} – оценки, полученные на экзамене.
График соответствия G
1
={<Иванов, 4>, <Петров, 3>, <Сидоров, 5>,
<Кузнецов, 5>}.
y
2
y
3
y
1

17 2
3 4
5
Иванов
Петров
Сидоров
Кузнецов
Рис. 11. График соответствия между студентами и оценками на экзамене
Свойства соответствия G
1
:
1. Функциональное, т. к. его график функционален (каждый студент получил одну оценку).
2. Не инъективное, т. к. его график не инъективен (два студента получили одинаковые оценки).
3. Всюду определенное, т .к все студенты получили оценки.
4. Не сюръективное, т. к. двойку никто не получил, следовательно,
проекция графика на вторую ось не совпадает с областью прибытия (В).
5. Соответствие не является биективным.
2. A={Иванов, Петров, Сидоров, Кузнецов} – покупатели, пришедшие в магазин.
B={стиральный порошок, зубная паста, мыло, пена для бритья,
туалетная вода, средство для мытья окон, отбеливатель} – товары в магазине
(не виды товаров, а конкретные предметы!).
График соответствия G
2
={<Иванов, мыло>, <Иванов, стиральный порошок>, <Иванов, зубная паста>, <Кузнецов, пена для бритья> <Сидоров,
средство для мытья окон>}.
Иванов
Петров
Сидоров
Кузнецов стиральный порошок зубная паста мыло пена для бритья туалетная вода средство для мытья окон отбеливатель
Рис. 12. График соответствия между покупателями и товарами в магазине
Свойства соответствия G
2
:
1. Не функциональное, т. к. один покупатель может купить несколько товаров.

18 2. Инъективное, т. к. один товар не может быть куплен несколькими покупателями.
3. Не всюду определенное, т. к. один из потенциальных покупателей может не найти нужного товара в магазине.
4. Не сюръективное, т. к. какие-то товары могут не купить.
5. Соответствие не является биективным.
1.6. Функции и отображения
Понятие функции является одним из основополагающих в математике.
Функция f – это функциональное соответствие, т. е. если
∈
f и
∈
f,
то y=z.
Примеры.
f
1
={<1,2>,<2,3>,} – функция.
f
2
={<1,2>,<1,3>,<2,4>} – не является функцией.
f
3
={2
+2x+1>| x – действительное число } – функция.
К функциям применим интуитивный принцип объемности, т. е. две функции f и g равны, если они состоят из одних и тех же элементов.
Область определения функции – это множество существует такое
, что
Область значения функции - это множество существует такое
, что
Если
А, то функция называется тотальной (всюду определенной),
если
, то частичной.
Если
А и
, то говорят, что функция f задана на множестве А
со значениями во множестве В и осуществляет отображение множества А во множество В (или устанавливает соответствие между множествами А и В).
Всюду определенное функциональное соответствие называется
отображением.
Такая функция обозначается следующим образом: f : A
→
B.
Чаще используется префиксная форма записи: b=f(a), где а – аргумент функции, а b – значение функции.
Примеры.
Рассмотрим функции, отображающие множество действительных чисел R во множество действительных чисел R: f : R
→
R.
1.
- инъективная, не сюръективная.
2.
- сюръективная, не инъективная.
3.
- биективная.

19
1.7. Отношения
1.7.1. Понятие отношения
Отношение – это пара вида
, такая что
, где
Ф – график, а М – множество между элементами которого установлено данное отношение.
Для бинарных отношений обычно используется инфиксная форма записи: x φ y для
. Отношение называется полным, если Ф=М
2
Примеры.
1. М – множество целых чисел.
Ф={<1,1>,<2,4>,<3,9>,<4,16>…}={|
и
} – отношение x
2
на множестве целых чисел.
2. М – множество действительных чисел.
Ф={|
и x=y} – отношение равенства на множестве действительных чисел.
3. М – множество действительных чисел.
Ф={|
,z>0 и x+z=y} – отношение “меньше чем (<)” на множестве действительных чисел.
На множестве действительных чисел также хорошо известны отношения ≤, >, ≤ , ≠.
1.7.2. Свойства отношений
1. Рефлексивность. Для всех х справедливо х φ х , или
, т. е.
график отношения включает в себя диагональный график.
2. Антирефлексивность. Для всех х не выполняется х φ х , или
3. Симметричность. Если х φ y, то y φ x, или Ф=Ф
-1
, т. е. график равен своей инверсии.
4. Антисимметричность. Если х φ y и х≠у, то не выполняется y φ x,
или
5. Асимметричность. Если х φ y, то не выполняется y φ x, или
6. Связность. Если х≠у, то х φ y или y φ x, или
7. Транзитивность. Если х φ y и y φ z, то х φ z, или
Примеры.
1. Прямая х параллельна прямой у в плоскости z. Отношение является рефлексивным, симметричным, транзитивным.
•
Рефлексивное, т. к. х параллельна самой себе и график отношения будет содержать пару .
•
Симметричное, т. к., если х параллельна у, то и у параллельна х, и график отношения будет содержать пары и .
•
Транзитивное, т. к. если х параллельна у , а у параллельна w, то х тоже будет параллельна w, т. е. =.

20 2. Быть подмножеством на семействе множеств( ) . Отношение является рефлексивным, антисимметричным, транзитивным, связным.
•
Рефлексивно, т. к. множество Х является подмножеством самого себя
•
Антисимметрично, т. к. если и
, то Х=Y.
•
Транзитивно, т. к.
и
, то
•
Связно, т. к. X,Y,Z U.
3. Быть подмножеством на семействе множеств ( ). Отношение является антирефлексивным, асимметричным, транзитивным, связным.
•
Антирефлексивно, т. к. не выполняется свойство рефлексивности и Х не является подмножеством самого себя при строгом включении.
•
Асимметрично, т. к. если и Х≠Y, то
•
Транзитивно, т. к.
и
, то
•
Связно, т. к. X,Y,Z U.
1.8. Отношения эквивалентности. Классы эквивалентности
1.8.1. Понятие отношения эквивалентности
Отношение, обладающее одновременно свойствами рефлексивности,
симметричности и
транзитивности,
называется
отношением
эквивалентности ().
Примеры.
1. Отношение равенства на множестве целых чисел есть отношение эквивалентности.
2. Отношение сравнимости по модулю натурального числа n на множестве целых чисел Z: х=y (mod n) тогда и только тогда, когда х-у делится на n. Это отношение рефлексивно на Z, т. к. для любого х-х=0
и, следовательно, делится на n. Это отношение симметрично, т .к., если х-у делится на n, то и y-x тоже делится на n. Это отношение транзитивно, т. к.,
если х-у делится на n, то для некоторого целого числа t
1
имеем х-у=t
1
n, а если y-z тоже делится на n, то для некоторого целого числа t
2
имеем у-z=t
2
n.
Отсюда x-z=(t
1
+t
2
)n, т. е. x-z – делится на n.
3. Отношение принадлежности к одной студенческой группе на множестве студентов института есть отношение эквивалентности.
1.8.2. Понятие класса эквивалентности
Классом
эквивалентности,
порожденным элементом х
,
называется подмножество множества Х, состоящее из тех элементов
,
для которых x φ y . Класс эквивалентности обозначается [x]: [x]={y|
и x
φ y}.
Примеры.

21 1. Отношение равенства на множестве целых чисел Z порождает следующие классы эквивалентности: для любого элемента
, т. е.
каждый класс эквивалентности состоит из одного целого числа х.
2. Отношение сравнимости по модулю натурального числа n на множестве целых чисел Z порождает следующие классы эквивалентности:
если
, то в этом же классе эквивалентности будут содержаться все числа вида a+kn, где k – целое число. Таким образом, числа 1, 2, 3, … n-1
порождают различные классы эквивалентности, которые можно обозначить
[1], [2], [3],…,[n-1]. Их называют классами вычетов по модулю n.
3. Для отношения принадлежности к одной студенческой группе классом эквивалентности является множество студентов одной группы.
1.8.3. Свойства отношения эквивалентности
1. xx – следует из свойства рефлексивности.
2. Если x y , то [x] = [y].
Доказательство свойства 2.
1. Пусть z
∈
[x]. Следовательно, z x. Если x y , то z y,
следовательно, z
∈
[y],
т.е. [x]
⊆
[y]
2. Пусть z
∈
[y]. Следовательно, z y. Если x y , то z x,
следовательно,
z
∈
[x],
т.е. [y]
⊆
[x].
Следовательно, [x] = [y].
1.8.4. Покрытия и разбиения множеств
Множество всех подмножеств множества Х называется множеством-
степенью или булеаном , обозначается P(X).
Пример.
Х={1,2,3}
P(X)={
∅
,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.
Покрытие множества Х – это любое подмножество множества Р(Х),
такое, что объединение входящих в него элементов совпадает с Х.
Пример.
П(Х) = {{1,2}, {1,3}, {2,3}}так как {1,2}
∪
{1,3}
∪
{2,3} = {1, 2 ,3}
Разбиением множества Х R(X) называется такое покрытие множества
Х, в котором элементы не пересекаются.
Примеры.
1. Х={1,2,3}. Тогда R(X)={{1,2},{3}}.
2. Пусть Х – множество студентов института. Тогда разбиением этого множества может являться совокупность студенческих групп.
Свойства :

22 1. Каждый элемент исходного множества Х принадлежит какому- либо из множеств, составляющих разбиение.
2. Каждый элемент исходного множества принадлежит строго одному из множеств, составляющих разбиение.
Теорема: Отношение эквивалентности разбивает множество, на котором оно определено на классы эквивалентности.
Доказательство:
1. Очевидно. х [x]
2. Предположим, что z
∈
[x] и z
∈
[y]. Тогда из x y и z y следует x y и по второму свойству отношения эквивалентности [x] = [y].
Если
ρ
отношение эквивалентности на множестве Х, то совокупность классов эквивалентности называется фактормножество множества М и обозначается Х/
ρ
. Фактормножество является подмножеством булеана Х/
ρ⊆
P(X).

1   2   3   4   5