Отношения

Лекции по Дискретной математике Лекция 3 Отношения Отношение как частный случай соответствия Подмножество n-ой степени множества называется n-местным отношением на этом множестве. R An (a1, a2, …, an)R  R(a1, a2, …, an)  a1 R a2 R … R an ВИДЫ ОТНОШЕНИЙ: R={a|aA} 1-местное - подмножество R={(a1,a2)|a1,a2A} 2-местное – бинарное отношение R={(a1,a2,a3)|a1,a2,a3A} 3- местное – тернарное отношение R={(a1, …, an|a1,…,anA} n-местное – n-арное отношение ТИПЫ ОТНОШЕНИЙ: Обратное отношение Дополнение отношения Тождественное отношение Универсальное отношение -1 R ={(a,b)| (b,a)R} R= {(a,b)|(a,b)R} I= {(a,a)|aA} U= {(a,b)|a,bA} Примеры отношений M={1, 2, 4, 16, 256} RMM, где R={(a,b)| a=b*b} |M|=5, |M M|=25 R={(1,1); (4,2); (16,4); (256,16)} |R|=4 ОСТАЛЬНЫЕ ТИПЫ ОТНОШЕНИЙ: Обратное отношение Дополнительное отношение -1 R ={(1,1); (2,4); (4,16); (16, 256)} R= {(1,2); (1,4); (1,16); (1,256); (2,1); (2,2); (2,4); (2,16); (2,256); (4,1); (4,4); (4,16); (4,256); (16,1); (16,2); (16,16); (16,256); (256,1); (256,2); (256,4); (256,256)} Способы задания отношений RVV, где V={мама, папа, сын, соседи, друзья} n Список R={(мама, мама); (мама, папа); (папа, мама); (папа, папа); (мама, сын); (сын, сын); (сын, мама); (папа, сын); (сын, папа)} n Характеристический предикат R={(a,b)| «a родственник b»} Способы задания отношений RVV, где V={мама, папа, сын, соседи, друзья} мама n Диаграмма папа сын соседи друзья мама папа сын соседи друзья Способы задания отношений RVV, где V={мама, папа, сын, соседи, друзья} мама папа сын мама 1 1 1 папа 1 1 1 сын 1 1 1 соседи 1 друзья 1 n Матрица R[i,j]= . 1, если a i Ra j 0, если a i Ra j соседи друзья Свойства отношений n рефлексивность. (aA) aRa. n антирефлексивность. (aA) (aRa). n симметричность. (a,bA) (aRbbRa). n антисимметричность.(a,bA) (aRb=bRaa=b). n транзитивность. (a,b,cA) (aRbbRcaRc). n полнота (линейность).(a,bA)(a≠baRbbRa). Теорема 1 о матрицах отношений n Матрица композиции двух отношений равна произведению матриц этих отношений. R1R2 k = R1 * R2 следствие : R = R k Теорема 2 о матрицах отношений n Элементы матрицы объединения отношений совпадают с большим элементом из матриц этих отношений. R1R2 = R1  R2 Отношение порядка n Антисимметричность (a,bA) (aRb=bRaa=b) n Транзитивность (a,b,cA) (aRbbRcaRc) n рефлексивность n антирефлексивность (aA) aRa (aA) aRa нестрогий порядок строгий порядок n полнота (a,bA)(a≠baRbbRa). полный порядок Обозначение порядка ( x, y ) R xp y M={1, 2, 4, 16, 256} RMM R={(a,b)| a>b}: М={256, 16, 4, 2, 1} R={(a,b)| aab≠a а - максимальный элемент Упорядочивание комплекта RVV, где V={2, 3, 4, 5, 3, 1, 7, 9, 2, 3, 5, 9, 2, 2} R={(a,b)| a<=b} V={1, 2, 2, 2, 2, 3, 3, 3, 4, 5, 5, 7, 9, 9} 1 – минимальный элемент 9 – максимальный элемент Отношение эквивалентности n Рефлексивность n Симметричность отношение эквивалентности n Транзитивность . ОБОЗНАЧЕНИЕ a b или a ~ b Примеры эквивалентности n a=b равенство выражений n (а+с)(а-с)а - с 2 2 равносильность выражений n  ABC ~  MNK подобие треугольников Фактормножество R  AA (aА) (А1А) А1 = {y | yA, y~a}. A1 – класс эквивалентности элемента a по отношению R [a] = A1 Множество всех классов эквивалентности называется фактормножеством множества А по эквивалентности R и обозначается А/R={[x]| xA}. Пример фактормножества S={Уфа, Жилино, Белебей, Анновка, Приютово, Аксаково, Кумертау, Ира, Маячный, Шарипово, Мамяково} R={(x,y)| x и y одной районной принадлежности} [Уфа] = [Жилино] = {Уфа, Жилино} [Белебей]=[Анновка]=[Приютово]=[Аксаково]= {Белебей, Анновка, Приютово, Аксаково} [Кумертау]=[Ира]=[Маячный]= {Кумертау, Ира, Маячный} [Шарипово]=[Мамяково]={Шарипово, Мамяково} Пример фактормножества n [Уфа]=[Жилино]={Уфа, Жилино} n [Белебей]=[Анновка]=[Приютово]=[Аксаково]={Белебей, Анновка, Приютово, Аксаково} n [Кумертау]=[Ира]=[Маячный]={Кумертау, Ира, Маячный} n [Шарипово]=[Мамяково]={Шарипово, Мамяково} S/R={{Уфа, Жилино}, {Кумертау, Ира, Маячный}, {Белебей, Анновка, Приютово, Аксаково}, {Шарипово, Мамяково}} Леммы о классах эквивалентности n ЛЕММА 1. (aА) [а]~ ≠. n Лемма 2. a~b[a]~[b] n ЛЕММА 3. a ~ b[a][b]= .