2.2.Разнообразие булевых функций

Булевы функции от одной переменной приведены в табл.2.1.

Обозначение аргумента и функции	Значения аргумента и функции		Наименование функции
x	0	1
	0	0	Логический ноль
	0	1	Повторение x
	1	0	Инверсия x
	1	1	Логическая единица

Таблица 2.1. Булевы функции от одной переменной

Булева функция от n аргументов f ⁿ(Х) называется вырожденной по аргументу x_i, если ее значение не зависит от этого аргумента, то есть для всех наборов аргументов имеет место равенство:

f(x₁, x₂, ... , x_i-1, 0, x_i+1, ... , x_n) = f(x₁, x₂, x_i-1, 1, x_i+1, ... , x_n).

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

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

Булевы функций от двух переменных приведены в табл.2.2.

Среди функций от двух переменных шесть вырожденных функций, к которым относятся:

• логический ноль;

• логическая единица;

• функция повторения аргументов x₁ и x₂;

• отрицание аргументов x₁ и x₂.

Некоторые функции от трех переменных представлены в табл. 2.3.

Замечание. Функции сумма по модулю 2 и исключающее ИЛИ для трех аргументов являются неэквивалентными.

Утверждение. Общее число разнообразных булевых функций, в том числе и вырожденных, от n аргументов равно .

Аргументы и функции (в символической форме)	Значения аргументов и функций				Обозначение функций	Наименование	Вырожденность	Представление функции в булевом базисе
x1	0	0	1	1
x2	0	1	0	1
	0	0	0	0	0	Логический ноль	+	-
	0	0	0	1	x1 & x2	Конъюнкция	-
	0	0	1	0	x1  x2	Запрет x1 по x2	-
	0	0	1	1	x1	Повторение x1	+	-
	0	1	0	0	x2  x1	Запрет x2 по x1	-
	0	1	0	1	x2	Повторение x2	+	-
	0	1	1	0	x1 x2	Сумма по модулю 2, неравнозначность, исключительное ИЛИ	-
	0	1	1	1	x1 x2	Дизъюнкция	-
	1	0	0	0	x1 x2	Функция Вебба, стрелка Пирса	-
	1	0	0	1	x1 x2 (x1 x2)	Равнозначность, эквивалентность	-
	1	0	1	0		Отрицание x2	+
	1	0	1	1	x2 x1	Импликация от x2 к x1	-
	1	1	0	0		Отрицание x1	+
	1	1	0	1	x1 x2	Импликация от x1 к x2	-
	1	1	1	0	x1 x2	Штрих Шеффера	-
	1	1	1	1	1	Логическая единица	+	-

Таблица 2.2. Булевы функции от двух переменных

Значение аргументов			Значение функций
			Сумма по модулю 2	Исключающее ИЛИ	Функция мажоритарности
x1	x2	x3	x1 x2 x3	XOR (x1,x2,x3)	x1#x2#x3
0	0	0	0	0	0
0	0	1	1	1	0
0	1	0	1	1	0
0	1	1	0	0	1
1	0	0	1	1	0
1	0	1	0	0	1
1	1	0	0	0	1
1	1	1	1	0	1

Таблица 2.3. Некоторые функции от трех переменных