13.2. БУЛЕВЫ ФУНКЦИИ

Очень простое определение кодов Рида-Маллера может быть дано в терминах булевых функций. Мы собираемся определить коды длины чтобы его сделать, нам понадобится переменных принимающих значения 0 или 1. Другими словами, пусть пробегает множество всех двоичных -последовательностей. (В предыдущих главах это множество мы обозначали через но в гл. 13 и 14 нам удобнее пользоваться обозначением Любая функция принимающая значение 0 или 1, называется булевой функцией. Такая функция может быть задана таблицей

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

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

Предположим временно, что столбцы таблицы истинности естественно упорядочены, как в приведенном выше примере. Так как последняя строка таблицы может быть задана произвольным образом, то всего имеется различных булевых функций от переменных.

Обычно для булевых функций определяются следующие логические операции:

Правая сторона этих равенств определяет операции в терминах двоичных функций.

По таблице истинности булева функция выписывается сразу же; например, в предыдущем случае поскольку правая часть равна 1 как раз в тех случаях, когда равна 1 функция Это представление называется дизъюнктивной нормальной формой для (см. упражнение (1)).

Используя правила (13.1), последнее равенство можно переписать в упрощенном виде (проверить!) .

Заметим, что Ясно, что любую булеву функцию можно аналогичным образом записать в виде суммы функций

с коэффициентами, равными 0 или 1. Всего имеется булевых функций, поэтому все такие суммы различны.

Иными словами, векторов, соответствующих функциям (13.2), являются линейно независимыми.

Упражнение. (1). (Разложение булевых функций.) Доказать следующие свойства булевой функции

где булевы функции.

с). Дизъюнктивная нормальная форма:

где

Теорема 1. Любая булева функция может быть Записана в виде разложения в ряд по степеням переменных

причем коэффициенты разложения задаются равенствами

означает, что единичные координаты вектора образуют подмножество в множестве единичных координат вектора а.

Доказательство. При дизъюнктивная нормальная форма для равна:

что совпадает с (13.3) и (13.4). Аналогично при имеем:

что доказывает (13.3) и (13.4) для Ясно, что этот процесс можно продолжить и дальше.

Упражнение. (2). (Лемма о рандомизации.) Пусть произвольная булева функция. Доказать, что функция принимает значения 0 и 1 одинаково часто.