Презентация на тему: ТЕОРИЯ МНОЖЕСТВ БИНАРНЫЕ ОТНОШЕНИЯ. ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ ЛЕКЦИЯ 4

ТЕОРИЯ МНОЖЕСТВ БИНАРНЫЕ ОТНОШЕНИЯ. ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ ЛЕКЦИЯ 4
Цель лекции – изучить свойства бинарных отношений, способы их задания для применения в задачах компьютерной инженерии
ТЕОРИЯ МНОЖЕСТВ БИНАРНЫЕ ОТНОШЕНИЯ. ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ ЛЕКЦИЯ 4
ТЕОРИЯ МНОЖЕСТВ БИНАРНЫЕ ОТНОШЕНИЯ. ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ ЛЕКЦИЯ 4
ТЕОРИЯ МНОЖЕСТВ БИНАРНЫЕ ОТНОШЕНИЯ. ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ ЛЕКЦИЯ 4
ТЕОРИЯ МНОЖЕСТВ БИНАРНЫЕ ОТНОШЕНИЯ. ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ ЛЕКЦИЯ 4
ТЕОРИЯ МНОЖЕСТВ БИНАРНЫЕ ОТНОШЕНИЯ. ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ ЛЕКЦИЯ 4
ТЕОРИЯ МНОЖЕСТВ БИНАРНЫЕ ОТНОШЕНИЯ. ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ ЛЕКЦИЯ 4
ТЕОРИЯ МНОЖЕСТВ БИНАРНЫЕ ОТНОШЕНИЯ. ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ ЛЕКЦИЯ 4
ТЕОРИЯ МНОЖЕСТВ БИНАРНЫЕ ОТНОШЕНИЯ. ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ ЛЕКЦИЯ 4
ТЕОРИЯ МНОЖЕСТВ БИНАРНЫЕ ОТНОШЕНИЯ. ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ ЛЕКЦИЯ 4
ТЕОРИЯ МНОЖЕСТВ БИНАРНЫЕ ОТНОШЕНИЯ. ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ ЛЕКЦИЯ 4
ТЕОРИЯ МНОЖЕСТВ БИНАРНЫЕ ОТНОШЕНИЯ. ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ ЛЕКЦИЯ 4
ТЕОРИЯ МНОЖЕСТВ БИНАРНЫЕ ОТНОШЕНИЯ. ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ ЛЕКЦИЯ 4
ТЕОРИЯ МНОЖЕСТВ БИНАРНЫЕ ОТНОШЕНИЯ. ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ ЛЕКЦИЯ 4
ТЕОРИЯ МНОЖЕСТВ БИНАРНЫЕ ОТНОШЕНИЯ. ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ ЛЕКЦИЯ 4
ТЕОРИЯ МНОЖЕСТВ БИНАРНЫЕ ОТНОШЕНИЯ. ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ ЛЕКЦИЯ 4
Выводы. 1
Выводы. 2
ТЕОРИЯ МНОЖЕСТВ БИНАРНЫЕ ОТНОШЕНИЯ. ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ ЛЕКЦИЯ 4
1/20
Средняя оценка: 4.6/5 (всего оценок: 63)
Код скопирован в буфер обмена
Скачать (203 Кб)
1

Первый слайд презентации: ТЕОРИЯ МНОЖЕСТВ БИНАРНЫЕ ОТНОШЕНИЯ. ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ ЛЕКЦИЯ 4

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

Изображение слайда
2

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

2 Цель лекции – изучить свойства бинарных отношений, способы их задания для применения в задачах компьютерной инженерии Содержание: Определение бинарного отношения Способы задания бинарных отношений Свойства бинарных отношений Бинарное отношение эквивалентности Классы эквивалентности Применение в задачах компьютерной инженерии Тема: Бинарные отношения. Отношение эквивалентности

Изображение слайда
3

Слайд 3

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

Изображение слайда
4

Слайд 4

4 Термины Базовые понятия: множество подмножество упорядоченная пара вектор декартово произведение декартова степень отношение Ключевые слова: бинарное отношение матрица смежности граф фактор-множество рефлексивность симметричность транзитвность отношение эквивалентности

Изображение слайда
5

Слайд 5

5 Def : бинарным (двухместным) отношением на множестве M называется подмножество декартова квадрата множества М : R 2  М 2 n =2 – степень отношения (бинарное) Определение бинарного отношения Множества Декартово произведение A  B Декартов квадрат A 2 Бинарное отношение R 2  A 2

Изображение слайда
6

Слайд 6

