Qattiq tartib munosabatlari. Qattiq tartib munosabati Qattiq chiziqli tartib munosabati xossalarga ega

"Buyurtma" so'zi ko'pincha eng xilma-xil masalalarda qo'llaniladi. Ofitser buyruq beradi: "Raqamlar tartibida hisoblang", arifmetik amallar ma'lum tartibda amalga oshiriladi, sportchilar balandlikka ko'tariladi, barcha etakchi shaxmatchilar Elo koeffitsientlari deb ataladigan (amerikalik professor) ma'lum bir tartibda joylashadilar. o'yinchilarning barcha yutuq va kamchiliklarini hisobga olishga imkon beruvchi tizim koeffitsientlarini kim ishlab chiqdi), chempionatdan so'ng barcha futbol jamoalari ma'lum bir tartibda joylashadilar va hokazo qismlarni ishlab chiqarishda operatsiyalarni bajarish tartibi mavjud. , jumladagi so'z tartibi ("u keksa odam" jumlasi eshak ekilgan emas "!) nimani anglatishini tushunishga harakat qiling.

Muayyan to'plamning elementlarini birin-ketin joylashtirish orqali biz ularni tartibga solamiz yoki ular o'rtasida qandaydir aloqa o'rnatamiz. ketma-ket. Eng oddiy misol - natural sonlarning natural tartibi. Uning tabiiyligi shundan iboratki, har qanday ikkita natural son uchun biz ulardan qaysi biri ikkinchisini kuzatib borishini yoki qaysi biri ikkinchisidan katta ekanligini bilamiz, shuning uchun biz natural sonlarni ketma-ketlikda joylashtirishimiz mumkin, shunda kattaroq son joylashadi. masalan, kichikroqning o'ng tomonida: 1, 2, 3, ... . Albatta, elementlarning ketma-ketligini faqat chapdan o'ngga emas, balki istalgan yo'nalishda yozish mumkin. Natural sonlar tushunchasi allaqachon tartib g'oyasini o'z ichiga oladi. Har qanday to'plam elementlarining qandaydir nisbiy joylashishini o'rnatib, biz shu bilan unga har bir aniq holatda o'z nomiga ega bo'lishi mumkin bo'lgan qandaydir ikkilik tartib munosabatlarini o'rnatamiz, masalan, "kamroq bo'lish", "kattaroq bo'lish", "o'z ichiga" , "kuzatish" va hokazo. Buyurtma berish uchun belgilar ham har xil bo'lishi mumkin, masalan, Í va boshqalar.

Tartib munosabatining asosiy farqlovchi xususiyati uning tranzitivlik xususiyatiga egaligidir. Shunday qilib, agar biz ba'zi ob'ektlar ketma-ketligi bilan shug'ullanadigan bo'lsak x 1, x 2, ..., x n,... , buyurilgan, masalan, ga nisbatan, keyin bajarilganidan x 1x 2... x n..., har qanday juftlik uchun shunga amal qilishi kerak x i, x j bu ketma-ketlikning elementlari ham bajariladi x ix j:

Bir juft elementlar uchun x ij munosabatlar grafigida biz yuqoridan o'qni chizamiz x i tepaga x j, ya'ni kichikroq elementdan kattaroq elementga.

Tartib munosabatlari grafigi deb atalmish yordamida soddalashtirilishi mumkin Hasse diagrammasi. Hasse diagrammasi quyidagicha tuzilgan. Kichikroq elementlar quyida, kattalari esa yuqorida joylashgan. Tasvir uchun shunday bitta qoida yetarli emasligi sababli, ikkita elementning qaysi biri ikkinchisidan kattaroq va qaysi biri kichikroq ekanligini ko'rsatadigan chiziqlar chiziladi. Bunday holda, bir-birining elementlarini darhol kuzatib borish uchun faqat chiziqlarni chizish kifoya. Hasse diagrammalariga misollar rasmda ko'rsatilgan:

Hasse diagrammasida strelkalar qoldirilishi mumkin. Hasse diagrammasi tekislikda aylantirilishi mumkin, lekin o'zboshimchalik bilan emas. Burilish paytida diagramma cho'qqilarining nisbiy holatini (yuqorida - pastda) saqlash kerak:

Munosabat R ko'plikda X chaqirdi qat'iy tartib munosabati, agar u tranzitiv va assimetrik bo'lsa.

Qattiq tartib munosabati aniqlangan to'plam deyiladi tartibli. Masalan, natural sonlar to`plami “kichikroq” munosabati bilan tartiblangan. Ammo xuddi shu to'plam boshqa munosabat bilan ham tartibga solinadi - "bo'linadi" va "kattaroq".

Natural sonlar to'plamidagi "kichik" munosabat grafigi nur sifatida ifodalanishi mumkin:

Munosabat R ichida X munosabat deyiladi qat'iy bo'lmagan (qisman) tartib, agar u tranzitiv va antisimmetrik bo'lsa. Qat'iy bo'lmagan tartibning har qanday munosabati refleksdir.

"Qisman" epiteti, ehtimol, to'plamning barcha elementlarini bu jihatdan solishtirish mumkin emasligini ifodalaydi.

Qisman tartib munosabatining tipik misollari: "ortiq emas", "kam emas", "eski emas". Munosabatlar nomlaridagi “no” zarrasi ularning refleksligini ifodalashga xizmat qiladi. “Ko‘p emas” munosabati “kichik yoki teng” munosabatiga to‘g‘ri keladi, “kam emas” munosabati esa “katta yoki teng” munosabati bilan bir xil bo‘ladi. Shu munosabat bilan, qisman tartib ham deyiladi lax tartibda; ... uchun. Ko'pincha qisman (qat'iy bo'lmagan) tartib munosabati "" belgisi bilan belgilanadi.

Ba'zi to'plamning kichik to'plamlari orasidagi U inklyuziya munosabati ham qisman tartibdir. Shubhasiz, bu jihatdan hech qanday ikkita kichik to'plamni solishtirish mumkin emas. Quyidagi rasmda to'plamning barcha kichik to'plamlari to'plamiga kiritish orqali qisman tartib ko'rsatilgan (1,2,3). Grafikdagi yuqoriga qaratilishi kerak bo'lgan o'qlar ko'rsatilmagan.

Qisman buyruq berilgan to'plamlar chaqiriladi qisman buyurtma qilingan, yoki oddiygina tartibli to'plamlar.

Elementlar X va da qisman tartiblangan to'plam deyiladi solishtirish, agar Xda yoki daX. Aks holda, ularni taqqoslab bo'lmaydi.

Har qanday ikkita element o'xshash bo'lgan tartiblangan to'plam deyiladi chiziqli tartiblangan, va tartib chiziqli tartibdir. Chiziqli tartib mukammal tartib deb ham ataladi.

Masalan, natural tartibli barcha haqiqiy sonlar to‘plami, shuningdek, uning barcha kichik to‘plamlari chiziqli tartiblangan.

Eng xilma-xil tabiat ob'ektlari buyurtma qilinishi mumkin ierarxik tarzda. Mana bir nechta misollar.

1-misol: Kitobning qismlari shunday tartiblanganki, kitobda boblar, boblar bo'limlardan, bo'limlar esa kichik bo'limlardan iborat.

2-misol. Kompyuter fayl tizimidagi papkalar bir-birining ichiga joylashib, tarmoqlanuvchi strukturani tashkil qiladi.

Misol 3. O'zaro munosabatlar ota-onalar - bolalar deb atalmish shaklida tasvirlangan bo'lishi mumkin oila daraxti, bu kimning ajdodi (yoki avlodi) ekanligini ko'rsatadi.

To'plamga qo'ying LEKIN qisman buyruq berildi. Element X chaqirdi maksimal (minimal) A to'plamning elementi, agar shundan kelib chiqsa Xda(daX), tenglik kelib chiqadi X= y. Boshqacha aytganda, element X har qanday element uchun maksimal (minimal) hisoblanadi da yoki bu haqiqat emas Xda(daX), yoki bajariladi X=y. Shunday qilib, maksimal (minimal) element u bilan bog'liq bo'lgan barcha boshqa elementlardan kattaroq (kamroq).

Element X chaqirdi eng katta (eng kichik), har qanday bo'lsa daÎ LEKIN amalga oshirildi da< х (х< у).

Qisman tartiblangan to'plamda bir nechta minimal va/yoki maksimal elementlar bo'lishi mumkin, lekin bir nechta minimal va maksimal elementlar bo'lishi mumkin emas. Eng kichik (eng katta) element ham minimal (maksimal) hisoblanadi, ammo buning aksi to'g'ri emas. Chapdagi rasmda ikkita minimal va ikkita maksimal elementlardan iborat qisman tartib, o'ngda esa eng kichik va eng katta elementlar bilan qisman tartib ko'rsatilgan:

Cheklangan qisman tartiblangan to'plamda har doim minimal va maksimal elementlar mavjud.

Eng katta va eng kichik elementlarga ega bo'lgan tartiblangan to'plam deyiladi cheklangan. Rasmda cheksiz chegaralangan to'plamning namunasi ko'rsatilgan. Albatta, cheksiz to'plamni chekli sahifada tasvirlab bo'lmaydi, lekin uni qurish tamoyilini ko'rsatish mumkin. Bu erda chizmani soddalashtirish uchun cho'qqilar yaqinidagi halqalar ko'rsatilmagan. Xuddi shu sababga ko'ra, o'tish xususiyatini ko'rsatishni ta'minlaydigan yoylar ko'rsatilmaydi. Boshqacha qilib aytganda, rasmda tartib munosabatlarining Hasse diagrammasi ko'rsatilgan.

Cheksiz to'plamlar maksimal yoki minimal yoki ikkalasiga ega bo'lmasligi mumkin. Masalan, natural sonlar to'plami (1,2, 3, ...) eng kichik element 1 ga ega, lekin maksimal emas. Tabiiy tartibli barcha haqiqiy sonlar to'plami na eng kichik, na eng katta elementga ega. Biroq, uning kichik to'plami barcha raqamlardan iborat X< 5 eng katta elementga ega (5 raqami), lekin eng kichik elementi yo'q.

A to‘plamdagi R ikkilik munosabat bo‘lsin.

TA'RIF. ikkilik munosabat A to'plamdagi R A to'plamdagi tartib munosabati yoki A to'plamdagi tartib deyiladi, agar u o'tish va antisimmetrik bo'lsa.

TA'RIF. A to'plamdagi R tartib munosabati, agar u A to'plamida, ya'ni A ning har qandayida refleksiv bo'lsa, qat'iy emas deb ataladi.

Tartib munosabati R qat'iy (A bo'yicha) deyiladi, agar u A da, ya'ni A ning istalgan biri uchun antirefleksiv bo'lsa. Biroq, R o'tish munosabatining antisimmetriyasi uning antirefleksli ekanligidan kelib chiqadi. Shuning uchun biz quyidagi ekvivalent ta'rifni berishimiz mumkin.

