Разделы презентаций


ТЕОРИЯ МНОЖЕСТВ УПОРЯДОЧЕННЫЕ МНОЖЕСТВА. ОТНОШЕНИЕ ПОРЯДКА лекция 5

Содержание

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

Слайды и текст этой презентации

Слайд 1ТЕОРИЯ МНОЖЕСТВ УПОРЯДОЧЕННЫЕ МНОЖЕСТВА. ОТНОШЕНИЕ ПОРЯДКА лекция 5
Факультет компьютерной инженерии и

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

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

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

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

порядка
Упорядоченные множества
Линейный и частичный порядок
Диаграммы Хассе
Старший элемент, мажоранта, миноранта
Обратное отношение. Принцип двойственности

Тема: Упорядоченные множества. Отношение порядка

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

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

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

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

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

транзитивность
Ключевые слова:
бинарное отношение порядка,
рефлексивность,
антисимметричность,
транзитивность,
старший элемент,

наибольший (наименьший) элемент,
мажоранта (миноранта),
верхняя (нижняя) грань,
супремум (инфимум)
ТерминыБазовые понятия: множество, подмножество, бинарное отношение, рефлексивность, симметричность, транзитивностьКлючевые слова: бинарное отношение порядка, рефлексивность, антисимметричность, транзитивность, старший

Слайд 5Def: бинарным отношением порядка (упорядоченности) называется рефлексивное, антисимметричное и транзитивное

отношение
Обозначение: RМ2 :
1. xM: xx;
2. x,yM: xy, yx  x=y;
3.

x,y,zM: xy, yz  xz
Def: упорядоченным называется множество с заданным отношением порядка (М, R).

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

Def: бинарным отношением порядка (упорядоченности) называется рефлексивное, антисимметричное и транзитивное отношениеОбозначение: RМ2 :1. xM: 		xx;2. x,yM: 	xy,

Слайд 6Примеры
Отношение родства
Отношение знакомства (знать человека)
1
2
3
Алла
Пугачева
Филя
Киркоров
Студент ХНУРЭ

ПримерыОтношение родстваОтношение знакомства (знать человека)123Алла ПугачеваФиля КиркоровСтудент ХНУРЭ

Слайд 7Линейный и частичный порядок
Def: линейно упорядоченное множество

 x,yM xy или

yx

частично упорядоченное множество (имеются несравнимые элементы)
x,yM  (x  y)

или (x  y )

Строгий порядок = =антирефлексивность+
+антисимметричность+
+транзитивность

Примеры
1. < R, >


2.


Линейный и частичный порядокDef: линейно упорядоченное  множество x,yM	xy или yx	частично упорядоченное множество (имеются несравнимые элементы)x,yM 

Слайд 8Пример
Жить этажами выше
Антирефлексивность:
11
1
Антисимметричность:
12
Транзитивность:
12, 23  13

ПримерЖить этажами вышеАнтирефлексивность:111Антисимметричность:12Транзитивность:12, 23  13

Слайд 9Диаграммы Хассе
Пример
Коды можно рассматривать как геометрические пространственные фигуры


Н

Диаграммы Хассе

известны с XIX в., использовались в генеалогии при задании родства


Диаграммы ХассеПримерКоды можно рассматривать как геометрические пространственные фигуры НДиаграммы Хассе известны с XIX в., использовались в генеалогии

Слайд 10Time-Out

Time-Out

Слайд 11Покрываемость элементов:
aj

(наибольший) элемент ai :
ji ai

(sup)
Инфимум (inf)

Отношение покрываемости в упорядоченном множестве

Н

{a}<{a,c}
{a,c} – старший элемент
Пустое множество является нулевым элементом: infM=; универсум – единичным элементом supM=U.

M={a,b,c}

Покрываемость элементов:aj

Слайд 12Пример
B1={{1},{2}}; B2={{1},{1,2}}.
Для B1: множество верхних граней – {

{1,2}, {1,2,3} }
sup B1={1,2}, inf B1=.

