Полином Жегалкина

[Daniil_Sh]

Сначала рассмотрим пример, пусть $f(x_1,x_2,x_3)=x_1x_2\oplus x_1x_3 \oplus x_2x_3$. Сделав, например, подстановку $x_1=x_1$, $x_2=z_1\oplus z_2 \oplus z_1z_3\oplus z_1z_2$, $x_3=z_1\oplus z_3\oplus z_1z_2\oplus z_1z_3$, получим $f(z_1,z_2,z_3)=z_1\oplus z_2z_3$, так что выделили переменную $x_1$ и удалили все мономы, которые её содержали.
В общем случае, пусть задан полином $f(x_1,x_2,...,x_n)=x_ix_j\oplus \sum\limits_{x_i\in m_j} m_j \oplus \sum\limits_{x_i\notin m_j} m_j$, $\deg f \geq 2$, $m_i$ — мономы, $f$ — сбалансирован (вес Хэмминга равен $2^{n-1}$). Какую сделать обратимую подстановку, чтобы получилось $f(z_1,z_2,...,z_n)=z_i\oplus \sum\limits_{z_i\notin m_j}m_j$ (слагаемые $\sum\limits_{z_i\notin m_j}m_j$ совпадают с $\sum\limits_{x_i\notin m_j} m_j$ с точностью до буквы)?

[Лукомор]

Daniil_Sh в сообщении #1494002 писал(а):

так что выделили переменную $x_1$

Точнее, не выделили, а потеряли...

Вы распишите, что и куда Вы подставляли в этой подстановке...

[Daniil_Sh]

Задан полином $f(x_1,x_2,x_3)=x_1x_2\oplus x_2x_3\oplus x_1x_3$. Вычисляем $f(p_1(z_1,z_2,z_3),p_2(z_1,z_2,z_3),p_3(z_1,z_2,z_3))$, где $p_1(z_1,z_2,z_3)=z_1$, $p_2(z_1,z_2,z_3)=z_1\oplus z_2\oplus z_1z_2 \oplus z_1z_3$, $p_3(z_1,z_2,z_3)=z_1\oplus z_3\oplus z_1z_2 \oplus z_1z_3$.

Получим $p_1(z_1,z_2,z_3)p_2(z_1,z_2,z_3)\oplus p_2(z_1,z_2,z_3)p_3(z_1,z_2,z_3)\oplus p_1(z_1,z_2,z_3)p_3(z_1,z_2,z_3)=z_1(z_1\oplus z_2\oplus z_1z_2 \oplus z_1z_3)\oplus (z_1\oplus z_2\oplus z_1z_2 \oplus z_1z_3)(z_1\oplus z_3\oplus z_1z_2 \oplus z_1z_3)\oplus z_1(z_1\oplus z_3\oplus z_1z_2 \oplus z_1z_3)=z_1\oplus z_1z_2\oplus z_1z_2\oplus z_1z_3\oplus z_1\oplus z_1z_3\oplus z_1z_2\oplus z_1z_3\oplus z_2z_1\oplus z_2z_3\oplus z_1z_2\oplus z_1z_2z_3\oplus z_1z_2\oplus z_1z_2z_3\oplus z_1z_2\oplus z_1z_2z_3\oplus z_1z_3\oplus z_1z_3\oplus z_1z_2z_3\oplus z_1z_3\oplus z_1\oplus z_1z_3\oplus z_1z_2\oplus z_1z_3=z_1\oplus z_2z_3$.

[Лукомор]

Daniil_Sh в сообщении #1494243 писал(а):

где $p_1(z_1,z_2,z_3)=z_1$,

Ну, вот, совсем другое дело!
А в стартовом сообщении было:

Daniil_Sh в сообщении #1494002 писал(а):

Сделав, например, подстановку $x_1=x_1$

Только к чему все это?
Понятно, что подставив вместо $x_1$,$x_2$ и $x_3$ какие-то комбинации из $z_1$,$z_2$ и $z_3$,
получим какую-то $f(p_1(z_1,z_2,z_3),p_2(z_1,z_2,z_3),p_3(z_1,z_2,z_3))$.

При этом таблицы истинности у $f(x_1,x_2,x_3)$
и у $f(p_1(z_1,z_2,z_3),p_2(z_1,z_2,z_3),p_3(z_1,z_2,z_3))$
могут получиться разные.
Или одинаковые.
В вашем случае они разные.

Составьте таблицу истинности для

Daniil_Sh в сообщении #1494243 писал(а):

$f(x_1,x_2,x_3)=x_1x_2\oplus x_2x_3\oplus x_1x_3$

и отдельно для $f(p_1(z_1,z_2,z_3),p_2(z_1,z_2,z_3),p_3(z_1,z_2,z_3)) = z_1\oplus z_2z_3$

[Daniil_Sh]

По таблицам я понимаю, что есть $2^{n-1}!2^{n-1}!$ таких подстановок, и что любую из них можно найти преобразованием Мёбиуса. Но интересно получить что-нибудь универсальное, так, чтобы не перебирать всю таблицу.

[Лукомор]

Daniil_Sh в сообщении #1494310 писал(а):

По таблицам я понимаю, что есть $2^{n-1}!2^{n-1}!$ таких подстановок

