Exercícios de Lógica de Primeira Ordem

Estes exercícios foram copiados e/ou inspirados nas seguintes obras:

• Lógica e Aritmética de Augusto Franco de Oliveira.
• forallχ de P. D. Magnus.
• Logic in Computer Science de Michael Huth e Mark Ryan.
• Artificial Intelligence, A Modern Approach de Stuart Russell e Peter Norvig.
• Mathematics for Computer Science: Course Textbook de Eric Lehman, F Thomson Leighton e Albert R Meyer.

Formalização de Linguagem Natural

Exercício 1 No domínio dos animais, formalize:

1. O Aníbal, o Bói e a Certa vivem no Jardim Zoológico.
2. Bói é um réptil, mas não é um crocodilo.
3. Se Certa gosta do Bói então Bói é um macaco.
4. Se Bói e Certa são crocodilos, Aníbal gosta de ambos.
5. Alguns répteis vivem no jardim zoológico.
6. Todo o crocodilo é um réptil.
7. Qualquer animal que viva num jardim zoológico é um macaco ou um crocodilo.
8. Alguns répteis não são crocodilos.
9. Certa gosta de um réptil.
10. Bói gosta de todos os macacos que moram no jardim zoológico.
11. Todos os animais de que Aníbal gosta também gostam dele.
12. Se algum animal for um réptil, é o Aníbal.
13. Se algum animal for um crocodilo, também é um réptil.
14. Qualquer animal de que Certa gosta, também Aníbal gosta.
15. Há um animal que gosta do Bói mas, infelizmente, o Bói não corresponde.

Exercício 2 $$\begin{array}{ll}S\left(x\right)& x\text{sabe a combinac¸a˜o do cofre.}\\ E\left(x\right)& x\text{eˊ espia˜o.}\\ V\left(x\right)& x\text{eˊ vegetariano.}\\ C\left(x,y\right)& x\text{confia em}y.\\ B& \text{Bond, James.}\\ G& \text{Nell, Ma.}\end{array}$$

Use os símbolos acima para formalizar:

1. Bond é um espião, mas nenhum vegetariano é espião.
2. Ninguém sabe a combinação do cofre, a não ser que Nell a saiba.
3. Nenhum espião sabe a combinação do cofre.
4. Nem Bond nem Nell são vegetarianos.
5. Nell confia num vegetariano.
6. Quem confia em Bond confia num vegetariano.
7. Quem confia em Bond confia em alguém que confia num vegetariano.
8. Só Nell sabe a combinação do cofre.
9. Nell confia em Bond, mas em mais ninguém.
10. A pessoa que sabe a combinação do cofre é vegetariano.
11. A pessoa que sabe a combinação do cofre não é espião.

Exercício 3 Defina linguagens adequadas, formalize e demonstre:

1. Os únicos candidatos são o João e o Alberto. O João e o Alberto são idiotas. Portanto, qualquer candidato é idiota.
2. Todo o barbeiro faz a barba das pessoas que não se barbeiam a si próprias. Nenhum barbeiro faz a barba das pessoas que se barbeiam a si próprias. Portanto, não existem barbeiros.

Fórmulas Proposicionais

Exercício 4 Tendo em conta as convenções de escrita, desenhe árvores de análise sintática das seguintes fórmulas:

1. $p\left(a\right)$
2. $p\left(a\right)\to q\left(a\right)$
3. $\forall xp\left(x\right)\to q\left(x\right)$
4. $p\left(a\right)\wedge \left(\forall xp\left(x\right)\to q\left(x\right)\to q\left(a\right)\right)$
5. $\left(p\left(a\right)\wedge \forall xp\left(x\right)\to q\left(x\right)\right)\to q\left(a\right)$
6. $\left(p\left(a\right)\wedge \forall xp\left(x\right)\right)\to \left(q\left(x\right)\to q\left(a\right)\right)$

Exercício 5 Ocorrências Livres e Ligadas

1. Identifique as ocorrências livres e ligadas da variável $x$ nas seguintes fórmulas:

   1. $\forall x(p(x)\to q(x))$
   2. $p(x)\wedge \exists yr(x,y)$
   3. $\forall y(p(y)\to q(x))$
   4. $\exists x(p(x)\vee r(x,y))$
   5. $(\forall xp(x))\to q(x)$

2. Indique se as seguintes afirmações são verdadeiras ou falsas:

   1. Na fórmula $\forall x(p(x)\to q(x))$, todas as ocorrências de $x$ são ligadas.
   2. Na fórmula $p(x)\wedge \exists yr(x,y)$, a primeira ocorrência de $x$ é livre e a segunda é ligada.
   3. Na fórmula $\forall y(p(y)\to q(x))$, a variável $x$ não tem ocorrências ligadas.
   4. Na fórmula $\exists x(p(x)\vee r(x,y))$, a variável $y$ tem uma ocorrência livre.
   5. Na fórmula $(\forall xp(x))\to q(x)$, a variável $x$ tem uma ocorrência livre.

