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


 

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

49468. Создание компьютерной программы «Расчет длительности опреации на конвейре» 50.27 KB
  Компьютерные продукты являются объектами нематериальных активов – это часть активов предприятия, которые обладают стоимостью, но не имеют материального содержания. Они используются в хозяйственном обороте и способны приносить доход. Расчет оплаты специалистов производиться исходя из дневной тарифной ставки каждого.
49469. Проектирование электрического освещения ремонтно-механического цеха 1.25 MB
  Проектирование электрического освещения ремонтно-механического цеха по дисциплине: Электрическое освещение Выполнила студентка гр. Выбор источников света для системы общего равномерного освещения цеха и вспомогательных помещений Светотехнический расчёт системы общего равномерного освещения и определение установленной мощности источников света в помещениях Выбор источников света типов светильников их размещение и светотехнический расчёт...
49470. Проектирование электрического освещения 434 KB
  Выбор того или иного источника света определяется требованиями к освещению (цветность излучения, зрительный комфорт, показатель блескости и других) и выполняется на основании сопоставления достоинств и недостатков существующих источников света. При этом предпочтение необходимо отдавать...
49474. Создание компьютерной программы «Формирование статистики звонков аппарата Градиент» 49.19 KB
  Компьютерные продукты являются объектами нематериальных активов – это часть активов предприятия, которые обладают стоимостью, но не имеют материального содержания. Они используются в хозяйственном обороте и способны приносить доход. Расчет оплаты специалистов производиться исходя из дневной тарифной ставки каждого.
49475. Проектирование железнодорожной линии в Читинской области 447.5 KB
  В соответствии с заданным соотношением вагонного состава определяется количество вагонов соответствующего типа и длина поезда: 1 где: Ln длина поезда м; ni количество вагонов iго типа; li длина вагонов iго типа м; lл длина локомотива м; Количество вагонов определяется: 2 где: Q масса поезда т; Длина приёмо-отправочных путей принимается равной 1050 м. 40001200 800 600 Наименьшая длина прямой: а Нормативные условия: между кривыми направленными в одну сторону между кривыми направленными в...