Ну, с теми ограничениями, которые вы наложили в условии, их гораздо меньше будет.

Вот для $n=2$ я вижу только один вариант:

$f(x_1,x_2)=x_1\wedge x_2$.

Соответственно, Ваша задача заключается в том, чтобы найти два таких полинома,
$p_1(z_1,z_2)$ и $p_2(z_1,z_2)$,
что $p_1\wedge p_2=z_1$.

Как Вы эту задачу будете решать?

[Daniil_Sh]

А $x_1x_2$ не является сбалансированной. Видимо, надо предполагать, что $n\geq 3$, потому что при $n=2$ все сбалансированные функции будут не выше второй степени: $1\oplus x_1$, $1\oplus x_2$, $1\oplus x_1\oplus x_2$, $x_1\oplus x_2$, $x_1$, $x_2$.

[Лукомор]

Daniil_Sh в сообщении #1494475 писал(а):

А $x_1x_2$ не является сбалансированной.

Тем не менее, и для нее найдутся два таких полинома, какие Вам требуются.

[Daniil_Sh]

Да, конечно, в этом случае есть 6 вариантов. Сбалансированность важна с точки зрения обратимости сделанной подстановки. Функция $x_i\oplus g(x_1,...,x_{i-1},x_{i+1},...,x_n)$ является сбалансированной, поэтому и исходная функция должна обладать таким свойством.

[Лукомор]

Daniil_Sh в сообщении #1494606 писал(а):

Функция $x_i\oplus g(x_1,...,x_{i-1},x_{i+1},...,x_n)$ является сбалансированной, поэтому и исходная функция должна обладать таким свойством.

Это ниоткуда не следует...
Ничто не мешает получить из исходной сбалансированной функции несбалансированную, и обратным преобразованием снова получить исходную функцию?

Или я опять не понял...

Вы которую функцию исходной полагаете?

[Daniil_Sh]

Сначала есть сбалансированная функция $f(x_1,x_2,...,x_n)=x_ix_j\oplus \sum\limits_{x_i\in m_j} m_j \oplus \sum\limits_{x_i\notin m_j} m_j$ степени не меньше 2 (могут быть мономы второй степени и кроме $x_ix_j$, для определённости выбираем $x_ix_j$), есть какие-то мономы, содержащие $x_i$, есть мономы без $x_i$. А нужно получить функцию $x_i\oplus g(x_1,...,x_{i-1},x_{i+1},...,x_n)$, где $g$ состоит из тех мономов, которые были в $f$ и которые не содержали $x_i$. Функции $f$ и $x_i\oplus g$ сбалансированные, поэтому существует обратимая подстановка $x_1=p_1(z_1,z_2,...,z_n)$,..., $x_n=p_n(z_1,z_2,...,z_n)$, для которой $f(p_1(z_1,z_2,...,z_n),...,p_n(z_1,z_2,...,z_n))=x_i\oplus g(x_1,...,x_{i-1},x_{i+1},...,x_n)$. С помощью таблиц легко выписать все варианты таких подстановок.
Например, пусть $f(x_1,x_2,x_3)=x_1x_2\oplus x_2x_3\oplus x_1x_3$ и нужно получить $z_1\oplus z_2z_3$. Этим функциям соответствуют такие таблицы:
000 0
001 0
010 0
011 1
100 0
101 1
110 1
111 1
и
000 0
001 0
010 0
011 1
100 1
101 1
110 1
111 0
Нужно переставить строки первой таблицы так, чтобы вектор значений был, как у второй. Переставим, например, так:
000 0
001 0
010 0
011 1
111 1
101 1
110 1
100 0
то есть перестановка определяется векторами 00001111, 00111010, 01011100. В алгебраической форме это значит, что $p_1(z_1,z_2,z_3)=z_1$, $p_2(z_1,z_2,z_3)=z_1\oplus z_2\oplus z_1z_3\oplus z_1z_2$, $p_3(z_1,z_2,z_3)=z_1\oplus z_3\oplus z_1z_3\oplus z_1z_2$.

[Лукомор]

Это хорошо.
В чем вопрос-то заключается?!

[Daniil_Sh]

Так таблицу нужно строить, это долго, $2^n$. Можно ли по виду исходной функции сразу предложить подстановку, преобразующую функцию к нужному виду?

[Лукомор]

Daniil_Sh в сообщении #1494664 писал(а):

Можно ли по виду исходной функции сразу предложить подстановку,

Так Вы же предложили:

Daniil_Sh в сообщении #1494002 писал(а):

$f(z_1,z_2,...,z_n)=z_i\oplus \sum\limits_{z_i\notin m_j}m_j$ (слагаемые $\sum\limits_{z_i\notin m_j}m_j$ совпадают с $\sum\limits_{x_i\notin m_j} m_j$ с точностью до буквы)

[Daniil_Sh]

Это уже результат подстановки, то есть $f(p_1(z_1,z_2,...,z_n),...,p_n(z_1,z_2,...,z_n))$, а мне нужны $p_1(z_1,z_2,...,z_n)$, $p_2(z_1,z_2,...,z_n)$, ..., $p_n(z_1,z_2,...,z_n)$.