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 2ⁿ⁺¹ 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, ${\displaystyle f:\{0,1,...,n\}\rightarrow \{0,1\))$.

Symmetric Boolean functions are used to classify Boolean satisfiability problems.

Special cases

A number of special cases are recognized:^[1]

• 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, ${\displaystyle f_{k))$ denotes the value of the function ${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\))$ when applied to an input vector of weight ${\displaystyle k}$.

Weight

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

$${\displaystyle |f|=\sum _{k=0}^{n}{\binom {n}{k))f_{k))$$

Algebraic normal form

The algebraic normal form either contains all monomials of certain order ${\displaystyle m}$, or none of them; i.e. the Möbius transform ${\displaystyle {\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 ${\displaystyle {\hat {f))_{m))$. The ANF and value vectors are related by a Möbius relation:

$${\displaystyle {\hat {f))_{m}=\bigoplus _{k_{2}\subseteq m_{2))f_{k))$$

${\displaystyle k_{2}\subseteq m_{2))$

For example, for three-variable functions:

$${\displaystyle {\begin{array}{lcl}{\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{array))}$$

So the three variable majority function with value vector (0, 0, 1, 1) has ANF vector (0, 0, 1, 0), i.e.:

$${\displaystyle {\text{Maj))(x,y,z)=xy\oplus xz\oplus yz}$$

Unit hypercube polynomial

The coefficients of the real polynomial agreeing with the function on ${\displaystyle \{0,1\}^{n))$ are given by:

$${\displaystyle f_{m}^{*}=\sum _{k=0}^{m}(-1)^{|k|+|m|}{\binom {m}{k))f_{k))$$

$${\displaystyle {\text{Maj))(x,y,z)=(xy+xz+yz)-2(xyz)}$$

Examples