Me has recordado a cuando había que demostrar el homomorfismo, específicamente que \( h(u\lor v)=h(u)\cup h(v) \) y \( h(\overline{u})=\overline{h(u)} \) se deducen las otras 3 propiedades (se preserva el ínfimo y los primer y último elementos).
¿Eso es así porque el conjunto \( \{\lor,\overline{\vphantom{a}}\} \) es funcionalmente completo? Llamamos a un conjunto de tipos de compuertas lógicas (AND, NOT etc.) funcionalmente completo si con dicho conjunto se pueden representar cualquier función booleana.
Sí, exacto.
Esto es así pues para definir a \( \land \) basta con decir \( a\land b=\overline{\overline{a}\lor\overline{b}} \), para \( 1 \) se escribe \( 1=\overline{a}\lor a \) y \( 0=\overline{a}\land a=\overline{a\lor\overline{a}} \), ¿está bien?
Sí, está perfecto.
Pero también es cierto que el conjunto \( \{\mathrm{NAND}\} \) (Not-AND) es funcionalmente completo. ¿Por qué Carlos entonces usa un conjunto funcionalmente completo de 2 elementos y no de 1 solo? ¿Y por qué no eligió un conjunto de 3 elementos?
Sí, lo podrías hacer con una sola operación usando el NAND. Si no se suele hacer así es por varios motivos.
Uno es que el NAND tiene una interpretación bastante menos natural que las tres habituales, lo que hace más difícil pensar en términos de NAND que en términos de \( \vee,\wedge \) y complementos. Por ejemplo, si \( A,B \) son conjuntos de un álgebra, la unión, intersección y complementos son operaciones muy naturales, que se usan continuamente. En cambio el NAND corresponde a \( \overline{A \cap B} \), que es menos natural y no se usa tanto.
Otro motivo es que a la hora de definir álgebra de Boole es conveniente usar la definición con \( \wedge,\vee \) y complementos, porque así puedes ver directamente un álgebra de Boole como un caso particular de retículo, y usar toda la teoría que sabes sobre retículos directamente.
Sobre por qué Carlos usa dos operaciones en lugar de una o tres habría que preguntárselo a él. Pero mi conjetura es que usa dos porque en las definición usual de álgebra de conjuntos, la que se suele encontrar en prácticamente cualquier libro de teoría de la medida, se define álgebra de conjuntos en \( X \) como un subconjunto de \( P(X) \) que cumple que \( X \) está en el algebra y que es cerrada bajo complementos y uniones. Es una cuestión de convenio, pero así te ahorras tratar explícitamente una operación (la intersección en este caso) y por otro lado trabajas con dos operaciones "naturales" (complemento y unión) en vez de con una operación menos natural (NAND).
Pero vamos, que es cuestión de gustos. Lo puedes hacer como quieras, tanto con tres, como con dos, como con una operación y nadie te podrá decir que esté mal.
Puedes corregirme lo anterior, creo que la siguiente nota simplifica los cálculos:
NOTA Para poder representar cualquier función booleana es necesario y suficiente que se puedan representar las dos operaciones binarias (supremo e ínfimo) y la unaria (complemento).
Con esto nos quitamos de encima las pruebas de \( h(1)=1 \) y \( h(0)=0 \), ¿verdad? ¿Y cómo se demostraría esa nota/propiedad? Dice que es condición necesaria y suficiente, o sea una doble implicación...
Sí. Es lo mismo de antes. Si partes de un conjunto primitivo de operaciones y eres capaz de representar \( \vee, \wedge \) y complementos eres capaz de representar cualquier función Booleana (porque éstas son por definición las que puedes obtener usando esas tres operaciones). Y al revés, si puedes representar cualquier función Booleana a partir de un conjunto de operaciones, puedes representar \( \vee,\wedge \) y complementos (porque \( (p,q) \mapsto p \vee q \) es una función Booleana y lo mismo con las otras).