4.1. Способы задания булевой функции

Пусть х₁, х₂, ... , х_n – некоторые булевы переменные, т. е. переменные, принимающие значение из множества {0, 1}. Упорядоченную совокупность булевых переменных (х₁, х₂, ... , х_n) можно рассматривать как n‑компонентный булев вектор х. Число компонент вектора определяет его длину, или размерность. При фиксации значений всех переменных получается набор значений переменных (х₁, х₂, ..., х_n), задаваемый булевым вектором длины n, состоящим из констант 0 и 1. Очевидно, 2^п – число всех таких векторов. Они образуют булево пространство. Булевой функцией называется функция f : {0, 1}ⁿ  {0, 1}. Областью определения булевой функции является булево пространство М = {0, 1}ⁿ, областью значений – множество {0, 1}.

Задание булевой функции f на булевом пространстве М делит его на две части: M_f¹ – область, где функция принимает значение 1, и M_f⁰ – область, где функция принимает значение 0. Множество M_f¹ называется характеристическим множеством функции f.

Универсальным способом задания для любой дискретной функции является табличный способ. Таблица, представляющая функцию и называемая таблицей истинности, имеет два столбца. В левом столбце перечислены все наборы значений аргументов, в правом столбце – соответствующие им значения функции. Примером задания булевой функции от трех аргументов является табл. 4.1.

Таблица 4.1

Задание функции f(x₁, x₂, x₃)

Для задания булевой функции можно ограничиться перечислением элементов ее характеристического множества M_f¹. Множество M_f¹ задается булевой матрицей, строки которой представляют элементы этого множества. Следующая матрица, задающая приведенную выше функцию, является матричным способом представления булевой функции:

.

Компактность представления характеристического множества M_f¹ можно повысить, используя троичные векторы, компоненты которых могут принимать в качестве своих значений кроме символов 0 и 1 также символ «–». В этом случае значения булевой функции будут задаваться не на отдельных элементах, а на интервалах пространства переменных х₁, х₂, ..., х_n. Чтобы определить понятие интервала булева пространства, введем отношение  на множестве булевых векторов.

Булевы векторы а = (а₁, а₂, … , а_п) и b = (b₁, b₂, … , b_п) находятся в отношении  (а  b) и говорят, что а меньше b, если а_i  b_i  для любого i = 1, 2, … , п, в противном случае они несравнимы. При этом считается, что 0  1. Тогда интервалом булева пространства называется множество векторов, среди которых есть минимальный и максимальный векторы, а также все векторы, меньшие максимального и большие минимального. Интервал представляется троичным вектором, который задает множество всех булевых векторов, получаемых заменой символа «–» на 1 или 0.

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

,

которая представляет ту же булеву функцию f (x₁, x₂, x₃). Такой способ задания булевой функции называют еще интервальным. Представление булевой функции троичной матрицей не однозначно, т. е. для одной и той же булевой матрицы существует в общем случае не одна эквивалентная ей троичная матрица.

Две троичные матрицы эквивалентны, если они эквивалентны одной и той же булевой матрице, т. е. если они представляют одну и ту же булеву функцию.

Векторное задание булевой функции представляет собой булев вектор, компоненты которого соответствуют наборам значений аргументов. Эти наборы упорядочиваются обычно согласно порядку чисел, двоичные коды которых они представляют. Рассмотренная выше булева функция f(x₁, x₂, x₃) представляется вектором (0 1 1 1 0 1 0 1), показывающим, что функция принимает значение 0 на наборах (0 0 0), (1 0 0), (1 1 0) и значение 1 на наборах (0 0 1), (0 1 0), (0 1 1), (1 0 1), (1 1 1). Заметим, что этот вектор совпадает с правым столбцом табл. 8.1.

Если значения булевой функции определены для всех 2ⁿ наборов значений вектора x, она называется полностью определенной, в противном случае – не полностью определенной, или частичной. Задание не полностью определенной булевой функции f разбивает булево пространство на три множества: кроме M_f¹ и M_f⁰ в нем присутствует множество M_f ^–, где значения функции f не определены. Для задания частичной булевой функции необходимо задать не менее двух множеств. Обычно это M_f¹ и M_f⁰.

Далее будет рассмотрен алгебраический способ задания булевой функции.