Булевы функции

Двоичные векторы

Любое положительное целое число имеет единственное двоичное представление (в виде суммы неповторяющихся степеней числа 2). Например:

7=1+2+4; 35=32+2+1.

В общем случае, чтобы получить двоичное представление целого числа x>0, можно воспользоваться следующим соотношением:

x = α₀+2(α₁+2(α₂+…+2(α_n−2+2α_n−1)…),

где α₀ – остаток от деления x на 2 (то есть α₀=0, если x четно, и α₀=1, если x нечетно); α₁ – остаток от деления на 2 числа x₁=(x−α₀)/2; α₂ – остаток от деления на 2 числа x₂=(x₁−α₁)/2; и т.д. Тогда

x = α_n−1⋅2^n-1+α_n−2⋅2^n-2+…+α₁⋅2+α₀.

Числа α₀, α₁,…, α_n−1 называют двоичными цифрами числа x, а последовательность из нулей и единиц

α_n−1α_n−2…α₁α₀

– двоичной записью числа x. Пишут также

x = (α_n−1α_n−2…α₁α₀)₂.

Пример.

25=1+2⋅12=1+2⋅(0+2⋅6)=1+2⋅(0+2⋅(0+2⋅3))=

= 1+2⋅(0+2⋅(0+2⋅(1+2⋅1)),

откуда

25=1⋅1+0⋅2+0⋅4+1⋅8+1⋅16.􀀀

Самое большое число, которое можно записать с помощью n двоичных цифр, содержит в свой двоичной записи одни единицы. Это число равно

2^n-1+2^n-2+…+2+1=2ⁿ−1.

Декартову степень {0,1}ⁿ , n≥1, составляют всевозможные упорядоченные последовательности из нулей и единиц длины n. Мы будем называть такие последовательности n-мерными двоичными векторами.

Произвольному n-мерному двоичному вектору можно сопоставить неотрицательное целое число, двоичными цифрами которого служат компоненты вектора

(α₁,α₂,…,α_n)→ α₁⋅2^n-1+α₂⋅2^n-2+…+α_n-1⋅2+α_n.

Этим устанавливается взаимно однозначное соответствие между множеством всех n-мерных двоичных векторов и множеством неотрицательных целых чисел, меньших 2ⁿ. Таким образом, общее число n-мерных двоичных векторов равно 2ⁿ, то есть |{0,1}ⁿ|=2ⁿ.

Пример.При n=3 имеем:

(0,0,0) ↔ 0; (0,0,1) ↔ 1; (0,1,0) ↔ 2; (0,1,1) ↔ 3;

(1,0,0) ↔ 4; (1,0,1) ↔5; (1,1,0) ↔ 6; (1,1,1) ↔ 7.􀀀

Пусть α=(α₁,α₂,…,α_n) и β=(β₁,β₂,…,β_n) – двоичные векторы. Будем писать α≤β (или β≥α), если α_i≤β_i для всех i=1,2,…, n. Если α≤β, но α≠β, будем писать α<β (последнее означает, что α_i.≤β_i для всех i=1,2,…, n, и при этом хотя бы одно из этих неравенств строгое). Заметим, что имеются векторы α и β, для которых неверно ни α≤β, ни β≤α. Такие векторы будем называть несравнимыми.

Примеры.Двумерные двоичные векторы можно рассматривать как вершины единичного квадрата в двумерном евклидовом пространстве:

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

Векторы α и β связаны отношением ≤, если из вершины α можно пройти в вершину β по сторонам квадрата в направлении координатных осей (направо и вверх). Аналогично, трехмерные векторы соответствуют вершинам куба; векторы α и β связаны отношением ≤, если из вершины α можно пройти в вершину β по ребрам куба в направлении координатных осей.􀀀