Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров, страница 6

31 Поскольку отношения на М задаются подмножествами М', для них можно определить те же операции, что и над множествами. Например, отношение 2 нз примера 1.11,6 является дополнением отношения 1, отношение ( является объединением отношений ( и равенства. Определим еще одну операцию над отношениями. Отношение 'называется обрагиылг к отношению Л (обозначение )с-ч), если ал 'а< тогда н только тогда, когда агт<аб Из определения непосредственно следует, что ()<-')-'=Я. Для отношения ( обратным является отношение ~. Свойства отношений.

Отношение )<' называется рефлексивнвглз, если для любого а~М имеет место а)<а. Главная диагональ его матрицы содержит только единицы. Отношение 1< называется антнрефлекснвным, если пн для какого аенМ не выполняется аЛа. Главная диагональ его матрицы содержит только нули. Отношение ( н «нметь общий делитель» рефлекснвны, отношения ( н «быть сыном» антирефлекснвны. Отношение «быть симметричным относительно осн х» не является нн рефлексивным, нн антнрефлекснвным: точка плоскости симметрична сама себе, если она лежит на осн х, н несимметрична сама себе в протвином случае.

Отношение )г назывзется симметричным, если для пары (а, Ь)епМт нз а)<Ь следует Ь)<а (нначе говоря, для любой пары )<' выполняется либо в обе стороны, либо не выполняется вообще). Матрица симметричного отношения симметрична относительно главной диагонали: сн=сп для любых 1 н 1. Отношение 1< называется антпсилзметричнв<лг, если нз аЯат н аг)<а< следует, что а;=а;. Отношение «быть симметричным относительно осн х» является симметричным '.

если первая точка симметрична второй, то н вторая симметрична первой. Пример антнснмметрнчного отношения — отношение (: действительно, если а(Ь н Ь(а, то а=Ь. Нетрудно убедиться в том, что отношение )< снмметрнчпо тогда н только тогда, когда )т=)с '. Отношение)< называется транзитивным, если для любых а, Ь, с нз а)<Ь н й)<с следует а1<с. Отношения «равенство», (, «жнть в одном городе» транзнтнвны; отношение «быть сыном» нетранзнтнвно.

Отношение «пересекаться», т. е. «нметь непустое пересечение», заданное на системе множеств, также нетранзнтнвпо. Например, (1, 2) пересекается с (2, 3), (2, 3) пересекается с (3, 4), однако (1, 2) н (3, 4) не пересекаются. ' Эта фраза вовсе не ивлветсв тавтологией, так как два упоминанни в ней термина «симметричный» имеют разный смысл и относится к двух разным типам объектов; первое упоминание — к свойству пар точек на плоскости, а второе — к свойству отаошении между парами точек. 32 л Для любого отношения Я отношение )с, называемое транзитиенгнм зажыканиг и К, определяется следующим образом: л аЯЬ, если в М существует цепочка из и элементов а=аь аз, ..., а„ь а„=Ь, в которой между соседними элементами выполнено )1: а)1аз, абаз, ..., а ЯЬ. Если )1 транзитивно, л л то К =Е.

Действительно, если а)1Ь, то а)1Ь (цепочка сод л стоит из двух элементов а, Ь), поэтому Я: — )1. Если же а)сЬ, то существует цепочка а1га„аз)газ, ..., ач-~Н. Но так как )1 л транзитивно ', то аЯЬ, поэтому 11с:-)с. Из включения в обе д стороны следует Р=й. Транзитивным замыканием отношения «быть сыном» является отношение «быть прямым потомком», являющееся объединением отношений «быть сыном», «быть внуком», «быть правнуком» и т. д. Транзитивпым замыканием отношения «иметь общую стену» для жильцов дома является отношение «жить на одном этаже». Отношения эквивалентности.

Отношение называется огг«ошениел~ эквиеалгигности (или просто эквивалентностью), если оио рефлексивно, симметрично и траизитивно. Пример 112. а. Отношение равенства Е на любом множестве является отношением эквивалентности. Равенство— это минимальное отношение эквивалентности в том смысле, что при удалении любой пары из Е (т. е. любой единицы на диагонали матрицы Е) оно перестает быть рефлексивным и, следовательно, уже не является эквивалентностью. б.

Утверждения вида (а+Ь) (а — Ь) =а' — Ь' или з)из х+ +сонях=1, состоящие из формул. соединенных знаком равенства, задают бинарное отношение на множестве формул, описывающих суперпозицни элементарных функций (см. пример 1.10,г). Это отношение обычно называется отношением равносильности и определяется следующим образом: формулы равносильны, если они задают одну и ту же функцию.

