Логические функции. Полные системы логических функций

Совокупность значений n аргументов можно задать как строку нулей и единиц длины n. Существует ровно 2ⁿ различных двоичных строк длины n. Так как на каждой такой строке некая функция может принимать значение 0 или 1, общее количество различных булевых функций от n аргументов равно 2²n.

Для n = 2 существует 16 различных логических функций. Для n = 3 таких функций уже 256.

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

Любая логическая функция может быть записана, используя только:

• логические операции «И», «ИЛИ» и «НЕ»;
• логические операции «И-НЕ» или «ИЛИ-НЕ».