🔍 quantificadores em profundidade

Na lógica de primeira ordem, quantificadores permitem expressar propriedades sobre todos ou alguns elementos de um domínio. Os dois principais são o quantificador universal (\(\forall\)) e o quantificador existencial (\(\exists\)). Compreender seu uso, aninhamento e interação é fundamental para formalizar matemática, computação e linguagem natural.

📌 fundamentos

\(\forall x\) (para todo x)

\(\forall x P(x)\) significa que a propriedade \(P\) é verdadeira para todos os elementos do domínio.

Exemplo: \(\forall x (x \ge 0)\) no domínio dos números naturais é verdadeiro.

\(\exists x\) (existe x)

\(\exists x P(x)\) significa que existe pelo menos um elemento no domínio para o qual \(P\) é verdadeira.

Exemplo: \(\exists x (x < 0)\) nos inteiros é verdadeiro (ex.: -1).

🎯 escopo e variáveis livres/ligadas

O escopo de um quantificador é a parte da fórmula onde a variável quantificada está ligada. Variáveis fora do escopo de qualquer quantificador são livres.

Na fórmula \(\forall x (P(x) \land Q(y))\), \(x\) está ligada, \(y\) é livre. O escopo de \(\forall x\) é \(P(x) \land Q(y)\).

Uma fórmula sem variáveis livres é chamada de sentença (ou fórmula fechada).

🚫 negação de quantificadores

A negação de um quantificador troca o tipo e nega a propriedade:

• \(\neg \forall x P(x) \equiv \exists x \neg P(x)\)
• \(\neg \exists x P(x) \equiv \forall x \neg P(x)\)

Exemplo: Negar "Todos os cisnes são brancos" (\(\forall x (Cisne(x) \rightarrow Branco(x))\)) resulta em "Existe um cisne que não é branco" (\(\exists x (Cisne(x) \land \neg Branco(x))\)).

🔄 aninhamento e ordem

Quando múltiplos quantificadores aparecem, a ordem pode mudar o significado. Considere um domínio de pessoas e a relação \(Ama(x, y)\) significando "x ama y".

\(\forall x \exists y Ama(x, y)\)

"Toda pessoa ama alguém" (cada um ama uma pessoa, possivelmente diferente).

\(\exists y \forall x Ama(x, y)\)

"Existe uma pessoa que é amada por todos" (um amado universal).

Note a diferença: a primeira não implica a segunda. A ordem dos quantificadores importa crucialmente.

Outras combinações comuns

• \(\forall x \forall y P(x, y)\): "Para todo x e todo y, P(x,y) vale".
• \(\exists x \exists y P(x, y)\): "Existem x e y tais que P(x,y)".
• \(\exists x \forall y P(x, y)\): "Existe um x tal que para todo y, P(x,y)".

🌍 interpretação em modelos

O valor lógico de uma fórmula quantificada depende do modelo (domínio + interpretação dos símbolos).

Considere o domínio \(D = \{a, b\}\) e a relação \(R\) definida por \(R(a,a)=V, R(a,b)=F, R(b,a)=V, R(b,b)=F\).

\(\forall x \exists y R(x, y)\)? Para x=a, existe y=a tal que R(a,a)=V. Para x=b, existe y=a tal que R(b,a)=V. Logo, a fórmula é verdadeira neste modelo.

\(\exists y \forall x R(x, y)\)? Para y=a, R(a,a)=V, R(b,a)=V → funciona. Portanto, também verdadeira. Nem sempre acontece.

🧠 propriedades importantes

• \(\forall x (P(x) \land Q(x)) \equiv (\forall x P(x)) \land (\forall x Q(x))\) (distribuição do universal sobre a conjunção).
• \(\exists x (P(x) \lor Q(x)) \equiv (\exists x P(x)) \lor (\exists x Q(x))\) (distribuição do existencial sobre a disjunção).
• \(\forall x P(x) \equiv \neg \exists x \neg P(x)\) (relação entre os quantificadores).
• \(\exists x P(x) \equiv \neg \forall x \neg P(x)\).
• \(\forall x (P(x) \rightarrow Q) \equiv (\exists x P(x)) \rightarrow Q\) (se Q não depende de x).
• \(\exists x (P(x) \rightarrow Q) \equiv (\forall x P(x)) \rightarrow Q\).

🗣️ tradução da linguagem natural

"Todo gato é mamífero":
\(\forall x (Gato(x) \rightarrow Mamifero(x))\)

"Algum gato é preto":
\(\exists x (Gato(x) \land Preto(x))\)

"Nenhum gato é cão":
\(\forall x (Gato(x) \rightarrow \neg Cao(x))\) ou \(\neg \exists x (Gato(x) \land Cao(x))\)

"Nem todo gato é preto":
\(\neg \forall x (Gato(x) \rightarrow Preto(x))\) ≡ \(\exists x (Gato(x) \land \neg Preto(x))\)

📐 exemplos matemáticos

• \(\forall \epsilon > 0 \; \exists \delta > 0 \; \forall x \;(|x - a| < \delta \rightarrow |f(x) - f(a)| < \epsilon)\) (continuidade).
• \(\exists M > 0 \; \forall n \in \mathbb{N} \; |a_n| \leq M\) (sequência limitada).
• \(\forall x \in \mathbb{R} \; \exists y \in \mathbb{R} \; (y^2 = x)\) é falso (números negativos).

📊 tabela de negações

Fórmula	Negação
\(\forall x P(x)\)	\(\exists x \neg P(x)\)
\(\exists x P(x)\)	\(\forall x \neg P(x)\)
\(\forall x \exists y R(x,y)\)	\(\exists x \forall y \neg R(x,y)\)
\(\exists x \forall y R(x,y)\)	\(\forall x \exists y \neg R(x,y)\)

\(\displaystyle \forall x (P(x) \rightarrow Q) \equiv (\exists x P(x)) \rightarrow Q \quad (x \text{ não livre em } Q)\)

✦ “A ordem dos quantificadores altera o significado.” ✦