Symmetric Boolean function explained

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 2ⁿ⁺¹ 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,

f: \{ 0 , 1 , ..., n\} → \{ 0 , 1 \} .

Symmetric Boolean functions are used to classify Boolean satisfiability problems.

Special cases

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 k, m
• Parity function

their value is 1 if the input vector has odd number of onesThe n-ary versions of AND, OR, XOR, NAND, NOR and XNOR are also symmetric Boolean functions.

Properties

In the following,

f _{k} denotes the value of the function f: \{ 0 , 1 \} ^{n} → \{ 0 , 1 \} when applied to an input vector of weight k .

Weight

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

$$|f|\; =\; \backslash sum\_^n\; \backslash binomf\_k$$

Algebraic normal form

The algebraic normal form either contains all monomials of certain order

m , or none of them; i.e. the Möbius transform \hat f of the function is also a symmetric function. It can thus also be described by a simple (n+1) bit vector, the ANF vector \hat f _{m} . The ANF and value vectors are related by a Möbius relation:$$\backslash hat\; f\_m\; =\; \backslash bigoplus\_\; f\_k$$where k _{2} \subseteq m _{2} 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.:$$\backslash text(x,\; y,\; z)\; =\; xy\; \backslash oplus\; xz\; \backslash oplus\; yz$$

Unit hypercube polynomial

The coefficients of the real polynomial agreeing with the function on

\{ 0 , 1 \} ^{n} are given by:$$f^*\_m\; =\; \backslash sum\_^m\; (-1)^$$

m

\binom f_kFor example, the three variable majority function polynomial has coefficients (0, 0, 1, -2):$$\backslash text(x,\; y,\; z)\; =\; (xy\; +\; xz\; +\; yz)\; -2(xyz)$$

Examples

Function value! rowspan="2"

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

• Symmetric function

Notes and References

1. [Ingo Wegener]
2. Web site: BooleanCountingFunction—Wolfram Language Documentation. 2021-05-25. reference.wolfram.com.
3. Canteaut. A.. Videau. M.. 2005. Symmetric Boolean functions. IEEE Transactions on Information Theory. 51. 8. 2791–2811. 10.1109/TIT.2005.851743. 1557-9654.