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

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

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

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

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

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

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

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

наибольший (наименьший) элемент,
мажоранта (миноранта),
верхняя (нижняя) грань,
супремум (инфимум)

отношение
Обозначение: 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).

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

yx

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

или (x  y )

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

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


2.



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

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

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

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

Н

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

M={a,b,c}

{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} частично упорядочено отношением включения

элемента.

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

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

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

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

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

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

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

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

Rn  An

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

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

Свойства

+

=

+

=

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

+

Ar = < Nr , Sr>

=

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

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

R~  A2

R  A2

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

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

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