Пусть заданы множество M = {m1, m2, ... , mn} и подмножество A Í M. Построим булев вектор a = a1 a2 ... an, представляющий подмножество A, по следующему правилу:
ì 1, если mi Î A;
ai = í
î 0, если mi Ï A.
Примеры.В множестве M = {2, 6, 4, 7, 8 } булев вектор a = 11101 выделяет подмножество четных чисел, булев вектор b = 10010 выделяет подмножество простых чисел.
Представление булевыми векторами целых неотрицательных чисел
Введем следующее соответствие между булевыми векторами длины n и числами 0, 1, ... , 2n -1: пусть булев вектор a = a1 a2 ... an соответствует числу
a = ai ´ 2n - i
ai принимает значение 0 или 1.
Пример. Задан булев вектор a = 1001; подставив его компоненты в формулу, получим число: a = 1´23 + 0´22 + 0´21 + 1´20 = 8 + 1 = 9.
2. Булев вектор, расстояние между булевыми векторами, отношение предшествования.
Булев вектор — это последовательность конечного числа булевых констант, называемых компонентами булева вектора.
Булев вектор обозначают греческими буквами, а компоненты вектора — латинскими с указанием номеров компонент.
Пример: a = a1 a2 ... an = 010101,
b = b1 b2 ... bn = 11110000
Определение. Говорят, что булевы векторы a и b ортогональны по i‑й компоненте, если ai ¹ bi .
Расстояниеммежду булевыми векторами называют число ортогональных компонент в данной паре векторов (его еще называют расстоянием по Хэммингу).
Булевы векторы называются соседними,если они ортогональны по одной и только одной компоненте.
Булевы векторы называют противоположными (антиподами), если они ортогональны по всем компонентам.
Булев вектор a = a1 a2 ... an предшествуетбулеву вектору b = b1 b2 ... bn (обозначают a £ b), если для любого i = 1, 2, ... , n выполняется условие: ai £ bi . В этом случае также говорят, что булев вектор b следует за булевым вектором a, булев вектор a называют предшественником, а b - последователем.
Пример. Расстояние по Хэммингу между булевыми векторами a = 1010 и b = 1001 равно двум.
2) Матрицей в коде Грея. Булево пространство размерности n представляется матрицей, состоящей из 2s строк и 2pстолбцов, где s и p — целые числа, такие что s + p = n и s = p либо s = p - 1. Строкам матрицы поставлены в соответствие булевы векторы длины s (их называют кодами строк), а столбцам — булевы векторы длины p (коды столбцов).
Элемент матрицы, стоящий в i – й строке и j – м столбце, задает булев вектор, который получается приписыванием к коду строки i кода столбца j.
Можно задавать матрицу в позиционном коде, или матрицей Грея.
Пример. Пусть n = 5. Тогда a = 2, b = 3, строк 22 = 4, столбцов 23 = 8.
Выделенная клетка задает булев вектор 10011. На левой матрице показан процесс построения кодов столбцов.
На правой матрице коды изображены условно: единица - черточкой, а ноль - ее отсутствием: такой код более нагляден, да и быстрее рисуется.
На правой матрице пунктирными линиями обозначены места смены значений компонент, эти линии называются осями симметрии компонент.
Нетрудно заметить, что пара соседних векторов располагается в матрице симметрично относительно оси той компоненты, по которой векторы ортогональны.
4. Интервал в булевом пространстве, утверждение о мощности интервала, способы задания интервала.
Пусть задана пара векторов одинаковой длины: a = a1 a2 ... an и b = b1 b2 ... bn .
Интервалом I (a,b) в булевом пространстве B n, заданным парой булевых векторов a и b, таких что a £ b, называется множество всех булевых векторов g длины n, удовлетворяющих условию a £ g £ b, т.е. I (a,b) = {g Î Bn : a £ g £ b}. Булевы векторы a и b называются границами интервала, вектор a - наименьшим элементом интервала, а b - наибольший элемент.
ai ´ 2n - i