42417

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

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

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

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

Русский

2013-10-29

141.5 KB

55 чел.

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


 

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

52984. Внеклассное мероприятие по физике «Лирическая физика» 64.5 KB
  1 конкурс Разминка Разминка физическая Кто открыл явление инерции Из чего состоят молекулы Прибор для измерения массы тела Основная единица измерения силы В каком городе жил Архимед Состояние вещества если молекулы расположены в строгом порядке Научные предположения о чем – либо Основная единица количества теплоты Плотность чистой воды Какую физическую величину измеряют мензуркой Как называют изменение формы или размеров тела Как называется процесс превращения пара в жидкость Основная единица...
52985. Взаємодія тіл 1.18 MB
  Запропоновані тестові завдання можуть бути використані як для поточної перевірки знань учнів, так і для тематичних атестацій. Задачі і завдання підібрані різних типів - розрахункові, графічні, якісні, задачі-малюнки, умова яких задається за допомогою малюнка, графіка, фотографії.
52987. Компетентнісний підхід у викладанні фізики 105.5 KB
  Ключові компетенції включають в себе вміння виконувати цілісну ясну грамотну дію вирішувати реальну ситуацію задачу. У зв'язку з цим можна виділити навички та вміння які повинні виникнути у студентів: володіння інформаційними технологіями уміння їх застосовувати збір і обробка необхідної інформації; здатність вчитися все життя це основа безперервної підготовки в професійному плані а також в особистому і суспільному житті; вміння спілкуватися поважати один одного здатність жити з людьми інших культур мов і релігій. Це призводить...
52988. Методичні рекомендації з проведення навчального експерименту в системі вивчення фізики в середній школі 170.5 KB
  Методичні рекомендації з проведення навчального експерименту в системі вивчення фізики в середній школі м. Система шкільного експерименту з фізики. Роль експерименту в процесі вивчення фізики в школі.
52989. ФОРМУВАННЯ САМООСВІТНЬОЇ КОМПЕТЕНТНОСТІ УЧНІВ ЗАСОБАМИ ФІЗИКИ 103 KB
  Модель випускника готового до самоосвіти Засоби організації самоосвітньої діяльності учнів Пам’ятки раціональної організації навчальної роботи школяра як розв’язати задачу як здійснити перевірку розв’язків задачі робота з підручником фізики складання плану відповіді з фізики як скласти конспект як готувати доповідь реферат як працювати з додатковою літературою як готувати домашнє завдання як виконувати письмову домашню роботу Зразки тестів та контрольних робіт для перевірки навчальних досягнень...
52990. Вивчати фізику цікаво 270 KB
  Серед безлічі шляхів формування у школярів пізнавального інтересу одним з найбільш ефективних є організація ігрової діяльності. Ігрові форми навчання дозволяють пожвавити навчальний процес, зробити його більш привабливим для учнів, підвищують інтерес до предмета в цілому, активізують мислення та творчу діяльність учнів.
52991. Використання моделей і моделювання в шкільному курсі фізики 230.5 KB
  Наводиться технологічний ланцюжок вирішення завдань на комп'ютері. Технологія моделювання вимагає від дослідника уміння ставити проблеми і завдання прогнозувати результати дослідження проводити розумні оцінки виділяти головні і другорядні чинники для побудови моделей вибирати аналогії і математичні формулювання вирішувати завдання з використанням комп'ютерних систем проводити аналіз комп'ютерних експериментів. Моделювання експерименту засобами ІКТ Сьогодні коли комп'ютер став основним інструментом дослідника різні види моделей можна...