TA'RIF. A to'plamdagi R ikkilik munosabat, agar u A da o'tish va antirefleksiv bo'lsa, A da qat'iy tartib deyiladi.

Misollar. 1. M to‘plamning barcha kichik to‘plamlari to‘plami bo‘lsin. To‘plamdagi inklyuziya munosabati qat’iy bo‘lmagan tartibli munosabatdir.

2. Haqiqiy sonlar to'plamidagi munosabatlar, mos ravishda, qat'iy va qat'iy bo'lmagan tartibli munosabatdir.

3. Natural sonlar to‘plamidagi bo‘linish munosabati qat’iy bo‘lmagan tartibli munosabatdir.

TA'RIF. A to'plamdagi R ikkilik munosabatlari, agar u refleksiv va o'tishli bo'lsa, A to'plamida oldindan tartib munosabati yoki oldingi tartib deb ataladi.

Misollar. 1. Butun sonlar to‘plamidagi bo‘linuvchanlik nisbati tartib emas. Biroq, u refleksli va o'tish xususiyatiga ega, ya'ni bu oldindan buyurtma.

2. Mantiqiy oqibat munosabati taklif mantiqiy formulalar to‘plamidagi oldingi tartibdir.

Chiziqli tartib. Buyurtmaning muhim maxsus holati chiziqli tartibdir.

