Дискретная Математика. Учебное пособие Допущено научнометодическим советом по математике вузов СевероЗапада в качестве учебного пособия для студентов вузов, обучающихся по специальностям 220200
 Скачать 6.37 Mb.
|
3 , 2 , 1 , 2 A A P изображено на рис. 1.8. Его мат- рица имеет вид 1 0 1 1 1 0 1 1 0 P . Пусть 0 1 0 1 0 0 1 0 1 Q , тогда 1 1 1 1 1 0 1 1 1 Q P Q P , 2 3 0 0 0 1 0 0 1 0 0 Q P Q P , 1 1 1 1 1 0 1 1 0 Q P Пусть P - бинарное отношение на множестве A , 2 A P 1 Отношение P на множестве A называется рефлексивным, если Рис. 1.8. P x x A x , , , т. е. P id A , 1 1 1 P , где звез- дочкой обозначены нули или единицы. Отношение P называется иррефлексивным, если P x x A x , , . Отношение P на множестве A называется симметричным, если P y x , из условия P y x , следует, что P x y , . Это значит, что P P T . Отношение P называется антисимметричным, если из условий P y x , и P x y , следует, что y x , т. е. A id P P 1 или T P P P P 1 . Это свойство приводит к тому, что у матрицы 1 P P все элементы вне главной диагонали будут нулевыми (на главной диагонали тоже могут быть нули). Отношение P называется транзитивным, если из P y x , и P z y , следует, что P z x , , т. е. P P P Пример 4. Рассмотрим все свойства следующего отношения P , если 1 0 1 1 1 0 1 1 1 P Здесь на главной диагонали матрицы P стоят все единицы, следовательно, P рефлексивно, т. е. P id A . Матрица P не симметрична, тогда не симметрично и отношение P . 1 0 1 0 1 0 1 0 1 1 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 1 1 T P P P P . Эта матрица нужна для проверки антисимметричности. Так как не все элементы, стоящие вне главной диагонали, нулевые, то отношение P не антисимметрично. Из этого примера видно, что свойство несимметричности не совпадает со свойством антисимметричности. Наконец, 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 P P P P , т. е. P P P , следовательно, отношение P не транзитивно. 8 Рефлексивное, транзитивное и симметричное отношение на множестве A называется эквивалентностью на A . Эквивалентность обозначается символами E или , например, xEy , y x Классом эквивалентности (смежным классом) элемента A x называется множество y x y x E . Множество классов эквивалентности элементов множества A по эквива- лентности E называется фактор-множеством A по E и обозначается A x x E E A Пример 5. Докажем, что на множестве N N отношение Q является отношением эквивалентности, если c b d a Q d c b a , , , Если отношение Q рефлексивно на A , то Q x x Q x , . В нашем случае роль A играет множество N N , а роль элемента x играет пара y x, . Тогда отношение Q рефлексивно на N N , если Q y x y x Q y x , , , , . По определению c b d a Q : , но a b b a , следовательно, Q рефлексивно. Аналогично, если Q d c b a , , , , то и Q b a d c , , , , так как из c b d a следует, что a d b c . Таким образом, Q симметрично. Наконец, если Q d c b a , , , , Q g f d c , , , , то Q g f b a , , , , так как c b d a и f d g c . Тогда g c d a f d c b g c d a f b g a f d c b , т. е. Q транзитивно. Разбиением множества A называется совокупность попарно непересекающихся подмножеств A таких, что каждый элемент множества A принадлежит одному и только одному из этих подмножеств. Теорема 1.1. Фактор-множество E A является разбиением множества A . Наоборот, если i A R - некоторое разбиение множества A , то можно задать соответствующее ему отношение эквивалентности E по правилу i A y x xEy , для некоторого i . Если E - эквивалентность на конечном множестве A , то i x E - классы эквивалентности, а n x E x E x E E A ,..., , 2 1 и n i b b b x E i m i i i i , 1 , ,..., , 2 1 . Если множество A пронумеровано в следующем порядке n m n n m m n b b b b b b b b b ,..., , ,..., ,..., , , ,..., , 2 1 2 2 2 2 1 1 1 2 1 1 2 1 , то матрица отношения эквивалентности E имеет блочно-диагональный вид: 1 0 0 0 1 0 0 0 1 2 1 2 1 n m m m n m m m E , где блоки 1 состоят из единиц, а остальные элементы равны нулю. Если же множество A пронумеровано произвольным образом, то матрица j i e E , приводится к блочно-диагональному виду перестановкой строк и столбцов. Отношение 2 A P называется предпорядком, если оно рефлексивно и транзитивно. Очевидно, что симметричный предпорядок является отношением эквивалентности. Пример 6. Пусть 4 , 3 , 2 , 1 A Тогда отношение 1 , 4 , 2 , 3 , 2 , 1 , 4 , 4 , 3 , 3 , 2 , 2 , 1 , 1 P - предпорядок. Рефлексивное, транзитивное и антисимметричное отношение на множестве A называется частичным порядком на A . Частичный порядок обозначается символом , а 9 обратное ему отношение 1 символом . Отношение < называется строгим порядком и определяется таким образом y x y x y x и . Это отношение не является частичным порядком, так как не удовлетворяет условию рефлексивности x x Если во множестве A есть элементы x и y , о которых нельзя сказать, что y x или x y , то такие элементы называются несравнимыми. Частичный порядок называется линейным порядком, если любые два элемента x и y из множества A сравнимы, т. е. y x или x y Непустое множество A , на котором зафиксирован некоторый частичный (линейный) порядок, называется частично (линейно) упорядоченным множеством. Элемент A a частично упорядоченного множества A называется максимальным (минимальным), если для A x из того, что a x x a следует x a . Элемент A a называется наибольшим (наименьшим), если x a a x для всех A x . Наибольший элемент обозначается A max , наименьший - A min . Этих элементов у множества может и не быть, например, линейно упорядоченное множество рациональных чисел 1 , 0 не имеет наименьшего элемента, наибольший элемент равен единице. Верхней (нижней) гранью подмножества B частично упорядоченного множества A называется всякий элемент A a и такой, что b a a b для всех B b . Точной верхней (нижней) гранью подмножества A B называется наименьшая верхняя (наибольшая нижняя) грань для B . Точная верхняя и точная нижняя грани множества A B обозначаются через B sup (супремум) и B inf (инфимум) соответственно. Линейный порядок на множестве A называется полным, если каждое непустое подмножество множества A имеет наименьший элемент. В этом случае множество A называется вполне упорядоченным. Рассмотрим непустое конечное частично упорядоченное множество A . Говорят, что элемент y покрывает элемент x , если y x и не существует такого элемента z , что y z x Если y x , то существуют такие элементы n x x x ,..., , 2 1 , что y x x x x n 2 1 , где 1 i x покрывает i x . Любое частично упорядоченное множество можно представить в виде схемы, в которой каждый элемент изображается точкой на плоскости, и если y покрывает элемент x , то точки x и y соединяются отрезком, причем точку, соответствующую x располагают ниже y . Такие схемы называются диаграммами Хассе Пример 7. Пусть 7 , 6 , 5 , 4 , 3 , 2 , 1 , 0 A линейно упорядоченное множество с обычным отношением порядка на множестве натуральных чисел, не превосходящих семи. Его диаграмма Хассе изображена на рис. 1.9. Элементы этого отношения упорядочены обычным от- 7 (2,2) ношением частичного порядка . Рассмотрим еще одно отношение: 6 2 0 , 2 0 , 1 , , / , y x y x Z y x y x P . Элементы 5 (1,2) этого отношения – пары чисел будут упорядочены отноше- 4 нием включения d b c a d c b a , , . Проверим 3 (0,2) (1,1) теперь будет ли это множество частично упорядоченным. 2 2 , 2 , 2 , 1 , 1 , 1 , 2 , 0 , 1 , 0 , 0 , 0 P . Так как 1 0 x x для 1 (0,1) всех возможных x , то отношение P рефлексивно. P 2 , 1 0 (0,0) и P 1 , 2 , следовательно, P не симметрично. Однако, если 1 y x и 1 x y , то y x , иначе из y x следует Хельмут Хассе (1898 – 1979) – немецкий математик. 10 Рис. 1.9. Рис. 1.10. 1 y x . Таким образом, отношение P антисимметрично. Пусть теперь P y x , , P z y , и 1 и 1 z y y x . Тогда y x и z y и, следовательно, z x , т. е. 1 z x и P z x , . Отношение P транзитивно, тогда P есть частично упорядоченное множество. Его диаграмма Хассе изображена на рис. 1.10. 1.3. Практическое занятие № 1. Операции над множествами. Отношения и функции 1.3.1. Доказать равенства: а) B A B А A \ \ ; б) C B A C B A \ \ \ ; в) C B C A C B A \ \ 1.3.2. Пусть 6 2 x N x A , 4 1 x N x B , 0 4 2 x N x C . Из каких элементов состоят множества: а) C B ; б) C B A ; в) C B A ; г) C B ; д) B C ? 1.3.3. Доказать включения: а) C B A C B A \ \ ; б) C B A B C A \ \ 1.3.4. Пусть U B U A , . Найти множество U X , удовлетворяющее уравнению B A X A X 1.3.5. Доказать, что а) если C B A , то B A и C A ; б) если C B A , то C B A ; в) если C B A , то C A и C B ; г) если C B A , то C B A 1.3.6. Решить систему уравнений , , C X A B X A где C A B 1.3.7. Доказать, что: а) если B A , то A B ; б) если B A , то C B C A ; в) если B A , то C B C A 1.3.8. Решить систему уравнений , \ , \ C A X B X A C A A B , 1.3.9. Доказать, что система уравнений X B X A , имеет решение тогда и только тогда, когда A B , при этом условии решением системы является любое множество X такое, что A X B 1.3.10. Пусть c b a A , , , 4 , 3 , 2 , 1 B , 2 2 1 , B P B A P . Изобразить 1 P и 2 P графически, найти 1 2 1 P P . Проверить с помощью матрицы 2 P является ли отношение 2 P рефлексивным, симметричным, антисимметричным, транзитивным? а) ; 2 , 4 , 4 , 2 , 4 , 1 , 4 , 3 , 2 , 2 , 3 , 2 , 1 , 1 , 4 , , 1 , , 3 , , 4 , , 3 , , 2 , 2 1 P c c b a a a P б) 4 , 4 , 4 , 3 , 2 , 3 , 3 , 3 , 4 , 2 , 2 , 2 , 4 , 1 , 2 , 1 , 1 , 1 , 4 , , 2 , , 1 , , 4 , , 1 , , 3 , , 2 , 2 1 P c c c b b a b P 1.3.11. Найти область определения, область значений отношения P . Является ли отношение P рефлексивным, симметричным, антисимметричным, транзитивным? а) 1 , , 2 2 2 y x P y x R P ; б) y x P y x Z P , , 2 четно. 11 1.3.12. Найти P P P P P P P R D P P 1 1 1 , , , , , для отношений: а) y x N y x y x P делит и , , ; б) y x R y x y x P 3 2 и , , 1.3.13. Пусть A и B - конечные множества, состоящие из m и n элементов соответственно. а) Сколько существует бинарных отношений между элементами множеств A и B ? б) Сколько имеется функций из A в B ? 1.3.14. Построить бинарное отношение: а) рефлексивное, симметричное, не транзитивное; б) рефлексивное, антисимметричное, не транзитивное; в) рефлексивное, не симметричное, транзитивное; г) не рефлексивное, антисимметричное, транзитивное. 1.3.15. На множествах N и N N определим m P и S следующим образом: а) b a P b a m , делится на 0 m m ; б) 0 , 0 , или 0 и 0 и , , , d b c a d b c b d a S d c b a Доказать, что m P и S являются отношениями эквивалентности. 1.3.16. а) доказать, что всякое частично упорядоченное множество содержит не более одного наибольшего (наименьшего) элемента; б) построить пример частично упорядоченного множества, имеющего точно один минимальный элемент, но не имеющего наименьшего элемента. |