2 – апта. Арнайы бинарлық қатынастар
Жаттығу. Жоғарыда келтірілген мысалдарға сәйкес фактор-жиындар қандай болады? Қасиеттері
жүктеу/скачать 172,92 Kb.
|
2 лекция (2)
- Бұл бет үшін навигация:
- Теорема 1.13 (Бөліктеу туралы ).
- Транзитивтiлiк.
| Жаттығу. Жоғарыда келтірілген мысалдарға сәйкес фактор-жиындар қандай болады?
Қасиеттері. Бұл қасиеттердің алғашқы екеуі эквиваленттік қатынастың рефлексивтілік және cимметриялық қасиеттерінен, үшіншісі екінші қасиетке транзитивтілікті қолданғаннан, ал төртіншісі эквиваленттілік класының анықтамасынан шығады. Егер А жиыны және оның iшкi жиындары 1, 2, … m …үшiн болғанда, шарттары орындалса, бiрiгу мүшелерi А жиынының бөлiктерi, ал осы шарттарды қанағаттандыратын 1 2… m … жиындар тiзбегi А жиынының бөлiктеуi деп аталады. Теорема 1.13 (Бөліктеу туралы). А жиынында анықталған кез келген эквиваленттiлiк қатынас үшiн оның эквиваленттiлiк кластары А жиынының бөлiктеуiн анықтайды. Керiсiнше, жиынның әрбiр бөлiктеуі осы жиындағы өзiне сәйкес эквиваленттiлiк қатынасты анықтайды. Дәлелдеуi. – А жиынында анықталған эквиваленттік қатынас болса, онда оның жиынының бөліктеулерін анықтайтыны жоғарыда келтірілген төрт қасиеттен тікелей шығады. А жиыны мен оның бөлiктеуiн құратын iшкi жиындарының тiзбегi 1 2… m … берiлсiн. Онда қатынасын x, y үшiн x y iI табылып, x, y i шартымен анықтайық. Бұл қатынастың рефлексивтi және симметриялы болатыны анықтамадан айқын көрiнiп тұр. Сондықтан оның транзитивтiлiгiн көрсетсек жеткiлiктi. Транзитивтiлiк. Қандай да бiр x, y, z элементтерi үшiн, анықтама бойынша x y және y z болсын. Онда i, jI нөмірлері табылып, x, yAi және y, z Ai болады. Яғни yAiAj. Ал (1) бөлiктеу болғандықтан, Ai Aj немесе i = j. Яғни x, y, z Ai. Онда x z. Теорема дәлелдендi. Егер – А жиынында анықталған эквиваленттік қатынас болса, онда эквиваленттілік кластар жиынын эквиваленттілік қатынасы бойынша А жиынында анықталған фактор-жиын деп атайды. Бинарлық қатынастарға келесі амалдарды қолдануға болады. – жиынында анықталған бинарлық қатынас болсын. Онда , , Егер – жиынында анықталған бинарлық қатынастар болса, онда . Осы амалдардан басқа бинарлық қатынастардың жиын болатынын ескеріп, олардың бірігуін, қиылысуын, айырмаларын, симметриялық айырмаларын және берілген қатынасқа жиынындағы толықтауышын қарастыруға болады. Оларды жиындарға қолданылататын амалдардың белгілеулеріне сәйкес және таңбаларымен белгілейміз. Мысалы амалы төмендегідей анықталады: Бөліктеу туралы теорема көптеген комбинаторикалық есептерде өте пайдалы құрал болып табылады. Біз осы теореманы қолдануға және арнайы бинарлық қатынастар санын анықтауға мысал келтірейік. Мысал. жиынында анықталған рефлексивті, иррефлексивті, симметриялы және эквиваленттілік қатынастар болатын бинарлық қатынастардың сандарын анықтайық. . Бинарлық қатынас рефлексивті болу үшін ондағы барлық диагоналдық элементтер осы қатынасқа тиісті болуы керек. Яғни, диагоналдық элементтер рефлексивті қатынастардың санына әсер етпейді. Сондықтан, рефлексивті қатынастар саны жиынының ішкі жиындарының санына тең болады. Демек берілген жиындағы рефлексивті қатынастар саны . Дәл осылай ой түю осы жиындағы иррефлесивті қатынастар саны да болатынын көрсетеді. Ал симметриялық қатынастардың санын есептегенде компоненттері әртүрлі элементі қатынасына тиісті болса, онда болуы керек. Сондықтан, симметриялы қатынастар саны комбинаториканың негізгі (көбейту) принципі бойынша және жиындарының ішкі жиындарының сандарының көбейтіндісіне тең. Яғни . Тура осылай берілген жиындағы антисимметриялық қатынастар саны да 64 болады. Ал берілген жиындағы эквиваленттілік қатынастар санын анықтау үшін бөліктеу туралы теореманы қолданамыз. А жиынының барлық бөліктеулері мыналар: , , , , . Онда теорема бойынша осы жиындағы барлық эквиваленттілік қатынастар саны 5-ке тең. жүктеу/скачать 172,92 Kb. Достарыңызбен бөлісу:
|