TA'RIF. To'plamdagi tartib munosabati chiziqli tartib munosabati yoki chiziqli tartib munosabati deyiladi, agar u ga ulangan bo'lsa, ya'ni A dan istalgan x, y uchun.

Chiziqli bo'lmagan tartib munosabati odatda qisman tartib munosabati yoki qisman tartib deb ataladi.

Misollar. 1. Haqiqiy sonlar to‘plamidagi “kichikroq” munosabati chiziqli tartibli munosabatdir.

2. Rus tili lug'atlarida qabul qilingan tartib munosabati leksikografik deyiladi. Rus tilidagi so'zlar to'plamidagi leksikografik tartib chiziqli tartibdir.

“Buyurtma” so‘zi ko‘pincha turli masalalarda qo‘llaniladi. Ofitser buyruq beradi: "Raqamlar tartibida hisoblang", arifmetik amallar ma'lum tartibda bajariladi, sportchilar balandlikka ko'tariladi, qismni, gapda so'z tartibini yasashda operatsiyalarni bajarish tartibi mavjud.

Buyurtma haqida gap ketganda, barcha holatlarda umumiy nima? "Tartib" so'zining shunday ma'noga ega ekanligi: u yoki bu to'plamning qaysi elementi qaysidan keyin (yoki qaysi element qaysi elementdan oldin) ekanligini anglatadi.

