С.Н. Селезнева - Основы дискретной математики, страница 6

Является ли данное отношение свойством на множествестудентов некоторой группы:1)2)3)4)множество отличников“;”множество студентов, участвующих в самодеятельности;множество пар студентов, играющих друг с другом в шахматы;множество пар студентов, подготавливающих один диалог по иностранному языку.Задача 3.3. Является ли данное отношение на множестве месяцев годабинарным:1)2)3)4)множествомножествомножествомножествопар месяцев одного времени года;летних месяцев;пар месяцев, один из которых следует за другим;месяцев отопительного периода.33Задача 3.4. Какие из следующих бинарных отношений являются рефлексивными; иррефлексивными; симметричными; антисимметричными; транзитивными?1. Пусть A – множество студентов какой-то группы, R(2) ⊆ A2 – бинарное отношение на множестве A, и R – множество пар студентов,1) пишущих один вариант на контрольной;2) в которых фамилия первого студента по алфавиту располагаетсяраньше фамилии второго;3) приехавших из разных городов;4) получивших одинаковые оценки в сессию.2.

Пусть A – множество букв русского алфавита, R(2) ⊆ A2 – бинарноеотношение на множестве A, и R – множество пар букв,1)2)3)4)стоящих подряд по алфавиту;первая из которых расположена в алфавите раньше, чем вторая;являющихся гласными;одна из которых – звонкая согласная, другая – соответствующаяей глухая согласная.Задача 3.5. Для данного отношения R на множестве A описать его n-юстепень – отношение Rn на множестве An :1) A = {0, 1}, R(2) ⊆ A2 и R(2) = {(0, 0), (0, 1), (1, 1)}.2) A – множество букв русского алфавита с символом пробела, R – бинарное отношение на множестве A, содержащее пары букв, первая из которых расположена в алфавите не позже, чем вторая.

Считается, чтопробел расположен раньше всех букв алфавита.Задача 3.6. Доказать, что если бинарное отношение R на множестве Aявляется одновременно и симметричным, и антисимметричным, то оноявляется также и транзитивным.Задача 3.7. Пусть A – множество из k элементов. Сколько можно определить различных1) свойств на множестве A;2) бинарных отношений на множестве A.343.3Отношение эквивалентностиОпределение 3.4.

Бинарное отношение R(2) ⊆ A2 называется отношением эквивалентности (на множестве A), если оно рефлексивно, симметрично и транзитивно.Теорема 3.1. Если R – отношение эквивалентности на множествеA, то его n-я степень Rn – отношение эквивалентности на множестве An , n ≥ 2.Определение 3.5. Классом эквивалентности по отношению эквивалентности R, порожденным элементом a, называется множество всехтаких элементов множества A, которые находятся в отношении R с элементом a.Обозначение:[a]R = {b ∈ A | R(a, b)} – класс эквивалентности по отношению эквивалентности R, порожденный элементом a ∈ A.Теорема 3.2. 1. Классы эквивалентности или не пересекаются, илисовпадают.2.

Класс эквивалентности порождается любым своим элементом.Следствие 3.2.1. Отношение эквивалентности разбивает множество, на котором оно задано, на классы эквивалентности.Определение 3.6. Фактор-множеством множества A по отношениюэквивалентности R называется множество всех классов эквивалентностипо этому отношению.Обозначение:A/R = {[a]R | a ∈ A} – фактор-множество множества A по отношению эквивалентности R.Как правило, отношение эквивалентности обозначают ∼ и говорятэквивалентно“.”Пусть ∼ – отношение эквивалентности на множестве A.Записывают x ∼ y и говорят элемент x эквивалентен элементу y“.”353.4УпражненияЗадача 3.8.

Пусть A – множество студентов некоторого вуза. Являетсяли бинарное отношение R на множестве A отношением эквивалентности?Если да“, найти фактор-множество по этому отношению эквивалентно”сти.1) R – множество пар студентов, получивших одинаковое количествовступительных баллов;2) R – множество пар студентов, празднующих день рождения в одном месяце;3) R – множество пар студентов из одной группы;4) R – множество пар студентов с разных курсов.Задача 3.9. Пусть A – множество месяцев года.

Является ли бинарноеотношение R на множестве A отношением эквивалентности? Если да“,”найти фактор-множество по этому отношению эквивалентности.1) R – множество пар месяцев одного времени года;2) R – множество пар месяцев разных времен года.Задача 3.10. Пусть A – множество букв русского алфавита. Являетсяли бинарное отношение R на множестве A отношением эквивалентности?Если да“, найти фактор-множество по этому отношению эквивалентно”сти.1) R – множество пар согласных букв одинаковой звонкости;2) R – множество пар букв, содержащих или две согласные, или двегласные буквы.Задача 3.11.

