ДИСКРЕТНАЯ МАТЕМАТИКА (1). В. А. Ломазов р рязанов, Ю. Д. Дискретная математика учеб пособие. Ю. Д. Рязанов е изд, доп. Белгород Издво бгту, 2016. 298 с
 Скачать 4.33 Mb.
|
|
3.2. Способы задания отношений 1. Перечислением всех упорядоченных пар, принадлежащих отношению. A = {(1,2),(1,3),(3,1)}, B = {(3,1),(2,1),(1,3)} , C = Из определения равенства множеств вытекает, что A = C и A B. 2. Заданием характеристического свойства, выделяющего упорядоченные пары данного отношения среди упорядоченных пар других отношений и y N и x 10 и y < 10 и x — четно и y — нечетно. 3. Описанием порождающей процедуры с указанием множества (или множеств, которое пробегает параметр (или параметры) этой процедуры. Пару (x,y) можно изобразить точкой на координатной плоскости с абсциссой x и ординатой y, а бинарное отношение А — множеством точек, называемым графиком отношения А. График отношения A = {(1,2), (1,3),(3,1)} представлен на рис y Рис. График отношения 2 1 122 5. Бинарное отношение А можно представить в графической форме в виде графа, в котором вершины (кружочки или точки) соответствуют элементам множества и если (x,y) A, то вершины, соответствующие и y, соединяются дугой (стрелочкой) от x к y. Если же (x,y) A и (y,x) A, то вершины, соответствующие x и y соединяются ребром (линией, не имеющей направления. Граф отношения A = {(1,2),(1,3),(3,1)} представлен на рис 1 2 3 Рис. Граф отношения 6. Бинарное отношение А можно задать характеристической функцией А, которая принимает истинное значение, если (x,y) A и ложное — в противном случае. Характеристическую функцию отношения наконечном множестве мощностью N можно представить матрицей размером N N. Матрица характеристической функции отношения представлена на рис 0 0 1 0 0 0 1 Рис. Матрица характеристической функции отношения 3.3. Операции над отношениями 1. Включение А в В (А Вили В А) истинно, если каждая упорядоченная пара (x,y) отношения А принадлежит отношению В. 2. Равенство Аи В (А = В) истинно, если отношения Аи В состоят из одних и тех же упорядоченных парили если А В и В А. 3. Строгое включение А в В (А Вили В А) истинно, если А В и А В. 4. Объединение Аи В (А Весть отношение, состоящее из всех тех и только тех упорядоченных пар, которые принадлежат А или В, те. А Вили. Пересечение Аи В (А Весть отношение, состоящее из всех тех и только тех упорядоченных пар, которые принадлежат каждому из отношений Аи В, те. А В = {(x,y) | (x,y) A и (x,y) B}. 6. Разность Аи В (А – Весть отношение, состоящее из всех тех и только тех упорядоченных пар отношения А, которые не принадлежат отношению В, те. А – В = {(x,y) | (x,y) A и (x,y) B}. 7. Симметрическая разность Аи В (А Весть отношение, состоящее из всех тех и только тех упорядоченных пар отношения А, которые не принадлежат отношению В и только тех упорядоченных пар отношения В, которые не принадлежат отношению А, те. А В = {(x,y) | (x,y) A и (x,y) B или (x,y) В и (x,y) А. 8. Дополнение А до универсального отношения U ( A ) есть отношение, состоящее из всех тех и только тех упорядоченных пар универсального отношения U, которые не принадлежат отношению А, те. A = {(x,y) | (x,y) А. Операции 1 — 8 над отношениями аналогичны операциям надмножествами. Обращением А (А) называется отношение, которое состоит из всех тех и только тех упорядоченных пар (x,y), для которых (y,x) принадлежит отношению А, те. А = {(x,y) | (y,x) A}. 10. Композицией (суперпозицией или умножением) Аи В (А В) называется отношение, состоящее из всех тех и только тех упорядоченных пар (x,y), для которых найдѐтся хотя бы один элемент z такой, что (x,z) A и (z,y) B, те. А В = {(x,y) | существует z такой, что (x,z) A и (z,y) B}. 11. Степенью отношения А называется его композиция с самим собой А = I, А = А, А = А А, А = А А n-1 Пара (x,y) принадлежит отношению А , если в графе отношения А есть цепочка из n дуг (ребер, соединяющая вершину x с вершиной y. Отношения часто встречаются в математике ив повседневной жизни. К математическим отношениям на множестве целых чисел можно отнести отношение МЕНЬШЕ, представляющее собой множество таких упорядоченных пар, в которых первый элемент меньше второго. Характеристическим свойством это отношение можно задать так МЕНЬШЕ = {(x,y) | x < y }. По аналогии определим отношения БОЛЬШЕ, РАВНО, НЕРАВНО, МЕНЬШЕ ИЛИ РАВНО, БОЛЬШЕ ИЛИ РАВНО БОЛЬШЕ = {(x,y) | x > y } РАВНО = {(x,y) | x = y } НЕРАВНО = {(x,y) | x ≠ y } МЕНЬШЕ ИЛИ РАВНО = {(x,y) | x y } БОЛЬШЕ ИЛИ РАВНО = {(x,y) | x ≥ y } В результате выполнения операций над этими отношениями будем получать новые отношения. МЕНЬШЕ РАВНО = МЕНЬШЕ ИЛИ РАВНО МЕНЬШЕ ИЛИ РАВНО БОЛЬШЕ ИЛИ РАВНО = РАВНО МЕНЬШЕ ИЛИ РАВНО БОЛЬШЕ ИЛИ РАВНО = НЕРАВНО МЕНЬШЕ ИЛИ РАВНО – РАВНО = МЕНЬШЕ МЕНЬШЕ = БОЛЬШЕ МЕНЬШЕ = БОЛЬШЕ ИЛИ РАВНО РАВНО = РАВНО РАВНО = НЕРАВНО МЕНЬШЕ МЕНЬШЕ = МЕНЬШЕ 2 Отношение МЕНЬШЕ можно назвать МЕНЬШЕ КАК МИНИМУМ НА ДВА (почему. Теперь рассмотрим некоторые родственные отношения на множестве людей. Отношение ЖЕНА представляет собой множество таких упорядоченных пар, в которых первый человек является женой второго человека. Характеристическим свойством это отношение можно задать так ЖЕНА = {(x,y) | x — жена y }. По аналогии определим другие родственные отношения. Далее представим результаты выполнения операций над такими отношениями. ЖЕНА = МУЖ МАТЬ ОТЕЦ = РЕБЕНОК МАТЬ (МАТЬ ОТЕЦ) = БАБУШКА ОТЕЦ (МАТЬ ОТЕЦ) = ДЕД СЫН (СЫН ДОЧЬ ВНУК МАТЬ ЖЕНА = ТЕЩА РЕБЕНОК – СЫН = ДОЧЬ МАТЬ ОТЕЦ = РОДИТЕЛЬ ЖЕНА ОТЕЦ = МАТЬ ИЛИ МАЧЕХА СЫН (МАТЬ ОТЕЦ) = БРАТ 125 3.4. Алгоритмы реализации операций над отношениями Бинарное отношение R на множестве A будем задавать характеристической функцией R(x,y), представленной матрицей R размером N N, где N = |A| и R x,y принимает истинное значение, если (x,y) R и ложное — в противном случае. Для хранения матрицы будем использовать двумерный массив R с элементами типа boolean. Алгоритм 3.1 (рис) вычисления равенства отношений Аи В А = В. Вход А — двумерный массив, хранящий матрицу отношения А B — двумерный массив, хранящий матрицу отношения B; N — мощность множества. Выход F = true, если А = В, иначе F = false. Рис. Блок-схема алгоритма вычисления равенства отношений F:=true; x:=1 x N и F=true F:=A x,y = B x,y ; y:=y+1 A=B y:=1 y N и F=true Конец x:=x+1 126 Алгоритм 3.2 (рис) вычисления включения отношения А в В А В. Вход А — двумерный массив, хранящий матрицу отношения А B — двумерный массив, хранящий матрицу отношения B; N — мощность множества. Выход F = true, если А В, иначе F = false. Рис. Блок-схема алгоритма вычисления включения отношения А в В x:=1 x N и F=true F:=A x,y B x,y ; y:=y+1 A B y:=1 y N и F=true Конец x:=x+1 127 Алгоритм 3.3 (рис) вычисления объединения отношений Аи В А В. Вход А — двумерный массив, хранящий матрицу отношения А B — двумерный массив, хранящий матрицу отношения B; N — мощность множества. Выход С — двумерный массив, хранящий матрицу объединения Аи. Рис. Блок-схема алгоритма вычисления объединения отношений Алгоритм 3.4 (рис) вычисления пересечения отношений Аи В А В. Вход А — двумерный массив, хранящий матрицу отношения А B — двумерный массив, хранящий матрицу отношения B; N — мощность множества. Выход С — двумерный массив, хранящий матрицу пересечения Аи. Рис. Блок-схема алгоритма вычисления пересечения отношений y:=1,N Конец C x,y := A x,y and B x,y А В C x,y := A x,y or B x,y x:=1,N y:=1,N Конец А В 128 Алгоритм 3.5 (рис) вычисления разности отношений Аи В А – В. Вход А — двумерный массив, хранящий матрицу отношения А B — двумерный массив, хранящий матрицу отношения B; N — мощность множества. Выход С — двумерный массив, хранящий матрицу разности Аи. Рис. Блок-схема алгоритма вычисления разности отношений Алгоритм 3.6 (рис) вычисления симметрической разности отношений Аи В (А В. Вход А — двумерный массив, хранящий матрицу отношения А B — двумерный массив, хранящий матрицу отношения B; N — мощность множества. Выход С — двумерный массив, хранящий матрицу симметрической разности Аи. Рис. Блок-схема алгоритма вычисления симметрической разности отношений y:=1,N Конец C x,y := A x,y xor B x,y А В C x,y := A x,y > B x,y x:=1,N y:=1,N Конец А – В 129 Алгоритм 3.7 (рис) вычисления дополнения отношения А ( A ). Вход А — двумерный массив, хранящий матрицу отношения А N — мощность множества. Выход С — двумерный массив, хранящий матрицу дополнения А. Рис. Блок-схема алгоритма вычисления дополнения отношения Алгоритм 3.8 (рис) вычисления обращения отношения А (А. Вход А — двумерный массив, хранящий матрицу отношения А N — мощность множества. Выход С — двумерный массив, хранящий матрицу обращения А. Рис. Блок-схема алгоритма вычисления обращения отношения y:=1,N Конец C x,y := A y,x А not A x,y x:=1,N y:=1,N Конец A A A А-В 130 Алгоритм 3.9 (рис) вычисления композиции отношений Аи В А В. Вход А — двумерный массив, хранящий матрицу отношения А B — двумерный массив, хранящий матрицу отношения B; N — мощность множества. Выход С — двумерный массив, хранящий матрицу отношения А B. Рис. Блок-схема алгоритма вычисления композиции отношений Алгоритм вычисления композиции (произведения) отношений представляет собой обычный алгоритм вычисления произведения матриц, в котором арифметические операции (+, ) заменены логическими (or, and). Учитывая то, что элементы матрицы имеют булевский тип, самый вложенный цикл с фиксированным числом повторений целесообразно заменить итерационным циклом с предусловием, в котором выражение C x,y = false и z N является условием входа в цикл. Конец C x,y := false x:=1,N y:=1,N C x,y := C x,y or A x,z and B z,y z:=1,N A o B 131 3.5. Свойства отношений Пусть R — бинарное отношение на множестве A, I — тождественное отношение, U — универсальное отношение. Вместо (x,y) R будем иногда использовать обозначение xRy. Отношения могут обладать следующими основными свойствами 1. R рефлексивно, если xRx для всех x A (граф такого отношения имеет петли при каждой вершине. Рефлексивность отношения R определяется истинностью значения выражения I R. 2. R антирефлексивно, если (x,x) R для всех x A (граф такого отношения не имеет петель. Антирефлексивность отношения R определяется истинностью значения выражения R I = . Нерефлексивное отношение в общем случае не является антирефлексивным. Отношение, граф которого содержит вершины с петлями и без петель — нерефлек- сивное и не антирефлексивное. 3. R симметрично, если из xRy следует yRx для всех x,y A (такое отношение изображается неориентированным графом, возможно спет- лями). Симметричность отношения R определяется истинностью значения выражения R = R -1 4. R антисимметрично, если из xRy следует (y,x) R для всех x,y A такое отношение изображается ориентированным графом, возможно с петлями. Антисимметричность отношения R определяется истинностью значения выражения R R -1 I . Отношение, граф которого содержит ориентированные дуги и неориентированные рѐбра, не является ни симметричным, ни антисимметричным. 5. R транзитивно, если из xRz и zRy следует xRy для всех x,y,z A. Транзитивность отношения R определяется истинностью значения выражения антитранзитивно, если из xRz и zRy следует (x,y) R для всех x,y,z A. Антитранзитивность отношения R определяется истинностью значения выражения (R R) R = 7. R полно, если из x y следует, что xRy или yRx для всех x,y A такое отношение изображается полным графом. Полнота отношения R определяется истинностью значения выражения R I R -1 = U. Следующие производные свойства отношений определяются совокупностью основных свойств. Отношение R является отношением — толерантности, если оно рефлексивно, симметрично — эквивалентности, если оно рефлексивно, симметрично и транзи- тивно (обозначается ); — порядка, если оно антисимметрично и транзитивно; 132 — нестрогого порядка, если оно отношение порядка (антисимметрично и транзитивно) и рефлексивно (обозначается ); — строгого порядка, если оно отношение порядка (антисимметрично и транзитивно) и антирефлексивно (обозначается <); — линейного порядка, если оно отношение порядка (антисимметрично и транзитивно) и полно — нестрогого линейного порядка, если оно отношение нестрогого порядка (антисимметрично, транзитивно и рефлексивно) и полно — строгого линейного порядка, если оно отношение строгого порядка (антисимметрично, транзитивно и антирефлексивно) и полно. В табл. 3.1 приведены примеры отношений на множествах целых чисел, прямых и окружностей на плоскости, на множестве людей и их основные и производные свойства. Таблица 3.1 Отношения и их свойства Отношение Рефлексивность Антир еф ле кс ив но сть С им метр ично сть А нтис им метр ич но сть Т ра нз итив но сть А нти транзитивность Полнота Производное свойство 2 3 4 5 6 7 8 9 Равно на множестве целых чисел + + + Эквивалентность Неравно на множестве целых чисел+ + + Больше на множестве целых чисел + + + + Строгий линейный порядок Больше или равно на множестве целых чисел + + + + Нестрогий линейный порядок Конгруэнтность на множестве треугольников+ Эквивалентность Включение на подмножествах некоторого множества + + + Нестрогий порядок 133 Окончание табл 1 2 3 4 5 6 7 8 9 Непустое пересечение на подмножествах некоторого множества+ + Толерантность Параллельность прямых на плоскости + + + Эквивалентность Перпендикулярность прямых на плоскости + + + Касание окружностей на плоскости+ + Концентричность окружностей на плоскости+ Эквивалентность Старше на множестве людей + + + + Строгий линейный порядок Мать на множестве людей + + + Родственник на множестве людей+ + + Эквивалентность Предок на множестве людей+ + + Строгий порядок Брат на множестве людей+ + Брат на множестве мужчин+ + + Эквивалентность Двоюродный брат на множестве мужчин+ + Друг на множестве людей+ + Толерантность Семья на множестве людей, живущих водной квартире+ + + + Эквивалентность Семья на множестве людей, живущих водном городе+ + + Эквивалентность |