Conjuntos de conectivos funcionalmente completos

Question

¿Por qué el conjunto de conectivos {¬,#} no es completo? si # es el conectivo Mayoría el cual se puede definir como:

#(A,B,C) = (A^B)v(A^C)v(B^C), en todo caso cualquier fórmula que se escriba solo con {¬,#} tendrá una equivalente que se escriba solo con {¬,^,v} conjunto que si es completo.

 

por otra parte, ¿cómo se demuetra que {^, ⇔,+} es completo?

 

De antemano, gracias!!

Answer 1

Para ver que {¬,#} no es completo, probaremos que cualquier fórmula construída con dos variables A y B, usando los conectivos ¬ y #, es equivalente a una de las siguientes cuatro fórmulas: A, ¬A, B, ¬B. O sea que con {¬, #} no podemos construir ninguna función de dos variables que realmente dependa de las dos, no podemos construir ^ o v, por ejemplo.

Para probar eso, basta ver que las cuatro funciones de dos variables {A, ¬A, B, ¬B} son cerradas bajo ¬ y #. Esto es claro para ¬. Para # notemos consideremos cualquier expresión #(X,Y,Z) donde X, Y y Z están en {A, ¬A, B, ¬B}. Al menos dos de los tres argumentos X, Y y Z, deben involcurar a la misma variable A o B. Como # es simétrica, podemos suponer sin pérdida de generalidad que X y Y usando la misma variable. Entonces Y=X o Y=¬X, pero #(X,X,Z) = X y #(X,¬X,Z) = Z.

 

Para probar que {^,⇔,+} es completo (suponiendo que + es "o exclusivo") basta ver que:

• X⇔X es siempre verdadero
• ¬X es entonces equivalente a X + (X⇔X)
• X v Y es equivalente a ¬(¬X ^ ¬Y), y ya expresamos ¬ en términos de {^,⇔,+}.

Entonces {^,⇔,+} puede expresar {¬,^,v} y por lo tanto es universal.

Comments

Gracias! Apenas estoy empezando con esto de lógica matemática. Por cierto, ya que {^,⇔,+}es completo, si solo considero {^,+}, entonces no podría construir fórmulas considerando un símbolo de enunciado puesto que si (A+A)=¬A independientemente de si A es verdadero o falso. Luego si asignamos Falso a A, no se tendría nada tautológicamente equivalente a A verdadero y por tanto {^,+}, no es completo.
No se si mi razonamiento es correcto.

Saludos.

---

Creo que lo que pensaste está bien aunque lo dijiste ligeramente mal: A+A es siempre Falso, no es ¬A.

Como yo diría el argumento es así: el conjunto {Falso, A} de funciones de una sola variable A es cerrado bajo {^, +} y por lo tanto esas son todas las funciones de una variable que puedes expresar con {^, +}.