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