Jump to content

Symmetric Boolean function

From Wikipedia, the free encyclopedia

In mathematics, a symmetric Boolean function is a Boolean function whose value does not depend on the order of its input bits, i.e., it depends only on the number of ones (or zeros) in the input.[1] For this reason they are also known as Boolean counting functions.[2]

There are 2n+1 symmetric n-ary Boolean functions. 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. Mathematically, the symmetric Boolean functions correspond one-to-one with the functions that map n+1 elements to two elements, .

Symmetric Boolean functions are used to classify Boolean satisfiability problems.

Special cases

[edit]

A number of special cases are recognized:[1]

  • Majority function: their value is 1 on input vectors with more than n/2 ones
  • Threshold functions: their value is 1 on input vectors with k or more ones for a fixed k
  • All-equal and not-all-equal function: their values is 1 when the inputs do (not) all have the same value
  • Exact-count functions: their value is 1 on input vectors with k ones for a fixed k
    • One-hot or 1-in-n function: their value is 1 on input vectors with exactly one one
    • One-cold function: their value is 1 on input vectors with exactly one zero
  • Congruence functions: their value is 1 on input vectors with the number of ones congruent to k mod m for fixed km
  • Parity function: their value is 1 if the input vector has odd number of ones

The n-ary versions of AND, OR, XOR, NAND, NOR and XNOR are also symmetric Boolean functions.

Properties

[edit]

In the following, denotes the value of the function when applied to an input vector of weight .

Weight

[edit]

The weight of the function can be calculated from its value vector:

Algebraic normal form

[edit]

The algebraic normal form either contains all monomials of certain order , or none of them; i.e. the Möbius transform of the function is also a symmetric function. It can thus also be described by a simple (n+1) bit vector, the ANF vector . The ANF and value vectors are related by a Möbius relation:where denotes all the weights k whose base-2 representation is covered by the base-2 representation of m (a consequence of Lucas’ theorem).[3] Effectively, an n-variable symmetric Boolean function corresponds to a log(n)-variable ordinary Boolean function acting on the base-2 representation of the input weight.

For example, for three-variable functions:

So the three variable majority function with value vector (0, 0, 1, 1) has ANF vector (0, 0, 1, 0), i.e.:

Unit hypercube polynomial

[edit]

The coefficients of the real polynomial agreeing with the function on are given by:For example, the three variable majority function polynomial has coefficients (0, 0, 1, -2):

Examples

[edit]
The 16 symmetric Boolean functions of three variables
Function value Value vector Weight Name Colloquial description ANF vector
0 1 2 3
F F F F (0, 0, 0, 0) 0 Constant false "never" (0, 0, 0, 0)
F F F T (0, 0, 0, 1) 1 Three-way AND, Threshold(3), Count(3) "all three" (0, 0, 0, 1)
F F T F (0, 0, 1, 0) 3 Count(2), One-cold "exactly two" (0, 0, 1, 1)
F F T T (0, 0, 1, 1) 4 Majority, Threshold(2) "most", "at least two" (0, 0, 1, 0)
F T F F (0, 1, 0, 0) 3 Count(1), One-hot "exactly one" (0, 1, 0, 1)
F T F T (0, 1, 0, 1) 4 Three-way XOR, (odd) parity "one or three" (0, 1, 0, 0)
F T T F (0, 1, 1, 0) 6 Not-all-equal "one or two" (0, 1, 1, 0)
F T T T (0, 1, 1, 1) 7 Three-way OR, Threshold(1) "any", "at least one" (0, 1, 1, 1)
T F F F (1, 0, 0, 0) 1 Three-way NOR, Count(0) "none" (1, 1, 1, 1)
T F F T (1, 0, 0, 1) 2 All-equal "all or none" (1, 1, 1, 0)
T F T F (1, 0, 1, 0) 4 Three-way XNOR, even parity "none or two" (1, 1, 0, 0)
T F T T (1, 0, 1, 1) 5 "not exactly one" (1, 1, 0, 1)
T T F F (1, 1, 0, 0) 4 (Horn clause) "at most one" (1, 0, 1, 0)
T T F T (1, 1, 0, 1) 5 "not exactly two" (1, 0, 1, 1)
T T T F (1, 1, 1, 0) 7 Three-way NAND "at most two" (1, 0, 0, 1)
T T T T (1, 1, 1, 1) 8 Constant true "always" (1, 0, 0, 0)

See also

[edit]

References

[edit]
  1. ^ a b Ingo Wegener, "The Complexity of Symmetric Boolean Functions", in: Computation Theory and Logic, Lecture Notes in Computer Science, vol. 270, 1987, pp. 433–442
  2. ^ "BooleanCountingFunction—Wolfram Language Documentation". reference.wolfram.com. Retrieved 2021-05-25.
  3. ^ Canteaut, A.; Videau, M. (2005). "Symmetric Boolean functions". IEEE Transactions on Information Theory. 51 (8): 2791–2811. doi:10.1109/TIT.2005.851743. ISSN 1557-9654.