Completitud funcional

Funciones de verdad

La clase sobre la semántica de la lógica proposicional asignó a cada fórmula, en cada valoración, un valor de verdad, y mostró que ese valor depende solo de los valores de las variables que aparecen en ella; de donde toda fórmula con $n$ variables tiene una tabla de verdad de $2^{n}$ filas. La pregunta de esta clase es la inversa. Dada una tabla cualquiera, es decir, una columna de unos y ceros escrita arbitrariamente junto a las $2^{n}$ filas, ¿hay alguna fórmula que la tenga por tabla? Si esto es así para toda tabla, el lenguaje no tiene lagunas expresivas: todo lo que puede decirse sobre el valor de verdad de $n$ enunciados, en función de los valores de estos, se dice con una fórmula. Y como en este curso la única fórmula compuesta es la negación conjunta, la respuesta dirá también si un solo conector basta para decirlo todo.

Lo que se usa de las clases anteriores

Una valoración es una función $v$ del conjunto de las variables $\{v_1, v_2, \ldots\}$ en $\{0, 1\}$, donde $1$ es lo verdadero y $0$ lo falso; su extensión a todas las fórmulas, que también se escribe $v$, está definida por recursión: $v((\varphi \downarrow \psi)) = 1$ si y solo si $v(\varphi) = 0$ y $v(\psi) = 0$. De las abreviaturas oficiales, la misma clase calculó, en el teorema de los valores de los conectores derivados, el valor de cada conector; escritos con sumas y productos, son los siguientes, para toda valoración $v$ y todas las fórmulas $\varphi$ y $\psi$:

Además, $v((\varphi \leftrightarrow \psi)) = v(\varphi)\,v(\psi) + (1 - v(\varphi))\,(1 - v(\psi))$, que vale $1$ si y solo si $v(\varphi) = v(\psi)$, y $v((\varphi \veebar \psi)) = v(\varphi) + v(\psi) - 2\,v(\varphi)\,v(\psi)$, que vale $1$ si y solo si $v(\varphi) \neq v(\psi)$. Como los valores son $0$ o $1$, el cuadrado de un valor es el propio valor, $v(\varphi)\,v(\varphi) = v(\varphi)$, y un producto de valores vale $1$ si y solo si cada factor vale $1$; ambas observaciones se usarán sin repetirlas. Se usa también el lema de coincidencia: si dos valoraciones coinciden en las variables de $\varphi$, es decir, en las variables que son subfórmulas de $\varphi$, dan a $\varphi$ el mismo valor. De la clase sobre consecuencia y equivalencia semántica se toma la equivalencia semántica: $\varphi \eqsem \psi$ cuando $v(\varphi) = v(\psi)$ para toda valoración $v$. Por último, rige el convenio de las letras de la clase sobre la formalización: $p$, $q$ y $r$ designan las variables $v_1$, $v_2$ y $v_3$.

Funciones de verdad y su número

Sea $n$ un natural. Una fila de $n$ valores es una sucesión $a = (a_1, \ldots, a_n)$ en que cada $a_i$ es $0$ o $1$; el conjunto de todas ellas se denota $\{0, 1\}^{n}$. Una función de verdad de $n$ argumentos es una función

que asigna a cada fila un valor de verdad. Se presenta como una tabla: las filas se escriben en el orden de la tabla, desde aquella en que todos los valores son $1$ (para dos argumentos, $1\,1$, $1\,0$, $0\,1$, $0\,0$), y junto a cada fila se escribe su valor. Una función de verdad es, por tanto, una tabla de verdad sin fórmula: la columna de la derecha, sin nada escrito en su encabezado.

Fórmulas que representan funciones

Una fórmula y una función de verdad se relacionan del modo siguiente. Si $\varphi$ es una fórmula cuyas variables están entre $v_1, \ldots, v_n$, se dice que $\varphi$ representa la función de verdad $f$ de $n$ argumentos cuando, para toda valoración $v$,

es decir, cuando la tabla de $\varphi$, escrita con las variables $v_1, \ldots, v_n$, es la tabla de $f$. La condición sobre las variables no es un detalle: la fórmula $(p \wedge q)$ no representa ninguna función de un argumento, porque su valor no depende solo del de $p$.

Hay infinitas fórmulas con variables entre $v_1, \ldots, v_n$ y solo $2^{2^{n}}$ funciones; por tanto, muchas fórmulas representan la misma función, y la proposición dice que son exactamente las equivalentes entre sí. Lo que falta saber es si toda función es representada por alguna fórmula, o si algunas tablas quedan sin fórmula que las tenga.