3. Reescreva as seguintes fórmulas, renomeando as variáveis ligadas para evitar conflitos de nomes:

   1. $\forall x(p(x)\to \exists xq(x))$
   2. $\exists x(p(x)\wedge \forall yr(x,y))$
   3. $\forall x(p(x)\to \exists y(q(y)\wedge r(x,y)))$

4. Construa fórmulas da lógica de primeira ordem que satisfaçam as seguintes condições:

   1. Uma fórmula com duas variáveis livres e uma variável ligada.
   2. Uma fórmula com uma variável livre e duas variáveis ligadas.
   3. Uma fórmula com todas as variáveis ligadas.
   4. Uma fórmula com todas as variáveis livres.

5. Considere a seguinte fórmula: $\forall x(p(x)\to \exists y(q(x,y)\wedge r(y)))$

   1. Identifique as ocorrências livres e ligadas de $x$ e $y$.
   2. Reescreva a fórmula, renomeando as variáveis ligadas para evitar conflitos de nomes.
   3. Construa um modelo que satisfaça a fórmula.

6. Identifique os termos livres e não livres na fórmula $\forall x(p(x,y)\to q(f(x),z))$.

7. Quais dos seguintes termos são livres e quais são não livres na fórmula $\exists x(r(x,g(y))\wedge \forall zs(x,z,h(x)))$?

   1. $x$
   2. $y$
   3. $z$
   4. $g(y)$
   5. $h(x)$

8. Dada a fórmula $\forall x(p(x)\to \exists yq(x,y,f(z)))$, determine se as seguintes afirmações são verdadeiras ou falsas:

   1. O termo $x$ é livre para $z$.
   2. O termo $y$ é não livre para $z$.
   3. O termo $z$ é livre para $z$.
   4. O termo $f(z)$ é não livre para $z$.

9. Construa uma fórmula da lógica de primeira ordem com as seguintes características:

   1. Contém pelo menos um termo livre e um termo não livre.
   2. Utiliza as funções $f$ e $g$ e os predicados $p$ e $q$.

Dedução Natural

Exercício 6 Faça as seguintes provas, usando acumulativamente as regras e condições indicadas:

Sejam $p,q,r$ símbolos relacionais, $f$ funcional e $a,b$ termos adequados.

Eliminação Universal: ${\forall }^{-}$

1. $p\left(a\right),\forall xp\left(x\right)\to q\left(x\right)⊢q\left(a\right)$
2. $\neg q\left(a\right),\forall xp\left(x\right)\to q\left(x\right)⊢\neg p\left(a\right)$

Introdução Universal: ${\forall }^{+}$.

3. $\forall xp\left(x\right)\to q\left(x\right),\forall xq\left(x\right)\to r\left(x\right)⊢\forall x\left(p\left(x\right)\to r\left(x\right)\right)$
4. $\forall xp\left(x\right),\forall xp\left(x\right)\to q\left(x\right)⊢\forall xq\left(x\right)$
5. $\forall xp\left(x\right)\wedge q\left(x\right)⊢\forall xp\left(x\right)$
6. $\forall xp\left(x\right)\wedge q\left(x\right)⊣⊢\forall xp\left(x\right)\wedge \forall xq\left(x\right)$
7. $\forall xp\left(x\right)\vee q\left(x\right),\forall x\neg p\left(x\right)⊢\forall xq\left(x\right)$

Introdução Existencial: ${\exists }^{+}$.

8. $p\left(a\right),\forall xp\left(x\right)\to q\left(x\right)⊢\exists xq\left(x\right)$

Eliminação Existencial: ${\exists }^{-}$.

N.B. $\forall xy$ abrevia $\forall x\forall y$ e também $\exists xy$ abrevia $\exists x\exists y$._

9. $\exists xp\left(x\right),\forall xp\left(x\right)\to q\left(x\right)⊢\exists xq\left(x\right)$
10. $\forall xp\left(x\right)⊣⊢\forall yp\left(y\right)$
11. $\exists xp\left(x\right)⊣⊢\exists yp\left(y\right)$
12. $\forall xyp\left(x,y\right)⊣⊢\forall yxp\left(x,y\right)$
13. $\exists xyp\left(x,y\right)⊣⊢\exists yxp\left(x,y\right)$
14. $\exists xp\left(x\right)⊣⊢\exists xyp\left(x\right)\wedge p\left(y\right)$
15. $\exists x\forall yp\left(x,y\right)⊢\forall y\exists xp\left(x,y\right)$
16. $\forall xp\left(x\right)⊣⊢\neg \exists x\neg p\left(x\right)$
17. $\exists xp\left(x\right)⊣⊢\neg \forall x\neg p\left(x\right)$

