Symmetric Boolean function

Short description: Boolean function whose output depends only on the number of true inputs

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, f:{0,1,...,n}->{0,1}.

Symmetric Boolean functions are used to classify Boolean satisfiability problems.

## Contents

* 1 Special cases
* 2 Properties
* 2.1 Weight
* 2.2 Algebraic normal form
* 2.3 Unit hypercube polynomial
* 3 Examples
* 4 See also
* 5 References

## 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, fk denotes the value of the function f:{0,1}n->{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|=∑k=0n(nk)fk

### 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 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 f^m. The ANF and value vectors are related by a Möbius relation:f^m=⨁k2⊆m2fkwhere k2⊆m2 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:

f^0=f0f^1=f0⊕f1f^2=f0⊕f2f^3=f0⊕f1⊕f2⊕f3

So the three variable majority function with value vector (0, 0, 1, 1) has ANF vector (0, 0, 1, 0), i.e.:Maj(x,y,z)=xy⊕xz⊕yz

### Unit hypercube polynomial

The coefficients of the real polynomial agreeing with the function on {0,1}n are given by:fm*=∑k=0m(−1)|k|+|m|(mk)fkFor example, the three variable majority function polynomial has coefficients (0, 0, 1, -2):Maj(x,y,z)=(xy+xz+yz)−2(xyz)

## Examples

The 16 symmetric Boolean functions of three variables  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

* Symmetric function

## References

1. ↑ 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
2. ↑ "BooleanCountingFunction—Wolfram Language Documentation". https://reference.wolfram.com/language/ref/BooleanCountingFunction.html.en.
3. ↑ 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.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Symmetric Boolean function. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Symmetric_Boolean_function&oldid=4296473"