Conjunto funcionalmente completo de conectivos y equivalencia de conectivos

Re: Conjunto funcionalmente completo de conectivos y equivalencia de conectivos

de Fernando Carpani -
Número de respuestas: 0
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.