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 role in theoretical investigation of circuit complexity of Boolean functions.

The output of the parity function is the parity bit.

Definition

-variable parity function is the Boolean function if and only if is defined as follows:

denotes exclusive or.

Properties

Parity only depends on the number of ones and is therefore a symmetric Boolean function.

The n-variable parity function and its negation are the only Boolean functions for which all disjunctive normal forms have the maximal number of 2n1 monomials of length n and all conjunctive normal forms have the maximal number of 2n1 clauses of length n.

Computational complexity

Some of the earliest work in computational complexity was 1961 bound of Bella Subbotovskaya showing the size of a Boolean formula by Paterson and Zwick by Håstad (1998).

In the early 1980s, Merrick Furst, James Saxe and Michael Sipser and independently Miklós Ajtai established super-polynomial lower bounds on the size of constant-depth Boolean circuits for the parity function, i.e., they showed that polynomial-size constant-depth circuits cannot compute the parity function. Similar results were also established for the majority, multiplication and transitive closure functions, by reduction from the parity function.

established tight exponential lower bounds on the size of constant-depth Boolean circuits for the parity function. Håstad's Switching Lemma is the key technical tool used for these lower bounds and Johan Håstad was awarded the Gödel Prize for this work in 1994. The precise result is that depth- to compute the parity function. This is asymptotically almost optimal as there are depth-.

Infinite version

differ on an even number of coordinates.

Assuming axiom of choice. It is enough to take one representative per equivalence class values are deducted unambiguously.

Another construction of an infinite parity function can be done using a non-principal ultrafilter is an element of the ultrafilter.

as a subset of the Cantor space is a non-measurable set and does not have the property of Baire. Without the axiom of choice, it is consistent (relative to ZF) that all subsets of the Cantor space are measurable and have the property of Baire and thus that no infinite parity function exists; this holds in the Solovay model, for instance.

See also

• Walsh function, a continuous equivalent

• Parity bit, the output of the function

• Piling-up lemma, a statistical property for independent inputs

• Multiway switching, a physical implementation often used to control lighting

Related topics:

• Error Correction

• Error Detection

References