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

Для задания произвольной булевой функции широко используются табличный (матричный) и аналитический способы. При табличном способе булева функция f (х₁,...,х_n) задается таблицей истинности (табл. 7), в левой части которой представлены все возможные двоичные наборы длины n, а в правой указываются значения функции на этих наборах.

Таблица 7

Под двоичным набором понимается совокупность значений аргументов х₁,х₂,...,x_n булевой функции f. Двоичный набор имеет длину n, если он представлен n цифрами из множества {0,1}. В табл. 7 представлены все двоичные наборы длиной 3. Иногда двоичные наборы из таблицы истинности булевой функции удобно представлять их номерами. Запишем аргументы х₁,х₂,...,x_n в порядке возрастания их индексов. Тогда любому двоичному набору можно поставить в соответствие целое десятичное число N, называемое номером набора. Например, двоичные наборы 011 и 101 имеют номера 3 и 5 соответственно. Булевы функции, зависящие от большого числа переменных, задавать таблицей истинности неудобно в силу ее громоздкости. Например, таблица истинности булевой функции 8 переменных будет содержать 2⁸ = 256 строк. Для задания функций многих переменных удобно использовать модификацию таблицы истинности. Рассмотрим способ построения такой таблицы истинности для функции n переменных. Множество из n переменных функции разбивается на два подмножества: х₁, х₂,..., х_j-1 и х_j, х_j+1,..., х_n. Переменными x₁, x₂,..., x_n отмечают строки таблицы истинности, задавая в каждой строке значение соответствующего двоичного набора длины j-1. Переменными x_j, x_j+i,..., x_n отмечают ее столбцы, задавая в каждом столбце значения соответствующего двоичного набора длиной n-j+1. Значение функции записывается в клетке на пересечении соответствующей строки и столбца (табл. 8).

При аналитическом способе булева функция задается формулой, то есть аналитическим выражением, построенным из операций булевой алгебры. Аналитический способ задания булевых функций занимает особое место в проектировании цифровых автоматов. Фактически все преобразования над булевыми функциями, необходимые для построения цифровых автоматов, ведутся на аналитическом уровне.

Таблица 8