In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, 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.

The definition implies that instead of the truth table

Truth table

A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—to compute the functional values of logical expressions on each of their functional arguments, that is, on each combination of values taken by their...

, 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.

• 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 function
  Parity function
  In Boolean algebra, a parity function is a Boolean function whose value is 1 if the input vector has an odd number of ones.The parity function is notable for its role in theoretical investigation of circuit complexity of Boolean functions.-Definition:...
  
  s: their value is 1 if the input vector has odd number of ones.