Определение

Булевой функцией f(x₁,...,x_n) называется функция, у которой и значения и аргументы принадлежат одному множеству B = {0,1}.

Элементы множества B интерпретируются как «истина» и «ложь».

Число булевых функций от n переменных равняется 2²ⁿ.

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

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

1. Табличный

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

2. Векторный

Если последний столбец таблицы 1 выписать в виде вектора, то получим векторный способ задания булевой функции: f = (f(0, 0, ..., 0), f(0, 0, ..., 1), ..., f(1, 1, ..., 1))

Например, функция f = (1,1,1,0) от двух переменных, заданная в векторном виде.

3. Формульный

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

Например, применяя операцию суперпозиции к элементарным функциям f₃ и g₃, представленных ниже, можно получить функцию .

В таблице перечислены элементарные булевы функции от одного аргумента:

где

- тождественный нуль,
- тождественная единица,
- тождественная функция,
- отрицание.

В таблице перечислены булевы функции от двух аргументов:

где

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

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

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