42417

Бинарные отношения. Симметричные отношения

Лабораторная работа

Математика и математический анализ

Определение 6: Отношение  на множестве Х называется рефлексивным если для любого элемента хХ выполняется хх. Определение 7: Отношение  на множестве Х называется симметричным если для любых хуХ из ху следует ух. Определение 8: Отношение  на множестве Х называется транзитивным если для любых хуzХ из ху yz следует xz. Определение 9: Отношение  на множестве Х называется антисимметричным если для любых xy X из xy и yx следует x=y.

Русский

2013-10-29

141.5 KB

61 чел.

Практическое занятие №4

Тема: Бинарные отношения. Симметричные отношения.

Основные свойства отношений. Специальные бинарные отношения.

Занятие рассчитано на 2 академических часа.

Цель работы: Ознакомить с главными понятиями теории отношений, понятиями отношения эквивалентности и отношения порядка. Научить составлять матрицу и граф бинарного отношения, изображать матрицу и граф отношения эквивалентности и порядка.

Теоретический материал

Понятие бинарного отношения ведено для строгого математического описания любых связей между элементами двух множеств. Такие бинарные отношения, как отношение эквивалентности и частичного порядка часто появляются как в математике, так и в информатике. Отношения между элементами нескольких множеств задаются в виде таблиц данных. N - арные отношения применяются для описания простой системы управления базами данных.

Определение 1: Бинарным отношением называется множество упорядоченных пар. Если - некоторое отношение и пара <x,y> принадлежит этому отношению, то наряду с записью <x,y> употребляется запись xy.  Элементы x и y называются координатами отношения .

Определение 2: Областью определения бинарного отношения называется множество D={x|существует такое y, что xy}.

Определение 3: Областью значений бинарного отношения называется множество R={y|существует такое x, что xy}.

 Бинарное отношение между конечными множествами может быть задано одним из следующих способов:

• словами (с помощью подходящих предикатов);

• как множество упорядоченных пар;

• как орграф;

• как матрица.

Отношение можно изобразить соответствующей ему прямоугольной таблицей (матрицей). Ее столбцам отвечают первые координаты, а срокам – вторые координаты. На переcечении І-го столбика и J-ой сроки ставится единица, если выполнены соотношения ХіYі, и ноль, если соотношение не выполняется.

Пусть например: Х={x1, x2, x3, x4, x5}; Y={y1, y2, y3, y4}

1. ={(x1, y1), (x1, y3), (x2, y1), (x2, y3), (x2, y4), (x3, y1), (x3, y2), (x3, y4), (x4, y3), (x5, y2), (x5, y4)}

Матрица отношений :

x1

x2

x3

x4

x5

y1

1

1

1

0

0

y2

0

0

1

0

1

y3

1

1

0

1

0

y4

0

1

1

0

1

Отношение можно также изобразить с помощью ориентированного графа. Вершины графа отвечают элементам множеств X и Y, а дуга, которая направлена из вершины Xi к Yi, означает что XiYi.

Граф отношения (1).

x1

  y1

x2

  y2

x3

  y3

x4

  y4

x5

Свойства бинарных отношений

Определение 4: Симметрическим (обратным) отношением для  называется отношение

-1={<x,y>|<y,x>}.

Определение 5: Композицией отношений 1 и 2 называется отношение

21={<x,z>|, существует y такое, что <x,y>1 и <y,z>2}.

Матрица отношения 21 получается путем умножения матрицы 1 на матрицу 2. Чтобы получить граф композиции 21 надо к графу отношения 1 достроить граф отношения 2 и включить вершины множества Y, заменив маршруты, которые проходят через них из множества Х в Y одной дугой.

1.(-1)-1=;

2. (21)-1=1-1  2-1.

Определение 6: Отношение на множестве Х называется рефлексивным, если для любого элемента хХ выполняется хх.

Определение 7: Отношение на множестве Х называется симметричным, если для любых х,уХ  из ху следует ух.

Определение 8: Отношение на множестве Х называется транзитивным, если для любых х,у,zХ  из ху, yz следует xz.

Определение 9: Отношение на множестве Х называется антисимметричным, если для любых x,y X из xy и yx следует x=y.

Определение 10: Рефлексивное, симметричное и транзитивное отношение на множестве X называется отношением эквивалентности на множестве Х.

Для бинарных отношений обычным образом определены теоретико-множественные операции объединения, пересечения и т.д.

Определение 11: Рефлексивное, антисимметричное и транзитивное отношение называется отношением частичного порядка на множестве Х и обозначается <.

