Symmetric Boolean function

In <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, a symmetric Boolean function is a <a href="/facts/Boolean_function/uT7E8pqC">Boolean function</a> whose value does not depend on the <a href="/facts/Permutation/JSw9ukmv">order</a> 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 <a href="/facts/Truth_table/4KsmArDW">truth table</a>, 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
 }
 →
 {
 0
 ,
 1
 }
 
 
 {\displaystyle f:\{0,1,...,n\}\rightarrow \{0,1\}}
 
.
Symmetric Boolean functions are used to classify <a href="/facts/Boolean_satisfiability_problem/wBVRjWoy">Boolean satisfiability problems</a>.

Symmetric Boolean function open-in-new

Symmetric Boolean function