- 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 par 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.
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.[2]
Referencias
- ↑ Weisstein, Eric W. «Parity» (en inglés). MathWorld. Wolfram Research.
- ↑ Ingo Wegener, Randall J. Pruim, Complexity Theory, 2005, ISBN 3540210458, p. 260
Categorías:- Álgebra de Boole
- Funciones discretas
Wikimedia foundation. 2010.