Difference between revisions of "Parity"

From Boolean Zoo
Jump to: navigation, search
m (Added title to definition)
m (Definition)
Line 1: Line 1:
 
== Definition ==
 
== Definition ==
The <math>n</math>-variable '''parity function''' is the Boolean function <math>f:\{-1,1\}^n\to\{-1,1\}</math> such that <math>f(x)=1</math> if and only if the number of ones in the vector <math>x\in\{-1,1\}^n</math> is odd. In other words,
+
The <math>n</math>-variable '''parity function''' is the Boolean function <math>f:\{-1,1\}^n\to\{-1,1\}</math> defined by <math>f(x)=x_1 \cdot x_2 \cdot \ldots \cdot x_n</math>. In other words, <math>f(x)=1</math> if and only if the number of ones in the vector <math>x\in\{-1,1\}^n</math> is odd.
 
 
<math>f(x)=x_1 \cdot x_2 \cdot \ldots \cdot x_n</math>.
 
  
 
==Properties==
 
==Properties==

Revision as of 11:36, 2 September 2018

Definition

The [math]n[/math]-variable parity function is the Boolean function [math]f:\{-1,1\}^n\to\{-1,1\}[/math] defined by [math]f(x)=x_1 \cdot x_2 \cdot \ldots \cdot x_n[/math]. In other words, [math]f(x)=1[/math] if and only if the number of ones in the vector [math]x\in\{-1,1\}^n[/math] is odd.

Properties

  • Parity only depends on the number of ones and is therefore a symmetric Boolean function.
  • Over [math]\{-1,1\}[/math], the representation of the parity function is exactly the monomial [math]x_1 x_2 \ldots x_n[/math]. Thus all of its Fourier mass rests on the highest level.
  • The n-variable parity function and its negation are the only Boolean functions for which all disjunctive normal forms have the maximal number of 2 n − 1 monomials of length n and all conjunctive normal forms have the maximal number of 2 n − 1 clauses of length n. [1]
  • A constant-depth Boolean circuit must have exponential size in order to represent the parity function. [2]


References

  1. Ingo Wegener, Randall J. Pruim, Complexity Theory, 2005, Template:Isbn, p. 260
  2. Johan Håstad, Computational limitations of small depth circuits, 1987.