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

Основными являются следующие способы представления булевых функций: табличный и аналитический.

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

Таблица 1. Таблица истинности булевой функции

00…00
00…01
00…10
…	…
11…10
11…11

В качестве примера в таблице 2 задана функция от трех переменных, которая равна 1, нечетное количество переменных равно 1, и 0 – в остальных случаях.

Таблица 2. Пример задания булевой функции

Отметим, что наборы значений аргументов в таблице записывают в естественной форме, то есть -ый по порядку набор представляет собой двоичную запись числа , =0, 1, 2, …, .

Обозначим через систему всех булевых функций от переменных. Число всех функций из равно числу перестановок с повторениями значений функции {0, 1} на выборке из входных наборов переменных, то есть .

Следует отметить, что числа с ростом быстро растут:

Следовательно, уже при сравнительно небольших значениях () перебор функций из данного множества становится практически невозможен даже с использованием вычислительной техники. Кроме того, с ростом числа аргументов таблица истинности сильно усложняется. Так, например, уже при не очень большом числе аргументов, скажем при =10, таблица становится громоздкой (имеет 1024 строки), а при =20 – практически необозримой. Поэтому используют другие способы задания функции, среди которых основным является аналитический способ, то есть при помощи формул. При этом способе некоторые функции выделяются и называются элементарными, а другие функции строят из элементарных с помощью суперпозиции. Такой способ задания функции хорошо известен в математическом анализе. Например, функция построена суперпозицией многочлена , квадратного корня, косинуса и функции .