Количество булевых функций от n переменных. Булевы функции от двух переменных. Полные системы, состоящие из одной функции

Любую булеву функцию от n переменных можно задать таблицей истинности из двух в n-й степени строк. Последний столбец таблицы истинности задаёт булеву функцию. Существует два в степени два в n-й степени (2 ) способов задать булеву функцию от n переменных. Столько же существует булевых функций от n переменных. При n = 2 существует 16 булевых функций от двух переменных x и y:

x	y	f0=0	f1=x&y	f2= f13	f3=x	f4= f11	f5=y	f6=x+y	f7=x y
x	y	f8=x y	f9=x~y	f10= y	f11= y x	f12= x	f13=x y	f14=x	f15=1

Система булевых функций называется полной, если любая булева функция может быть выражена через функции системы с помощью суперпозиций (т.е. составления сложных функций). Например, система из трёх функций { , &, } является полной, так как каждая булева функция имеет свои ДНФ и КНФ.