Diskretka

Diskretka.doc20.02.2014

41

Отношение R намножестве Х является транзитивным, есдлявсехи

x, y, z X из

соотношений хRу, уRz следует хRz. Например,вотно«перацшениия

х

предшествует

операции y,аоперация

у предшествуетоперации

z из хRу и уRz следует хRz.

- город x связангородом

y шоссейндорогой

– междугородом

y и z

- студент x ровесникстуденту

y

- треугольник x подобентреугольнику

y

- действительноечисло

x большедействительногочисла

y

(в) симметрично,

если xRy yRz дляпроизвольных

x, y X ,

Отношение R намножестве Х является симметричным, есдлявсехи

х,у Х из хRу

следует уRх. Например,вотношениях

«х похожна

у»,операция«

х несовместима

операцией у» иместокакет

хRу, таки

уRх. Действ,еслительно

х похожна

у, то у похож

на х, еслиоперация

х несовместима

у, тооперация

у несовместима

х.

- прямая х перпендикулярна у (нерефлексивно)

.

- студент х приходитсясоседом

у (нерефлексивно) .

(в1) антисимметрично,

если xRy yRz x

y= дляпроизвольных

x, y X .

Отношение R намножестве

Х является антисиммитричным,

еслиоотношения

хRу

и уRх выполняютсятогдаитолькотогда,когда

ху=

длявсех

x, y X .

Например,в

отно«перацшениия

х являечасоперацитьюся

и у» иместоет

хRу и уRх толькотогда,

когда х=у .

- бинарноеотношевключениямножествие

(в2) асимметрично,

если xRy yRz x y= дляпроизвольных

x, y X .

Отношение R намножестве

Х является асимметричным, еслииздвухсоотношений

хRу,

уRх одновыполненодлявсех

x, y X . Например,вотношениях

«х подчиняется у»,

«операция х выполненараньшеоперации

у» иместоет

хRу, ноневыполняется

уRх.

Посмыслуотношение

эквивалопркакеделяентносэлементы« сяи

х и у

одинаковы»,элементы«

х и у взаимозаменяемы».

Вэтомотношениикаждыйэлементэквсамомувалсебер( нтенфлексивность).

Есэлементи

х

эквивалэлементену

у, тоиэлемент

у

эквивалэлементену

х

(симме тричность)Ес. элемент

х эквивалэлементену

у,

аэлемент у

эквивалентен

элементу z,тоэлемент х эквивалэлементену

z (транзитивность).

Лемма1.

ВсякоеразбиениемножестваАнаклассызадмножествеетА

отношениеэквивал.

нтности

a, b A,положим aRb ↔ a и b лежатводномклассе

Доказательство.Пусть

разбиения.Покажем,чтоп лученноебинарнотношеявляетсяношением

эквивал.Дляэтогонентнобхдоказать,чтооностидиморефлексивно,симметрично

a лежитвнекоторклассеразбиения,том

aRa,т.е.

транзитиДействительно.

.Поскольку

онорефлексивно.

Пусть K – некоторыйклразбиениясс

a,b K тогдаи

b, a K т.е

aRb → bRa,

Симметричностьдоказана.

Из aRb → bRc следует a,b, c K ,Сл едовательно aRc,ч.т.д.

Diskretka.doc20.02.2014

42

Лемма2.

Всякоеотношениеэквивал нтности

R,определенноена

множествеА

задразбиениенаетклассы.

Междуразбиениямимноженаклаотношениямиссытва

Лемма3.

эквив,заледанныминаэтоммножестветностисуществует, взаимно

однозначное

соответствие.

Пример1

.Отношениеэквивмножесалчиселнтносношениеявляевется

a=a

равенства(=)Любоечисло.

а измножестдействительныхчиселравносамомусебе

(рефлекс)Есл. ивность

а= b, то b=а

(симметричность)

. Если а= b,

а b=с , то а=с

(транзитивность)

.

Пример2.

Отношенияпараллельнплоскостипрямыхвэвклидовой.

Пример3.

Отношенияпроживанияодномдомежителейгорода.

Отношениеэквивразбивалюбомннтннепересекающиесяжествоости

подмножества(

классыэквивале

нтности)В.примвсе3житгореразбиваютсялиодана