munosabat " X ergashadi da» o'tish: agar « X ergashadi da"va" da ergashadi z", keyin" x ergashadi z". Bundan tashqari, bu nisbat antisimmetrik bo'lishi kerak: ikki xil uchun X va da, agar X ergashadi da, keyin da ergashmaydi X.

Ta'rif. Munosabat R to'plamda X chaqirdi qat'iy tartib munosabatlari, agar u tranzitiv va antisimmetrik bo'lsa.

Grafikning xususiyatlarini va qat'iy tartib munosabatlari grafigini bilib olaylik.

Bir misolni ko'rib chiqing. To'plamda X= (5, 7, 10, 15, 12) munosabat R: « X < da". Bu munosabatni juftlarni sanab o'tish orqali aniqlaymiz
R = {(5, 7), (5, 10), (5, 15), (5, 12), (7, 10), (7, 15), (7, 12), (10, 15), (10, 12), (12, 15)}.

Keling, uning grafigini tuzamiz. Bu munosabat grafigida halqalar yo‘qligini ko‘ramiz. Grafikda qo'sh strelkalar yo'q. Agar dan X strelka boradi da, va dan da- ichida z, keyin dan X strelka boradi z(8-rasm).

Tuzilgan grafik to'plam elementlarini tartibga solish imkonini beradi X bu tartibda:

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

6-rasmda (ushbu bobning 6-bandi) VII, VIII ustunlar qat'iy tartibli munosabatlar grafiklaridir.

Qattiq bo'lmagan tartib munosabatlari

Haqiqiy sonlar to‘plamidagi “kamroq” munosabati “kam emas” munosabatiga qarama-qarshidir. Bu endi qat'iy tartib emas. Gap shundaki, da X = da, munosabatlar X ³ da va da ³ X, ya'ni. “kam emas” munosabati refleksdir.

Ta'rif. Munosabat R to'plamda X chaqirdi qat'iy bo'lmagan tartib munosabatlari, agar u refleksli, antisimmetrik va tranzitiv bo'lsa.

Bunday munosabatlar o'ziga xoslik munosabati bilan qat'iy tartibli munosabatlarning birlashmasidir.

