Как найти булев вектор

Двоичным
(булевым) n-мерным
вектором
называют набор из n
чисел (b₁, b₂, …, b_n),
каждое из которых может принимать только
значения в двоичной системе счисления
– 0
или 1.

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

Например,
если
= (0, 1, 1, 1, 0, 1),
то
= (1, 0, 0, 0, 1, 0).

Если
в записи двоичного вектора
длиныn
устранить запятые, его можно рассматривать
как двоичную запись некоторого целого
числа. Наименьшим таким числом является
0.
Ему соответствует
вектор
= (0, …, 0).
Наибольшим является число 2ⁿ – 1,
которому соответствует вектор
=(1, …, 1).
Следовательно, при помощи полного набора
двоичных векторов
длиныn
можно записать все 2ⁿ
целых чисел из отрезка
[0, 2ⁿ – 1].
Такие числа называют порядковыми
номерами
векторов.
Их используют как в двоичном виде, так
и в десятичной системе счисления.

Пример 1.
Найти
порядковый номер булева вектора
=(1,
0,
0,
1,
0,
1)
в десятичной системе счисления.

Решение.
Устраняя запятые в векторе, получим
двоичную запись 100101₂.
Переводя ее по правилу 2.1.1 в десятичную
систему счисления, получим:

100101₂ = 1  2⁵ + 1  2² + 1  2⁰ = 32₁₀ + 4₁₀ + 1₁₀ = 35₁₀.

Ответ:десятичный порядковый номер заданного
булева вектора равен35₁₀.

В качестве меры
близости булевых векторов используют
расстояние
Хэмминга.

Определение. Расстоянием
Хемминга 
между булевыми векторами 
ⁿ и
ⁿ
называют величину 
(
ⁿ, 
ⁿ),
которая равна числу координат,
по которым различаются векторы 
ⁿ и
ⁿ.

Пример 8. 

(100011, 110011)=1,

(0101, 1010)=4.

Определение.
Булевы векторы
ⁿ и
ⁿ ,
различающиеся ровно по одной координате
(  (ⁿ,
ⁿ)
= 1), называют
соседними.

Рассмотрим
наиболее употребительные геометрические
интерпретации булевых n
– мерных векторов.

1. Представление
в виде двоичных чисел.
Если в записи вектора bⁿ
устранить запятые, ее можно рассматривать
как двоичную запись некоторого целого
числа. Наименьшим таким числом является
0. Ему соответствует
вектор bⁿ
=(0, …, 0).
Наибольшим является число 2ⁿ
– 1, которому
соответствуетbⁿ
= (1, …, 1).
Следовательно, при помощи векторов bⁿ
можно
записать все 2ⁿ
целых чисел из интервала [0, 2ⁿ
– 1].
Такие числа будем называть порядковыми
номерами
векторов.

Лексикографическим
называют такой порядок векторовbⁿ,
когда соответствующие им двоичные числа
расположены по возрастанию от 0 до 2ⁿ
– 1.

В
качестве примера рассмотрим полное
множество 3-мерных двоичных векторов,
расположенных в лексикографическом
порядке:

0 (0, 0, 0), 4 (1, 0, 0),

1 (0, 0, 1), 5 (1, 0, 1),

2 (0, 1, 0), 6 (1, 1, 0),

3 (0, 1, 1), 7 (1, 1, 1).

2. Бинарное
дерево Тⁿ.
Сопоставим множеству всех 2ⁿ
векторовbⁿ
следующую древовидную структуру,
начинающуюся
в корневой
вершине О
(вершине
нулевого уровня).
Из нее выходят вниз два отрезка (ребра),
соответствующие значениям b₁=0
(влево) и
b₁=1
(вправо) и
оканчивающиеся вершинами
первого уровня.
Из них выходят вниз по два ребра,
соответствующие b₂=0
(влево) и
b₂=1
(вправо) и
оканчивающиеся новыми вершинами
— второго
уровня и т.
д. Процесс завершается построением всех
вершин n-го
уровня.
Данная структура называется
бинарным
деревом и
обозначается
Тⁿ.
На рис. 4.1
показано
дерево Т³
для 3-мерного
булевого вектораb³
=
(х,
у, z).

