ТЕОРИЯ МНОЖЕСТВ БИНАРНЫЕ ОТНОШЕНИЯ. ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ ЛЕКЦИЯ 4

управления, кафедра АПВТ, ХНУРЭ
ДИСКРЕТНАЯ МАТЕМАТИКА

для применения в задачах компьютерной инженерии
Содержание:
Определение бинарного отношения

Способы задания бинарных отношений
Свойства бинарных отношений
Бинарное отношение эквивалентности
Классы эквивалентности
Применение в задачах компьютерной инженерии

Тема: Бинарные отношения. Отношение эквивалентности

10-14 с.
Лавров И.А., Максимова Л.Л. Задачи по теории множеств,

математической логике и теории алгоритмов. М.: Наука. Главная редакция физико-математической литературы, 1984. 224 с.
Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергия, 1980. 344 с.
Богомолов А.М., Сперанский Д.В. Аналитические методы в задачах контроля и анализа дискретных устройств. Саратов: Изд-во Саратовкого ун-та, 1986. 240с.
Новиков Ф.А. Дискретная математика для программистов. С.-П., 2001. С. 4-24.
Хаханов В.І., Хаханова І.В., Кулак Е.М., Чумаченко С.В. Методичні вказівки до практичних занять з курсу “Дискретна математика”. Харків, ХНУРЕ. 2001. 12-16 с.

декартова степень
отношение
Ключевые слова:
бинарное отношение
матрица смежности
граф
фактор-множество

рефлексивность
симметричность
транзитвность
отношение эквивалентности

квадрата множества М:
R2М2
n=2 – степень отношения
(бинарное)
Определение бинарного отношения

на
множестве А={а1, а2, а3, …¾, an} –
это таблица размера nn,

в которой элемент cij ,
определяется следующим образом:

Пример

Дано: А={а, b},
R2={(a,a), (b,a)}  A2

Матрица смежности
бинарного отношения
R2 представляется так:

множества V с заданным на нем отношением UV2:
G=
V

– носитель графа (множество вершин),
U – сигнатура графа (множество ребер или дуг).

Пример

Дано: А={а, b},
R2={(a,a), (b,a)}  A2

Граф бинарного
отношения R2
изображается так:

– процессор;
c – устройство управления;
d – запоминающее устройство;

e – устройство вывода.

Пример: информационный обмен между устройствами ЭВМ

Член Национальной Академии наук США
Профессор Принстонского университета

в США с 1933
Член Комиссии по атомной энергии США с 1954
Директор Бюро по проектированию ЭВМ (1945-1955)

aiA :

O(ai)={ aj | (ai,aj)RA2, ajA }

Def: фактор-множество A/R
(или

A|R) множества À по
отношению RA2 есть
совокупность окрестностей
единичного радиуса

A/R = { O(ai) | aiA }

Пример

a b c d e
{b,c,d}{c,d,e}{a,b,d,e}{b,c,а}{c}

Верхняя строка – элементы множества À
Нижняя – совокупность окрестностей единичного радиуса элементов ai

единичную главную диагональ:




в графе – петли:
2. Симметричность

RA2 – симметрично, если
ai, aj A : (ai,aj)R  (aj,ai)RA2
матрица смежности симметрична относительно главной диагонали:




в графе – симметрично направленные дуги:

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

графе – транзитивно замыкающая дуга:
Дополнительные свойства:
антирефлексивность
нерефлексивность
антисимметричность
несимметричность
нетранзитивность
Пример

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

Транзитивность: xy, yz  xz
Пример

попарно непересекающихся подмножеств, объединение которых совпадает с А
Свойства ГВ(А)

KiÃ: Ki 
Ki, Kj Г: KiKj = 

Пример
Для трехэлементного множества
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~

Выберем элемент a1A и образуем подмножество (класс) K1A,

состоящий из элемента а1 и всех элементов, эквивалентных ему:


Выберем элемент a2A, а2а1, и образуем подмножество (класс) K2A, состоящий из элемента а2 и всех элементов, эквивалентных ему:


Таким образом, получаем систему классов, объединение которых совпадает с множеством А

два элемента из одного класса эквивалентны
любые два элемента из

разных классов не эквивалентны

Def: класс эквивалентности [à] элемента à
[a]={ x | xa, xA }

Свойства классов эквивалентности:
a[a]
b[a][b]=[a]
[a][b]=,
[a][b] [a]=[b]

блочно-диагональном
виде, где каждая
подматрица,
состоящая из единиц,
соответствует классу

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

моделируемого объекта. Отношение эквивалентности, с одной стороны, отождествляет второстепенные, несущественные

признаки и свойства, и, с другой – выделяет в качестве представителей классов эквивалентности основные свойства.
Понятия "отношение эквивалентности", "фактор-множество", "классы эквивалентности" используются при построении математической модели некоторой реально функционирующей сложной системы.
Модель есть некоторое фактор-множество элементов моделируемого объекта относительно некоторого отношения эквивалентности, заданного на исходной системе.

некоторого базисного множества, то вопрос о соотношении модели и ее

прообраза разрешается на основе информации об элементах, на которых вводится отношение эквивалентности - либо это сами элементы базисного множества, либо некоторые подмножества элементов, либо подмножества множества подмножеств элементов.

R=M2.
2. Если матрица, описывающая бинарное
отношение, содержит на главной
диагонали

нули и единицы, то
отношение:
а) рефлексивно; б) антирефлексивно;
в) не рефлексивно.
3. Если все вершины графа,
описывающего отношение, имеют петли,
то отношение:
а) рефлексивно; б) антирефлексивно;
в) не рефлексивно.

4. Если в графе, описывающем
отношение, имеется хотя бы одна
пара вершин, соединенных одной
дугой, является ли данное
отношение симметричным?
а) да; б) нет.
5. Классы эквивалентности:
а) попарно пересекаются;
б) попарно не пересекаются.
6. Верно ли, что любые два
элемента из одного класса
эквивалентности эквивалентны?
а) да; б) нет.