МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ
БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ОБРАЗОВАНИЯ
«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ»
СБОРНИК ЗАДАЧ
ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
Учебно-методическое пособие для вузов
Составители:
Т.М. Леденева, С.Ю. Балашева
Воронеж
Издательский дом ВГУ
2016
Стр.1
1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
Ключевые понятия: множество, подмножество,
булеан,
отношения включения и равенства множеств, операции над множествами
и их свойства, покрытие и разбиение, мощность множества, счетные
множества, равномощные множества, эквивалентные множества,
формула включений и исключений.
1.1. Операции над множествами и их свойства
Задача 1.1.1. Пусть заданы множества
{
−
−
Найдите
здесь
= {
множества
Bx x ≤=≤ и x целое число кратное 3}.
A B, A B, A\ B,B\ A∩∪
,
.
A 2, 4, 6, 8,10,12},
является множество
= {
U 1, 2,3, 4,5,6,7,8,9,10,11,12},
= {
Ax:1 12x ≤=≤ и x четное целое число},
{ :1 12
Постройте
характеристические векторы исходных и искомых множеств.
Решение. Прежде всего, заметим, что универсальным множеством
тогда
B 3, 6, 9,12}. Пересечение множеств AB∩
содержит элементы, которые одновременно принадлежат обоим
множествам, т.е.
из U , которые встречаются в A или в B , т.е. ∪= {AB 2,3,4,6,8,9,10,12}.
Множество A\B содержит те элементы из A , которые не принадлежат B ,
т.е.
A () ()BA\ B B\ A=∪
Найдем
AB 0,0,0,0,0,1,0,0,0,0,0,1 AB 0,1,1,1,0,1,0,1,1,1,0,1 ,
AB\ ()0,1,0,1,0,0,0,1,0,1,0,0 , ()\ 0,0,1,0,0,0,0,0,1,0,0,0 ,
∩= (), ()
=
∪=
BA=
AB 0,1,1,1,0,0,0,1,1,1,0,0 .
= ()
Задача 1.1.2. Выясните взаимное расположение множеств
3
A\ B = {2,4,8,10}. Аналогично,
= {
B\ A = { }3,9 . Учитывая,
, получим AB 2,3,4,8,9,10}.
Выпишем характеристические векторы исходных множеств
() (
0,1,0,1,0,1,0,1,0,1,0,1 ,
AB 0,0,1,0,0,1,0,0,1,0,0,1== .
)
что
AB {6, }12∩= . Объединение множеств содержит элементы
Стр.3
принадлежит множеству A BA C∩∪ ∩ . Итак, пусть ()x AB C∈∩ ∪ , тогда
x A∈ и x BC
∈∩ ∪ ∩ . Если x C∈ , то x AC
Таким образом, ()A BC AB A
Теперь
x AB A
докажем,
x AB A
C
∩∪ ⊆ ∩ ∪ ∩ .
что
∈∩ ∪ ∩ . Если x AB
x A∈ и x BC
A BA C A B
A ()
C
Отсюда следует, что x A∈ и x BC
∩∪ ∩ ⊆ ∩ ∪ . () Таким
BC AB A
C
∈∪ . Если x B∈ , то x AB
C
∈∩ , и тогда, x AB A
C
A BA C A B
∈∪ , т.е. ()x AB C∈∩ ∪ . Если x AC
C
∈∩ , а, следовательно,
∈∩ ∪ ∩ .
C
∩∪ ∩ ⊆ ∩ ∪ . () Пусть
∈∩ , то x A∈ и x B∈ . Отсюда следует, что
∈∩ , то x A∈ и x C∈ .
∈∪ , т.е. ()x AB C∈∩ ∪ . Итак,
образом,
получили,
∩∪ ⊆ ∩ ∪ ∩ и ∩∪ ∩ ⊆ ∩ ∪ , а это означает,
A BA C A B
()
C
что эти два множества равны.
Замечание: Решение подобных задач можно оформлять в более формализованном
виде, используя скобки { для системы высказываний, объединенных союзом «и», [ − для
системы высказываний, объединенных союзом «или».
Задача 1.1.6. Докажите следующее утверждение: если X Y⊆ , то
YX⊆ .
Решение. Чтобы доказать YX⊆ , выберем произвольный элемент
x Y∈ и покажем, что x X∈ . Итак,
xY xU xX X xX
xY
∈
∉
xY
∈
∈
∈∪
xY
xX
xY xY
⊆
∈∈
∈∈
XY
∈
xY
∈
∈
xE
xX
∈
xX x X
∈
xY
∈
Таким образом, YX⊆ , что и требовалось доказать.
Задача 1.1.7. Докажите, что () (
A\\ \ \ \
BC A C B C) .
=
)
6
(
Решение. Заметим, что подобные задачи можно решать как на основе
определения, так и с помощью равносильных преобразований. Используя
∉
∈
∈
∈∈
xX xX
xY xY
xX xX
∈∈
что
Стр.6
свойства операций над множествами, покажем, что правую часть
выражения с помощью равносильных преобразований можно свести к
левой.
(A C) \ (B C\ )( ) ( )( ) ( )( ) (
=∩ ∩C BA C() ( ∩ ∩ =∩ ∩C BA A
\
A
∪
A CB C
A
=∩ ∩ =∩ ∩ =
Задача 1.1.8. Упростите выражение
A BY X A
C) () ( ∩∅ =∩ ∩B
(\) \
A CB C
∪
Y BY Y X
() () () ()
преобразований
() () () ()
()()
X
B YX A
Y B
Y YX
=∩ ∩ ∩ ∪() ()() ()
B
=∩ ∩ ∩ ∪ ∩ ∩ = ∩ =
ΑΒ
AB Y X Y ( AB X )
YX Y
YA B
(() ()) Y
X A
X
=∩
=∩
⊆∩
CB X A
XC A B
CA B
∩ ∪ ∪ =
∩ A∩ ∪ =
B
A∩ ∩ ∩ ∪ ∩∪ ∩∪∩ =
=∩ ∩ ∩ ∪
U Y .
Задача 1.1.9. Решите систему уравнений относительно множества X
\
и укажите условия совместности системы.
Решение. Построим множества ,,A BX , находящиеся в общем
положении, и множество C , которое, с одной стороны, удовлетворяет
условию CA B⊆∩ , а с другой – находится в общем положении с
множеством X (рис. 1.2). Итак, имеем
A 1,2,3,5,6,7}, B 2,3, 4,6,7,8},
= {
C { }3,7=
, X 5,6,7,8,9}.
= {
Проанализируем систему уравнений. Рассмотрим левую и правую
= {
,
A = {1, }3,6 , B { }3,6=
, C { }3= , X { }6,9=
7
. Для второго уравнения
части первого уравнения. CB 2,4,6,8} XA {5, }6,7∩= . По условию эти
множества равны, следовательно, списки элементов 2,4,5,7,8 пусты. Тогда
получим
= {
∩ ∩ ∩ ∪ ∩∪ ∩∪∩ .
Решение. Упростим выражение с помощью равносильных
AC B A B C A BC
= ∩ ∩∩ = ∩ ∩∪ = ∩ ∩∪ =
) ()∪∅ =
A CB C)
C
Стр.7
системы XC =
то списки элементов 3 и 9 пустые, поэтому A { }1,6=
\6 { },9 AB { }3,6∩= . Поскольку данные множества равны,
, B { }6= , C =∅ .
,
Поскольку C =∅ , то последнее соотношение в системе выполняется
всегда. Таким образом, решением системы является множество
1
3
2
X { }6= .
4
A
C
B
7
5
X
Рисунок 1.2 − Множества ,, ,
8
9
A BC X находятся в общем положении
С другой стороны, легко проверить, что X B= является решением
заданной системы. Если C =∅ и BA⊆ , то CA B⊆∩ . Пусть, например,
B { }b= ,
A { },ab=
CB \B C b==
{ }, XC\ X b== ,
{ } CX { },a b A
B
образом, все соотношения системы удовлетворяются, т.е. множество X B=
является решением исходной системы при выполнении условий BA⊆ ,
C =∅ .
Задача 1.1.10. Пусть BA C⊆⊆ . Найдите множество X ,
удовлетворяющее системе уравнений
A XB
A XC.
∩=
∪=
8
, где ,ab − списки элементов. Пусть XB { }b== , тогда
{ } A \ Xb= , ∩= = ∩ . Таким
6
Стр.8
Решение. Из первого соотношения следует, что BX⊆ ,
следовательно, это множество можно представить в виде XBX′=∪ ,
причем BX′∩=∅. Рассмотрим
A XA B∩ ∪ = ∩ ∪ ∩ = ∪ ∩ .
⊆
∩= ′′ ′
()
BA
X A
B
A
X B
Подставим XBX′=∪ во второе уравнение системы
() (
A XA B∪ ∪ = ∪ ∪ = ∪ = .
∪= ′′ ′X C
X A
Таким образом, имеем
A X,
⊆
A C
откуда можно заключить, что X C\ A. Окончательно, ()XB C \ A=∪ .
∩=′ ∅
′ =
Задачи и упражнения
1. Перечислите элементы множеств
а) {
xx:
:
б) {:, }2 ;
2
xx положительное четное целое число меньшее
в) {xx целое и x−< ;100}
{xx и xx
− гласная буква};
−
г) :61 0∈+ − = };
2
д) :6 {xx и xx 1∈+ − = 0}.
2
2. Опишите следующие множества с помощью характеристического
свойства:
а) {
3,6,9,12,15,18,21,24};
б) {1,1,2,3,5,8,13,21,...};
в) {1, 4,9,16,25,36,...};
г) {2,5,8,11,...};
д) {11 2 358 13
, , ,,,, ,... ;
}
д) 11 1
.
1,,, ,...
35 7
9
B X A
BA
)
⊆
A
X
По условию полученное выражение равно B , но тогда A X ′∩=∅.
Стр.9
3. Установите истинность или ложность каждого из следующих
утверждений:
а) , ,
б) { } {
= {
= {
в) ∅= { }∅ .
4. Определите булеан ()Aβ множества A , если
а)
A a,b,c}; б) A a,b,c}}; в) A { { }}
= { {
5. Определите ()Aβ , если
а)
A a,b,c}; б) A a,b,c}}; в) A { { }}
6. Определите ()ββ , если()A
{ { }}
= { {
,
.
A , ,..., nAA , таких что
8. Наследником множества A называется множество
Определите наследников следующих множеств:
а) ∅, б) { }∅ , в)
{ { }}∅∅,
An n
3:
=∈ и n ≥
−
−
4 An n=∈ ,} =∈ и n ≤
2
},
{2:
An:100}.
{
n
.
9. Пусть заданы следующие подмножества целых чисел
{
С помощью операций над множествами выразите следующие
множества через ,,A BC :
а) {
б) { nn и n∈≥
− −
6:
−−10,8,6,4,2,0,2,4,6,8,10};
2};
−
в) {−−−9, 7, 5, 3, 1,1,3,5,7,9}.
подмножества A pq r s , B ,, }rt v Cp,, },
= {
,
= s t u . Найдите элементы
{
A BA C∪∩ , A BC
\ ) ∪∪ .
следующих множеств:
B C∩ , A C∪ , A B∪ , B C , () (
10
10. Пусть на универсальном множестве U p qr s t uv w} заданы
= { ,, },
= { ,, ,
, ,
,
,
A { }A∪ .
A AA A
12 1
...
n
A AAn
...
== = .
= a, b,c .
= a, b,c .
а) A=∅; б) A=∅ ∅ ; в) A { }0,1=
7. Докажите, что для любых множеств 12
⊆⊆ ⊆ ⊆ , справедливо 12
∅⊆∅∅⊂∅∅∈∅∅⊆ ∅∈ ( A − произвольное множество);
} { } {
,
A,
2 1, 2,3,4,5 , 2 1, 2,3, 4,5∈⊆ ;
}
A
Стр.10