Презентация на тему: ТЕОРИЯ МНОЖЕСТВ УПОРЯДОЧЕННЫЕ МНОЖЕСТВА. ОТНОШЕНИЕ ПОРЯДКА лекция 5

ТЕОРИЯ МНОЖЕСТВ УПОРЯДОЧЕННЫЕ МНОЖЕСТВА. ОТНОШЕНИЕ ПОРЯДКА лекция 5
Цель лекции – изучить свойства упорядоченных множеств и отношения порядка для применения в задачах компьютерной инженерии
ТЕОРИЯ МНОЖЕСТВ УПОРЯДОЧЕННЫЕ МНОЖЕСТВА. ОТНОШЕНИЕ ПОРЯДКА лекция 5
ТЕОРИЯ МНОЖЕСТВ УПОРЯДОЧЕННЫЕ МНОЖЕСТВА. ОТНОШЕНИЕ ПОРЯДКА лекция 5
ТЕОРИЯ МНОЖЕСТВ УПОРЯДОЧЕННЫЕ МНОЖЕСТВА. ОТНОШЕНИЕ ПОРЯДКА лекция 5
Примеры
ТЕОРИЯ МНОЖЕСТВ УПОРЯДОЧЕННЫЕ МНОЖЕСТВА. ОТНОШЕНИЕ ПОРЯДКА лекция 5
Пример
ТЕОРИЯ МНОЖЕСТВ УПОРЯДОЧЕННЫЕ МНОЖЕСТВА. ОТНОШЕНИЕ ПОРЯДКА лекция 5
Time-Out
ТЕОРИЯ МНОЖЕСТВ УПОРЯДОЧЕННЫЕ МНОЖЕСТВА. ОТНОШЕНИЕ ПОРЯДКА лекция 5
ТЕОРИЯ МНОЖЕСТВ УПОРЯДОЧЕННЫЕ МНОЖЕСТВА. ОТНОШЕНИЕ ПОРЯДКА лекция 5
ТЕОРИЯ МНОЖЕСТВ УПОРЯДОЧЕННЫЕ МНОЖЕСТВА. ОТНОШЕНИЕ ПОРЯДКА лекция 5
Пример
ТЕОРИЯ МНОЖЕСТВ УПОРЯДОЧЕННЫЕ МНОЖЕСТВА. ОТНОШЕНИЕ ПОРЯДКА лекция 5
Выводы
Выводы
ТЕОРИЯ МНОЖЕСТВ УПОРЯДОЧЕННЫЕ МНОЖЕСТВА. ОТНОШЕНИЕ ПОРЯДКА лекция 5
1/18
Средняя оценка: 4.5/5 (всего оценок: 68)
Код скопирован в буфер обмена
Скачать (2314 Кб)
1

Первый слайд презентации: ТЕОРИЯ МНОЖЕСТВ УПОРЯДОЧЕННЫЕ МНОЖЕСТВА. ОТНОШЕНИЕ ПОРЯДКА лекция 5

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

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

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

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

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

Слайд 3

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

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

Слайд 4

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

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

Слайд 5

5 Def : бинарным отношением порядка (упорядоченности) называется рефлексивное, антисимметричное и транзитивное отношение Обозначение : 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  ). Определение отношения порядка Бинарное отношение порядка R  Рефлексивность Анти- симметричность Транзитивность = + +

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

Слайд 6: Примеры

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

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

Слайд 7

7 Линейный и частичный порядок Def : линейно упорядоченное множество  x,yM xy или yx частично упорядоченное множество ( имеются несравнимые элементы ) x,yM  ( x  y ) или ( x  y ) Строгий порядок = =антирефлексивность+ +антисимметричность+ +транзитивность Примеры 1. < R,  > 2. <M, B(M)> 

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

Слайд 8: Пример

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

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

Слайд 9

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

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

Слайд 10: Time-Out

10 Time-Out

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

Слайд 11

11 Покрываемость элементов: a j <a i  a k : a j < a k <a i a i – старший элемент Наименьший (наибольший) элемент a i :  ji a i <a j ( a j <a i ) Миноранта (мажоранта) Верхняя (нижняя) грань Супремум ( sup ) Инфимум ( inf) Отношение покрываемости в упорядоченном множестве Н {a}<{a,c} {a,c} – старший элемент Пустое множество является нулевым элементом : infM=; универсум – единичным элементом supM=U. M={a,b,c}

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

Слайд 12

12 Пример B 1 ={{1},{2}}; B 2 ={{1},{1,2}}. Для B 1 : множество верхних граней – { {1,2}, {1,2,3} } s up B 1 ={1,2}, inf B 1 = . Ни одна из верхних граней не принадлежит множеству B 1. Для B 2 : множество верхних граней – {{1,2},{1,2,3}}, множество нижних граней B 2 –{ ,{1}}. supB 2 ={1,2}, infB 2 ={1}, т.е. обе точные грани принадлежат множеству B 2.  A={1,2,3} частично упорядочено отношением включения <A,  >

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

Слайд 13

13 Единственность наибольшего (наименьшего) элемента Теорема. Упорядоченное множество М содержит не более одного наибольшего (наименьшего) элемента. Пусть m i, m j – два наибольших элемента, m i  m j или m j  m i Тогда в силу антисимметричности получаем m i =m j  существует единственный наибольший элемент Def: цепь M´ M - подмножество упорядоченного множества. Длина цепи : l =| M´|-1. Def: высота элемента d(m i ) упорядоченного множества M – максимум длин цепей m 0 <m 1 <…  <m i в М, m i – наибольший элемент, m 0 – минимальный элемент множества M. Def: длина упорядоченного множества :

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

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

14 Пример  {a,b,c,d} { a } {b} {c} {d} { a,b} { a,c} { a,d} {b,c} {b,d} {c,d} {a,b,c} {a,b,d} {a,c,d} {b,c,d} M M ´

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

Слайд 15

15 Def: отношение R -1 называется обратным к R, если (y,x)  R -1  (x,y)R Принцип двойственности : отношение, обратное к отношению упорядоченности, является отношением упорядоченности. Упорядоченные множества М и М двойственны, если М определено на том же носителе с помощью обратного отношения. Диаграмма, двойственная к диаграмме Хассе Обратное отношение. Принцип двойственности

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

Слайд 16: Выводы

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

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

Слайд 17: Выводы

17 Выводы Множества Декартово произведение A  B, A 1  A 2 …  A n Декартова степень A n Операции, законы Соответствия G  A  B Отношения R n  A n A k = < N k, S k > Классификация соответствий Свойства + = + = Операции, законы + A r = < N r, S r > = Декартов квадрат A 2 Бинарное отношение R 2  A 2 R ~  A 2 R   A 2

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

Последний слайд презентации: ТЕОРИЯ МНОЖЕСТВ УПОРЯДОЧЕННЫЕ МНОЖЕСТВА. ОТНОШЕНИЕ ПОРЯДКА лекция 5

18 Тест-вопросы 1. Если отношение антирефлексивно, антисимметрично и транзитивно, оно является: а) отношением нестрогого порядка; б) отношением строгого порядка; в) не является отношением порядка. 2. Если любые два элемента множества M, на котором задано отношение порядка, сравнимы, М является: а) неупорядоченным; б) линейно упорядоченным; в) частично упорядоченным. 3. Среди следующих отношений, заданных на множестве отрезков, укажите отношение порядка: а) отрезок х равен отрезку у; б) отрезок х короче отрезка у в 2 раза; в) отрезок х длиннее отрезка у.

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