To'plam uchun "endi yo'q" (£) munosabatini ko'rib chiqing

X= (5, 7, 10, 15, 12). Uning grafigini tuzamiz (9-rasm).

Qattiq bo'lmagan tartibli munosabatlar grafigi, qat'iy tartib munosabatlari grafigidan farqli o'laroq, har bir tepada halqalarga ega.

Shaklda. 6 (ushbu bobning 6-bandi) V, VI grafiklar qat'iy bo'lmagan tartibli munosabatlar grafiklaridir.

Buyurtma qilingan to'plamlar

To'plam qandaydir tartib munosabati bo'yicha tartiblangan bo'lishi mumkin (ular ham to'liq tartiblangan deb aytishadi), boshqasi esa bunday munosabat bilan tartibsiz yoki qisman tartiblangan bo'lishi mumkin.

Ta'rif. Kopgina X chaqirdi tartibli ba'zi tartib munosabatlari R har qanday ikkita element uchun bo'lsa x, y dan X:

(X, da) Î R yoki ( y, x) Î R.

Agar a R qat'iy tartib munosabati, keyin to'plam X sharti ostida bu munosabat bilan tartiblangan: agar X, da to'plamning har qanday ikkita teng bo'lmagan elementi X, keyin ( X, da) Î R yoki ( y, x) Î R, yoki har qanday ikkita element x, y to'plamlar X teng.

Maktab matematika kursidan ma'lumki, raqamlar to'plami N , Z , Q , R "dan kam" nisbati bo'yicha tartiblangan (<).

Muayyan to'plamning kichik to'plamlari to'plami yuqoridagi ma'noda qo'shilish munosabati (U) yoki qat'iy inklyuziya munosabati (T) kiritilishi bilan tartibga solinmaydi, chunki birortasi boshqasiga kiritilmagan kichik to'plamlar mavjud. Bunda berilgan to‘plam Í (yoki Ì) munosabati bilan qisman tartiblangan deyiladi.

To'plamni ko'rib chiqing X= (1, 2, 3, 4, 5, 6) va u ikkita "kichik" va "bo'linuvchi" munosabatlariga ega. Bu munosabatlarning ikkalasi ham tartib munosabatlari ekanligini tekshirish oson. Kichikroq munosabat grafigi nur sifatida ifodalanishi mumkin.

"bo'linadi" munosabatining grafigi faqat tekislikda ifodalanishi mumkin.

Bundan tashqari, ikkinchi munosabat grafigida o'q bilan bog'lanmagan cho'qqilar mavjud. Misol uchun, 4 va 5 raqamlarini bog'laydigan o'q yo'q (10-rasm).

