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.

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. |f| = \sum_{k=0}^n \binom{n}{k}f_k 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 The coefficients of the real polynomial agreeing with the function on \{0, 1\}^n are given by: f^*_m = \sum_{k = 0}^m (-1)^ \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) ==References==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1345538600 under CC BY-SA 4.0; modifications have been made.