¿Cuál es el número mínimo de conjuntos de operadores funcionalmente completos que contienen XOR?
Dado que AND, OR y NOT son un conjunto funcionalmente completo, tengo que encontrar un conjunto de operadores que puedan construir estos tres operadores.
He completado el ejercicio de esta manera: Set = {XOR, AND}
¿Mi solución es correcta? ¿Alguien puede dimostrar por qué este es el conjunto de operadores funcionalmente completo más pequeño o por qué no lo es (y publicar la solución)?
XOR debe estar incluido (esto está dado). Se puede mostrar que XOR y AND están completos. (OP ha hecho esto) XOR y AND son solo dos elementos (por inspección). Para ser más mínimo, tendrías que eliminar AND. La única forma de eliminar Y mantener la integridad es implementar Y utilizando solo XOR.
Por lo tanto, indicar AND no se puede implementar utilizando solo XOR es exactamente equivalente a decir que {AND, XOR} es el conjunto mínimo que contiene XOR. Puede que no sea el ÚNICO conjunto mínimo, pero es un conjunto mínimo.
Para generar una prueba rigurosa, vea el trabajo de Emil Post. Aparentemente descubrió las propiedades necesarias para la integridad. Entonces, si puedes usar su teorema, puedes demostrar que XOR no está completo por sí mismo usando su trabajo.
Lea otras preguntas en las etiquetas boolean-algebra