Symmetric Boolean function

In mathematics, a symmetric Boolean function is a Boolean function whose value does not depend on the permutation of its input bits, i.e., it depends only on the number of ones in the input.[1]

From the definition follows, that there are 2n+1 symmetric n-ary Boolean functions. It implies that 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.

Special cases

A number of special cases are recognized.[1]

References

  1. 1 2 Ingo Wegener, "The Complexity of Symmetric Boolean Functions", in: Computation Theory and Logic, Lecture Notes in Computer Science, vol. 270, 1987, pp. 433–442

See also

This article is issued from Wikipedia - version of the 10/3/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.