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 elements to two elements,. Symmetric Boolean functions are used to classify Boolean satisfiability problems.

Special cases

A number of special cases are recognized: 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 when applied to an input vector of weight k.

Weight

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

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:where 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 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 {0, 1}^n are given by:For example, the three variable majority function polynomial has coefficients (0, 0, 1, -2):

Examples