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.[1] For this reason they are also known as Boolean counting functions.[2] 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, [math]\displaystyle{ f: \{0, 1, ..., n\} \rightarrow \{0, 1\} }[/math].
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, [math]\displaystyle{ f_k }[/math] denotes the value of the function [math]\displaystyle{ f: \{0, 1\}^n \rightarrow \{0, 1\} }[/math] when applied to an input vector of weight [math]\displaystyle{ k }[/math].
Weight
The weight of the function can be calculated from its value vector:
[math]\displaystyle{ |f| = \sum_{k=0}^n \binom{n}{k}f_k }[/math]
Algebraic normal form
The algebraic normal form either contains all monomials of certain order [math]\displaystyle{ m }[/math], or none of them; i.e. the Möbius transform [math]\displaystyle{ \hat f }[/math] of the function is also a symmetric function. It can thus also be described by a simple (n+1) bit vector, the ANF vector [math]\displaystyle{ \hat f_m }[/math]. The ANF and value vectors are related by a Möbius relation:[math]\displaystyle{ \hat f_m = \bigoplus_{k_2 \subseteq m_2} f_k }[/math]where [math]\displaystyle{ k_2 \subseteq m_2 }[/math] denotes all the weights k whose base-2 representation is covered by the base-2 representation of m (a consequence of Lucas’ theorem).[3] 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:
[math]\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} }[/math]
So the three variable majority function with value vector (0, 0, 1, 1) has ANF vector (0, 0, 1, 0), i.e.:[math]\displaystyle{ \text{Maj}(x, y, z) = xy \oplus xz \oplus yz }[/math]
Unit hypercube polynomial
The coefficients of the real polynomial agreeing with the function on [math]\displaystyle{ \{0, 1\}^n }[/math] are given by:[math]\displaystyle{ f^*_m = \sum_{k = 0}^m (-1)^{|k|+|m|} \binom{m}{k} f_k }[/math]For example, the three variable majority function polynomial has coefficients (0, 0, 1, -2):[math]\displaystyle{ \text{Maj}(x, y, z) = (xy + xz + yz) -2(xyz) }[/math]
Examples
| Function value | Value vector | Weight | Name | Colloquial description | ANF vector | |||
|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | |||||
| 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) |
See also
References
- ↑ 1.0 1.1 Ingo Wegener, "The Complexity of Symmetric Boolean Functions", in: Computation Theory and Logic, Lecture Notes in Computer Science, vol. 270, 1987, pp. 433–442
- ↑ "BooleanCountingFunction—Wolfram Language Documentation". https://reference.wolfram.com/language/ref/BooleanCountingFunction.html.en.
- ↑ Canteaut, A.; Videau, M. (2005). "Symmetric Boolean functions". IEEE Transactions on Information Theory 51 (8): 2791–2811. doi:10.1109/TIT.2005.851743. ISSN 1557-9654. https://hal.inria.fr/inria-00001148/document.
 |  |
