Операции над бинарными отношениями

Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

Отношение, обратное к данному. Пусть Р— бинарное отношение на множестве А . Тогда бинарное отношение на множестве А , состоящее из всес таки:в пар (а, Ь) , что (Ь, а) Е, называется обратным (или инверсией) Для и обозначается через

Таким образом, по определению

Например, если F задано равенством , то

= 1), (2, 2), (6, 6), (2, 1), (6, 1), (6,2)}.

Как уже отмечалось, отношение F является областью истинности предиката ” с Делит у ” . Легко видеть, что является областью истинности предиката ” с Делится на у

Заметим, что если бинарное отношение задано диаграммой, то диаграмма обратного к нему отношения получается из данной ” обращением стрелов , т. е. для получения диаграммы отношения нужно в диаграмме отношения каждую стрелку заменить на стрелку

Для иллюстрации обратимся снова к бинарному отношению , заданному равенством (*) . Его диаграмма построена на рис. 8.

Диаграмма отношения в этом случае выглядит как на рис. 10.

Рис. 10

Очевидно, что любое бинарное отношение на множестве имеет обратное и

(Р -1 ) -1 = Е

Композиция. Пусть F и S — бинарные отношения, опреДеленные на множестве А . ТогДа ис композицией называется бинарное отношение 1⁷о S , состоящее из всес пар (с, у) элементов мноэюества А, Для которых во множестве А существует элемент 7- такой, что (с, z) F и (z, у) ? S Таким образом, по опреДелению

или

FoS= {(с,у) 13z ? А(с, z) ? Ел (z,y) ? S}.

П р и м е р. Пусть А = {а, Ь, с} , где а, Ь, с— различные элементы и 1

Тогда F о s =

Примечание. Очевидно, что для отношений F и S , указанных в предыдущем примере, равенство F о S = S о F не верно.

Объединение, пересечение и разность бинарных отношений. Пусть F и S — какие-нибудь бинарные отношения на некотором множестве А . Тогда, по определению, каждое из отношений F и S является подмножеством множества А х А. Отсюда следует, что если применить к F и S одну из операчий СобъеДинение", “пересечение“ либо ”разность"), то снова получим подмножество множества А х А , т. е. — бинарное отношение на множестве А .

Это означает, что можно говорить об операцияс ”объеДинения“, “пересечения" и ”разности“ над бинарными отношениями на данном множестве А и использовать такие же симвоЛЫ для обозначения результатов этих операций как в теории множеств, т. е. И, П и \

Таким образом, по определению, имеем:

а) FUS= {(г,у) (с, у) ? (с, у) S}— объединение отношений и S Ь) {(с,у) (с, у) ? (с, у) е S}— пересечение отношений 1⁵' и S •

с) = {(с,у) (г, у) ? (с, у) S} разность отношений F и S.

П р и м е р. A,F и S — такие, как и в пункте 2. Тогда

8. Свойства бинарных отношений

Отношение на множестве А называется рефлексивным, если (с, с) ? F для любого Е- А, т.е. если Д С F либо в другой записи: F — рефлексивно тогДа и только тогДа, тсогДа ус ? A(cFc)

Очевидно, что равенство является рефлексивным отношением.

Отношение с > у не рефлексивно, однако отношение с > у будет рефлексивным. Геометрически множество , изображающее множество точек плоскости, принадлежащих данному отношению, содержит все точки прямой у г.

Отношение F на множестве А называется симметричным, если из того, что пара (с, у) следует, что (у, с) (- Р' для любых с, у ? А :

или

V УРС).

Заметим, что если А = R , т. е. бинарное отношение задано на множестве действительных чисел, то свойство симметричности имеет наглядное геометрическое выражение:

множество пар Действительныс чисел, принаДлежащиг симметричному отношению, изображается множеством то. чек, симметричныс относительно прямой у = (рис. 11).

У'=х

Рис. 11

Отношение называется транзитив ным, если из того, что (с, у) ? F и (у, 2) F следует, что пара (с, z) е F для любых элементов г, y,z ? А, или

А (zFy Л yFz cFz).