Рис. 4.1.
Бинарное дерево Т³

Пронумеруем
слева направо все вершины n-го
уровня от 0
до
2ⁿ
– 1. Каждому вектору bⁿ
можно однозначно поставить
в
соответствие путь из корневой вершины
О
в вершину n–го
уровня с порядковым номером вектора
bⁿ.
Например, вектору (0,1,0)
в рассмотренном
примере соответствует путь из корневой
вершины в вершину 2 (010₂
= 2₁₀)
по ребрам х
= 0,
у = 1,
z = 0.
Таким образом, бинарное дерево полностью
описывает все 2ⁿ
векторовbⁿ.

3. Единичный
n-мерный
куб Вⁿ.
Единичным n-мерным
кубом называют полный набор вершин,
соответствующих векторамbⁿ,
в котором каждые две соседних вершины
(которым соответствуют векторы,
различающиеся ровно по одной координате)
соединены отрезком (ребром).
Обозначается единичный n-мерный
куб как Вⁿ.
На рис. 4.2 показаны кубы В¹,
В²,
а также плоские проекции кубов В³,
В⁴.

Определение.
Дана вершинаⁿ
в Вⁿ.
Множество вершин Вⁿ
{ⁿ},
для которых  (ⁿ,ⁿ)
=
r, называют
сферой радиуса
r. Множество
{ⁿ}
вершин Вⁿ,
для которых (ⁿ,ⁿ)

r, называют
шаром радиуса
r.

Рис. 4.2. Единичные
n-мерные
кубы В¹,
В² и
плоские проекции кубов В³,
В⁴

Вопросы для
проверки знаний.

1. Есть ли
принципиальное различие правил выполнения
сложения и вычитания в десятичной
системе счисления и других системах с
постоянными основаниями?

2. Какой формат
компьютерного представления чисел
называют беззнаковым целым числом?

3. Какой формат
компьютерного представления чисел
называют целым числом со знаком?

4. Какой способ
компьютерного представления целых
чисел называют прямым кодом?

5. Какой способ
компьютерного представления целых
чисел называют дополнительным кодом?

6. Для каких целых
чисел прямой код совпадает с дополнительным
кодом?

7.
Может ли целое число занимать в электронной
памяти а) 4
бита, б) 6 бит, в) 8
бит, г) 10
бит?

8. По каким правилам
осуществляется перевод беззнаковых
байтовых целых чисел из прямого кода в
дополнительный и обратно?

9. По каким правилам
осуществляется перевод байтовых целых
чисел со знаком из прямого кода в
дополнительный и обратно?

10. В каких случаях
вычитание байтовых беззнаковых целых
чисел дает результат в прямом коде, а в
каких – в дополнительном?

11.
Что называют двоичным (булевым) n-мерным
вектором?

12. Какую операцию
называют инвертированием булевого
вектора?

13. Какие числа
называют порядковыми номерами булевых
векторов?

14. Что называют
лексикографическим порядком двоичных
векторов?

Практические
задания.

1.
Сложить в системе с основанием 16
числа 23301₄
и 1435₈.

2.Сложить
в восьмеричной системе числа 101101101₂
и 9СВ₁₆.

3.
Выполнить вычитание (192 – 103)
байтовых беззнаковых чисел с использованием
дополнительного кода.

4.
Найти порядковый номер двоичного вектора
(0,
0,
1,
0,
1,
1,
0)
в десятичной системе счисления.

5.
Упорядочить по возрастанию порядковых
номеров булевы векторы длины 5:
(0,
0,
1,
0,
1),
(0,
1,
1,
0,
1),
(1,
0,
1,
0,
0).

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

1. Дискретная математика

Лекция 3. Булевы константы и
вектора

2. Булевы константы

• Булевыми константами называются
символы: 0 и 1.
• Символы 0 и 1 могут интерпретироваться как
числа: ноль и единица, знаки: минус и плюс,
потенциалы: низкий и высокий, высказывания:
ложь и истина, и многое другое.
• Булевым множеством B называется
множество булевых констант, т.е. B = { 0, 1 }.

