Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

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

Содержание

Цель лекции – изучить свойства бинарных отношений, способы их задания для применения в задачах компьютерной инженерииСодержание: Определение бинарного отношения Способы задания бинарных отношений Свойства бинарных отношений Бинарное отношение эквивалентности Классы эквивалентности Применение в задачах компьютерной инженерииТема:
ТЕОРИЯ МНОЖЕСТВ БИНАРНЫЕ ОТНОШЕНИЯ. ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ   ЛЕКЦИЯ 4Факультет компьютерной инженерии Цель лекции – изучить свойства бинарных отношений, способы их задания для применения Литература Горбатов В.А. Основы дискретной математики. М.: Высш. шк., 1986. 10-14 с. ТерминыБазовые понятия: множество подмножество упорядоченная пара вектор декартово произведение декартова степень отношениеКлючевые Def: бинарным (двухместным) отношением на множестве M называется подмножество декартова квадрата множества Способы задания бинарных отношений. 11. Матрица смежностиDef: матрица смежностибинарного отношения намножестве А={а1, Способы задания бинарных отношений. 22. ГрафDef: граф – это совокупность множества V V={a, b, c, d, e}, Т⊂V2a – устройство ввода; b – процессор; Историческая справкаДжон фон Нейман Американский математик Доктор физико-математических наук Член Национальной Академии Способы задания бинарных отношений. 33. Фактор-множествоDef: окрестность единичного радиуса элемента ai∈A :O(ai)={ РефлексивностьR⊆A2 – рефлексивно, если∀ai ∈A ⇒ (ai,ai)∈R⊆A2матрица смежности имеет единичную главную 3. ТранзитивностьR⊆A2 – транзитивно, если∀ai,aj,ak ∈A : (ai,aj)∈R, (aj,ak)∈R ⇒(ai,ak)∈R⊆A2в графе – Бинарное отношение эквивалентности Обозначение: R~ Граф Рефлексивность: 	x~x Симметричность: x~y⇔y~x Транзитивность: x~y, y~z ⇒ x~z Пример Разбиение множества Def: разбиение Г множества А – семейство непустых попарно непересекающихся Процедура построения разбиения множества Пусть на множестве А задано отношение эквивалентности R~ Классы эквивалентностиПостроенная система классов обладает следующими свойствами: образует разбиение любые два элемента Матрица бинарного отношения эквивалентностиМатрицу бинарного отношения эквивалентности можно представить в блочно-диагональном виде, Выводы. 1При исследовании возникает задача выбора существенных свойств, деталей, признаков моделируемого объекта. Выводы. 2 Если моделируемый объект представлен в виде композиции элементов некоторого базисного Тест-вопросы1. Какое из отношений является бинарным:а) R⊂M3;  б) R⊂M2;	в) R=M2.2. Если
Слайды презентации

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

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

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

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

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


Слайд 3 Литература
Горбатов В.А. Основы дискретной математики. М.: Высш.

Литература Горбатов В.А. Основы дискретной математики. М.: Высш. шк., 1986. 10-14

шк., 1986. 10-14 с.
Лавров И.А., Максимова Л.Л. Задачи

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

Слайд 4 Термины
Базовые понятия:
множество
подмножество
упорядоченная пара
вектор

ТерминыБазовые понятия: множество подмножество упорядоченная пара вектор декартово произведение декартова степень

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

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

Слайд 5 Def: бинарным (двухместным) отношением на множестве M называется

Def: бинарным (двухместным) отношением на множестве M называется подмножество декартова квадрата

подмножество декартова квадрата множества М:
R2⊆М2
n=2 – степень отношения


(бинарное)

Определение бинарного отношения





Слайд 6 Способы задания бинарных отношений. 1
1. Матрица смежности

Def: матрица

Способы задания бинарных отношений. 11. Матрица смежностиDef: матрица смежностибинарного отношения намножестве

смежности
бинарного отношения на
множестве А={а1, а2, а3, …¾, an} –
это

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

Пример

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

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


Слайд 7 Способы задания бинарных отношений. 2
2. Граф

Def: граф –

Способы задания бинарных отношений. 22. ГрафDef: граф – это совокупность множества

