# Estruturas e formas prenexas

Interpretação de termos e fórmulas, modelos, contraestruturas e transformação prenexa.

Página: https://resumos.rgo.pt/cadeiras/md/semantica-primeira-ordem/

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.

## Exercícios

Uma estrutura com dois objetos

Considera $A=\{0,1\}$, $R^{\mathcal A}=\{(0,1),(1,0)\}$ e $P^{\mathcal A}=\{0\}$. Avalia $\forall x\exists yR(x,y)$, $\exists y\forall xR(x,y)$ e $\exists x(P(x)\land R(x,x))$. Justifica.

Pista

A relação liga cada objeto apenas ao outro.

Mais uma pista

Para o candidato $y=0$, testa $x=0$; para $y=1$, testa $x=1$.

Solução

Os resultados são verdadeira, falsa e falsa. Na primeira, escolhemos $y=1-x$. Na segunda, para qualquer $y$, $x=y$ refuta $R(x,y)$. Na terceira, só $x=0$ tem $P$, mas $(0,0)\notin R^{\mathcal A}$, e nenhum objeto tem $R(x,x)$.

Confere a tua resposta:

*   Para o primeiro universal escolhi a testemunha por x.
*   Para o segundo existencial mostrei que nenhum y serve para todos.
*   Conferi a diagonal da relação na terceira fórmula.

Erros frequentes

Uma testemunha diferente por $x$ não satisfaz uma fórmula que exige um único $y$ exterior para todos.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/semantica-primeira-ordem/#testemunhas-e-contraexemplos-numa-estrutura)

Uma forma prenexa

Obtém uma forma prenexa de cada fórmula e indica as variáveis que continuam livres:

1.  $(\neg\forall xP(x))\lor\exists xQ(x,z)$;
2.  $(\forall xP(x))\to\exists x\forall yR(x,y,z)$.

No segundo caso, justifica por que muda o tipo do quantificador do antecedente.

Pista

As duas ocorrências quantificadas de $x$ pertencem a âmbitos diferentes.

Mais uma pista

Renomeia para $u$ e $v$, depois transporta os dois existenciais através de $\lor$.

Solução

Para a primeira, uma forma é $\exists u\exists v(\neg P(u)\lor Q(v,z))$. Primeiro $\neg\forall xP(x)\Leftrightarrow\exists u\neg P(u)$. O segundo existencial pode chamar-se $v$. Nenhuma das variáveis novas ocorre livre na outra parte, por isso podemos transportar. $z$ continua livre.

Na segunda, renomeamos as variáveis ligadas dos dois âmbitos para $u$ e $v$, e $y$ para $w$:

Eliminar a implicação deixa a negação do antecedente:

$$
\neg\forall uP(u)\lor\exists v\forall wR(v,w,z).
$$

A negação troca o universal por um existencial:

$$
\exists u\neg P(u)\lor\exists v\forall wR(v,w,z).
$$

Transportamos depois os quantificadores para o início:

$$
\exists u\exists v\forall w(\neg P(u)\lor R(v,w,z)).
$$

Cada transporte é válido porque a variável não ocorre livre na outra parte; o domínio é não vazio. $z$ continua livre e $w$ continua dentro da escolha de $v$.

Confere a tua resposta:

*   Troquei o universal negado por um existencial com negação.
*   Usei nomes distintos para os dois quantificadores.
*   Mantive z livre na matriz.
*   Justifiquei a troca do quantificador negado no antecedente.

Erros frequentes

Usar uma só variável para os dois quantificadores pode juntar testemunhas que eram independentes. Forma prenexa não exige fechar as variáveis livres.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/semantica-primeira-ordem/#forma-normal-prenexa)

Refutar a distribuição errada

Refuta $(\exists xP(x))\land(\exists xQ(x))\models\exists x(P(x)\land Q(x))$ com uma estrutura finita.

Pista

Usa objetos diferentes para as duas testemunhas.

Mais uma pista

Dois objetos com $P$ verdadeiro só no primeiro e $Q$ só no segundo chegam.

Solução

Escolhe $A=\{a,b\}$, $P^{\mathcal A}=\{a\}$ e $Q^{\mathcal A}=\{b\}$. Ambas as existências são verdadeiras, mas $P^{\mathcal A}\cap Q^{\mathcal A}=\emptyset$, logo a conclusão é falsa.

Confere a tua resposta:

*   Declarei o domínio e as duas relações unárias.
*   Cada existência tem uma testemunha.
*   Nenhum objeto satisfaz ambas as propriedades.

Erros frequentes

Um domínio vazio não é uma estrutura admitida nesta LPO e também não satisfaria as premissas.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/semantica-primeira-ordem/#equival%C3%AAncias-com-quantificadores)