Файл: Учебнометодический комплекс по дисциплине Дискретная математика Основная образовательная программа 010800 Механика и математическое моделирование.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.10.2024
Просмотров: 28
Скачиваний: 0
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Операции над множествами
1. Объединение
A B = {x x A или x B}.
А
В
2. Пересечение
A B = {x x A и x B},
A B = AB.
А
В
3. Вычитание (из A вычесть B)
A \ B = {x x A и x B}.
А
В
4. Симметрическая разность
A B = (A \ B) (B \ A) =
= (A B) \ (A B)
А
В
5.
A
x
x
A
U
A
\
- дополнение множества A (до универсального множества U).
А
U
1.28. U = {a, b, c, d, e, f, g, h, i, j}, A = {a, b, c, h, i}, B = {a, c, e, f, i}, C = {a, d, e, h, j}. На диаграммах Венна 1 и 2 типа расставить все элементы.
1.29. Дана пара множеств X и Y, которые образованы тремя произвольными множествами A, B и C при помощи операций над ними. На диаграммах Венна 1 и 2 типа заштриховать множества X и Y и определить отношения между ними. Варианты: X = Y, X Y, X Y или X и Y не сравнимы. а) X = A \ (B C), Y = ( A \ B) \ C, б) X = A (B \ C), Y = ( A B) \ C, в) X = ( A \ B) C, Y = A (C \ B), г) X = ( A B) C, Y =( A B) C.
Пример: X =( A C) B, Y =( A B)
C .
Диаграмма Венна I типа
А
В
C
+
+
+
+
0 0
0 0
А
В
C
+
+ +
0 0 0
+
0
А
В
C
А
В
C
Диаграмма Венна II типа
A
A
B
0 0 +
0 +
0
B
+
+
C
C
C
C
A
A
B
0
+
+ 0
B
+
+ 0 0
C
C
C
C
A C – “+”
B - “0”
A B – “+”
C
- “0”
Результат: X Y
1.30. На диаграммах Венна 1 и 2 типа заштриховать множества: а)
C
B
A
\
, б)
C
B
A
\
, в)
C
B
A
, г)
C
B
B
A
\
, д)
C
A
C
B
\
, е)
C
B
A
\
, ж)
D
C
B
A
\
(диаграмма Венна 2 типа), з)
D
B
C
A
\
(диаграмма Венна 2 типа), и)
B
C
A
\
, к)
C
B
C
A
\
, л)
C
B
A
, м)
C
B
B
A
\
\
, н)
C
B
A
\
, о)
C
A
B
A
\
, п)
C
B
A
, р)
C
B
A
, с)
C
B
A
1.9. Законы алгебры множеств
Пусть задано универсальное множество U. Тогда A, B, C U.
1. Законы коммутативности
1.1.
A
B
B
A
1.2.
A
B
B
A
1.3.
A
B
B
A
A
B
A
B
A
B
B
A
B
A
B
A
\
\
2. Законы ассоциативности
2.1.
C
B
A
C
B
A
C
B
A
2.2.
ABC
C
B
A
C
B
A
C
B
A
2.3.
C
B
A
C
B
A
3. Законы дистрибутивности
3.1.
BC
AC
C
B
C
A
C
B
A
3.2.
C
B
C
A
C
B
A
4. Законы де Моргана
4.1.
B
A
B
A
4.2.
B
A
B
A
5. Законы поглощения
5.1.
A
A
B
A
5.2.
A
A
B
A
6. Законы идемпотентности
6.1.
A
A
A
6.2.
A
A
A
7. Закон инволютивности
A
A
8. Свойства нуля и единицы
8.1.
U
8.4.
U
8.2.
A
A
8.5.
A
U
A
8.3.
A
8.6.
U
U
A
9. Свойства дополнения
9.1.
U
A
A
9.2.
A
A
10. Выражение для разности
B
A
B
A
\
Для упрощения записи формул скобки можно опускать, придерживаясь следующего правила: пересечение сильнее всех остальных операций (сам знак пересечения можно опустить).
Например,
C
B
A
C
B
A
C
B
A
C
AB
C
B
A
Закон дистрибутивности 3.1 можно записать следующим образом:
BC
AC
C
B
A
Пример.
При помощи законов алгебры множеств доказать справедливость тождества:
C
B
A
BC
AC
(*)
Y
X
Y
X
X
Y
Y
X
X
Y
Y
X
Y
X
\
\
Используя закон де Моргана и закон дистрибутивности, получим
BC
A
C
B
A
BC
C
BC
A
C
AC
B
AC
BC
C
A
C
B
AC
BC
AC
BC
AC
BC
AC
X
X
C
BC
BC
C
C
AC
,
,
Аналогично преобразуем правую часть
BC
A
C
B
A
C
B
A
B
A
C
B
A
Так как обе формулы
BC
AC
и
C
B
A
задают одно и тоже множество, то они тождественно равны. Тождество (*) выполнено.
1.31. Путем алгебраических преобразований упростить а)
B
B
A
б)
B
B
A
в)
A
B
A
г)
B
B
A
д)
B
A
B
A
AB
е)
D
C
D
B
C
A
B
A
ж)
A
AD
ABCDE
ABD
з)
CD
C
B
C
A
D
ABC
и)
B
A
A
к)
AB
A
л)
AB
B
A
м)
AB
B
A
1.10. Прямое произведение множеств
Определение. Прямое (декартово) произведение множеств A и B
B
b
A
a
b
a
B
A
,
,
- множество упорядоченных пар
b
a,
, где a – элемент множества A, а b – элемент множества B.
Определение. Кортеж длины n – это упорядоченный набор n элементов
n
a
a
a
,
,
,
2 1
Определение.
Множество
n
i
A
a
a
a
a
A
A
A
i
i
n
n
,
1
,
,
,
,
2 1
2 1
называется прямым произведением n множеств.
Лемма.
B
A
B
A
Теорема.
k
k
A
A
A
A
A
1 2
1
Следствие.
k
k
k
A
A
A
A
раз
1.32. Найти множество D и его мощность, если A = {a, b, c}, B = {0,1}, C
= {+, -} а) D = A B; б) D = B
2
C; в) D = A B C;
1.33. Написать несколько элементов множества D и найти его мощность:
D = A
4
B
5
C
3
Глава 2. Отношения
Понятие отношения является одним из наиболее общих понятий математики.
Отображения и функции являются частными случаями отношений. Что касается дискретной математики, все ее разделы, рассматриваемые в данной работе, так или иначе связаны с изучением отношений, а теория графов полностью посвящена изучению их свойств специфическими методами.
2.1. Отношение. Композиция отношений. Свойства отношений
Определение. Отношением R из множества A в множество B называется подмножество прямого произведения A
B:
R
A
B
(мы рассматриваем только бинарные отношения, т. е. отношения для двух множеств). Для отношений используется следующая форма записи:
aRb, если <a,b>
R
A
B.
Определение. Если A=B, то отношение R называется отношением на
множестве A. Вместе с любым отношением на множестве A мы также будем рассматривать следующие отношения:
универсальное отношение: U= A
B,
дополнение отношения:
R
U
R
\
,
обратное отношение:
}
,
:
,
{
:
1
R
a
b
b
a
R
,
тождественное отношение:
}
:
,
{
A
a
a
a
I
Определение. Композицией двух отношений
B
A
R
1
и
C
B
R
2
назовем отношение
}
,
:
:
)
,
{(
2 1
2 1
c
bR
b
aR
B
b
c
a
C
A
R
R
Композиция отношений на множестве A является отношением на множестве A.
Определение. Степенью отношения R на множестве A называется его композиция с самим собой:
раз
n
n
R
R
R
Вводя также определение нулевой и первой степени отношения, получим:
R
R
R
R
R
R
R
R
I
R
n
n
1 2
1 0
,
,
,
,
Теорема. Если некоторая пара <a,b> принадлежит какой-либо степени отношения R на множестве A мощности n, то эта пара принадлежит и степени
R
не выше n -1.
Следствие.
1 1
1 2
)
,
(
n
i
i
i
i
R
R
n
A
A
R
Свойства отношений на множестве
Пусть R – отношение на множестве A:
2
A
R
Рассмотрим важнейшие свойства отношений на множестве.
R рефлексивно, если
R
a
a
A
a
,
,
R антирефлексивно, если
R
a
a
A
a
,
,
R симметрично, если
R
a
b
R
b
a
,
,
,
R антисимметрично, если
b
a
R
a
b
R
b
a
A
b
a
)
,
,
,
(
:
,
,
R транзитивно, если
R
c
a
R
c
b
R
b
a
A
c
b
a
,
)
,
,
,
(
:
,
,
,
R полное или линейное, если
)
,
(
)
,
(
,
R
a
b
или
R
b
a
A
b
a
,
Теорема. Пусть R – отношение на множестве A:
2
A
R
. Тогда:
R рефлексивно
R
I
R антирефлексивно
I
R
R симметрично
1
R
R
R антисимметрично
I
R
R
1
R транзитивно
R
R
R
R полно
U
R
I
R
1
2.2. Функции
Понятие функции – одно из основополагающих в математике. Под функцией
B
A
f
:
мы будем понимать отношение из A в B, обладающее свойством однозначности.
Определение функции
Пусть f – отношение из A в B, такое, что
c
b
f
c
a
f
b
a
)
,
,
,
(
, тогда отношение называется функцией из из A в B и обозначается:
B
A
f
:
или
B
A
f
Если
f
b
a
,
, то используют обозначение
)
(a
f
b
, при этом a называют аргументом функции, а b – значением функции.
Функция
B
A
f
:
называется:
инъективной, если из
)
(
1
a
f
b
и
)
(
2
a
f
b
следует
2 1
a
a
;
сюръективной, если
)
(
:
a
f
b
A
a
B
b
;
биективной или взаимнооднозначной, если она инъективная и сюръективная.