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]
- Threshold functions: their value is 1 on input vectors with k or more ones for a fixed k
- Exact-value functions: their value is 1 on input vectors with k ones for a fixed k
- Counting functions : their value is 1 on input vectors with the number of ones congruent to k mod m for fixed k, m
- Parity functions: their value is 1 if the input vector has odd number of ones.
gollark: "A wizard did it" is a more plausible explanation for lightning than several hundred pages of theory on meteorology and electromagnetism.
gollark: Humans are generally wired to see agency in things which don't actually have it.
gollark: The problem is that "people using psychedelics feel god-related things" is entirely consistent with "god(s) exist" and "god(s) don't exist, but drugs can push god-related buttons in the brain".
gollark: That makes me less convinced, really.
gollark: What of it? Human brains are very glitchy.
References
- 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. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.