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. For this reason they are also known as Boolean counting functions.

There are 2n+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.

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 kmodm 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

when applied to an input vector of weight.

Weight

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

Algebraic normal form

The algebraic normal form, or none of them; i.e. the Möbius transform of the function is also a symmetric function. It can thus also be described by a simple (n+1) bit vector, the ANF vector 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:

So the three variable majority function

Unit hypercube polynomial

For example, the three variable majority function

Examples

See also

• Symmetric function

References