3. Булев вектор

• Булев вектор — это последовательность
конечного числа булевых констант,
называемых компонентами булева вектора.
• Договоримся обозначать булевы векторы
греческими буквами, а компоненты вектора —
латинскими с указанием номеров
компонент.
• Примеры. = a1 a2 … an = 010101,
=b1b2 … bn=11110000.
• Длиной булева вектора назовем количество
его компонент, а весом вектора —
количество компонент, равных единице.
• Пример. Длина булева вектора = 101010
равна шести, а вес — трем.

4. Теорема о числе булевых векторов

• Теорема. Число различных булевых векторов
длины n равно 2n .
• Доказательство (методом математической индукции по длине
булева вектора).
• База индукции. При n = 1 утверждение выполняется (число
различных булевых векторов длины 1 равно двум: это 0 и
1).
• Предположение. Пусть число различных булевых векторов
длины n равно 2n .
• Вывод. К булевым векторам длины n добавим n +1- ю
компоненту, присвоив ей сперва значение 0 (получим 2n
векторов длины n +1), затем — значение 1 (получим еще 2n
векторов длины n +1), т.е. всего 2n + 2n = 2n+1 различных
векторов длины n +1. ЧТД.

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

6. Пара булевых векторов

Рассмотрим булевы векторы = a1 a2 … an и = b1 b2 … bn .
Говорят, что булевы векторы и ортогональны по i-й компоненте,
если ai bi .
Пример. Булевы векторы = 1010 и = 1000 ортогональны по 3-й
компоненте.
Расстоянием между булевыми векторами (расстоянием по Хэммингу)
называют число ортогональных компонент в данной паре векторов.
Пример. Расстояние по Хэммингу между булевыми векторами = 1010 и =
1001 равно двум.
Булевы векторы называются соседними (соседями), если они ортогональны по
одной и только одной компоненте.
Пример. Булевы векторы = 1010 и = 1000 соседние.
Булевы векторы называются противоположными (антиподами), если они
ортогональны по всем компонентам, т.е. расстояние по Хэммингу между
булевыми векторами равно их длине.
Пример. Булевы векторы = 1010 и = 0101 противоположные.

7. Пара булевых векторов

8. Булево пространство и способы его представления

• Булевым пространством B n размерности n называется
множество всех булевых векторов длины n, расстояние
между которыми вычисляется по Хэммингу.
• Примеры. B 1 = {0,1} = B ,
B 2 = {00,01,10,11}.
• Способы представления:
• 1) Явным перечислением векторов.
• Пример. B 3 = {000, 001, 010, 011, 100, 101, 110, 111}.
• 2) Матрицей в коде Грея. Булево пространство
размерности n представляется матрицей, состоящей из 2a
строк и 2b столбцов, где a и b — целые числа, такие
что a + b = n. Строкам матрицы поставлены в соответствие
булевы векторы длины a (их называют кодами строк), а
столбцам — булевы векторы длины b (коды столбцов).

9. Пример матрицы Грея

Пусть n = 5 . На левой матрице показан процесс построения кодов столбцов.
Выделенная клетка задает булев вектор 10011.
Договоримся изображать коды условно: 1 – черточкой, 0 – ее отсутствием.
Такой код более нагляден и быстрее рисуется.
Код Грея обладает свойством симметрии. Места смены значений компонент
называются осями симметрии компонент.
Каждая ось имеет свою зону симметрии, т.е. область, на которую
распространяется ее действие:
зоной симметрии осей младших компонент строк и столбцов (в примере:
первой и третьей) является вся матрица;
зонами симметрии осей следующих компонент (в примере: второй и
четвертой) являются половины матрицы;
и так далее (с каждым разом размер зоны уменьшается в два раза).

10. Интервал в булевом пространстве

11. Крайние случаи. Мощность интервала