Seja $s$ uma fórmula sem variáveis livres e onde não ocorre $x$.

18. $\forall xs\to p\left(x\right)⊣⊢s\to \forall xp\left(x\right)$
19. $\forall xs\wedge p\left(x\right)⊣⊢s\wedge \forall xp\left(x\right)$
20. $\forall xs\vee p\left(x\right)⊣⊢s\vee \forall xp\left(x\right)$
21. $\exists xs\vee p\left(x\right)⊣⊢s\vee \exists xp\left(x\right)$
22. $\exists xs\wedge p\left(x\right)⊣⊢s\wedge \exists xp\left(x\right)$
23. $\exists x\left(p\left(x\right)\to s\right)⊣⊢\left(\forall xp\left(x\right)\right)\to s$
24. $\forall x\left(p\left(x\right)\to s\right)⊣⊢\left(\exists xp\left(x\right)\right)\to s$

Introdução da Igualdade: ${=}^{+}$.

25. Se em $t$ não ocorrem variáveis, $⊢\exists xx=t$
26. $⊢\exists xx=x$

Eliminação da Igualdade: ${=}^{-}$.

27. $⊢\forall xx=x$
28. $⊢\forall xyx=y\to y=x$
29. $⊢\forall xyz\left(x=y\wedge y=x\right)\to x=z$
30. $⊢\forall xyuv\left(x=u\wedge y=v\right)\to \left(r\left(x,y\right)\leftrightarrow r\left(u,v\right)\right)$
31. $⊢\forall xyuv\left(x=u\wedge y=v\right)\to \left(f\left(x,y\right)=f\left(u,v\right)\right)$
32. $p\left(a\right)⊣⊢\exists xx=a\wedge p\left(x\right)$
33. $\forall xp\left(x\right)\to \left(x=a\vee x=b\right),\exists xp\left(x\right)\wedge q\left(x\right)⊢q\left(a\right)\vee q\left(b\right)$
34. $p\left(a\right)⊣⊢\forall xx=a\to p\left(x\right)$
35. $⊢\forall xyz\left(x=y\wedge y=z\right)\to x=y$.

Consequência Semântica

Exercício 7 Senhor dos Anéis $$\begin{array}{ll}\mathcal{U}& \left\{\text{Legolas},\text{Aragorn}\right\}\\ a^v& \left\{\text{Legolas},\text{Aragorn}\right\}\\ b^v& \left\{\text{Legolas}\right\}\\ n^v& \varnothing \\ c^v& \text{Aragorn}\end{array}$$

Use a interpretação acima para determinar das fórmulas seguintes quais são verdadeiras e quais são falsas.

1. $b\left(c\right)$
2. $a\left(c\right)\leftrightarrow \neg n\left(c\right)$
3. $\forall xa\left(x\right)$
4. $n\left(c\right)\to \left(a\left(c\right)\vee b\left(c\right)\right)$
5. $\forall x\neg b\left(x\right)$
6. $\exists xa\left(x\right)\wedge b\left(x\right)$
7. $\exists xa\left(x\right)\to n\left(x\right)$
8. $\exists xb\left(x\right)\to \forall xa\left(x\right)$

Exercício 8 Alien

$$\begin{array}{ll}\mathcal{U}& \left\{\text{Ripley},\text{Dallas},\text{Kane}\right\}\\ h^v& \left\{\text{Ripley},\text{Dallas},\text{Kane}\right\}\\ w^v& \left\{\text{Ripley},\text{Dallas}\right\}\\ r^v& \left\{\left(\text{Ripley},\text{Dallas}\right),\left(\text{Dallas},\text{Kane}\right),\left(\text{Kane},\text{Ripley}\right)\right\}\\ m^v& \text{Kane}\end{array}$$

Use a interpretação acima para determinar das fórmulas seguintes quais são verdadeiras e quais são falsas.

1. $\exists xr\left(x,m\right)\wedge r\left(m,x\right)$
2. $\forall xr\left(x,m\right)\vee r\left(m,x\right)$
3. $\forall xh\left(x\right)\leftrightarrow w\left(x\right)$
4. $\forall xr\left(x,m\right)\to w\left(x\right)$
5. $\forall xw\left(x\right)\to \left(h\left(x\right)\wedge w\left(x\right)\right)$
6. $\exists xr\left(x,x\right)$
7. $\exists xyr\left(x,y\right)$
8. $\forall xyr\left(x,y\right)$
9. $\forall xyr\left(x,y\right)\vee r\left(y,x\right)$
10. $\forall xyz\left(r\left(x,y\right)\wedge r\left(y,z\right)\right)\to r\left(x,z\right)$

