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.^[1]​

La función paridad es una función booleana simétrica, de mucha utilidad en la investigación teórica de complejidad de circuitos.

Una función paridad de n variables es la función booleana ${\displaystyle f:\{0,1\}^{n}\to \{0,1\}}$ tal que ${\displaystyle f(x)=1}$ si y solo si el número de unos en el vector ${\displaystyle x\in \{0,1\}^{n}}$ es impar. En otras palabras, ${\displaystyle f}$ se define como sigue:

${\displaystyle f(x)=x_{1}\oplus x_{2}\oplus \dots \oplus x_{n}}$.

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.^[2]​