close

Вход

Забыли?

вход по аккаунту

?

ДИСКРЕТНАЯ МАТЕМАТИКА

код для вставкиСкачать
ДИСКРЕТНАЯ МАТЕМАТИКА
ТЕОРИЯ МНОЖЕСТВ.
БИНАРНЫЕ ОТНОШЕНИЯ.
ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ.
ГБПОУ Колледж связи № 54 г. Москва
Преподаватель математики
Тамара Нельевна Рудзина
2015г.
Содержание:
• Определение бинарного отношения
• Способы задания бинарных отношений
• Свойства бинарных отношений
• Бинарное отношение эквивалентности
• Классы эквивалентности
• Применение в задачах компьютерной инженерии
2
Термины
Базовые понятия:
 множество
 подмножество
 упорядоченная
пара
 вектор
 декартово
произведение
 декартова степень
 отношение
Ключевые слова:
 бинарное отношение
 матрица смежности
 граф
 фактор-множество
 рефлексивность
 симметричность
 транзитвность
 отношение
эквивалентности
3
Определение бинарного отношения
Множества


Def: бинарным (двухместным)
отношением на множестве M
называется подмножество
декартова квадрата множества
М:
R2М2
n=2 – степень отношения
(бинарное)
Декартово
произведение AB
Декартов
квадрат A2
Бинарное
2
отношение R2A
4
Способы задания бинарных отношений. 1
1. Матрица смежности
Пример
Def: матрица смежности
бинарного отношения на
множестве А={а1, а2, а3, …¾, an} –
это таблица размера nn,
в которой элемент cij ,
определяется следующим образом:
Дано: А={а, b},
R2={(a,a), (b,a)}  A2
1, если a i Ra j ;
c ij  
 0 в противном
случае
Матрица смежности
бинарного отношения
R2 представляется так:
a
b
a
1
0
b
1
0
5
Способы задания бинарных отношений. 2
2. Граф
Пример
Def: граф – это совокупность
множества V с заданным на
нем отношением UV2:
G=<V, U>
V – носитель графа (множество
вершин),
U – сигнатура графа (множество
ребер или дуг).
Дано: А={а, b},
R2={(a,a), (b,a)}  A2
Граф бинарного
отношения R2
изображается так:
a
b
6
Пример: информационный обмен между
устройствами ЭВМ
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
e
d
a – устройство ввода;
b – процессор;
c – устройство управления;
d – запоминающее устройство;
e – устройство вывода.
7
Историческая справка
 Американский математик
 Доктор физико-математических
наук
 Член Национальной Академии
наук США
 Профессор Принстонского
университета в США с 1933
 Член Комиссии по атомной
энергии США с 1954
 Директор Бюро по
проектированию ЭВМ (1945-1955)
Джон фон Нейман
8
Способы задания бинарных отношений. 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 }
9
Свойства бинарных отношений. 1
2. Симметричность
1. Рефлексивность
 RA2 – рефлексивно, если  RA2 – симметрично, если
ai, aj A : (ai,aj)R 
ai A  (ai,ai)RA2
(aj,ai)RA2
 матрица смежности имеет
 матрица смежности
единичную главную
диагональ:
симметрична относительно
главной диагонали:

1
...
...
...
1
0
...
1
...
1
...
0
...
...
1
0
0
...
в графе – петли:

ai
в графе – симметрично
направленные дуги:
ai
aj
10
Свойства бинарных отношений. 2
3. Транзитивность
 RA2 – транзитивно, если
ai,aj,ak A :
(ai,aj)R, (aj,ak)R 
(ai,ak)RA2

в графе – транзитивно
замыкающая дуга:
Дополнительные свойства:
 антирефлексивность
 нерефлексивность
 антисимметричность
 несимметричность
 нетранзитивность
Пример
a
aj
ai
b
ak
d
e
11
Бинарное отношение эквивалентности
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
12
Разбиение множества
 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
13
Процедура построения разбиения множества
 Пусть на множестве А задано отношение эквивалентности R~
 Выберем элемент a1A и образуем подмножество (класс) K1A,
состоящий из элемента а1 и всех элементов, эквивалентных ему:
 a 1  A  K 1  A : K 1  a 1   x  A : x ~ a 1 
 Выберем элемент a2A, а2а1, и образуем подмножество (класс)
K2A, состоящий из элемента а2 и всех элементов, эквивалентных
ему:
 a 2  A , a 2  K 1  A  K 2  A : K 2  a 2   x  A , x  K 1 : x ~ a 2 
 Таким образом, получаем систему классов, объединение
которых совпадает с множеством А
14
Классы эквивалентности
Построенная система
классов обладает
следующими свойствами:
 образует разбиение
 любые два элемента из
одного класса
эквивалентны
 любые два элемента из
разных классов не
эквивалентны
Def: класс эквивалентности
[à] элемента à
[a]={ x | xa, xA }
 Свойства классов
эквивалентности:
 a[a]
 b[a][b]=[a]
 [a][b]=,
[a][b] [a]=[b]

 [a ]  A
aA
15
Матрица бинарного отношения
эквивалентности
Матрицу бинарного
отношения
эквивалентности
можно
представить
в блочно-диагональном
виде, где каждая
подматрица,
состоящая из единиц,
соответствует классу
эквивалентности
a
b
c
...
...
...
x
y
a
1
1
1
b
1
1
1
c
1
1
1
.
1
1
.
1
1
.
1
1
1
x
1
1
1
y
1
1
1
z
z
1
16
Выводы. 1



При исследовании возникает задача выбора
существенных свойств, деталей, признаков
моделируемого объекта. Отношение
эквивалентности, с одной стороны, отождествляет
второстепенные, несущественные признаки и
свойства, и, с другой – выделяет в качестве
представителей классов эквивалентности основные
свойства.
Понятия "отношение эквивалентности", "фактормножество", "классы эквивалентности" используются
при построении математической модели некоторой
реально функционирующей сложной системы.
Модель есть некоторое фактор-множество элементов
моделируемого объекта относительно некоторого
отношения эквивалентности, заданного на исходной
системе.
17
Выводы. 2
Если моделируемый объект представлен в виде
композиции элементов некоторого базисного
множества, то вопрос о соотношении модели и ее
прообраза разрешается на основе информации об
элементах, на которых вводится отношение
эквивалентности - либо это сами элементы
базисного множества, либо некоторые
подмножества элементов, либо подмножества
множества подмножеств элементов.

Множество
+
Отношение
=
Модель
18
Литература
• Горбатов В.А. Основы дискретной математики. М.: Высш. шк.,
1986. 10-14 с.
• Лавров И.А., Максимова Л.Л. Задачи по теории множеств,
математической логике и теории алгоритмов. М.: Наука. Главная
редакция физико-математической литературы, 1984. 224 с.
• Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная
математика для инженера. М.: Энергия, 1980. 344 с.
• Богомолов А.М., Сперанский Д.В. Аналитические методы в
задачах контроля и анализа дискретных устройств. Саратов: Изд-во
Саратовкого ун-та, 1986. 240с.
• Новиков Ф.А. Дискретная математика для программистов. С.-П.,
2001. С. 4-24.
19
Автор
profobrazovanie
Документ
Категория
Без категории
Просмотров
56
Размер файла
269 Кб
Теги
дискретное, математика
1/--страниц
Пожаловаться на содержимое документа