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 tal que si y solo si el número de unos en el vector es impar. En otras palabras, se define como sigue: .
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.Ingo Wegener, Randall J. Pruim, Complexity Theory, 2005, ISBN 3540210458, p. 260
Referencias
Categoría:Álgebra de Boole Paridad