Основные понятия и факты, связанные с булевым кубом

В дальнейшем в качестве множества будет использоваться множество .

Набор , где , называется булевым или двоичным набором (вектором). Элементы набора называют компонентами или координатами. Число называют длиной набора. Кратко обозначают или . Весом (или нормой) набора называют число его координат, равных 1, т.е. . Число называют номером набора .

Замечание. Набор есть разложение числа в двоичной системе и находится следующим образом: а) делим на 2, остаток есть частное ; б) делим на 2, остаток есть частное ; и т.

Множество всех булевых векторов длины называется -мерным кубом (). Сами векторы называются вершинами -мерного куба.

Кроме обозначения для -мерного куба используют обозначение , а наборы называют вершинами куба .

Геометрическая реализация. На рисунке 1.1. изображены проекции 1-мерного, 2-мерного, 3-мерного и 4-мерного кубов на плоскость.

Пусть фиксированный набор чисел из 0 и 1 (). Множество всех вершин куба таких, что , называется -мерной гранью.

Замечание. -мерная грань является -мерным подкубом куба .

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

Вершины и куба – соседние, если , и противоположные; если .

Говорят, что набор предшествует набору (обозначают ), если для всех . Если и , то говорят, что набор строго предшествует набору и обозначают . Наборы и называют сравнимыми, если либо либо .

Функция такая, что , называется булевой функцией (или функцией алгебры логики) от переменных.

Замечание. Булевы функции являются удобными для описания, анализа и синтеза переключательных схем, выходные сигналы которых характеризуются лишь двумя уровнями напряжения: высоким (1) и низким (0). Поэтому в практических приложениях их еще называют переключательными.

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

Табл. 1.1.

0	0		0	0
0	0		1	1
0	0		1	0
0	1		1	1
1	1		1	1

При стандартном расположении наборов (в соответствии с увеличением их номера), функцию можно задавать вектором ее значений (или ), где координата равна значению функции в -ой строке таблицы (), т.е.

Обозначим через множество всех булевых функций от переменных, а множество всех булевых функций.

Теорема. .

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