Quantificadores e linguagem de primeira ordem

«Todos os estudantes gostam de alguma cadeira» não é só uma combinação de proposições. Fala de objetos, os estudantes e as cadeiras, e de uma relação entre eles. A lógica de primeira ordem, LPO ou FOL, permite escrever essa estrutura e distinguir «uma cadeira por estudante» de «a mesma cadeira para todos».

Termos e afirmações

Em “a soma de $x$ e $2$”, $x+2$ é um termo: nomeia um objeto. Em "$x+2=5$", a igualdade transforma o termo numa fórmula. A notação $F_n$ e $R_n$ distingue funções de relações pelo número de argumentos; o valor de $n$ é a aridade, definida já a seguir. Lê $F_1$ como “função de um argumento” e $R_2$ como “relação binária”.

Termos e fórmulas

Uma linguagem de primeira ordem tem variáveis, conetivas, quantificadores e, quando indicado, igualdade. Os símbolos não lógicos especificam o que podemos nomear:

• $F_0$ contém constantes, como $a$ ou $0$.
• $F_n$ contém símbolos de função com aridade $n$, como $s$ de aridade 1 ou $f$ de aridade 2.
• $R_n$ contém símbolos de predicado com aridade $n$, como $P$ de aridade 1 ou $R$ de aridade 2.

A aridade é o número de argumentos. Uma constante pode ver-se como uma função de aridade zero.

Um termo representa um objeto. Uma variável é termo, uma constante é termo e aplicar uma função a termos também produz um termo. Um termo é fechado quando não contém variáveis.

Se $F_0=\{a\}$, $F_1=\{s\}$ e $F_2=\{f\}$, então $f(s(a),x)$ é termo, mas não é fechado. $f(a,s(a))$ é fechado. $f(a)$ tem aridade errada, por isso não é termo desta linguagem.

Uma fórmula atómica aplica um predicado a termos, ou compara dois termos pela igualdade. Com $R_1=\{P\}$ e $R_2=\{R\}$, temos $P(s(a))$, $R(x,f(a,x))$ e $x=s(a)$. Os predicados produzem afirmações, não objetos. Por isso, $s(P(a))$ e $P(a)=P(x)$ não são fórmulas bem formadas.

A partir das fórmulas atómicas usamos as conetivas e os quantificadores. Se $\varphi$ é fórmula, $\forall x\,\varphi$ e $\exists x\,\varphi$ também são.

Domínio e tradução

O quantificador universal $\forall x$ significa “para todo o objeto $x$ do domínio”. O existencial $\exists x$ significa “existe pelo menos um objeto $x$ do domínio”. O domínio não muda a meio da fórmula.

Se o domínio são pessoas, $E(x)$ significa ”$x$ é estudante” e $L(x)$ significa ”$x$ lê”:

Frase	Fórmula
Todos os estudantes leem	$\forall x(E(x)\to L(x))$
Algum estudante lê	$\exists x(E(x)\land L(x))$
Nenhum estudante lê	$\forall x(E(x)\to\neg L(x))$
Nem todos os estudantes leem	$\exists x(E(x)\land\neg L(x))$

O universal usa uma implicação para restringir a exigência aos estudantes. Uma pessoa que não é estudante não viola a primeira fórmula. O existencial usa uma conjunção para exigir que a testemunha seja estudante e leia. $\exists x(E(x)\to L(x))$ seria verdadeira só por existir uma pessoa que não é estudante.

Quando o domínio já contém apenas estudantes, “todos leem” pode escrever-se $\forall x\,L(x)$. Explicitar o domínio antes de traduzir evita restrições em falta.

Ordem dos quantificadores

Se $E(x)$ significa ”$x$ é estudante”, $C(y)$ significa ”$y$ é uma cadeira” e $G(x,y)$ significa ”$x$ gosta da cadeira $y$”, então “todos os estudantes gostam de alguma cadeira” escreve-se, num domínio com pessoas e cadeiras:

$$\forall x\bigl(E(x)\to\exists y(C(y)\land G(x,y))\bigr).$$

O $y$ pode depender de $x$. A Ana pode gostar de MD e o Rui de outra cadeira. A existência não exige que só gostem de uma.

Por exemplo, num domínio que contém exatamente Ana, Rui, MD e FP, fixamos $E=\{\text{Ana},\text{Rui}\}$ e $C=\{\text{MD},\text{FP}\}$. A tabela dá os únicos pares de $G$:

Estudante	MD	FP
Ana	Sim	Não
Rui	Não	Sim

Cada linha tem um «Sim»: cada estudante tem uma cadeira. Nenhuma coluna tem dois «Sim»: não há cadeira comum. A tabela separa as duas condições sem mudar os objetos nem a relação.

Para exigir uma cadeira comum, usamos a fórmula seguinte, falsa nessa tabela:

$$\exists y\bigl(C(y)\land\forall x(E(x)\to G(x,y))\bigr).$$

