Demostrar que las conectivas monotónicas y las conectivas autodobles no son funcionalmente completas.

Question

Un conjunto de conectivas lógicas es funcionalmente completo si y sólo si no es un subconjunto de ninguno de estos conjuntos de conectivas:

Las conectivas monotónicas, Las conectivas afines, Las conectivas autoduales, Las conectivas que preservan la verdad, Las conectivas que preservan la falsedad.

¿Cómo demuestro que las conectivas monotónicas no son funcionalmente completas? ¿Cómo demuestro que las conectivas autoduales no son funcionalmente completas?

Demostrar que las conectivas de preservación de la verdad y de preservación de la falsedad no son funcionalmente completas es fácil. Para demostrar que las conectivas afines no son funcionalmente completas se puede demostrar que la tabla de verdad siempre tendrá un número par de valores verdaderos bajo cualquier valoración.

Answer 1

En cada caso, como la clase de funciones booleanas monótonas (resp. autoduales) es cerrado bajo composición .

Esto significa que cada fórmula que construyas a partir de estas conectivas expresará una función monótona (o autodual) de las variables libres.

Puesto que hay existe funciones de verdad que no son monótonas (por ejemplo, la negación) o autoduales (por ejemplo, la conjunción) esto demuestra que no todo se puede construir a partir de su clase.

---

(Este enfoque funciona igualmente para funciones afines o que preservan la verdad o la falsedad).