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

Все логические операции, которые были рассмотрены в 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.

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

x1	x2	…	xn-1	xn	F(x1, x2,…, xn-1, xn)
		…			F (0,0,…, 0,0)
		…			F (0,0,…, 0,1)
		…			F (0,0,…, 1,0)
…	…	…	…	…	…
		…			F (1,1,…, 1,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. Упорядоченные наборы аргументов