Булев куб

По определению, булев куб размерности n есть множество Вⁿ ={<x₁,x₂,…,x_n>|x_k=0,1; k=1,2,…,n}. Элементы (точки) булева куба принять записывать в виде последовательности нулей и единиц, без запятых и скобок: x₁x₂…x_n.

ê Булев куб является частично упорядоченным множеством:

a ´ b Ç а_i ≤ b_i для всех i=1,n.

ê Вектора 0 = (0, …,0) и 1 = (1,…,1) являются наименьшим и наибольшим элементами куба.

ê Этот порядок будем называть булевым порядком.

ê Булев куб с таким упорядочиванием является полной дистрибутивной решёткой.

ê Полная дистрибутивная решётка в то же время является и алгеброй типа <2,2,1>.

Алгеброй Буля называется алгебра, операции которой удовлетворяют следующим свойствам:

ê Простейшая алгебра Буля B = (B; Ú, Ù,) имеет носителем двухэлементное множество B={0,1}, {Л, И} {F,T}, {^,¨}.

ê n–мерный булев куб является алгеброй Bⁿ = (Bⁿ; Ú, Ù,, 0,1).

ê n–мерный булев куб является полной дистрибутивной решёткой.

ê Алгебру Bⁿ можно интерпретировать как векторное пространство над полем (B; Ú, Ù).

ê Алгебра Bⁿ изоморфна алгебре (2^U;Ç,È,¯,Æ,U) с n–элементным множеством U.

Точки булева куба представляются последовательностью (словом) длины n. Интерпретация этого слова как двоичного числа является нумерацией и, следовательно, задаёт на кубе линейный порядок, отличный от булева. Будем его называть числовым порядком.

n-мерный булев куб состоит из 2ⁿ элементов. Конечное число точек всегда можно изобразить на плоскости – т.е. булев куб произвольной размерности можно изображать графически.

Рассмотрим примеры.

n=0 n=1. – Двухэлементное множество, диаграмма Хассе которого имеет вид:

n=2. Булев квадрат имеет четыре элемента, изображаемые диаграммой:

n=3. Трёхмерный булев куб изображается следующим образом:

n=4. Четырёхмерный куб можно изобразить следующим образом:

Этот же куб часто изображают в виде ориентированной сети. Линии сети соединяют элементы куба, находящиеся в отношении доминирования, а каждый слой (уровень) сети состоит из элементов антицепи.

Грани булева куба.

Если в определении булева куба, т.е. множества всех двоичных векторов длины n, зафиксировать некоторую компоненту, скажем, k-ую, мы получим множество из 2^n-1 элементов, которое будет изоморфно кубу размерности n–1. Это множество называется подкубом, или гранью, размерности n–1.

На подкубе индуцируется частичный порядок.

Номер зафиксированной компоненты называется направлением грани. Всего можно зафиксировать n различных компонент – говорят об n способах вложения или о соответствующем числе граней.

Продолжая процедуру фиксации компонент куба k раз, получим грань (подкуб) размерности n–k, номера зафиксированных компонент 1≤i₁< … <i_k≤n, определяющие направление грани, и значения (σ₁, …, σ_k) зафиксированных компонент из множества {0,1}.

Грань размерности n–k – это множество наборов, имеющее не менее k одинаковых компонент. Грань данного куба задаётся: а) кортежем номеров (i₁, …,i_k) и б) значениями (σ₁, …, σ_k).

Ребро – это грань размерности 1, т.е. подмножество куба, состоящее из двух элементов, один из которых доминирует над другим.

Параллельные грани.