2.2.1. Булевы функции. Понятие булевой функции. Число булевых функций от n переменных

Пусть — числовое поле из двух элементов. Отображение называется Булевой функцией. Как обычно, переменные булевой функции будем обозначать: . Таким образом, булева функция  — это функция, переменные которой могут принимать только значения 0 или 1; сама булева функция также может принимать только значения 0 или 1.

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

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

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

Теорема 1. Число различных булевых функций от N переменных равно .

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

< Предыдущая		Следующая >