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

[Лукомор]

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

Это уже результат подстановки

То-есть, с самой подстановкой, вплоть до получения ее результата, Вам всё ясно?
И Вы, по известным $f(x_1,x_2\dots,x_n)$ и $g(z_1,z_2\dots,z_n)$ и без таблиц истинности можете в одно действие находить такую $h(y_1,y_2\dots,y_n)$, что
$f(x_1,x_2\dots,x_n)\oplus h(y_1,y_2\dots,y_n)=g(z_1,z_2\dots,z_n)$,
и, соответственно, $g(z_1,z_2\dots,z_n)\oplus h(y_1,y_2\dots,y_n)=f(x_1,x_2\dots,x_n)$?

[Daniil_Sh]

Важно, чтобы была композиция функций, а не просто сложение. Хочу найти все нули функции $f(x_1,x_2,...,x_n)$. Если получилось, например, $f(p_1(x_1,x_2,...,x_n),...,p_n(x_1,x_2,...,x_n))=x_1+g(x_2,...,x_n)$, то я переберу $2^{n-1}$ наборов по $x_2$,..., $x_n$, получу автоматически соответствующие значения $x_1$, и с помощью обратной подстановки найду те наборы, на которых зануляется $f$. А если есть $g\oplus h=f$, то из $g=0$ не следует , что $f=0$.

[Лукомор]

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

А если есть $g\oplus h=f$, то из $g=0$ не следует , что $f=0$.

А если есть $f=x_1\oplus g$, то из $g=0$ также не следует $f=0$, но Вас это не смущает.

-- Ср дек 02, 2020 05:44:03 --

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

то я переберу $2^{n-1}$ наборов по $x_2$,..., $x_n$

А почему Вы решили, что наборов будет $2^{n-1}$, а не $2^n$?
У Вас же в примере, приведенном в стартовом сообщении, полиномы $x_2$ и $x_3$ от трех переменных.
А $x_1=z_1$. Тогда что Вы собрались перебирать сокращенным перебором?

-- Ср дек 02, 2020 05:54:38 --

(Оффтоп)

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

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

Вспомнилось почему-то...

Цитата:

«Почему сие важно в-третьих?» — «Сие в-третьих не важно»
/А.И. Куприн "Поединок"/

-- Ср дек 02, 2020 06:04:40 --

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

Хочу найти все нули функции $f(x_1,x_2,...,x_n)$.

И для решения этой задачи Вы хотите применить метод подстановки вместо себя какого-либо участника форума?
Тогда Вы выбрали самый не подходящий для такой подстановки раздел форума.

Дело в том, что в разделе ПРР запрещено давать полное решение задачи,
а рекомендуется мягко и ненавязчиво подталкивать ТС к тому, чтобы он решил ее сам.
Я Вас подталкиваю, а Вы упираетесь.

[Daniil_Sh]

Если есть $f=x_1\oplus g$, то из $g=0$, конечно, не следует $f=0$. У меня есть две функции: $f(x_1,x_2,...,x_n)$ и $\bar{f}(x_1,x_2,...,x_n)=x_1\oplus g(x_2,x_3,...,x_n)$, и я знаю, что $f \circ p =\bar{f}$ для некоторой обратимой функции $p:\mathbb{F}_{2}^{n}\rightarrow \mathbb{F}_{2}^{n}$. Если я найду нули функции $\bar{f}$, то с помощью $p^{-1}$ найду нули функции $f$. А нули функции $\bar{f}$ находятся из условия $x_1=g(x_2,...,x_n)$ перебором по $n-1$ переменным, то есть нули $\bar{f}$ имеют вид $(g(x_2,...,x_n),x_2,...,x_n)$. Тогда нули функции $f$ можно найти по формуле $p^{-1}(g(x_2,...,x_n),x_2,...,x_n)$.

[Лукомор]

Хорошо.
Так в чем вопрос-то?
Вроде Вы во всем и сами разобрались...

-- Чт дек 03, 2020 07:14:23 --

Одно только небольшое уточнение.
Насколько я понял, в примере из стартового поста у Вас сделана подстановка:
$x_1=x_1$, откуда следует, что $g(x_2,x_3)=0$.
У полинома $\bar{f}(x_1,x_2,x_3)=x_1$ - четыре нуля.
Найдите их любым способом, хоть перебором, и выпишите здесь в явном виде.
Я хочу на них посмотреть!

[Daniil_Sh]

Там $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_2\oplus z_1z_3$, а $f(x_1,x_2,x_3)=x_1x_2\oplus x_2x_3\oplus x_1x_3$. Значит $\bar{f}(z_1,z_2,z_3)=f\circ p(z_1,z_2,z_3)=z_1\oplus z_2z_3$. Нули функции $\bar{f}$: 000, 001, 010, 111. Здесь $p^{-1}=p$, поэтому нули функции $f$: $(p_1(0,0,0),p_2(0,0,0),p_3(0,0,0))=(0,0,0)$, $(p_1(0,0,1),p_2(0,0,1),p_3(0,0,1))=(0,0,1)$, $(p_1(0,1,0),p_2(0,1,0),p_3(0,1,0))=(0,1,0)$, $(p_1(1,1,1),p_2(1,1,1),p_3(1,1,1))=(1,0,0)$.

