04.1. Псевдобулевы функции

Пусть Р — произвольное поле. Элементы будем рассматривать как нуль и единицу поля .

Определение 4.1. Псевдобулевой функцией от переменных, или -местной псевдобулевой функцией, над полем Р при называется любое отображение в Р. Нуль-местными псевдобулевыми функциями над Р называются все элементы поля Р.

Множество всех пседобулевых функций от переменных над полем Р обозначим через . В частности, при класс совпадает с классом булевых функций . В других случаях эти классы различны, и если условиться псевдобулеву функцию со значением из считать булевой, то . Множество функций относительно естественным образом определяемых операций сложения функций и умножения функций на элементы из Р образуют линейное пространство над полем Р.

Рассмотрим систему функций:

, (4.1)

Где  — символ Кронекера, т. е.

Утверждение 4.2. Система функций (4.1) является базисом пространства .

Доказательство. Очевидно, что система (4.1) — линейно независимая система. Далее пусть  — произвольная функция из . Тогда очевидно, что

. (4.2)

Отсюда следует, что (4.1) — базис пространства .

Замечание 4.3. Если , то  — булева функция и разложение (4.2) функции совпадает с разложением, полученным заменой в её СДНФ операции на .

Замечание 4.4. Если , то система функций

(4.3)

Является базисом пространства . Это следует из теоремы 2.15 об однозначном представлении булевых функций многочленами Жегалкина. В этом случае представление функции многочленом Жегалкина есть (4.3).

Замечание 4.5. Представление булевых функций через базисы пространства сопряжено со многими трудностями. Вот две из них:

Непростым является вопрос об описании базисов пространства ;

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

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

< Предыдущая		Следующая >