В.Н. Нефедов, В.А. Осипова - Курс дискретной математики, страница 4

Пусть теперь хру н ург. Тогда х, уш Хь у, ген Х>. где Х, н Хз — подмноже,ства из разбиения Х. Поскольку ушХь ушХь то Х, Хз. Следовательно, х, гшХ> и хрг. Утзирисжние 0.3. Всякое отношение эквивалентности р определяет разбиение множества Х на классы зквиваяентности относительно этого отношения Докажем, что совокупность классов эквивалентности опре,деляет разбиение множества Х.

В силу утверждения 0.6 х ш]х]. а следовательно, каждый элемент множества Х принадлсжиг некоторому классу эквиваленш>ости, Из утверждения 0.6 выте.кает также, что два класса эквивалентности либо не пересекаются, либо совпадают, так как если гш ]х] и гш ]у], то хрг, откуда ]х] = ]г], н ург, откуда ]у] = ]г]. Следовательно, ]х] = ]у]. Совокупность классов эквивалентности элементов множества Х по отношению эквивалентности р называется фактор-мно.жежвом множества Х по отношеяию р и обозначается К/р. Рассмотрим е>пе один тип специальных бинарных отноше. лий.

Отношение р на множестве Х называется антисимметричнмм, если для любых к, ушХ нз хру н урх следует х =- у. Рефлексивнос, антисимметричнос н транзнтнвное отношение ч>азывается отношением частичного лорлдка на множестве Х н обозначается символом (. Пример 0.13. !. Отношение х ( у на множестве действительных чисел есть отношснис частичного порядка.

2. Во множестве подмножеств некоторого универсального множества О отношение Л ш В есть отношенае частичного порядка. 3. Схема оргапнзапии подчинения в учреждении есть отпошенис частичного порядка на множестве должностей. Отношение частичного порядка на множестве К, для которого любые два элемента сравнимы, т. е. для любых х, уж К х(у или у(х, называется отношением линейного порядка. Пример 0.14. В примере О.!3 отношение, определенное в и. 1, есть отношение линейного порядка, а отношение, определенное в п. 2, таковым не является.

Заметим, что мы определили тип отношений, прсобраеом которых служит интуитивное понятие отношания порядка (прели>ествовання, предпочтения). Пусть на множестве Х задано отношение частичного порядка р. Как можно задать отношение частичного варнака иа мио>кестве Х Х Х, т. е. как сравнивать пары элементов нз мнсшестт — !зш 7 ва Кр Одна из возможных способов состоит в следуюшем: на множестве К)(К определяем отиоюеипе П услозиеы (а, Ь)П<с, Л>.сэорс н Ьру. Отношшше П есть отношение частичного порядка.

Оио называется отношением Парето. Множество К с заданным иа нем частичным (линейным) порядком называется чосгочяо (япнейхо) упорядоченяыл. Рассмотрви непустое конешиж мнгпкеспю К, нз кшороы задано отношение частичного порядка (. Запишем «(у, сслэ х(у к хчьу. Говорят, что элемент д покрывает элемент х, если х(д и не суоыствует таного элемента и, что х(и(д. Тогда х(у равносильно тому, что сушествуни такие элементы х,..., х„, что х=к~(хт( ..

(х =д, где хин покрывает хг. Любое частично упорядоченное множество можно предсгазнть в воле схемы, в кошрой каждый элемаш пзображается точкой на нлоскостн, н если д покрывает х, то точки к и д ссаюы няют отрезком, причем точку, соответствующую х, располагают ниже у. Такие схемы называются дпаграммамн Хассе. На рпс. 0.2, о, б показаны две диаграммы Хассе, причем вторая соответствуег линейно упорядоченному множеству. :ее~ и) л) б) Ркс од Рнс. пэ Пример 0.13. Рассмотрим три отношения частичного порядка и построим для ипх диаграммы Хассе: !. Пусть А (1, 2, 3), Йа множестве Р(А) рассмотрим отношение «быть подмножествам». Множество Р(А) солсржпт восемь элементов: (!г», (1), (2), (3), (1 2), (!.

3) (2 3). (1. 2. 3)). Его диаграмма Хассе изображена на рис. 03 о (отршок соелнняюгний точки (1, 2) и (1, 2 3), на рисувие пе показан). 2. Пусть К (1, 2, 3, 5, б, !О, 1б. 30). На этом еосьмиэлемеитном множестве рассмотрим отношение частичного порядка кт(дчюу делится иа х». диаграмма Хассе для этого отношения изображена на рис. 0.3,6 (отрезок, соединяющий точки б н 30, на рисунке не показан). га 3. На множестве К = (1, 2, 3, 4, й б, 7, 3» рассмотрнм атно. шапке лппейного порядка ~.

Бго дкаграмма Хассе изображена на рнс. 0.3, з. Заметны, что диаграммы Хассе первых днух атношепвй совпадают. Это означает, что зтн частвмю упорядоченные множе. агва нмеют одинаковую струмтуру, нрпчем отличную от струн- туры третьего частична угюрядоченного множества, хотя оно тоже содержит восемь влемснтов. Более точно такая общность струнтуры определяется понятием пзоморфнзма.

дза чзсппиз тзсрзпзчпипгх иззж смз Х я у хззызаюгс шз зрй зг ыь зсла стызсгзует Лксзак Е:Х у, сз рзнякжмя з щ хм е чамзчкзгь «срял з. минич сз зз к,,(х гзгха а темза гзгла, «с ла ч(х )(ч(х), 9 Ы ( и С вЂ” огаазсяха часппизгз пзр зка, ылаи е а азжсспжх Х и в Г ех змсгзммз. Частично упорядоченные множества, рассмотренные в примере 0.13 (пункты 1 н 2), нзоморфвы.

Утвержденне 0.0. Всамое частично улорядоеишое ммхиесл ао Х гмоморфио некоторой системе ладмиамесгза множества Х, чосгичио упорлдочеллой отношением еключепиж Для каждого элемента аж К рассмотрим множество 5 = (хснХ)х(а». Тогда 5,щХ п (5,»ащХ) — совокупность всех танях подмножеств. Докажем, что зта скстема пгжмножеств, частично унорядоченнзя откошенпем включенпя, нзоморфна Х. Рассмотрим счображеппе агХ-е (5 ) а сяК» такое, что 0(а) = 5 . Тогда а — бпекцкя. Действительно, если 5 = =Вь, то, поскольку аак5, в силу рсфлсксввностн (, пмеем ашуь и а(Ь. Аналогнчио получаем Ь(а п в сплу аптпспммет.

ркчностн ( нмсем а=-Ь, т. с. отобрюкеппе а кнъектпвна. Кроме того, а сюръектнвно, так кан у любого подмножества 5 еегь прообраз а Докажем, что отображение сохраняет отношекие частпчного порядка. Пусть а(Ь. Тогда пз х(а в силу транзптпвгюстп отношения ( следует х(Ь, а злачпт, к 5 гл5ь. Беля 5 ан5ь, то, поскольку аш5ю имеем аш5ь откуда а(Ь. Задачм н упражнення !. Прявестп прнмсры опюшенкйг а] не рефлексивного, но снмметрпчиого к транзптнвногог б) не снмметркчного, по рефлексквного к травзятнвпого; в) не транзнтнвного, но рефлексквного к симметричного.

2. На множестве прямых на плоскости рассмотрам ство. шалвы йз 13 я) параллельности прямых; б) перпендикулярности прдыых. Определить, будут ли этн отиопгепия отноюениими эиввввлыпнссти на агом множестве. 3. На множестве Р)х Д), где Аг — множество нзтуралыгых чисел (1, 2, 3...), определим отношение р: <к, р> р (гь «>чюх+ о р+ л. Доказать, что р — отношение эквивалентности на этом множестве. 4. Доказать, что пересечение отношений эквивалентности яв множестве Х есть отвошение эквивалентности на этом множестве. 5. Доказать, что объедвнеиие ргОрт двук отношений эквивалентности рг и рт заданных ва множестве Х, является агнш шепнем эквивалентности тогда и талька тогда, кагпа рг))рг ргО рзб. Доказать, что сслн р — частичный порялок, то р-' — также частичный порядок. 7.

Привести пример линейного порядка на множестве Аг х Аг. где Аг — миожаство натуральных чисел. 5. Доказать, что всякий частичный порядок на конечною множестве может быть продолжен до линейного порядка. 04. АЛГЕБРАИЧЕСКИЕ ОПЕРАЦИИ Систематизируем пшгятие алгебраической операции. с которым мм уже встречались в различных разделак курса математик». Пусть дано множество М. Говорят, чта на М определена бинарная алгебраическая операция, если всякой упорядоченной паре элементов множества М по некоторому закону ставится в соответствие вполне определенный элемент этого же множества. Примерами бинарных операций на множестве целых чиссг являются сложение м умножение.

Однако нашему определению не удовлетворяют, например, множество отрицательных целых чисел относительно умножение и множество действительных чисел относительно деленна нз.за невозможности деления на. нуль. Среди известных бинарных операций, произеодииык не пап числами, отметвм векторное умножение векторов пространства умножение квадратных матриц зарядка л, коыпазицию апгбрежений множества Х в себ», теоретико-многкествепнае обьединение и пересечение множеств.

Кап видим, фактическое задание алгебраической операцигз нз множестве может быть произведено различнымв мапжамя. Возможно также непосредственное перечисление всех ршультатов операпни лля конечных множеств. Его удобно описать с помощью таи нааываемой таблицы Кэпи. Слева и сверху нвадрагнай таблицы выпнсмвают все элементы множества.На пере- 20 тззз н Ог Тзаэзчз 02 сечении строки, соответствующей элементу а, и стоабца, свцветствующего элементу Ь, записывают результат операции над а и 6. Из двух приведенных таблиц Кэпи (табл.

0.1 и 0.2] вторая — таблица для операции конъюнкции на множество (И, Л), о которой будет говориться в гл. Е булем употреблять следующую терминоиогаю и снмволикуг опеРацию называть умножением, а результат применения операции к элементам а и Ь вЂ” произведением аЬ. Это мультиплнкатнвная терминология. Иногда естественнее и удобнее испольаовать адаптивную терминологию и сиыволикуг операцию называть сложением, а результат ее выполнения — суччой а +Ь" элементов а и Ь. Если для любых элементов а и Ь множества М справедливо равенство аб = Ьа, то операцию называют ковлртатсзлой. Коммутатнвиы, например, сложение н умножение чисел, сложение матриц одного порядка и т. д.

Нексммутатизвымн ояерацняыи являются векторное произведение векторов, произведение матриц порядка л при л ) 2 н др. Если Лли любых элемептов а, 6, с множества М справедливо равенство а(Ьс) (аВ)с, та операцию называют асгочяагиз«ой. Ассоциативны, например, сложение и умножение целых чисех, умножение матриц, «омпозипи» отображений, а также операции, определенныс таблицамн Кэпи. Неассопиативной операцией является векторное умножение венторов прсстраиства.

Е ряде сл)пасв множесгво М, на кщором определена алгебраическая операция, обладает едяяи«нмл элементом. т. е.. таким элементом е, что ае = са = а дл» всех а нз М. Елиничный элемент единственен, так как если существует еще один зэемент е' с этим же свойством, то се' = е и ее' е', откуда е =- з'. Пря алднтивной записи слиничный элемент называется нулевым н обозначастси О. На миопгестве квадратных матриц порядка я едгщнчныю т!' млементом относительно операции учножеии» является едииичпая матрица, на множестве отображений множества Х в себи единичным элементом относиюльно композиции отображений является тождественное отображение.