Content deleted Content added
+ it |
Added section on ANF |
||
Line 7:
There are <math>2^{2^n}</math> such functions; these play a basic role in questions of [[complexity theory]] as well as the design of circuits and chips for [[digital computer]]s. The properties of boolean functions play a critical role in [[cryptography]], particularly in the design of [[symmetric key algorithm]]s (see [[S-box]]).
A '''boolean operation''' on boolean-valued functions combines values point-wise (for example, by [[Exclusive or|XOR]], or other [[boolean operator]]).
==Algebraic Normal Form==
A boolean function can be written uniquely as a sum ([[Exclusive or|XOR]]) of products ([[Logical_conjunction|AND]]). This is known as the [[Algebraic Normal Form]] (ANF).
<math>f(x_1, x_2, \ldots , x_n) = a_0 \oplus a_1x_1 \oplus a_2x_2 \oplus \ldots \oplus a_nx_n \oplus a_{1,2}x_1x_2 \oplus a_{n-1,n}x_{n-1}x_n \oplus \ldots \oplus a_{1,2,\ldots,n}x_1x_2\ldots x_n</math>
==See also==
| |||