Formas normais

Nas aulas anteriores desta unidade deu-se significado às fórmulas: a aula sobre a semântica da lógica proposicional estendeu cada valoração a todas as fórmulas; a aula sobre consequência e equivalência semânticas definiu a equivalência $\varphi \eqsem \psi$ e demonstrou a substituição semântica; a aula sobre as leis generalizadas de De Morgan e distributivas estendeu essas leis a conjunções e disjunções de $n$ fórmulas; e a aula sobre a completude funcional mostrou que toda função de verdade é representada por alguma fórmula. Ora, uma função de verdade é representada por infinitas fórmulas, que podem ser muito diferentes entre si: $(v_1 \rightarrow v_2)$, $\neg(v_1 \wedge \neg v_2)$ e $(((v_1 \downarrow v_1) \downarrow v_2) \downarrow ((v_1 \downarrow v_1) \downarrow v_2))$ são três nomes da mesma coisa. Se isso é assim, convém escolher em cada classe de equivalência um representante de forma fixa, que se leia sem esforço e com o qual certas perguntas se respondam olhando. Isso são as formas normais.

Literais, cláusulas e formas normais

Recorde-se, da aula sobre as leis generalizadas, a notação da conjunção e da disjunção de $n$ fórmulas, definida por recursão e associando pela esquerda; a de uma só fórmula é a própria fórmula.

Na mesma aula demonstrou-se que a ordem e o agrupamento dos termos não alteram a fórmula a menos de equivalência (associatividade generalizada e independência da ordem e das repetições); por isso escreveremos também $\varphi_1 \wedge \varphi_2 \wedge \cdots \wedge \varphi_n$ sem parênteses, entendendo o agrupamento pela esquerda.

Um literal é uma variável $v_n$, que se chama literal positivo, ou a negação $\neg v_n$ de uma variável, que se chama literal negativo. O oposto de um literal $\ell$, que escrevemos $\ell^{*}$, é o literal da mesma variável e do outro sinal:

Da definição segue-se que $(\ell^{*})^{*} = \ell$. Dois literais formam um par complementar se um é o oposto do outro, como $v_3$ e $\neg v_3$.

Uma cláusula é uma disjunção de literais, $\bigvee_{j=1}^{k} \ell_j$, e uma conjunção elementar é uma conjunção de literais, $\bigwedge_{j=1}^{k} \ell_j$, com $k \geq 1$ em ambos os casos; um literal sozinho é, portanto, ao mesmo tempo uma cláusula e uma conjunção elementar. Diz-se que um literal está em uma cláusula ou em uma conjunção elementar se é um dos seus $\ell_j$.

Uma fórmula está em forma normal disjuntiva se é uma disjunção de conjunções elementares, e em forma normal conjuntiva se é uma conjunção de cláusulas; isto é, se é, respectivamente, de uma das duas formas seguintes, onde $m$ e $k_1, \ldots, k_m$ são números naturais e cada $\ell_{i,j}$ é um literal:

Diremos que $\Phi$ é uma forma normal disjuntiva de $\varphi$ se está em forma normal disjuntiva e $\varphi \eqsem \Phi$, e o mesmo com a conjuntiva. Os comprimentos $k_i$ podem variar de uma conjunção (ou cláusula) para outra: exigir o mesmo número de literais em todas obrigaria a preencher com repetições e não acrescentaria nada.

Convém deter-se no que significa “estar em forma normal”. É uma propriedade da cadeia de círculos e discos, não do seu significado: a aula sobre a indução sobre os números naturais e sobre as fórmulas demonstrou a leitura única, de modo que perguntar se uma fórmula é uma disjunção, e de quê, tem uma só resposta. Ora, as abreviaturas oficiais fazem com que algumas fórmulas estejam em forma normal sem o parecer. A implicação $(v_1 \rightarrow v_2)$ define-se como $(\neg v_1 \vee v_2)$: não é que equivalha a essa cláusula, mas que é essa mesma cadeia, e portanto já está em forma normal. Mais surpreendente é a dupla negação. Pelas definições de $\neg$ e de $\vee$, a cadeia $(\varphi \vee \varphi)$ é $\neg(\varphi \downarrow \varphi)$, isto é, $\neg\neg\varphi$; donde $\neg\neg v_1$ não é um literal, mas é, símbolo por símbolo, a cláusula $(v_1 \vee v_1)$.

O valor das conjunções e das disjunções

Da aula sobre a semântica tomam-se os valores dos conectivos derivados: $v(\neg\varphi) = 1 - v(\varphi)$; $v(\varphi \wedge \psi) = v(\varphi)\,v(\psi)$, que vale $1$ se e somente se ambas valem $1$; e $v(\varphi \vee \psi) = 0$ se e somente se ambas valem $0$. A aula sobre as leis generalizadas de De Morgan e distributivas estendeu-os a $n$ fórmulas, por indução sobre o número de termos, no lema do valor: para toda valoração $v$, a conjunção $\bigwedge_{i=1}^{n} \varphi_i$ vale $1$ em $v$ se e somente se cada $\varphi_i$ vale $1$ em $v$, e a disjunção $\bigvee_{i=1}^{n} \varphi_i$ vale $1$ em $v$ se e somente se alguma $\varphi_i$ vale $1$ em $v$. Esse lema, que aqui se cita sem repetir sua demonstração, é o instrumento com que se calcula o valor de qualquer forma normal.

O segundo caso é fácil de passar despercebido: ao negar uma forma normal tende-se a escrever $\neg\ell_{i,j}$ em lugar de um literal, e $\neg\neg v_n$ não o é. A dupla negação é o que devolve o resultado ao molde.