Харьковский национальный университет радиоэлектроники, кафедра АПВТ, тел , е-mail: 1 ТЕОРИЯ МНОЖЕСТВ БИНАРНЫЕ ОТНОШЕНИЯ. ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ ЛЕКЦИЯ 4 С.В.ЧУМАЧЕНКО Факультет компьютерной инженерии и управления, кафедра АПВТ, ХНУРЭ ДИСКРЕТНАЯ МАТЕМАТИКА

ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Бинарные отношения. Отношение эквивалентности Март, Цель лекции – изучить свойства бинарных отношений, способы их задания для применения в задачах компьютерной инженерии Содержание: Определение бинарного отношения Способы задания бинарных отношений Свойства бинарных отношений Бинарное отношение эквивалентности Классы эквивалентности Применение в задачах компьютерной инженерии Тема: Бинарные отношения. Отношение эквивалентности

ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Бинарные отношения. Отношение эквивалентности Март, Литература Горбатов В.А. Основы дискретной математики. М.: Высш. шк., с. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Наука. Главная редакция физико-математической литературы, с. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергия, с. Богомолов А.М., Сперанский Д.В. Аналитические методы в задачах контроля и анализа дискретных устройств. Саратов: Изд-во Саратовкого ун-та, с. Новиков Ф.А. Дискретная математика для программистов. С.-П., С Хаханов В.І., Хаханова І.В., Кулак Е.М., Чумаченко С.В. Методичні вказівки до практичних занять з курсу Дискретна математика. Харків, ХНУРЕ с.

ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Бинарные отношения. Отношение эквивалентности Март, Термины Базовые понятия: множество подмножество упорядоченная пара вектор декартово произведение декартова степень отношение Ключевые слова: бинарное отношение матрица смежности граф фактор-множество рефлексивность симметричность транзитвность отношение эквивалентности

ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Бинарные отношения. Отношение эквивалентности Март, n Def: бинарным (двухместным) отношением на множестве M называется подмножество декартова квадрата множества М: R 2 М 2 n n=2 степень отношения (бинарное) Определение бинарного отношения Множества Декартово произведение A B Декартов квадрат A 2 Бинарное отношение R 2 A 2

ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Бинарные отношения. Отношение эквивалентности Март, Способы задания бинарных отношений Матрица смежности Def: матрица смежности бинарного отношения на множестве А={а 1, а 2, а 3, …¾, a n } – это таблица размера n n, в которой элемент c ij, определяется следующим образом : Пример Дано: А={а, b}, R 2 ={(a,a), (b,a)} A 2 Матрица смежности бинарного отношения R 2 представляется так:

ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Бинарные отношения. Отношение эквивалентности Март, Способы задания бинарных отношений Граф Def: граф – это совокупность множества V с заданным на нем отношением U V 2 : G= V – носитель графа (множество вершин), U – сигнатура графа (множество ребер или дуг). Пример Дано: А={а, b}, R 2 ={(a,a), (b,a)} A 2 Граф бинарного отношения R 2 изображается так : a b

ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Бинарные отношения. Отношение эквивалентности Март, V={a, b, c, d, e}, Т V 2 a – устройство ввода ; b – процессор ; c – устройство управления ; d – запоминающее устройство ; e – устройство вывода. Пример: информационный обмен между устройствами ЭВМ

ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Бинарные отношения. Отношение эквивалентности Март, Историческая справка Джон фон Нейман Американский математик Доктор физико-математических наук Член Национальной Академии наук США Профессор Принстонского университета в США (с 1933) Член Комиссии по атомной энергии США (с 1954) Директор Бюро по проектированию ЭВМ ( ).

ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Бинарные отношения. Отношение эквивалентности Март, Способы задания бинарных отношений Фактор-множество Def: окрестность единичного радиуса элемента a i A : O(a i )={ a j | (a i,a j ) R A 2, a j A } Def: фактор-множество A/R ( или A|R) множества À по отношению R A 2 есть совокупность окрестностей единичного радиуса A/R = { O(a i ) | a i A } Пример a b c d e {b,c,d}{c,d,e}{a,b,d,e}{b,c,а}{c} Верхняя строка – элементы множества À Нижняя – совокупность окрестностей единичного радиуса элементов a i

ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Бинарные отношения. Отношение эквивалентности Март, Рефлексивность R A 2 – рефлексивно, если a i A (a i,a i ) R A 2 матрица смежности : в графе – петли : 2. Симметричность R A 2 – симметрично, если a i, a j A : (a i,a j ) R (a j,a i ) R A 2 матрица смежности : в графе – симметрично направленные дуги : Свойства бинарных отношений. 1

ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Бинарные отношения. Отношение эквивалентности Март, Транзитивность R A 2 – транзитивно, если a i,a j,a k A : (a i,a j ) R, (a j,a k ) R (a i,a k ) R A 2 в графе – транзитивно замыкающая дуга : Дополнительные свойства : антирефлексивность нерефлексивность антисимметричность несимметричность нетранзитивность Пример Свойства бинарных отношений. 2

ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Бинарные отношения. Отношение эквивалентности Март, Бинарное отношение эквивалентности Обозначение : R ~ Граф Рефлексивность : x x Симметричность : x y y x Транзитивность : x y, y z x z Пример Бинарное отношение эквивалентности R ~ Рефлексивность Симметричность Транзитивность = + +

ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Бинарные отношения. Отношение эквивалентности Март, Разбиение множества Def: разбиение Г множества А – семейство непустых попарно непересекающихся подмножеств, объединение которых совпадает с А Свойства Г В (А) K i Ã: K i K i, K j Г: K i K j = Пример Для трехэлементного множества A={a,b,c} разбиениями являются Г 1 ={ {a, b, c} } Г 2 ={ {a}, {b}, {c} } Г 3 ={ {a}, {b,c} } Г 4 ={ {b}, {a,c} } Г 5 ={ {c}, {a,b} }

ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Бинарные отношения. Отношение эквивалентности Март, Процедура построения разбиения множества Пусть на множестве А задано отношение эквивалентности R ~ Выберем элемент a 1 A и образуем подмножество (класс) K 1 A, состоящий из элемента а 1 и всех элементов, эквивалентных ему: Выберем элемент a 2 A, а 2 а 1, и образуем подмножество (класс) K 2 A, состоящий из элемента а 2 и всех элементов, эквивалентных ему : Таким образом, получаем систему классов, объединение которых совпадает с множеством А

ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Бинарные отношения. Отношение эквивалентности Март, Классы эквивалентности Построенная система классов обладает следующими свойствами: образует разбиение любые два элемента из одного класса эквивалентны любые два элемента из разных классов не эквивалентны Def: класс эквивалентности [à] элемента à [a]={ x | x a, x A } Свойства классов эквивалентности : a [a] b [a] [b]=[a] [a] [b]=, [a] [b] [a]=[b]

ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Бинарные отношения. Отношение эквивалентности Март, Матрица бинарного отношения эквивалентности Матрицу бинарного отношения эквивалентности можно представить в блочно- диагональном виде, где каждая подматрица, состоящая из единиц, соответствует классу эквивалентности

ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Бинарные отношения. Отношение эквивалентности Март, Выводы. 1 n При исследовании возникает задача выбора существенных свойств, деталей, признаков моделируемого объекта. Отношение эквивалентности, с одной стороны, отождествляет второстепенные, несущественные признаки и свойства, и, с другой – выделяет в качестве представителей классов эквивалентности основные свойства. n Понятия "отношение эквивалентности", "фактор- множество", "классы эквивалентности" используются при построении математической модели некоторой реально функционирующей сложной системы. n Модель есть некоторое фактор-множество элементов моделируемого объекта относительно некоторого отношения эквивалентности, заданного на исходной системе.

ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Бинарные отношения. Отношение эквивалентности Март, Выводы. 2 Если моделируемый объект представлен в виде композиции элементов некоторого базисного множества, то вопрос о соотношении модели и ее прообраза разрешается на основе информации об элементах, на которых вводится отношение эквивалентности - либо это сами элементы базисного множества, либо некоторые подмножества элементов, либо подмножества множества подмножеств элементов. Множество ОтношениеМодель + =

ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , Бинарные отношения. Отношение эквивалентности Март, Тест-вопросы 1. Какое из отношений является бинарным: а) R M 3 ; б) R M 2 ;в) R=M Если матрица, описывающая бинарное отношение, содержит на главной диагонали нули и единицы, то отношение: а) рефлексивно; б) антирефлексивно; в) не рефлексивно. 3. Если все вершины графа, описывающего отношение, имеют петли, то отношение: а) рефлексивно; б) антирефлексивно; в) не рефлексивно. 4. Если в графе, описывающем отношение, имеется хотя бы одна пара вершин, соединенных одной дугой, является ли данное отношение симметричным? а) да; б) нет. 5. Классы эквивалентности: а) попарно пересекаются; б) попарно не пересекаются. 6. Верно ли, что любые два элемента из одного класса эквивалентности эквивалентны? а) да; б) нет.