Релација со строг редослед. Релација со строг редослед Релација со строг линеарен редослед ги има својствата

Зборот „ред“ често се користи во најразновидните прашања. Офицерот дава команда: „Пресметај по редослед на броеви“, аритметичките операции се изведуваат по одреден редослед, спортистите стануваат во висина, сите водечки шахисти се распоредени по одреден редослед според таканаречените Ело коефициенти (американски професор кој го развил системските коефициенти, што овозможува да се земат предвид сите успеси и неуспеси на играчите), по првенството, сите фудбалски тимови се распоредени по одреден редослед, итн. засадени магаре не "!).

Со подредување на елементите на одредено множество еден по друг, ние со тоа ги наредуваме или воспоставуваме некаков однос меѓу нив. во низа.Наједноставниот пример е природниот редослед на природните броеви. Неговата природност лежи во тоа што за кои било два природни броја знаеме кој од нив следи по другиот или кој од нив е поголем од другиот, така што можеме да ги подредиме природните броеви во низа така што ќе се лоцира поголемиот број, за на пример, десно од помалиот: 1, 2, 3, ... . Се разбира, низата на елементи може да се напише во која било насока, а не само од лево кон десно. Самиот концепт на природни броеви веќе ја содржи идејата за ред. Со воспоставување на одреден релативен распоред на елементите на кое било множество, на тој начин поставивме на него некаква релација со бинарен ред, која во секој конкретен случај може да има свое име, на пример, „биди помал“, „биди постар“, „содржан во“ , „следи“ итн. Симболите за нарачка можат да бидат и различни, на пример, Í итн.

Главната карактеристика на релацијата поредок е тоа што има својство на транзитивност. Значи, ако имаме работа со низа од некои објекти x 1, x 2, ..., x n,... , нареди, на пример, во однос на , потоа од она што се врши x 1x 2... x n..., треба да следи дека за кој било пар x i, x jсе врши и елементи од оваа низа x ix j:

За пар елементи x iјво графиконот за односи цртаме стрелка одозгора x iдо врвот x jт.е. од помал елемент до поголем.

Графикот на релација на редот може да се поедностави со користење на т.н Хасе дијаграми.Дијаграмот Хасе е конструиран на следниов начин. Помалите елементи се поставени подолу, а големите се горе. Бидејќи едно такво правило не е доволно за сликата, се цртаат линии кои покажуваат кој од двата елементи е поголем, а кој помал од другиот. Во овој случај, доволно е да се нацртаат само линии за непосредно следење на елементите. Примери на Хасе дијаграми се прикажани на сликата:

Стрелките може да се испуштат во Хасе дијаграм. Хасе дијаграмот може да се ротира во рамнината, но не произволно. При вртење, неопходно е да се одржи релативната положба (горе - долу) на темињата на дијаграмот:

Став Рво мноштво Xповикани однос на строг ред,ако е преоден и асиметричен.

Се нарекува множество во кое е дефинирана релација со строг редослед уреден.На пример, множеството природни броеви е подредено според релацијата „помалку од“. Но, истото множество е подредено и со друга релација - „се дели со“ и „поголемо“.

Графикот на релацијата „помалку од“ во множеството природни броеви може да се претстави како зрак:

Став Рво Xсе нарекува релација нестрог (делумен) ред, ако е транзитивен и антисиметричен. Секоја врска од нестрог ред е рефлексивна.

Епитетот „делумно“ го изразува фактот дека можеби не сите елементи на множеството се споредливи во овој поглед.

Типични примери за однос на парцијален ред се „не повеќе“, „не помалку“, „не постаро“. Честичката „не“ во имињата на односите служи за изразување на нивната рефлексивност. Релацијата „не повеќе“ се совпаѓа со релацијата „помалку или еднаква на“, а релацијата „не помалку“ е иста како „поголема или еднаква на“. Во овој поглед се нарекува и делумниот ред лабавиво ред. Често, делумна (не-строга) релација за ред се означува со симболот "".

Релацијата за вклучување U помеѓу подмножества на некое множество е исто така делумен редослед. Очигледно, ниту едно две подмножества не се споредливи во овој поглед. Сликата подолу покажува делумен редослед со вклучување на множеството од сите подмножества од множеството (1,2,3). Стрелките на графиконот, кои треба да се насочени нагоре, не се прикажани.

