Двоичные переменные и булевы функции

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

Двоичные переменные могут принимать только два значения 0 (ложь) и 1 (истина), и обозначаются символами x₁, x₂, … , x_n. Двоичные (логические, булевы) переменные являются аргументами булевых (переключательных) функций.

Функция f, зависящая от n переменных x₁, x₂, ...., x_n, называется булевой, или переключательной, если функция f и любой из ее аргументов x_i, (i = 1...n) принимают значения только из множества {0, 1}.

Иначе говоря, булева функция – это функция, и аргументы и значение которой принадлежат множеству { 0, 1 }. Множество { 0, 1 } обозначим через B.

Булеву функцию от n аргументов можно рассматривать как n-местную алгебраическую операцию на множестве B. При этом алгебра <B;Ω>, где Ω – множество всевозможных булевых функций, называется алгеброй логики (булевой алгеброй).

Конечность области определения функции имеет существенное достоинство – такие функции можно задавать перечислением значений при различных значениях аргументов. Для того, чтобы задать значение функции от n переменных, надо определить значения для каждого из 2ⁿ возможных наборов. Эти значения записывают в таблицу истинности в порядке соответствующих двоичных чисел (рассмотрим позже).

x₁ x₂ ... x_n-1 x_n f

0 0 ... 0 0 f(0,0,...,0,0)

0 0 ... 0 1 f(0,0,...,0,1)

0 0 ... 1 0 f(0,0,...,1,0)

0 0 ... 1 1 f(0,0,...,1,1)

... ... ... ... ... ...

1 1 ... 0 0 f(1,1,...,0,0)

1 1 ... 0 1 f(1,1,...,0,1)

1 1 ... 1 0 f(1,1,...,1,0)

1 1 ... 1 1 f(1,1,...,1,1)

Для того, чтобы задать функцию достаточно выписать значения f(0,0,...,0,0), f(0,0,...,0,1), f(0,0,...,1,0), f(0,0,...,1,1),..., f(1,1,...,0,0), f(1,1,...,0,1), f(1,1,...,1,0), f(1,1,...,1,1). Этот набор называют вектором значений функции.

Таким образом, булевы функции на конечном множестве своих аргументов могут принимать значения 0 и 1 и обозначаются f(x₁,x₂, … ,x_n). Булевы функции могут служить аргументами более сложных логических функций.