In
mathematics, a symmetric Boolean function is a
Boolean function
In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth 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.
Ingo Wegener
Ingo Wegener (December 4, 1950 in Bremen – November 26, 2008 in Bielefeld) was an influential German computer scientist working in the field of theoretical computer science.
Education and career
Wegener was educated at the Bielefeld University. ...
, "The Complexity of Symmetric Boolean Functions", in: ''Computation Theory and Logic'', ''Lecture Notes in Computer Science
''Lecture Notes in Computer Science'' is a series of computer science books published by Springer Science+Business Media since 1973.
Overview
The series contains proceedings, post-proceedings, monographs, and Festschrifts. In addition, tutorial ...
'', vol. 270, 1987, pp. 433–442 For this reason they are also known as Boolean counting functions.
There are 2
''n''+1 symmetric ''n''-ary Boolean functions. Instead of the
truth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional argumen ...
, 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
A number of special cases are recognized:
[
*]Majority function In Boolean logic, the majority function (also called the median operator) is the Boolean function that evaluates to false when half or more arguments are false and true otherwise, i.e. the value of the function equals the value of the majority of t ...
: 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
In digital circuits and machine learning, a one-hot is a group of bits among which the legal combinations of values are only those with a single high (1) bit and all the others low (0). A similar implementation in which all bits are '1' except ...
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 ''k'', ''m''
*Parity function In Boolean algebra, a parity function is a Boolean function whose value is one if and only if the input vector has an odd number of ones. The parity function of two inputs is also known as the XOR function.
The parity function is notable for its r ...
: their value is 1 if the input vector has odd number of ones
The n-ary versions of AND
or AND may refer to:
Logic, grammar, and computing
* Conjunction (grammar), connecting two words, phrases, or clauses
* Logical conjunction in mathematical logic, notated as "∧", "⋅", "&", or simple juxtaposition
* Bitwise AND, a boolea ...
, OR, XOR, NAND, NOR and XNOR
The XNOR gate (sometimes XORN'T, ENOR, EXNOR or NXOR and pronounced as Exclusive NOR. Alternatively XAND, pronounced Exclusive AND) is a digital logic gate whose function is the logical complement of the Exclusive OR ( XOR) gate. It is equival ...
are also symmetric Boolean functions.
Properties
In the following, denotes the value of the function when applied to an input vector of weight
In science and engineering, the weight of an object is the force acting on the object due to gravity.
Some standard textbooks define weight as a vector quantity, the gravitational force acting on the object. Others define weight as a scalar qua ...
.
Weight
The weight of the function can be calculated from its value vector:
Algebraic normal form
The algebraic normal form
In Boolean algebra, the algebraic normal form (ANF), ring sum normal form (RSNF or RNF), '' Zhegalkin normal form'', or '' Reed–Muller expansion'' is a way of writing logical formulas in one of three subforms:
* The entire formula is purely tr ...
either contains all monomials of certain order , or none of them; i.e. the Möbius transform
Moebius, Möbius or Mobius may refer to:
People
* August Ferdinand Möbius (1790–1868), German mathematician and astronomer
* Theodor Möbius (1821–1890), German philologist
* Karl Möbius (1825–1908), German zoologist and ecologist
* Pau ...
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). Effectively, an n-variable symmetric Boolean function corresponds to a log(n)-variable ordinary Boolean function
In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth function ...
acting on the base-2 representation of the input weight.
For example, for three-variable functions:
So the three variable majority function In Boolean logic, the majority function (also called the median operator) is the Boolean function that evaluates to false when half or more arguments are false and true otherwise, i.e. the value of the function equals the value of the majority of t ...
with value vector (0, 0, 1, 1) has ANF vector (0, 0, 1, 0), i.e.:
Unit hypercube polynomial
The coefficients of the real polynomial agreeing with the function on are given by:For example, the three variable majority function In Boolean logic, the majority function (also called the median operator) is the Boolean function that evaluates to false when half or more arguments are false and true otherwise, i.e. the value of the function equals the value of the majority of t ...
polynomial has coefficients (0, 0, 1, -2):
Examples
See also
* Symmetric function
In mathematics, a function of n variables is symmetric if its value is the same no matter the order of its arguments. For example, a function f\left(x_1,x_2\right) of two arguments is a symmetric function if and only if f\left(x_1,x_2\right) = f ...
References
{{reflist
Boolean algebra
Cryptography