• Крайние случаи:
• I (010, 010) = 010, границы интервала совпадают, он состоит из
одного булева вектора, ранг r = 3, размерность s = 0;
• I (000, 111) = — — — , интервал — все булево пространство B 3,
ранг r = 0, размерность s = 3.
• Утверждение о мощности интервала. Мощность интервала
размерности s равна 2s.
• Доказательство. Так как интервал состоит из булевых
векторов со всевозможными комбинациями нулей и единиц во
внутренних компонентах, а внутренние компоненты образуют
булев вектор длины s, то число таких векторов равно 2s.
• Примеры. Мощность интервала -0- = {000, 001, 100, 101} равна
22 = 4, интервала1-1 = {101, 111 } равна
21 = 2, интервала 101 равна 20 = 1.

12. Алгоритм распознавания интервала

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

• Интервалы I1, I2 называют соседними интервалами (соседями), если они
совпадают по номерам внешних компонент, но различаются по значению
одной из внешних компонент. Ее называют ортогональной компонентой,
а интервалы I1, I2 — соседями по данной компоненте.
• Примеры. Интервалы I1 = 11- и I2 = 01- — соседи (по первой
компоненте);
интервалы I1 = 01- и I2 = 10- — не соседи (различаются по двум
внешним компонентам);
интервалы I1 = 01- и I2 = 1-0 — не соседи (различаются по номерам
внешних компонент).
• Утверждение о соседних интервалах. Два соседних интервала ранга
r (размерности s) не пересекаются, но, объединяясь, образуют интервал
ранга r-1 (размерности s+1).
• Операцию объединения двух интервалов I1 и I2, соседних по i-й
компоненте, назовем склеиванием интервалов, а результат их склеивания (I
= I1 I2) — расширением интервалов I1 и I2 по i-й компоненте.
• Пример. Соседние интервалы I1 = 11-, I2 = 01- ранга 2 склеиваются,
образуя интервал I = -1- ранга 1 (он является расширением интервалов
I1 и I2 по первой компоненте).

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

Мы уже пользовались тремя способами представления интервалов.
1) Границами интервала.
2) Явным перечислением всех векторов, образующих интервал.
3) Троичным вектором.
4) Матрица Грея.
Булево пространство представляется матрицей, а все булевы
векторы (клетки), образующие интервал, выделяются.
• Чтобы нарисовать интервал, достаточно отметить все строки и все
столбцы, коды которых совпадают с заданным интервалом по
внешним компонентам — на их пересечении и будет лежать интервал.
• Пример. I = — 0-10 : отмечаем строки,
в кодах которых вторая компонента равна
0 (верхняя и нижняя строки), и столбцы,
в кодах которых четвертая компонента
равна1, а пятая — 0 (два средних
столбца ), — на их пересечении и
лежит заданный интервал.

15. Алгоритм распознавания интервала на матрице Грея

• Шаг 1: если количество клеток заданного
множества A не является целой степень (c)
двойки, то A — не интервал, идем на шаг 3.
• Шаг 2: если множество клеток (A) лежит
симметрично относительно c осей симметрии,
т.е. его можно “разрезать” осями симметрии на
половины, затем каждую половину на четвертины,
затем любую четвертину на осьмушки и так далее
до тех пор, пока множество A не “разрежется” на
отдельные клетки, то A — интервал, идем на шаг
3. иначе A — не интервал.
• Шаг 3: конец.

16. Примеры

На левой матрице интервал I = -0 — — 1 (8 клеток и 3 оси симметрии) , на
правой — не интервал (4 клетки, но одна ось симметрии).
Частные случаи
Очевидно, что интервалами являются следующие множества:
каждая отдельная клетка,
любая пара симметричных клеток, в том числе, рядом лежащих,
любая строка и любой столбец,
любая пара симметричных строк или столбцов, в том числе, рядом лежащих,
любой “квадрат” размером 2 2,
любая половина или четвертина матрицы,
четверка клеток, лежащих в углах матрицы.

17. Задачи

Определение.

Множество M с двумя введенными бинарными операциями (& V), одной унарной операцией (*) и двумя выделенными элементами называется булевой алгеброй, если выполнены следующие свойства (Аксиомы булевой алгебры). Названия операций пока не введены.

