Дискретная математика (помогите)

[sts05]

Добрый день! Не могли бы вы помочь с задачей по дискретной математике? Дали задание совсем не по курсу (препод, мягко говоря, не хороший...) Несколько дней мучаюсь, информацию найти не могу. Хотя бы идейку подкиньте.
Задание:


Зарание спасибо.

[cepesh]

картинку перезагрузите куда-нить, например, на http://**invalid link**

[Руст]

Возьмите функцию:

$$f(x)=(1+x_1^2)\prod_{k=2}^n [x_k^2+(x_k-1)^2].$$

Так как каждый множитель (при действительных аргументах) больше или равно 1, то f(x) будет равно 1 только в случае, когда все множители равны 1. А это имеет ровно $2^{n-1}$ решений (n>0).

[sts05]

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

[PAV]

Вообще-то привести пример есть лучший способ доказательства существования...

Но возможно пройдет следующий метод. С одной стороны, можно подсчитать количество функций логики, которые принимают значение 1 ровно на $2^{n-1}$ наборах. Это число равно $C_{2^n}^{2^{n-1}}$

С другой стороны, наверняка в курсе был подсчет числа линейных функций. (Что, кстати, означает понятие линейной логической функции?) Сгодится даже не точное значение, а оценка сверху. Если окажется, что это число меньше указанного выше, то это и есть доказательство. И вполне возможно, что при $n\le 2$ это утверждение не пройдет.

[Руст]

Доказательство я привёл каждый множитель имеет два решения.
А если функция логики, то это ещё проще.

[sts05]

Линейная функция - это функция f(x_1,x_2...x_n), в которой нет перемножений (конъюкций) между переменными, например f ( x_1,x_2...x_n)=c_0+c_1 * x_1 + c_2 * x_2 +...+ c_n * x_n В нелинейной имеются конъюкции между аргументами.
Количество значений функции всего 2^n. Если единиц будет 2^{n-1}, то остальные будут нули (тоже 2^{n-1}).
Придумать функцию можно, но решение мне не засчитают.

[Руст]

Линейная это тривиальный вариант. Можно и аналог дествительной функции, приведённой выше. Например:
$x_1(x_2Vx_3V....Vx_n)V(s(x_1)s(x_2x_3...x_n)).$
Здесь, через s я обозначил отрицание.

[sts05]

Где-то мелькало, когда искал инфу, что нужно разложить по первой переменной, т.е. f(x_1,x_2,x_3...x_n)=x_1*f(1,x_2,x_3...x_n)V s(x_1)*f(0,x_2,x_3...x_n) (s - отрицание). Только как это применить? Советовали индукцией дальше, но не доходит что-то до меня

[nworm]

Число линейных ФАЛ от $n$ переменных - есть $2^{n+1}$ и доказательство PAV проходит.

[juna]

Пока писал ответ, nworm - уже все, что нужно указал. Не хочется осознавать , что трудился напрасно, поэтому продублирую, простите
Идея должна быть такая – оценить мощность множества линейных функций как функцию от $n$ - $M(n)$ и показать, что $\forall {n\geqslant3}M(n)<C_{2^n}^{2^{n-1}}$
Функция $M(n)=2^{n+1}$ - легко находится.
Для $n<3$ оценка не проходит. Так, что Ваш преподаватель ничего некорректного не спрашивает – считайте, что хороший.

[sts05]

Артамонов Ю.Н. писал(а):

Так, что Ваш преподаватель ничего некорректного не спрашивает – считайте, что хороший.

Может и корректное спрашивает, но не для нашего уровня Ничего близко похожего на лекциях не слышал.

[PAV]

sts05 писал(а):

Может и корректное спрашивает, но не для нашего уровня Ничего близко похожего на лекциях не слышал.

Но ведь наверняка многие результаты дискретной математики в курсе доказывались путем нахождения или оценки мощности тех или иных множеств объектов. Так что это просто достаточно общий метод решения задач в данной области. Преподаватель просто проверяет, насколько студенты осознали саму идею метода и готовы применять его для решения новых задач, которые видят впервые.

[Руст]

Но это не совсем корректно. Говорит только о существовании нелинейных функций, для которых не существует линейной функции, совпадающей с ним при всех значениях аргументов из набора 0,1. При n<3 такие нелинейные функции так же существуют, но для них существует линейный аналог.

[sts05]

PAV писал(а):

Но ведь наверняка многие результаты дискретной математики в курсе доказывались путем нахождения или оценки мощности тех или иных множеств объектов. Так что это просто достаточно общий метод решения задач в данной области. Преподаватель просто проверяет, насколько студенты осознали саму идею метода и готовы применять его для решения новых задач, которые видят впервые.

Не учили мы мощности множеств. Ничерта мы толкового не учили. Препод даже по русски то нормально не говорит. Зато гордится тем, что в МГУ учился. Теперь этим нас и заваливает

У меня просьба, не могли бы вы написать решение задачи, которое я мог бы сдать, а то у меня такое чувство, что я сам так и не пойму ничего.
Спасибо.