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, .
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.
Examples
| Input weight | Name | Colloquial description | |||
|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | ||
| F | F | F | F | Constant false | "never" |
| F | F | F | T | Three-way AND, Threshold(3), Count(3) | "all three" |
| F | F | T | F | Count(2), One-cold | "exactly two" |
| F | F | T | T | Majority, Threshold(2) | "most", "at least two" |
| F | T | F | F | Count(1), One-hot | "exactly one" |
| F | T | F | T | Three-way XOR, (odd) parity | "one or three" |
| F | T | T | F | Not-all-equal | "one or two" |
| F | T | T | T | Three-way OR, Threshold(1) | "any", "at least one" |
| T | F | F | F | Three-way NOR, Count(0) | "none" |
| T | F | F | T | All-equal | "all or none" |
| T | F | T | F | Three-way XNOR, even parity | "none or two" |
| T | F | T | T | "not exactly one" | |
| T | T | F | F | (Horn clause) | "at most one" |
| T | T | F | T | "not exactly two" | |
| T | T | T | F | Three-way NAND | "at most two" |
| T | T | T | T | Constant true | "always" |
See also
References
- ^ a b 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". reference.wolfram.com. Retrieved 2021-05-25.