Преобразование Жегалкина

[luitzen]

Надеюсь, все помнят, как по таблице булевой функции строится СДНФ…

Объединяются через дизъюнкцию все элементарные конъюнкции, соответствующие наборам, на которых функция принимает значение 1. Соответствие задаётся следующим образом: если значение переменной в наборе равно 1, то она входит в элементарную конъюнкцию сама по себе, а если равно 0, то она входит в элементарную конъюнкцию с отрицанием.

Но давайте попробуем объединять элементарные конъюнкции через строгую дизъюнкцию, а сами элементарные конъюнкции строить по «дающим единицу» наборам вот как: если значение переменной в наборе равно 1, то она входит в элементарную конъюнкцию, если же 0, то не входит (для набора из одних нулей соответствующей элементарной конъюнкцией будет просто единица).

Функцию, полученную таком вот образом на основании исходной функции $f$, обозначим через $F(f)$.

Проблема в том, что отнюдь не всегда $F(f)\equiv f$. Однако же, всегда $F(F(f))\equiv f$. Что и требуется доказать .

[Sonic86]

Если $f(a_{i1}, a_{i2},..., a_{in}) = b_i$, то $F(f)= \sum\limits_{i=0}^{2^n-1} b_i \prod\limits_{j=1}^n x_j^{aij}$ - формула для преобразования Жегалкина (можно рассматривать $a_{ij}$ как цифры индекса $i$ в двоичной системе счисления). То есть можно рассматривать $F$ как функцию формулы от $n$ переменных, а можно как функцию $2^n$ булевых констант.
Доказать можно по индукции по $n$ (только обозначения немного кривые, если кто знает лучше - напишите):
Для $n=1$ проверяем, что $F(F(f)) \equiv f$:
$f \to F(f) \to F(F(f))$
$(0, 0) \to (0, 0) \to (0, 0)$
$(0, 1) \to (0, 1) \to (0, 1)$
$(1, 0) \to (1, 1) \to (1, 0)$
$(1, 1) \to (1, 0) \to (1, 1)$
Пусть для любой $f$ от $n-1$ переменных $F(F(f)) \equiv f$.
$f(x_1, ..., x_n) = f^1(x_1, ..., x_{n-1}) + x_n f^2(x_1, ..., x_{n-1})$
$F_n(f(x_1,...,x_n,)) |_{x_n=0} = F_{n-1}(f(x_1,...,x_{n-1},0))$. Слева - преобразование Жегалкина от функции $n$ nеременных, в которую потом подставили $x_n =0$, а справа - преобразование Жегалкина функции $n-1$ переменных $f(x_1,...,x_{n-1},0)$. Причем, если рассматривать преобразования Жегалкина как функции от энки булевых констант, то у функции справа размерность $2^n$, а у функции слева - $2^{n-1}$, поэтому они разные и для различия пишется индекс.
Это соотношение доказывается через формулу для преобразования Жегалкина. Обе части при определенном выборе порядка аргументов равны $ \sum\limits_{i=0}^{2^{n-1}-1} b_i \prod\limits_{j=1}^n x_j^{aij}$.
Представим $f$ как $f(x_1, ..., x_n) = f^1(x_1, ..., x_{n-1}) + x_n f^2(x_1, ..., x_{n-1})$.
При $x_n = 0$ $f(x_1, ..., x_n) = f^1(x_1, ..., x_{n-1})$, и тогда $F(F(f(x_1,...,x_n))|_{x_n=0} = F(F(f^1(x_1, ..., x_{n-1})) = f^1(x_1, ..., x_{n-1})$ по предположению индукции.
Если $x_n=1$, то $f(x_1, ..., x_n) = f^1(x_1, ..., x_{n-1}) + f^2(x_1, ..., x_{n-1})$, а функция $F$ - аддитивна, поэтому опять по предположению индукции $F(F(f)) = F(F(f^1))+F(F(f^2)) = f^1+f^2$.
Таким образом, формула $F(F(f)) = f$ верна при $x_n=0$, и верна при $x_n=1$. Значит, она верна и в общем случае для $n$ переменных, значит по индукции верна для всех $n$.

З.Ы. А можно ли найти число $f: F(f) \equiv f$.

[Профессор Снэйп]

Строгая дизъюнкция --- это исключающее "или"? Или что-то иное?

P. S. Непонятно, кстати, как определяется $F(f)$ для функции, тождественно равной нулю. Для такой функции, впрочем, и с. д. н. ф. не определена

[Sonic86]

Строгая дизъюнкция - действительно исключающее или, она же сумма по модулю 2.
Вроде как если $f \equiv 0$, то и $F(f) \equiv 0$.

[luitzen]

А я ведь вроде подписывался на эту тему…

Sonic86 писал(а):

Доказать можно по индукции по $n$…
Представим $f$ как…

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

Sonic86 писал(а):

А можно ли найти число $f: F(f) \equiv f$

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

[Sonic86]

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