2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Пороговая функция
Сообщение29.09.2009, 15:13 


29/09/09
4
Булева функция называется пороговой если выражается в виде $ f(x_1...x_n)=[a_1x_1+...a_nx_n >= b] $ , где a_i и b - вещественные числа.
Пусть $ N(f) $ - колличество наборов $x_1..x_n$ на которых $f(x_1..x_n)=1$, а $E(f)$ - сумма таких наборов, интерпретируемых как векторы вещественных чисел. Доказать, что если N(f)=N(g) и E(f)=E(g), то $f=g$

 Профиль  
                  
 
 Re: Пороговая функция
Сообщение12.10.2009, 06:46 
Заслуженный участник


08/04/08
8562
Доказываем по индукции.
Для $n=1$ есть только 3 пороговые функции: у первой решений нет ($N(f)=0, S(f)=(0)$), у второй одно решение ($N(f)=1,S(f)=(x^*)$), у третьей два решения ($N(f)=2, S(f)=(1)$), так что для них утверждение верно.
Пусть теперь $f_n=g_n \Leftrightarrow N(f_n)=N(g_n), E(f_n)=E(g_n)$.
Рассмотрим функции $f_{n+1},g_{n+1}:f_{n+1}=g_{n+1}$.
Если $f_{n+1}=g_{n+1}$, то $E(f_{n+1})=E(g_{n+1}),N(f_{n+1})=N(g_{n+1})$.
Обратно, пусть $E(f_{n+1})=E(g_{n+1}),N(f_{n+1})=N(g_{n+1})$
$f_{n+1}=g_{n+1} \Leftrightarrow f_{n+1}(x_i,0)=g_{n+1}(x_i,0),f_{n+1}(x_i,1)=g_{n+1}(x_i,1)$. Эти функции обозначим $f_{n0},f_{n1},g_{n0},g_{n1}$. Они также являются пороговыми функциями, поэтому $f_{n0}=g_{n0},f_{n1}=g_{n1} \Leftrightarrow N(f_{n0})=N(g_{n0}),N(f_{n1})=N(g_{n1}),E(f_{n0})=E(g_{n0}),E(f_{n1})=E(g_{n1})$. То есть достаточно доказать эти 4 равенства для того, чтобы доказать, что булевы функции равны.
$E(f_{n+1})=(\sum\limits_{x_{n+1}=0} x_i^*;0)+(\sum\limits_{x_{n+1}=1} x_i^*;1)=E(f_{n0}) \times \{ 0 \} + E(f_{n1}) \times \{ N(f_{n1}) \} = E(g_{n0}) \times \{ 0 \} + E(g_{n1}) \times \{ N(g_{n1}) \} = E(g_{n+1})$.
Отсюда получаем, что $N(f_{n1})=N(g_{n1}),E(f_{n0})=E(g_{n0}),E(f_{n1})=E(g_{n1})$.
Далее
$N(f_{n+1})=N(f_{n+1}(x_i,0)=1)+N(f_{n+1}(x_i,1)=1)=N(f_{n0})+N(f_{n1})=N(g_{n0})+N(g_{n1})=N(g_{n+1})$
То есть $N(f_{n0})+N(f_{n1})=N(g_{n0})+N(g_{n1})$, а поскольку мы уже нашли $N(f_{n1})=N(g_{n1})$, то отсюда получаем $N(f_{n1})=N(g_{n1}), N(f_{n0})=N(g_{n0})$.
В итоге мы доказали все 4 равенства, так что $E(f_{n+1})=E(g_{n+1}), N(f_{n+1})=N(g_{n+1}) \Rightarrow f_{n+1}=g_{n+1}$.
Т. обр. из равносильности для $n$ следует равносильность для $n+1$, поэтому утверждение верно для всех $n$.
Правильно?
З.Ы. Кажется утверждение верно не только для пороговых булевых функций, но и для всех булевых функций. Как Вы думаете?

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

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



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

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


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

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