это совокупность множества V с заданным на нем отношением

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

Пример

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

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


Слайд 8 V={a, b, c, d, e}, Т⊂V2






a – устройство

V={a, b, c, d, e}, Т⊂V2a – устройство ввода; b –

ввода;
b – процессор;
c – устройство управления;
d

– запоминающее устройство;
e – устройство вывода.

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



Слайд 9
Историческая справка

Джон фон Нейман
Американский математик
Доктор

Историческая справкаДжон фон Нейман Американский математик Доктор физико-математических наук Член Национальной

физико-математических наук
Член Национальной Академии наук США

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

Слайд 10 Способы задания бинарных отношений. 3
3. Фактор-множество
Def: окрестность единичного

Способы задания бинарных отношений. 33. Фактор-множествоDef: окрестность единичного радиуса элемента ai∈A


радиуса элемента 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


Слайд 11 Рефлексивность
R⊆A2 – рефлексивно, если
∀ai ∈A ⇒ (ai,ai)∈R⊆A2
матрица

РефлексивностьR⊆A2 – рефлексивно, если∀ai ∈A ⇒ (ai,ai)∈R⊆A2матрица смежности имеет единичную

смежности имеет единичную главную диагональ:




в графе – петли:


2. Симметричность
R⊆A2 – симметрично, если
∀ai, aj ∈A : (ai,aj)∈R ⇒ (aj,ai)∈R⊆A2
матрица смежности симметрична относительно главной диагонали:




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

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


Слайд 12 3. Транзитивность
R⊆A2 – транзитивно, если
∀ai,aj,ak ∈A :
(ai,aj)∈R,

3. ТранзитивностьR⊆A2 – транзитивно, если∀ai,aj,ak ∈A : (ai,aj)∈R, (aj,ak)∈R ⇒(ai,ak)∈R⊆A2в графе

(aj,ak)∈R ⇒
(ai,ak)∈R⊆A2

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

свойства:
антирефлексивность
нерефлексивность
антисимметричность
несимметричность
нетранзитивность
Пример

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


Слайд 13 Бинарное отношение эквивалентности
Обозначение: R~

Граф

Рефлексивность: x~x

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

Симметричность: x~y⇔y~x
Транзитивность: x~y, y~z ⇒ x~z
Пример






Слайд 14 Разбиение множества
Def: разбиение Г множества А –

Разбиение множества Def: разбиение Г множества А – семейство непустых попарно

семейство непустых попарно непересекающихся подмножеств, объединение которых совпадает с

А
Свойства Г⊂В(А)
∀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} }


Слайд 15 Процедура построения разбиения множества
Пусть на множестве А

Процедура построения разбиения множества Пусть на множестве А задано отношение эквивалентности

задано отношение эквивалентности R~

Выберем элемент a1∈A и образуем

подмножество (класс) K1⊂A, состоящий из элемента а1 и всех элементов, эквивалентных ему:


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


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

Слайд 16 Классы эквивалентности
Построенная система классов обладает следующими свойствами:
образует

Классы эквивалентностиПостроенная система классов обладает следующими свойствами: образует разбиение любые два

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

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

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

Свойства классов эквивалентности:
a∈[a]
b∈[a]⇒[b]=[a]
[a]∩[b]=∅,
[a]∩[b]≠∅⇒ [a]=[b]




Слайд 17 Матрица бинарного отношения эквивалентности
Матрицу бинарного
отношения
эквивалентности
можно

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


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

единиц,
соответствует классу
эквивалентности

Слайд 18 Выводы. 1
При исследовании возникает задача выбора существенных свойств,

Выводы. 1При исследовании возникает задача выбора существенных свойств, деталей, признаков моделируемого

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

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

Слайд 19 Выводы. 2
Если моделируемый объект представлен в виде

Выводы. 2 Если моделируемый объект представлен в виде композиции элементов некоторого

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

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

  • Имя файла: teoriya-mnozhestv-binarnye-otnosheniya-otnoshenie-ekvivalentnosti-lektsiya-4.pptx
  • Количество просмотров: 86
  • Количество скачиваний: 0