Birinchi munosabat X < da' chiziqli deb ataladi. Umuman olganda, tartib munosabati bo'lsa R(qat'iy va qat'iy bo'lmagan) to'plamda X xususiyatiga ega: har qanday uchun X, daÎ X yoki xRy, yoki yRx, u holda chiziqli tartib munosabati va to'plam deyiladi X chiziqli tartiblangan to‘plamdir.

Agar to'plam X albatta, va iborat n elementlar, keyin chiziqli tartib X uning elementlarini 1,2,3, ... raqamlari bilan sanab o'tishga qisqartiradi, n.

Chiziqli tartiblangan to'plamlar bir qator xususiyatlarga ega:

1°. Mayli a, b, c- elementlarni o'rnatish X, munosabat bo'yicha tartiblangan R. Agar ma'lum bo'lsa aRv va vRc, keyin biz element deb aytamiz ichida elementlar orasida joylashgan a va Bilan.

2°. Kopgina X, munosabati bilan chiziqli tartiblangan R, diskret deyiladi, agar uning istalgan ikkita elementi orasida faqat shu to'plam elementlarining cheklangan to'plami bo'lsa.

3°. Chiziqli tartiblangan to'plam zich deb ataladi, agar ushbu to'plamning har qanday ikkita alohida elementi uchun ular orasida to'plamning elementi bo'lsa.

Ikkilik munosabatlarning muhim turi tartib munosabatlaridir. Qattiq tartib munosabatlari - antirefleksiv, antisimmetrik va tranzitiv bo'lgan ikkilik munosabat:

belgilash - (a oldingi b). Misollar

munosabatlari "kattaroq", "kichikroq", "kattaroq" va boshqalar. Raqamlar uchun odatiy belgi - bu belgilar "<", ">".

Qattiq bo'lmagan tartib munosabatlari - binar refleksiv, antisimmetrik va tranzitiv munosabat. Raqamlar uchun qat'iy bo'lmagan tengsizliklarning tabiiy misollari bilan bir qatorda, tekislik yoki fazoning nuqtalari orasidagi "koordinatalar kelib chiqishiga yaqinroq bo'lish" munosabati misol bo'la oladi. Butun sonlar va haqiqiy sonlar uchun qat'iy bo'lmagan tengsizlikni tenglik va qat'iy tartib munosabatlarining diszyunksiyasi sifatida ham ko'rish mumkin.

Agar sport musobaqasi joylarni taqsimlashni nazarda tutmasa (ya'ni, har bir ishtirokchi ma'lum, faqat ovqatlanish/mukofotlangan joyni oladi), unda bu qat'iy tartibning namunasidir; aks holda, qat'iy bo'lmagan.

Tartib munosabatlari to'plamda uning ayrim yoki barcha juftlari uchun munosabat aniqlanganda o'rnatiladi.elementlar.

ustunlik. To'plam uchun qandaydir tartib munosabatlarini o'rnatish deyiladi uning "buyrug'i, va "o'zini. buning natijasida belgilangan bo'ladi tartibli. Tartib munosabatlari turli usullar bilan kiritilishi mumkin. Cheklangan to’plam uchun uning elementlarining har qanday o’rin almashtirishi “qandaydir qat’iy tartibni belgilaydi. Cheksiz to’plam cheksiz ko’p usullarda tartiblanishi mumkin. Faqat mazmunli ma’noga ega bo’lgan tartiblar qiziqish uyg’otadi.

Agar buyurtma munosabati uchun R to'plamda .M va ba'zi turli elementlar, hech bo'lmaganda munosabatlardan bittasi mavjud

aRb yoki b Ra, keyin elementlar a va b chaqirdi solishtirish mumkin aks holda - tengsiz.

To'liq (yoki chiziqli) tartiblangan to'plam M -

tartib munosabati berilgan to‘plam va to‘plamning istalgan ikkita elementi M solishtirish mumkin; qisman buyurtma qilingan to'plam- bir xil, lekin tengsiz elementlarning juftligiga ruxsat beriladi.

Chiziqli tartiblangan toʻplam toʻgʻri chiziqdagi “oʻngga” munosabati bilan nuqtalar toʻplami, “katta”ga nisbatan butun, ratsional, haqiqiy sonlar toʻplami va hokazo.

Qisman tartiblangan to'plamga misol sifatida uch o'lchovli vektorlarni keltirish mumkin, agar tartib xuddi shunday berilgan bo'lsa

Ya'ni, agar har uchala koordinatada ham ustunlik bajarilsa, vektorlar (2, 8, 5) va (6, 9, 10) solishtirish mumkin, vektorlar (2, 8, 5) va (12, 7, 40) ) solishtirish mumkin emas. Bu tartiblash usuli har qanday o'lchamdagi vektorlarga kengaytirilishi mumkin: vektor

agar vektoridan oldin

Va bajarildi

Buyurtmaning boshqa misollarini vektorlar to'plamida ko'rib chiqish mumkin.

1) qisman buyurtma: , agar

Bular. vektorlarning uzunligi bo'yicha; bir xil uzunlikdagi vektorlarni taqqoslab bo'lmaydi.

2) chiziqli tartib: , agar a agar a-d, keyin b< е ; agar jed \u003d c?u6 \u003d e, keyin