Логические основы вычислительной техники

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

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

Двоичные переменные могут принимать только два значения: 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 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). Булевы функции могут служить аргументами более сложных логических функций.