Определение 12: Отношение частичного порядка на множестве Х, для которого любые две элемента сравнимы, т.е. для любых х,у Х, х<y или y<x, называется отношением линейного порядка.

Определение 13: Множество Х с заданным на нем частичным (линейным) порядком называется частично (линейно) упорядоченным.

Любое частично упорядоченное множество можно представить в виде схемы, в которой каждый элемент изображается точкой на плоскости, и если у покрывает х, то точки х и у соединяют отрезком, причем точку, соответствующую х, располагают ниже у. Такие схемы называют диаграммами Хассе.

Различные сортирующие процедуры в информатике требуют, чтобы элементы сортируемых множеств были линейно упорядочены. В этом случае они могут выдавать упорядоченный список. Другие приложения используют частичный порядок, предполагая, что в любом частично упорядоченном множестве найдется минималъный элемент (не имеющий предшественников) и максимальный (не имеющий последующих элементов).

Теорема: Если на множестве А заданное отношение эквивалентности, то это отношение индуцирует единичное разбиение и наоборот: если на множестве задано разбиение, то ему отвечает единое отношение эквивалентности.

Матрицу отношения эквивалентности всегда можно привести к такому виду, в котором единичные элементы матрицы образуют квадраты, которые не пересекаются, и диагонали которых располагаются на главной диагонали матрицы. Граф отношения эквивалентности – это несвязный граф, который состоит из полных компонент.

 Разбиением множества Х называется совокупность попарно непересекающихся подмножеств Х таких, что каждый элемент множества Х принадлежит одному и только одному из этих подмножеств.

Методические указания

Пример 1: Множество R = {(х, у) : х — делитель у} определяет отношение на множестве А = {1, 2, 3, 4, 5, 6}. Найдите все упорядоченные пары, ему принадлежащие. Изобразите граф, представляющий отношение R.

 Решение: R состоит из пар: (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 2), (2, 4), (2, 6), (3, 3), (3, 6), (4, 4), (5, 5) и (6, 6). Ориентированный граф будет иметь шесть вершин (рис.1):

Рисунок 1. Отношение R на множестве А.

Пример 2: Отношение R на множестве А = {а, b, с, d} задается матрицей:

порядок строк и столбцов в которой соответствует порядку выписанных элементов множества А. Назовите упорядоченные пары, принадлежащие R.

 Решение: Отношение R содержит упорядоченные пары: (а, b), (а, с), (b,с), (b, d), (с, b), (d, а), (d, b) .

 Пример 3: Дано, что отношение «...делитель...» определяет частичный порядок на множестве А = {1, 2, 3, 6, 12, 18}. Составьте таблицу предшественников и непосредственных предшественников, после чего постройте соответствующую диаграмму Хассе.

 Решение: Таблица и диаграмма приведены ниже.

Таблица 1.

Рисунок 2. Диаграмма Хассе.

Частично упорядоченное множество из примера обладает одним минимальным элементом, а именно, числом 1. С другой стороны, в нем есть два максимальных: 12 и 18. В этом множестве содержится несколько линейно упорядоченных подмножеств. Каждое из них соответствует цепочке ребер на диаграмме Хассе. Например, множество {1, 2, 6, 18} линейно упорядочено относительно отношения «... делитель...».

Контрольные вопросы

  1.  Привести частные случаи отношений в Х.
  2.  Как составляется матрица бинарного отношения?
  3.  Как изображается граф бинарного отношения?
  4.  Что такое композиция отношений?
  5.  Что такое отношение эквивалентности?
  6.  Что такое отношение порядка?

7. Дайте характеристику матрице и графу отношения эквивалентности и порядка.

Индивидуальные задания

1. Даны два множества Х и Y и бинарное отношение . Для данного отношения :

а) записать  области определения и область значений;

б) определить сечение по каждому элементу из Х;

в) определить сечение по подмножествам Х' i X” множества Х;

г) записать матрицу и начертить граф;

д) определить обратное отношение.

Варианты:

  1.  X={x1, x2, x3, x4, x5, x6}; Y={y1, y2, y3, y4}

A={(x1, y2), (x2, y1), (x2, y2), (x4, y2), (x4, y3), (x5, y1), (x5, y3)};

X’={x1, x4}; X”={ x2, x3, x5};

  1.  X={a, d, c, d, e}; Y={k, l, m, n}

A={(a, k), (a, m), (a, n), (b, k), (b, m), (c, l), (c, m), (c, n)};

