ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 9367
Скачиваний: 93
11
Задача 2. Задано универсальное множество U
}
7
,
6
,
5
,
4
,
3
,
2
,
1
{
=
и множе-
ства
}
6
,
5
,
3
,
2
{
},
,
5
,
3
,
1
{
},
7
,
4
,
2
{
=
=
Z
Y
X
. Перечислить элементы множества
X
Y
Z
W
∪
∩
=
)
(
. Записать булеан множества
Х
и какое-либо разбиение
множества
Y
.
Решение. Для нахождения множества
W
выполним операции над множе-
ствами в следующем порядке:
1)
}
7
,
4
,
1
{
}
6
,
5
,
3
,
2
{
\
}
7
,
6
,
5
,
4
,
3
,
2
,
1
{
\
=
=
=
Z
U
Z
- по определению опе-
рации дополнения;
2)
}
7
,
1
{
}
7
,
5
,
3
,
1
{
}
7
,
4
,
1
{
=
∩
=
∩Y
Z
- по определению операции пере-
сечения множеств;
3)
}
7
,
4
,
2
,
1
{
}
7
,
4
,
2
{
}
7
,
1
{
)
(
=
∪
=
∪
∩
=
X
Y
Z
W
.
Итак,
}.
7
,
4
,
2
,
1
{
=
W
В булеан множества
Х
включаем пустое множество, само множество
Х
(см. свойства включения в 1.1.3), все одноэлементные подмножества, все
двухэлементные подмножества множества Х:
B
{
=
)
(
X
∅
,
}
}
7
,
4
,
2
{
},
7
,
4
{
},
4
,
2
{
},
7
,
2
{
},
7
{
},
4
{
},
2
{
.
Для множества
Y
построим разбиение, состоящее из трех блоков
R
}
,
,
{
)
(
3
2
1
Y
Y
Y
Y
=
, например, таким образом:
}.
5
{
},
3
{
},
7
,
1
{
3
2
1
=
=
=
Y
Y
Y
Определение разбиения выполняется: множества
3
2
1
,
,
Y
Y
Y
не пусты, не
пересекаются (
=
∩
2
1
Y
Y
∅
,
=
∩
3
2
Y
Y
∅
,
=
∩
2
1
Y
Y
∅
), их объединение равно
множеству Y:
}.
7
,
5
,
3
,
1
{
}
5
{
}
7
,
3
,
1
{
}
5
{
})
3
{
}
7
,
1
({
)
(
3
2
1
3
2
1
=
=
∪
=
∪
∪
=
∪
∪
=
∪
∪
Y
Y
Y
Y
Y
Y
Задача 3. Упростить выражение, пользуясь законами алгебры множеств:
B
C
B
B
A
A
∪
∪
∪
∪
∩
)
(
)
(
.
Решение. Договоримся считать, что операция пересечения множеств
имеет более высокий приоритет, чем объединение множеств, т.е., если нет
скобок, изменяющих приоритет, вначале выполняется пересечение, а затем
объединение. Пользуясь этим правилом и законом ассоциативности, опреде-
лим порядок действий:
)
)
((
))
(
(
2
3
1
B
C
B
B
A
A
∪
∪
∪
∪
∩
.
Выполним преобразования, указывая номер закона (табл. 1.1) над знаком
равенства:
1)
B
A
B
A
B
A
A
A
B
A
A
∩
=
∩
∪
∅
=
∩
∪
∩
=
∪
∩
1
1
5
)
(
)
(
)
(
)
(
;
12
2)
B
C
B
B
C
B
B
C
B
C
B
∪
=
∪
∪
=
∪
∪
=
∪
∪
7
4
3
)
(
)
(
)
(
;
3)
3
4
3
)
)
((
)
(
)
(
)
(
)
(
=
∪
∪
∩
=
∪
∪
∩
=
∪
∪
∩
C
B
B
A
C
B
B
A
B
C
B
A
.
))
(
(
9
C
B
C
B
A
B
∪
=
∪
∩
∪
=
Ответ:
C
B
∪
.
1.1.9. Контрольные вопросы и упражнения
1. Вставьте обозначения числовых множеств:
- множество натуральных чисел;
- множество целых чисел;
- множество рациональных чисел;
- множество действительных чисел.
2. Вставьте пропущенный знак
∈
или
∉
:
117
____
N
; 22,4
____
Z
; 4/3
____
Q
;
2
____
Q
;
75
____
R
;
π
____
Z
.
3. Принадлежит ли множеству корней уравнения
0
6
5
2
=
+
− x
x
число
3
−
=
x
?
4. Какими способами можно задать множество?
5. Запишите множество действительных корней уравнения
0
4
3
=
+
x
.
Как записать ответ, если требуется найти множество целых корней этого
уравнения?
6. Что такое подмножество данного множества? Какой символ использу-
ется для записи “множество
А
является подмножеством множества
В
”? Запи-
шите его:
А
____
В
.
7. Вставьте пропущенный символ
∈
или
⊆
:
1 ____ {1,2,3};
{1}____ {1,2,3};
∅ ____ {1,2,3}; {2,3}____ {1,2,3}.
8. Обведите кружком номер правильного ответа:
Множество всех элементов, принадлежащих как множеству
А
, так и
множеству
В
, называется:
13
1) объединением множеств
А
и
В
;
2) пересечением множеств
А
и
В
;
3) разностью множеств
А
и
В
.
9. Вставьте пропущенные знаки операций над множествами:
}
,
,
{
c
b
a
___
}
{
}
,
,
{
b
e
b
d
=
;
}
,
,
{
c
b
a
___
}
,
,
,
{
}
,
{
d
c
b
a
d
c
=
;
}
,
,
{
c
b
a
___
}
,
{
}
,
{
c
b
d
a
=
.
10. Что такое булеан множества
Х
?
11. Является ли булеаном множества
}
,
,
{
c
b
a
система подмножеств
{
}
}
{
},
{
},
{
c
b
a
?
12. Является ли разбиением множества
}
,
,
{
c
b
a
система подмножеств
{
}
}
,
{
},
,
{
},
,
{
c
a
c
b
b
a
?
13. Нарисуйте диаграмму Эйлера – Венна для множества
)
(
C
B
A
∪
∩
.
Нарисуйте диаграмму для
)
(
)
(
C
A
B
A
∩
∪
∩
. Сравните заштрихованную
часть на обеих диаграммах. Как называется закон, который Вы проиллюстри-
ровали?
14. Нарисуйте диаграммы Эйлера – Венна для левой и правой частей за-
кона де Моргана. Сравните их.
15. Запишите законы алгебры множеств. Запомните их названия.
1.2. Бинарные отношения
1.2.1. Декартово произведение множеств
Декартовым произведением
Y
X
×
двух множеств
X
и
Y
называется
множество всех упорядоченных пар (
x,y
) таких, что
X
x
∈
, а
Y
y
∈
.
Пример 1. Пусть
}
1
,
0
,
1
{
},
2
,
1
{
−
=
=
Y
X
. Тогда
{
}
)
1
,
2
(
),
0
,
2
(
),
1
,
2
(
)
1
,
1
(
),
0
,
1
(
),
1
,
1
(
−
−
=
×Y
X
,
{
}
)
2
,
1
(
),
1
,
1
(
),
2
,
0
(
),
1
,
0
(
),
2
,
1
(
),
1
,
1
(
−
−
=
× X
Y
.
Очевидно, что
X
Y
Y
X
×
≠
×
, т.е. для операции декартова произведе-
ния множеств закон коммутативности не выполняется.
Наглядно декартово произведение множеств можно представить в виде
графика. На рис. 1.7 звездочками отмечены элементы множества
}.
4
,
2
{
}
3
,
2
,
1
{
×
=
×Y
X
Декартовым произведением множеств
n
X
X
X
,
,
,
2
1
…
будем называть
множество
n
X
X
X
×
×
×
…
2
1
всех упорядоченных наборов
)
,
,
,
(
2
1
n
x
x
x
…
таких, что
.
,
,
2
,
1
,
n
i
X
x
i
i
…
=
∈
14
1.2.2. Определение бинарного отношения
Пусть среди трех людей (назовем их Андрей, Василий и Сергей) двое
знакомы друг с другом (Андрей и Василий) и знают третьего (Сергея), но тот
их не знает. Как описать отношения между этими людьми? Имеем множество
Х
={
А
.
В
,
С
}, из элементов которого составлены упорядоченные пары: (
А
,
В
),
(
В
,
А
), (
А
,
С
), (
В
,
С
), т.е. выделено некоторое подмножество декартова произве-
дения
.
X
X
×
Это подмножество и описывает связи между элементами мно-
жества
Х
.
Определение. Говорят, что на множестве
X
задано бинарное отношение
R
,
если задано подмножество декартова произведения
X
X
×
(т.е.
X
X
R
×
⊆
).
Пример 2. Пусть
}.
4
,
3
,
2
,
1
{
=
X
Зададим на
Х
следующие отношения:
}
,
,
)
,
{(
y
x
X
y
x
y
x
T
=
∈
=
– отношение равенства;
}
1
,
,
)
,
{(
−
=
∈
=
y
x
X
y
x
y
x
P
– отношение предшествования;
x
X
y
x
y
x
Q
,
,
)
,
{(
∈
=
делится на
}
y
– отношение делимости.
Все эти отношения заданы с помощью характеристического свойства.
Ниже перечислены элементы этих отношений:
{
}
;
)
4
,
4
(
),
3
,
3
(
),
2
,
2
(
),
1
,
1
(
=
T
{
}
;
)
4
,
3
(
),
3
,
2
(
),
2
,
1
(
=
P
{
}
.
)
1
,
1
(
),
1
,
2
(
),
2
,
2
(
),
1
,
3
(
),
3
,
3
(
),
1
,
4
(
),
2
,
4
(
),
4
,
4
(
=
Q
Тот факт, что пара (
x
,
y
) принадлежит данному отношению
R
, будем за-
писывать:
R
y
x
∈
)
,
(
или
xRy
. Например, для отношения
Q
запись 4
Q
2 озна-
чает, что 4 делится на 2 нацело, т.е.
.
)
2
,
4
(
Q
∈
Областью определения
R
D
бинарного отношения
R
называется мно-
жество
.
}
)
,
(
{
R
y
x
x
D
R
∈
=
Областью значений
R
E
называется множество
.
}
)
,
(
{
R
y
x
y
E
R
∈
=
R
E
15
Так, для отношения
Р
из примера 2 областью определения является мно-
жество
}
3
,
2
,
1
{
=
P
D
, а областью значений –
}
4
,
3
,
2
{
=
P
E
.
1.2.3. Способы задания бинарного отношения
Бинарное отношение можно задать, указав характеристическое свойство
или перечислив все его элементы. Существуют и более наглядные способы
задания бинарного отношения: график отношения, схема отношения, граф
отношения, матрица отношения.
График отношения изображается в декартовой системе координат; на
горизонтальной оси отмечается область определения, на вертикальной – об-
ласть значений отношения; элементу отношения (
х
,
у
) соответствует точка
плоскости с этими координатами. На рис. 1.8, а приведен график отношения
Q
примера 2.
Схема отношения изображается с помощью двух вертикальных прямых,
левая из которых соответствует области определения отношения, а правая –
множеству значений отношения. Если элемент (
х
,
у
) принадлежит отношению
R
, то соответствующие точки из
R
D
и
R
E
соединяются прямой. На рис. 1.8,
б приведена схема отношения Q из примера 2.
Граф отношения
X
X
R
×
⊆
строится следующим образом. На плоско-
сти в произвольном порядке изображаются точки – элементы множества
Х
.
Пара точек
х
и
у
соединяется дугой (линией со стрелкой) тогда и только тогда,
когда пара (
х
,
у
) принадлежит отношению
R
. На рис. 1.9, а приведен граф
отношения
Q
примера 2.
Матрица отношения
X
X
R
×
⊆
– это квадратная таблица, каждая
строка и столбец которой соответствует некоторому элементу множества
Х
.
На пересечении строки
х
и столбца
у
ставится 1, если пара
R
y
x
∈
)
,
(
; все
остальные элементы матрицы заполняются нулями. Элементы матрицы нуме-
руются двумя индексами, первый равен номеру строки, второй - номеру