Completude funcional

Funções de verdade

A aula sobre a semântica da lógica proposicional atribuiu a cada fórmula, em cada valoração, um valor de verdade, e mostrou que esse valor depende só dos valores das variáveis que nela ocorrem; donde toda fórmula com $n$ variáveis tem uma tabela-verdade de $2^{n}$ linhas. A pergunta desta aula é a inversa. Dada uma tabela qualquer, isto é, uma coluna de uns e zeros escrita arbitrariamente ao lado das $2^{n}$ linhas, há alguma fórmula que a tenha por tabela? Se isso vale para toda tabela, a linguagem não tem lacunas expressivas: tudo o que se pode dizer sobre o valor de verdade de $n$ enunciados, em função dos valores destes, diz-se com uma fórmula. E como neste curso toda fórmula composta é uma negação conjunta, a resposta dirá também se um só conectivo basta para dizer tudo.

O que se usa das aulas anteriores

Uma valoração é uma função $v$ do conjunto das variáveis $\{v_1, v_2, \ldots\}$ em $\{0, 1\}$, onde $1$ é o verdadeiro e $0$ o falso; a sua extensão a todas as fórmulas, que também se escreve $v$, é definida por recursão: $v((\varphi \downarrow \psi)) = 1$ se e somente se $v(\varphi) = 0$ e $v(\psi) = 0$. Das abreviaturas oficiais, a mesma aula calculou, no teorema dos valores dos conectivos derivados, o valor de cada conectivo; escritos com somas e produtos, são os seguintes, para toda valoração $v$ e todas as fórmulas $\varphi$ e $\psi$:

Além disso, $v((\varphi \leftrightarrow \psi)) = v(\varphi)\,v(\psi) + (1 - v(\varphi))\,(1 - v(\psi))$, que vale $1$ se e somente se $v(\varphi) = v(\psi)$, e $v((\varphi \veebar \psi)) = v(\varphi) + v(\psi) - 2\,v(\varphi)\,v(\psi)$, que vale $1$ se e somente se $v(\varphi) \neq v(\psi)$. Como os valores são $0$ ou $1$, o quadrado de um valor é o próprio valor, $v(\varphi)\,v(\varphi) = v(\varphi)$, e um produto de valores vale $1$ se e somente se cada fator vale $1$; ambas as observações serão usadas sem repeti-las. Usa-se também o lema da coincidência: se duas valorações coincidem nas variáveis de $\varphi$, isto é, nas variáveis que são subfórmulas de $\varphi$, dão a $\varphi$ o mesmo valor. Da aula sobre consequência e equivalência semânticas toma-se a equivalência semântica: $\varphi \eqsem \psi$ quando $v(\varphi) = v(\psi)$ para toda valoração $v$. Por último, vale a convenção das letras da aula sobre a formalização: $p$, $q$ e $r$ designam as variáveis $v_1$, $v_2$ e $v_3$.

Funções de verdade e o seu número

Seja $n$ um número natural. Uma linha de $n$ valores é uma sequência $a = (a_1, \ldots, a_n)$ em que cada $a_i$ é $0$ ou $1$; o conjunto de todas elas denota-se $\{0, 1\}^{n}$. Uma função de verdade de $n$ argumentos é uma função

que atribui a cada linha um valor de verdade. Apresenta-se como uma tabela: as linhas escrevem-se na ordem da tabela, a partir daquela em que todos os valores são $1$ (para dois argumentos, $1\,1$, $1\,0$, $0\,1$, $0\,0$), e ao lado de cada linha escreve-se o seu valor. Uma função de verdade é, portanto, uma tabela-verdade sem fórmula: a coluna da direita, sem nada escrito no seu cabeçalho.

Fórmulas que representam funções

Uma fórmula e uma função de verdade relacionam-se do modo seguinte. Se $\varphi$ é uma fórmula cujas variáveis estão entre $v_1, \ldots, v_n$, diz-se que $\varphi$ representa a função de verdade $f$ de $n$ argumentos quando, para toda valoração $v$,

isto é, quando a tabela de $\varphi$, escrita com as variáveis $v_1, \ldots, v_n$, é a tabela de $f$. A condição sobre as variáveis não é um detalhe: a fórmula $(p \wedge q)$ não representa nenhuma função de um argumento, porque o seu valor não depende só do de $p$.

Há infinitas fórmulas com variáveis entre $v_1, \ldots, v_n$ e só $2^{2^{n}}$ funções; portanto, muitas fórmulas representam a mesma função, e a proposição diz que são exatamente as equivalentes entre si. O que falta saber é se toda função é representada por alguma fórmula, ou se algumas tabelas ficam sem fórmula que as tenha.