Бинарлық қатынастарды зерттеу Жоспары
жүктеу/скачать 26,37 Kb.
|
07.11.20 (1)
5. Бинарлық қатынастың \\aij\\ матрица түрінде берілуі. Матрицаның жолдары мен бағандары қатынастың өрісіне сәйкес келеді. Бұл матрицада i-ші жол қатынастың сол жақ облысының қандайда бір элементімен байланыста, ал j -ші баған оң жақ облысының қандайда бір элементімен байланыста болады. Сонда aij =1 егер сәйкес элементтер берілген қатынаста жатса, қарсы жағдайда aij = 0. Мысалы, алдыңғы мысалдағы S қатынасы келесі кесте түрінде жазылуы мүмкін:
S жиынындағы бинарлы қатынастар. S жиыны және солардың (яғни, X=Y=S) арасындағы бинарлы қатынас S жиынындағы қатынас деп аталады. Бұл түсініктің маңызды жеке жағдайы болып S-қа e теңдігінің қатынасы: x=y табылады. Анық, n жиыныда оған бірлік матрица жауап береді: егер i=j болса, 1 I = ║δij║, мұндағы δij = 0, егер i≠j. Бұл квадратты n×n – басты диагоналінде бірліктері бар және қалған жерлерде нөлдері бар матрица. Aнықтамасы S жиынында кез келген екі композиция бар екенін көрсетеді. e теңдігінің қатынасы барлық α үшін eα = αe = α шартын қанағаттандырады. Сонымен, кез келген S-тағы α, β, γ қатынастары үшін α(βγ) = (αβ)γ ассоциативтілік заңы дұрыс. (2.1) Ақикатымен де, екі тұжырым да x[α(βγ)]y және x[(αβ)γ]y сай келетін элементтері z1 , z2 Î S үшін xαz1 , z1βz2 және z2γy тұжырымдары орын алатынын көрсетеді. Айтылғанды түсіндіреміз: Теорема 2. S жиынындағы бинарлы қатынастар композицияға қатысты ассоциативті және бірлік ретінде теңдік қатынасы бар алгебралық жүйені құрайды. f: S→S функциялар жиыны осындай қасиеттерге ие, бұндай жүйелер моноидтар деп аталған еді (моноидтерді 7 тарауда оқитын боламыз). Сонымен, 2 теореманы келесі түрде қайта тұжырымдауға болады: Салдар. Кез келген жиындағы бинарлы қатынастар композицияға қатысты моноидті құрайды. S-та көптеген маңызды бинарлы қатынастар бар. Егер xαx барлық xÎS үшін болса, онда α қатынасы рефлексивті деп аталады. Егер xαx қандай да бір х үшін болса, α қатынасы иррефлексивті деп аталады. Егер xαy-дан yαx екені шықса, α қатынасы симметриялы деп аталады, керісінше жағдайда – антисимметриялы деп аталады. Егер x=y болса, онда xαy-тан yαx шығатыны анық; керісінше, егер xαy –тан және yαx-тан y=x екендігі шығады, α қатынасы антисимметриялы деп аталады. Біз жиындар арасындағы қосылу қатынасы рефлексивті және антисимметриялы екенін көрдік. Сондықтан қатынастар арасындағы қосылу қатынасы да осындай. S жиынындағы α бинарлы қатынасы транзитивті деп аталады, егер xαy және yαz (x, y, zÎS)-тен xαz екендігі шықса. Дербес жағдайда, жиындар арасындағы қосылу операциясы Ì транзитивті. Теңдік қатынасы e (яғни =) рефлексивті, симметриялы және транзитивті. Айталық, мысалы, T = {1,2,3} S(α) = {(1,1) (1,2) (2,1) (2,2) (2,3) (3,2) (3,3)} графиктің Т-ға қатынасы. Бұл қатынас рефлексивті және симметриялы, бірақ транзитивті емес, әйтпесе 1α2 және 2α3 , бірақ 1α'3 болады. Ескерейік, α2 қатынасының S(α2) графигі T×T-мен сәйкес келеді. Осылайша, α2 – барлық T-да: барлық x,yÎТ үшін xα2y орындалатын қатынас. Жоғарыда берілген анықтамаларды енгізілген қатынастар терминдерінде қайта тұжырымдауға болады. S-тағы α бинарлы қатынасы теңдік қатынасын e (e £ α) қамтыса, немесе e Ù α = e және e Ú α = α болғанда сол сияқты болса, сонда, тек қана сонда рефлексивті болады. Ол α = α˘. болғанда, тек қана осы жағдайда симметриялы болады. Ол α Ù α' £ e болғанда, тек қана осы жағдайда антисимметриялы болады. Ол α2 £ α болғанда, тек қана осы жағдайда транзитивті болады (мұндағы α2, әрине, αα болады). Дәлелдеулерді қалдырып кетеміз. Егер S = n болса, S-қа қатынастың рефлексивтілігі осы қатынастың матрицасының барлық диагональ элементтері бірге тең екенін білдіреді. α қатынасы оның матрицасы ║aij║ симметриялы болған жағдайда ғана және тек осы жағдайда симметриялы болады. (яғни, барлық i,j үшін aij = aji). Сонымен, функцияның декарттық көбейтіндісінің түсінігі қатынасқа келесі түрде жалпыланады. Айталық, α,β - A және Y жиындары арасындағы бинарлы қатынас, ал β - B және Y арасындағы. Декарттық (немесе тензорлы) көбейтіндіні γ = α×β A×B және Ү жиындары арасындағы қатынас ретінде анықтайық. Және мынадай түрде (a,b) γy aαy және bβy екенін білдіреді Тура осылайша, айталық ξ – А және X жиындары арасындағы бинарлы қатынас, η- A және Y жиындары арасындағы бинарлы қатынас. ζ = ξ×η қатынасын келесі түрде анықтайық: aζ (x,y) aξx және aηy екенін білдіреді. Үй жұмысы: Бинарлық қатынас бұл қандай қатынас? Бинарлық қатынасының оң жақ облысы дегеніміз? S жиынындағы бинарлы қатынастар жүктеу/скачать 26,37 Kb. Достарыңызбен бөлісу:
|