Ряды фурье для булевых функций

[BapuK]

В какой книжке можно про них прочитать?

[lel0lel]

(Оффтоп)

Сначала хотел написать, что это что-то из области фантастики, потому как трудно представить, как может булева функция удовлетворять условиям Дирихле. Но погуглив, на нескольких серьёзных сайтах нашел упоминания об этом, правда там всё больше темы конференций, а не литература.

[Xaositect]

В книге "Булевы функции в теории кодирования и криптологии" активно используется преобразование Фурье булевых функций, но на основах авторы подробно не останавливаются.

Есть обзор http://www.cs.cmu.edu/~odonnell/papers/ ... survey.pdf

Есть еще хорошее введение в http://cosec.bit.uni-bonn.de/fileadmin/ ... /tof05.pdf , там рассматривается общий случай функций над конечным полем, главы по булевым функциям есть.

[BapuK]

lel0lel в сообщении #327001 писал(а):

(Оффтоп)

Сначала хотел написать, что это что-то из области фантастики, потому как трудно представить, как может булева функция удовлетворять условиям Дирихле. Но погуглив, на нескольких серьёзных сайтах нашел упоминания об этом, правда там всё больше темы конференций, а не литература.

(Оффтоп)

могу даже подсказать как выглядят эти ряды:

$$f(x_1,\dots,x_n)=2^{-n}\sum\limits_{\alpha\in V_n} C_\alpha^f (-1)^{(\alpha , x)},$$

где $\alpha = (\alpha_1, \dots, \alpha_n), x = (x_1, \dots, x_n), V_n$ - всевозможные вектора длины $n$ над множеством $\{0,1\}. C_\alpha^f = \sum_{x\in V_n} f(x)(-1)^{(\alpha , x)}$ и $(a,b) = a_1b_1 + \dots a_nb_n$, где сложение ведется по модулю 2.

Просто у нас преподаватель, который ведет дискретную математику, весь материал берет из каких-либо книжек, про которые нам ничего не рассказывает, думал может здесь знают откуда же он его берет)

[RIP]

Ещё по анализу Фурье на конечных группах рекомендуют книжку A. Terras, Fourier analysis on finite groups and applications, но сам я не читал (и в свободном доступе книжка не очень хочет находиться).

[Ales]

Ряды Фурье появились для решения линейных дифференциальных уравнений.
Решение ищется в виде суммы собственных функций оператора дифференцирования.
Экспонента, синусы и косинусы.

Для чего нужны ряды Фурье булевых функций? Какие задачи они помогают решить?

[Xaositect]

Ales в сообщении #327128 писал(а):

Для чего нужны ряды Фурье булевых функций? Какие задачи они помогают решить?

Они используются для изучения алгебраических свойств, например таких, как нелинейность(широко используется в криптологии). Также есть оценки, связывающие спектральные характеристики и сложность реализации булевых функций: http://ilex.iit.cnr.it/codenotti/ps_files/fourier.ps . Наверняка еще есть применения.

[Ales]

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

Они используются для изучения алгебраических свойств

А они там естественно возникли или принесены искусственно?
Не факт ведь, что ряды полезные в гладком анализе, будут также полезны в дискретной математике.
Хорошо ли вводить ряды Фурье для булевых функций?

[warezhunter_]

Как раз в тему:
Помогите разложить в ряд Фурье следующую булеву функцию:
$f(a,b,c)=(a \cap c) \cup ({\overline{a}} \cap {\overline{c}})$

[BapuK]

warezhunter_ в сообщении #336754 писал(а):

Как раз в тему:
Помогите разложить в ряд Фурье следующую булеву функцию:
$f(a,b,c)=(a \cap c) \cup ({\overline{a}} \cap {\overline{c}})$

каким методом разложить надо и в чем затруднения?

[warezhunter_]

BapuK в сообщении #336774 писал(а):

warezhunter_ в сообщении #336754 писал(а):

Как раз в тему:
Помогите разложить в ряд Фурье следующую булеву функцию:
$f(a,b,c)=(a \cap c) \cup ({\overline{a}} \cap {\overline{c}})$

каким методом разложить надо и в чем затруднения?

Затруднение в том, что я просто не могу найти практический материал или похожий пример как это сделать, в учебниках не понятно ничего.

[warezhunter_]

А, все похоже разобрался, сначала строим матрицу Уолша, затем Радехаммера, перемножаем по таблице истинности функцию и матрицу Радехаммера, получаем коэффициенты Уолша и затем формируем ряд Фурье.

[BapuK]

warezhunter_ в сообщении #336807 писал(а):

А, все похоже разобрался, сначала строим матрицу Уолша, затем Радехаммера, перемножаем по таблице истинности функцию и матрицу Радехаммера, получаем коэффициенты Уолша и затем формируем ряд Фурье.

Все верно, только таким образом получаем коэффициенты Фурье, если бы переменожали столбец истинности действительной функции, которая соответсвует данной булевой, то получили бы коэффициенты Уолша.