Дискретная математика

18 Яа множествах Л и С такое, что; (a,c)e(R °S)<i> 3 ЬфеВ и (a,b}eR и ф,с)е8). Если R определено на Л, В, а S на С, D, ВпС=0, то R °S не определено. Свойства операций над отношениями. Для пересечения, объединения и дополнения отношений справедливы все свойства, установленные ранее (см. равенства 1)-19) в теореме 1.1). Кроме того, можно доказать следующие свойства; 1) R, °(R2°R3)=(Ri°R2)°R3 - ассоциативность композиции; 2) (R,oR2)-'='Ri'oR,-'; 3) C(R-')=(CR)-'; 4) (R,uR2)-'=R{'UR2-'\ 5) (R,nR2)-'^Rf'nR2'- 6) RI °(R2UR})-(RioR2) U(RI°R3)\ 7) еслиЛ/С-йг, тоЛ/'с-Яг"'. Свойства отношений на множестве А. Бинарное отношение R на множестве А называется: 1) рефлексивным, если для VaeA (a,a}eR\ 2) антирефлексивным (иррефлексивным), если для VasA (a,a}0R; 3) сшшетртным, если из ^, У ) ЕК следует, что (y,x)eR\ 4) антисимметричным, если из <^,y}eR и (y,x)eR следует, что х=у; 5) транзитивньш, если из {x,y)eR и (y,z} £R следует, что {x,z}eR. Теорема 1.2. Пусть R - бинарное отношение шА. Тогда: 1) 7? рефлексивно <^EcR-, 2) R антирефлексивно cs>RnE=0, 3) R симметрично <=>R=R''\ 4) антисимметрично <i>Rr)R''=E\ 5) транзитивно oR °R=R. Доказательство: Рассмотрим утверждение 1). Необходимость условия: если R рефлексивно, то для VasA имеет место (a,a)eR, отсюда следует, что £ сЛ . Достаточность условия; пусть EcR, тогда для VaeA имеем (a,a)eR, а это и означает, что R рефлексивно. Рассмотрим утверждение 2). Необходимость докажем от противного. Пусть Яг)Е^0, тогда найдется а что (a,a}eR и (а,а)еЕ, но этого не может быть, ибо для VaeA имеем (a.a}gR. Итак, RnE=0. Достаточность. Пусть Кг)Е=0. Это означает, что не существует аеА, что (a,a)eR и (а,а}еЕ. Тогда для любогоа еЛ выполняется (u,a)gR. что и требовалось. Аналогично доказываются утверждения 3) - 5).