3.5 Логические функции многих переменных

Все логические операции, которые были рассмотрены в 3.2, распространяются и на функции нескольких переменных. Теперь будем рассматривать функции F(x₁, x₂,…, x_n), где x_i - логические переменные, которые принимают значения нуля или единицы. Для описания логики функционирования аппаратных и программных средств компьютера используется алгебра логики, или булева алгебра. Два элемента алгебры логики - ее константы - 0 (ложь) и 1 (истина). Во всех компьютерах используются сигналы двух видов. Сигналы можно интерпретировать как двоичные числа, или логические переменные.

Логической функцией F от набора логических переменных х₁,…, х_n называется функция, которая может принимать только два значения: логический 0 и логическая 1.

Область определения логической функции конечна и зависит от количества возможных наборов аргументов. Если n - число аргументов, то количество возможных наборов аргументов равно 2ⁿ.

Множество значений функции F(x₁,…, x_n) - это множество {0,1}, т. е. F=0 либо 1.

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

Вектором значений булевой функции F(x₁,…, x_n) называется упорядоченный набор всех значений функции F, при которых значения упорядочены по лексикографическому порядку множества аргументов {0,1}ⁿ.

Поскольку всего имеется 2ⁿ наборов нулей и единиц (|{0,1}ⁿ|=2ⁿ), существует ровно булевых функций F(x₁,…, x_n) от n переменных:

.

При n=2 количество функций равно 16, при n=3 - 256 и т. д. На рис. 3 представлены в упорядоченном виде наборы аргументов для ряда функций - отрицания 0, функций одного, двух и трёх аргументов.

Рис. 3. Упорядоченные наборы аргументов