Многочлен Жигалкина. Количество многочленов Жигалкина для n переменных. Единственность многочлена Жигалкина для каждой булевой функции

Многочлен Жигалкина является суммой константы 0 или 1 и различных одночленов (элементарных конъюнкций переменных без инверсий), в которые все переменные входят не более одного раза (могут не входить). Причём все одночлены в многочлене Жигалкина различны.

Подсчитаем число различных многочленов Жигалкина. Количество различных одночленов из n переменных равно числу всех подмножеств множества мощности n (мощности множества – степени), т.е. равно два в степени n. Пустое подмножество здесь – это константа 1. Например, при n = 2 имеет четыре одночлена: x y, x, y и 1.

Число полиномов (многочленов) Жигалкина равно числу булевых функций (от n переменных), т.е. между полиномами и функциями можно установить взаимно однозначное соответствие, что доказывает единственность полинома Жигалкина для каждой булевой функции. Все полиномы Жигалкина от двух переменных x и y и функции f0, …, f15, которым они соответствуют:

		x	x+1	y	y+1	x+y	x+y+1
f0=0	f15=1	f3=x	f12= x	f5=y	f10= y	f6=x+y	f9=x~y

xy	xy+1	xy+x	xy+y	xy+x+1	xy+y+1	xy+x+y	xy+x+y+1
f1=x&y	f14=x	f2= (x y)	f4= (y x)	f13= x y	f11= y x	f7=x y	f8=x y

27. Правила перехода к равносильным формулам в логике предикатов: перестановка одноименных кванторов и переименование связанных переменных.

3. Перестановка одноименных кванторов:

( x) ( y) A(x, y) ( y) ( x) A(x, y);

( x) ( y) A(x, y) ( y) ( x) A(x, y).

4. Переименование связанных переменных. Заменяя связанную переменную формулы A другой переменной, не входящей в эту формулу, в кванторе и всюду в области действия квантора, получаем формулу, равносильную A. Это правило применяется при составлении формул ЛП из формул A и B, если есть переменные, свободные в одной из них и связанные в другой. Такую связанную переменную заменяем другой переменной, не входящей в эти формулы. Это утверждение доказывается индукцией по длине формулы.