[Лукомор]

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

Нули функции

Ну вот и замечательно!

Поищите поиском " Разложение логической функции по переменным ",
или сразу " Разложение Шеннона ",
и будет Вам счастье...

И, кстати, я Вам с самого начала намекал, что если уж речь идет о перестановках,
то существует функция $h(y_1,y_2,\dots{y_n})$, оператор перестановки, такая, что переводит функцию $f(x_1,x_2,\dots{x_n})$ в функцию $g(z_1,z_2,\dots{z_n})$ путем
операции сложения по модулю два: $f\oplus{h}=g$, и эта же функция, тем же самым путем производит обратную перестановку: $g\oplus{h}=f$.
И найти ее можно точно так же: $h=f\oplus{g}$.

Но все это - лишние движения, ибо решить Вашу задачу можно по разному и даже проще,
чем Вы там себе придумали.

[Daniil_Sh]

Я понимаю, что можно просто за счёт сложения получить нужную функцию, но тогда неясно, как по нулям функции $g$ восстановить нули функции $f$.

[Лукомор]

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

но тогда неясно, как по нулям функции $g$ восстановить нули функции $f$.

И всего-то?

Мне гораздо труднее чем Вам.
Мне "неясно", что именно Вам "неясно".

Если бы Вы сформулировали однозначно условие, а заодно привели бы ответ для вашего примера, из стартового поста,
каким Вы его видите, я бы мог Вам помочь чем-то.

А так у Вас в стартовом сообщении -
подстановка $x_1 = x_1$.
А уже в следующем Вашем сообщении эта же подстановка выглядела, как:
$p(z_1, z_2, z_3) = z_1$.
Еще через пару сообщений вдруг оказывается, что:

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

$x_i\oplus g(x_1,...,x_{i-1},x_{i+1},...,x_n)$

.
И теперь, сделав эту подстановку, как в стартовом сообщении ($x_1 = x_1$), получаем:
$x_1 =x_1 \oplus g(x_1,x_2,x_3)$,
откуда $g(x_1,x_2,x_3)=0$
А подставив, как в следующем сообщении, $p(z_1, z_2, z_3) = z_1$. , получаем нечто другое:
$x_1 =x_1 \oplus g(x_1,x_2,x_3)=x_1 \oplus {z_1}$, откуда опять следует $z_1=0$, а $x_1$ и вообще не определено,
поскольку сокращается.
Вы уж определитесь как-нибудь однообразно, что куда подставлять, а я Вам подскажу тогда уже про обратную подстановку.

Кстати, то же самое и для остальных двух переменных:

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

$x_2=z_1\oplus z_2 \oplus z_1z_3\oplus z_1z_2$,

Здесь у Вас $x_2 = z_2 \oplus g(z_1,z_3)$,
где $g(z_1,z_3) = z_1 \oplus z_1z_3 \oplus z_1z_2$?
Или всё же $x_2 = g(z_1,z_2,z_3)=z_1\oplus z_2\oplus z_1z_2\oplus z_1z_3$?
Определитесь уже, чему в Вашем примере равно $g(\dots{z_n}\dots)$,
а то у Вас в разных сообщениях трактуется по разному...

[Daniil_Sh]

