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

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

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

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

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

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

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

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

Рис. 9

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

Рис. 10

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

Рис. 11

3.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 наглядно можно представить в следующем виде

Рис. 12

Областью определения (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), - в противном случае. Тогда для выше приведенного примера имеем матрицу

Таблица 6

	x	y
a	1	1
b	0	1
c	1	0

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

Рис. 13

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

Рис. 14