Fandom

DSZQUP XJLJ

Symmetric Boolean function

566pages on
this wiki
Add New Page
Talk0 Share

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]

The definition 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 casesEdit

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 km
  • Parity functions: their value is 1 if the input vector has odd number of ones.

ReferencesEdit

  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
es:Función booleana simétrica

uk:Симетричні функції алгебри логіки

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.