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: It's a shame we can't just set up "test civilizations" somewhere and see how well each thing works.
gollark: I mean. Maybe it could work in small groups. But small tribe-type setups scale poorly.
gollark: 1. Is that seriously how you read what I was saying? I was saying: fix our minds' weird ingroup/outgroup division.2. That is very vague and does not sound like it could actually work.
gollark: I'm pretty sure we *have* done the ingroup/outgroup thing for... forever. And... probably the solutions are something like transhumanist mind editing, or some bizarre exotic social thing I can't figure out yet.
gollark: I mean that humans are bad in that we randomly divide ourselves into groups then fiercely define ourselves by them, exhibit a crazy amount of exciting different types of flawed reasoning for no good reason, get caught up in complex social signalling games, come up with conclusions then rationalize our way to a vaguely sensible-looking justification, sometimes seemingly refuse to be capable of abstract thought when it's politically convenient, that sort of thing.

References
  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

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.