🔍 exercícios de lógica de primeira ordem

A lógica de primeira ordem (ou cálculo de predicados) estende a lógica proposicional com quantificadores (\(\forall\), \(\exists\)), variáveis e predicados. Os exercícios a seguir envolvem a tradução de sentenças, negação de fórmulas quantificadas, validade de argumentos e interpretação em modelos. Pratique para dominar essa linguagem fundamental da matemática e da computação.

🔰 nível 1 · predicados e quantificadores básicos

1. Considere o domínio dos números inteiros e os predicados: \(P(x)\): "x é par", \(Q(x)\): "x é ímpar". Escreva em linguagem natural:
   a) \(\forall x (P(x) \rightarrow \neg Q(x))\)
   b) \(\exists x (P(x) \land Q(x))\)
   c) \(\neg \forall x P(x)\)
2. Traduza para a linguagem da lógica de primeira ordem:
   a) "Todo número natural é maior ou igual a zero." (use \(\mathbb{N}\) como domínio e o predicado \(M(x,y)\) para "x é maior ou igual a y").
   b) "Existe um número primo que é par." (use \(Primo(x)\) e \(Par(x)\)).
   c) "Nenhum gato é cão." (use \(Gato(x)\) e \(Cao(x)\)).
3. Identifique quais das expressões abaixo são fórmulas bem formadas (FBF) da lógica de primeira ordem. Corrija as que não são.
   a) \(\forall x (P(x) \land Q(y))\)
   b) \(\exists x P(x) \rightarrow \forall y Q(y)\)
   c) \(P(\forall x) \rightarrow Q(x)\)
   d) \(\forall x (P(x) \rightarrow \exists y R(x,y))\)

🔄 nível 2 · negação de fórmulas quantificadas

1. Negue as seguintes sentenças, aplicando as regras de negação dos quantificadores:
   a) \(\forall x (P(x) \rightarrow Q(x))\)
   b) \(\exists x (P(x) \land \neg Q(x))\)
   c) \(\forall x \exists y R(x,y)\)
   d) \(\exists x \forall y (P(x,y) \leftrightarrow Q(x))\)
2. Considere a afirmação: "Toda pessoa tem uma mãe." (use \(Pessoa(x)\) e \(Mae(y,x)\) para "y é mãe de x"). Escreva sua negação em linguagem natural e em lógica de primeira ordem.
3. Determine o valor lógico (V ou F) das seguintes sentenças, considerando o domínio dos números reais:
   a) \(\forall x (x^2 \ge 0)\)
   b) \(\exists x (x^2 = -1)\)
   c) \(\forall x \exists y (y = x+1)\)
   d) \(\exists x \forall y (x \le y)\)

🧠 nível 3 · validade e interpretação

1. Considere um domínio com os elementos {a, b} e os predicados definidos por: \(P(a)=V, P(b)=F, Q(a)=V, Q(b)=V, R(a,a)=V, R(a,b)=F, R(b,a)=V, R(b,b)=F\). Determine se as fórmulas abaixo são verdadeiras nesse modelo:
   a) \(\forall x P(x)\)
   b) \(\exists x (P(x) \land Q(x))\)
   c) \(\forall x \exists y R(x,y)\)
   d) \(\exists x \forall y R(x,y)\)
2. Mostre que a fórmula \(\forall x (P(x) \lor Q(x)) \rightarrow (\forall x P(x) \lor \forall x Q(x))\) não é universalmente válida, exibindo um contraexemplo (um modelo onde ela é falsa).
3. Verifique se o argumento é válido: \(\forall x (P(x) \rightarrow Q(x)),\ \forall x (Q(x) \rightarrow R(x)) \vdash \forall x (P(x) \rightarrow R(x))\).
4. Construa um modelo (domínio e interpretação dos predicados) que torne a sentença \(\exists x P(x) \land \exists x Q(x) \land \neg \exists x (P(x) \land Q(x))\) verdadeira.

⚡ nível 4 · desafios e aplicações

1. Traduza para a lógica de primeira ordem e depois negue: "Existe um número real que é maior que todos os números racionais." (domínio: números reais; use \(Racional(x)\) e \(Maior(x,y)\)).
2. Considere a sentença: \(\forall x \forall y (x = y \leftrightarrow (P(x) \leftrightarrow P(y)))\). Em que tipo de domínio essa sentença é verdadeira? O que ela afirma sobre o predicado \(P\)?
3. Prove, usando dedução natural (informalmente), que \(\forall x (P(x) \rightarrow Q(x))\) e \(\forall x (Q(x) \rightarrow R(x))\) implicam \(\forall x (P(x) \rightarrow R(x))\).
4. Escreva uma fórmula de primeira ordem que expresse a propriedade "uma relação \(R\) é transitiva". Depois, escreva sua negação.
5. Desafio: Mostre que a fórmula \(\forall x \exists y R(x,y) \land \forall x \forall y \forall z (R(x,y) \land R(x,z) \rightarrow y = z)\) implica a existência de uma função. Explique.

💡 dicas e respostas selecionadas

• Nível 1 - 2a: \(\forall x (Nat(x) \rightarrow M(x,0))\).
• Nível 1 - 3: a) FBF (variável livre y), b) FBF, c) não é FBF (quantificador sobre termo), d) FBF.
• Nível 2 - 1a: \(\neg \forall x (P(x) \rightarrow Q(x)) \equiv \exists x \neg (P(x) \rightarrow Q(x)) \equiv \exists x (P(x) \land \neg Q(x))\).
• Nível 2 - 1c: \(\neg \forall x \exists y R(x,y) \equiv \exists x \forall y \neg R(x,y)\).
• Nível 3 - 1a: Falso (pois \(P(b)=F\)).
• Nível 3 - 1c: Verdadeiro (para cada x existe y: a→a, b→a).
• Nível 4 - 2: A sentença força que \(P\) é constante (todos os elementos têm o mesmo valor de verdade em P) ou então o domínio tem no máximo um elemento.

Use papel e lápis para construir tabelas e modelos. A prática leva à compreensão profunda!

\(\displaystyle \forall x (P(x) \rightarrow Q(x)),\ \exists x P(x) \vdash \exists x Q(x)\) (exemplo de regra válida)

✦ pratique quantificadores, predicados e mundos possíveis ✦