Се нарекуваат множества на кои се дава делумна наредба делумно нарачана,или едноставно уреденмножества.

Елементи Xи насе нарекуваат делумно наредени множества спореди,ако Xнаили наX.Инаку, тие не се споредливи.

Се нарекува подредено множество во кое било кои два елементи се споредливи линеарно подредени, а редоследот е линеарен редослед. Линеарниот ред се нарекува и совршен ред.

На пример, множеството од сите реални броеви со природен ред, како и сите негови подмножества, е линеарно подредено.

Може да се нарачаат предмети од најразновидна природа хиерархиски.Еве неколку примери.

Пример 1: Деловите од книгата се подредени така што книгата содржи поглавја, поглавјата содржат делови, а деловите се состојат од потсекции.

Пример 2. Папките во компјутерскиот датотечен систем се вгнездени една во друга, формирајќи структура на разгранување.

Пример 3. Односот родители - деца може да се прикаже во форма на т.н семејно дрво,кој покажува кој е чиј предок (или потомок).

Нека на сетот НОдадена делумна наредба. Елемент Xповикани максимум (минимум)елемент од множеството А, ако од фактот дека Xна(наX),следи еднаквост X= y.Со други зборови, елементот Xе максимумот (минимумот) ако за кој било елемент наили не е точно дека Xна(наX), или се изведува X=y.Така, максималниот (минималниот) елемент е поголем (помал) од сите други елементи со кои е во врска.

Елемент Xповикани најголем (најмал),ако за некој наÎ НОизведена на< х (х< у).

Делумно подредено множество може да има повеќе минимални и/или максимални елементи, но не може да има повеќе од еден минимален и максимален елемент. Најмалиот (најголем) елемент е исто така минимум (максимум), но обратното не е точно. Сликата лево покажува делумен редослед со два минимум и два максимални елементи, а десно - делумен редослед со најмалите и најголемите елементи:

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

Подредено множество кое има најголеми и најмали елементи се нарекува ограничен .Сликата покажува пример на бесконечно ограничено множество. Се разбира, невозможно е да се прикаже бесконечно множество на конечна страница, но можно е да се прикаже принципот на неговата конструкција. Овде јамките во близина на темињата не се прикажани за да се поедностави цртежот. Од истата причина, не се прикажани лаците кои обезбедуваат приказ на својството за транзитивност. Со други зборови, на сликата е прикажан Хасе дијаграм на релацијата на редот.

Бесконечните множества може да немаат максимум, минимум или и двете. На пример, множеството природни броеви (1,2, 3, ...) има најмал елемент 1, но нема максимум. Множеството од сите реални броеви со природен ред нема ниту најмал ниту најголем елемент. Сепак, неговото подмножество се состои од сите броеви X< 5 има најголем елемент (број 5), но нема најмал елемент.

Нека R е бинарна релација на множество А.

ДЕФИНИЦИЈА. бинарна врска R на множеството А се нарекува релација за ред на А или ред на А ако е преодно и антисиметрично.

ДЕФИНИЦИЈА. Релацијата на редот R на множеството А се нарекува нестрога ако е рефлексивна на А, т.е. за кое било од А.

Релацијата за редослед R се вели дека е строга (на А) ако е антирефлексивна на А, т.е. за кое било од А. Меѓутоа, антисиметријата на преодната релација R произлегува од фактот дека таа е антирефлексна. Затоа, можеме да ја дадеме следната еквивалентна дефиниција.

ДЕФИНИЦИЈА. Бинарната релација R на множеството А се нарекува строг редослед на А ако е преоден и антирефлексивен на А.

Примери. 1. Нека е множеството од сите подмножества на множеството M. Релацијата за вклучување на множеството е релација со нестрог редослед.

2. Односите на множеството реални броеви се, соодветно, однос на строг и нестрог редослед.

3. Релацијата на деливост во множеството природни броеви е однос од нестрог ред.

ДЕФИНИЦИЈА. Бинарната релација R на множеството А се нарекува релација пред ред или предредба на А ако е рефлексивна на и преодна.

Примери. 1. Односот на деливост во множеството цели броеви не е ред. Сепак, тој е рефлексивен и транзитивен, што значи дека е претходна нарачка.

