Estruturas e formas prenexas

A fórmula $\forall x\,P(x)$ não diz quais são os objetos nem o que significa $P$. Para a avaliar precisamos de uma estrutura. Se a fórmula tiver variáveis livres, também precisamos de atribuir valores a essas variáveis.

Quantificadores num domínio finito

Toma a linguagem com um único predicado $P$ e domínio $A=\{a,b\}$, onde $P^{\mathcal A}=\{a\}$. Os nomes $a,b$ aqui identificam os objetos do domínio.

Objeto atribuído a $x$	$P(x)$
$a$	T
$b$	F

$\exists x\,P(x)$ calcula a disjunção dos dois valores, $T\lor F=T$: $a$ é uma testemunha. $\forall x\,P(x)$ calcula a conjunção, $T\land F=F$: $b$ é um contraexemplo. Esta expansão funciona porque listámos todos os objetos do domínio finito.

Uma estrutura completa

Para uma linguagem $L$, uma estrutura $\mathcal A=(A,\cdot^{\mathcal A})$ tem um domínio não vazio $A$ e uma interpretação de todos os símbolos não lógicos:

• Uma constante $a$ recebe um objeto $a^{\mathcal A}\in A$.
• Uma função de aridade $n$ recebe uma função total $f^{\mathcal A}:A^n\to A$.
• Um predicado de aridade $n$ recebe uma relação $R^{\mathcal A}\subseteq A^n$.

Considere-se $F_0=\{a\}$, $F_1=\{g\}$, $R_1=\{P\}$ e $R_2=\{R\}$. Vamos usar:

$$\begin{gathered} A=\mathbb N=\{0,1,2,\ldots\},\qquad a^{\mathcal A}=2,\\ g^{\mathcal A}(n)=n+1,\qquad P^{\mathcal A}=\{0,2,4,\ldots\},\\ R^{\mathcal A}=\{(n,m)\in\mathbb N^2:n<m\}. \end{gathered}$$

Nesta estrutura, $P$ significa “é par” e $R$ significa “é menor”. Numa estrutura diferente, esses símbolos podem ter outros significados. A igualdade, quando pertence à linguagem, compara os próprios objetos do domínio.

Avaliar termos e fórmulas

Uma interpretação das variáveis é uma função $s:\mathrm{Var}\to A$. Para $s(x)=3$, o termo $g(a)$ da linguagem representa $3$, e o termo $g(x)$ representa $4$.

A avaliação de um termo composto faz-se de dentro para fora. Por exemplo, $g(g(a))$ representa $4$, pois $a$ representa $2$ e aplicamos o sucessor duas vezes.

Escrevemos $\mathcal A\models_s\varphi$ quando $\varphi$ é verdadeira na estrutura com essa interpretação. Para uma fórmula atómica:

$$\mathcal A\models_s R(t_1,t_2) \quad\Longleftrightarrow\quad (\text{valor de }t_1,\text{valor de }t_2)\in R^{\mathcal A}.$$

Com $s(x)=3$, $R(a,x)$ é verdadeira, porque $2<3$. $P(x)$ é falsa, porque $3$ não é par. As conetivas calculam-se pelas mesmas tabelas da lógica proposicional.

Para quantificar, variamos só a variável ligada. $s[x\mapsto d]$ coincide com $s$ nas outras variáveis e atribui $d$ a $x$:

$$\begin{aligned} \mathcal A\models_s\forall x\,\varphi &\Longleftrightarrow\text{ para todo }d\in A, \ \mathcal A\models_{s[x\mapsto d]}\varphi,\\ \mathcal A\models_s\exists x\,\varphi &\Longleftrightarrow\text{ para algum }d\in A, \ \mathcal A\models_{s[x\mapsto d]}\varphi. \end{aligned}$$

Só os valores das variáveis livres podem alterar a verdade da fórmula. Uma proposição não tem variáveis livres, por isso escrevemos simplesmente $\mathcal A\models\varphi$.

Testemunhas e contraexemplos numa estrutura

Na estrutura dos naturais acima:

Fórmula	Resultado e justificação
$\forall x\exists y\,R(x,y)$	Verdadeira. Para cada $x$, escolhemos $y=x+1$.
$\exists y\forall x\,R(x,y)$	Falsa. Para qualquer $y$, $x=y$ dá $y<y$, falso.
$\exists x\,g(x)=a$	Verdadeira. $x=1$ é testemunha.
$\forall x\,g(x)\ne x$	Verdadeira. $x+1\ne x$ para todo o natural.
$\exists x(P(x)\land P(g(x)))$	Falsa. Dois naturais consecutivos não são ambos pares.

A frase $\forall x\exists y\,R(x,y)$ é verdadeira nesta estrutura, mas não é logicamente válida. Numa estrutura com domínio $\{u\}$ e $R^{\mathcal B}=\emptyset$ para $R$ binário, é falsa. Ou seja, não transformes a interpretação habitual de um símbolo numa propriedade lógica obrigatória.

Validade, satisfazibilidade e modelos

Uma fórmula é válida se é verdadeira em todas as estruturas da linguagem e todas as interpretações das variáveis. É satisfazível se existe pelo menos uma estrutura e uma interpretação que a tornam verdadeira. É insatisfazível se nenhuma serve.

Uma estrutura que satisfaz uma proposição é um modelo dessa proposição. Para um conjunto de proposições, um modelo tem de satisfazer todas na mesma estrutura.