Например, отношение ” больше“ для действительных чисел транзитивно: если с > у и у > z , то и с z.

Отношение называется антисимметричным, если того, что (с, у) ? и (у, с) ? F следует, что с = у , т.е. с, у ? А (cFy Л yFz с = у).

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

Предложение. Пусть F — произвольное бинарное отношение на некотором множестве А .

ТогДа:

1) Р— рефлексивно Д С , где Д — диагональ на множестве А ;

2) 1⁷— симметрично

З) Р— транзитивно FoF С F

2) Р— антисимметрично F П С д .

Докажем, например, утверждение 2)

Пусть F симметрично на множестве А и (г, у) (- F—1 Тогда (у, с) F , откуда в силу симметричности отношения F следует, что (с, у) ?- F , и, значит, С F . Докажем обратное включение.

Пусть (с, у) Р. Отсюда в силу симметричности отношения F следует, что (у, с) ? Е, откуда, по определению, (с, у) е Р—1. Следовательно, F С Таким образом,

Этим доказана импликация

— СИЛЬКТРИЧНО

Докажем обратную импликацию.

Пусть = и (г, у) F для некоторой пары (с, у) е А х А. Тогда в силу равенства Е-1 = F получим, что (с, у) е откуда, по определению, следует (у, г) ? Р. Таким образом,

для любой пары (с, у) ? А У. А и, значит, Е— симметрично.

Отношение порядка

Рефлексивное, транзитивное и антисимметричное бинарное отношение называется отношением частичного поряДка.

Легкб видеть, что известное отношение < меньше либо равно") является отношением частичного порядка на любом множестве чисел.

Другим классическим примером этого типа отношений является отношение С включения“ на множестве Р (А) всех подмножеств произвольного фиксированного множества А.

Бинарное отношение на множестве А называется отношением строгого поряДка, если оно антирефлексивно ((а, а) Р для любого а Е А), транзитивно и удовлетворяет дополнительному условию

У а, Ь е А (aFbv bFa).

Например, отношение ” меньше“ на множестве действительных чисел является отношением строгого порядка.

В дальнейшем для обозначения отношения частичного порядка на произвольном множестве А , как правило, будет использоваться стандартный знак < .

Фраза: (А, — частично упорядоченное множество“ озна-

чает, что на множестве А задано отношение частичного порядка < .

Вместо слов ”частично упорядоченное множество“ используется также сокращенная запись ч.у. множество

Пусть (А, — ч.у. множество. Элементы а, Ь А называются сравнимы.ИИ, если выполняется хотя бы одно из условий a < b либо Ь

Частично упорядоченное множество, в котором любые Деа элемента сравнимы, называется линейно упоряДоченным или цепью.

Пусть (А, — ч.у. множество. На множестве А зададим новое бинарное отношение > по правилу:

Уа, Ь < Ь).

Очевидно, что отношение > также является отношени ем частичного порядка. Этот порядок называется двойственвым к данному.

Заметим, что если взять порядок, двойственный к > , то получим исходный порядок < .

Ч.у. множество (А, >) называется Двойственным к ч. множеству (А,

Пусть Ф — некоторое утверждение о ч.у. множествах, сформулированное в общелогических терминах (и терминах отношения частичного порядка).

Утверждение Ф * , полученное из Ф заменой всес всожДениб знака < на знак Двойственного тс нему отношения, называется утеержДением, двойственным к Ф.

В теории ч.у. множеств имеет место интересный факт, относящийся к теоремам этой теории.

Принцип двойственности. Если некоторое утвержДение Ф верно для всех упоряДоченныс множеств (т.е. является теоремой теории ч.у, множеств), то Двойственное тс нему утвержДение также верно Для всес ч.у. множеств.

Подчеркнем еще раз значение слова ”Для всес" в формулировке принципа Двойственности. Если какое-либо утверждение верно для конкретного ч.у. множества, то этот факт совсем не означает, что и двойственное утверждение будет верным Р этом частично упорядоченном множестве.

Принцип двойственности позволяет ” экономить на доказательствах" (избавляет от проведения лишней работы).

Справедливость его имеет место в силу того, что утверж-

Дение Ф верно в ч.у. множестве (А, тогДа и только тогДа, когда Двойственное тс нему утвержДение Ф* имеет место в ч.у. множестве (А, .

Таким образом, принцип двойственности является непосредственным слеДствием опреДелений двойственного порядка и двойственного ч.у. множества.

Однако для сомневающегося читателя мы можем предложить следующую стаму рассужДений для обоснования этого

принципа.

Пусть Ф— утверждение, о котором говорится выше. Его можно представить в виде импликации Р S двух предложений ( Р— посылка, S — заключение утверждения Ф ) Тогда утверждение Ф * будет выглядеть так:

Пусть теперь утверждение Ф верно в любом частично упоряДоченном множестве.

Пусть (А, — произвольное частично упорядоченное множество. Покажем, что Ф * верно в А . Для этого нужно убедиться в том, что утверждение S* является следствием утверждения Р* (об элементах множества А). Применим метод вспомогательной гипотезы. Предположим, что Р* верно в (А, . Тогда (Р*)* верно в двойственном ч.у. множестве

Далее, очевидно, что (Р*)* = Р, т.е. Р верно в (А, . Отсюда, поскольку импликация Р S верна в любом ч.у. множестве, то S верно в КА, >) , откуда следует, что S* верно в двойственном ч.у. множестве (А,

Таким образом, из предположения справедливости Р* в КА, следует справедливость S * в (А, и, значит, утверждение Р S * верно в КА, , т.е. Ф * верно в (А, <) .

Ниже будут приведены примеры применения принципа двойственности.

Пусть (А, — произвольное ч.у. множество.

Элемент а ? А называется минимальным, если из с < а слеДует с а Для любого ? А .

Двойственным образом получаем определение максимального элемента:

Элемент а называется максимальным, если из с > а слеДует с = а Для любого с ? А

Это означает, что при построении предложения Ф * , двойственного к Ф, необходимо заменить на всех местах слово ” минимальный” на ” максимальный“ и обратно.

Элемент а называется наи.,иеньшим, если а < с Для всес

Двойственное понятие:

Элемент а называется наибольшим, если а > с Для всес

Пр им е р ы:

1. Очевидно, что ВсякиЙ наименьший элемент является МИНИЛшЛЬНЫМ. По принципу двойственности отсюда следятет, что всякий наибольший элемент является максимальным.

2. Покажем, что если в ч. у. множестве (А, существует НОИЛсНЬШИЙ элемент а , то он единственен. При этом во множестве А никаких других наименьших элементов, отличных от а, не существует.

Действительно, пусть а— наименьший элемент в А .

Предположим, что Ь также является натьиеньшил в А Тогда, с одной стороны, а < Ь , поскольку а— наименьший в А , а с другой — Ь < а . Отсюда в силу свойства антисимметричности отношения < следует, что а = Ь

Далее, пусть с— произвольный минимальный элемент в А Тогда а < с , поскольку а— наименьший, откуда в силу определения минимального элемента получим, что а = с .

Отсюда по принципу Двойственности справедливо следукощее предложение: “Если ч.у. множество (А, соДержитп наибольший элемент, то кроме него во множестве А никакис ни НСИб0ЛЬШИС, ни максимальныс элементов не существует

Предлагаем читателю в качестве интересного упражнения

получить текст доказательства этого утверждения из доказательства предыдущего утверждения, заменив в нем каждую фразу двойственной.

Отношение эквивалентности

Наряду с отношениями порядка в математике особую роль играют бинарные отношения, которые одновременно обладают свойствами рефлексивности, симметричности и транзитивности. Любое такое отношение принято называть отношением эквивалентностпи или эквивалентностью на данном множестве.

Для обозначения эквивалентности используется, как правило, станДартньиЈ знак . Например, запись у означает, что с находится в данном отношении с у .

Простейшим примером отношения эквивалентности на множестве Х может служить отношение равенства между элементами этого множества.

Укажем примеры отношений эквивалентности, которые не являются равенством.

П р и м е р 1. Пусть т Z и т > 1 . (Z— множество всех целых чисел). Определим бинарное отношение F на множестве Z как область истинности предиката Р(с, у) .