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

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

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

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

Бинарные отношения. Отношение эквивалентности
Сентябрь, 2006
Тема: Бинарные отношения.
Отношение эквивалентности
Цель лекции – изучить свойства
бинарных отношений, способы их задания
для применения в задачах компьютерной
инженерии
Содержание:
• Определение бинарного отношения
• Способы задания бинарных отношений
• Свойства бинарных отношений
• Бинарное отношение эквивалентности
• Классы эквивалентности
• Применение в задачах компьютерной инженерии
ХНУРЭ, факультет КИУ, кафедра АПВТ,
тел. 7021 326, e-mail: [email protected]
2

3.

Бинарные отношения. Отношение эквивалентности
Сентябрь, 2006
Литература
• Горбатов В.А. Основы дискретной математики. М.: Высш. шк.,
1986. 10-14 с.
• Лавров И.А., Максимова Л.Л. Задачи по теории множеств,
математической логике и теории алгоритмов. М.: Наука. Главная
редакция физико-математической литературы, 1984. 224 с.
• Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная
математика для инженера. М.: Энергия, 1980. 344 с.
• Богомолов А.М., Сперанский Д.В. Аналитические методы в
задачах контроля и анализа дискретных устройств. Саратов: Изд-во
Саратовкого ун-та, 1986. 240с.
• Новиков Ф.А. Дискретная математика для программистов. С.-П.,
2001. С. 4-24.
• Хаханов В.І., Хаханова І.В., Кулак Е.М., Чумаченко С.В.
Методичні вказівки до практичних занять з курсу “Дискретна
математика”. Харків, ХНУРЕ. 2001. 12-16 с.
ХНУРЭ, факультет КИУ, кафедра АПВТ,
тел. 7021 326, e-mail: [email protected]
3

4.

Бинарные отношения. Отношение эквивалентности
Сентябрь, 2006
Термины
Базовые понятия:
множество
подмножество
упорядоченная
пара
вектор
декартово
произведение
декартова степень
отношение
ХНУРЭ, факультет КИУ, кафедра АПВТ,
тел. 7021 326, e-mail: [email protected]
Ключевые слова:
бинарное отношение
матрица смежности
граф
фактор-множество
рефлексивность
симметричность
транзитвность
отношение
эквивалентности
4

5.

Бинарные отношения. Отношение эквивалентности
Сентябрь, 2006
Определение бинарного отношения
Множества
Def: бинарным (двухместным)
отношением на множестве M
называется подмножество
декартова квадрата множества
М:
R2 М2
n=2 – степень отношения
(бинарное)
ХНУРЭ, факультет КИУ, кафедра АПВТ,
тел. 7021 326, e-mail: [email protected]
Декартово
произведение A B
Декартов
квадрат A2
Бинарное
2
отношение R2 A
5

6.

Бинарные отношения. Отношение эквивалентности
Сентябрь, 2006
Способы задания бинарных отношений. 1
1. Матрица смежности
Пример
Def: матрица смежности
бинарного отношения на
множестве А={а1, а2, а3, …¾, an} –
это таблица размера n n,
в которой элемент cij ,
определяется следующим образом:
Дано: А={а, b},
R2={(a,a), (b,a)} A2
1, если a i Ra j ;
cij
0 в противном случае
ХНУРЭ, факультет КИУ, кафедра АПВТ,
тел. 7021 326, e-mail: [email protected]
Матрица смежности
бинарного отношения
R2 представляется так:
a b
a 1 0
b 1 0
6

7.

Бинарные отношения. Отношение эквивалентности
Сентябрь, 2006
Способы задания бинарных отношений. 2
2. Граф
Пример
Def: граф – это совокупность
множества V с заданным на
2
нем отношением U V :
G=<V, U>
V – носитель графа (множество
вершин),
U – сигнатура графа (множество
ребер или дуг).
Дано: А={а, b},
R2={(a,a), (b,a)} A2
Граф бинарного
отношения R2
изображается так:
a
ХНУРЭ, факультет КИУ, кафедра АПВТ,
тел. 7021 326, e-mail: [email protected]
b
7

8.

Бинарные отношения. Отношение эквивалентности
Сентябрь, 2006
Пример: информационный обмен между
устройствами ЭВМ
V={a, b, c, d, e}, Т V2
T (a , b), (a , c), (a , d), (b, c), (b, d), (b, e), (c, a ),
a
(c, b), (c, d), (c, e), (d, b), (d, c), (e, c), (d, e)}
b
c
d
e
ХНУРЭ, факультет КИУ, кафедра АПВТ,
тел. 7021 326, e-mail: [email protected]
a – устройство ввода;
b – процессор;
c – устройство управления;
d – запоминающее устройство;
e – устройство вывода.
8

9.

