Булевы функции. Анализ и синтез булевых функций

Булевой (логической) функцией называется произвольная функция булевых переменных, связанных между собой операциями И, ИЛИ и НЕ. Поэтому в аналитическом виде булева функция записывается через основные операции, символьные обозначения которых приведены в таблице 1.

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

Набор записывается в виде последовательности переменных и может отождествляться (рассматриваться) как - разрядное двоичное число, так как каждая переменная равна нулю или единице.

В случае переменных можно построить различных наборов, то есть комбинаций из нулей и единиц. Для каждого набора булева функция принимает только одно из двух возможных значений: лог. 0 или лог. 1, поэтому ее часто называют двоичной, переключательной функцией.

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

В первые столбцов и строк в произвольном порядке записываются все возможные наборы переменных из 0 и 1.

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

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

Таблицы истинности трех основных логических функций ИЛИ, И, НЕ, а также двух сдвоенных из них функций ИЛИ-НЕ и И-НЕ для любого количества аргументов можно построить по их словесному определению, данному выше.

В частном случае двух переменных и таблица имеет строки. Таблицы истинности пяти перечисленных выше функций для двух переменных сведены в одну таблицу 3.

Таблица 3

		ИЛИ	И	НЕ	ИЛИ-НЕ	И-НЕ

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

.

(3)

Это функция двух переменных, поэтому таблица имеет 4 строки, три столбца и выглядит так:

Предлагается проверить построение таблицы 4 самостоятельно.

Сравнение полученной таблицы с таблицей функции ИЛИ (третий столбец таблицы 3) показывает, что они совпадают за исключением последней строки, когда обе переменные равны 1. Поэтому функцию (3) называют «исключающее ИЛИ» (XOR).

Можно интерпретировать полученную таблицу иначе, заметив, что первые три строки совпадают с результатом арифметического сложения двух двоичных цифр (0 и 1) до тех пор, пока обе эти цифры не равны 1. Поэтому функцию (3) называют еще «сложение по модулю два».

Поскольку функция (3) встречается часто, ей присвоен особый символ – . В этих обозначениях функция (3) записывается так:

.

В булевой алгебре существуют алгоритмы, позволяющие решать обратную задачу, а именно, получать булеву функцию в аналитическом виде по заданной таблице истинности. Существование таких алгоритмов имеет огромное практическое значение, так как позволяет создавать логические схемы, выполняющие заданное преобразование двоичных сигналов. Один из таких алгоритмов подробно рассмотрен ниже в разделе 5.2.6.2 «Синтез комбинационных схем».