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.[1] For this reason they are also known as Boolean counting functions.[2]
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 elements to two elements, .
Symmetric Boolean functions are used to classify Boolean satisfiability problems.
In the following, denotes the value of the function when applied to an input vector of weight .
Weight
The weight of the function can be calculated from its value vector:
The algebraic normal form either contains all monomials of certain order , 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 . The ANF and value vectors are related by a Möbius relation:
where denotes all the weights k whose base-2 representation is covered by the base-2 representation of m (a consequence of Lucas’ theorem).[3] 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 with value vector (0, 0, 1, 1) has ANF vector (0, 0, 1, 0), i.e.:
Unit hypercube polynomial
The coefficients of the real polynomial agreeing with the function on are given by:
For example, the three variable majority function polynomial has coefficients (0, 0, 1, -2):