Дополнение множества
Лекция 2: «Теория булевых функций. Булева алгебра»
Определение:
Множество M с двумя введенными бинарными
операциями (& V), одной унарной операцией
(
)
и двумя выделенными элементами называется
булевой алгеброй, если выполнены
следующие свойства (аксиомы булевой
алгебры). Названия операций пока не
введены.
X & Y = Y&X, X V Y = Y V X – коммутативность.
(X & Y) & Z = X & (Y & Z), (X V Y) V Z = X V (Y V Z) – ассоциативность.
(X V Y) & Z = (X & Z) V (Y & Z), (X & Y) V (Y & Z) = (X V Z) & (Y & Z) – дистрибутивность.
Поглощение – X & X = X, X V X = X.
Свойства констант
X & 0 = 0
X & I = X, где I – аналог универсального множества.
Инвальтивность (двойное отрицание)
.Дополнимость X V
= I, X &
= 0.Законы двойственности – (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 = {, 2 ..n)
n = [P(U)]
i = 1, если ai <- A (принадлежит).
i = 0, если ai не принадлежит A.
U = {1 2 3 4 5 6 7 8 9}
A = {2 4 6 8}
B = {1 2 7}
A = {0 1 0 1 0 1 0 1 0}
B = {1 1 0 0 0 0 1 0 0}
или
A = 010101010 – скобки не нужны
A= 110000100
Характеристические векторы размерностью n называются булевыми векторами.
Они располагаются в вершинах n – мерного булева куба.
Номером булевого вектора является число в двоичном представлении, которым он является
1101 – номер.
Два булевых вектора называются соседними, если их координаты отличаются только в одном разряде (если они отличаются только одной координатой).
Совокупность всех булевых векторов размерности n называется булевым кубом размерностью Bn.
Б
0 1
улев куб размерности 1
Булев куб размерности 2
00
01
10
11
Б
улев
куб размерности 3
001
011
111
101
000
010
100
110
0 – нулевой вектор.
I
Логическое умножение
– вектор из одних единиц.
X Логическое сложение Y |
X&Y |
X V Y |
00 |
0 |
0 |
01 |
0 |
1 |
10 |
0 |
1 |
11 |
1 |
1 |
Отрицание
X = 0 Y = 0
_ _
Х = 1 Y= 1
Для размерности n операции над векторами производятся покоординатно.
Логическая сумма двух векторов – вектор, координаты которого являются логическими суммами соответствующих исходных векторов. Аналогично определено произведение.