Функции алгебры логики

Функция называется n-местной булевой функцией, если каждая переменная принимает только два значения 0 или 1 и функция принимает значения в этом же множестве {0; 1}. Булевой функцию называют в честь ирландского математика Джорджа Буля (1815–1864), работавшего в университете города Корк, отца писательницы Этель Лилиан Войнич. С именем Буля связана революция в логике, она приобрела письменность, появился новый тип алгебры. Другие имена, связанные с этой теорией: Аристотель, Раймундо Луллий (исп. философ, монах-отшельник XII-XIII вв.), Б. Спиноза, Н. Винер. Булевые функции называют также функциями алгебры логики или, более полно, алгебры двузначной логики.

Булеву функцию можно задать таблицей:

Таблица 3.1

		…..	xn– 1	xn
		….			f (0, …, 0)
		….			f (0, …, 1)
…	…	….	….	…	…
		….			f (1, …, 1)

Всюду в дальнейшем наборы значений переменных булевой функции будем располагать в стандартном порядке, при котором набор представляет собой двоичную запись своего номера в n разрядах (нумерация начинается с нуля), т.е.