жителей,живущиходнихтехжедомах.Врезультатеполучимсток ассовько

U

I

Мi, — i-й

эквивалентности,сколькодомов,которыхпрожлюди.Такимобразомвают,если

класс iÎI, а М — множествожителей,

то

iÎIMi =M,

Mi

Mj= длявсех

i, j Î I ,где I —

множествоклассов.

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

1. R - отношениеравенства

(=).

Отношениеравенства

x = y являетсяэквивнлюбмножеале тностьюве

A, так

каконо

рефлексивно (x = x),

симметрично (x = y y = x),

транзитивно (x = y & y = z x = z).

2. R - отнподобиятреугольниковшение

.

Отнпонашендобиямножестветр угольниковявляетсяотношением

эквивалентности.

рефлексивно (x = x),

симметрично (x = y y = x),

транзитивно (x = y & y = z x = z).

3. R - отношениеравномощности

.

Налюбмножестве

B(U) отношениеравномощности

|A| = |B| являетсяотношением

эквивалентности.Длялюбыхмножеств

A, B, C выполняследусвойства:ютсящие

рефлексивно:

(A ~ A поскольку idA : A ↔ A),

f: A ↔ B следует f-1: B ↔ A),

симметрично:если

A ~ B,то

B ~ A (таккакиз

транзитивно:если

A ~ B и B ~ C,то

A ~ C (таккакиз

f: A ↔ B, g: B ↔ C следует

f◦g: A ↔ C).

4. R - отношениепринадлежности

.

Отношениепринак студенойлежностигруппемножествеачестудентовкой

МГСУявляетсяотношениемэквивалентности.

рефлексивно (x = x),

симметрично (x = y y = x),

транзитивно (x = y & y = z x = z).

5. R - отношевычислениеодтойжефункции

.

Пусть M – множествопрограмм,вычисляющиходнутужефункцию.Отношение

E = {(x,y)|программы

x и y вычоднуисляютжефункцию}

намножеств

е M является

отношениемэквивалентности.

Diskretka.doc20.02.2014

43

симметрично (x = y y = x),

транзитивно (x = y & y = z x = z).

Отношение толерантности

Отношение R намножестве

Х называетсяотношением

толерантности,

еслионо

- рефлексивно

- симметрично.

Пример.Отношениеигрок«

х играетсамсобойвшахматыидругом

у» есть

отнтолерш,такниекакнтности

хRх, а хRу влечет уRх.

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

А)Нестпорядокогий

Отношение R намножестве

Х называетсяотн

ошением нестпо,рядкаого

еслионо

- рефлексивно,

- антисимметрично

- транзитивно.

Отношения ≤,≥

намножествечисел

Х являютсяотношенинестрогогопор,такядками

каклюбоечисло

хÎХ

равносамомусеберефлексивность( ).

Длялюбойпарычисел

х,у

ÎХ

при а≤b невыполняется

b≤a, апри

а≥b невыполняется

b≥a (антисимметричность).

х,у, zÎX, если а≤b и b≤с, то а≤с или,если

а≥

b, b≥с, то а≥с

Длялюбтрчиселойки

(транзитивность).

Отношениечастичнойупорядообыобозччерезностиноачается

«≤»

,апара <Х,≤

> называется частичноупорядмножеством. ченным

Будемпримен

ятакжеьочевидные

обозн,такичения

х≥у для у ≤ х, х<у. для x ≤ y x ≠ y ит.д.

Примеромчастичноупорядможетслужитьчемножествогоствацелых

чиселотношеделимости, ножествоцилилых(веще)чиселобычнтвеныхм

≤ »,атакжемножество

Р(X) сотношениемвключения

отношенменьшеиравнолием«

.

В)Отношение строгопорядка

Отношение R намножестве

Х называетсяотношением

строгопорядка,

еслионо

Отношения <, > намножествечисел

Х являютсяотношениямистрп ,гоготакрядка

каклюбоечисло

хÎX

неможбытьеилиньшебольшесамогосебяантирефлексивность( ).

Длялюбойпарычисел

х,уÎX

при х<у

неможетбыть

у<х

, апри х>у

невыполняется

у>х (антисимметр ичность).

х,у,

zÎX, если х<у , а у<

z, то х<

z, если х>у

, а у> z,то х> z

