Сборник задач и упражнений с решениями по разделу математики
"Дискретная математика" содержит краткий курс теоретического материала, решение типовых задач, задачи для самостоятельного решения по темам "Теория множеств. Действия над множествами", "Теория графов". Может применяться для проверки текущих и итоговых знаний по данным темам.
Сборник задач и упражнений с решениями по разделу математики Дискретная математика.doc
Государственное образовательное учреждение среднего
профессионального образования
Губернский колледж города Похвистнево
Элементы теории множеств и теории
графов
Сборник задач и упражнений с решениями по разделу математики
"Дискретная математика"
Рассмотрено и одобрено ПЦК математических и
естественнонаучных дисциплин в качестве учебного пособия
для студентов среднего профессионального образования 2011 1. Элементы теории множеств
1.1 Теоретикомножественные операции
По определению Г. Кантора, основоположника теории множеств,
множество есть любое собрание определенных и различимых между
собой объектов нашей интуиции или интеллекта, мыслимое нами как
единое целое. Между отдельными объектами и множествами существует
отношение принадлежности. Если предмет х принадлежит множеству А,
то это записывают в виде хА, если не принадлежит множеству А, то
пишут хА.
Для обозначение множества служит пара фигурных скобок {….},
внутри которых перечисляются элементы множества.
Существует три способа задания множества:
перечисление
описание, порождающие процедуры. Во втором случае элементы
множества определяются по заданному закону (правилу). Например,
А={x|(утверждение об х)}, которое читается как: “А есть множество
таких элементов х, для которых (утверждение об х) верно”. Или можно
записывать и так: А={x|P(x)}, которое читается как “А есть множество
таких элементов х, которые обладают свойством Р”.
Порождающей процедурой
называется способ получения
элементов множества из уже полученных элементов. Например,
множество А всех целых чисел, являющихся степенями числа 2 может
быть представлено порождающей процедурой, заданной двумя
правилами, называемыми рекурсивными или индуктивными:
.Ax2то
,Ax
)б;A1)a
Множество, не содержащее ни одного элемента, называется пустым
множеством и обозначается символом .
Между различными множествами может существовать отношение
включения, как отношение “быть подмножеством”. Множество А
является подмножеством В, если любой элемент множества А
принадлежит множеству В. Это определение записывают в виде АВ, где
символ означает включение. Для подмножеств справедливо свойство
рефлексивности (АА) и транзитивности [(АВ и ВС)АС]. Кроме
того, для любого множества А справедливо А.
тех же элементов, т.е. АВ и ВА.
Если А – конечное nэлементное множество, тогда имеется ровно
2n различных подмножеств, составленное из элементов множества А,
включая несобственные подмножества и А.
Два множества называются равными, если они состоят из одних и
если
Множество всех подмножеств данного множества А называется
степенью множества А или булеаном (А).
Если при некотором рассмотрении участвуют только
подмножества некоторого фиксированного множества I, то это самое
большое множество называется универсальным (полным) множеством и
графически обозначается в виде точек прямоугольника, отдельные
области которого обозначают различные подмножества I. Такое
изображение множеств называется диаграммой Эйлера – Венна.
Основные операции над множествами:
Объединение: АВ={x|xA или xB};
Пересечение: АВ={x|xA и xB};
Разность: А\В={x|xA и xB};
Симметрическая разность: АВ=(А\В)(В\А);
Дополнение: A =I\A={x|xI и xA}.
Система множеств X={X1, X2,….Xn} называется разбиением
множества А, если она удовлетворяет следующим условиям:
AX i
n
1i
XiX и XA;
XiX, XjX и XiXj=;
Свойства операций пересечения и объединения являются
двойственными при замене знаков на , на I и наоборот, поэтому
основные тождества и законы алгебры множеств можно записать
следующим образом:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
A
A
,
IAA
,
IA
I
I ,
AAA
AA .
ABBA
)CB(AC)BA(
)CA(C)BA(
A)BA(A
A
A
ABBA
)CB(AC)BA(
)CA(C)BA(
A)BA(A
A
A
;
AIA
AA
A
I
AAA
A
1
A
1
)CB(
)CB(
A
A
A
2
A
2
;
;
;
,
,
A
2
1
;
n
.
n
,
n
1
n
;
A
2
.
,
,
;
Пример 1. Задать различными способами множество А всех четных
чисел 2, 4, 6, …., не превышающих 1000.
Решение. 1. Перечислением: А={2, 4, 6, 8, 10, …, 998, 1000};
1. Описанием: А={x|xN и х/2N,
(N – множество
N1000};
натуральных чисел 1, 2, 3, ….)
2. Порождающей процедурой: а) 2А; б) если хА, то (х+2)А; в) х1000.
Пример 2. Верно ли, что: 1). {{1,2}, {2,3}}={1,2,3}? 2).{{1,2}}={1,2}?
Решение. 1). Нет, так как элементами первого множества являются
подмножества {1,2} и {2,3}, а второго – элементы 1,2,3.
2). Нет, так как первое множество одноэлементное, состоящее из одного
элемента подмножества, а второе имеет два элемента 1 и 2.
Пример 3. Перечислить элементы следующих множеств:
1). А={a|aB, B={1,2,3}};
2). A={a|aB, B={1,2,3}}.
Решение. 1). Так как аВ, а В – трехэлементное множество, то имеется
23=8 подмножеств: А={{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}, }.
2). Так как аВ, то А=В={1,2,3}.
Пример 4. Доказать, используя тождества алгебры множеств, что
.BA)A\B(A
Решение. Используя тождества алгебры множеств, получаем
)AB(A)A\B(A
.BAI
)AA(
)BA(
)BA(
Пример 5. Упростить выражение
Решение. Используя законы и тождества алгебры множеств, получаем:
)CBA(
)CB(CBCBI
I
CB]CB)AA[(CB)CBA(
.CB)CBA(
)CBA(
)CB(
Пример 6. Построить диаграммы Венна для множеств А, В, С, DI, если
АВСD,
Решение. Одно из возможных решение может быть представлено
следующей диаграммой:
DA
BA
,
. Пример 7.
Опрос 100 студентов, изучающих иностранные языки,
показал: английский язык изучают 29 студентов, немецкий –30,
французский –9, только французский 1, английский и немецкий – 10,
немецкий и французский – 4, все три языка – 3 студента. Сколько
студентов не изучают ни одного языка? Сколько студентов изучают
только немецкий язык? При решении использовать диаграммы Венна.
Решение. Введем обозначения:
I – множество всех опрошенных
студентов; А – множество студентов, изучающих английский язык; Н –
множество студентов, изучающих немецкий язык; Ф – множество
студентов, изучающих французский язык (См. диаграмму ЭйлераВенна
на рис. 1.1)
что
НФА
тогда
103=7. В таком случае
=3,
По условию задачи очевидно,
)НА(
)НФА(
=43=1;
)НФА(\)ФН(
только немецкий язык изучают 30731=19 студентов.
9113=4, а
Из условия задачи также слежует, что
поэтому только английский язык изучают 29437=15 студентов. Тогда
число студентов, не изучающих ни одного языка, будет равно
)НФА(\I
100(1+1+3+4+7+15+19)=50 студентов.
)НФА(\)ФА(
Рис. 1.1
)CA(C)BA(
)CB(
.
)CB(
Пример 8. Доказать аналитически:
Решение. Введем обозначения:
C)BA(D
Dx
а). Пусть
, тогда имеет место либо
, тогда
Ax и
BAx
что тоже самое,
)CA(x
записать
и
CAx
случае
)CB(
)CA(x
Dx
Итак, если
, то
Ex . Следовательно,
CBx
, т.е.
, т.е.
Bx и в таком случае
, либо
Cx . Если
или,
Cx , тогда можно
)CB(
одновременно. Откуда, очевидно, и в этом
Ex .
Ex . Если
CAx
CBx
;
)CA(E
BAx
.ED
.
и Ex . Тогда
.Cx Но если
б). Пусть
,Ax либо
тогда
или, что тоже самое,
Ex то
Итак, если
Из пп. а и б следует, что
)CA(C)BA(
)CB(
.Bx Из последнего следует, что
Ax и
,Bx т.е.
CAx
и
CBx
. Если
CAx
Cx , то (см. п.а)
Dx . Если же
, то либо
Cx ,
,
BAx
C)BA(
x
Dx
Dx
. Следовательно,
, т.е.
.
DE .
ED и
DE . Следовательно, D=E, т.е.
. Тождество доказано.
Пример 9. Доказать, что для произвольных множеств А и В имеет место
соотношение
Решение. Для доказательства используем метод от противного, т.е.
предположим, что
ABиBA
ABBA
. Тогда
.
Из АВ если аА, то аВ. (1)
С другой стороны, из B A существует такой элемент а, что
Ba и
AaиBa
Aa
Но с учетом (1) и (2)
BaиAa
BaиBa
противоречие.
. (2)
a
)BB(
=,
т.е.
получили
Следовательно, предположение
AB ложно и поэтому
AB , т.е.
BA
AB
.
Аналогично можно показать, что
ABBA
, что и требовалось доказать.
AB
BA
и, значит,
Задачи для самостоятельного решения.
№ 1.1. Пусть А={{1,2,3}, {1,3}, 1, 2}. Верно ли, что {1, 2}А?
{1, 2}A?
№ 1.2. Перечислить элементы множества
x|x{A
n
3n
2
n
, n=1, 2,…}.
№1.3. Перечислить элементы следующих множеств:
x|x{A
x|x{B
x|x{C
d,c,a{},c,b,a{},b,a{{
}};d,c,b,a{
}}.d,c,b,a{
}}};
№ 1.4. Перечислите все элементы множества
}.1},3{},2,1{{AP
№1.5. Пусть А – произвольное множество. Что представляют собой
следующие множества:
A
A?
\A?
?A\A?
№ 1.6. Множество А состоит из натуральных чисел, делящихся на 4,
множество В – из натуральных чисел, делящихся на 10, множество С – из
натуральных чисел, делящихся на 75. Из каких чисел состоит множество
?CBA
№ 1.7. Даны произвольные множества А, В, С такие, что:
BA и
1.
CA и
2.
Чему равно
;CA
.CB
?CBA?CBA
№ 1.8. Даны произвольные множества А, В и С такие, что
Чему равно
?A\C?C\A?CBA?CBA
,BA
CB .
№ 1.9. Даны множества:
а). А={h,o,t} и B={t,o,o,t,h};
б). A={r,e,s,t} и В={s,t,r,e,e,t}.
?BA?AB?BA
Верно ли, что
№ 1.10. Известно, что а).
следствия из этих уравнений?
;ACBA
б).
ACBA
. Каковы
№ 1.11. Задано, что S={a1, a2, a3}, причем известно, что
SB , B={a2, a3};
;AB;BA;AA
SA , A={a1, a2};
SC ; C={a2}. Найти элементы следующих множеств:
).CB(
)BA(
№ 1.12. Пусть I={1,2,3,4,5}, X={1,5}, Y={1,2,4}, Z={2,5}.
Найти множества:
а)
д)
;Y)ZX(
;YX ж)
; г)
;Z)YX(
);ZX(
);ZY(X
)YX(
и)
;YX з)
)ZY(X
в)
YX ; б)
;YX е)
;Z\X
)Z\X(
л)
).Z\Y(
к)
№ 1.13. Пусть I={a,b,c,d,e,f}, A={a,b,c}, B={f,e,c,a}, C={d,e,f}.
Найти множества:
;B\C
а)
;AB ж)
;BA е)
;CA
;B\A
;C\A
д)
б)
;C\B
г)
в) з)
;AC и)
.AC
№ 1.14. Даны два произвольных множества А и В такие, что
Что представляют собой множества
и
B\A
?A\B
№ 1.15. Даны два произвольных множества С и D такие, что
Что можно сказать о множествах
DC и
?DC
BA
.
DC
.
№ 1.16. Дано произвольное множество Х. Найти множества:
б)
;XX в)
;X\X
г)
.
X\X
;XX)a
№ 1.17. Какие из следующих утверждений справедливы:
а)
д)
0 б)
;1|}{|
};0{
в)
г)
}}};
{{{
}}
{{
;
{{|
?2|}}
№ 1.18. Сформулируйте следующее утверждение на языке множеств:
даны множества А, В и С; определить множество, включающее в себя
только два из этих множеств.
№ 1.19. Решите предыдущую задачу при условии, что множества А, В и С
взаимно не пересекаются.
№ 1.20. Даны множества V, W, Y, X и Z. Определить множество,
включающее по крайней мере два из множеств V, W, X и Y и не
включающее Z.
;BBA
№ 1.21. Упростить выражения:
1)
2)
3)
4)
5)
;)BA(
;)BA(
)CA(
)BA(
)BA(
)CB(
)BA(
)BA(
)BA([
)DCBA(
)DCBA(
);DCBA(
)DCBA(
);DCBA(
)DCBA(
)DCBA(
)DCBA(
)DCBA(
)DCBA(
)DCBA(
)DCBA(
);DCBA(
)DCBA(
)DCBA(
)DCBA(
;)IDCBA(
B)BA(
)CBA(
)]DB(
6)
7)
8)
;DC\)CB\B\A(
9)
10)
11)
12)
13)
14)
15)
16)
17)
;C\BA)CABAA(
;CBACBA\CB\A
;A\CBBAA
;CBACBA\CB\A
)B\A(A
);B\A(
;B\CBBA
;CBA)CABAA(
)CBÀCB(\)CBA(
C\CA)CA)A\B(A(
.
);CBA(
№ 1.22. Доказать тождества, используя законы алгебры множеств:
1)
;A\B)BA(
)BA(
)BA[(\A
)]B\A(
;
2)
3)
4)
5)
)CB(
)CA(
)DCBA(
)DBA(
)BA[(
)BA(
)EDCBA(
)]EDA(
;DBA)ADA(
)CBA([
)EDA(
)CA(
).EDBA(
;C)DC(
])EBA(
№ 1.23. Для произвольных множеств А, В, С, D I построить диаграммы
ЭйлераВенна при условии:
1)
;
2)
3)
CBA;DC,B,A
DC;BD;BAC
DA;DC;BA
CB;
;
;
;BAC
C)B\A(
;
C)A\B(
.
4)
№1.24. С помощью диаграмм ЭйлераВенна установить справедливость
каждого из следующих утверждений относительно произвольных
множеств А, В, С I:
);C\B(\)C\A(C\)B\A(
1)
2) если
CBA
и
BCA
, то
CA
; 3) если
4)
и
)CA(C)BA(
,CBA
,CAB
).CB(
то
B
;
№ 1.25. показать с помощью диаграмм Эйлера Венна, какое из двух
множеств
)BA( является подмножеством другого.
)BA( и
№ 1.26. Как можно представить следующие множества, используя
диаграммы ЭйлераВенна:
{A, {A}}, {{a}, {b}}, {X, Y, Z},
где Х={x|х=1 или (х2)Х},
Y={х|х=3 или (х3)Y},
Z={x|x=2 или (х2)Z}?
№ 1.27. Пусть даны множества А, В и С. С В. Доказать, что:
а)
;BACA
б)
;BACA
в)
;C\AB\A
г)
д)
.A\CA\B
A\BA\C
;
№ 1.28. Доказать, что если
,BA то
)A(P
)B(P
.
№ 1.29. Доказать, что
.BABA
Решите задачи № 1.30 1.39 с использованием диаграммы Эйлера
Венна.
№ 1.30. В студенческом потоке 37 человек хорошо знают математику, а
25 человек – электронику, и 19 человек хорошо знают и математику и
электронику. Если в потоке каждый из студентов знает хотя бы один из
этих предметов, то сколько студентов в потоке?
№ 1.31. Из 250 студентов 151 изучают немецкий язык, 136 – французский
язык, 27 – итальянский, 63 – французский и немецкий, 7 – итальянский и
французский, 11 – немецкий и итальянский, 4 – все три языка.
а) Сколько студентов изучают немецкий или французский язык?
б) Сколько студентов изучают только итальянский язык? в) Сколько студентов изучают немецкий и французский язык, но не
итальянский?
г) Сколько студентов не изучают ни одного языка?
д) Сколько студентов изучают хотя два иностранных языка?
№ 1.32. В отчете о количестве студентов, изучающих иностранные языки,
сообщалось, что из 100 студентов все три языка изучают 5 человек,
немецкий и английский – 10 человек, французский и английский – 8
человек, немецкий и французский – 20 человек, английский – 30,
немецкий – 23, французский – 50. Инспектор, представивший этот отчет,
был отстранен от работы. Почему?
№ 1.33 Каждый из 500 студентов обязан посещать хотя бы один из трех
спецкурсов: по математике, физике, астрономии. Три спецкурса
посещают 10 студентов, по математике и астрономии –25 студентов,
спецкурс только по физике – 80 студентов. Известно также, что спецкурс
по математике посещают 345 студентов, по физике – 145, по астрономии
– 100 студентов. Сколько студентов посещают спецкурс только по
астрономии? Сколько студентов посещают два спецкурса?
№ 1.34. Экзамен по математике содержал три задачи: по алгебре,
геометрии и тригонометрии. Из 800 абитуриентов задачу по алгебре
решили 250 человек; по алгебре или геометрии – 660 человек; по две
задачи решили 400 человек, из них две задачи по алгебре и и геометрии
решили 150 человек, по алгебре и тригонометрии – 50 человек; ни один
абитуриент не решил все задачи; 20 абитуриентов не решили ни одной
задачи; только по тригонометрии задачи решили 120 человек. Сколько
абитуриентов решили только одну задачу? Сколько абитуриентов решили
задачи по тригонометрии?
№ 1.35. На курсах иностранных языков учится 600 человек. Из них
французский изучают 220 человек, английский – 270 человек. Слушатели,
изучающие английский язык, не изучают немецкий язык; один
французский язык изучают 100 человек, один немецкий язык изучают 180
человек. Сколько человек изучает по два иностранных языка? Сколько
человек изучает один иностранный язык?
№ 1.36. На кафедре иностранных языков работают 18 преподавателей. Из
них 12 преподают английский язык, 11 – немецкий язык, 9 – французский
язык. 5 преподавателей преподают английский и немецкий языки, 4 –
английский и французский, 3 – немецкий и французский. Сколько преподавателей преподают все три языка? Сколько преподавателей
преподают только два языка?
№ 1.37. Группа студентов из 25 человек сдала экзаменационную сессию
со следующими результатами: 2 человека получили только “отлично”; 3
человека получили отличные, хорошие и удовлетворительные оценки; 4
человека только “хорошо”; 3 человека только хорошие и
удовлетворительные оценки. Число студентов, сдавших сессию только на
“удовлетворительно”, равно числу студентов, сдавших сессию только на
“хорошо” и “отлично”. Студентов, получивших только отличные и
удовлетворительные оценки – нет. Удовлетворительные или хорошие
оценки получили только 22 студента. Сколько студентов сдали сессию
только на “удовлетворительно”?
№ 1.38. Преподаватели кафедры Прикладной математики преподают на
трех факультетах: механическом, технологическом, экономическом. На
технологическом факультете работает 22 преподавателя,
на
механическом – 23 преподавателя, на механическом и экономическом –
36 преподавателей. Только на технологическом факультете работают 10
преподавателей. 2 – на трех факультетах. 5 преподавателей работают
только на механическом и экономическом факультетах. Число
преподавателей, работающих только на механическом и технологическом
работающих на
факультетах,
экономическом и технологическом факультетах.
Сколько
преподавателей работает на кафедре? Сколько преподавателей работает
только на одном факультете?
равно числу преподавателей,
№ 1.39. Экзамен по математике содержал три задачи: по алгебре,
геометрии и тригонометрии. Из 750 абитуриентов задачу по алгебре
решили 400 абитуриентов, по геометрии – 480, по тригонометрии – 420.
Задачи по алгебре или геометрии решили 630 абитуриентов; по
геометрии или тригонометрии – 600 абитуриентов; по алгебре или
тригонометрии – 620 абитуриентов. 100 абитуриентов не решили ни
одной задачи. Сколько абитуриентов решили все задачи? Сколько
абитуриентов решили только одну задачу?
№ 1.40. Доказать аналитически, что для любых трех множеств А, В и С
справедливы равенства:
а)
б)
);CB(
и
в)
;IB,A
г)
);CB(AC)BA(
)CA(C)BA(
,IBA
,BABA
если
если
IB,A
;AB д)
е)
ж)
з)
)CB(A
)CB(A
,CA если
,AC если
)BA(
)BA(
BA и
).CB(AC)BA(
);CA(
);CA(
;CB
1.2 Соответствия. Отображения. Отношения
АВ={(x,y)|xA,
Прямым произведением множеств А и В называют множество,
обозначаемое АВ и состоящее из всех и только тех упорядоченных пар,
первая компонента которых принадлежит множеству А, а вторая –
yB}. Прямое произведение
множеству В, т.е.
дистрибутивно относительно объединения и пересечения.
Соответствием между множествами Х и Y называется подмножество
. Если (x, y) G , то говорят, что у соответствует х при
YXG
соответствии G. Множество Пр1G называется областью определения
соответствия, множество Пр2G – областью значений соответствия. Если
Пр2G=Y, то соответствие называется сюръективным. Множество всех
,Xx называется образом х в Y при
,Yy соответствующих элементу
Множество всех х, которым соответствует у,
соответствии G.
называется прообразом у в Х при соответствии G.
Соответствие называется функциональным (или однозначным), если
образом любого элемента Пр1G является единственный элемент из Пр2G.
Функцией называется функциональное соответствие.
Если функция f устанавливает соответствие между множествами Х и Y,
то говорят, что функция f имеет тип ХY и обозначается f:XY.
Полностью определенная функция f:XY называется отображением Х
в Y. Образ Х при отображении f обозначается f(X). Если соответствие
при этом сюръективно, т.е. каждый элемент Y имеет прообраз в Х, то
говорят, что имеет место отображение Х на Y (сюръективное
отображение).
Если
есть функция, определенная на А
Y
со значениями в Y. Эту функцию называют сужением f на множество А и
обозначают f|A или fA.
XA , то
и
X:f
f
)YA(
Пример 10. {(1,2), (2,2), (Иванов, Петров)} есть функция с областью
определения {1, 2, Иванов} и областью значений {2, Петров}.
Пример 11. {(1,2), (1,3), (2,5)} не является функцией, т.к. различные
элементы (1,2) и (1,3) имеют одинаковую первую координату. Пример 12. Множество {(a,b), (c,b), (e,d), (k,m)} есть функция, а
подмножество этого множества {(a,b), (e,d)} является сужением этой
функции на множество {a,e}.
X
X:R представляет собой отображение множества Х в
Отображение
самого себя и определяется парой (Х, R), где
2XR . В этом случае для
обозначения данного отображения используется термин отношение и
вводят специальную символику: yRx – у находится в отношении R к х.
Подмножество
между А1, А2, …..An. Если n=2, то R называется бинарным отношением.
Пример 13. Множество {(3,4), (4,6), (7,9), (4,12)} будучи множеством
упорядоченных пар натуральных чисел, есть бинарное отношение на N,
где N – множество натуральных чисел.
называется nместным отношением
AAR
A
n
2
1
):
2AAAR
Aa имеет место
Отношение R называется (
рефлексивным, если для любого
антирефлексивным, если ни для какого
симметричным, если для пары
антисимметричным, если из aiRaj и ajRai следует, что ai=aj;
транзитивным, если для любых a, b, c из aRb и bRc следует aRс.
рефлексивно, симметрично и транзитивно. Обозначается символом .
Aa не выполняется
из aRb следует bRa;
Отношение R называется отношением эквивалентности, если оно
2A)b,a(
aRa
aRa
;
;
Пример 14. Докажите, что отношение равенства «=» на любом
множестве является отношением эквивалентности.
свойства: рефлексивности
транзитивности [(а=в и в=с) а=с].
Решение. Действительно, для данного отношения выполняются
(а=а); симметричности (а=в в=а);
, если оно рефлексивно и транзитивно.
Отношением предпорядка на множестве А называется отношение
AAR
Отношением порядка называется отношение, если оно рефлексивно,
антисимметрично и транзитивно.
антирефлексивно, антисимметрично и транзитивно.
Отношением строгого порядка называется отношение, если оно
Пример 15. Задано бинарное отношение R на множестве М={1, 2, 3, 4}.
Является ли оно рефлексивным, симметричным, антисимметричным,
транзитивным? Найти область определения R, область значений R,
обратное отношение R1, пересечение и объединение отношений R и R1
R={(1,1), (1,2), (1,3), (1,4), (4,1), (4,2), (4,3), (4,4). Решение.
Отношение R, заданное на множестве М, называется рефлексивным,
если для всякого х из этого множества хRх истинно. Заданное отношение
не является рефлексивным, так как нет пар (2,2) и (3,3).
Отношение R, заданное на множестве M называется симметричным, если
на этом множестве из xRy следует yRx. Заданное отношение не является
симметричным, т.к., например, пара (1,2)R, а (2,1)R.
Отношение R, заданное на множестве M называется антисимметричным,
если на этом множестве из xRy и yRx следует x=y. Заданное отношение
не является антисимметричным, так как ему принадлежат пары (1,4) и
(4,1), но 14.
Отношение R, заданное на множестве M называется антирефлексивным,
если для любого Mx xRx ложно. Заданное отношение антирефлек
сивно, так как (уже было показано) нет пар (2,2) и (3,3).
Отношение R, заданное на множестве M называется транзитивным, если
на этом множестве из xRy и yRz следует xRz. Заданное отношение
является транзитивным, так как для любых двух пар (a,b) и (b,c) следует,
что (a,c)R, где а, в, с М.
Областью определения отношения R называется множество R ={x| (у)
xRy}. Следовательно, областью определения R является двухэлементное
множество {1, 4}.
Областью значений отношения R называется множество R={y|(x) xRy}.
Следовательно, областью значений является все множество М={1, 2, 3,
4}.
Обратным отношением для R называется отношение R1={(y,x)|(x,y)R}.
Обратное отношение R1={(1,1), (2,1), (3,1), (4,1), (1,4), (2,4), (3,4), (4,4)}.
Пересечение R и R1 равно R R1={(1,1), (4,1), (1,4), (4,4)}.
Объединение R и R1 равно R R1={(1,1), (1,2), (1,3), (1,4), (4,1), (4,2),
(4,3), (4,4), (2,1), (3,1)}.
Пример 16. График функции f(x) (cм. рис. 1.2) представляет собой
ломанную, звенья которой параллельны координатной оси, либо
биссектрисам координатных углов.
Координаты каждой вершины
ломанной являются целыми числами. Функция f(x) определяет
отношение Rf на множестве Х=[0, 5]: xRfy f(x)=f(y), т.е. х находится в
отношении Rf с у тогда и только тогда, когда f(x)=f(y).
Доказать, что Rf – эквивалентность на Х. Перечислить все классы
эквивалентности.
2+ Рис. 1.2
2
Решение.
Рефлексивное, симметричное и транзитивное отношение на множестве
Х называется отношением эквивалентности на множестве Х. Классом
эквивалентности, порожденным элементом х, называется подмножество
множества Х, состоящее из тех элементов уХ, для которых ху и
обозначается [x]. [x]={y| уХ и ху}.
Сначала докажем, что отношение Rf есть отношение эквивалентности.
Действительно, рефлексивность хRfy, очевидна, так как f(x)=f(y).
Симметричность: пусть хRfy т.е.
f(x)=f(y), но тогда f(y)=f(x) и,
следовательно, yRfx. Транзитивность: если f(x)=f(y), а f(y)=f(z), то
f(x)=f(z) и, следовательно, хRfy и уRfz влечет xRfz.
Классы эквивалентности: {, 2, 2+}, [4, 5], {0,2}, {1,3}, {3+},
где (0,1).
Задачи для самостоятельного решения
№ 1.41. Какое множество имеет большую мощность: а) множество
натуральных чисел или множество четных чисел? б) множество четных
чисел или множество простых чисел?
№ 1.42 Установить эквивалентность между множеством натуральных
чисел N и множеством
}
,3,2,1{;M
.
№ 1.43 Показать, что мощность всякого произвольного множества
больше или равна мощности всех чисел натурального ряда.
№ 1.44. Установить взаимнооднозначное соответствие между
множествами всех рациональных чисел на отрезках (0; 1) и (0; ).
№ 1.45. Установить эквивалентность между множеством всех
положительных рациональных чисел и множеством натуральных чисел.
№ 1.46. Задана система числовых множеств:
x|x{A1
};Nn,n
x|x{
A 2
};Nn,n2
………………………..
.
A k
}Nn,kn
x|x{
.
Определить мощность множества
C
kA
1k
№ 1.47. Является ли множество {(1, 2), (3, 4), (5, 6), (7, 8)} бинарным
отношением. Почему?
№ 1.48. Выписать элементы множества {0, 1, 2}{a,b}. Найти область
определения и область значений этого отношения, построить его график.
№ 1.49. Показать на примере, что операция образования декартового
произведения не является ни коммутативной, ни ассоциативной.
№ 1.50. Доказать, что декартово произведение дистрибутивно
относительно операции объединения, т.е. что для любых множеств А, В и
С
)CA(C)BA(
)CB(
.
№ 1.51. Пусть отношение “есть брат”, отношение “есть сестра”.
Описать отношения
\
;
;
.
№ 1.52. Является ли отношение “быть рядом” транзитивным?
симметричным,
№ 1.53. Задано бинарное отношение на множестве М={1,2,3,4}. Является
ли оно рефлексивным,
антисимметричным,
транзитивным? Почему? Найдите область определения R, область зна
чений R, обратное отношение R1, пересечение и объединение R и R1.
а) R={(1,1), (1,2), (1,3), (2,3), (3,3), (4,1), (4,4)};
б) R={(1,1), (1,2), (2,1), (2,3), (3,2), (3,3), (4,4)};
в) R={(1,1), (1,4), (2,3), (3,2), (4,1)};
г) R={(1,1), (1,2), (1,4), (2,2), (2,3), (3,3), (4,4)};
д) R={(1,1), (1,3), (2,2), (3,3), (4,1), (4,4)};
е) R={(1,1), (1,2), (3,1), (3,2), (3,3), (4,4)};
ж) R={(1,1), (1,2), (2,2), (2,3), (3,4), (4,4)};
з) R={(1,2), (1,3), (2,2), (2,3), (3,3), (4,3)};
и) R={(1,4), (2,3), (3,2), (3,4), (4,1), (4,3)};
к) R={(2,1), (3,1), (3,2), (3,3), (3,4), (4,1)}.
№ 1.54 Найти область определения, область значений, построить график
каждого из следующих отношений:
а)
б)
x|RR)y,x{(
};1|y|2|x||RR)y,x{(
2
};y
2 в)
x|RR)y,x{(
2
2
y
1
x
и
г)
д)
е)
y,0
y|RR)y,x{(
2
x|RR)y,x{(
)1y(
2
2
x|RR)y,x{(
y
}.1
};0
};1
};1yx,x
2
№ 1.55 Доказать, что если:
а)
,CAA
BA и
BA и
то
;CBB
;B\CA\C
,BC,AC
то
б)
в)
,A\BB\A
то
.BA
№ 1.56. Доказать, что множество всех окружностей (на плоскости),
радиусы которых рациональны и центры которых имеют рациональные
координаты, есть счетное множество.
№ 1.57. Доказать, что множество всех четырехугольников (на плоскости),
вершины которых имеют целые координаты, есть счетное множество.
№ 1.58. Доказать, что множество всех точек плоскости, обе координаты
которых есть двоичные дроби, есть счетное множество.
№ 1.59. На улице есть 30 домов, пронумерованных обычным способом:
нечетные номера с одной стороны, а четные с другой стороны. Пусть hn
обозначает жителя, живущего в доме с номером n. Описать при помощи
символов отношение N на множестве жителей такое, что hi находится в
отношении N к hj, если они являются соседями.
Как будет выглядеть N, если улица является тупиком?
№ 1.60. Доказать, что любое отношение эквивалентности порождает
такое разбиение, что для любых х, уА или [x]1=[y], или [x][y]= .
№ 1.61. Если {A1, A2, … , An} – разбиение А и А конечное, показать, что
i |A|
|A|
.
n
1i
№ 1.62. Пусть А –произвольное множество и отношение на множестве
тогда и
)A(P)A(P
, определенное следующим образом:
)Y,X(
)Q,P(
1 Запись [x] означает класс эквивалентности для хА. только тогда, тогда
порядка?
)QP(
)YX(
. Является ли отношением
1.63. Докажите справедливость соотношения
)CB(A
)CA(
)BA(
.
1.64. Проиллюстрируйте диаграммой Венна следующие разбиения
множества I:
а)
б)
в)
};A,A{
};BA,BA,BA,BA{
}.A\B,BA,B\A{
1.65 Каковы свойства соответствия между множеством N натуральных
чисел и множеством А степени числа 2:
?AN}A
2,Nn|)
2,n{(
G
1n
1n
1.66 Является ли функция f(x)=2x, имеющая тип NN, отображением, и
если – да, то каким? Имеет ли функция f обратную функцию f1, и если –
да , то является ли f1 отображением?
1.67 Чему равна композиция функций f(x) и g(x), если:
а) f(x)=2x и g(x)=
xlg ;
б) f(x)=x3 и g(x)= x ;
в) f(x)=2x и g(x)=x+1?
Каковы области определения функций и их композиций?
1.68 Найти композицию преобразований:
,
321
122
;
321
123
,
cba
cbc
dcba
cadb
,
cba
abb
;
dcba
ddac
.
1.69 Пусть множества (I), где I={a, b, c} A3 определены следующим
образом: (I) – множество всех подмножеств (булеан) множества I={a, b,
c}; А3 – множество всех двоичных векторов длины 3, т.е. А3=ВВВ, где
В={0, 1}.
Показать, что между множествами (I) и А3 имеет место взаимно
однозначное соответствие.
)x(f
№ 1.70. График функции
представляет собой ломанную, звенья
которой параллельны координатной оси,
либо биссектрисам
координатных углов. Координаты каждой вершины ломанной являются
определяет отношение Rf на множестве
целыми числами. Функция
)x(f
Х=[0, 5]. xRfy f(x)=f(y) ( т.е. x
,X y X находится в отношении Rf с y
X тогда и только тогда, когда f(x)=f(y). Докажите, что Rf –эквива
лентность на Х. Перечислите все классы эквивалентности. а) б)
а) б)
в) г)
д) е)
ж) з)
2 Элементы теории графов
2.1Основные определения. ),Г,A(
A
G
A
A
A)Гx(xГ,XA
где
Частичным графом G по отношению к графу G=(Х, Г) называется
граф, содержащий только часть дуг графа G, т.е. определяемый
условием:
.
Пусть Х – множество вершин, V –множество ребер, соединяющие
вершины. Граф G=(X,V) cчитается заданным, если дано множество его
вершин Х и способ отображения Г этого множества в самого себя.
Подграфом GA графа G=(Х, Г) называется граф, в который входит лишь
часть вершин графа G, образующих множество А, вместе с дугами,
соединяющими эти вершины:
G
,X(
),
где
x
Гx
.
Важными понятиями в теории графов являются понятия пути, длины
пути, контур
. Для описания графа используются матрицы смежности и матрицы
инцидентности.
Пример 2.1 Построить граф G, заданный множеством вершин Х={X1, X2,
X3, X4} и их отображениями Г(Х1)={X1, X2}, Г(Х2)={X3, X4}, Г(X3)={X1,
X4}, Г(Х4)={X1, X2, X3}.
Решение. Данный граф приведен на рис. 2.1
X1
X4
X2
X3
Рис. 2.1
Два графа G1 и G2 изоморфны, если существует такое взаимно
однозначное соответствие между множествами их вершин Х1 и Х2, что
вершины соединены ребрами в одном из графов в том и только том
случае, когда соответствующие им вершины соединены в другом графе.
Если ребра ориентированы, то их направления
также должны
соответствовать друг другу.
Пример 2.2 Изоморфны ли графы, изображенные на рис. 2.2 и 2.3? A1
A2
Рис.2.2
B1
B2
Рис. 2.3
Решение. Графы А1 и А2 не изоморфны, хотя они и имеют одинаковое
число вершин и ребер. Но в графе А1 одно из ребер направлено от а к b, а
в графе А2 оно направлено в другую сторону. Графы В1 и В2 изоморфны,
т.к. они имеют одно и то же число вершин и любые две вершины графа В1
соединены ребром только тогда, когда соответствующие им вершины
графа В2 также соединены ребром.
Пример 2.3 Являются ли полными (без учета петель) графы А1, В1,
изображенные на рис. 2.2 и 2.3?
Решение. Граф В1 не является полным, т.к.
не все пары его вершин соединены
ребрами. Например, (а1, а6), (а3, а8) и
другие. Граф А1 не является полным, т.к.
ребро (a, b) ориентировано только в одном
направлении.
Рис. 2.4
Пример 2.4 Дан ориентировнный граф
(рис. 2.4). Построить его матрицы смежности и инцидентности. Решение. В соответствии с определением матрица смежности есть
квадратная матрица с элементами множества вершин в качестве
координат ее столбцов и строк.
Элемент матрицы в строке i и столбце j равен 1, если есть ребро от
вершины i к вершине j, 1 если есть ребро к вершине i от вершины j и 0 –
если вершины i и j не соединены. Матрица смежности приведена
в таблице 2.1
Таблица 2.1 Таблица 2.2
V
V4
X
a
b
c
d
V
X
1
0
0
1
0
1
0
1
b
1
0
1
1
c
0
1
0
0
V1
V2
V3
0
1
0
1
d
1
1
0
0
a
a
b
c
d
1
1
0
0
0
1
1
0
В матрице инцидентности координатами строк являются элементы
множества вершин, а координатами столбцов – элементы множества
ребер. Элемент матрицы в строке i и столбце j равен 1, если ребро j
исходит из вершины i, 1 – если ребро j входит в вершину i, 0 – если
ребро j не инцидентно вершине i. Матрица инцидентности приведена в
таблице 2.2.
Пример 2.5 На рис. 2.5. задан граф G. Построить матрицу смежности и
выяснить, сколько путей длины три существует в графе G.
Х2 Х4
V1 V2 V3
X1 X3
Рис. 2.5
Решение. A
0010
0100
1000
000
0
3
A
0
0
0
0
100
000
000
000
2
A
0100
1000
0000
0000
4
A
000
000
000
000
0
0
0
0
1
Элемент
14 , следовательно, в данном графе существует
a )3(
единственный путь длиной три. Это путь из вершины Х1 в вершину Х4:
X
1
Все элементы матрицы А4 равны нулю, следовательно, в графе
отсутствуют пути длиной четыре.
2V
3V
1V
.
X
4
X
2
X
3
Задачи для самостоятельного решения № 2.1 Показать, что два графа на рис. 2.6 изоморфны.
Рис. 2.6
№ 2.2 «Три дома и три колодца». Три поссорившихся соседа имеют три
общих колодца. Можно ли провести непересекающиеся дорожки от
каждого дома к колодцу?
№ 2.3 Найти степени и числа вершин для графов пяти правильных
многогранников.
№ 2.4 Для графов, изображенных на рис. 2.7, указать пары, изоморфные
друг другу.
А Б В
Г Д Е
Ж З И Ж З И
К Л М
Рис.2.7
№ 2.5 Среди графов, указанных на рис. 2.8, выделить полные графы (без
учета петель).
А Б В Г
Д Е Ж И К Л М
Рис. 2.8
№ 2.6 Дан граф G (Рис. 2.9). Указать, какие из графов, изображенных на
рис. 2.9б, являются частями графа G и какие – подграфами.
Рис. 2.9
А Б В
Г Д Е Ж З И
К Л М Н
Рис. 2.9б.
№ 2.8 Какие из графов, приведенных на рис.2.8 и 2.9, являются
плоскими?
№ 2.9. Составить матрицы смежности и инцидентности для правильных
многогранников.
№ 2.10. Построить матрицы смежности графов, изображенных на рис.
2.9.
№ 2.11 Для заданного на рис. 2.10 (ак) графа построить: матрицу
смежности, матрицу инциденции, матрицу достижимостей. Найти число
внутренней устойчивости. Найти число внешней устойчивости.
А Б В Г Д Е Ж
З И К
Рис. 2.10.
№ 2.12. Для приведенных на рис. 2.11. графов G1 и G2 найти
G ,
1 GG .
2
1 G
2
G ,
2
1 G
А Б
В Г
Д Е Ж З
Рис. 2.11
№ 2.13. Построить графы, матрицы смежности которых указаны:
M
1
;
110
101
011
M
2
;
1110
1101
1011
0111
M
3
;
1110
1101
1001
0111
;
1
10
101
011
M
4
0
1
0
1
1
0
0
1
01
10
10
01
10
11
;
M
5
;
1000
1100
0010
1011
M
6
1010010
1101101
0001110
0010110
1111001
1110010
1110011
;
M
7
0
1
0
0
1
M
8
0
1
0
1
10
1
0
11
001
001
;
M
9
1
1
1
1
1
1
.
1
1
1
№ 2.14. Построить графы, матрицы инцидентности которых указаны:
1
0
1
0
0
1
0
0
1
0
0
1
0
1
0
;
0
0
0
1
1
1
1
0
0
0
M
3
;
M
5
1
1
0
0
1
0
0
1
1
0
1
1
0
1
0
1
0
1
1
0
0
0
1
1
;
M
1
;
011
101
110
1
0
0
1
1
1
0
0
0
1
1
0
;
0
0
1
1
M
2
M
4
0
1
1
0
0
0
001
100
001
110
000
000
0
0
0
1
1
0
0
0
0
1
0
1
M
6
000111
001010
111000
100001
010100
;
M
7
1
0
0
1
1
1
0
0
0
1
1
0
0
0
1
1
;
0
1
0
1
M
8
.
1010
0101
1010
0101
№ 2.15 Груз доставляется из пункта Х0 в пункт Х7 через перевалочные
пункты Х0…Х7 (Рис.2.12). Расстояния между пунктами ХiXj указаны на
соответствующем графе. Найти путь минимальной длины между Х0 и Х7
и его длину.
А Б В Г
Рис. 2.12
№ 2.16 Задан сетевой граф проекта (Рис.2.12). Найти критический путь и
минимальное время проекта
Литература
1. Кук Д., Бейз Г. Компьютерная математика. Пер. с англ., М., Мир,
1992 г.
2. Кузнецов О.П., АдельсонВельский Г.М. Дискретная математика
для инженера. М., Энергоатомиздат, 1989 г.
3. Ф.А. Новиков. Дискретная математика для программистов. Санкт
Петербург, Питер, 2001 г.
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Элементы теории множеств и теории графов
Материалы на данной страницы взяты из открытых истончиков либо размещены пользователем в соответствии с договором-офертой сайта. Вы можете сообщить о нарушении.
10.02.2017
© ООО «Знанио»
С вами с 2009 года.
О портале