X’={a, d}; X”={k, m};

3) X={x1, x2, x3, x4, x5}; Y={y1, y2, y3, y4, y5, y6}

A={(x1, y2), (x2, y1), (x2, y2), (x4, y1), (x4, y6), (x5, y3), (x5, y5)};

X’={x2, x3}; X”={ x2, x4, x5};

4) X={a, d, c, d, e}; Y={k, l, m, n}

A={(b, k), (a, l), (a, m), (b, n), (c, k), (c, l), (c, n), (d, l), (d, m), (e, k), (e, l), (e, m)};

X’={a, b, c}; X”={e, m, n};

5) X={x1, x2, x3, x4, x5, x6}; Y={y1, y2, y3, y4, y5}

A={(x1, y1), (x1, y2), (x2, y1), (x2, y2), (x4, y5), (x5, y1), (x5, y3), (x6, y1), (x6, y3), (x6, y5)};

X’={x3}; X”={ x1, x2, x4, x6};

6)  X={x1, x2, x3, x4, x5, x6}; Y={y1, y2, y3}

A={(x1, y2), (x1, y3), (x2, y1), (x2, y2), (x3, y1), (x4, y3), (x5, y1), (x5, y3), (x6, y2)};

X’={x2, x3, x4}; X”={ x1, x6};

7) X={a, d, c, d, e, f}; Y={x, y, z}

A={(a, x), (a, y), (a, z), (b, x), (c, y), (d, x), (d, z), (e, y), (f, x), (f, y), (f, z)};

X’={a, b, f}; X”={b, d, e};

8) X={a, d, c, d, e, f}; Y={x, y, z}

A={(a, y), (a, z), (b, x), (b, y), (c, x), (c, z), (d, x), (d, y)};

X’={a, c, e}; X”={d};

9) X={x1, x2, x3, x4, x5}; Y={y1, y2, y3, y4, y5}

A={(x1, y1), (x1, y5), (x2, y1), (x2, y3), (x2, y5), (x3, y2), (x3, y4), (x4, y1), (x4, y2), (x5, y1), (x5, y3)};

X’={x1, x3}; X”={ x2, x5};

10) X={a, d, c, d, e, f, k}; Y={n, m, t, u}

A={(a, n), (a, t), (b, m), (c, t), (c, u), (d, m), (d, u), (e, m), (e, u), (f, t), (f, u), (k,   m)};

X’={a, d, e}; X”={d, f, k};

11) X={a, d, c, d, e, f}; Y={m, t, u, x}

A={(a, m), (a, t), (b, u), (b, x), (c, m), (d, u), (d, x), (e, t), (e, u), (f, m), (f, t)};

X’={a, c, e, f}; X”={a, b, d};

12) X={x1, x2, x3, x4, x5}; Y={y1, y2, y3, y4, y5}

A={(x1, y2), (x1, y5), (x2, y2), (x2, y3), (x2, y5), (x4, y3), (x4, y5), (x5, y1), (x5,  y2), (x5, y4), (x5, y5)};

X’={x1, x4, x5}; X”={ x2, x3}.

2. Какие свойства имеют бинарные отношения, заданные в некотором множестве людей Х и выраженные соотношением (Хі, Xj X)?

(Доказать)

Варианты:

1) ”Хі мужчина Хj”

2) ”Хі знакомый с Хj”

  1.  ”Хі похожий на Хj”
  2.  ”Хі старше Хj”
  3.  ”Хі младше Хj”
  4.  ”Хі родственник Хj”
  5.  ”Хі сосед Хj”
  6.  ”Хі однокурсник Хj”
  7.  ”Хі проживает в одном доме с Хj”
  8.  ”Хі весит большее чем Хj”
  9.  ”Хі сотрудник Хj”
  10.  ”Хі подчиненный Хj”

3. Записать композицию С= В о А отношений А и В. Проверить результат с помощью операций над матрицами и графами заданных отношений:

Варианты:

  1.  А={(1, 2), (1, 3), (2, 1), (2, 4), (3, 3)};

B={(1, 1), (1, 3), (2, 2), (2, 3), (3, 1), (4, 2), (4, 3)};

2)  А={(x1, y1), (x1, y2), (x2, y1), (x3, y2), (x4, y3)};

B={(y1, z2), (y2, z1), (y2, z3), (y3, z4), (y3, z5)};

3)  А={(1, 2), (1, 4), (2, 1), (2, 2), (3, 1)};

B={(1, 4), (2, 1), (2, 2), (2, 3), (3, 1), (4, 1), (4, 3)};