Длялюбтрчиселойки

(транзитивность).

Множество Х сзаданнымнанемотношеннестрогилипемогогорядка

<X, R>.

R

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

Есдкаждлия

ойпары

х,уÎX

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

порядка,томножество

<X, R> называется полностьюупорядоченным.

Впротивномслучае

Diskretka.doc20.02.2014

44

Строгийилинестрогийпорядок,заданныйнаполнупорядстью

очемнноможестве

<X, R>,называется

линейнымпорядком

.

Пример1.

Всемножествачиселлинейноупорядо,таккаклюбыхячизенысел

этихмнодноменьшеждругогоствилиониравны.

Пример2.

Множествобукврусскогоилатинскогоалфавиталинейноуп ря

дочено

отношениемпредшествования,или,чтоже,отношениемследования.

Пример3.

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

строгийчастичныйпорядок,таккаквнемнесравнимысотразнудникиотделов. х

Тернарныеотношения

Декартовым произведением X ×Y ×Z трехмножеств

X,Y,Z называетсямножествовсех

упорядоченныхтроек

<х,у, z>, составленизэлемеэтихмножествтактовых,что

X×Y×Z =

{<х,у, z>|хÎХ,уÎ

Y, zÎZ}. Любоенепустое

подмножество T декартовапроизведения

X×Y×Z

множеств X, Y, Z называется тернарнымотношением

между X, Y и Z изаписываетсятак:

Т

X ×Y×Z.

Пример.Трехместнымиотношениями

Т X×Y×Z могутбытьтакие: из1)

х видов

сырья у предприятийвыпускают

z видовпродукции; 2)

х покупаелейтоваренпают

z це;н3)амо

х бомбардировщикам у ракетно-зенитныхкомпдазалпексови

z ракетами.

n-арныеотношения

X,Y можнопостроить

Поаналогиисдекапроизведениемтомножествымух

декартовопроизведение

X×Y×Z трехмножеств

X,Y,Z ивообщедекартовопроизведение

Х1 ×

Х2 × ... ×Хn

п множеств Х1,Х 2, Х... , n.

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

Х1 ×Х2 × ...

×Хn

п множеств Х1,Х 2, Х... , n

называется

множествовсехупорядоченных

п-ок

<х 1,х 2,...,

xn>,составленизэлемеэтихнтовых

множествтак,что

Х1 ×Х2 × ...

×Хn =х {< 1,х

2,..., xn>|x1 X1, x2 X2, …, xn Xn}. Любое

непустоеодмножество

N декартовапроизведения

Х1 ×Х2 × ... ×Хn п множеств Х1,Х 2, Х... ,

n

называется n-арнымотношением

между Х1,Х 2, Х... ,

n изаписываетсятак:

N Х1 ×Х2 × ... ×

Хn.

M1 = M2 =…= Mn,топиш

ут Mn.Часто Mn называют универсальным

Втомслучае,если

отношением. Точка наплоскосрассматриможеткакупорядоченная,врааться

пространстве - упорядтройка.К ченнаяординатноепредставвпервыеввеРенеление

«декартов опроизведение»

Декарт(1596

-1650),поэтониоазываетсяму

.

множеств М1,М 2,М 3, .М. . ,

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

M = {(mi

, mi

,..., mi

)

mi

M1, mi

M 2 ..., mi

M n }.

1

2

n

1

2

n

Элементамидекартовапроизведения

M1 × M2 × M ×...× Mn

являютсявсевозможные

последова,каждаяизкостельностиизстоитрых

п элементов,причемпервыйэлемент

принадлежитмножеству

М1, второй — множеству М2,..., п-йэлемент

— множеству Мn.

Теорема.

Дляконечныхмножеств

A и B, мощносдекартопроизраьведенияна

произведениюмощнодекарстейжесоизведеният,т..о ого

|A´B| = |A| |B|

Доказательство.

Первыйкомупонентрядпарыможновыбратьченной

|A|

способами,второй

|B| способами.Всегоупорядоченныхпар

<aibj> будет |A| |B|ч.т.д.

Diskretka.doc20.02.2014

45

Пример1.

Скольвариантовкквадрантраскикругаозм,еслидопускаетсявжно

пятьцветовкраски.

Решение:

