Integridad funcional en la lógica proposicional
Un conjunto de funciones booleanas que por composición genera todas las funciones booleanas se denomina funcionalmente completo .
Para que un conjunto de funciones booleanas sea funcionalmente completo, debe contener al menos una función para cada una de las cinco clases precompletas de lógica booleana, también conocidas como clases de Post, que no pertenece a esa clase .
La razón: las clases precompletas están cerradas bajo composición. Por lo tanto, si compone funciones pertenecientes a una de ellas, por ejemplo, clase [math] X [/ math], el resultado también estará en [math] X [/ math].
- ¿Qué es más importante en programación, lógica o sintaxis?
- ¿Por qué algunos días se consideran auspiciosos y otros no? ¿Cuál es el punto de vista lógico de esta superstición?
- ¿Cuál es un gran libro para aprender lógica simbólica desde cero?
- ¿Puedes discutir los méritos de la lógica, sin caer en ningún razonamiento circular?
- La demostración de contradicciones performativas en casos particulares sirve para refutar contraargumentos escépticos. ¿Podemos utilizar presuposiciones pragmáticas universales de argumentación para analizar su contenido normativo?
Las cinco clases precompletas son
- funciones monótonas,
- funciones auto-duales,
- funciones afines (lineales),
- funciones de preservación de la verdad,
- funciones de preservación de la falsedad.
Hay exactamente dos generadores mínimos (bases) para la lógica booleana que consisten en una única función binaria: [math] \ {Nand \} [/ math] y [math] \ {Nor \} [/ math]. Ambos conjuntos son funcionalmente completos porque ambas funciones no son monótonas ni auto duales, ni lineales, ni preservadoras de la verdad, ni falsas.
Por lo tanto, determina para cada conectivo en el conjunto, mediante la inspección de la tabla de verdad, las clases precompletas a las que pertenece. Si y solo si para cada una de las cinco clases precompletas encuentra al menos un conectivo que no pertenece a esa clase, su conjunto está funcionalmente completo.
Considere esta tabla:
/main-qimg-c8ed1134c438d22d5fe24e469c8e1028.png)
Muestra la clasificación de las 16 funciones booleanas binarias con respecto a las clases precompletas, más una evaluación de simetría (que no produce una clase precompleta).
Como ejemplo, las tres columnas con un borde en negrita representan los elementos de la base algebraica de la lógica booleana: conjunción (Y), disyunción exclusiva (Xor) y la constante verdadera .
Es una base (un generador mínimo ) porque no puede encontrar un subconjunto que todavía esté funcionalmente completo:
- Si elimina Y le quedan dos funciones que son lineales, por lo tanto, solo puede componer funciones lineales con ellas.
- Si elimina Xor, le quedan dos funciones que son tanto monotónicas como de preservación de la verdad, por lo tanto, solo puede componer funciones que sean monótonas y de preservación de la verdad.
- Si elimina true , le quedan dos funciones que preservan la falsedad, por lo tanto, solo puede componer funciones de preservación de la falsedad.