Exercício 9 Mostre que as seguintes relações $\models$ estão erradas, construindo interpretações onde as hipóteses são verdadeiras a conclusão falsa:

1. $\forall xp\left(x\right)\to q\left(x\right)\models \exists xq\left(x\right)$
2. $\forall xp\left(x\right)\to q\left(x\right),\forall xp\left(x\right)\to r\left(x\right)\models \exists xq\left(x\right)\wedge r\left(x\right)$
3. $\exists xp\left(x\right)\to q\left(x\right)\models \exists xp\left(x\right)$
4. $p\left(a\right),p\left(b\right),p\left(c\right)\models \forall xp\left(x\right)$
5. $p\left(a,b\right),\exists xp\left(x,a\right)\models p\left(b,a\right)$
6. $\exists xp\left(x\right)\wedge q\left(x\right),\exists xq\left(x\right)\to \exists xr\left(x\right)\models \exists xp\left(x\right)\wedge r\left(x\right)$
7. $\forall xp\left(x,a\right),\forall xp\left(a,x\right)\models \forall xp\left(x,x\right)$
8. $\exists xp\left(x\right)\wedge q\left(x\right),\exists x\neg p\left(x\right),\exists x\neg q\left(x\right)\models \exists x\neg p\left(x\right)\wedge \neg q\left(x\right)$
9. $p\left(a,b\right)\to \forall xp\left(x,b\right),\exists xp\left(x,b\right)\models p\left(b,b\right)$

Aplicações

Exercício 10 Linguagem das Árvores Genealógicas

• Partindo apenas das relações $\text{Descendente},\text{Coˆnjuge}$ e $\text{Feminina}$, defina as restantes relações e funções $$\begin{array}{c}{\text{Progenitor}\epsilon }_2,{\text{Irm}\epsilon }_2,{\text{Irma˜o}}_2,{\text{Irma˜}}_2,{\text{Descendente}}_2,{\text{Filha}}_2,\\ {\text{Filho}}_2,{\text{Coˆnjuge}}_2,{\text{Marido}}_2,{\text{Esposa}}_2,{\text{Av}\epsilon }_2,{\text{Net}\epsilon }_2,{\text{Ti}\epsilon }_2\end{array}$$
• Consulte a árvore genealógica dos deuses gregos nesta página da wikipédia e deduza quem são $\epsilon s\text{Net}\epsilon s$ de $\text{Phoebe}$, $\epsilon s\text{Cunhad}\epsilon s$ de $\text{Hestia}$, e $\epsilon s\text{Bisav}\epsilon s$ de $\text{Anteros}$ num sistema lógico adequado (por exemplo, prolog).

Exercício 11 Linguagem dos Conjuntos

Formalize:

1. Um conjunto é subconjunto de outro se e só se todos os elementos do primeiro conjunto são elementos do segundo conjunto.
2. Dois conjuntos são iguais se e só se cada um é subconjunto do outro.
3. Um elemento está na interseção de dois conjuntos se e só se é elemento de ambos os conjuntos.
4. Um elemento está na união de dois conjuntos se e só se é elemento de algum dos conjuntos.

Exercício 12 Linguagem das Listas

1. Formalize as regras das listas.

Formalize, classifique (compatível, contingente, válida, contradição) justificando formalmente, dê exemplos e contra-exemplos das seguintes afirmações e afirmações:

2. $\text{First}\left(\left[x|y\right]\right)=x$ e $\text{Rest}\left(\left[x|y\right]\right)=y$.
3. $\text{Find}\left(a,\left[x|y\right]\right)$ se e só se $a=x$ ou $\text{Find}\left(a,y\right)$.
4. Duas listas são iguais se têm os mesmos elementos nas mesmas posições.
5. Defina a função $\text{Append}\left(x,y\right)$ de acordo com as seguintes regras: $$\begin{array}{rl}\text{Append}\left(\left[\right],z\right)& =z\\ \text{Append}\left(\left[x|y\right],z\right)& =\left[x|\text{Append}\left(y,z\right)\right]\end{array}$$
6. Defina a função comprimento de uma lista, acrescentando a linguagem dos números naturais.
7. Mostre que duas listas iguais têm o mesmo comprimento.
8. Mostre se existem listas diferentes com o mesmo comprimento (e se no domínio existir só um elemento?).
9. Mostre se duas listas que têm os mesmos elementos também têm o mesmo comprimento.