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.

Referencias

• Datos: Q2898309