Доказать, что если замкнутый класс содержит функцию, существенно зависящую более, чем от одной переменной, то он содержит бесконечно много попарно неконгруэнтных функций. Функции называются конгруэнтными, если одна получается из другой переименованием каких-то переменных (х+у и х+z). И верно ли, что, если замкнутый класс содержит функцию, зависящую от n>1 переменных, то для любого m>n либо m=n, он содержит и функцию существенно зависящую от m переменных?

задан 14 Мар 22:04

@Cromasali: то для любого m>n либо m=n -- имеется в виду для любого m>=n? Если так, то непонятно, зачем охватывать случай m=n. Ведь для него всё уже дано в условии.

(14 Мар 22:30) falcao

@falcao: Я думал об этом, но возможно автор имел ввиду, что замкнутый класс содержит другую функцию от n переменных, отличную от первой

(14 Мар 22:41) Cromasali

@Cromasali: здесь речь идёт о существовании (хотя бы одной функции из класса), поэтому всегда можно взять ту, которая уже есть.

Ещё одну вещь дано уточнить. Нужно ли доказывать, что класс содержит функцию, существенно зависящую ровно от m переменных, или достаточно того, что по крайней мере m переменных окажутся существенными? Понять можно и так, и так.

(14 Мар 22:54) falcao

@falcao: Сам до конца не понял, но предполагаю, что "ровно"

(14 Мар 23:11) Cromasali
10|600 символов нужно символов осталось
0

Пусть $%f(x_1,\ldots,x_n)$% -- булева функция $%n$% переменных, и все они существенны. Рассмотрим суперпозицию $%g(x_1,\ldots,x_{n-1},y_1,\ldots,y_n)=f(x_1,\ldots,x_{n-1},f(y_1,\ldots,y_n))$%. Проверим, что все $%2n-1$% переменных являются существенными для $%g$%.

Для начала рассмотрим одну из переменных вида $%x_i$%. Она существенна для $%f$%, поэтому можно зафиксировать значения для остальных $%n-1$% аргументов функции $%f$% так, что полученная функция одной переменной $%x_i$% будет от неё существенно зависеть (то есть даст $%x_i$% или её отрицание). "Иксам" мы придаём заданные константные значения, а функция $%f(y_1,\ldots,y_n)$% не является константой, поэтому принимает как значение 0 на некотором наборе, так и значение 1. Выбирая подходящие "игреки", мы делаем значение последнего из аргументов "внешней" функции $%f$% заданным, и отсюда следует существенная зависимость суперпозиции от $%x_i$%.

Теперь докажем существенность каждой из переменных вида $%y_j$%. Воспользуемся тем, что последняя из переменных для $%f$% существенна. По определению, это означает, что можно выбрать константные значения для "иксов", получая не константную функцию одного аргумента (последнего). Далее, пользуясь существенностью переменной $%y_j$%, выбираем константные значения остальных "игреков" так, чтобы смена значения $%y_j$% давала смену значения функции $%f$% от набора "игреков". Тогда смена значения $%y_j$% при выбранных константных значениях прочих переменных даст изменение значения $%g$%, что доказывает существенность каждого "игрека" для композиции.

Это рассуждение показывает, что если замкнутый класс содержит функцию с $%n > 1$% существенными переменными, то он же содержит функцию с $%2n-1 > n$% существенными переменными. То есть количество существенных функций можно неограниченно увеличивать. Этим доказано последнее утверждение условия, если понимать его в смысле "не менее $%m$% переменных существенны" для любого $%m > n$%. Первое утверждение отсюда также следует, так как функции с разным числом существенных переменных не конгруэнтны.

ссылка

отвечен 16 Мар 3:01

@falcao: Если есть функция от 2 переменных, из решения вытекает, что в классе есть функция и от 4 переменных, а как получается функция от 3 переменных?

(19 Мар 5:41) Cromasali

@Cromasali: если есть f(x,y), то мы строим f(x,f(y,z)). Существенных переменных тут именно три.

(19 Мар 5:45) falcao

@falcao: Точно, я не так понял. Спасибо

(19 Мар 6:05) Cromasali

@falcao: Если второе утверждение понимать в смысле"ровно m существенных переменных", то оно не будет верным?

(19 Мар 20:26) Cromasali

@Cromasali: я в таком виде задачу не решал, так как она в этом виде не ставилась. Сам по себе вопрос интересный, но я не знаю, в какой степени он лёгкий. Ввиду того, что конец условия сформулирован был неточно, и со странностями типа лишнего m=n, я счёл этот анализ излишним.

(19 Мар 21:03) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×77

задан
14 Мар 22:04

показан
101 раз

обновлен
19 Мар 21:03

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

по почте:

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

по RSS:

Ответы

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

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