В примере функция $f(x_1,x_2,x_3)=x_1x_2\oplus x_1x_3 \oplus x_2x_3$, и делается подстановка $x_1=p_1(z_1,z_2,z_3)$, $x_2=p_2(z_1,z_2,z_3)$, $x_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_3\oplus z_1z_2$, $p_3(z_1,z_2,z_3)=z_1\oplus z_3\oplus z_1z_2\oplus z_1z_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_1p_2\oplus p_1p_3\oplus p_2p_3$ $=$ $z_1(z_1\oplus z_2 \oplus z_1z_3\oplus z_1z_2)\oplus z_1(z_1\oplus z_3\oplus z_1z_2\oplus z_1z_3)$ $\oplus (z_1\oplus z_2 \oplus z_1z_3\oplus z_1z_2)(z_1\oplus z_3\oplus z_1z_2\oplus z_1z_3)=...=z_1\oplus z_2z_3$.
Теперь у меня две функции $f=x_1x_2\oplus x_1x_3 \oplus x_2x_3$ и $\bar{f}=z_1\oplus z_2z_3$, и я знаю, что если $(z_1^*,z_2^*,z_3^*)$ – ноль функции $\bar{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=z_1$, просто не исправить уже было.

[Лукомор]

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

Теперь у меня две функции

Третья - в подарок!
У которой нули будут там, где значения $(z_1,z_2,z_3)$ совпадают со значениями
$(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 в сообщении #1495278 писал(а):

В примере функция $f(x_1,x_2,x_3)=x_1x_2\oplus x_1x_3 \oplus x_2x_3$, и делается подстановка $x_1=p_1(z_1,z_2,z_3)$, $x_2=p_2(z_1,z_2,z_3)$, $x_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_3\oplus z_1z_2$, $p_3(z_1,z_2,z_3)=z_1\oplus z_3\oplus z_1z_2\oplus z_1z_3$

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

Цитата:

Для функции $f(x_1,x_2,x_3)=x_1 \oplus x_2x_3$
сделать подстановку:
$x_1=p_1(z_1,z_2,z_3)$, $x_2=p_2(z_1,z_2,z_3)$, $x_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_3\oplus z_1z_2$,
$p_3(z_1,z_2,z_3)=z_1\oplus z_3\oplus z_1z_2\oplus z_1z_3$.

[Daniil_Sh]

В примере $p^{-1}=p$, поэтому $x_1\oplus x_2x_3$ преобразуется к $z_1z_2\oplus z_2z_3\oplus z_1z_3$.
Но я не знаю, что делать с функцией, значения которой ноль, если $(z_1,z_2,z_3)=(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 в сообщении #1495589 писал(а):

В примере $p^{-1}=p$, поэтому $x_1\oplus x_2x_3$ преобразуется к $z_1z_2\oplus z_2z_3\oplus z_1z_3$.

Это не в примере, это в булевой алгебре работает для любого примера.

Если у нас есть булева функция $f(x_1,x_2,x_3)$, и другая булева функция $g(z_1,z_2,z_3)$,
у которых значения некоторых строк в таблицах истинности совпадают (у обоих для данной строки нули, или у обоих - единицы), а значения остальных строк - не совпадают (нулю одной функции в этой строке соответствует единица у другой функции), то существует такая булева функция (оператор перестановки) , которая переводит одну функцию в другую и наоборот.

Этот перевод реализуется сложением по модулю $2$ полинома Жегалкина любой из функций, с функцией - оператором перестановки.
$f(x_1,x_2,x_3)\oplus h(x_1,x_2,x_3)=g(x_1,x_2,x_3)$.
и наоборот:
$g(z_1,z_2,z_3)\oplus h(z_1,z_2,z_3)=f(z_1,z_2,z_3)$

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

Как найти функцию - оператор перестановки, не составляя таблиц истинности?

Нужно сложить полиномы Жегалкина двух исходных функций по модулю два.
$h(x_1,x_2,x_3)=g(x_1,x_2,x_3)+f(x_1,x_2,x_3)$
Как раз у этой функции нули будут там, где у обеих исходных функций будут нули, или у обеих исходных функций будут единицы. А единицы у нее будут в тех строках, где исходные функции имеют разные значения. В тех строках, которые у исходной функции "переставлены".

Для Вашего примера:
$f(z_1,z_2,z_3)=z_1z_2\oplus z_2z_3\oplus z_1_z_3$
$g(z_1,z_2,z_3)=z_1\oplus z_2z_3$,
откуда находим:
$h(z_1,z_2,z_3)=z_1\oplus z_1z_2 \oplusz_1z_3$.
Ничего не напоминает вид этой функции?

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

Но я не знаю, что делать с функцией, значения которой ноль, если $(z_1,z_2,z_3)=(p_1(z_1,z_2,z_3),p_2(z_1,z_2,z_3),p_3(z_1,z_2,z_3))$.

На это есть простой рецепт:

Лукомор в сообщении #1495098 писал(а):

Поищите поиском " Разложение логической функции по переменным ",
или сразу " Разложение Шеннона ",

Лучше всего сразу глянуть параграф 11.2.6.
Это разложение и даст сразу необходимые подстановки, которые суть :
$h_1(z_1,z_2,z_3)$
$h_2(z_1,z_2,z_3)$
$h_3(z_1,z_2,z_3)$
в формулы:
$x_1(z_1,z_2,z_3)=g_1(z_1,z_2,z_3)\oplus h_1(z_1,z_2,z_2)$
$x_2(z_1,z_2,z_3)=g_2(z_1,z_2,z_3)\oplus h_2(z_1,z_2,z_2)$
$x_3(z_1,z_2,z_3)=g_3(z_1,z_2,z_3)\oplus h_3(z_1,z_2,z_2)$,
соответственно:
$g_1(x_1,x_2,x_3)=f_1(x_1,x_2,x_3)\oplus h_1(x_1,x_2,x_2)$
$g_2(x_1,x_2,x_3)=f_2(x_1,x_2,x_3)\oplus h_2(x_1,x_2,x_2)$
$g_3(x_1,x_2,x_3)=f_3(x_1,x_2,x_3)\oplus h_3(x_1,x_2,x_2)$,
для обратной подстановки.

[Лукомор]

Лукомор в сообщении #1495615 писал(а):

откуда находим:
$h(z_1,z_2,z_3)=z_1\oplus z_1z_2 \oplusz_1z_3$

Я дико извиняюсь, в опечатку вкралась ошибка!
Функция - оператор перестановки будет на самом деле такой:
$h(z_1,z_2,z_3)=z_1\oplus z_1z_2 \oplus z_1z_3$