2. Релацијата логичка последица е предредба на множеството искази логички формули.

Линеарен редослед. Важен посебен случај на нарачка е линеарен редослед.

ДЕФИНИЦИЈА. Релација за редослед на множество се нарекува релација со линеарен ред или линеарен редослед на ако е поврзана на , т.е. за кое било x, y од A

Релацијата за ред што не е линеарна најчесто се нарекува релација со парцијален ред или делумен ред.

Примери. 1. Релацијата „помалку од“ на множеството реални броеви е релација од линеарен ред.

2. Релацијата на редот прифатена во речниците на рускиот јазик се нарекува лексикографска. Лексикографскиот редослед на множеството зборови во рускиот јазик е линеарен редослед.

Зборот „ред“ често се користи во различни прашања. Службеникот ја дава командата: „Пресметај по редослед на броеви“, аритметичките операции се изведуваат по одреден редослед, спортистите стануваат во висина, има налог за извршување операции при изработка на дел, редослед на зборови во реченица.

Што е заедничко во сите случаи кога се работи за нарачка? Фактот дека зборот „ред“ има такво значење: значи кој елемент од ова или она множество кое следи (или кој елемент му претходи на кој).

став“ Xследи на» преодно: ако « Xследи на"и" наследи z", тогаш" xследи z“. Покрај тоа, овој сооднос мора да биде антисиметричен: за две различни Xи на, ако Xследи на, тогаш нане следи X.

Дефиниција.Став Рна сетот Xповикани строг однос на редот, ако е транзитивен и антисиметричен.

Дозволете ни да ги дознаеме карактеристиките на графикот и графикот на односите со строг редослед.

Размислете за пример. На сетот X= (5, 7, 10, 15, 12) релацијата Р: « X < на“. Оваа врска ја дефинираме со набројување на парови
Р = {(5, 7), (5, 10), (5, 15), (5, 12), (7, 10), (7, 15), (7, 12), (10, 15), (10, 12), (12, 15)}.

Ајде да го изградиме неговиот график. Гледаме дека графикот на оваа релација нема јамки. Нема двојни стрелки на графиконот. Доколку од Xстрелката оди до на, и од на- во z, потоа од Xстрелката оди до z(Сл. 8).

Конструираниот график ви овозможува да ги распоредите елементите на множеството Xпо овој редослед:

{5, 7, 10, 12, 15}.

На сл. 6 (§ 6 од ова поглавје) колоните VII, VIII се графикони на односи од строг редослед.

Нестрога релација за нарачка

Релацијата „помалку од“ во множеството реални броеви е спротивна на релацијата „не помалку“. Тоа веќе не е строга наредба. Поентата е, во X = на, односи X ³ наи на ³ X, т.е. релацијата „ни помалку“ е рефлексивна.

Дефиниција.Став Рна сетот Xповикани нестрога релација на ред, ако е рефлексивен, антисиметричен и транзитивен.

Ваквите односи се соединувања на строг редоследен однос со идентитетски однос.

Размислете за релацијата „нема повеќе“ (£) за множеството

X= (5, 7, 10, 15, 12). Да го изградиме неговиот график (сл. 9).

Графикот на релација со строг редослед, за разлика од графикот на релација со строг ред, има јамки на секое теме.

На сл. 6 (§ 6 од оваа глава) графиконите V, VI се графикони на односи од нестрог редослед.

Нарачани комплети

Едно множество може да испадне дека е подредено (велат и целосно подредено) од некоја релација на редот, додека друго може да биде неуредено или делумно подредено од таква релација.

Дефиниција.Многу Xповикани уреденнекаков ред однос Рако за кои било два елементи x, yод X:

(X, на) Î Рили ( y, x) Î Р.

Ако Ре строга редовна релација, потоа множеството Xнаредено со оваа релација под услов: ако X, накои било два нееднакви елементи од множеството X, тогаш ( X, на) Î Рили ( y, x) Î Р, или кои било два елементи x, yмножества Xсе еднакви.

Од училишниот курс по математика е познато дека бројот се поставува Н , З , П , Р подредено според соодносот „помалку од“ (<).

