42417

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

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

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

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

Русский

2013-10-29

141.5 KB

62 чел.

Практическое занятие №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


 

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

67674. Проект редуктора нереверсивного с использованием программы Solid Works 2005 1.13 MB
  Редуктор проектируют либо для привода определенной машины, либо по заданной нагрузке и передаточному числу без указания конкретного задания. Наиболее распространены горизонтальные редукторы. Как горизонтальные, так и вертикальные редукторы могут иметь колеса с прямыми, косыми и круговыми зубьями.
67675. Изучение станка качалки привода штанговой глубинной насосной установки 646.55 KB
  В начале нашего века произошли коренные изменения в нефтепереработке. Быстрое распространение карбюраторных бензиновых двигателей внутреннего сгорания с искровым зажиганием для автомобилей (а позже в авиации) потребовало огромного количества топлива.
67676. Завод по производству стальных пространственных конструкций 232 KB
  Эта жизненная среда называемая архитектурой воплощается в зданиях имеющих внутреннее пространство комплексах зданий и сооружений организующих наружное пространство улицы площади и города. В современном понимании архитектура это искусство проектировать и строить здания сооружения и их комплексы.
67677. Сталь 40ХНМА и прочая полезная информация 1.66 MB
  При выборе термической обработки необходимо представлять себе сущность изменений, происходящих в стали при этой обработке. Для этого необходимо знать основные положения металловедения, в частности строение стали и механизм протекания фазовых превращений.
67678. Разработка считывателя системы контроля за персоналом на основе микроконтроллера AVR 494.5 KB
  На основании анализа функциональной спецификации можно выделить следующие блоки которые необходимо реализовать аппаратным способом: Входы: модуль контактного устройства модуль связи с компьютером модуль часов Выходы: модуль светодиодных индикаторов модуль переноса данных Функции: модуль защиты...
67681. Проект отделения ремонта двигателей на обслуживание 459 автомобилей ГАЗ-33075 569.5 KB
  Основной объём работ по ЕО приходится на УМР. Рабочий пост предназначен для выполнения основных работ по ТО и ТР автомобилей и представляет собой участок пола здания производственное площади для постановки автомобилей и размещения одного или нескольких рабочих мест.