книги / Основы дискретной математики

- II -

инверсией соответствующих пар графика Р

„ Вели Р ш{<

то

< d , c > } -

Композицией графиков Р

и Q

назы­

вается такой график R= P°Q , что < x , y > e R тогда и только тогда,

когда есть

такой элемент

2

, что<к,г> *Р % a < z . y > e

Q

Диагональный график - график вида

= /<*,х-> <у,у;>...}

для всех

x . f €Л7. График называется функциональным,

если он не

содержит

пар с одинаковыми первыми и различными вторыми компонентами.

График называется инъективным, если он не содержит

пар с одина­

ковыми вторыми в различными первыми компонентами.

Декартовым произведением множеств

А жб

называется множест­

во

A * & s { < a . 6 > \ а е А , ё е в } .

Декартово произведение множеств A f,. ,

А п

4 ' “V

' АП * i < a r аг ...ап >1а-,*А1. а г £ А , ... А п }.

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

< Р , Х , У >

такая, ч г о Р £

Л

* У

, где множество

X называется

областью отправления, множество У

- областью прибытия.

но.

Отношением называется пара вида У7» <Ф,м>

такая, что

ф £ М*

, где

Ф - график, a flf - то множество,

между элемента­

ми которого

существует данное отношение <Р . Отношение называет­

ся полным,

если

Ф -М . Отношение называется отношением равенст­

ва, воли

Ф *

. Отношение называется отношением неравенства,

(наименьшим),

если для воех и справедливо, что а е

А ^

х

( х ^ а е А

). Минимальным (максимальным) элементом частично

упорядоченного множества А

называется такой элемент

б е А ,

когда

в А нет

элемента строго большего (строго меньшего)

$ .

Пусть дано ф я в Я А

, где А - частично упорядоченное мно­

жество. Мажорантой б

называется такой элемент а е А , где

а.

является

наибольшим элементом для

3

, минорантойЛ назовем такой

элемент

б е А

» когда б является наименьшим элементом для

б .

Множество мажорант

&

образует верхние грань множества в .

Множество минорант

3

образует нижнюю грань множества в . Наи­

меньший из элементов верхней грани

В

называется точной верх­

Алгебраическое

представление решетки

Введем обозначении:

S u p ( a , S ) = a и ё ,

1 р / ( а , б ) = а . п ё ,

(в данном случае символы U,f) -

это не знаки операций объедине­

2. Ассоциативный.

а

п (б л с ) = ( а п 6 ) л с , а и ( & и с ) =

» (а и ё ) и с ;

3. Идемпотентности.

a n c z = a . а. и а, *

а. ;

4. Поглощения, а

о ( а и $J= CL , а и (а. л

& ) - <х .

Решетка называется дистрибутивной, если

справедлив, хроме

шие элементы, а также Sap б

и I n f 3 для множеств, представ­

ленных диаграшамн Хаосе рис.

I.I7.

Рис. I.17.

(5) врешетке любо! максимальный элемент является нанболь-

янм,

а яхк>1 минимальные - наименьшим;

в)

в любов конечно! решетке существуют наибольшие и наимень

шие

элементы,

32.

Привести примеры решеток:

а) беэ наибольшего элемента, но с наименьшим элементом;

б'

зэ наименьшего элемента, но с наибольшим элементом;

Jes наибольшего и наименьшего элементов.

33.

Являютоя ли множества, представленные диаграммами lacce

рис. I.I8:

а)

решетками;

б) дистрибутивными решетками;

в)

булевыми решетками?