42417

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

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

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

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

Русский

2013-10-29

141.5 KB

70 чел.

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


 

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

30736. Рабочее и социалистическое движение в годы первой мировой войны 23.5 KB
  Тяжелые условия войны вызывали недовольство населения и к 1916 г. Фактически под напором революционной войны вынуждены были прекратить сопротивление Россия Болгария АвстроВенгрия и др. Если в довоенное время рабочее и социалистическое движение было хорошо организовано как на национальном так и на международном уровне европейские социалистические или социалдемократические партии которые были объединены в Рабочий Интернационал то после Первой мировой войны рабочее движение раскололось.
30737. Антифашистская борьба и движение Сопротивления в Италии (1920-1930-е гг.) 22 KB
  Антифашистская борьба зародилась в тот же момент когда буржуазия стала прибегать к фашистскому режиму для сохранения своих идеалов. В Италии антифашистская борьба развернулась в 1921 году в ответ на наступление фашистов. состоялась всеобщая политическая антифашистская забастовка которая могла бы преградить путь фашизму но она была сорвана. Уже к 1924 году Антифашистская борьба зародившаяся в Италии призывала к объединению всех странпротивников фашизма.
30738. Характерные черты и особенности капитализма в Западной Европе и Америке накануне первой мировой войны 23 KB
  Накануне первой мировой войны правила диктовали социальные протесты и стремление уменьшения политической нестабильности. Следовательно первой чертой капитализма накануне первой мировой войны в Западной Европе и Америке мы можем назвать возникновение основ социального государства начинается социализация капитализма.
30739. Особенности неоконсерватизма в Великобритании. Внутренняя и внешняя политика Тэтчер 31.5 KB
  Внутренняя и внешняя политика Тэтчер. Главой правительства стала Маргарет Тэтчер. Тэтчер проявила себя убежденной сторонницей консервативных взглядов за твердый и непреклонный характер ее прозвали âжелезная ледиâ. Тэтчер пользовалась большим авторитетом и в Англии и в мире под ее руководством консервативная партия одержала победы на выборах 1983 г.
30740. Политическая борьба в западной зоне оккупации Германии. Образование ФРГ 24.5 KB
  После войны в Западной Германии происходит борьба партий: одни за единое немецкое государство СДПГ соцдемокр партия герм но против советского военнополитического присутствия другие за формирование западноевропейского государства Христ. но распространить свое влияние на всю территорию Германии она не сумела оказавшись под жестким прессингом со стороны советской администрации.и раскол Германии Уже в начале 1947 г.
30741. Основные направления внутренней и внешней политики республиканских администраций в США (1921 – 1933-е гг.) 23 KB
  у власти в США стояли республиканцы. Это был период процветания США. В 20е годы мировая капиталистическая экономика стабилизировалась и в США наступил экономический подъем: рост автомобилей строительство дорог США становится мировым кредитором оттеснив Англию и т.
30742. Коминтерн и РСИ – особенности стратегии и тактики в 1920 – 1930 гг 25 KB
  в России по инициативе Ленина был создан Коммунистический интернационал Коминтерн участвовали 28 стран был провозглашен курс на мировую социалистическую революцию. На первый план выдвигались не социалистические путем революции а демократические задачи реформы как подготовительный этап на пути к социальной революции. Новые задачи потребовали изменение отношения коммунистов к социалдемократии. Если раньше союз с социалдемократией был невозможен изза разницы во взглядах то теперь этот союз стал возможен т.
30743. Холодная война и ее этапы (с 40-х по 90-е гг.) 24.5 KB
  Конфликт двух сверх держав США и СССР противостояние двух военнополиитческих блоков НАТО и Варшавского договора. Воплощением конфликта стала холодная война между США и СССР. Начало Холодной войны было в момент послевоенного урегулирования когда возникли противоречия между союзниками антигитлеровской коалиции США и Великобритании и СССР. был создан англоамериканский военный союз для борьбы с СССР и коммунистической угрозой.
30744. Захватнические планы Гитлеровской Германии и их осуществление (1935 – 1941 гг.) 24 KB
  Захват чужих территорий стал центром всей политики гитлеровской Германии. Немаловажное значение для развития экономического потенциала Германии и использования его в военных целях против СССР имели захват и ограбление Австрии Чехословакии Польши Франции и других европейских стран. На выполнение только военных заказов Германии работали предприятия оккупированных западноевропейских стран.