11 Тема 2. Булевая функция

Понятие булевой функции

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

Определение. Если для каждого элемента имеется один элемент вида , то функция называется полностью определенной, в противном случае – частично определенной.

Определение. Рассмотрим функцию , если , где , аргументы которых определены на множестве , и такие, что , то эти функции будем называть функциями алгебры логики или булевыми функциями.

Каждая функция определяет отображение

,

которое может быть задано таблицей 1.

Таблица 1

0	0	0	0
1	0	0	1
2	0	1	0
3	0	1	1
4	1	0	0
5	1	0	1
6	1	1	0
7=	1	1	1

- элементы множества декартова произведения, а - элементы множества .

Обозначим через множество всех функций алгебры логики, содержащее также константы 0 и 1.

Теорема 1. Число всех функций из множества , зависящих от переменных , равно .

Входных наборов , а выходных - Докажем это. Входные элементы – это множество , а его мощность , а набор выходных элементов – это булеан этого множества, а булеан (таблица 2).

Таблица 2

0 0 0 1 0 1 1	0 0 0 0	1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1	1 1 1 0 0 0 1 0 0 1 0 1 0 1 0 1 1 0 0 0 1 0 1 1	1 1 0 1 1 0 1 1 1 1 1 0 0 1 1 1	1 1 1 1

Обратим внимание на два обстоятельства.

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

, , ,

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

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

Введенное выше понятие функции несовершенно, поскольку оно затрудняет рассмотрение функции от большего числа аргументов. Для устранения этого недостатка введем следующее определение.

Определение. Функция из множества зависит существенным образом от аргумента , если существуют такие значения переменных , что

.

В этом случае переменная называется существенной. В противном случае она называется несущественной или фиктивной.

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

Пример 1. Проверим, является ли переменная фиктивной, для этого построим таблицу 3, используя таблицу 1.

Таблица 3

0 0	0	0
0 1	0	0
1 0	1	1
1 1	0	0

Из таблицы видно, что функции = , следовательно, переменная - фиктивная.

Пример 2. Пусть переменная является фиктивной. По таблице 1 построим новую таблицу путем вычеркивания столбца для аргумента и всех строк, где . Получим таблицу 4.

Таблица 4

0 0	0
0 1	0
1 0	1
1 1	0

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

Пример. Функции ≡ , так как функция получена путем удаления фиктивной переменной .