12,179
edits
Changes
MyWikiBiz, Author Your Legacy — Tuesday December 16, 2025
Jump to navigationJump to search→Fourier Transforms of Boolean Functions
$latex
$latex
\begin{tabular}{|c|c||c|c|c|c|}
\begin{tabular}{|c|c||c|c|c|c|}
\multicolumn{6}{c}{Table A6. \(\mathrm{D}f\) Expanded Over Ordinary Features \(\{x, y\}\)} \\
\multicolumn{6}{c}{Table A5. \(\mathrm{E}f\) Expanded Over Ordinary Features \(\{x, y\}\)} \\
\hline
\hline
&
&
\(~~~~~~~~ f ~~~~~~~~\)&
\(~~~~~~~~ f ~~~~~~~~\)&
\(~~\mathrm{D}f|_{ x\;y }~~~\)&
\(~~\mathrm{E}f|_{ x\;y }~~~\)&
\(~~\mathrm{D}f|_{ x~(y)}\,~~\)&
\(~~\mathrm{E}f|_{ x~(y)}\,~~\)&
\(~~\mathrm{D}f|_{(x)~y }\,~~\)&
\(~~\mathrm{E}f|_{(x)~y }\,~~\)&
\(~~\mathrm{D}f|_{(x)(y)}\,~\)
\(~~\mathrm{E}f|_{(x)(y)}\;~\)
\\
\\
\hline\hline
\hline\hline
\(f_{1}\)&
\(f_{1}\)&
\((x)(y)\)&
\((x)(y)\)&
~d\(x\)~~d\(y~\)&
~d\(x\)~(d\(y\))&
(d\(x\))~d\(y~\)&
(d\(x\))(d\(y\))
\\
\\
\(f_{2}\)&
\(f_{2}\)&
\((x)~y~\)&
\((x)~y~\)&
~d\(x\)~(d\(y\))&
~d\(x\)~~d\(y~\)&
(d\(x\))(d\(y\))&
(d\(x\))~d\(y~\)
\\
\\
\(f_{4}\)&
\(f_{4}\)&
\(~x~(y)\)&
\(~x~(y)\)&
(d\(x\))~d\(y~\)&
(d\(x\))(d\(y\))&
~d\(x\)~~d\(y~\)&
~d\(x\)~(d\(y\))
\\
\\
\(f_{8}\)&
\(f_{8}\)&
\(~x~~y~\)&
\(~x~~y~\)&
(d\(x\))(d\(y\))&
(d\(x\))~d\(y~\)&
~d\(x\)~(d\(y\))&
~d\(x\)~~d\(y~\)
\\
\\
\hline
\hline
\(f_{3}\)&
\(f_{3}\)&
\((x)\)&
\((x)\)&
d\(x\)&
d\(x\) &
d\(x\)&
d\(x\) &
d\(x\)&
(d\(x\))&
d\(x\)
(d\(x\))
\\
\\
\(f_{12}\)&
\(f_{12}\)&
\( x \)&
\( x \)&
d\(x\)&
(d\(x\))&
d\(x\)&
(d\(x\))&
d\(x\)&
d\(x\) &
d\(x\)
d\(x\)
\\
\\
\hline
\hline
\(f_{6}\)&
\(f_{6}\)&
\( (x,y) \)&
\( (x,y) \)&
(d\(x\), d\(y\))&
(d\(x\), d\(y\)) &
(d\(x\), d\(y\))&
((d\(x\), d\(y\)))&
(d\(x\), d\(y\))&
((d\(x\), d\(y\)))&
(d\(x\), d\(y\))
(d\(x\), d\(y\))
\\
\\
\(f_{9}\)&
\(f_{9}\)&
\(((x,y))\)&
\(((x,y))\)&
(d\(x\), d\(y\))&
((d\(x\), d\(y\)))&
(d\(x\), d\(y\))&
(d\(x\), d\(y\)) &
(d\(x\), d\(y\))&
(d\(x\), d\(y\)) &
(d\(x\), d\(y\))
((d\(x\), d\(y\)))
\\
\\
\hline
\hline
\(f_{5}\)&
\(f_{5}\)&
\((y)\)&
\((y)\)&
d\(y\)&
d\(y\) &
d\(y\)&
(d\(y\))&
d\(y\)&
d\(y\) &
d\(y\)
(d\(y\))
\\
\\
\(f_{10}\)&
\(f_{10}\)&
\( y \)&
\( y \)&
d\(y\)&
(d\(y\))&
d\(y\)&
d\(y\) &
d\(y\)&
(d\(y\))&
d\(y\)
d\(y\)
\\
\\
\hline
\hline
\((~x~~y~)\)&
\((~x~~y~)\)&
((d\(x\))(d\(y\)))&
((d\(x\))(d\(y\)))&
((d\(x\))~d\(y\)~)&
(~d\(x\)~(d\(y\)))&
(~d\(x\)~~d\(y\)~)
\\
\\
\(f_{11}\)&
\(f_{11}\)&
\((~x~(y))\)&
\((~x~(y))\)&
((d\(x\))~d\(y\)~)&
((d\(x\))(d\(y\)))&
((d\(x\))(d\(y\)))&
(~d\(x\)~~d\(y\)~)&
(~d\(x\)~(d\(y\)))
\\
\\
\(f_{13}\)&
\(f_{13}\)&
\(((x)~y~)\)&
\(((x)~y~)\)&
(~d\(x\)~(d\(y\)))&
(~d\(x\)~~d\(y\)~)&
((d\(x\))(d\(y\)))&
((d\(x\))(d\(y\)))&
((d\(x\))~d\(y\)~)
\\
\\
\(f_{14}\)&
\(f_{14}\)&
\(((x)(y))\)&
\(((x)(y))\)&
(~d\(x\)~~d\(y\)~)&
(~d\(x\)~(d\(y\)))&
((d\(x\))~d\(y\)~)&
((d\(x\))(d\(y\)))
((d\(x\))(d\(y\)))
\\
\\
\(f_{15}\)&
\(f_{15}\)&
1&
1&
1&
1&
1&
1
\\
\\
\hline
\hline
\\
\\
\hline
\hline
\end{tabular}&fg=000000$
\end{tabular}
&fg=000000$
</pre>
</pre>
For ease of reading formulas, let <math>x = (x_1, x_2) = (u, v).\!</math>
For ease of reading formulas, let <math>x = (x_1, x_2) = (u, v).\!</math>
====Table 2.1. Values of χ<sub>S</sub>(x)====
<pre>
<pre>
$latex
$latex
\begin{tabular}{|c||*{4}{c}|}
\begin{tabular}{|c||*{4}{c}|}
\multicolumn{5}{c}{Table 2.1. Values of \( \chi_S(x) \) for \( f : \mathbb{B}^2 \to \mathbb{B} \)} \\[4pt]
\multicolumn{5}{c}{Table 2.1. Values of \( \boldsymbol{\chi}_\mathcal{S}(x) \) for \( f : \mathbb{B}^2 \to \mathbb{B} \)} \\[4pt]
\hline
\hline
\( S \backslash (u, v) \) &
\( \mathcal{S} \backslash (u, v) \) &
\( (1, 1) \) &
\( (1, 1) \) &
\( (1, 0) \) &
\( (1, 0) \) &
\end{tabular}
\end{tabular}
&fg=000000$
&fg=000000$
</pre>
</pre>
====Table 2.2. Fourier Coefficients of Boolean Functions on Two Variables====
<pre>
<pre>
$latex
$latex
\begin{tabular}{|*{5}{c|}*{4}{r|}}
\begin{tabular}{|*{5}{c|}*{4}{r|}}
\hline
\hline
~&~&~&~&~&~&~&~&~\\
~&~&~&~&~&~&~&~&~\\
\( L_1 \)&
\(L_1\)&\(L_2\)&&\(L_3\)&\(L_4\)&
\( L_2 \)&&
\(\hat{f}(\varnothing)\)&\(\hat{f}(\{u\})\)&\(\hat{f}(\{v\})\)&\(\hat{f}(\{u,v\})\) \\
\( L_3 \)&
\( L_4 \)&
\( \hat{f}(\varnothing) \)&
\( \hat{f}(\{u\}) \)&
\( \hat{f}(\{v\}) \)&
\( \hat{f}(\{u,v\}) \)
\\
~&~&~&~&~&~&~&~&~\\
~&~&~&~&~&~&~&~&~\\
\hline
\hline
\\
\\
\hline
\hline
\end{tabular}&fg=000000$
\end{tabular}
</p>
&fg=000000$
</pre>
====Table 2.3. Fourier Coefficients of Boolean Functions on Two Variables====
<pre>
$latex
\begin{tabular}{|*{5}{c|}*{4}{r|}}
\multicolumn{9}{c}{Table 2.3. Fourier Coefficients of Boolean Functions on Two Variables} \\[4pt]
\hline
~&~&~&~&~&~&~&~&~\\
\(L_1\)&\(L_2\)&&\(L_3\)&\(L_4\)&
\(\hat{f}(\varnothing)\)&\(\hat{f}(\{u\})\)&\(\hat{f}(\{v\})\)&\(\hat{f}(\{u,v\})\) \\
~&~&~&~&~&~&~&~&~\\
\hline
&& \(u =\)& 1 1 0 0&&&&& \\
&& \(v =\)& 1 0 1 0&&&&& \\
\hline
\(f_{0}\)&
\(f_{0000}\)&&
0 0 0 0&
\((~)\)&
\(0\)&
\(0\)&
\(0\)&
\(0\)
\\
\hline
\(f_{1}\)&
\(f_{0001}\)&&
0 0 0 1&
\((u)(v)\)&
\(1/4\)&
\(1/4\)&
\(1/4\)&
\(1/4\)
\\
\(f_{2}\)&
\(f_{0010}\)&&
0 0 1 0&
\((u)~v~\)&
\( 1/4\)&
\( 1/4\)&
\(-1/4\)&
\(-1/4\)
\\
\(f_{4}\)&
\(f_{0100}\)&&
0 1 0 0&
\(~u~(v)\)&
\( 1/4\)&
\(-1/4\)&
\( 1/4\)&
\(-1/4\)
\\
\(f_{8}\)&
\(f_{1000}\)&&
1 0 0 0&
\(~u~~v~\)&
\( 1/4\)&
\(-1/4\)&
\(-1/4\)&
\( 1/4\)
\\
\hline
\(f_{3}\)&
\(f_{0011}\)&&
0 0 1 1&
\((u)\)&
\(1/2\)&
\(1/2\)&
\( 0 \)&
\( 0 \)
\\
\(f_{12}\)&
\(f_{1100}\)&&
1 1 0 0&
\(u\)&
\( 1/2\)&
\(-1/2\)&
\( 0 \)&
\( 0 \)
\\
\hline
\(f_{6}\)&
\(f_{0110}\)&&
0 1 1 0&
\((u,~v)\)&
\( 1/2\)&
\( 0 \)&
\( 0 \)&
\(-1/2\)
\\
\(f_{9}\)&
\(f_{1001}\)&&
1 0 0 1&
\(((u,~v))\)&
\(1/2\)&
\( 0 \)&
\( 0 \)&
\(1/2\)
\\
\hline
\(f_{5}\)&
\(f_{0101}\)&&
0 1 0 1&
\((v)\)&
\(1/2\)&
\( 0 \)&
\(1/2\)&
\( 0 \)
\\
\(f_{10}\)&
\(f_{1010}\)&&
1 0 1 0&
\(v\)&
\( 1/2\)&
\( 0 \)&
\(-1/2\)&
\( 0 \)
\\
\hline
\(f_{7}\)&
\(f_{0111}\)&&
0 1 1 1&
\((u~~v)\)&
\( 3/4\)&
\( 1/4\)&
\( 1/4\)&
\(-1/4\)
\\
\hline
\(f_{11}\)&
\(f_{1011}\)&&
1 0 1 1&
\((~u~(v))\)&
\( 3/4\)&
\( 1/4\)&
\(-1/4\)&
\( 1/4\)
\\
\(f_{13}\)&
\(f_{1101}\)&&
1 1 0 1&
\(((u)~v~)\)&
\( 3/4\)&
\(-1/4\)&
\( 1/4\)&
\( 1/4\)
\\
\(f_{14}\)&
\(f_{1110}\)&&
1 1 1 0&
\(((u)(v))\)&
\( 3/4\)&
\(-1/4\)&
\(-1/4\)&
\(-1/4\)
\\
\hline
\(f_{15}\)&
\(f_{1111}\)&&
1 1 1 1&
\(((~))\)&
\(1\)&
\(0\)&
\(0\)&
\(0\)
\\
\hline
\end{tabular}
&fg=000000$
</pre>
</pre>
