MyWikiBiz

Changes

User:Jon Awbrey/WORDPRESS (view source)

Revision as of 03:28, 5 June 2013

6,700 bytes added ,  03:28, 5 June 2013
→‎Fourier Transforms of Boolean Functions
Line 4: Line 4:     
==Tables==
 
==Tables==
 +
 +
* Examples of LaTeX tabular markup from [http://inquiryintoinquiry.com/tables/ Inquiry Into Inquiry : Tables]
    
===Boolean Functions and Propositional Calculus===
 
===Boolean Functions and Propositional Calculus===
−
  −
* Examples of LaTeX tabular markup at [http://inquiryintoinquiry.com/tables/ Inquiry Into Inquiry : Tables]
      
====Table A1. Propositional Forms on Two Variables====
 
====Table A1. Propositional Forms on Two Variables====
Line 135: Line 135:  
\\
 
\\
 
\hline
 
\hline
−
\end{tabular}&fg=000000$
+
\end{tabular}
 +
&fg=000000$
 
</pre>
 
</pre>
   Line 269: Line 270:  
\\
 
\\
 
\hline
 
\hline
−
\end{tabular}&amp;fg=000000$
+
\end{tabular}
 +
&amp;fg=000000$
 
</pre>
 
</pre>
   Line 419: Line 421:  
\\
 
\\
 
\hline
 
\hline
−
\end{tabular}&amp;fg=000000$
+
\end{tabular}
 +
&amp;fg=000000$
 
</pre>
 
</pre>
   Line 556: Line 559:  
\\
 
\\
 
\hline
 
\hline
−
\end{tabular}&amp;fg=000000$
+
\end{tabular}
 +
&amp;fg=000000$
 
</pre>
 
</pre>
   Line 693: Line 697:  
\\
 
\\
 
\hline
 
\hline
−
\end{tabular}&amp;fg=000000$
+
\end{tabular}
 +
&amp;fg=000000$
 
</pre>
 
</pre>
   Line 830: Line 835:  
\\
 
\\
 
\hline
 
\hline
−
\end{tabular}&amp;fg=000000$
+
\end{tabular}
 +
&amp;fg=000000$
 +
</pre>
 +
 
 +
===Fourier Transforms of Boolean Functions===
 +
 
 +
Re: [http://rjlipton.wordpress.com/2013/05/21/twin-primes-are-useful/ Another Problem]
 +
 
 +
<blockquote>
 +
<p>The problem is concretely about Boolean functions <math>f\!</math> of <math>k\!</math> variables, and seems not to involve prime numbers at all.  For any subset <math>S\!</math> of the coordinates, the corresponding Fourier coefficient is given by:</p>
 +
 
 +
<p align="center"><math>\hat{f}(S) = \frac{1}{2^k} \sum_{x \in \mathbb{Z}_2^k} f(x)\chi_S(x)\!</math></p>
 +
 
 +
<p>where <math>\chi_S(x)\!</math> is <math>-1\!</math> if <math>\textstyle \sum_{i \in S} x_i\!</math> is odd, and <math>+1\!</math> otherwise.</p>
 +
</blockquote>
 +
 
 +
<math>k = 1\!</math>
 +
 
 +
&hellip;
 +
 
 +
<math>k = 2\!</math>
 +
 
 +
For ease of reading formulas, let <math>x = (x_1, x_2) = (u, v).\!</math>
 +
 
 +
====Table 2.1. Values of &chi;<sub>S</sub>(x)====
 +
 
 +
<pre>
 +
$latex
 +
\begin{tabular}{|c||*{4}{c}|}
 +
\multicolumn{5}{c}{Table 2.1. Values of \( \boldsymbol{\chi}_\mathcal{S}(x) \) for \( f : \mathbb{B}^2 \to \mathbb{B} \)} \\[4pt]
 +
\hline
 +
\( \mathcal{S} \backslash (u, v) \) &amp;
 +
\( (1, 1) \) &amp;
 +
\( (1, 0) \) &amp;
 +
\( (0, 1) \) &amp;
 +
\( (0, 0) \)
 +
\\
 +
\hline\hline
 +
\( \varnothing \) &amp; \( +1 \) &amp; \( +1 \) &amp; \( +1 \) &amp; \( +1 \) \\
 +
\( \{ u \} \)    &amp; \( -1 \) &amp; \( -1 \) &amp; \( +1 \) &amp; \( +1 \) \\
 +
\( \{ v \} \)    &amp; \( -1 \) &amp; \( +1 \) &amp; \( -1 \) &amp; \( +1 \) \\
 +
\( \{ u, v \} \)  &amp; \( +1 \) &amp; \( -1 \) &amp; \( -1 \) &amp; \( +1 \) \\
 +
\hline
 +
\end{tabular}
 +
&amp;fg=000000$
 +
</pre>
 +
 
 +
====Table 2.2. Fourier Coefficients of Boolean Functions on Two Variables====
 +
 
 +
<pre>
 +
$latex
 +
\begin{tabular}{|*{5}{c|}*{4}{r|}}
 +
\multicolumn{9}{c}{Table 2.2. Fourier Coefficients of Boolean Functions on Two Variables} \\[4pt]
 +
\hline
 +
~&amp;~&amp;~&amp;~&amp;~&amp;~&amp;~&amp;~&amp;~\\
 +
\(L_1\)&amp;\(L_2\)&amp;&amp;\(L_3\)&amp;\(L_4\)&amp;
 +
\(\hat{f}(\varnothing)\)&amp;\(\hat{f}(\{u\})\)&amp;\(\hat{f}(\{v\})\)&amp;\(\hat{f}(\{u,v\})\) \\
 +
~&amp;~&amp;~&amp;~&amp;~&amp;~&amp;~&amp;~&amp;~\\
 +
\hline
 +
&amp;&amp; \(u =\)&amp; 1 1 0 0&amp;&amp;&amp;&amp;&amp; \\
 +
&amp;&amp; \(v =\)&amp; 1 0 1 0&amp;&amp;&amp;&amp;&amp; \\
 +
\hline
 +
\(f_{0}\)&amp;
 +
\(f_{0000}\)&amp;&amp;
 +
0 0 0 0&amp;
 +
\((~)\)&amp;
 +
\(0\)&amp;
 +
\(0\)&amp;
 +
\(0\)&amp;
 +
\(0\)
 +
\\
 +
\(f_{1}\)&amp;
 +
\(f_{0001}\)&amp;&amp;
 +
0 0 0 1&amp;
 +
\((u)(v)\)&amp;
 +
\(1/4\)&amp;
 +
\(1/4\)&amp;
 +
\(1/4\)&amp;
 +
\(1/4\)
 +
\\
 +
\(f_{2}\)&amp;
 +
\(f_{0010}\)&amp;&amp;
 +
0 0 1 0&amp;
 +
\((u)~v~\)&amp;
 +
\( 1/4\)&amp;
 +
\( 1/4\)&amp;
 +
\(-1/4\)&amp;
 +
\(-1/4\)
 +
\\
 +
\(f_{3}\)&amp;
 +
\(f_{0011}\)&amp;&amp;
 +
0 0 1 1&amp;
 +
\((u)\)&amp;
 +
\(1/2\)&amp;
 +
\(1/2\)&amp;
 +
\( 0 \)&amp;
 +
\( 0 \)
 +
\\
 +
\(f_{4}\)&amp;
 +
\(f_{0100}\)&amp;&amp;
 +
0 1 0 0&amp;
 +
\(~u~(v)\)&amp;
 +
\( 1/4\)&amp;
 +
\(-1/4\)&amp;
 +
\( 1/4\)&amp;
 +
\(-1/4\)
 +
\\
 +
\(f_{5}\)&amp;
 +
\(f_{0101}\)&amp;&amp;
 +
0 1 0 1&amp;
 +
\((v)\)&amp;
 +
\(1/2\)&amp;
 +
\( 0 \)&amp;
 +
\(1/2\)&amp;
 +
\( 0 \)
 +
\\
 +
\(f_{6}\)&amp;
 +
\(f_{0110}\)&amp;&amp;
 +
0 1 1 0&amp;
 +
\((u,~v)\)&amp;
 +
\( 1/2\)&amp;
 +
\( 0 \)&amp;
 +
\( 0 \)&amp;
 +
\(-1/2\)
 +
\\
 +
\(f_{7}\)&amp;
 +
\(f_{0111}\)&amp;&amp;
 +
0 1 1 1&amp;
 +
\((u~~v)\)&amp;
 +
\( 3/4\)&amp;
 +
\( 1/4\)&amp;
 +
\( 1/4\)&amp;
 +
\(-1/4\)
 +
\\
 +
\hline
 +
\(f_{8}\)&amp;
 +
\(f_{1000}\)&amp;&amp;
 +
1 0 0 0&amp;
 +
\(~u~~v~\)&amp;
 +
\( 1/4\)&amp;
 +
\(-1/4\)&amp;
 +
\(-1/4\)&amp;
 +
\( 1/4\)
 +
\\
 +
\(f_{9}\)&amp;
 +
\(f_{1001}\)&amp;&amp;
 +
1 0 0 1&amp;
 +
\(((u,~v))\)&amp;
 +
\(1/2\)&amp;
 +
\( 0 \)&amp;
 +
\( 0 \)&amp;
 +
\(1/2\)
 +
\\
 +
\(f_{10}\)&amp;
 +
\(f_{1010}\)&amp;&amp;
 +
1 0 1 0&amp;
 +
\(v\)&amp;
 +
\( 1/2\)&amp;
 +
\( 0 \)&amp;
 +
\(-1/2\)&amp;
 +
\( 0 \)
 +
\\
 +
\(f_{11}\)&amp;
 +
\(f_{1011}\)&amp;&amp;
 +
1 0 1 1&amp;
 +
\((~u~(v))\)&amp;
 +
\( 3/4\)&amp;
 +
\( 1/4\)&amp;
 +
\(-1/4\)&amp;
 +
\( 1/4\)
 +
\\
 +
\(f_{12}\)&amp;
 +
\(f_{1100}\)&amp;&amp;
 +
1 1 0 0&amp;
 +
\(u\)&amp;
 +
\( 1/2\)&amp;
 +
\(-1/2\)&amp;
 +
\( 0 \)&amp;
 +
\( 0 \)
 +
\\
 +
\(f_{13}\)&amp;
 +
\(f_{1101}\)&amp;&amp;
 +
1 1 0 1&amp;
 +
\(((u)~v~)\)&amp;
 +
\( 3/4\)&amp;
 +
\(-1/4\)&amp;
 +
\( 1/4\)&amp;
 +
\( 1/4\)
 +
\\
 +
\(f_{14}\)&amp;
 +
\(f_{1110}\)&amp;&amp;
 +
1 1 1 0&amp;
 +
\(((u)(v))\)&amp;
 +
\( 3/4\)&amp;
 +
\(-1/4\)&amp;
 +
\(-1/4\)&amp;
 +
\(-1/4\)
 +
\\
 +
\(f_{15}\)&amp;
 +
\(f_{1111}\)&amp;&amp;
 +
1 1 1 1&amp;
 +
\(((~))\)&amp;
 +
\(1\)&amp;
 +
\(0\)&amp;
 +
\(0\)&amp;
 +
\(0\)
 +
\\
 +
\hline
 +
\end{tabular}
 +
&amp;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
 +
~&amp;~&amp;~&amp;~&amp;~&amp;~&amp;~&amp;~&amp;~\\
 +
\(L_1\)&amp;\(L_2\)&amp;&amp;\(L_3\)&amp;\(L_4\)&amp;
 +
\(\hat{f}(\varnothing)\)&amp;\(\hat{f}(\{u\})\)&amp;\(\hat{f}(\{v\})\)&amp;\(\hat{f}(\{u,v\})\) \\
 +
~&amp;~&amp;~&amp;~&amp;~&amp;~&amp;~&amp;~&amp;~\\
 +
\hline
 +
&amp;&amp; \(u =\)&amp; 1 1 0 0&amp;&amp;&amp;&amp;&amp; \\
 +
&amp;&amp; \(v =\)&amp; 1 0 1 0&amp;&amp;&amp;&amp;&amp; \\
 +
\hline
 +
\(f_{0}\)&amp;
 +
\(f_{0000}\)&amp;&amp;
 +
0 0 0 0&amp;
 +
\((~)\)&amp;
 +
\(0\)&amp;
 +
\(0\)&amp;
 +
\(0\)&amp;
 +
\(0\)
 +
\\
 +
\hline
 +
\(f_{1}\)&amp;
 +
\(f_{0001}\)&amp;&amp;
 +
0 0 0 1&amp;
 +
\((u)(v)\)&amp;
 +
\(1/4\)&amp;
 +
\(1/4\)&amp;
 +
\(1/4\)&amp;
 +
\(1/4\)
 +
\\
 +
\(f_{2}\)&amp;
 +
\(f_{0010}\)&amp;&amp;
 +
0 0 1 0&amp;
 +
\((u)~v~\)&amp;
 +
\( 1/4\)&amp;
 +
\( 1/4\)&amp;
 +
\(-1/4\)&amp;
 +
\(-1/4\)
 +
\\
 +
\(f_{4}\)&amp;
 +
\(f_{0100}\)&amp;&amp;
 +
0 1 0 0&amp;
 +
\(~u~(v)\)&amp;
 +
\( 1/4\)&amp;
 +
\(-1/4\)&amp;
 +
\( 1/4\)&amp;
 +
\(-1/4\)
 +
\\
 +
\(f_{8}\)&amp;
 +
\(f_{1000}\)&amp;&amp;
 +
1 0 0 0&amp;
 +
\(~u~~v~\)&amp;
 +
\( 1/4\)&amp;
 +
\(-1/4\)&amp;
 +
\(-1/4\)&amp;
 +
\( 1/4\)
 +
\\
 +
\hline
 +
\(f_{3}\)&amp;
 +
\(f_{0011}\)&amp;&amp;
 +
0 0 1 1&amp;
 +
\((u)\)&amp;
 +
\(1/2\)&amp;
 +
\(1/2\)&amp;
 +
\( 0 \)&amp;
 +
\( 0 \)
 +
\\
 +
\(f_{12}\)&amp;
 +
\(f_{1100}\)&amp;&amp;
 +
1 1 0 0&amp;
 +
\(u\)&amp;
 +
\( 1/2\)&amp;
 +
\(-1/2\)&amp;
 +
\( 0 \)&amp;
 +
\( 0 \)
 +
\\
 +
\hline
 +
\(f_{6}\)&amp;
 +
\(f_{0110}\)&amp;&amp;
 +
0 1 1 0&amp;
 +
\((u,~v)\)&amp;
 +
\( 1/2\)&amp;
 +
\( 0 \)&amp;
 +
\( 0 \)&amp;
 +
\(-1/2\)
 +
\\
 +
\(f_{9}\)&amp;
 +
\(f_{1001}\)&amp;&amp;
 +
1 0 0 1&amp;
 +
\(((u,~v))\)&amp;
 +
\(1/2\)&amp;
 +
\( 0 \)&amp;
 +
\( 0 \)&amp;
 +
\(1/2\)
 +
\\
 +
\hline
 +
\(f_{5}\)&amp;
 +
\(f_{0101}\)&amp;&amp;
 +
0 1 0 1&amp;
 +
\((v)\)&amp;
 +
\(1/2\)&amp;
 +
\( 0 \)&amp;
 +
\(1/2\)&amp;
 +
\( 0 \)
 +
\\
 +
\(f_{10}\)&amp;
 +
\(f_{1010}\)&amp;&amp;
 +
1 0 1 0&amp;
 +
\(v\)&amp;
 +
\( 1/2\)&amp;
 +
\( 0 \)&amp;
 +
\(-1/2\)&amp;
 +
\( 0 \)
 +
\\
 +
\hline
 +
\(f_{7}\)&amp;
 +
\(f_{0111}\)&amp;&amp;
 +
0 1 1 1&amp;
 +
\((u~~v)\)&amp;
 +
\( 3/4\)&amp;
 +
\( 1/4\)&amp;
 +
\( 1/4\)&amp;
 +
\(-1/4\)
 +
\\
 +
\hline
 +
\(f_{11}\)&amp;
 +
\(f_{1011}\)&amp;&amp;
 +
1 0 1 1&amp;
 +
\((~u~(v))\)&amp;
 +
\( 3/4\)&amp;
 +
\( 1/4\)&amp;
 +
\(-1/4\)&amp;
 +
\( 1/4\)
 +
\\
 +
\(f_{13}\)&amp;
 +
\(f_{1101}\)&amp;&amp;
 +
1 1 0 1&amp;
 +
\(((u)~v~)\)&amp;
 +
\( 3/4\)&amp;
 +
\(-1/4\)&amp;
 +
\( 1/4\)&amp;
 +
\( 1/4\)
 +
\\
 +
\(f_{14}\)&amp;
 +
\(f_{1110}\)&amp;&amp;
 +
1 1 1 0&amp;
 +
\(((u)(v))\)&amp;
 +
\( 3/4\)&amp;
 +
\(-1/4\)&amp;
 +
\(-1/4\)&amp;
 +
\(-1/4\)
 +
\\
 +
\hline
 +
\(f_{15}\)&amp;
 +
\(f_{1111}\)&amp;&amp;
 +
1 1 1 1&amp;
 +
\(((~))\)&amp;
 +
\(1\)&amp;
 +
\(0\)&amp;
 +
\(0\)&amp;
 +
\(0\)
 +
\\
 +
\hline
 +
\end{tabular}
 +
&amp;fg=000000$
 
</pre>
 
</pre>
  
Jon Awbrey
12,089

edits

Retrieved from "https://mywikibiz.com/Special:MobileDiff/181547...181988"