Ни одна из верхних граней не принадлежит множеству B1.
Для B2 : множество верхних граней – {{1,2},{1,2,3}}, множество нижних граней B2 –{,{1}}.
supB2={1,2}, infB2={1}, т.е. обе точные грани принадлежат множеству B2.


A={1,2,3} частично упорядочено отношением включения

Пример B1={{1},{2}}; B2={{1},{1,2}}. Для B1: множество верхних граней – { {1,2}, {1,2,3} } sup B1={1,2},

Слайд 13Единственность наибольшего (наименьшего) элемента
Теорема. Упорядоченное
множество М содержит не
более одного наибольшего
(наименьшего)

элемента.

Пусть mi , mj – два наибольших элемента,


mi  mj или mj  mi
Тогда в силу
антисимметричности
получаем mi=mj 
существует единственный наибольший элемент

Def: цепь M´M - подмножество упорядоченного множества.
Длина цепи: l =| M´|-1.
Def: высота элемента d(mi) упорядоченного множества M – максимум длин цепей m0mi – наибольший элемент, m0– минимальный элемент множества M.
Def: длина упорядоченного множества:

Единственность наибольшего (наименьшего) элементаТеорема. Упорядоченноемножество М содержит неболее одного наибольшего(наименьшего) элемента.  Пусть mi , mj –

Слайд 14Пример

Пример

Слайд 15Def: отношение R-1 называется обратным к R, если
(y,x) R-1

 (x,y)R
Принцип двойственности: отношение, обратное к отношению упорядоченности, является отношением

упорядоченности. Упорядоченные множества М и М двойственны, если М определено на том же носителе с помощью обратного отношения.
Диаграмма, двойственная к диаграмме Хассе

Обратное отношение. Принцип двойственности

Def: отношение R-1 называется обратным к R, если (y,x) R-1  (x,y)RПринцип двойственности: отношение, обратное к отношению

Слайд 16Выводы
Бинарное отношение порядка устанавливает на множестве отношение покрываемости, задает предшествование

и старшинство элементов
Упорядоченные множества являются иерархическими структурами
Упорядоченные множества представляются диаграммами

Хассе
Коды можно рассматривать как некоторые пространственные геометрические фигуры
Триаду можно представить в виде единичного куба, имеющего координаты вершин, которые отвечают двоичным символам
ВыводыБинарное отношение порядка устанавливает на множестве отношение покрываемости, задает предшествование и старшинство элементовУпорядоченные множества являются иерархическими структурамиУпорядоченные

Слайд 17Выводы
Множества
Декартово
произведение AB,
A1A2… An

Декартова
степень An

Операции, законы

Соответствия
GAB


Отношения


Rn  An

Ak = < Nk, Sk>
Классификация

соответствий



Свойства


+

=

+

=



Операции,
законы


+

Ar = < Nr , Sr>

=

Декартов
квадрат A2

Бинарное
отношение
R2  A2

R~  A2

R  A2

ВыводыМножества Декартово произведение AB,A1A2… An  Декартова степень AnОперации, законыСоответствияGABОтношения Rn  AnAk = < Nk, Sk>

Слайд 18Тест-вопросы
1. Если отношение антирефлексивно, антисимметрично и транзитивно, оно является:
а) отношением

нестрогого порядка;
б) отношением строгого порядка;
в) не является отношением порядка.
2. Если

любые два элемента множества M, на котором задано отношение порядка, сравнимы, М является:
а) неупорядоченным;
б) линейно упорядоченным;
в) частично упорядоченным.

3. Среди следующих отношений, заданных на множестве отрезков, укажите отношение порядка:
а) отрезок х равен отрезку у;
б) отрезок х короче отрезка у в 2 раза;
в) отрезок х длиннее отрезка у.

Тест-вопросы1. Если отношение антирефлексивно, антисимметрично и транзитивно, оно является:а) отношением нестрогого порядка;б) отношением строгого порядка;в) не является

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

Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

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

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


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

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