Понятие отношения

Булев куб и его свойства

Булев вектор может применяться для моделирования операций на конечных множествах. Пусть – некоторое универсальное множество в рамках решаемой задачи. Элементы множества для удобства помечены числовыми индексами. Если, то множеству А ставится в соответствие n - мерный булев вектор, в котором, если и в противном случае. Такая строка бит называется характеристическим вектором множества А. При этом, операции на множествах имитируются соответствующими логическими операциями на характеристических векторах.

Для размерности n операции над векторами производятся покоординатно. Логическая сумма двух векторов – вектор, координаты которого являются логическими суммами соответствующих исходных векторов. Аналогично определено произведение.

Между множеством всех подмножеств множества U и булевым кубом, где можно установить взаимнооднозначное соответствие, при котором операции объединения множества соответствует операции логического сложения (их характеристических векторов), операции пересечения множеств соответствует операция логического умножения их характеристических векторов, а операции дополнения – операция отрицания. Пустому множеству соответствует нулевой вектор, а универсальному – единичный.

Пример. Пусть, и. Характеристическими векторами множеств А, В,, и соответственно будут:. Полученные векторы позволяют легко выписать элементы множеств:.

Номером булевого вектора называется число его двоичного представления. Например, булев вектор а из предыдущего примера имеет номер 10101.

Два булевых вектора называются соседними, если их координаты отличаются только в одном разряде (т.е. они отличаются только одной координатой).

Булев куб размерности 1

0 1

Булев куб размерности 2

Булев куб размерности 3

Для выражения взаимодействий и связей между элементами множеств в математике используется понятие отношения.

n – местным ( n – арным) отношением R на множествах называется любое подмножество прямого произведения этих множеств, то есть. Другими словами, элементы этих множеств связаны отношением R тогда и только тогда, когда n упорядоченных чисел.

Отношение называется n – местным на множестве А.

При отношение R задает фиксированный элемент множества А. При отношение R представляет собой подмножество множества А и называется унарным отношением или свойством. При отношение R называется бинарным или соответствием. При отношение тернарное и т. д.

В математике чаще всего используются бинарные отношение (соответствия). В дальнейшем рассматриваются в основном только такие отношения и при этом слово “бинарные” опускается.

Пусть А и В – два множества. Соответствием или (бинарным) отношением из множества А в множество В называется подмножество R прямого произведения, т.е.. Если aÎA, bÎB, находятся в отношении, то пишут: (a,b)ÎR или R(a,b), а также в инфиксной форме aRb. При этом говорят, что b соответствует a при соответствии R или b находится в отношении R с a. Если R=Æ, то отношение называют пустым. Отношение называют полным. Для любого множества А определяется тождественное отношение -.

Принадлежность элементов а и b отношению R наглядно можно представить в следующем виде

Областью определения (DomR) соответствия R, называется множество элементов aÎA, для каждого из которых, найдется хотя бы один элемент bÎB, такой, что aRb.

Областью значения (ImR) соответствия R называется множество элементов bÎB, для каждого из которых, найдется хотя бы один элемент aÎA, такой, что aRb.

Соответствие R называется всюду определенным, если DomR=A, в противном случае – частично определенным. Соответствие называется сюръективным, если ImR=B.

Для каждого aÎA, множество элементов bÎB таких, что aRb называется образом элемента aÎA относительно R и обозначается im_Ra.

Прообразом элемента bÎB относительно R, называется множество элементов aÎA, таких, что aRb. Прообраз обозначается: coim_Rb

Заметим, что и.

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

Отношения, определенные на конечных множествах, могут быть заданы:

1) Списком, т.е. перечислением тех пар элементов, для которых это отношение выполнено. Например, если A= { a,b,c } и B= { x,y }, то R= {(a,x), (a,y), (b,y), (c,x)}.

2) Матрицей [ R ] размерности, элементы которой т.е. строки этой матрицы помечаются элементами из A, а столбцы – элементами из B, а на пересечении строки a _i со столбцом b _i стоит единица (1), если aRb; и нуль (0), - в противном случае. Тогда для выше приведенного примера имеем матрицу

	x	y
a
b
c

3)

x

y

a

b

c

Графиком на координатной плоскости, горизонтальная и вертикальная оси которой представляют элементы множеств А и В соответственно.

4) Графом, в котором элементы множеств А и В изображаются точками на плоскости. Причем эти точки обозначаются теми же символами, что и соответствующие элементы. Точки a и b соединяются направленным отрезком от a к b, если aRb. Например, для предыдущего случая отношение R изображается ориентированным графом.

Дата добавления: 2014-01-11