4) А={(x1, y2), (x2, y1), (x2, y2), (x3, y1), (x3, y3)};

B={(y1, z1), (y2, z1), (y3, z3), (y3, z4), (y3, z5)};

5) А={(1, 1), (1, 2), (2, 1), (2, 4), (3, 1)};

    B={(1, 2), (1, 3), (2, 2), (2, 3), (3, 1), (4, 1), (4, 3)};

6) А={(x1, y1), (x2, y1), (x2, y2), (x3, y2), (x4, y3)};

B={(y1, z1), (y2, z1), (y3, z2), (y3, z3), (y3, z4)};

7) А={(1, 1), (1, 3), (2, 1), (2, 2), (3, 2)};

    B={(1, 2), (2, 1), (3, 1), (2, 3)};

8) А={(1, 2), (1, 3), (2, 1), (2, 4), (3, 1) , (4, 1)};

    B={(1, 1), (1, 3), (2, 2), (2, 3) , (3, 2), (4, 2) , (4, 3)};

9) А={(x1, y1), (x2, y2), (x2, y3), (x2, y4), (x3, y2) , (x4, y1)};

B={(y1, x2), (y2, x1), (y2, x3), (y3, x1)};

10) А={(1, 1), (1, 2), (1, 3), (2, 2), (2, 4), (3, 1), (3, 2), (4, 1)};

      B={(1, 2), (2, 2), (2, 3), (3, 2), (3, 3), (4, 3)};

11) А={(x1, y1), (x2, y2), (x2, y3), (x3, y1), (x3, y2) , (x4, y3)};

      B={(y1, z1), (y2, z1), (y2, z2), (y3, z3), (y3, z4), (y3, z5)};

12) А={(1, 2), (1, 3), (2, 1), (2, 4), (3, 1), (3, 2), (3, 3), (4, 1)};

      B={(1, 1), (2, 1), (2, 2), (3, 1), (3, 2), (4, 1), (4, 2)};

4. Постройте графики для таких отношений (в тех случаях, если график есть частью плоскости, эта часть штрихуется).

{(x,y) R*R}

Варианты:

  1.  {(x, y) R*R: x <= y}
  2.  {(x, y) R*R: x >= y}
  3.  {(x, y) R*R: y >= x  x>=0}
  4.  {(x, y) R*R: x^2+y^2=1}
  5.  {(x, y) R*R: x<y}
  6.  {(x, y) R*R: |x|+|y|=1}
  7.  {(x, y) R*R: y>=0y<=x}
  8.  {(x, y) R*R: x>y+3}
  9.  {(x, y) R*R: y>0x+y<1}
  10.  {(x, y) R*R: |x|+2*|y|=1}
  11.  {(x, y) R*R: x^2+y^2<=1}
  12.  {(x, y) R*R: x2+y2>1}

5. Докажите, что отношения будут отношениями эквивалентности:

Варианты:

  1.  “сходство” в множестве всех треугольников на площади.
  2.  “принадлежность до одной группы” в множестве студентов.
  3.  “равенство веса” в множестве разновесов.
  4.  “взаемозаменяемость” в множестве деталей.
  5.  “концентричность” в множестве кругов на площади.
  6.  “проживать в одном доме” в множестве людей.
  7.  “принадлежность к одному факультету” в множестве студентов факультета.
  8.  “параллельность” в множестве прямых на плоскости.
  9.  “взаимозаменяемость” в множестве работников цеха.
  10.  “принадлежать к одной семье” в множестве людей.
  11.  “равенство объемов” в множестве пространственных тел.
  12.  “равенство площадей” в множестве плоскостных фигур.

6. Доказать, что приведенные ниже отношения есть отношениями порядка и определить тип упорядоченности:

Варианты:

  1.  x более тяжелый y” в множенные деталей.
  2.  x подчиненный y” в множестве должностей.
  3.  x длиннее y” в множестве отрезков на плоскости.
  4.  x старший y”  в множестве людей.
  5.  x не превышает y” в множестве номеров домов на улице.
  6.  “с x вытекает y” в множестве высказываний.
  7.  x находится внутри y” в множестве концентрических кругов.
  8.  x младший y” в множестве людей.
  9.  x более легкий y” в множестве деталей.
  10.  x короче y” в множестве отрезков на плоскости.
  11.  x не длиннее y” на множестве отрезков на плоскости.
  12.  x не старший y” в множестве людей.

