WikiDer > Qaramlik munosabati - Vikipediya

Bu maqola uchun qo'shimcha iqtiboslar kerak tekshirish. Iltimos yordam bering ushbu maqolani yaxshilang tomonidan ishonchli manbalarga iqtiboslarni qo'shish. Ma'lumot manbasi bo'lmagan material shubha ostiga olinishi va olib tashlanishi mumkin. Manbalarni toping: "Qaramlik munosabati" – Yangiliklar · gazetalar · kitoblar · olim · JSTOR (2008 yil mart) (Ushbu shablon xabarini qanday va qachon olib tashlashni bilib oling)

Yilda Kompyuter fanlari, xususan kelishuv nazariyasi, a qaramlik munosabati a ikkilik munosabat bu cheklangan,^[1]:4 nosimmetrikva reflektiv;^[1]:6 ya'ni cheklangan bag'rikenglik munosabati. Ya'ni, bu cheklangan to'plamdir buyurtma qilingan juftliklar ${ displaystyle D}$, shu kabi

• Agar ${ displaystyle (a, b) in D}$ keyin ${ displaystyle (b, a) in D}$ (nosimmetrik)
• Agar ${ displaystyle a}$ bu munosabat aniqlangan to'plam elementidir, keyin ${ displaystyle (a, a) in D}$ (refleksiv)

Umuman olganda, qaramlik munosabatlari bunday emas o'tish davri; Shunday qilib, ular an tushunchasini umumlashtiradilar ekvivalentlik munosabati transitivitni bekor qilish orqali.

Agar ${ displaystyle Sigma}$ (shuningdek, deyiladi alifbo) qaysi to'plamni bildiradi ${ displaystyle D}$ belgilanadi, keyin mustaqillik tomonidan qo'zg'atilgan ${ displaystyle D}$ ikkilik munosabatdir ${ displaystyle I}$

${ displaystyle I = ( Sigma times Sigma) setminus D}$

Ya'ni, mustaqillik bu mavjud bo'lmagan barcha buyurtma qilingan juftlarning to'plamidir ${ displaystyle D}$. Mustaqillik munosabati nosimmetrik va irrefleksivdir. Aksincha, har qanday nosimmetrik va irrefleksiv munosabat berilgan ${ displaystyle I}$ cheklangan alfavitda, munosabat

${ displaystyle D = ( Sigma times Sigma) setminus I}$

qaramlik munosabati.

Juftliklar ${ displaystyle ( Sigma, D)}$ va ${ displaystyle ( Sigma, I)}$,^{[iqtibos kerak]} yoki uchlik ${ displaystyle ( Sigma, D, I)}$ (bilan ${ displaystyle I}$ tomonidan qo'zg'atilgan ${ displaystyle D}$) ba'zan bir vaqtda alifbo^{[iqtibos kerak]} yoki ishonch alifbosi. Bunday holda, elementlar ${ displaystyle x, y in Sigma}$ deyiladi qaram agar ${ displaystyle xDy}$ ushlab turadi va mustaqil, boshqasi (ya'ni, agar shunday bo'lsa) ${ displaystyle xIy}$ ushlab turadi).^[1]:6

Ishonch alifbosi berilgan ${ displaystyle ( Sigma, D, I)}$, nosimmetrik va irrefleksiv munosabat ${ displaystyle doteq}$ da belgilanishi mumkin bepul monoid ${ displaystyle Sigma ^ {*}}$ chekli uzunlikdagi barcha mumkin bo'lgan satrlar bo'yicha: ${ displaystyle xaby doteq xbay}$ barcha torlar uchun ${ displaystyle x, y in Sigma ^ {*}}$ va barcha mustaqil belgilar ${ displaystyle a, b in I}$. The ekvivalentlikni yopish ning ${ displaystyle doteq}$ bilan belgilanadi ${ displaystyle equiv}$, yoki ${ displaystyle equiv _ {( Sigma, D, I)}}$va chaqirdi ${ displaystyle ( Sigma, D, I)}$-ekvivalentlik. Norasmiy, ${ displaystyle p equiv q}$ agar mag'lubiyat bo'lsa ${ displaystyle p}$ ga aylantirilishi mumkin ${ displaystyle q}$ qo'shni mustaqil belgilarni almashtirishning cheklangan ketma-ketligi bilan. The ekvivalentlik darslari ning ${ displaystyle equiv}$ deyiladi izlar,^[1]:7–8 va o'rganiladi iz nazariyasi.

Misollar

Alifbo berilgan ${ displaystyle Sigma = {a, b, c }}$, mumkin bo'lgan bog'liqlik ${ displaystyle D = {(a, b), , (b, a), , (a, c), , (c, a), , (a, a), , (b, b), , (c, c) }}$, rasmga qarang.

Tegishli mustaqillik ${ displaystyle I = {(b, c), , (c, b) }}$. Keyin, masalan. belgilar ${ displaystyle b, c}$ bir-biridan mustaqil va h.k. ${ displaystyle a, b}$ bog'liqdir. Ip ${ displaystyle acbba}$ ga teng ${ displaystyle abcba}$ va ga ${ displaystyle abbca}$, lekin boshqa mag'lubiyatga.

Adabiyotlar

Bu mavhum algebrabilan bog'liq maqola a naycha. Siz Vikipediyaga yordam berishingiz mumkin uni kengaytirish. v t e

Bu Kompyuter fanlari maqola a naycha. Siz Vikipediyaga yordam berishingiz mumkin uni kengaytirish. v t e