Докажите, что коэффициент при каждом одночлене в многочлене Жегалкина равен сумме значений функции на некоторых наборах. На каких наборах?

задан 15 Окт 22:12

10|600 символов нужно символов осталось
2

Пусть дана функция $%f(x_1,...,x_n)$%. Тогда коэффициент полинома Жегалкина при одночлене $%x^{d_1}...x^{d_n}$%, где показатели равны нулю или единице, равен сумме значений функции на всех наборах $%(\alpha_1,...,\alpha_n)$%, для которых $%\alpha_i\le d_i$% при всех $%1\le i\le n$%.

Иными словами, если какая-то переменная в запись одночлена не входит, то в наборе соответствующую координату полагаем нулевой, а остальные координаты принимают любые значения. Например, при $%n=3$% коэффициент при $%x_1x_3$% равен сумме значений на четырёх наборах: $%f(0,0,0)+f(0,0,1)+f(1,0,0)+f(1,0,1)$%.

Легко заметить, что если утверждение верно для функций $%f$% и $%g$%, то оно верно и для суммы функций $%f+g$%. Это следует из того, что условие на наборы зависит только от одночлена, а сумма значений функции $%f+g$% по всем таким наборам равна сумме значений $%f$% плюс сумма значений $%g$%.

По индукции, сказанное верно для любого числа слагаемых. Поэтому достаточно доказать утверждение для функций, которые можно назвать базисными. Это те функции, которые ровно на одном наборе равны $%1$%. Ясно, что любая функция задаётся вектором значений, а он равен сумме базисных.

Пусть $%f$% базисная, и она равна $%1$% на одном наборе $%\beta=(\beta_1,...,\beta_n)$%. Тогда её полином Жегалкина равен произведению $%(x_1+\beta_1+1)...(x_n+\beta_n+1)$%. Это очевидно, так как произведение равно $%1$% тогда и только тогда, когда все сомножители равны $%1$%.

Сумма значений такой функции $%f$% на любом множестве наборов равна $%0$%, если набор $%\beta$% в это множество не входит, и равна $%1$%, если входит. При раскрытии скобок в произведении, переменная $%x_i$% присутствует во всех одночленах тогда и только тогда, когда $%\beta_i=1$%. Моном $%x_1^{d_1}...x_n^{d_n}$% войдёт в состав полинома тогда и только тогда, когда из первой скобки можно взять $%x_1^{d_1}$%, ... , из $%n$%-й можно взять $%x_n^{d_n}$%. При этом $%x_i=x_i^1$% всегда можно взять из $%i$%-й скобки, а $%x_i^0$% только если $%\beta_i=0$%. Поэтому коэффициент при рассматриваемом мономе равен $%1$% тогда и только тогда, когда из $%d_i=0$% следует $%\beta_i=0$% для всех $%i$%. Последнее равносильно неравенству $%\beta_i\le d_i$%. А это в точности означает, что набор $%\beta$% попал в состав числа тех мономов, по которым мы суммируем значения функции, чтобы получить коэффициент при данном одночлене.

ссылка

отвечен 15 Окт 23:14

1

Похоже сегодня день математической логики!) Прошу прощения за офтоп)

(15 Окт 23:33) Klin

@Klin: соприкосновение с этой благородной областью математики всегда можно только приветствовать. Чай, не дифференциальная геометрия какая-нибудь, и не уравнения матфизики! :)

(15 Окт 23:37) falcao

@falcao, чем Вам нравится этот раздел? У меня он почему-то вызывает отторжение

(15 Окт 23:44) haosfortum

@haosfortum: комбинаторика, дискретная математика, математическая логика, теория чисел, хорошие разделы алгебры (не алгебраическая геометрия), теория вероятностей -- это всё я считаю наиболее для себя интересным.

Полиномы Жегалкина, например, прекрасная и удобная вещь, так как они полностью "убивают" старую булеву алгебру с вычислениями в неудобной сигнатуре с x V y вместо правильного x+y (исключающего или).

(16 Окт 0:46) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×911

задан
15 Окт 22:12

показан
64 раза

обновлен
16 Окт 0:46

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

по почте:

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

по RSS:

Ответы

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

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