title: Función paridad
text: # Función paridad
  
  En el álgebra de Boole, una función paridad es una función booleana cuyo valor es 1 si el vector de entrada tiene un número impar de unos.
  
  La función paridad es una función booleana simétrica, de mucha utilidad en la investigación teórica de complejidad de circuitos.
  
  ## Definición
  
  Una función paridad de n variables es la función booleana $f:\{0,1\}^{n}\to \{0,1\}$ tal que $f(x)=1$ si y solo si el número de unos en el vector $x\in \{0,1\}^{n}$ es impar. En otras palabras, $f$ se define como sigue:
  
      $f(x)=x_{1}\oplus x_{2}\oplus \dots \oplus x_{n}$.
  
  ### Ejemplo
  
  | Entrada | Paridad | Entrada | Paridad |
  | - | - | - | - |
  | 1 | 1 | 1011 | 1 |
  | 10 | 1 | 1100 | 0 |
  | 11 | 0 | 1101 | 1 |
  | 100 | 1 | 1110 | 1 |
  | 101 | 0 | 1111 | 0 |
  | 110 | 0 | 10000 | 1 |
  | 111 | 1 | 10001 | 0 |
  | 1000 | 1 | 10010 | 0 |
  | 1001 | 0 | 10011 | 1 |
  | 1010 | 0 | 10100 | 0 |
  
  ## Propiedades
  
  La función paridad es una función booleana simétrica.
  
  La función de paridad de n variables y su negación son las únicas para las cuales todas sus formas normales disyuntivas tienen el número máximo de $2^{n−1}$ monomios de tamaño n, y todas sus formas normales conjuntivas tienen el número máximo de $2^{n−1}$ cláusulas de tamaño n.
  
  