Основы дискретной математики В.А. Осипова (Основы дискретной математики В.А.Осипова), страница 3

Так как А П В = А, то А О В = (А П В) О В. По закону поглощения (см. тождество 9) В О (А П В) = В. Отсюда, используя закон коммутативности, получаем А О В = В. Докажем, что из третьего предложения следует первое. Так как А С А О В, а по условию третьего предложения А О В = В, то А С В. 1.1.3. Упорядочение. Прямое произведение множеств Введем понятие упорядоченной пары и упорядоченной и-ки элементов.

Как н понятие множества эти понятия являются исходными, неопределяемыми. Упрорядоченна пара < х, у > интуитивно определяется как совокупность, состоящая из двух элементов х и у, расположенных в определенном порядке. Две пары < х, у > и < и, и > считаются равными тогда и только тогда, когда х = и и у = и. Упорядоченная и-ка элементов х1, хгп ..., х„обозначается < Х1, Хг, ..., Ха > И, ПО ОПРЕДЕЛЕНИЮ, ЕСТЬ «Х1,Ха,...,Х„1>,х„> Элементы х1, хз, ..., х„называются компонентами или координатами и-ки.

Упорядоченная п-ка называется также кортежем из элементов х1, хз, ..., х„. Координаты точки на плоскости — упорядоченная пара чисел, координаты точки в пространстве — упорядоченная тройка чисел. Очередь из покупателей в магазине, кортеж автомобилей при встрече официального лица являются примерами таких упорядоченных наборов элементов. Прямым произведением множеств Х и У называется совокупность всех упорядоченных пар < х, у > таких, что х Е Х и у Е У. Обозначается прямое произведение множеств Х и У через Х х У, !3 ь 2 зжожясувл я отноыяяяя пр р 1.8.

1.пу х=(1,2,2),У=(8,1) т д х У=(<го>, <11>, <г о>, <2 1>, <З.О>, <3,1>); у х-(<аг>,<о,г>,<о,з>,<1,1>, <1, З>. <1, З>) му ° р,.дд х У, хУА АУ Х. р (О, 1) (1, г1 Р (О, 1). (О, 2), (1,<1), 13 )(А(в)(С (А(с)((В(с), )А)(ВОС) (А(В)(С1 д)А((в(с) (А)В)с(АПС), .) Ая(вяс)-(А<в)+с ) АП(В Я С) = (АПВ) Я (АСС). 3 Д ) (Аов)со д д д Асср всс, б)дсвпс д . «д. д А<В АСС, )АПВСС дв ° я*яд .д АФВОС, )АСВССу д у д д, д АСВСС б Д 3 Я„,Р(дпв)-Р(л)пр(в) Уяурдг,р,джАВС » АбВ ВбС..

Аяс, б) . АСВСС АСВСС, ° АСС=С, ) ААВ ВАС, Афс. ) АСВнС ВЯАСС, В=Ф 8 Рв «уур я АПХ=В: АСХ-С, Р, 1.2 Зд ур 1. Д, ((1,2),(2,3))А(1,2,3) А и С = Ф, (А П В) ) С = Фу 3 Д в А ) (А П В) С (А П В) = (А С В) П (А С В) = А, б) (АСВ)ПА=АПВ, д А,В С вЂ” д,В<АСС , '(АСВ) (Ссс)-(А С)П(В «С), б)(А>в) с=(А с)с(в»сх )(А)в) С=(А С)((В С); )А (В(с)=(А В))(А С) и и А,в<Ф (А в)и(в А)=-с В д 1б Пр .р 1.7. ПУ Х ( (! ~~!) Ро=.)',У>)<У. >б ) Рн У УНУОжббтнб Н ОтНОНННИЯ 1.2.

Бинарные отношения. Специальные бинарные отношения 1.2.1. Обы ее н о ш няя К я б, Я.. РУ Р =(<* >) УУ 1 У,' У У'б0 Су >ну) 2' )и Ру)'=-р,' пр я Л. Уу, > Р, ~У*> ° РУУ РЯ У 1.2.2. Снуцняяьны«бнн рны тн ш ння й ,у б .РЕХ *ру Ру у~ Главе 1. МНОЖЕСТВА И ОТНОШЕНИЯ Рефлексивное, симметричное и транзитивное отношение на множестве Х называется отношением эквивалентности на множестве Х.

Пример 1.8. 1. Отношение равенства на множестве целых чисел есть отношение эквивалентности. 2. Отношение подобия на множестве треугольников есть отношение эквивалентности. 3. Отношение х < у на множестве действительных чисел не рефлексивно, не симметрично, но транзитивно на этом множестве. 4. Отношение сравнимости по модулю натурального числа п на множестве целых чисел .'Е: х = у [тод п) тогда и только тогда, когда х — у делится на п. Это отношение рефлексивно на .'Е, так как для любого х Е Е х — х = О, и, следовательно, делится на п.

Это отношение симметрично, так как если х — у делится на п, то у — х делится на п. Это отношение транзитивно, так как если х — у делится на п, то для некоторого целого $1 имеем х — у = $1п, а если у — г делится на и, то для некоторого целого 12 имеем у — и = 12п. Отсюда х — г = [г1+ 12)п, т. е, х — э делится на п. 5. Отношение принадлежности к одной студенческой группе на множестве студентов института — отношение эквивалентности. б.