7. Составить матрицу и нарисовать граф отношения порядка на множестве Х.

     Найти мажоранты, миноранти, подмножества Q, min (Q) и max (Q), inf (Q), sup (Q):

Варианты:

  1.  “быть делителем” на X = {1, 2, 3, 4, 6, 12, 14, 28, 42, 420}

    Q = {4, 12, 28}

  1.  “>” на X = {10, 11, 13, 14, 15, 20, 25, 40, 50}

      Q = {11, 13, 15}

  1.  “<=” на X = {5, 7, 9, 11, 20, 25, 26, 27, 40, 45, 55}

        Q = {9, 20, 27, 40}

  1.  “быть делителем” на X = {2, 4, 6, 7, 8, 9, 10, 15, 18, 54}

    Q = {6, 9}

  1.  “>” на X = {1, 2, 3, 10, 11, 13, 15, 16, 17, 20, 25, 40}

      Q =  {10, 13, 15, 16}

  1.  “<” на X = {20, 21, 22, 23, 24, 25, 40, 41, 42, 44, 45}

      Q = {22, 23, 24, 25}

  1.  “быть старшей” на множестве веков человека

X = {7, 8, 10, 11, 12, 15, 20, 25, 40, 41, 42}

Q = {11, 12, 15, 25}

  1.  “ быть делителем ” на X = {4, 5, 8, 10, 12, 14, 60, 120}

      Q = {10, 12}

  1.  “быть младшей” на множестве веков человека

X = {8, 10, 11, 12, 20, 21, 22, 24, 26, 40}

Q = {10, 20, 22, 24}

  1.  “ быть делителем ” на множестве X.

X = {1, 2, 3, 4, 10, 12, 15, 17, 20, 21, 44, 440}

Q = {10, 20, 21, 44}

  1.  “ быть делителем ” на множестве X.

X = {2, 3, 10, 11, 12, 13, 14, 15, 16, 60, 300}

Q = {3, 12, 15}

  1.  “ быть делителем ” на множестве X.

X = {1, 2, 3, 5, 7, 8, 9, 12, 27, 54}

Q = {1, 3, 9}

8. Нарисуйте диаграмму Хассе для каждого из следующих частично упорядоченных множеств:

(а) множество {1, 2, 3, 5, 6, 10, 15, 30} с отношением «х делит у»;

(б) множество всех подмножеств в {1, 2, 3} с отношением «X подмножество Y».

9. Диаграмма Хассе частичного порядка R на множестве А = {а, Ь, с, d, е, f, g, h} показана на рис. 3. Перечислите элементы R и найдите минимальный и максимальный элементы частично упорядоченного множества А.

Рисунок 3.

PAGE  1


 

А также другие работы, которые могут Вас заинтересовать

28485. Алгоритм симплексного методу 23.31 KB
  Заповнення початкової симплекстаблиці перша ітерація Таблиця 1 В рядках 1 3 записані відповідні рівняння системи 12 при цьому спочатку права частина в стовпці опорний план а потім коефіцієнти при відповідних змінних. Отже з початкової таблиці безпосередньо виписується початковий опорний план: Х1 оп = 0; 0; 182; 316; 238. В нульовому рядку міститься інформація про цільову функцію: для зручності функція 11 розглядається формалізовано як рівняння z 18х1 16х2 = О...
28486. Постановка транспортної задачі та її математична модель 31.64 KB
  Постановка транспортної задачі та її математична модель. Побудуємо математичну модель закритої транспортної задачі Позначимо через xij кількість одиниць вантажу запланованого до перевезення від iго постачальника до jго споживачаz сумарну вартість запланованих перевезень Для зручності умову задачі запишемо у вигляді таблиці табл 1 яку надалі будемо називати транспортною сіткою При цьому постачальників скорочено позначимо літерою П а споживачів С Таблиця 1...
28487. Методи побудови початкового опорного плану транспортної задачі 21.99 KB
  Рекомендуємо олівцем проставити прочерки в клітинках А2 В1 і А3 В1 потреби В1 задоволені а біля 300 справа записати залишки запасів в розмірі 150 од. запасів і 220 од. В напрямку який визначає діагональ переходимо до А2В2 в яку записуємо min70 230=70 виставивши прочерк в А3 В2 закресливши залишок потреб під В2 і записавши справа від 230 залишок запасів 23070=160. В клітинку А2В3 заносимо min 160 280= 160 виставляємо прочерк в А2В4 закреслюємо залишок запасів А2 160 а під потребами В3 записуємо залишок потреб В3 в розмірі...