1. X & Y = Y&X, X V Y = Y V X – коммутативность.

2. (X & Y) & Z = X & (Y & Z), (X V Y) V Z = X V (Y V Z) – ассоциативность.

3. (X V Y) & Z = (X & Z) V (Y & Z), (X & Y) V (Y & Z) = (X V Z) & (Y & Z) – дистрибутивность.

4. Поглощение – X & X = X, X V X = X.

5. Свойства констант

X & 0 = 0

X & I = X, где I – аналог универсального множества.

6. Инвальтивность (X*)* = X

7. Дополнимость X V X* = I, X & X* = 0.

8. Законы двойственности – (X & Y)* = X* V Y*, (X V Y)* = X* & Y

Булева алгебра всех подмножеств данного множества.

U = {a1, a2… an)

[U] = N

[P(U)] = 2n

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

Oбъединение эквивалентно V, пересечение — &, дополнение — *, пустое множество – 0, а универсальное – I.

Все аксиомы булевой алгебры справедливы в операциях над множествами.

Булева алгебра характеристических векторов.

Пусть A <= U, A <- P(U) a- характеристический вектор этого подмножества.

AA = {a, a2 ..an)

N = [P(U)]

Ai = 1, если ai <- A (принадлежит).

Ai = 0, если ai не принадлежит A.

U = {1 2 3 4 5 6 7 8 9}

A = {2 4 6 8}

B = {1 2 7}

AA = {0 1 0 1 0 1 0 1 0}

AB = {1 1 0 0 0 0 1 0 0}

Или

AA = 010101010 – скобки не нужны

AA= 110000100

Характеристические векторы размерностью n называются булевыми векторами.

Они располагаются в вершинах n – мерного булева куба.

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

1101 – номер.

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

Совокупность всех булевых векторов размерности n называется булевым кубом размерностью Bn.

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

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

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

0 – нулевой вектор.

I – вектор из одних единиц.

Отрицание

X = 0 Y = 0

_ _

Х = 1 Y= 1

Для размерности n операции над векторами производятся покоординатно.

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

Утверждение

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

Следствие

Множество всех характеристических векторов является булевой алгеброй.

Булева алгебра высказываний (алгебра логики)

Высказыванием об элементах множества U называется любое утверждение об элементах множества U, которое для каждого элемента либо истинно, либо ложно.

U = {1 2 3 4 5 6 7 8 9}

A = «число четное»

B = «число, меньшее пяти»

Множеством истинности высказывания называется совокупность всех элементов, для которых это высказывание истинно.

SA = {2 4 6 8}

SB = {1 2 3 4}

Высказывание, для которого множество истинности пусто, называется тождественно ложным, а для которого SB = U называется тождественно истинным.

Высказывания, для которых множества истинности совпадают, называются тождественными или равносильными.

Равносильные высказывания объединим в один класс Р. В. и не будем их разделять, т. к. все они имеют одно и то же множество истинности.

Операции над высказываниями

Дизъюнкция высказываний (V, ИЛИ, OR)

Дизъюнкция высказываний – высказывание, истинное тогда, когда истинно хотя бы одно из высказываний.

Конъюнкция высказываний (&, И, AND).

Конъюнкцией высказываний называется высказывание, истинное тогда и только тогда, когда истинны все высказывания.

Отрицание высказываний (- над буквой, НЕ, NOT).

Отрицанием высказывания называется высказывание, истинное только тогда, когда исходное высказывание ложно.

Л – ложно.

И – истинно.

Утверждение (основа всей алгебры логики)

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

Следствие. Множество классов эквивалентных высказываний является булевой алгеброй.

Теорема

Существуют 3 булевых алгебры:

1. P(U)

2. Bn

3. Множество классов эквивалентных высказываний.

Три булевых алгебры являются изоморфными, если между их элементами можно установить такое однозначное соответствие, при котором операции сохраняются.

Договоримся конъюнкцию обозначать точкой (как знак умножения в алгебре чисел). Конъюнкция выполняется раньше дизъюнкции (аналог выполнения операций сложения и умножения в алгебре чисел).