Symmetric Boolean function
# 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. 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:\{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:

* 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:\{0,1\}^{n}\rightarrow \{0,1\}$ when applied to an input vector of weight $k$.

### Weight

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

$|f|=\sum _{k=0}^{n}{\binom {n}{k}}f_{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 _{k_{2}\subseteq m_{2}}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{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.:

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

### Unit hypercube polynomial

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

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

For example, the three variable majority function polynomial has coefficients (0, 0, 1, -2):

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

## Examples

The 16 symmetric Boolean functions of three variables :

| Function value | Function value | Function value | Function value | Value vector | Weight | Name | Colloquial description | ANF vector |
| - | - | - | - | - | - | - | - | - |
| 0 | 1 | 2 | 3 | Value vector | Weight | Name | Colloquial description | ANF vector |
| F | F | F | F | (0, 0, 0, 0) | 0 | Constant false | "never" | (0, 0, 0, 0) |
| F | F | F | T | (0, 0, 0, 1) | 1 | Three-way AND, Threshold(3), Count(3) | "all three" | (0, 0, 0, 1) |
| F | F | T | F | (0, 0, 1, 0) | 3 | Count(2), One-cold | "exactly two" | (0, 0, 1, 1) |
| F | F | T | T | (0, 0, 1, 1) | 4 | Majority, Threshold(2) | "most", "at least two" | (0, 0, 1, 0) |
| F | T | F | F | (0, 1, 0, 0) | 3 | Count(1), One-hot | "exactly one" | (0, 1, 0, 1) |
| F | T | F | T | (0, 1, 0, 1) | 4 | Three-way XOR, (odd) parity | "one or three" | (0, 1, 0, 0) |
| F | T | T | F | (0, 1, 1, 0) | 6 | Not-all-equal | "one or two" | (0, 1, 1, 0) |
| F | T | T | T | (0, 1, 1, 1) | 7 | Three-way OR, Threshold(1) | "any", "at least one" | (0, 1, 1, 1) |
| T | F | F | F | (1, 0, 0, 0) | 1 | Three-way NOR, Count(0) | "none" | (1, 1, 1, 1) |
| T | F | F | T | (1, 0, 0, 1) | 2 | All-equal | "all or none" | (1, 1, 1, 0) |
| T | F | T | F | (1, 0, 1, 0) | 4 | Three-way XNOR, even parity | "none or two" | (1, 1, 0, 0) |
| T | F | T | T | (1, 0, 1, 1) | 5 | | "not exactly one" | (1, 1, 0, 1) |
| T | T | F | F | (1, 1, 0, 0) | 4 | (Horn clause) | "at most one" | (1, 0, 1, 0) |
| T | T | F | T | (1, 1, 0, 1) | 5 | | "not exactly two" | (1, 0, 1, 1) |
| T | T | T | F | (1, 1, 1, 0) | 7 | Three-way NAND | "at most two" | (1, 0, 0, 1) |
| T | T | T | T | (1, 1, 1, 1) | 8 | Constant true | "always" | (1, 0, 0, 0) |
