Кто силен в дискре и матлогике?

[Gilb007]

Условие задачи:
_____________________________________________________
Показать, что средняя сложность системы, состоящей из n-местных
дизъюнкции и конъюнкции, зависящих от одних и тех же перемен-
ных, не превосходит пяти.
_____________________________________________________

Ребята,помогите плиз)

[Бодигрим]

Хотя бы определения знаете? Приведите.

[Gilb007]

Привожу ссылку на лекции преподавателя,который собственно и дал эту задачу.

http://www.math.msu.su/department/dm/dmmc/EDU/DM07.pdf

Определение в лекции 11 (в ней же в конце эта задача) на стр. 164-165.

Если быть еще конкретнее,то он написал систему из двух уравнений:

x1 OR x2 OR...........OR xn
x1 AND x2 AND ......AND xn

Нужно найти среднюю сложность этой системы.

[AKM]

Forum Administration в сообщении #31728 писал(а):

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

Вы, похоже, не поняли про определение.
Это Вам предлагается его изучить и начинать решать.
Видимо, автор вопроса готов Вам помочь, подсказать; а не решать за Вас.

[Xaositect]

Там есть схемы отдельно для конъюнкции и дизъюнкции.
Можно по аналогии построить схему для двух функций, вроде должно прокатить.

[Gilb007]

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

[Бодигрим]

Конкретнее: вам надо скомбинировать схему из двух схем, приводимых в доказательстве теоремы 11.2.

[Xaositect]

Gilb007 в сообщении #219743 писал(а):

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

Давайте я пример напишу.
Вот такая программа
$z_1 = 1$
$y = x_1\oplus x_2$
$z_2 = y\oplus x_3$
$\mathtt{Stop}(z_2)$
$\mathtt{Stop}(y)$
$\mathtt{Stop}(x_1)$
$z_1 = 0$
вычисляет две функции $z_1 = x_1\vee x_2\vee x_3$, $z_2 = x_1\oplus x_2\oplus x_3$

Средняя ее сложность $\dfrac{1}{8}(\overset{001,010,100,111}{4\cdot 4} + \overset{011,101}{2\cdot 5} + \overset{110}{6} + \overset{000}{7}) = \dfrac{39}{8}$

Или непонятки не в этом?

[Gilb007]

Друзья,сорри за долгое молчание!Только сегодня смог добраться до компа!

Xaositect,спасибо за ответ!
Только не совсем понял ваш пример.Вторая операция сложения по модуля два в вашей программе можно было бы заменить на конъюнкцию и по аналогии вычислить среднюю сложность программы?