Para refutar $\Gamma\models\varphi$, construímos uma estrutura e, se necessário, uma interpretação que satisfazem todas as premissas e tornam a conclusão falsa. Uma descrição incompleta do domínio ou dos símbolos não fornece uma contraestrutura completa.

Por exemplo, $\forall x(P(x)\lor Q(x))$ não implica $(\forall xP(x))\lor(\forall xQ(x))$. Escolhemos:

$$B=\{u,v\},\qquad P^{\mathcal B}=\{u\},\qquad Q^{\mathcal B}=\{v\}.$$

Cada objeto tem $P$ ou $Q$, por isso a premissa é verdadeira. Nem todos têm $P$ e nem todos têm $Q$, por isso a conclusão é falsa. Num domínio com um único objeto não conseguiríamos esta separação.

Validade proposicional e validade de primeira ordem

Se tratarmos cada fórmula atómica como uma variável proposicional independente, algumas atribuições deixam de corresponder a estruturas. Por exemplo, $a=b$, $b=c$ e $a=c$ não podem ter respetivamente os valores $T,T,F$: a igualdade dos objetos é transitiva.

Assim, $(a=b\land b=c)\to a=c$ é válida em todas as estruturas com igualdade, mas a sua abstração proposicional $(p\land q)\to r$ não é uma tautologia. A atribuição $p=q=T,r=F$ refuta apenas a abstração; não é uma contraestrutura da fórmula original.

Uma tautologia proposicional continua válida quando substituímos as variáveis por fórmulas de primeira ordem. A recíproca falha, porque igualdade e quantificadores impõem relações que uma tabela de variáveis independentes não representa.

Equivalências com quantificadores

Podemos distribuir um universal sobre conjunção e um existencial sobre disjunção:

$$\begin{aligned} \forall x(\varphi\land\psi)&\Leftrightarrow (\forall x\varphi)\land(\forall x\psi),\\ \exists x(\varphi\lor\psi)&\Leftrightarrow (\exists x\varphi)\lor(\exists x\psi). \end{aligned}$$

Não há equivalência geral para as outras duas combinações. No exemplo com $P^{\mathcal B}=\{u\}$ e $Q^{\mathcal B}=\{v\}$, também $(\exists xP(x))\land(\exists xQ(x))$ é verdadeira, mas $\exists x(P(x)\land Q(x))$ é falsa. As testemunhas das duas existências podem ser diferentes.

Se $x$ não ocorre livre em $\psi$, podemos transportar o quantificador através de $\land$ ou $\lor$:

$$(Qx\,\varphi)\circ\psi\Leftrightarrow Qx(\varphi\circ\psi),$$

para $Q\in\{\forall,\exists\}$ e $\circ\in\{\land,\lor\}$. A condição sobre as variáveis impede que o transporte capture um $x$ livre em $\psi$. Estas regras usam o domínio não vazio da LPO.

Ao transportar pela implicação, a posição importa, pois o antecedente fica negado quando substituímos $\to$ por $\neg\varphi\lor\psi$. Por exemplo, ainda com $x$ não livre em $\psi$:

$$(\forall x\varphi)\to\psi\Leftrightarrow \exists x(\varphi\to\psi).$$

Forma normal prenexa

Uma fórmula está na forma normal prenexa quando todos os quantificadores aparecem no início, seguidos de uma fórmula sem quantificadores, a matriz. Uma fórmula sem quantificadores já está nesta forma.

O método é:

1. Eliminar $\to$ e outras abreviaturas, ficando com $\neg$, $\land$ e $\lor$.
2. Renomear variáveis ligadas para evitar nomes repetidos ou nomes também usados livres.
3. Levar negações para dentro, trocando $\forall$ e $\exists$ quando necessário.
4. Levar os quantificadores para fora sem capturar variáveis livres.

Vamos transformar:

$$\neg\forall x\bigl(P(x)\to\exists y\,R(x,y)\bigr) \lor\forall x\,Q(x,z).$$

O $z$ está livre e tem de continuar livre. Renomeamos o segundo $x$ para $u$ e tratamos a negação:

$$\begin{aligned} &\exists x\neg\bigl(\neg P(x)\lor\exists y\,R(x,y)\bigr) \lor\forall u\,Q(u,z)\\ &\Leftrightarrow \exists x\bigl(P(x)\land\forall y\,\neg R(x,y)\bigr) \lor\forall u\,Q(u,z)\\ &\Leftrightarrow \exists x\forall y\forall u \bigl((P(x)\land\neg R(x,y))\lor Q(u,z)\bigr). \end{aligned}$$

No último passo, $y$ não ocorre livre em $P(x)$, e $x,y$ não ocorrem livres em $Q(u,z)$. O $u$ foi escolhido novo. Estas verificações justificam o transporte, que se decompõe em três movimentos, cada um com a sua condição:

1. $\exists x$ atravessa a disjunção, porque $x$ não ocorre livre em $\forall u\,Q(u,z)$.
2. $\forall y$ atravessa a conjunção com $P(x)$ e depois a disjunção, porque $y$ não ocorre livre em nenhuma das outras partes.
3. $\forall u$ atravessa a disjunção, porque $u$ foi escolhido novo e não ocorre livre na parte esquerda.

A ordem $\exists x\forall y\forall u$ conserva essas dependências. Trocar dois quantificadores do mesmo tipo mantém a equivalência; trocar $\exists x$ com $\forall y$ já exigiria nova verificação.

Não há uma única forma prenexa para cada fórmula. A ordem final dos quantificadores tem de resultar de equivalências permitidas, não de os ordenar por tipo ou nome.