Вопросы к зачету часть2 (1085483), страница 4
Текст из файла (страница 4)
Доказательство. Докажем сначала, что указанный ряд представляет функцию f(x). Имеем
поскольку в последней сумме будет только одно ненулевое слагаемое при y=x.
Покажем теперь, что коэффициенты Caf однозначно определяются по функции f(x). Предположим, что существует другое разложение
Тогда
Домножив обе части этого равенства на (-1)(b,x) для bÎF2n и просуммировав по xÎF2n полученные равенства, имеем
Отсюда . Так как b - произвольный вектор из Fcn, получаем требуемое утверждение.
Представление булевых и псевдобулевых функций через базисы линейных пространств.
33. Понятие псевдобулевой функции. Базис функций {fa: fa(b)=a,b, an.
ЛИНЕЙНЫХ ПРОСТРАНСТВ
34. Базис функций - конъюнкций + константа 1.
35. Доказательство утверждений об однозначном представлении псевдобулевой функии в виде аналога СДНФ.
36. Доказательство утверждений об однозначном представлении псевдобулевой функии в виде аналога многочлена Жегалкина.
37. Характеры группы n.
38. Доказательство теоремы об ортогональности характеров.
39. Ряд Фурье псевдобулевой функции.
40. Выражение коэффициентов Фурье через веса функций.
§ 4. ПРЕДСТАВЛЕНИЕ БУЛЕВЫХ И ПСЕВДОБУЛЕВЫХ ФУНКЦИЙ ЧЕРЕЗ БАЗИСЫ ФУНКЦИОНАЛЬНЫХ ЛИНЕЙНЫХ ПРОСТРАНСТВ
Введем одно обобщение понятия булевой функции. Для этого зафиксируем произвольное поле Р и будем рассматривать 0 и 1 из Ω как нуль и единицу поля Р.
Определение 1. Псевдобулевой функцией от n переменных, или n-местной псевдобулевой функцией, над полем Р при n>1 называется { любое отображение в Р. Нуль-местными псевдобулевыми функциями над Р называются все элементы поля Р.
Множество всех псевдобулевых функций от n переменных над полем Р обозначим через Р(n).В частности, при P=GF (2) класс Р(n) совпадает с классом булевых функций . В других случаях эти классы различны, и если условиться псевдобулеву функцию со значениями из
считать булевой, то будем иметь:
Множество функций Р(n) относительно естественным образом определяемых операций сложения функций и умножения функций на элементы из Р образует линейное пространство над полем Р.
Его базисом, очевидно, может служить система функций
Следовательно, размерность пространства равна
, и любую его функцию можно однозначно представить в виде линейной комбинации над полем
.
При этом будет булевой функцией в том и только том случае, когда коэффициенты
принимают лишь значения 0, 1. Заметим, что в случае
(2) разложение (1) функции
совпадает с разложением, полученным заменой в ее совершенной дизъюнктивной нормальной форме операции
на
.
Из теоремы об однозначном представлении булевых функций многочленами Жегалкина следует, что при (2) множество функций
вместе с 1 также образует базис пространства , и представление функции многочленом Жегалкина есть разложение функции по указанному базису.
Представление булевых функций через базисы пространства сопряжено со многими трудностями. Во-первых, нетривиальным является вопрос об описании базисов пространства
. Если же система. функций является базисом, то в общем случае сложным является вопрос о нахождении коэффициентов в разложении булевой функции по указанному базису.
В решении вопроса об описании базисов пространства иногда может оказаться полезным переход от пространства
к пространству векторов-столбцов длины
над полем
.
Сопоставим с каждой функцией вектор-столбец значений этой функции
. В итоге получим отображение v пространства функций
в пространство векторов-столбцов длины
над полем
. Нетрудно видеть, что v есть изоморфизм пространств, а потому система функций
является базисом пространства тогда и только тогда, когда матрица
является невырожденной.
В общем случае (в отличие от приведенных выше примеров) базис пространства может содержать и такие псевдобулевы функции, которые не являются булевыми. В качестве такого примера рассмотрим один из хорошо известных базисов псевдобулевых функций над полем комплексных чисел С, связанный с характерами абелевой группы
относительно операции
. Группа
разлагается в прямую сумму
циклических подгрупп порядка 2:
где - группа, порожденная вектором
Найдем все гомоморфизмы группы в мультипликативную группу С* поля комплексных чисел С. Из разложения (2) видно, что любой гомоморфизм
однозначно определяется своими значениями на векторах . Кроме того, поскольку
— гомоморфизм, то
А так как - нулевой вектор, то
. Следовательно,
. Отсюда следует, что существует ровно
различных гомоморфизмов группы
в С* и каждый гомоморфизм
определяется системой равенств
или набором . Гомоморфизм, определяемый указанными равенствами, обозначим через
. Очевидно, что
для любого набора . Легко видеть, что в равенстве (3), не нарушая его, сумму
можно заменить суммой
, понимая под ее значением целое число 0 или 1 (как наименьший неотрицательный вычет по модулю 2). Эта сумма называется иногда булевым скалярным произведением векторов
и
из
и обозначается в виде
. По аналогии с этим линейную булеву функцию
иногда также обозначают в виде , где
Используя эти обозначения, определенную выше псевдобулеву функцию можно записать в виде
Каждая из функций называется характером группы
. Ниже будет доказано, что множество характеров
является базисом пространства C(n). Предварительно введем обозначение для любых функций из С(n), положив
докажем соотношение ортогональности для характеров:
Из равенств (4), (6) имеем:
Если , то
и
. Если же
, то функция
равновероятна и потому
.
Из равенства (7) легко следует линейная независимость системы функций (5). Действительно, если выполняется равенство
то
для любого и из (7) следует, что
.
Итак, система характеров образует базис пространства С(n) и потому каждая булева функция
представляется в виде
Такое представление функции называют ее разложением в ряд Фурье. При этом числа
называются коэффициентами Фурье для функции
.
Из равенства (8) следует, что
Отсюда имеем:
и потому
Найдем значение . По определению
где
Из определений множеств Ω', Ω" имеем:
Отсюда
Если же , то
- ненулевая линейная функция от
и потому вес ее равен
. Следовательно, в этом случае
Пример. Найти разложение в ряд Фурье функции
Составим таблицу значений коэффициентов :
Таблица11
Из таблицы II имеем разложение
Статистическая структура двоичной функции.
41. Понятие статистического аналога двоичной функции.
Будем считать, что значения переменных двоичной функции f( ,..,
) являются независимыми случайными величинами с распределением
Тогда для любого двоичного набора
Двоичную функцию называют статистическим аналогом функции f(
,..,
) , если
. Заметим, что если для некоторой функции g(x)
, то стaтистическим аналогом функции f(x) будет функция
.