Утверждение о мощности интервала.

Представление булевыми векторами подмножеств

Пусть заданы множество M = {m₁, m₂, ... , m_n} и подмножество A Í M. Построим булев вектор a = a₁ a₂ ... a_n, представляющий подмножество A, по следующему правилу:

ì 1, если m_i Î A;

a_i = í

î 0, если m_i Ï A.

Примеры.В множестве M = {2, 6, 4, 7, 8 }
булев вектор a = 11101 выделяет подмножество четных чисел,
булев вектор b = 10010 выделяет подмножество простых чисел.

Представление булевыми векторами целых неотрицательных чисел

Введем следующее соответствие между булевыми векторами длины n и числами 0, 1, ... , 2ⁿ -1: пусть булев вектор a = a₁ a₂ ... a_n соответствует числу

a = a_i ´ 2^{n - i}

a_i принимает значение 0 или 1.

Пример. Задан булев вектор a = 1001; подставив его компоненты в формулу, получим число: a = 1´2³ + 0´2² + 0´2¹ + 1´2⁰ = 8 + 1 = 9.

2. Булев вектор, расстояние между булевыми векторами, отношение предшествования.

Булев вектор — это последовательность конечного числа булевых констант, называемых компонентами булева вектора.

Булев вектор обозначают греческими буквами, а компоненты вектора — латинскими с указанием номеров компонент.

Пример: a = a₁ a₂ ... a_n = 010101,

b = b₁ b₂ ... b_n = 11110000

Определение. Говорят, что булевы векторы a и b ортогональны по i‑й компоненте, если a_i ¹ b_i .

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

Булевы векторы называются соседними,если они ортогональны по одной и только одной компоненте.

Булевы векторы называют противоположными (антиподами), если они ортогональны по всем компонентам.

Булев вектор a = a₁ a₂ ... a_n предшествуетбулеву вектору b = b₁ b₂ ... b_n (обозначают a £ b), если для любого i = 1, 2, ... , n выполняется условие: a_i £ b_i . В этом случае также говорят, что булев вектор b следует за булевым вектором a, булев вектор a называют предшественником, а b - последователем.

Пример. Расстояние по Хэммингу между булевыми векторами a = 1010 и b = 1001 равно двум.

Пример.a = 1010, b = 1110: a £ b.

3. Булево пространство, способы задания булева пространства.

Булевым пространством Bⁿ размерности n называется множество всех булевых векторов длины n, расстояние между которыми вычисляется по Хэммингу.

1) Явным перечислением векторов.

Пример. B ³ = {000, 001, 010, 011, 100, 101, 110, 111}.

2) Матрицей в коде Грея. Булево пространство размерности n представляется матрицей, состоящей из 2^s строк и 2^p столбцов, где s и p — целые числа, такие что s + p = n и s = p либо s = p - 1. Строкам матрицы поставлены в соответствие булевы векторы длины s (их называют кодами строк), а столбцам — булевы векторы длины p (коды столбцов).

Элемент матрицы, стоящий в i – й строке и j – м столбце, задает булев вектор, который получается приписыванием к коду строки i кода столбца j.

Можно задавать матрицу в позиционном коде, или матрицей Грея.

Пример. Пусть n = 5. Тогда a = 2, b = 3, строк 2² = 4, столбцов 2³ = 8.

Выделенная клетка задает булев вектор 10011. На левой матрице показан процесс построения кодов столбцов.

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

На правой матрице пунктирными линиями обозначены места смены значений компонент, эти линии называются осями симметрии компонент.

Нетрудно заметить, что пара соседних векторов располагается в матрице симметрично относительно оси той компоненты, по которой векторы ортогональны.

4. Интервал в булевом пространстве, утверждение о мощности интервала, способы задания интервала.

Пусть задана пара векторов одинаковой длины: a = a₁ a₂ ... a_n и b = b₁ b₂ ... b_n .

Интервалом I (a,b) в булевом пространстве B ⁿ, заданным парой булевых векторов a и b, таких что a £ b, называется множество всех булевых векторов g длины n, удовлетворяющих условию a £ g £ b, т.е. I (a,b) = {g Î Bⁿ : a £ g £ b}. Булевы векторы a и b называются границами интервала, вектор a - наименьшим элементом интервала, а b - наибольший элемент.

Пример. I (000,011) = {000, 001, 010, 011}.

Утверждение о мощности интервала.

Мощность интервала размерности s равна 2^s .

Доказательство. Так как интервал состоит из булевых векторов со всевозможными комбинациями нулей и единиц во внутренних компонентах, а внутренние компоненты образуют булев вектор длины s, то число таких векторов (Теоремао числе булевых векторов: Число различных булевых векторов длины n равно 2ⁿ) равно 2^s.

Определение.Компоненты, по которым границы (а значит и все векторы интервала) совпадают, называются внешними компонентами интервала, остальные – внутренними. Число внешних компонент называется рангоминтервала (r), а число внутренних – его размерность(s).

Пример: Мощность интервала – 0 – равна 2² = 4, мощность интервала 101 равна 2⁰ = 1.

Способы задания интервалов

1) Границамиинтервала.

I (000,101) = {000, 001, 100, 101}, граница a = 000 – наименьший элемент, граница b = 101 – наибольшим.

I (010, 010) = 010, границы интервала совпадают, значит он состоит из одного

булева вектора.

I (000, 111) = - - - , интервал - все булево пространство B³,

2) Явным перечислением всех векторов, образующих интервал.

3) Троичным вектором.0 и 1 задают значения внешних компонент, а черточка внутренние компоненты.

Примеры.

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

Примеры.

5. Соседние интервалы. Утверждение о соседних интервалах.

Соседние интервалы

Рассмотрим пару интервалов булева пространства Bⁿ: I₁ (a₁, b₁) и I₂ (a₂, b₂) .

Интервалы I₁, I₂ называют соседними, если они совпадают по номерам внешних компонент, но различаются по значению одной из них; ее называют ортогональной компонентой, а интервалы I₁, I₂ - соседями по данной компоненте.

Примеры.Рассмотрим три пары интервалов

Интервалы I₁, I₂ являются соседями (по первой компоненте), I'₁, I'₂ не являются соседями (различаются по двум внешним компонентам), I''₁, I''₂ также не соседи (различаются по номерам внешних компонент).

Не нашли, что искали? Воспользуйтесь поиском по сайту: