Lógica: Conjunto funcionalmente completo de conectivos y equivalencia de conectivos

Hola, repasando en el libro y las trasparencias me surgio la siguiente duda :

Cuando se enuncia el teorema de que para cualquier conectivo n-ario aplicado sobre letras proposicionales es posible encontrar una proposicion equivalente que solo tenga los conectivos OR y NOT. La duda es porque se usan solo letras proposicionales? Segun entendi la idea detras de la equivalencia de conectivos es poder expresar cualquier formula de prop dada por un conectivo en base a otro dos , por ejemplo, phi -> psi eq (NOT(phi) OR (psi)). Pero aca phi y psi son formulas cualquiera de prop, no se restringe solo a letras proposicionales como en el caso del teorema para conectivos n-arios.

Entonces, el teorema se puede aplicar en cualquier formula o solo es valido para letras proposicionales? Si se puede aplicar sobre cualquier formula, porque es suficiente probarlo solo para letras proposicionales? La idea de un conjunto completo de conectivos es poder dar cualquier formula de prop solo usando esos conectivos y letras proposicionales (como se hace con los formas normales, pero generalizado a cualquier conjuto funcionalmente completo) ?

Re: Conjunto funcionalmente completo de conectivos y equivalencia de conectivos

de Fernando Carpani - viernes, 24 de abril de 2020, 08:21

Hola.
Un enfoque (creo yo) para terminar de entender el teorema es olvidarnos por un momento (luego volvemos a ella) de la sintaxis y trabajar todo desde la semántica.

Si hacemos eso, nos encontramos que cada conectivo no es más que una función booleana (función de verdad) que recibe ninguno (bottom), uno (not) o más de un valor booleano (el resto).

La pregunta es: Si me dan cualquier función booleana *$*, la puedo escribir en función de las otras? O sea, puedo expresar la función *$* como la composición de otras funciones ya conocidas ?

El conjunto funcionalmente completo es el dado por esas funciones ya conocidas que me permiten representar cualquier otra función.

Observar que en esa visión, no hay lenguaje (en el sentido de chirimbolos... conjunto definido inductivamente que luego tiene una semántica) . Sólo funciones booleanas. Esto hace que sólo nos importen los valores booleanos independientes que podemos pasar en cada parámetro de cada función.

Esto hace que, cuando consideramos el lenguaje, nos baste con considerar el conectivo *$* sólo con letras proposicionales.

Saludos
FDO.