Найти полином Жегалкина

[Arsenii]

Найти полином Жегалкина для функции $f(x,y,z)$ с $N(f)=147$

$ \begin{vmatrix} x & y & z & f \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 \end{vmatrix}$

[ИСН]

А где функция-то?
Или они каким-то оккультным образом все пронумерованы, и это её номер?

[Arsenii]

Да функцию нужно преобразовать из $N(f)=147$

[Arsenii]

$ \begin{vmatrix} x & y & z & f \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 \end{vmatrix}$

Вот поправил для такой функции нужно найти полином Жегалкина

[Sonic86]

Ну пробуйте тупо в лоб: выпишите полином Жегалкина в общем виде. Запишите его значения в точках - получите систему ограничений. Попробуйте решить. Таким способом все и получите. Если по ходу решения придет в голову более простой способ - пробуйте.

-- Сб май 26, 2012 10:55:51 --

ИСН в сообщении #575465 писал(а):

Или они каким-то оккультным образом все пронумерованы, и это её номер?

А я даже понял как - список значений упорядочивается и считается двоичной записью числа $N$.

[AV_77]

Найдите многочлены, которые равны 1 в одной точке и нулю во всех остальных и просуммируйте нужные. Например $(x+1)(y+1)(z+1)$ дает 1 при $x = y = z = 0$ и 0 во всех остальных случаях.

[Arsenii]

Я хочу попробовать через СДНФ решить
СДНФ у меня получился такой

$F(x,y,z)=(\bar{x}\wedge\bar{y}\wedge\bar{z})\vee(\bar{x}\wedge y\wedge z)\vee(x\wedge y\wedge\bar{z})\vee(x\wedge y\wedge z)$

Вот не знаю как выполнить следующий шаг.

При преобразовании СДНФ в полином Жегалкина, достаточно заменить все дизъюнкции на операции исключающее ИЛИ и избавиться от инверсий при помощи эквивалентного преобразования

[Toucan]

Тема перемещена в Карантин.

Запишите формулы в соответствии с требованиями Правил форума, т.е. в $\TeX$.
Краткие инструкции можно найти здесь: topic8355.html и topic183.html.
Кроме этого, в теме Видео-пособия для начинающих форумчан можно посмотреть видео-ролик "Как записывать формулы".

После того как исправите сообщение, сообщите об этом в теме Сообщение в карантине исправлено.

-- Сб 26.05.12 18:29:38 --

Вернул.

[Arsenii]

Я не понимаю.
С помощью программки получил свой полином.
$F(x,y,z)=1\oplus x\oplus y\oplus z \oplus x \vee z$
Но как мне его получить вручную. Покажите пошагово

[Xaositect]

Arsenii в сообщении #576667 писал(а):

При преобразовании СДНФ в полином Жегалкина, достаточно заменить все дизъюнкции на операции исключающее ИЛИ и избавиться от инверсий при помощи эквивалентного преобразования

Ну, собственно, так и сделайте. Замените все $\vee$ на $\oplus$, а $\bar{x}$ на $(x\oplus 1)$(и то же со всми остальными переменными). А потом раскройте скобки.

[AV_77]

Xaositect в сообщении #576738 писал(а):

Замените все $\vee$ на $\oplus$

Только $a \vee b = a \oplus b \oplus ab$.

[Xaositect]

Произведение двух разных конъюнкций в СДНФ рано нулю, так что в этом конкретном случае можно.

[Arsenii]

$F(x,y,z)=(\bar{x}\wedge\bar{y}\wedge\bar{z})\vee(\bar{x}\wedge y\wedge z)\vee(x\wedge y\wedge\bar{z})\vee(x\wedge y\wedge z)=(x\oplus 1\wedge y\oplus 1\wedge z\oplus 1)\oplus(x\oplus 1\wedge y\wedge z)\oplus(x\wedge y\wedge z\oplus 1)\oplus(x\wedge y\wedge z)$

Дайте пример раскрытия скобок, а то мой конспект не располагает такими знаниями

[Xaositect]

Ну, тут раскрывать нечего: вы забыли поставить скобки вокруг $x\oplus 1$, $y\oplus 1$ и $z\oplus 1$
а скобки раскрываются как обычно: $A\wedge(B \oplus C) = A\wedge B \oplus A\wedge C$, $(A\oplus B)\wedge(C \oplus D) = A\wedge C \oplus B\wedge C\oplus A\wedge D \oplus B\wedge D$ и так далее.

[Arsenii]

$F(x,y,z)=(\bar{x}\wedge\bar{y}\wedge\bar{z})\vee(\bar{x}\wedge y\wedge z)\vee(x\wedge y\wedge\bar{z})\vee(x\wedge y\wedge z)=((x\oplus 1)\wedge (y\oplus 1)\wedge (z\oplus 1))\oplus((x\oplus 1)\wedge y\wedge z)\oplus(x\wedge y\wedge (z\oplus 1))\oplus(x\wedge y\wedge z)=(x\oplus y\wedge 1 \oplus y\wedge 1\oplus y\wedge 1\oplus 1\wedge (z\oplus 1))\oplus(x\wedge y\oplus 1\wedge y\wedge z)\oplus(x\wedge y\wedge z\oplus y \wedge 1)\oplus(x\wedge y\wedge z)$

Правильно ли я раскрыл скобки $(x\oplus y\wedge 1 \oplus y\wedge 1\oplus y\wedge 1\oplus 1\wedge (z\oplus 1))$
И когда я раскрываю дальше то я единицу соединяю со скобкой $1\wedge (z\oplus 1)$
или там какое то выражение