какие отношения могут быть между множествами
Лекция 2. Отношение между множествами.
Ищем педагогов в команду «Инфоурок»
Лекция 2. Отношения между множествами.
Между двумя множествами существует пять видов отношений.
Множество В является подмножеством множества А, если каждый элемент множества В является также элементом множества А. Пустое множество является подмножеством любого множества. Само множество является подмножеством самого себя. (пишут В ⊂ А)
Если множества А и В состоят из одних и тех же элементов, то они называются равными.
Существует пять случаев отношений между двумя множествами. Их можно наглядно представить при помощи особых чертежей, которые называются кругами или диаграммами Эйлера-Венна.
Разбиение множества на классы называют классификацией.
Если элементы множества обладают двумя независимыми свойствами, то все множество разбивается на 4 класса. Например, на множестве натуральных чисел заданы два свойства: «быть кратным 2» и «быть кратным 3». При помощи этих свойств в множестве N можно выделить два подмножества А и В. Эти множества пересекаются, но ни одно из них не является подмножеством другого (рис. 6). Тогда в первый класс войдут числа, кратные 2 и 3, во второй – кратные 2, но не кратные 3, в третий – кратные 3, но не кратные 2, в четвертый – не кратные 2 и не кратные 3.
П р и м е р 1. Пусть Х – множество четырехугольников, А, В и С – его подмножества. Можно ли говорить о разбиении множества Х на классы А, В и С, если:
а) А – множество параллелограммов, В – множество трапеций, С – множество четырехугольников, противоположные стороны которых не параллельны;
б) А – множество параллелограммов, В – множество трапеций, С – множество четырехугольников, имеющих прямой угол?
Р е ш е н и е. а) Множества А, В и С попарно не пересекаются. Действительно, если у четырехугольника, противоположные стороны не параллельны, то он не может быть параллелограммом или трапецией. В параллелограмме противоположные стороны попарно параллельны, поэтому он не может принадлежать ни множеству В, ни множеству С. Наконец, в трапеции две противоположные стороны параллельны, а две другие не параллельны, поэтому трапеция не может принадлежать ни множеству А, ни множеству С. Объединение множеств А, В и С даст все множество четырехугольников. Условия классификации выполнены, множество всех четырехугольников можно разбить на параллелограммы, трапеции и четырехугольники, противоположные стороны которых не параллельны.
б) Множества А и В не пересекаются, но множества А и С имеют общие элементы, примером может служить прямоугольник, множества В и С тоже пересекаются: общим элементом является прямоугольная трапеция. Следовательно, нарушено первое условие классификации. Не выполняется и второе условие, так как некоторые четырехугольники не попадают ни в одно из подмножеств А, В или С, таким является четырехугольник с непараллельными сторонами и непрямыми углами. В этом случае множество Х на классы А, В и С не разбивается.
Задания для самостоятельной работы по теме:
Приведите примеры множеств А, В, С, если отношения между ними таковы:
2. Образуйте все подмножества множества букв в слове «крот». Сколько подмножеств получилось?
5. Имеется множество блоков, различающихся по цвету (красные, желтые, зеленые), форме (круглые, треугольные, прямоугольные), размеру (большие, маленькие). На сколько классов разбивается множество, если в нем выделены подмножества: А – круглые блоки, В – зеленые блоки, С – маленькие блоки? Сделайте диаграмму Эйлера и охарактеризуйте каждый класс.
6. Известно, что А – множество спортсменов класса, В – множество отличников класса. Сформулируйте условия, при которых: а) А ∩В=Ø
7. Пусть Х= < x 
N/ 1 
x 15>. Задайте с помощью перечисления следующие его подмножества:
А – подмножество всех четных чисел;
В – подмножество всех нечетных чисел;
С – подмножество всех чисел, кратных 3;
D – подмножество всех чисел, являющихся квадратами;
Разнообразие отношений объектов и их множеств. Отношения между множествами
Урок 4. Информатика 6 класс ФГОС
В данный момент вы не можете посмотреть или раздать видеоурок ученикам
Чтобы получить доступ к этому и другим видеоурокам комплекта, вам нужно добавить его в личный кабинет, приобрев в каталоге.
Получите невероятные возможности
Конспект урока «Разнообразие отношений объектов и их множеств. Отношения между множествами»
· отношения между множествами.
Итак, на первом уроке мы узнали, что такое объект и какие отличительные признаки он имеет. Объект также можно охарактеризовать с помощью отношений, в которых этот объект находится с другими объектами.
Подробнее разберём на примерах.
Антон сын Юрия. Эйфелева башня находится в Париже. Кислород входит в состав воды.
Москва – столица России (является столицей). Антон дружит с Аней.
В данных примерах выделено имя отношения, которое обозначает характер связи между ними.
Таким образом, отношение – это взаимосвязь между объектами.
Одинаковыми отношениями могут быть связаны одновременно несколько объектов.
ученик Антон решил составить генеалогическое дерево своей семьи.
Для этого ему необходимо было узнать, кто в каких отношениях находится. То есть он приходится сыном своего отца (Юрия) и мамы (Татьяны). В свою очередь Татьяна приходится дочерью Леонида (дедушка Антона) и Елены (бабушка Антона). Юрий приходится сыном Григория (дедушка Антона) и Марии (бабушка Антона). Так же у Антона есть сестра Маша. Так как словесное восприятие вызывает затруднение, давайте поможем Антону представить это все в виде схемы и постоим генеалогическое дерево.
Видим, что самыми старшими являются дедушки и бабушки Антона, поэтому расположим их в самом верху.
У Леонида и Елены есть дочь Татьяна, а у Григория и Марии сын Юрий. Значит, разместим их на втором уровне (если считать сверху) и укажем их отношения с родителями в виде стрелок.
У Татьяны и Юрия есть сын Антон и дочь Маша. Разместим их аналогичным образом на нашей схеме.
На данной схеме стрелками указаны отношения, то есть сверху вниз стрелка обозначает, что тот, кто находится выше – приходится отцом или матерью, а тот, кто ниже – приходится сыном или дочерью. В данном случае можно обойтись и без стрелок. Получим следующую схему.
Таким образом, мы узнали, как же можно схематически показать отношение между объектами.
Следует запомнить, что такими отношениями могут быть связаны только объекты некоторых видов. А в отношениях «является элементом множества», «входит в состав» и «является разновидностью» могут находиться любые объекты.
Подходя к рассмотрению отношений множеств, разберём несколько примеров.
Для начала рассмотрим, как отношения связывают два множества.
помидоры – это овощи (являются элементом множества);
тигры относятся к семейству кошачьих;
10 входит в состав двухзначных чисел.
Для графического представления множеств удобнее использовать круги Эйлера.
Существует два каких-то множества A и B (изобразим в виде двух кругов). Итак, если множества имеют общие элементы, то есть элементы одновременно принадлежат и множеству A, и множеству B, то эти множества пересекаются.
Например, Антон учится в 6 «А» классе. В классе восемнадцать человек: 8 мальчиков и 10 девочек.
У трёх девочек и у троих мальчиков по математике оценка пять. Учительница по математике попросила девочек и мальчиков, которые знают математику на пять сесть на средний ряд.
Для решения этого примера изобразим графически два множества: A – множество мальчиков, B – множество девочек. Так, как и в одном и во втором множестве есть ученики, которые знают математику на пять – объединим их и получим следующее.
Пересечением множеств и является количество девочек и мальчиков, знающих математику на пять, то есть это те учащиеся, которые сели на средний ряд.
Множества, не имеющие общих элементов, не пересекаются.
Разберём все тот же пример. В классе у Антона восемнадцать человек: восемь мальчиков и десять девочек. Возьмём A – множество мальчиков, B – множество девочек. Так как ничего общего, указанного в данном примере, между этими двумя множествами нет, то они не пересекаются.
Если каждый элемент множества B является элементом множества A, то B является подмножеством A.
И снова возвращаемся к примеру, с классом Антона. Антон учится в 6 «А» классе. В классе восемнадцать человек. В школе учатся четыре шестых класса. Пусть A – множество параллели шестых классов, B – множество 6 «А» класса. Таким образом, каждый учащийся 6 «А» класса также является учащимся параллели шестых классов. То есть множество B является подмножеством A.
Если каждый элемент множества В является элементом множества А и, наоборот, каждый элемент множества А является элементом множества В, то множества А и В равны.
Например, Антон учится в 6 «А» классе. В школе учатся четыре шестых класса – 6 «А», 6 «Б», 6 «В», 6 «Г». Три из четырёх классов – 6 «Б», 6 «В» и 6 «Г» отправились на экскурсию и в школе из всей параллели 6-х классов остался один 6 «А». Итак, пусть A – множество параллели шестых классов, которые остались в школе, B – множество 6 «А» класса. Таким образом, каждый учащийся 6 «А» класса также является учащимся параллели шестых классов, которые остались в школе. То есть множество B равно множеству A.
Отношение – это взаимосвязь между объектами.
Если два множества имеют общие элементы, т.е. элементы одновременно принадлежат и первому и второму множеству, то эти множества пересекаются.
Множества, не имеющие общих элементов, не пересекаются.
Если каждый элемент множества B является элементом множества A, то B является подмножеством A.
Если каждый элемент множества В является элементом множества А и, наоборот, каждый элемент множества А является элементом множества В, то множества А и В равны.
Разнообразие отношений объектов и их множеств. Отношения между множествами
Урок 4. Информатика 6 класс ФГОС
В данный момент вы не можете посмотреть или раздать видеоурок ученикам
Чтобы получить доступ к этому и другим видеоурокам комплекта, вам нужно добавить его в личный кабинет, приобрев в каталоге.
Получите невероятные возможности
Конспект урока «Разнообразие отношений объектов и их множеств. Отношения между множествами»
· отношения между множествами.
Итак, на первом уроке мы узнали, что такое объект и какие отличительные признаки он имеет. Объект также можно охарактеризовать с помощью отношений, в которых этот объект находится с другими объектами.
Подробнее разберём на примерах.
Антон сын Юрия. Эйфелева башня находится в Париже. Кислород входит в состав воды.
Москва – столица России (является столицей). Антон дружит с Аней.
В данных примерах выделено имя отношения, которое обозначает характер связи между ними.
Таким образом, отношение – это взаимосвязь между объектами.
Одинаковыми отношениями могут быть связаны одновременно несколько объектов.
ученик Антон решил составить генеалогическое дерево своей семьи.
Для этого ему необходимо было узнать, кто в каких отношениях находится. То есть он приходится сыном своего отца (Юрия) и мамы (Татьяны). В свою очередь Татьяна приходится дочерью Леонида (дедушка Антона) и Елены (бабушка Антона). Юрий приходится сыном Григория (дедушка Антона) и Марии (бабушка Антона). Так же у Антона есть сестра Маша. Так как словесное восприятие вызывает затруднение, давайте поможем Антону представить это все в виде схемы и постоим генеалогическое дерево.
Видим, что самыми старшими являются дедушки и бабушки Антона, поэтому расположим их в самом верху.
У Леонида и Елены есть дочь Татьяна, а у Григория и Марии сын Юрий. Значит, разместим их на втором уровне (если считать сверху) и укажем их отношения с родителями в виде стрелок.
У Татьяны и Юрия есть сын Антон и дочь Маша. Разместим их аналогичным образом на нашей схеме.
На данной схеме стрелками указаны отношения, то есть сверху вниз стрелка обозначает, что тот, кто находится выше – приходится отцом или матерью, а тот, кто ниже – приходится сыном или дочерью. В данном случае можно обойтись и без стрелок. Получим следующую схему.
Таким образом, мы узнали, как же можно схематически показать отношение между объектами.
Следует запомнить, что такими отношениями могут быть связаны только объекты некоторых видов. А в отношениях «является элементом множества», «входит в состав» и «является разновидностью» могут находиться любые объекты.
Подходя к рассмотрению отношений множеств, разберём несколько примеров.
Для начала рассмотрим, как отношения связывают два множества.
помидоры – это овощи (являются элементом множества);
тигры относятся к семейству кошачьих;
10 входит в состав двухзначных чисел.
Для графического представления множеств удобнее использовать круги Эйлера.
Существует два каких-то множества A и B (изобразим в виде двух кругов). Итак, если множества имеют общие элементы, то есть элементы одновременно принадлежат и множеству A, и множеству B, то эти множества пересекаются.
Например, Антон учится в 6 «А» классе. В классе восемнадцать человек: 8 мальчиков и 10 девочек.
У трёх девочек и у троих мальчиков по математике оценка пять. Учительница по математике попросила девочек и мальчиков, которые знают математику на пять сесть на средний ряд.
Для решения этого примера изобразим графически два множества: A – множество мальчиков, B – множество девочек. Так, как и в одном и во втором множестве есть ученики, которые знают математику на пять – объединим их и получим следующее.
Пересечением множеств и является количество девочек и мальчиков, знающих математику на пять, то есть это те учащиеся, которые сели на средний ряд.
Множества, не имеющие общих элементов, не пересекаются.
Разберём все тот же пример. В классе у Антона восемнадцать человек: восемь мальчиков и десять девочек. Возьмём A – множество мальчиков, B – множество девочек. Так как ничего общего, указанного в данном примере, между этими двумя множествами нет, то они не пересекаются.
Если каждый элемент множества B является элементом множества A, то B является подмножеством A.
И снова возвращаемся к примеру, с классом Антона. Антон учится в 6 «А» классе. В классе восемнадцать человек. В школе учатся четыре шестых класса. Пусть A – множество параллели шестых классов, B – множество 6 «А» класса. Таким образом, каждый учащийся 6 «А» класса также является учащимся параллели шестых классов. То есть множество B является подмножеством A.
Если каждый элемент множества В является элементом множества А и, наоборот, каждый элемент множества А является элементом множества В, то множества А и В равны.
Например, Антон учится в 6 «А» классе. В школе учатся четыре шестых класса – 6 «А», 6 «Б», 6 «В», 6 «Г». Три из четырёх классов – 6 «Б», 6 «В» и 6 «Г» отправились на экскурсию и в школе из всей параллели 6-х классов остался один 6 «А». Итак, пусть A – множество параллели шестых классов, которые остались в школе, B – множество 6 «А» класса. Таким образом, каждый учащийся 6 «А» класса также является учащимся параллели шестых классов, которые остались в школе. То есть множество B равно множеству A.
Отношение – это взаимосвязь между объектами.
Если два множества имеют общие элементы, т.е. элементы одновременно принадлежат и первому и второму множеству, то эти множества пересекаются.
Множества, не имеющие общих элементов, не пересекаются.
Если каждый элемент множества B является элементом множества A, то B является подмножеством A.
Если каждый элемент множества В является элементом множества А и, наоборот, каждый элемент множества А является элементом множества В, то множества А и В равны.
Отношения. Часть I
Формальная теория моделирования использует алгебраические отношения, включая их в сигнатуры моделей алгебраических структур, которыми описывает реальные физические, технические и информационные объекты, процессы их функционирования. К числу последних я отношу, например, базы данных (реляционные базы данных (РеБД)). Не менее важной считаю область принятия решений, которая состоит из двух основных статистической и алгебраической, основанной целиком на теории отношений. Образовательный уровень специалистов в этой теории близок к нулю.
Откройте учебник по специализации и там увидите в лучшем случае об эквивалентностях, которые авторами трактуются весьма своеобразно. Одного защитившегося уже ДТН спрашиваю: Вы рассматриваете отношение эквивалентности на указывая ни носителя отношения, ни конкретного отношения, как оно у Вас выглядит в записи? Ответ: как выглядит — обыкновенно. Выясняется, что он обо всем этом имеет весьма смутное представление.
Публикаций по проектированию РеБД, кроме иностранных статей назвать затрудняюсь. В 90-х годах был оппонентом, писал отзыв на диссертацию, где рассматривались и иерархические, и сетевые, и реляционные БД. Но как-то год, полтора назад опять на отзыв пришла работа, автор пишет уже только о РеБД, о нормализации отношений БД, но теоретической новизны не показал. Во многих ВУЗах читается курс о базах данных, но не о том, как их создать, создать СУБД, а как правило, о том как эксплуатировать готовую (зарубежную) БД.
Преп. состав не готов научить специалистов IТ-шников создавать отечественные СУБД, ОS, языки программирования, я уж не говорю о БИС, СБИС, заказных БИС. Здесь, по-видимому, поезд ушел давно и надолго. Так что напрасно надуваются у некоторых щеки от гордости (читай снобизма) это видно по комментариям к чужим публикациям, покажите сами, что можете, а не балуйтесь никчемными переводами и перепевками чужого ради предмета гордости — «рейтинга» и «кармы». Сказывается не только отсутствие креатива, но простой образованности и воспитания.
Вторая предметная область неразрывно, связанная с отношениями, — принятие решений. Каждый из нас постоянно занят этим. Мы без решения осознанного или неосознанного пальцем не пошевелим. Мало кто понимает, а еще меньше пишет о решениях. В основе решения любого ЛПР (лица, принимающего решение) лежит предпочтение альтернатив. А моделью предпочтения как раз и является такой тип отношений, который назван «пространством отношений предпочтения». Но кто их изучает. Когда я пришел к «специалисту» по отношениям с вопросом о количестве отношений каждого типа, он не зная ответа, «убил» встречным вопросом, а зачем это Вам?
Понятие отношения
Думаю, что термин отношение знаком каждому читателю, но просьба дать определение поставит большинство в тупик. Причин для этого много. Они чаще всего в преподавателях, которые, если и использовали отношения в процессе преподавания, внимания на этом термине не заостряли, запоминающихся примеров, по-видимому, не приводили.
В моей памяти есть несколько на всю жизнь запомнившихся примеров. Об отображениях и об отношениях. Расскажу вначале об отображениях. Имеется два ведерка с краской. В одном белая в другом — черная. И есть коробка с кубиками (очень много). Грани имеют рельефные номера. Сколькими способами можно раскрасить грани кубиков в два цвета? Ответ неожиданный — столькими, сколько 6-разрядных двоичных чисел, или 2 6 = 64. Поясню подробнее ф: 2→6 отображаются 2 объекта в 6. Каждая строчка таблицы- дискретное отображение фi.
Построим таблицу с 6 колонками и краскам сопоставим число белая — нуль, черная — единица, а граням кубика колонки. Начинаем с того, что все 6 граней белые — это 6-мерный нулевой вектор. Вторая строчка одна грань черная, т. е. младший разряд заполнен 1. и так до исчерпания 6-разрядных двоичных чисел. Кубики ставим в общий длинный ряд. У каждого из них как бы появился номер от 0 до 63.
Теперь отображение наоборот. Пачка листов бумаги (много) и 6 красок (фломастеры).
Фломастерами разного цвета надо пометить обе стороны бумажных листов. Сколько листов потребуется. Ответ f: 6 → 2 или 6 2 =36. Речь идет о произвольных отображениях.
Получили 9 упорядоченных пар элементов из А×А, в паре первый элемент из первого сомножителя, второй — из второго. Теперь попробуем получить все подмножества из декартова квадрата А×А. Вначале простенький пример.
Подмножества будут содержать из А×А разное количество элементов (пар): одну, две, три и так до всех 9 пар, включаем в этот список и пустое множество (Ø). Сколько же получилось подмножеств? Много, а именно 2 9 = 512 элементов.
Определение. Любое подмножество декартова произведения (у нас квадрата) множества называется отношением. Заметим, в произведении используется одно и то же множество. Если множества разные, возникает не отношение, а соответствие.
Символ отношения ставится слева от элементов R(x, y) или между ними x R y; х, у є А.
Определение Множество всех подмножеств множества А называется булеаном. Наш булеан состоит из 2 |А×А| элементов, здесь|А×А| — мощность множества.
Отношения можно задавать в разном представлении над А=
Рисунок 1.2. а)Матрица 4×4 бинарного отношения б) нумерация клеток Матрицы
Здесь используются номера клеток, заполненные единицами на рис. 1б)
— Векторное представление. Двоичный вектор для представления бинарного отношения формируется из элементов <0,1>следующим образом:
Рассмотренный пример задания отношения в векторной форме будет иметь следующий вид:
— Представление графом. Поставим в соответствие элементам множества
А =
Проведем в графе дугу от (xi) к (xj) тогда и только тогда, когда пара (xi,xj) є R (при i = j дуга (xi,xi) превращается в петлю при вершине (xi). Пример (рис. 1а) представления бинарного отношения A[4×4] графом изображен на рис.2.2.
Рисунок 2.2. Представление отношения ориентированным графом
Каталог бинарных отношений (n = 3)
Большое видится на расстоянии. Чтобы почувствовать отношения их разнообразие, мощность мне пришлось вручную создать каталог бинарных отношений над множеством из 3-х элементов, который включил все (боле 500 отношений) отношения. После этого «дошло» или «зашло»об отношениях.
Очевидно, что в каталог войдут 2 3×3 = 2 9 отношений, и каждое из них снабдим набором присущих им свойств. Ниже (табл. 3) приводится полный список всех 512 отношений над множеством А, |A| = 3, из трех элементов. Приводятся также результаты подсчета количества отношений (табл. 2), представленных сочетаниями номеров клеток декартова квадрата 3×3, различных подклассов для различных значений мощности множества-носителя (n = 3). Для каждого отношения указаны его основные свойства и принадлежность типу (табл. 3). Сокращения, используемые в каталоге раскрываются таблицей 2
Таблица 2. Количественные характеристики каталога при разных n
Сущность производимых операций с отношениями и их технику удобно пояснять на примерах, которые особенно просты и понятны для бинарных отношений. В операциях могут участвовать, два и/или более отношений. Операции, выполняемые над отдельными отношениями – унарные операции. Например, операции обращения (получение обратного) отношения, взятие дополнения, сужение (ограничение) отношения. Как пользоваться каталогом поясним примером примером.
Пример 2. Рассмотрим строку Nпр =14 таблицы каталога. Она имеет вид
Первые 9 символов строки (справа от равенства) — это двоичный вектор, соответствующий сочетанию из 9 по 2, а именно, номер первой клетки (отсчет слева направо) номер 5-й клетки матрицы бинарного отношения, т.е. элементы а1а1= а2а2 =1. Это сочетание имеет порядковый номер Ncч = 4 и сквозной номер Nпр = 14 в списке всех отношений. В остальных позициях этой строки стоят либо нули, либо единицы. Нули свидетельствуют об отсутствии свойства, соответствующего названию колонки нуля, а единицы – наличие такого свойства у рассматриваемого отношения.
Свойства и количественные характеристики отношений
Рассмотрим наиболее важные свойства отношений, которые позволят в дальнейшем выделить типы (классы) отношений, применяющиеся в реляционных базах данных в теории выбора и принятия решений и других приложениях. Далее будем обозначать отношение символом [R,Ω]. R- имя отношения, Ω — множество-носитель отношения.
1. Рефлексивность. Отношение [R,Ω] называется рефлексивным, если каждый элемент множества находится в отношении R сам с собой (рис. 2.3). Граф рефлексивного БО имеет во всех вершинах петли (дуги), а матрица отношения содержит (Е) единичную главную диагональ.
Рисунок 2.3. Рефлексивное отношение
2. Антирефлексивность. Отношение [R,Ω] называется антирефлексивным, если ни один элемент из множества не находится в отношении R сам с собой (рис. 2.4). Антирефлексивные отношения называют строгими.
Рисунок 2.4. Антирефлексивное отношение
3. Частичная рефлексивность. Отношение [R,Ω] называется частично
рефлексивным, если один или более элементов из множества не находится в отношении R сам с собой (рис. 2.5).
4. Симметричность. Отношение [R,Ω] называется симметричным, если вместе с упорядоченной парой (х, у) отношение содержит и упорядоченную пару (у, х) (рис. 2.6).
7. Транзитивность. Отношение [R,Ω] называется транзитивным, если для всяких упорядоченных пар (х, у),(у, z) є R, в отношении R найдется упорядоченная пара (х, z) є R или если R×R⊆R (рис. 2.9).
8. Цикличность. Отношение [R,Ω] называется циклическим, если для его элементов
9. Ацикличность. Отношения, в которых отсутствуют контуры называются, ациклическими. Для ациклических отношений выполняется соотношение R k ∩R = Ø для любого k > 1 (рис. 2.11).
10. Полнота (связность). Отношение [R,Ω] называется полным (связным), если для любых двух элементов (у, z) є Ω один из них находится в отношении с другим (рис 2.12). Линейность. Линейные отношения – это минимально полные отношения.
Рисунок 2.12. Линейное отношение
Итак, нами установлено, что отношения, как математические объекты, обладают определенными свойствами, определение которых приведены ранее. В следующем пункте рассмотрим существо и проявление некоторых свойств:
Количественные соотношения таких дискретных пространств представляют большой как
теоретический, так и практический интерес. Ниже рассматриваются некоторые аспекты количественных характеристик, связанных со свойствами отношений разных типов.
Операции над отношениями
Как и большинстве систем счисления с отношениями выполняются операции:
Выше было введено понятие бинарного отношения, как подмножества упорядоченных пар декартова произведения множеств, а также были рассмотрены свойства отношений. Кроме того, были упомянуты бинарные отношения и матричное представление отношений. Рассмотрим теперь понятие отношения более подробно, кроме того, рассмотрим основные операции бинарных отношений, наиболее важные из всего их множества для отношений.
Для них должны выполняться следующие условия:
Унарные операции над отношениями
9. Двойственное отношение (P d ) к отношению Р – отношение, образованное всеми теми парами, которые принадлежат универсальному отношению и не принадлежат обратному отношению (дополнение к обратному):
Двойственное и обратное отношения в совокупности содержат все пары декартова произведения A×A и не имеют общих пар, они также как и отношения Р и P образуют разбиение A×A
Сужение (РА1). Отношение [R1, A1] называется сужением отношения [R, A] на множество Ω1, если Ω1⊆ Ω и R1=R∩Ω1×Ω1. Отношение РА1 на множестве А1 ⊆ А – отношение РА1 на множестве А1, образованное всеми теми парами, которые принадлежат отношению Р и одновременно входят в состав декартова произведения А1 × А1. Другими словами, РА1 – пересечение отношений Р и А1×А1. Пусть А1 =
Операции, требующие не менее двух отношений – n-арные (n-местные). В таких операциях могут участвовать отношения только одинаковой арности. Примеры таких операций: пересечение, объединение, разность, симметрическая разность отношений и некоторые другие. Если в операции используется более чем два отношения, то она выполняется последовательно для двух первых, а затем для итогового отношения и третьего и т.д.
Иначе говоря, эти операции определены для двух отношений. При операциях над отношениями предполагается, что области задания отношений (операндов и результата) совпадают, арности отношений совпадают, и результатом операции снова является отношение той же арности. В качестве примеров будем рассматривать операции над бинарными отношениями P и Q, заданными на дискретном множестве
А =
1. Пересечение (P ∩ Q) – отношение, образованное всеми теми парами элементов из А, которые входят в оба отношения, т.е. общие для P и Q,
P ∩ Q = <(ai aj) | ((ai aj) є P) & ((ai aj) є Q)>.
Матрица отношения P ∩ Q получается как булево пересечение матриц P и Q:
При отсутствии таких общих пар говорят, что пересечение отношений пусто, т.е. оно является нуль-отношением. Пересечением отношений R1 и R2 (R1∩R2 ) называется отношение, определяемое пересечением соответствующих подмножеств из А×А.
2. Объединение (PUQ). Объединением отношений R1 и R2 (R1UR2 ) называется отношение, определяемое объединением соответствующих подмножеств из А×А. Отношение, образованное всеми парами, составляющими или отношение P, или отношение Q, т.е. парами, принадлежащими хотя бы одному из отношений (связка ∨ — или объединительная)
P U Q = <(ai aj) | ((ai aj) є P) ∨ ( (ai aj) є Q)>.
Если в множестве А×А нет других пар, не вошедших в отношение PUQ, а пересечение их нулевое, то говорят, что отношения P и Q при объединении образуют полное отношение А×А, а их система – разбиение этого полного отношения. Объединение матриц отношений образуется как булева сумма матриц отношений:
3.Разность (P\Q) – отношение, образованное теми парами из Р, которые не входят в отношение Q
P\Q = <(ai aj) | ((ai aj) є P)&((ai aj)∉Q)>.
Разность для отношений в матричном представлении имеет вид
4. Умножение отношений. Упорядоченные пары, образующие отношения могут содержать одинаковые элементы, а могут и не содержать. Среди пар, имеющих в своем составе одинаковые элементы, выделим такие упорядоченные пары, которые назовем смежными (примыкающими) и которые имеют во второй паре 1-й элемент, а в первой паре 2-й элемент один и тот же. Определим произведение смежных пар как упорядоченную пару:
( ai ak)∙( ak aj) => (ai aj).
В терминах теории графов сказанное означает, что смежные пары образуют маршрут из точки (ai) в точку (aj) транзитом через точку (ak), состоящий из 2-х смежных дуг. Произведение этих дуг – третья дуга из точки (ai) в точку (aj), реализующая переход между крайними точками маршрута в том же направлении, минуя промежуточную точку (ak). Говорят, что дуга (ai aj) замыкает эти точки напрямую.
5. Симметрическая разность (P∆Q) – отношение, образованное теми парами, которые входят в объединение PUQ, но не входят в пересечение P∩Q. Другая форма определения объясняет название операции: P∆Q образовано теми упорядоченными парами, которые являются объединением разностей P\Q и Q\P. Таким образом, выражение для симметрической разности записывается двумя разными способами:
P∆ Q = (PU Q)\(P ∩ Q) = (P\Q)U (Q\P).
Матрица симметрической разности имеет вид:
Из последней записи следует, что операция симметрической разности допускает перестановку операндов, т. е. коммутативна.
5. Композиция или произведение (P∙Q) – отношение, образованное всеми парами, для которых выполняется:
P∙Q = <(ai aj)|((ai ak) є P) & ((ak aj) є Q)>.
Другими словами, каждая упорядоченная пара в результирующем отношении есть результат умножения смежных пар, из которых 1-я пара принадлежит первому сомножителю-отношению, 2-я – второму сомножителю-отношению. Операция композиции не коммутативна.
Композиция (Р◦Q) на множестве М – отношение R, заданное на том же множестве М, которое содержит пару (x, y), когда существует Z є M такое, что (x, z) є P и (z, y) є Q.
При матричном представлении отношений матрица композиции отношений равна булеву произведению матриц исходных отношений:
Частный случай композиции отношений – квадрат отношения.
Можно показать, используя индукцию, что n-я степень отношения определяется рекуррентно по формуле:P n =P n-1 ◦Р, это означает, что пара (x,y) є P n в том случае, когда в матрице Р существует цепочка элементов: такая, что (xi, xi+1)є P, 1 Литература