На множестве Ы х Ы, где И вЂ” множество натуральных чисел, определим отношение р: < х, у > р < и, и >с=> хи = = уи. Это отношение рефлексивно: < х, у > р ( х, у >, так как ху = ух; симметрично: если < х, у > р ( и, и >, то ( и, и > р < х, у >, так как из хи = уи следует, что и иу = их; транзитнвно: если < х, у > р ( и, и >, с и, и > р ( ю, г >, то < х, у > р с ю, и >, так как, перемножая левые и правые части равенств хи = уи и ия = ию, после сокращения получаем хн = ую. Пусть р — отношение эквивалентности на множестве Х.

Классом эквивалентности, порожденным элементом х, называется подмножество множества Х, состоящее из тех элементов у е Х, для которых хру. Класс эквивалентности, порожденный элементом х, обозначается через [х): [х] = 1У) У Е Х и хру). 1.2. Вннарные отношения. Спецеальные наварные отношення 19 Пример 1.9. 1.

Отношение равенства на множестве целых чисел порождает следующие классы эквивалентности: для любого элемента х Е Е [х] = 1х), т. е. каждый класс эквивалентности состоит только из одного элемента — числа х. 2. Отношение сравнимости по модул1о числа и на множестве целых чисел '.Е порождает следующие классы эквивалентности: вместе с любым числом а е Е в этом же классе эквивалентности содержатся все числа вида а+ 1п, где й — целое. Очевидно, что числа О, 1, 2, ..., и, — 1 гюрождают различные классы эквивалентности, которые обозначим [О), [1], [2], ..., [и — 1]. Они называются классами вычетов по модулю п.

Все остальные классы эквивалентности для этого отношения совпадают с ними, так как любое число а 6 .'Е можно представить в виде а = уп + т, где О < т ( и. 3. Для отношения принадлежности к одной студенческой группе классом эквивалентности является множество студентов одной групшя. 4.

Класс эквивалентности, порожденный парой < х, у > для отношения р из примера 1.8, п. 6, определяется соотношением х и1 [<х,у>)= <и,и> у и Каждый класс эквивалентности в этом случае определяет одно положительное рациональное число. Ъ'тверждение 1.3. Пусть р -- отношение эквивалвьнпности на множестве Х. Тогда 1) если х' б Х, то х б [х]', 2) если х, у Е Х и хру, то [х] = [у] [т. в. класс эквивалентности порождается любым своим элементом).

Для доказательства первой части утверждения достаточно воспользоваться рефлексивностью отношения р: хрх и, следовательно, х е [х]. Докажем вторую часть утверждения. Пусть я Е [у). Тогда урн и в силу транзитивности отношения р хря, т. е. я е [х]. Отсюда [у] С [х]. Аналогично в силу симметричности р можно показать, что' [х) С [у], а значит, [х] = [у). Разбиением множества Х называется совокупность попарно непересекающихся подмножеств Х таких, что каждый элемент множества Х принадлежит одному и только одвюму из этих подмножеств.

20 Глава 1. МНОЖЕСТВА И ОТЕ1ОШЕНИЯ 1зв Бинарные отношения. Специальные бинарные отношения 21 Пример 1.10. 1. Х = 11, 2, 3, 4, 5). Тогда 1[1, 2), 13, 5), [4)) — разбиение множества Х. 2. Пусть Х вЂ” множество студентов института. Тогда разбиением этого множества является, например, совокупность студенческих групп. 'Утверждение 1.4. Всякое разбиение множества Х определлет на Х отпношение эквивалентностпи р: хру тпогда и только тогда, когда х и у принадлежат одному подмножеству разбиения.

Рефлексивпость и симметричность р очевидны. Пусть теперь хруиуря. Тогдах,у Е Х1, у, и Е Хг,гдеХ1 иХ2 подмножества из разбиения Х. Поскольку у Е Х1, у Е Хг, то Х1 = Хг. Следовательно, х, г Е Х1 и хрг. 'Утверждение 1.5. Всякое отпношение эквиволентностпи р определяет разбиение множества Х на классы эквивалентностпи относительно отлого отношения. Докажем, что совокупность классов эквивалентности определяет разбиение множества Х.

В силу утверждения 1.3 х е [х], а следовательно, каждый элемент множества Х принадлежит некоторому классу эквивалентности. Из утверждения 1.3 вытекает также, что два класса эквивалентности либо не пересекаются, либо совпадают, так как если и Е [х] и -" Е [у],то хрг, откуда [х] = [я],и ург, откуда [у] = [г].

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

Пример 1.11. 1. Отношение х < у на множестве действительных чисел есть отношение частичного порядка. 2. Во множестве подмножеств некоторого универсального 'множества 5т отношение А С В есть отношение частичного порядка. 3. Схема организации подчинения в учрезкденин есть отношение частичного порядка на множестве должностей. Отношение частичного порядка на множестве Х, для которого любые два элемента сравнимы, т. е. для любых х, у б Х х '~ у или у ~ х, называется о~ношением линейного порядка. Пример 1.12. В примере 1.11 отношение, определенное в п. 1, есть отношение линейного порядка, а отношение, определенное в п. 2, таковым не является.