Прямое произведение множеств. Соответствия. Операции над соответствиями

a, b - упорядоченная пара (кортеж длины 2) a, b, c ,... x1, x2 ,...,xn  A  B  a, b | a  A и b  B - декартово (прямое) произведение A  1,2 B  a, b A B  B  A a, b  b, a  A  B  (1, a), (2, a), (1, b), (2, b) A1  A2  ... An   x1, x2 ,..., xn  | x1  A1, x2  A2 ,..., xn  An A  A  A2 n A  A  ...  A  A A  O декартова степень     n раз Теорема. A  B  A  B An  A n (Доказательство самостоятельно) P  A1  A2  ... An n 1 P A n2 P  A B n – местное отношение (предикат) унарное отношение (свойство, признак) бинарное отношение (соответствие) A  2,3,4,5,6,7,8 P  ( x, y) | x, y  A, x  y делится на 3, x  5 P  2,4, 2,7, 3,3, 3,6, (4,2), 4,5, 4,8 Q  ( x, y) | x, y  R, x  y Q  R 2 , , , ,  P  A2 2 1 (1,2) (2,1) 1 2 R  R  R2 Блок-схема ЭВМ фон Неймана M  a, b, c, d , e a – устройство ввода, b – арифметическое устройство (процессор), с – устройство управления, d – запоминающее устройство, e – устройство вывода T – отношение информационного обмена T  M2 T  (a, b), (a, c), (a, d ), (b, c), (b, d ), (b, e), (c, a), (c, b), (c, d ), (c, e), (d , b), (d , c), (d , e), (e, c)   A B , A, B  A  2,3,4,5,6,7,8  - график соответствия A – область отправления B – область прибытия P  A2 P  2,4, 2,7, 3,3, 3,6, (4,2), 4,5, 4,8    x | y  B, ( x, y)   - область определения   y | x  A, ( x, y)   - область значений  P  2,3,4  P  2,3,4,5,6,7,8 Представление соответствий 2. Диаграмма 1. Графический способ 2 3 4 5 6 7 8 y 8 6 4 2 2 3 4 x 2 3 4 5 6 7 8 2 3 4 5 6 7 8   A2 граф G  M ,  P  2,4, 2,7, 3,3, 3,6, (4,2), 4,5, 4,8 1. Тождественное отношение (диагональ, рефлексия) id A  (a, a) | a  A id A  A2 2. Универсальное отношение U  A B 3. Пустое отношение O   A B 1, ai , b j  ,  i, j   0, ai , b j  . 3. Матрица       2 3 4 5 6 7 8 2 0 0 1 3 0 1 0 P  4 1 0 0 5 0 0 0 6 0 0 0 7 0 0 0 1 1 1 1 0 0 0 0 8 0 0 0 0 0 0 0 Операции над бинарными отношениями 1. Объединение 3. Дополнение 0    1 0 1    0 0 1 0 1 0  0 1 1 1 0 1  1 1        0      1 0 0      1 0 4. Обратное отношение A  2,3,4,5,6,7,8 1 0 1 1 0   0   0 1 0 1 0 1 1 0   0   0 1 0 1 1 0 0 1  0   1 1 0 1 1 1 0 1  1   1 1 0 1  (b, a) | (a, b)   P  A2 P  2,4, 2,7, 3,3, 3,6, (4,2), 4,5, 4,8 1 0 0 0  0 1 1 1 1 1  1 1 1 0 1   0 0 1 1 1 0 1 T 1 0  1 1 0 0 1  1 1 1 P 1  4,2, 7,2, 3,3, 6,3, (2,4), 5,4, 8,4 5.   A B, С  A, D  B       2. Пересечение (C,D)-ограничение Г  C , D  ( x, y) | ( x, y)  , x  C , y  D,  C , D    C  D  С  2,3, D  4,6,8, P C , D  (2,4), (3,6) (C,B)-ограничение Г – C-сужение P C  (2,4), (2,7), (3,3), (3,6) 6. Композиция соответствий   A B,   BC     a, c  | (a, b)  , (b, c)   A  a1, a2 , a3, B  b1, b2 , b3, С  с1, с2 , с3   (a1, b2 ), (a2 ,b1), (a2 , b2 ), (a3, b3 )   (b1, c1), (b1,c2 ), (b1, c3 ), (b2 , c3 ), (b3, c2 ), (b3, c3 ) a1 a2 a3      (a1, c3 ), (a2 , c1), (a2 , c2 ), (a2 , c3 ), (a3 , c2 ), (a3 , c3 ) 0 1 0 1 1 1      1 1 0  0 0 1  0 0 1 0 1 1 Свойства композиции 1) P  Q 1  Q 1  P 1 2) P  Q  S   P  Q   S 3) P  Q  S   P  Q   P  S  4) P  Q  S   P  Q   P  S  0 0 1 1 1 1   0 1 1  I  I    O  O   O     ...   n   n 0  I    b1 b2 b3  c1 c2 c3   A B. a  A (a)  y | (a, y)   7. Сечение соответствия Г по элементу P  2,4, 2,7, 3,3, 3,6, (4,2), 4,5, 4,8 P(3)  3,6 A  2,3,4,5,6,7,8 P  A2 Сечение соответствия Г по множеству ( X )  y | ( x, y)  , x  X  XA X  3,4 P(X )  2,3,5,6,8- образ множества X M / Фактор-множество множества M по отношению Г a 3 4 5 6 7 8  2 P (a ) 4,7 3,62,5,8O O O O  A / P  4,7 ,3,6 ,2,5,8, O  P 1( X )  2,3 - прообраз множества X P 1  4,2, 7,2, 3,3, 6,3, (2,4), 5,4, 8,4 8. Проекция соответствия Г 1  a | a, b    1P  2,3,4  2  b | a, b     2P  3,4,5,6,7,8    iR,ni ,...,i  ai1 , ai2 ,...,aim | a1, a2 ,...,an   Rn 1 2 m V  a, b, d , c, b, d , d , b, b 1V  a, c, d  V 2,3  (b, d ), (b, b) V 2  b  Свойства соответствий   A2 (отношений) 1) Рефлексивность a  A (a, a)   2) Антирефлексивность a  A (a, a)   3) Симметричность a, b  A (a, b)    (b, a)   4) Антисимметричность a, b  A (a, b)  , (b, a)    a  b 5) Транзитивность a, b, c  A (a, b)  , (b, c)    (a, c)   1) нерефлексивно 0 1 1  P  0 1 1 2) неантирефлексивно 3) несимметрично 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 P PT  0 1 1  1 1 0  0 1 0  0 1 0  I  0 0 0 1 1 0 0 0 0 0 0 1 0 1 1  0 1 1   0 1 1  P  P  0 1 1  0 1 1  0 1 1  P 0 0 0 0 0 0 0 0 0    1  I    4) антисимметрично 5) транзитивно 2) неантирефлексивно 1) x  R x  x рефлексивно 4) антисимметрично  y  x несимметрично 3) x, y  R x  y  5) x, y, z  R x  y, y  z  x  z транзитивно a, b  A, a  b, (a, b)   с  A(с  a, c  b) : (a, с)  , (с, b)   6) Плотность  R 2 - плотно  N 2 - неплотно  R 2 Классы отношений 1) Эквивалентность - рефлексивное, симметричное, транзитивное отношение 2) Толерантность - рефлексивное, симметричное отношение 3) Нестрогий порядок - рефлексивное, антисимметричное, транзитивное отношение 4) Строгий порядок - антирефлексивное, антисимметричное, транзитивное отношение 5) Нестрогий предпорядок - рефлексивное, транзитивное отношение 6) Строгий предпорядок - антирефлексивное, транзитивное отношение Соответствие рефлексивное симметричное отношение толерантности транзитивное симметричное отношение эквивалентности рефлексивное транзитивное антирефлексивное транзитивное отношение нестрогого предпорядка отношение строгого предпорядка антисимметричное отношение нестрогого порядка антисимметричное отношение строгого порядка Отношения эквивалентности (рефлексивное, симметричное, транзитивное) Отношение подобия на множестве Отношение равномощности множеств треугольников A  B  B  A, A  A, ABC ~ ABC, A  B, B  C  A  C ABC ~ XYZ  XYZ ~ ABC, ABC ~ XYZ , XYZ ~ KLM  ABC ~ KLM  M2 x  M x  y | y  M , y ~ x - класс эквивалетности Теорема: Для любого отношения эквивалентности на множестве M множество классов эквивалентности образуют разбиение множества M. Любое разбиение множества M задает на нем отношение эквивалентности, для которого классы эквивалентности совпадают с элементами разбиения. свойства классов эквивалентности:  a  a 1) a  M a  O Подобная матрица п  2) a ~ b  a  b  3) a ~ b  a  b  O Отношение толерантности (рефлексивное, симметричное) пример Ю.А. Шрейдера муха –мура – тура – тара – кара – каре - кафе – кафр – каюр – каюк – крюк – крок – срок – сток – стон - слон граничащие области на карте Задача минимизации объема оперативной памяти {a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15, a16} 2 a1 a5 a5 1 a4 a2 a3 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15 a16 a6 a7 3 4 5 a8 a9 схема программы 6 a6 7 a12 a6 8 a10 a11 a15 10 a16 9 a 14 a13 (ai , a j )  Rсц  T (ai )  T (a j )  O (ai , a j )   Rсц  (ai , a j )  Rсц a1 a2 a3 a4 a5 a6 a7 a8 a9 Rсц  a10 a11 a12 a13 a14 a15 a16   (схема потока данных) (А.П.Ершов, Г.И. Кожухин) {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 1 1 1  1 1 1    1 1 1 1 1 1 1 1 1    1 1 1     1 1 1   1 1 1 1 1 1 1 1 1 1 1     1 1 1 1 1   1 1 1 1 1     1 1 1 1 1   1 1 1 1 1     1 1 1 1 1   1 1 1 1 1     1 1 1 1 1   1 1 1    1 1 1    1 a1 1 a2  a3  a4 1  a5 1 Rсц  a6 1 a7 1 a8 1 a9 1  a10 1 a11 1  a12 1 a13 1  a14 1 a15 1 a16 1   1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 a1 1 a4 1 a6 1 a2   a5 1 Rсц п  a7 1 a10 1 a3  a11 1  a14 1 a8 1  a12 1 a15 1  a9 1 a13 1 a16 1   1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  1 1 1 1 1  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 K1  a1, a4 , a6 K2  a2 , a5 , a7 , a10 K3  a3 , a11, a14 K4  a8 , a12 , a15 K5  a9 , a13 , a16 Отношения порядка антисимметричное, транзитивное   {( x, y) | x  y}   R2 x, y  R x  y  y  x x, y, z  R x  y, y  z  x  z рефлексивное - нестрогое x  R x  x антирефлексивное - строгое   U 2 X  2U   {( X , Y ) | X  Y }  2 X , Y  2U X Y Y   X XX X , Y , Z  2U X  Y ,Y  Z  X  Z  M2 M – упорядоченное множество - полный (линейный) порядок - неполный (частичный) порядок a  M x  M x  a наибольший элемент b M x  M x  b либо они не сравнимы максимальный элемент a  M x  M a  x наименьший элемент минимальный элемент b M x  M b  x либо они не сравнимы нижняя граница для Х X M - наибольшая inf(X) - инфимум a [ a, b)  R m M : x  X нижняя граница [a, b),  b наименьший a, наибольшего нет множество нижних граней (, a], a = inf([a,b)) множество верхних граней [b,), b = sup([a,b)) mx верхняя граница для Х x  X m M : xm sup(X) - супремум - наименьшая верхняя граница C  ( x, y) | x  R, y  R С ,  (a, b)  (c, d )  a  c, b  d максимальные элементы A A D С AOBD  C С AOB  C O B O(0,0)-наименьший 2 A,  A  {a, b, c} O F E O = inf(CAOBD) A D = sup(CAOBD) O B B D С ABDE  C O = inf(CABDE) F = sup(CABDE) элемент - отношение частичного нестрого порядка 2 A  a, b, c,{a, b},{a, c},{b, c},{a, b, c}, O  Посет – частично упорядоченное множество {a, b, c} a, b a, с a b O {a, b, c} a, с b, с a, b с a b b, с с O Диаграмма Хассэ