Symmetric Boolean function

In mathematics, a symmetric Boolean function is a Boolean function whose value does not depend on the order of its input bits, i.e., it depends only on the number of ones (or zeros) in the input. Ingo Wegener, "The Complexity of Symmetric Boolean Functions", in: ''Computation Theory and Logic'', ''Lecture Notes in Computer Science'', vol. 270, 1987, pp. 433–442 For this reason they are also known as Boolean counting functions.

There are 2^''n''+1 symmetric ''n''-ary Boolean functions. Instead of the truth table, traditionally used to represent Boolean functions, one may use a more compact representation for an ''n''-variable symmetric Boolean function: the (''n'' + 1)-vector, whose ''i''-th entry (''i'' = 0, ..., ''n'') is the value of the function on an input vector with ''i'' ones. Mathematically, the symmetric Boolean functions correspond one-to-one with the functions that map ''n+1'' elements to two elements, $f: \ \rightarrow \$.

Symmetric Boolean functions are used to classify Boolean satisfiability problems.

Special cases

A number of special cases are recognized:

*Majority function: their value is 1 on input vectors with more than n/2 ones
*Threshold functions: their value is 1 on input vectors with ''k'' or more ones for a fixed ''k''
*All-equal and not-all-equal function: their values is 1 when the inputs do (not) all have the same value
*Exact-count functions: their value is 1 on input vectors with ''k'' ones for a fixed ''k''
**One-hot or 1-in-n function: their value is 1 on input vectors with exactly one one
**One-cold function: their value is 1 on input vectors with exactly one zero
* Congruence functions: their value is 1 on input vectors with the number of ones congruent to ''k'' mod ''m'' for fixed ''k'', ''m''
* Parity function: their value is 1 if the input vector has odd number of ones
The n-ary versions of AND, OR, XOR, NAND, NOR and XNOR are also symmetric Boolean functions.

Properties

In the following, $f_k$ denotes the value of the function $f: \^n \rightarrow \$ when applied to an input vector of weight $k$.

Weight

The weight of the function can be calculated from its value vector:

$, f, = \sum_^n \binomf_k$

Algebraic normal form

The algebraic normal form either contains all monomials of certain order $m$, or none of them; i.e. the Möbius transform $\hat f$ of the function is also a symmetric function. It can thus also be described by a simple (''n''+1) bit vector, the ''ANF vector'' $\hat f_m$. The ANF and value vectors are related by a Möbius relation:$\hat f_m = \bigoplus_ f_k$where $k_2 \subseteq m_2$ denotes all the weights ''k'' whose base-2 representation is covered by the base-2 representation of ''m'' (a consequence of Lucas’ theorem). Effectively, an n-variable symmetric Boolean function corresponds to a log(n)-variable ordinary Boolean function acting on the base-2 representation of the input weight.

For example, for three-variable functions:

$\begin\hat f_0 & = & f_0 \\ \hat f_1 & = & f_0 \oplus f_1 \\ \hat f_2 & = & f_0 \oplus f_2 \\ \hat f_3 & = & f_0 \oplus f_1 \oplus f_2 \oplus f_3 \end$

So the three variable majority function with value vector (0, 0, 1, 1) has ANF vector (0, 0, 1, 0), i.e.:$\text(x, y, z) = xy \oplus xz \oplus yz$

Unit hypercube polynomial

The coefficients of the real polynomial agreeing with the function on $\^n$ are given by:$f^*_m = \sum_^m (-1)^ \binom f_k$For example, the three variable majority function polynomial has coefficients (0, 0, 1, -2):$\text(x, y, z) = (xy + xz + yz) -2(xyz)$

Examples

See also

* Symmetric function

References

{{reflist
Boolean algebra
Cryptography