Em geral, $\exists y\forall x\,R(x,y)$ implica $\forall x\exists y\,R(x,y)$, mas a direção inversa falha. Em $\mathbb N$, $\forall x\exists y(x<y)$ é verdadeira, escolhendo $y=x+1$. $\exists y\forall x(x<y)$ é falsa: para qualquer candidato $y$, o próprio $x=y$ refuta $x<y$. Por isso, podes trocar universais entre si ou existenciais entre si, mas trocar quantificadores diferentes pode mudar o significado.

Negar frases quantificadas

Negar “todos” produz uma testemunha que falha. Negar “existe” exige que todos falhem:

$$\neg\forall x\,\varphi\Leftrightarrow\exists x\,\neg\varphi, \qquad \neg\exists x\,\varphi\Leftrightarrow\forall x\,\neg\varphi.$$

Por exemplo:

$$\begin{aligned} \neg\forall x\exists y\,R(x,y) &\Leftrightarrow\exists x\neg\exists y\,R(x,y)\\ &\Leftrightarrow\exists x\forall y\,\neg R(x,y). \end{aligned}$$

A negação diz que existe um $x$ para o qual nenhum $y$ serve. Não diz que nenhum $x$ tem um $y$.

“Nem todos os estudantes leem” é a negação de $\forall x(E(x)\to L(x))$. Obtemos $\exists x(E(x)\land\neg L(x))$ porque negar uma implicação exige antecedente verdadeiro e consequente falso.

Existência única e contagens pequenas

“Existe exatamente um $x$ com $P(x)$” escreve-se:

$$\exists x\bigl(P(x)\land\forall y(P(y)\to y=x)\bigr).$$

A abreviatura é $\exists!x\,P(x)$. A primeira parte prova existência; a segunda, unicidade. Só $\forall x\forall y((P(x)\land P(y))\to x=y)$ diz no máximo um e admite que não exista nenhum.

Para “pelo menos dois”, pedimos testemunhas distintas:

$$\exists x\exists y(P(x)\land P(y)\land x\ne y).$$

Para “exatamente dois”, acrescentamos que qualquer objeto com $P$ é um dos dois:

$$\exists x\exists y\bigl(P(x)\land P(y)\land x\ne y \land\forall z(P(z)\to(z=x\lor z=y))\bigr).$$

Variáveis livres e ligadas

O âmbito de um quantificador é a fórmula que ele quantifica. Uma ocorrência de $x$ está ligada quando está nesse âmbito de $\forall x$ ou $\exists x$. As restantes ocorrências são livres.

Em

$$(\forall x\,R(x,y))\land P(x),$$

o primeiro $x$ está ligado; o segundo está livre. $y$ também está livre. Logo, o conjunto de variáveis livres é $\{x,y\}$. Uma variável pode ter ocorrências livres e ligadas na mesma fórmula.

Uma fórmula sem variáveis livres é uma proposição, ou fórmula fechada. As variáveis ligadas continuam a aparecer, mas os seus valores são escolhidos pelos quantificadores. Não confundas termo fechado, que não contém variáveis, com fórmula fechada, que pode conter variáveis todas ligadas.

Pelas convenções de precedência, $\forall x\,P(x)\lor Q(x)$ significa $(\forall x\,P(x))\lor Q(x)$. Para quantificar as duas partes, escreve $\forall x(P(x)\lor Q(x))$.

Substituição sem captura

$\varphi[x\mapsto t]$ substitui apenas as ocorrências livres de $x$ pelo termo $t$.

Se $\varphi=(\forall x\,P(x))\land R(x,y)$, então:

$$\varphi[x\mapsto f(a,y)] =(\forall x\,P(x))\land R(f(a,y),y).$$

O $x$ ligado não muda. A substituição não deve ligar uma variável que estava livre no termo inserido. Dizemos que $t$ está livre para $x$ em $\varphi$ quando nenhuma ocorrência livre de $x$ está sob um quantificador de uma variável que ocorre em $t$.

Em $\forall y\,R(x,y)$, o termo $f(y)$ não está livre para $x$. A substituição literal daria $\forall y\,R(f(y),y)$ e capturaria o $y$ inserido. Para uma substituição que preserve o significado, renomeamos primeiro a variável ligada:

$$\forall y\,R(x,y)\Leftrightarrow\forall z\,R(x,z),$$

com $z$ novo. Agora substituímos e obtemos $\forall z\,R(f(y),z)$. O $y$ do termo continua livre.

Quando um exercício pede “para que variáveis o termo é livre”, verifica cada ocorrência livre dessa variável. Se uma única ocorrência provocaria captura, a condição falha. Se a variável não ocorre livre, não há ocorrência a capturar e a condição é satisfeita.

Numa substituição simultânea, os termos inseridos não recebem a outra substituição. Em $R(x,y)[x\mapsto y,y\mapsto a]$, o resultado é $R(y,a)$, não $R(a,a)$. Duas substituições sucessivas podem dar outro resultado.