¿Es posible derivar todas las demás funciones booleanas tomando otras primitivas diferentes de $NAND$ ?

Question

Estaba leyendo el libro de TECS (Los elementos de los sistemas informáticos) En el libro, empezamos a construir las otras puertas lógicas con una sola puerta lógica primitiva, la $NAND$ puerta. Con él, podríamos hacer fácilmente el $NOT$ puerta, entonces el $AND$ puerta y luego la $OR$ puerta.

Con la $NOT$ , $AND$ y $OR$ podríamos expresar cualquier tabla de verdad a través de representación canónica .

El libro tiene la tabla dada a continuación, me preguntaba si podríamos hacer lo mismo tomando cualquier otra función booleana como primitiva, estoy bastante seguro de que no es posible hacerlo con ambas constantes $0$ ni constante $1$ . ¿Y los demás?

Answer 1

Como has señalado, es imposible que las constantes generen todas las funciones booleanas; las puertas que son funciones de una sola entrada tampoco pueden hacerlo, por razones igualmente obvias (es imposible generar la función booleana $f(x,y)=y$ de cualquiera de los dos $f_1(x,y)=x$ o $f_2(x,y)=\bar{x}$ ).

OR y AND tampoco pueden hacerlo, por una razón algo más complicada: ¡es imposible generar nada a partir de algo! (Más concretamente, ninguno de los dos puede representar la negación, y en particular ninguno puede representar una función constante - esto es porque cualquier función compuesta sólo por ORs y ANDs siempre devolverá 0 cuando sus entradas sean todas-0s y devolverá 1 cuando sus entradas sean todas-1s.

XOR es un poco más complicado: obviamente es posible generar 0 y 1 a través de XOR, y por lo tanto NOT; pero la naturaleza de "preservación de la paridad" de XOR hace que sea imposible representar $x\wedge y$ sólo con XOR.

De hecho, se puede demostrar que NOR y NAND son las únicas funciones booleanas de dos entradas que se bastan a sí mismas; para más detalles, eche un vistazo a la página de Wikipedia sobre integridad funcional .

Answer 2

Su pregunta se refería a la arbitrariedad ( $n$ -ary) las funciones booleanas, sin embargo, usted parece haber restringido su búsqueda a $0$ -Ayuda, $1$ -ary y $2$ -funciones secundarias. Una colección $C$ de funciones booleanas que pueden generar todas las demás por composición se llama funcionalmente completa y cuando $C$ es un singleton $\{f\}$ llamamos a tales $f$ a Función Sheffer . Ahora, una caracterización completa de las colecciones funcionalmente completas de funciones booleanas fue dada en " Los sistemas iterativos de dos valores de la lógica matemática "(Puesto 1941). Sin embargo, como este libro es apenas legible, recomiendo de corazón la explicación del teorema principal en " Teorema de integridad funcional de Post " en su lugar. En "Composition and clones of Boolean functions", de Pöschel y Rosenberg (primer capítulo de Modelos y métodos booleanos en matemáticas, informática e ingeniería ), el número exacto de $n$ -ary las funciones de Sheffer está determinada: $2^{2^n - 2} - 2^{2^{n - 1} - 1}$ . Por lo tanto, si va más allá de la $2$ funciones binarias NAND y NOR debería encontrar $56$ funciones ternarias funcionalmente completas, $16\,256$ funciones cuaternarias funcionalmente completas, etc.