Loading AI tools
De Wikipedia, la enciclopedia libre
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 tal que si y solo si el número de unos en el vector es impar. En otras palabras, se define como sigue:
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 |
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]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.