4,каждаякомпоненкраскикоторогоестьцве,естьэлемент

Кортеждлины

Mк,б,з,с,=ф} {

декапроизведениятового.Пустьцветакраскиобразуютмножество

.Тогда

М4 =ММ´М´М´

и çМ 4ç = ç54ç = 625.

Отображения

Отображения – энекоторыесвязимеждуэле ножеентами.Проствейшими

х Х элемента х множеству Х и

примерамиотношеявляютсянпринадлежностиошенияий

отношениявключения

А В, А В подмножества А вподмножество В.

Пок личествуэле,междукоентоопределерымивсвязи,отношенияделятсяыа

n-арные(

n-

ународ( н),ыеоместбинардвухм( тернарные), трехместные( )и

мест)В.унаротыеноучаствуетшениимодинэлеме.Этиотнназываютсяошения

свойствамиотожде

ствляютсяподмножеэлемен,которыеэтимсвойством

обладают.Так,например,вмножествевсехположитечиселотношениесвойствольных

«бытьчетным»отождествляетподмножечисел2, 4,с6,ятвом....

Вбинарныхотношенияхучаствуютпарыэлементо

вмножеств,такназываемые

упорядоченныепары

<х 1,у 1>,х

<

2,у 2>,х 1,х 2, … Х,у

1,у 2, … Y. Упорядоченность

понимаетсякакто,чтовзаписи

<х,у>

напермевсомстоиттеегда

х X, анавтором

у Y.

Инымисловами,

х предшествует у.

Соответствие

Подмножество S декапроизведениятовогоназывается

n-арнымсоответствиe

элементовмножеств

Mi.

Формально S M.

Частныеслучаи.

1Если.

n = 2,тоговорят

бинарномсоответствии

S M1 M2.

2Еслиговорят. подмножескортежуниветйрсальношевеногоия

Mn,тоимеют

ввиду n-арноеотношение

r,т.е.

R Mn.

3. R M2 называют бинарнымотношением

намножестве M.

4. Однозначное n-арноеотношениеесть

n-местфу.наякция

Пример.

Пусть Mх= { 1,х 2,х 3} и R M2.

{‹x1,x1›, ‹x2,x1›, ‹x3,x1› }

Замечание.

{‹x1,x2›, ‹x2,x4›, ‹x3,x3› }

Поскольку S являетсяподмн,тоожговоритьествомнечётких

соответствиях,отношениях,функциях.

Функция

Восновевсехразделовдискр

етнойматематикилежитпонятфункции. е

Пусть Х — некотмножествоначислроеоси.Гово,чтонаэтомйрятмножестве

определена функция f,есликаждомучислу

хÎХ поставленосоответствиеопределенное

число у= f(х) . Приэтоммножество

Х называется областьюопределениязадания( )

функции f,

асовокупностьзначений

у=f(х)

— множество Y — областьюеезначений

.Длянаглядности

функцию у=f(х) представляютееграфикомкоординатных

осях хОу.

Diskretka.doc20.02.2014

46

Нарис. вкачествепр5, ,изображенамфункция

у=|х| . Областьопред

еленияэтой

функции — интервал(

-∞,∞)Обл. знастьчений

— интервал(0,∞).

Переменную х называют аргументом функции,а

у — ее значением. Значок f

интер,какпр,преобразованияавет лоруетсяаргумента

х взначение

у,

т.е.представляет

собойспособреали

зациисоответствия.Этотспособможетбытьзадананалитически

(формулой),ввидетабл,графиспециальнойцыкавычислительнойпроцедурой.Важно

хÎХ

толь,чтодлякаждогозначения

ондолжендаватьодитолькоднзачение

у=f(х) .

еременных у= f(х 1,х 2, х…,

n) вводитсяаналогич.Пустьзадано

Функциямногихп

множество Х1 ×Х2 × ... ×Хn.Тогда,еслилюбупорядоченномунабору

<х 1,х 2,..., xn>ÎХ

1 ×

Х2 × ... ×Хn поопределенномуправилу

f поставленосоответствиечисло

у= f(х 1,х 2, х…,

n),

тоговорят,чтонамножестве

Х1 ×Х2 × ...

×Хn определфункциямногихенаременных

f(х 1,

х2, х…, n).

Х1 ×Х2 × ...

×Хn

Рассвмчисловыхатриваяесто

множеств

множествалюбой

при, риходыксамбщемудимопределениюф .Пустьнкции

М и

N — два

произвольныхмножества.

хÎМ

Есликаждомуэлементу

понекоторомуправилупоставленсоответств

иеодин

итолькоодинэлемент

N.

уÎN ,тонамножестве

М определена

функция

f,

принимающая

значенияизмножества

функция»частоупотерминребляют«

отображение»,понимая

Вмтерминасто«

поднимотображениеодногомножествадругое.Вданномслучаеимеот м

ображения

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

М вмножество

N. Записываютэ :ако

f:М→N.

Представлениефункциитермотношенийнах

f,еслииз

Функцией называетсябинарноеотношение

< x, y > f

и

< x, z >

f

следует,что

y = z.

F M x × M y ,

функцией,

Подмножество

называется

есдлякаждогои

элемента

x, x M x ,найдетсянебодноголееэлемента

y, y M y вида (x, y) F ; приэтомесдляи

каждогоэлемента

х имеетсяодинэлемент

у вида (x, y) F ,

тофункцияназывается

всюду

(полностью)определенной,

впротивномслучае

—

частичноопределенной

(недоопределенной).

Множество Мx образуетобласопределенияфункцииь

F,множество Му

— область

значефункцииий

F. Частовместозаписи

(x, y) F используютзапись

у=

F(х)

; при этом

элементхназываютаргументомилипеременной,

у — значефункцииием

F.

Пусть X, Y - некотмн.Говорятжестварые,чтозадана

функцияотображения( )

,

действующаяизмножества

X множество

Y,еслизаданзаконилиправило

f,покоторому

каждомуэлеме

нту x измножества

X ставитсясоответствиеединствеэлементный

y из Y: y

= f(x).

Пусть X = R (всещественныечисла)

Y = [-1; 1].Рассмотрфункцимю

y =

Пример.

sin x.Каждомуэлементуиз

X поставленсоотвэлизменттствие

Y: пусть x =р/2,

тогда y =

sinр/2 = 1.

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

значенийфункции

f.Элемент

y

= f(x) Y

называют образом элемента x приотображении

f.Элемент

x - прообраз элемента y под

действиемотображения

f.Множество

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

прообразов отображения f.

Пример.

Дляфункции

y = sin x: x = R - множествопрообразов;

Y:=[-1; 1] - множество

значефункции; ий

y = 1 - образ x =р/2

приданномотображении

(yр/2= sin=1 ),

x =р/2

-

прообразэлемента

y = 1 приданномотображении.

Diskretka.doc20.02.2014

47

Пример1.1. Нарис. а1изображено.2,

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

множеств Мx = {х 1,х 2,х 3,х 4} и Му =у {

1,у 1,у 3}, не

являющеесяфу;нрисакцией. б, 1.2,

-

являющеесяполностьюопределенной

фу;нрисакцией. в 1.2,

—

частично

определеннойфункцией.

Количествоаргументовопределяет

местфункции. ость

Вышебылирассмотрены

одноместныефункции.Аналогичнопонятиюкартовапроизведениядвухмножеств

опрдекартоводелимпроизведение

п множеств.

Еслимножество

Мx вопределениифункции

у =

F(х) являетсядек

артовым

произведмножениемств

Мx1,М x2, .М. . , xn,тополучаемопределение

п-местфункцииой

у= F(х 1,х 2, .х. . , n).

Двефункции

f и g равны,еслионисостоятизоднихтехжеэлементов.Область

определфункцииобластьезначенийиязадается

акже,какидлябинарныхотношений.

Еслиобластьопределения

дf =Х иобластьзначений

сf Y,тоговорят,чтофункция

f задана

намножестве Х созначевомножествеиями

Y,приэтом

f отобрамножаетесво

Х во

множество Y.Этоотображение

обозначаетсякак

f: Х → Y.

Если f — функция,вместо

< x, y > f

пишут y = f(х) иговорят,что

y — значение,

соответствующееаргументу

х, или у — образэлемента

х приотображении

f.Приэтом

х

называютпрообразомэлемента

у.

Назовем f — n-местфункциейой

из Х в Y,если

f: Х →Y.Тогдазаписываем

y = f(х 1, …

хn) иговорим,что

у — значениефункции

призначенииргументов

х1, х… n.

x X элемент

Если функция

(отображение)

f сопоставляеткаждомуэлементу

f (x) Y , тобудемписать

f:Х →Y

(такаяфункцияможеттра отношениетоватьсяак

R X Y стемсвойством,чтодлякаждого

x X

существует

R точнооднапаравида

<х, y>,

y Y ;длянашихжецелейдоста

точноинтуитивногопонятияфункции).

Отношение R Х ×Y,т.е.множествоупорядпар ченных

<х,у

>, х X,у

Y называется

функцией тогдаитолькотогда,когдапервыеэлементыэтихпарнеповторяются.

Пример.

Отнявляетсяошениефун,таккаконоципредставленойследующими

парами:

<1,2>, <1,3>, <2,3>, <2,4>, <3,3>, <3,4>, <4,2>, <4,3>. Примеромфункциинатомже

декапроизведениитоявляетсятношением

<1,2>, <2,4>, <3,4>, <4,3>.

Требованиенепо

вторяемостипервыхэлементовупорядоченныхпар, едставляющих

отноше,гарантируетие

Diskretka.doc20.02.2014

48

Функции,функционалы,оператор

Х и

Взависимоттого,какойхарактерстимножестваеютзада

нияфункций

множестваеезначений

Y,выделяют

функциичисловые

(Х и Y — числовыемножества),

функционалы (множество

Х — любойприроды,амножество

Y — числовое),

операторы

(множества X, Y — любойприроды).

Пример. Число1. функцийявляютсявсеыхэле

ментарныефу, апримеркции,

у=

х2, у= logх,у=

sinх ит.д.а,такжеихсуперпозиции.

2. Функционал.Пустьвнекготродером

N междудвумяпунктами

АиВ

имеется

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

X, каждойизкотп ройставленосоотввр тствиемя

t Т передвижения

понейавто.Тогдамобиляножествопар

<х, t>, х X, t T — функционалот

t,определенный

намножестве

X.

3Примером.

оператора можбытьтелефкнига,вкоторойннаякаждойфамилии

абонентапоставленсоответс

тводинтолькоеодинномереготелефона.

Инъекция,сюръ,биекция

Х

в Y и

Прииспользованиитерминаотображение« » зличаютотображение

отображение Х на Y.

Х отображаетсянанек тороебствподмножествонное

Yс Y,

Втомслучае,когда

Х в Y.

— этоотображение

Yс=Y, — этоотображение

Х на Y. Ононазывается

Впротивномслучае,..когда

сюръекцией.

х1,и х2 функции f(x1) и f(x2) такжеразличны,такая

Есдлюбыхиядвухразличных

функция f называется инъективной.

Функцияназываетс

я биективной иливзаимноодноз,еслисъюрсктивначнойи

инъективна.

Пусть f: Х → Y.Функция f называется инъективной,есдлиюбыхя

х1, х2, y, из у=

f(x1) и у= f(x2) следует,что

x1 = x2.

y Y

Функция f называется сюръективной,еслид

лялюбогоэлементам

существует

элемент x X

такой,что

у= f(х) .

Функция f называется биективной,если

f одновременносюръективнаинъективна.

Есуществуетлибиективнаяфункци

f:

Х →Y,тоговорят,что

f осуществляет

взаимно-однозначноесоответствиемеждумножествами

Х и Y.

Суперпозициябинарныхотношений

x X

Если f:

Х →Y,а g:

Y →Z, тофункция

F: X →Z, определеннаядлякаждого

формулой F(х) =

g(f(х))

, называется

композициейсуперпозицией( )

функции

f и

g,или

сложнойфункцией

.

Diskretka.doc20.02.2014

49

Дляпроизвольных

A X ,

B Y определим

f(А) = {

y Y : существуеттакое

x А ,

что у=

f(х)}

f -1(В) = {

x X : f (x) B }.

Если f(А)

= Y,тобудемговорить

офункции

из Х на Y.Функция

f:Х→ Y называется

обратоднозначнойвза( им),но

еспроизвольныхдля

a,b X

а≠

b → f(а)≠

f(b).Пустьзадафунакция

f: Х → Y и сf

— множествоеезначений.

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

<y, f-1(y)>,

y ρ f

образуетфункцию,

котораяназывается

обратнойфункцией

дляфункции

f:иобозначается f-1.

Обратнаяфункция

f-1

ставитсоокаждомуветствиеэлемен

ту

y ρ f

егопрообраз

f-

1(y),т.е.некотмножествоэлеменрое.Заметим,чтодля,чтобыгов

f былаинъективной.

f-1

являлась

функцией,достаточно,чтобыфункция

Классификацияотображений

Пусть X и Y - двач стичноупорядмнож. ченныхства

Отображение ζ множеств X на Y есть изоморфизм (илиизоморфноеотображение),

еслионовзаимнооднозначпорядоксохра,тоестьння равенства

х≤у

и ζх)(≤ζу)(

равносильны.

ζ -1 естьтакжеизоморфизм.

Обратноеотображение

Вслучаесущизствования

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

называются изоморфными.

Изоморфныечастичноупорядочмн бычженстваныео

отождествляют,по точкиколькузрениясвой,связанпорядкомтв, ныхеразличимы.

Отображение ц называется изотопным,

еслинеравенс

тво х≤у

влечет ζх)(≤ζу)(

.

Изомотовсегдарфнбражизно(нетоннонаоборотние!).

ω множества X на Y называется дуальным

Взаимнооднозначноеот браж ние

изоморфизмом,

еслиравнеравенстваосильы

х≤у

и ζх)(≥ζу)(

.Еслитакоеотображение

существует,тоговорят,что

X и Y дуальноизом. рфны

Операция

п-местфунойкции

у =

F(х 1,х

2, .х . . ,

n) является п-местная

Часлучаемтным

операция.Под п-местнойоперацией

On вмножестве

М понимается п-местфунаякция

у=

F(х 1,х 2, .х. . ,

n),укоторойоб

ластиопределеаргументовиобластьзначеияфункцииий

совпадают:

М1

=М 2

= М... =

n

=М у. Такимобразом,

п-местнаяоперацияпо

п элементам

множества М определяет (п+ 1)

-йэлементэтогоже

множества.

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

-арной(n

-местной)операцией

намножес

тве M

называется n-

местфунаякция

у=

f(x 1,x2,...,xn),укоторойобластьопределенияаргументов

xi иобласть

значефункциисовпадаютий

(n N).

Пояснение.

1Тот.факт,чтоалгебраическаяоперацияявляечаслучаемтнымсябинарного

f: Mn → M., т.е.:

однозначногосоответствия,отражаетсяеёформальнойзаписи

2Поскольку. алгебраическаяоперацияпо

n элементаммножества

M определяет (n+1)

элемеэтогоженожества

M,то

n-местнуюалгебраическуюоперациюможно

рассматриватьикак (n+1)-арноеоднозотношениемножествеачное

M.

3Если.

f: M → M,тоговорятобународ( но)алгебраическойместнойоперации;

если f: M2 → M,тоимеютввидубинарнуюдвухместную( )алгебраическуюоперацию.

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

Множество S называется частичноупорядоченным

(ЧУМ),еслинанемзадано

рефлексивное,транзитивантисбинотношениемметричноеойарное

частичногопорядка

с.

Diskretka.doc20.02.2014

50

Частичнымупорядочениемчастичным( порядком)

внепустоммножестве

X

назывсякоеаетсяподмножествоа

P X 2 ,удовлетворяющееследующим

аксиомам:

x X справедливо (x, x) P - рефлексивность отношений.

I.Прилюбом

II.Если (x, x) P и ( y, x) P ,то

y = x - антисимметричность отношений.

III.Если

(x, y) P и ( y, z) P,то

(x, z) P - транзитивность отношений.

Частовместозаписи

(x, y) P пишут

x≤y

или

y≥x

.Иногдавместознака

≤

могутпридругиеменятьпохожиесимволынапример

p

.Тогдааксиомыможнозаписатьв

виде:

x X

I.

x ≤ x привсехправедливо

- рефлексивность отношений.

II.Если x≤y

и y≤x

,то

y = x - антисимметричность отношений.

III.Если

x≤y

и y≤z

,то

x≤z

- транзитивность отношений.

Этисоотношенияназываютсянеравенствами.