Алгебра отношений

Лекция Алгебра отношений. Отношение порядка Мы определили бинарное отношение частичного порядка R на M как рефлексивное, транзитивное и антисимметричное отношение. Если это отношение R еще и антирефлексивно, то оно называется отношением строгого порядка. Определение Если отношение частичного порядка R является полным, то оно называется отношением полного (или линейного) порядка. В общем случае отношение порядка будем обозначать через . Примеры отношений порядка. (Z,<) – отношение строгого полного порядка. (Z,) – отношение нестрогого полного порядка. (2M,) отношение нестрогого частичного порядка. Отношение доминирования Определение Для двух элементов x и y, по определению, будем считать, что они находятся в отношении доминирования ассоциированным с отношением порядка < (будем обозначать это через x строго меньше y и не существует такого элемента z, что x  z  y. Если имеет место x доминирует над элементом x. y ), т.и т.т., когда x y , то говорят, что элемент y Очевидно, что отношение доминирования иррефлексивно, антисимметрично, и не транзитивно. Оно также может быть и пусто. Примеры. 1) Рассмотрим множество действительных чисел с естественным числовым порядком. Пусть a  c . Известно, что для любых a и c найдется такое b, что a  b  c, то есть для R это отношение доминирования будет пустым. Но на множестве целых чисел (с тем же самым естественным числовым порядком) отношение доминирования не пусто. Так, 1 2 , 4 5 , то есть для любого n, n n 1. 2) На множестве всех подмножеств трехэлементного множества {a, b, c} c отношением теоретико-множественного включения , подмножество {a, b} доминирует над одноэлементными подмножествами {a} и {b} , но не доминирует над пустым множеством. В свою очередь, все множество {a, b, c} доминирует над любым своим двухэлементным подмножеством, но не доминирует ни над одноэлементным, ни над пустым. Минимальные и максимальные элементы Определение. Элемент x множества M, на котором определено отношение порядка , называется минимальным, если (y  M )[ y>x & y  x]. Другими словами, x– максимальный элемент множества X, если не существует элементов множества, строго предшествующих ему. Пример. 1)  - минимальный элемент в (2M,). 2) Рассмотрим множество натуральных чисел от 2 до 10 и отношение делимости: ({2,,…,10}, ). Минимальные элементы: 2,3,5,7. Определение. Элемент x множества M, на котором определено отношение порядка , называется наименьшим, если (y  M )[ y  x & x y] . Другими словами, x – наименьший элемент множества X, если все другие элементы строго следуют за ним. Пример. 1)  - наименьший элемент в (2M,). 2) 1 – наименьший элемент в (N, ). Имеют место и аналогичные (симметричные) максимального и наибольшего элементов. определения для Определение. Элемент x множества M, на котором определено отношение порядка , называется максимальным, если (y  M )[x< y & y  x]. Другими словами, x– максимальный элемент множества X, если не существует элементов множества, строго следующих за ним. Определение. Элемент x множества M, на котором определено отношение порядка, называется наибольшим, если (y  M )[ y  x & y, где:  булеан Р(Х) ={∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}};  строгий порядок на Х определен отношением доминирования, ассоциированным с отношением ⊆ Диаграмма Хассе будет выглядеть следующим образом (Рисунок 3): Рисунок 3 - На рис 3 –наименьший и минимальный элемент – ∅, наибольший и максимальный элемент – множество {a, b, c}. Задание Построить диаграммы Хассе для упорядоченных множеств делителей чисел 36, 48 и 49 по отношению делимости. Найти их наименьшие (наибольшие) элементы (если они существуют) и минимальные (максимальные элементы).