Полная версия

Главная arrow Математика, химия, физика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Способы заданий бинарных отношений

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

Пусть р С А х В и А = {«i, а2п}, В = {/ц, 62> • • •, Ьт}. Отношению р поставим в соответствие матрицу С = гз) размерности пх гп (г — 1,2,...,n; j — 1,2,.... ш), в которой с^- = 1 тогда и только тогда, когда г. bj) G р, в остальных случаях Су= 0. Такая матрица полностью определяет бинарное отношение и называется матрицей бинарного отношения р. Если р С /12, то матрица отношения будет квадратной. Такой способ задания отношений позволяет действия над отношениями моделировать операциями над соответствующими бинарными матрицами, т. е. матрицами, у которых любой элемент либо 0, либо 1.

Отметим основные свойства матриц бинарных отношений.

  • 1. Матрица произведения (композиции) рост бинарных отношений рСА х В и сгСВхС равна произведению матриц этих отношений, т. е. Сроа — СрСG. Умножают бинарные матрицы по обычным правилам, при этом 0 + 0 = 0, 0 + 1 = 1, 1+0 = 1, 1 + 1 = 1.
  • 2. Матрица обратного отношения р-1 равна транспонированной матрице отношения р, т. е. Ср- — {СР)Т.
  • 3. Если Cp=(pij), Ca = ((jij) - матрицы бинарных отношений р, (jC Ах В И р С (7, ТО Pij + Qij.

Пр и мер 2.1. Бинарные отношения рСАх В и аСВхС за-

/о 1 о 0 1

даны матрицами Ср= ( 1, Са= 1 0 I. Найти матрицы отно-

' 1 1 /

шений р-1, рост. Привести пример матрицы бинарного отношения тСр (тСЛх В).

0 10+

Используя свойства 1 и 2, получим Ср-1 = ( ] = I 1 1 ,

^ 1 1 0 ' 0 0 /

( 0 1 0 ( ? !| + 0 п .. „

Сроа = I 10 1 = 1 ). По свойству 3 матрица бинарно-

г- 1

го отношения тСр может, например, иметь вид I I.

Для наглядности используют графический способ задания бинарного отношения р на множестве A = {ai, а2,ап}. Он состоит в том, что элементы множества А изображаются точками. При этом две точки а,г и Uj соединяются направленной дугой тогда и только тогда, когда («., ++) G р. Существуют графические способы представления бинарных отношений между различными множествами.

Еще один способ задания бинарного отношения р на множестве А = {ац <22,ап} связан с понятием фактор-множества. Для каждого элемента щ множества А определяется подмножество А{ всех тех элементов из Л, которые находятся с ним в данном отношении, т. е.

Ai = {xx^A, (а;,ж)Ер} (иногда его называют образом элемента щ). Совокупность таких подмножеств Яу; (г = 1,2,..., п) называется фактормножеством множества А по отношению р и обозначается А/р. Если в одну строку выписать все элементы множества А, а во второй строке под каждым из них - соответствующие элементы (образы) фактормножества А/p, то очевидно, что отношение р будет полностью задано.

П р и мер 2.2. Пусть на множестве А = {ai = 2, ao = S, аз = 4, а4 = 6,а.5 = 12}, бинарное отношение а определено следующим образом: элемент а множества А находится в отношении а с элементом b ((a, b) Е (г) тогда и только тогда, когда а делит Ь. и а меньше Ь. Задать это отношение всеми возможными способами. Найти область определения и область значений отношения а.

В условии отношение а как подмножество А2 определено с помощью характеристического свойства,

1. Зададим отношение а перечислением его элементов: а — = {(2,4), (2,6), (2,12), (3,6), (3,12), (4,12), (6,12)}.

Рис. 4

2. Составим матрицу отношения сг.

  • 3. На рис. 4 изображено одно из возможных графических представлений отношения <7.
  • 4. Зададим отношение а с помощью фактор-множества А/ст = = {{4,6,12} {6,12}, {12}, {12}.0}.
  • 5. Область определения отношения а это множество D(a) = {2,3,4,6}, область значений - Е(а) = {4,6,12}.

Ясно, что от одного способа задания отношения всегда можно перейти к другому способу. Например, по рис. 4, можно задать отношение перечислением, записать его матрицу и фактор-множество.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>