Доказать, что если $%x_i$% - существенная переменная для функции $%f$%, тогда она существенна и для $%f^*$% (двойственная).

задан 2 Июн '15 20:19

изменен 2 Июн '15 22:41

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

1

В принципе, это очевидно: рассмотрим наборы, отличающиеся только значением i-й переменной, на которых f принимает различные значения. Тогда на противоположных наборах двойственная функция также принимает различные значения, и это доказывает, что i-я переменная для неё является существенной.

Если нужно непременно написать формулы, то это легко сделать.

(2 Июн '15 20:31) falcao

@falcao, было бы здорово, если бы Вы написали. Я пока представляю себе это как $%f(0,1,0,...,0) =1$% и $%f(0,0,0,...,0) = 0 \to$% что $%f^\ast (0,1,0,...,0)=0$% и $%f^\ast (0,0,0,...,0)=1$%, так?

(2 Июн '15 20:38) sleepless_study
1

@sleepless_study: я сейчас напишу -- это совсем несложно. Там только придётся набирать много "сигм". Мы ведь не знаем, на каком наборе имеет место различие значений. Такой набор в принципе может быть всего один, и он совершенно не обязательно нулевой.

Словесное доказательство, кстати, я считаю абсолютно строгим.

(2 Июн '15 20:54) falcao
10|600 символов нужно символов осталось
2

Пусть $%i$%-я переменная булевой функции $%f$% является существенной. Тогда по определению существует набор констант $%\sigma_1$%, ... ,$%\sigma_{i-1}$%, $%\sigma_{i+1}$%, ... , $%\sigma_n$% такой, что $%f(\sigma_1,\ldots,\sigma_{i-1},0,\sigma_{i+1},\ldots,\sigma_n)\ne f(\sigma_1,\ldots,\sigma_{i-1},1,\sigma_{i+1},\ldots,\sigma_n)$%. Следовательно, в силу определения двойственной функции, $%f^{\ast}(\bar\sigma_1,\ldots,\bar\sigma_{i-1},1,\bar\sigma_{i+1},\ldots,\bar\sigma_n)=\overline{f(\sigma_1,\ldots,\sigma_{i-1},0,\sigma_{i+1},\ldots,\sigma_n)}$%, что не равно $%\overline{f(\sigma_1,\ldots,\sigma_{i-1},1,\sigma_{i+1},\ldots,\sigma_n)}= f^{\ast}(\bar\sigma_1,\ldots,\bar\sigma_{i-1},0,\bar\sigma_{i+1},\ldots,\bar\sigma_n)$%. Отсюда по определению получаем, что $%i$%-я переменная существенна для $%f^{\ast}$%.

ссылка

отвечен 2 Июн '15 21:05

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,069
×137

задан
2 Июн '15 20:19

показан
314 раз

обновлен
2 Июн '15 21:05

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru