Булевы функции

[bgm313]

Не получается доказать следующее утверждении:

Докажите, что если у функции f(x1,...xn) (n >= 1) есть несущественные переменные, то она принимает значение 1 на чётном числе наборов.

[Xaositect]

Напишите определение несущественной переменной.

Пусть переменная $x_1$ несущественна и $f(0, \tilde\alpha) = 1$ тогда чему равно $f(1, \tilde\alpha)$?

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

[Toucan]

Тема перемещена из форума «Математика (общие вопросы)» в форум «Помогите решить / разобраться (М)»

[bgm313]

Мне почему-то кажется что тут не совсем всё так просто:
Функция f(0,x2,...xn) и f(1,x2,...xn) могут быть также равну и нулю.

-- 17.09.2012, 18:59 --

Причём вклад в ||f|| буду давать и другие переменные тоже же? И их вклад может быть как чётным так и нечётным числом. Не так?

[Xaositect]

Тут вся суть в том, что они равны 1 одновременно и равны 0 тоже одновременно.
То есть все единицы разбиваются на пары.

Вклад в множество единиц дают не переменные, а наборы.

Напишите все-таки определение несущественности, как его Вам давали.

[bgm313]

Вариант 1:
Переменная xi булевой функции f(x1,x2,...,xn) называется несущественной или фиктивной, если на любых соседних по i-ой координате векторах функция f(x1...xn) принимает одинаковые значения. В противном случае переменная xi б.ф. f(x1...xn) существенная.

Вариант 2:
Функция f(x1...xn) зависит существенно от переменной xi, если существуют такие значения а1 а2 ..а(i-1) а(i+1)...аn
переменных x1 x2 ...x(i-1) x(i+1)..xn , что
f(a1,a2,...,a(i-1),0,a(i+1),...an) != f(a1,a2,...,a(i-1),1,a(i+1),...an)

-- 17.09.2012, 19:21 --

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

Ну вот, например:
По определению 0 <= ||f|| <= 2^n

Пусть x1 фиктивная переменная и ни один набор соседних векторов по координате x1 не даёт вклад в ||f||. Тогда
0 <= ||f|| <= 2^n - 2^(n-1) = 2 ^(n-1) *(2 - 1) = 2 ^(n-1)

Предположим ,что n = 1
Тогда 0 <= ||f|| <= 2. Но как показать, что ||f|| != 1?


Вклад в множество единиц дают не переменные, а наборы.

-- 17.09.2012, 19:40 --

Всё понял. Спасибо. А можно ли это доказать как-то более строго или достаточно логических рассуждений?

[Профессор Снэйп]

bgm313 в сообщении #620114 писал(а):

Не получается доказать следующее утверждении:

Докажите, что если у функции f(x1,...xn) (n >= 1) есть несущественные переменные, то она принимает значение 1 на чётном числе наборов.

Сначала затупил по поводу тождественно нулевой функции. А потом вспомнил, что ноль - тоже чётное число

[bgm313]

Может ли иметь место следующий случай:

Пусть f(x1,x2,...,xn) имеет, например 2 фикт. переменные x1,x2. Наборы соседние по x1 порождаютя четное количество нулей и единиц в множестве значений функции f.
И наборы соседние от x2 делают тоже самое. Может ли быть такое, что 2 набора пересекаются, т.е. пусть 1 набор соседние по x1 породили 2k единиц, а наборы соседние по x2 породили 2p единиц, Но есть 1 набор общий и для x1 и для x2. И следователь ||f|| будет нечётной.

-- 17.09.2012, 22:58 --

Спасибо. Разобрался. Не могут.

[CptPwnage]

Это можно еще доказать используя что если переменная фиктивная, то она не входит в полином Жегалкина, а значит в нем нет слагаемого самой большой степени, что возможно только если вес функция нечетный

[bgm313]

Под это вы имели ввиду основной вопрос или это ответ на последнее сообщение?

[AKM]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Тема перемещена в Карантин по следующим причинам: запись формул.


Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.