Равносильность, хотя и обозначается знаком =, отличается от отношения равенства Е, так как оно может выполняться для различных формул (впрочем, можно считать, что знак равенства в таких соотношениях относится не к формулам, а к функциям, которые имн описы- ' В этом рассуждении используется тот фзкт, что транзитивное отношение «риспрострзняется по цепочке» не только нз трех (как унизано и определении), но и из любого числа элементоя. 3 — 750 ваются). Отношение 4' для формул — это совпадение формул по написанию.

Оно называется графическим равенством. в. Рассмотрим множество треугольников на плоскости, считая, что треугольник задан, если заданы координаты его вершин. Два треугольника называются конгруэитными (иногда их называют просто равными), если они при наложении совпадают, т. е. могут быть переведены друг в друга путем некоторого перемещения. 1(онгрузнтность является отношением эквивалентности па множестве треугольников. г. Отношение «иметь один и тот же остаток от деления на 7» является эквивалентностью на Л~. Это отношение выполняется, например, для пар (11, 46), (!4, 70) и не выполняется для пар (12, 13), (14, 71).

Пусть на множестве М задано отношение эквивалентности )г. Осуществим следующее построение. Выберем элемент а~еяМ и образуем класс (подмножество М) Со состоящий из а~ и всех элементов, эквивалентных аб затем выберем элемент аз фС1 и образуем класс См состоящий из а» и всех элементов, эквивалентных ам и т. д. Получится система классов С1, См„(возможно, бесконечная) такая, что любой элемент из М входит хотя бы в один класс, т.е. (.) С; =М. Эта система классов обладает следующими свойствами: 1) она образует разбиение, т.е. классы попарно не пересекаются; 2) любые два элемента из одного класса эквивалентны; 3) любые два элемента из разных классов не- эквивалентны. Все эти свойства немедленно вытекают из рефлексивности, симметричности и транзитивиости )г, Действительно, если бы классы, например С1 и См пересекались, то они имели бы общий элемент Ь, эквивалентный а1 н а„ но тогда из-за транзитивности 11 было бы аЯа„что противоречит построению Сь Аналогично доказываются другие два свойства.

Построенное разбиение, т. е. система классов, называется системой классов эквивалентности по отношению 11. Мощность этой системы яазывается индексом разбиения. С другой стороны, любое разбиение М на классы определяет некоторое отношение эквивалентности, а именно, отношение «входить в один и тот же класс данного разбиения». Пример 1.13. а. Все классы эквивалентности по отноше. нию равенства Е состоят из одного элемента. б.

Формулы, описывающие одну и ту же элементарную функцию, находятся в одном классе эквивалентности по отношению равносильности. В этом примере счетны само множество формул, множество классов эквивалентности (т. е. индекс разбиения) и каждый класс эквивалентности. в. Разбиение множества треугольников по отношению конгруэнтности имеет континуальный индекс, причем каждый класс также имеет мощность континуум. г. Разбиение У по отношению «иметь общий остаток от деления на 7» имеет конечный индекс 7 и состоит из 7 счетных классов О, 7, 14...; 1, 8, 15...; 2, 9, 16...; ...; 6, 13, 20...

Отношения порядка. Отношение называется огкошениси нестрогого порядка, если оно рефлексивно, антисимметрично и транзитивно. Отношение называется отношением строгого порядка, если оно антирефлексивно, антиснмметрично и транзитивно, Оба типа отношений называются отношениями порядка, Элементы а, Ь сравнимы по отношению по- рядна Й, если, выполняется а)сЬ или Ь)га. Множество М, на котором задано отношение порядка, называется полностью упорядоченным, если любые два элемента М сравнимы, и частично упорядоченным в противном случае. Пример 1.14.

а. Отношения ( н ) для чисел являются отношениями нестрогого порядка, отношения ( и )— отношениями строгого порядка. Оба отношения полностью упорядочивают множества У и (г. б. Определим отношения ( и ( на Я" следующим образом; (аь .. а„)((Ьь ..., Ь,), если а~<Ьп ..., а,<Ь«; (аь ... ..., а„) < (Ь|, ..., Ь„), если (аь ..., а„) : (Ьь ..., Ь,) и хотя бы в одной координате 1 выполнено а, с.Ьь Эти отношения определяют частичный порядок на )г": (5, 1(2, — 3) ((5, 2/3, — 3); (5, 1/2, — 3) и (5, О, О) не сравнимы. в. На системе подмножеств множества М отношение включения ~ задает нестрогий частичный порядок, а отношение строгого включения ~ задает строгий частичный порядок. Например, (1, 2)~(1, 2, 3), а (1, 2) и (1, 3, 4) не сравнимы.

г. Отношение подчиненности иа предприятии задает строгий частичный порядок. В нем несравнимыми являются сотрудники разных отделов. д. Пусть в списке букв конечного алфавита А порядок букв зафиксирован, т.е. всегда один и тот же, как, например, в русском или латинском алфавите цифр. Тогда этот список определяет полное упорядочение букв, которое назовем отношением предшествования н обозначим ( (а,(аь 3» если а; предшествует а~ в списке букв). На основе отношения предшествования букв строится отношение предшествования слов, определяемое следующим образом.