6 Способы задания бинарных отношений. 1 1. Матрица смежности Def: матрица смежности бинарного отношения на множестве А= { а 1, а 2, а 3, … ¾, a n } – это таблица размера n n, в которой элемент c ij, определяется следующим образом : Пример Дано: А= { а, b}, R 2 ={(a,a), (b,a)}  A 2 Матрица смежности бинарного отношения R 2 представляется так:

Изображение слайда
7

Слайд 7

7 Способы задания бинарных отношений. 2 2. Граф Def: граф – это совокупность множества V с заданным на нем отношением U V 2 : G=<V, U> V – носитель графа (множество вершин), U – сигнатура графа (множество ребер или дуг). Пример Дано: А= { а, b}, R 2 ={(a,a), (b,a)}  A 2 Граф бинарного отношения R 2 изображается так : a b

Изображение слайда
8

Слайд 8

8 V={ a, b, c, d, e }, Т  V 2 a – устройство ввода ; b – процессор ; c – устройство управления ; d – запоминающее устройство ; e – устройство вывода. Пример: информационный обмен между устройствами ЭВМ

Изображение слайда
9

Слайд 9

9 Историческая справка Джон фон Нейман Американский математик Доктор физико-математических наук Член Национальной Академии наук США Профессор Принстонского университета в США с 1933 Член Комиссии по атомной энергии США с 1954 Директор Бюро по проектированию ЭВМ (1945-1955)

Изображение слайда
10

Слайд 10

10 Способы задания бинарных отношений. 3 3. Фактор-множество 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

Изображение слайда
11

Слайд 11

11 Рефлексивность 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

Изображение слайда
12

Слайд 12

12 3. Транзитивность 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

Изображение слайда
13

Слайд 13

13 Бинарное отношение эквивалентности Обозначение : R ~ Граф Рефлексивность : x x Симметричность : x yyx Транзитивность : x y, yz  x z Пример Бинарное отношение эквивалентности R ~ Рефлексивность Симметричность Транзитивность = + +

Изображение слайда
14

Слайд 14

14 Разбиение множества 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} }

Изображение слайда
15

Слайд 15

15 Процедура построения разбиения множества Пусть на множестве А задано отношение эквивалентности R ~ Выберем элемент a 1 A и образуем подмножество (класс) K 1 A, состоящий из элемента а 1 и всех элементов, эквивалентных ему: Выберем элемент a 2 A, а 2 а 1, и образуем подмножество (класс) K 2 A, состоящий из элемента а 2 и всех элементов, эквивалентных ему : Таким образом, получаем систему классов, объединение которых совпадает с множеством А

Изображение слайда
16

Слайд 16

16 Классы эквивалентности Построенная система классов обладает следующими свойствами: образует разбиение любые два элемента из одного класса эквивалентны любые два элемента из разных классов не эквивалентны Def: класс эквивалентности [à] элемента à [a]={ x | x a, xA } Свойства классов эквивалентности : a [a] b [a][b]=[a] [a] [b]=, [a] [b] [a] =[b]

Изображение слайда
17

Слайд 17

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

Изображение слайда
18

Слайд 18: Выводы. 1

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

Изображение слайда
19

Слайд 19: Выводы. 2

19 Выводы. 2 Если моделируемый объект представлен в виде композиции элементов некоторого базисного множества, то вопрос о соотношении модели и ее прообраза разрешается на основе информации об элементах, на которых вводится отношение эквивалентности - либо это сами элементы базисного множества, либо некоторые подмножества элементов, либо подмножества множества подмножеств элементов. Множество Отношение Модель + =

Изображение слайда
20

Последний слайд презентации: ТЕОРИЯ МНОЖЕСТВ БИНАРНЫЕ ОТНОШЕНИЯ. ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ ЛЕКЦИЯ 4

20 Тест-вопросы 1. Какое из отношений является бинарным: а) R M 3 ; б) R M 2 ; в) R =M 2. 2. Если матрица, описывающая бинарное отношение, содержит на главной диагонали нули и единицы, то отношение: а) рефлексивно; б) антирефлексивно; в) не рефлексивно. 3. Если все вершины графа, описывающего отношение, имеют петли, то отношение: а) рефлексивно; б) антирефлексивно; в) не рефлексивно. 4. Если в графе, описывающем отношение, имеется хотя бы одна пара вершин, соединенных одной дугой, является ли данное отношение симметричным? а) да; б) нет. 5. Классы эквивалентности: а) попарно пересекаются; б) попарно не пересекаются. 6. Верно ли, что любые два элемента из одного класса эквивалентности эквивалентны? а) да; б) нет.

Изображение слайда