Определяется ли отношением эквивалентности1)2)3)4)разбиение месяцев года по временам года;распределение студентов факультета по группам;распределение станций метрополитена по веткам;распределение местности на зоны пригородного сообщения?Задача 3.12. Пусть A – множество прямых на плоскости. Является либинарное отношение R на множестве A отношением эквивалентности?Если да“, найти фактор-множество по этому отношению эквивалентно”сти.1) R – множество пар параллельных прямых;2) R – множество пар перпендикулярных прямых?36Задача 3.13. Является ли бинарное отношение R на множестве A отношением эквивалентности? Если да“, найти фактор-множество по этому”отношению эквивалентности.1) A – множество натуральных чисел, R – множество пар натуральныхчисел, первое из которых является делителем второго;2) A – множество целых чисел, R – множество пар целых чисел, разность которых делится на m, где m ≥ 1 – заданное натуральное число.Задача 3.14.

Пусть A = {1, 2, 3, 4, 5} – подмножество множества натуральных чисел. Является ли бинарное отношение R на множестве A2отношением эквивалентности? Если да“, найти классы эквивалентности”и фактор-множество по этому отношению эквивалентности.1) R = {((x1 , y1 ), (x2 , y2 )) ∈ (A2 )2 | x1 = x2 , y1 = y2 };2) R = {((x1 , y1 ), (x2 , y2 )) ∈ (A2 )2 | x1 + y1 = x2 + y2 };3) R = {((x1 , y1 ), (x2 , y2 )) ∈ (A2 )2 | x1 + y1 6= x2 + y2 };4) R = {((x1 , y1 ), (x2 , y2 )) ∈ (A2 )2 | |y1 − x1 | = |y2 − x2 |}.Задача 3.15. Пусть R – отношение эквивалентности на конечном множестве A. Верно ли, что1) все классы эквивалентности по отношению R содержат одинаковоечисло элементов множества A;2) каждый элемент множества A принадлежит какому-нибудь классуэквивалентности по отношению R;3) могут быть элементы в множестве A, принадлежащие несколькимразным классам эквивалентности по отношению R;4) количество классов эквивалентности по отношению R не зависитот того, по каким элементам множества A они построены?3.5Отношение частичного порядкаОпределение 3.7.

Бинарное отношение R(2) ⊆ A2 называется частичным порядком (на множестве A), если оно рефлексивно, антисимметрично и транзитивно.Обозначение:(A; R) – на множестве A задан частичный порядок R.Определение 3.8. Множество A с заданным на нем частичным порядком R называется частично упорядоченным множеством.37Теорема 3.3. Если R – частичный порядок на множестве A, то егоn-я степень Rn – частичный порядок на множестве An , n ≥ 2.Определение 3.9. Элементы x и y частично упорядоченного множества (A; R) называют сравнимыми, если верно или R(x, y), или R(y, x).Элементы x и y множества A называют несравнимыми, если они не являются сравнимыми.Определение 3.10. Частичный порядок R(2) ⊆ A2 называется линейным порядком, если любые два элемента множества A сравнимы.Определение 3.11.

Множество A с заданным на нем линейным порядком R называется линейно упорядоченным множеством.Как правило, частичный порядок обозначают ≤ и говорят меньше”или равно“.Обозначение:(A; ≤) – на множестве A задан частичный порядок ≤.Записывают x ≤ y и говорят элемент x меньше элемента y или равен”ему“.Записывают x < y и говорят элемент x (строго) меньше элемента”y“, если верно, что x ≤ y и элемент x не совпадает с элементом y.Записывают xly и говорят элемент x непосредственно предшеству”ет элементу y“, если верно, что x < y и не существует такой элемент z,что x < z < y.Если x ≤ y, то также говорят, что элемент y больше элемента x”или равен ему.

Аналогично при x < y и x l y говорят соответственно(строго) больше“ и непосредственно следует“.””Определение 3.12. Элемент a частично упорядоченного множества называется минимальным, если не существует такой элемент x в множестве A, что x < a.Элемент минимальный, если нет элементов, которые меньше его. Минимальных элементов может быть несколько.Определение 3.13.

Элемент a частично упорядоченного множества называется наименьшим, если для любого элемента x множества A верноa ≤ x.38Элемент наименьший, если он меньше всех других. Если наименьшийэлемент есть, то он всегда единственный. Наименьший элемент являетсяминимальным элементом, обратное в общем случае не верно.Аналогично вводятся понятия максимального и наибольшего элементов частично упорядоченного множества.Определение 3.14. Диаграммой Хассе10 частично упорядоченного множества (A; ≤) называется фигура на плоскости, которая получается, если1) каждому элементу x множества A сопоставлена некоторая точкаплоскости px , причем разным элементам сопоставлены разные точки;2) для любых элементов x и y множества A верно, что если x l y,то от точки px к точке py проведен направленный отрезок непрерывнойкривой.Определение 3.15. Множество элементов C частично упорядоченногомножества (A; ≤) назовем цепью, если все они попарно сравнимы.Так как все элементы цепи сравнимы, их можно линейно упорядочить.

Поэтому в конечной цепи всегда есть наименьший и наибольшийэлементы.Определение 3.16. Длиной конечной цепи в частично упорядоченноммножестве называется число, равное ее мощности. Один элемент частично-упорядоченного множества всегда образует цепь длины 1.Замечание 3.1. Часто в литературе длиной конечной цепи в частично-упорядоченном множестве считается число, на единицу меньшее еемощности.