Множеството подмножества на одредено множество не е подредено со воведување на инклузивна релација (U), или строга инклузивна релација (Т) во горната смисла, бидејќи има подмножества од кои ниту едно не е вклучено во другото. Во овој случај, даденото множество се вели дека е делумно подредено со релацијата Í (или Ì).

Размислете за комплетот X= (1, 2, 3, 4, 5, 6) и има две врски „помалку од“ и „деливи со“. Лесно е да се провери дали и двете од овие односи се релации на ред. Графикот помал од релација може да се претстави како зрак.

Графикот на релацијата „се дели со“ може да се прикаже само на рамнина.

Покрај тоа, на графикот на втората релација има темиња кои не се поврзани со стрелка. На пример, нема стрелка што ги поврзува броевите 4 и 5 (сл. 10).

Првата врска X < на' се нарекува линеарна. Во принцип, ако редоследот однос Р(строго и нестрого) на сетот Xима својство: за било кој X, наÎ Xили xRy, или yRx, тогаш се нарекува релација со линеарен ред, а множеството Xе линеарно подредено множество.

Доколку сетот Xсе разбира, и се состои од nелементи, потоа линеарното подредување Xсе сведува на набројување на неговите елементи со броевите 1,2,3, ..., n.

Линеарно подредените множества имаат голем број својства:

1°. Нека а, б, в– поставени елементи X, подредено по однос Р. Ако се знае дека aRvи vRc, тогаш велиме дека елементот волежи помеѓу елементите аи Со.

2°. Многу X, линеарно подредено според релацијата Р, се нарекува дискретно ако помеѓу кои било два негови елементи се наоѓа само конечен сет на елементи од ова множество.

3°. Линеарно подредено множество се нарекува густо ако за кои било два различни елементи од ова множество има елемент од множеството што лежи меѓу нив.

Важен тип на бинарни односи се релации со ред. Релација со строг ред -бинарна релација која е антирефлексна, антисиметрична и транзитивна:

ознака - (апретходеше б).Примери се

односи „поголемо од“, „помалку од“, „постари“ итн. За броевите, вообичаената нотација се знаците "<", ">".

Не-строга врска со нарачката -бинарна рефлексна, антисиметрична и транзитивна врска. Заедно со природните примери на нестроги неравенки за броеви, пример е односот помеѓу точките во рамнина или простор „да бидат поблиску до потеклото“. Нестрогата неравенка, за цели броеви и реални броеви, може да се смета и како дисјункција на еднаквоста и односите со строг ред.

Ако спортски турнир не предвидува поделба на места (т.е. секој учесник добива одредено, само јадење / наградено место), тогаш ова е пример за строг ред; во спротивно, не-строги.

Релациите за ред се воспоставуваат на множество кога, за некои или сите парови од неговите елементи., релацијата

првенство . Поставување-за множество се нарекува некаква релација за редослед неговата „наредба,и „себе.постави како резултат на ова станува уреден.Релациите на редот можат да се воведат на различни начини. За конечно множество, секоја пермутација на неговите елементи "одредува некој строг ред. Бесконечното множество може да се подреди на бесконечен број начини. Само оние подредувања што имаат значајно значење се од интерес.

Ако за нарачката релација Рна сетот .Ми некои различни елементи, барем една од односите важи

aRbили градник ,потоа елементите аи бповикани споредливиинаку - неспоредлив.

Целосно (или линеарно) подреден сет М -

множество на кое е дадена релацијата за ред, и кои било два елементи од множеството Мспоредливи; делумно нарачан сет- исто, но се дозволени парови на неспоредливи елементи.

Линеарно подредено множество е збир на точки на права линија со однос „десно“, множество од цели, рационални, реални броеви во однос на „поголемо од“ итн.

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

Односно, ако приоритетот е задоволен во сите три координати, векторите (2, 8, 5) и (6, 9, 10) се споредливи, а векторите (2, 8, 5) и (12, 7, 40 ) не се споредливи. Овој начин на подредување може да се прошири на вектори од која било димензија: вектор

му претходи на векторот ако

И готово

Други примери за подредување може да се разгледаат на множеството вектори.

1) делумна нарачка: , ако

Оние. по должината на векторите; вектори со иста должина се неспоредливи.

2) линеарен редослед: , ако а ако а-д,тогаш б< е ; ако jed \u003d c? u6 \u003d e, тогаш