Бинарные отношения. Отношение эквивалентности
Сентябрь, 2006
Историческая справка
Американский математик
Доктор физико-математических
наук
Член Национальной Академии
наук США
Профессор Принстонского
университета в США с 1933
Член Комиссии по атомной
энергии США с 1954
Директор Бюро по
проектированию ЭВМ (1945-1955)
ХНУРЭ, факультет КИУ, кафедра АПВТ,
тел. 7021 326, e-mail: [email protected]
Джон фон Нейман
9

10.

Бинарные отношения. Отношение эквивалентности
Сентябрь, 2006
Способы задания бинарных отношений. 3
Пример
3. Фактор-множество
Def: окрестность единичного
a
b
c
d
e
радиуса элемента ai A :
{b,c,d}{c,d,e}{a,b,d,e}{b,c,а}{c}
O(ai)={ aj | (ai,aj) R A2, aj A }
Верхняя строка – элементы
множества À
Def: фактор-множество A/R
Нижняя – совокупность
(или A|R) множества À по
окрестностей единичного
отношению R A2 есть
радиуса элементов ai
совокупность окрестностей
единичного радиуса
A/R = { O(ai) | ai A }
ХНУРЭ, факультет КИУ, кафедра АПВТ,
тел. 7021 326, e-mail: [email protected]
10

11.

Бинарные отношения. Отношение эквивалентности
Сентябрь, 2006
Свойства бинарных отношений. 1
2. Симметричность
1. Рефлексивность
2
R A2 – рефлексивно, если R A – симметрично, если
ai, aj A : (ai,aj) R
ai A (ai,ai) R A2
(aj,ai) R A2
матрица смежности имеет
матрица смежности
единичную главную
симметрична относительно
диагональ:
главной диагонали:
1 ... ...
... 1 ...
... 1
... ... 1
0
0
1 ... 0
в графе – петли:
ai
ХНУРЭ, факультет КИУ, кафедра АПВТ,
тел. 7021 326, e-mail: [email protected]
0 ...
в графе – симметрично
направленные дуги:
ai
aj
11

12.

Бинарные отношения. Отношение эквивалентности
Сентябрь, 2006
Свойства бинарных отношений. 2
3. Транзитивность
R A2 – транзитивно, если
ai,aj,ak A :
(ai,aj) R, (aj,ak) R
(ai,ak) R A2
в графе – транзитивно
замыкающая дуга:
aj
ai
Дополнительные свойства:
антирефлексивность
нерефлексивность
антисимметричность
несимметричность
нетранзитивность
Пример
a
b
ak
ХНУРЭ, факультет КИУ, кафедра АПВТ,
тел. 7021 326, e-mail: [email protected]
d
e
12

13.

Бинарные отношения. Отношение эквивалентности
Сентябрь, 2006
Бинарное отношение эквивалентности
b
Граф
a
c
Рефлексивность: x x
Симметричность: x y y x
Транзитивность: x y, y z x z
Пример
A
D
G
01
H
F
B
1
&
3
10
I
E
11
&
2
4
Бинарное
отношение
эквивалентности
R~
=
Обозначение: R~
Рефлексивность
+
Симметричность
+
Транзитивность
C
ХНУРЭ, факультет КИУ, кафедра АПВТ,
тел. 7021 326, e-mail: [email protected]
13

14.

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

15.

Бинарные отношения. Отношение эквивалентности
Сентябрь, 2006
Процедура построения разбиения множества
Пусть на множестве А задано отношение эквивалентности R~
Выберем элемент a1 A и образуем подмножество (класс) K1 A,
состоящий из элемента а1 и всех элементов, эквивалентных ему:
a1 A K1 A : K1 a1 x A : x ~ a1
Выберем элемент a2 A, а2 а1, и образуем подмножество (класс)
K2 A, состоящий из элемента а2 и всех элементов, эквивалентных
ему:
a 2 A , a 2 K1 A K 2 A : K 2 a 2 x A, x K1 : x ~ a 2
Таким образом, получаем систему классов, объединение
которых совпадает с множеством А
ХНУРЭ, факультет КИУ, кафедра АПВТ,
тел. 7021 326, e-mail: [email protected]
15

16.

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

17.

Бинарные отношения. Отношение эквивалентности
Сентябрь, 2006
Матрица бинарного отношения
эквивалентности
Матрицу бинарного
отношения
эквивалентности
можно
представить
в блочно-диагональном
виде, где каждая
подматрица,
состоящая из единиц,
соответствует классу
эквивалентности
ХНУРЭ, факультет КИУ, кафедра АПВТ,
тел. 7021 326, e-mail: [email protected]
a
a 1
b 1
c 1
.
.
.
x
y
z
b
1
1
1
c ... ... ... x
1
1
1
1
1
y z
1
1
1
1
1
1 1
1 1
1 1
1
17

18. Выводы. 1

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

19. Выводы. 2

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

20.

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