2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Найти полином Жегалкина
Сообщение24.05.2012, 09:19 


24/05/12
40
Найти полином Жегалкина для функции $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}$

 Профиль  
                  
 
 Re: Найти полином Жегалкина
Сообщение24.05.2012, 09:48 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Найти полином Жегалкина
Сообщение25.05.2012, 07:52 


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

 Профиль  
                  
 
 Re: Найти полином Жегалкина
Сообщение26.05.2012, 13:30 


24/05/12
40
$
\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}$

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

 Профиль  
                  
 
 Re: Найти полином Жегалкина
Сообщение26.05.2012, 13:54 
Заслуженный участник


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

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

ИСН в сообщении #575465 писал(а):
Или они каким-то оккультным образом все пронумерованы, и это её номер?
А я даже понял как :-) - список значений упорядочивается и считается двоичной записью числа $N$.

 Профиль  
                  
 
 Re: Найти полином Жегалкина
Сообщение26.05.2012, 14:20 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Найти полином Жегалкина
Сообщение26.05.2012, 16:30 


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

$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)$

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

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

 Профиль  
                  
 
 Re: Найти полином Жегалкина
Сообщение26.05.2012, 16:34 
Админ форума
Аватара пользователя


19/03/10
8952
 i  Тема перемещена в Карантин.

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

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


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

Вернул.

 Профиль  
                  
 
 Re: Найти полином Жегалкина
Сообщение26.05.2012, 18:11 


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

 Профиль  
                  
 
 Re: Найти полином Жегалкина
Сообщение26.05.2012, 18:16 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Arsenii в сообщении #576667 писал(а):
При преобразовании СДНФ в полином Жегалкина, достаточно заменить все дизъюнкции на операции исключающее ИЛИ и избавиться от инверсий при помощи эквивалентного преобразования
Ну, собственно, так и сделайте. Замените все $\vee$ на $\oplus$, а $\bar{x}$ на $(x\oplus 1)$(и то же со всми остальными переменными). А потом раскройте скобки.

 Профиль  
                  
 
 Re: Найти полином Жегалкина
Сообщение26.05.2012, 18:38 
Заслуженный участник


11/11/07
1198
Москва
Xaositect в сообщении #576738 писал(а):
Замените все $\vee$ на $\oplus$

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

 Профиль  
                  
 
 Re: Найти полином Жегалкина
Сообщение26.05.2012, 18:44 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Найти полином Жегалкина
Сообщение26.05.2012, 19:08 


24/05/12
40
$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)$

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

 Профиль  
                  
 
 Re: Найти полином Жегалкина
Сообщение26.05.2012, 19:22 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Ну, тут раскрывать нечего: вы забыли поставить скобки вокруг $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$ и так далее.

 Профиль  
                  
 
 Re: Найти полином Жегалкина
Сообщение27.05.2012, 08:22 


24/05/12
40
$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)$
или там какое то выражение

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 23 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group