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\at{x} & x~\text{sabe a combinação do cofre.}\cr E\at{x} & x~\text{é espião.}\cr V\at{x} & x~\text{é vegetariano.}\cr C\at{x,y} & x~\text{confia em}~y.\cr B & \text{Bond, James.}\cr 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\at{a}$
2. $p\at{a} \to q\at{a}$
3. $\forall x~ p\at{x}\to q\at{x}$
4. $p\at{a} \land \del{\forall x~ p\at{x}\to q\at{x} \to q\at{a}}$
5. $\del{p\at{a} \land \forall x~ p\at{x}\to q\at{x}} \to q\at{a}$
6. $\del{p\at{a} \land \forall x~ p\at{x}} \to \del{q\at{x} \to q\at{a}}$

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) \land \exists y~r(x, y)$
   3. $\forall y~ (p(y) \to q(x))$
   4. $\exists x~ (p(x) \lor r(x, y))$
   5. $(\forall x~ p(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) \land \exists y~ r(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) \lor r(x, y))$, a variável $y$ tem uma ocorrência livre.
   5. Na fórmula $(\forall x~p(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 x~ q(x))$
   2. $\exists x~ (p(x) \land \forall y~r(x, y))$
   3. $\forall x~(p(x) \to \exists y~ (q(y) \land 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) \land 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)) \land \forall z~ s(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 y~q(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: $\ndEQU$

1. $p\at{a}, \forall x~p\at{x}\to q\at{x} \vdash q\at{a}$
2. $\neg q\at{a}, \forall x~ p\at{x}\to q\at{x} \vdash \neg p\at{a}$

Introdução Universal: $\ndIQU$.

3. $\forall x~ p\at{x} \to q\at{x}, \forall x~q\at{x} \to r\at{x} \vdash \forall x~\del{p\at{x} \to r\at{x}}$
4. $\forall x~ p\at{x}, \forall x~ p\at{x}\to q\at{x} \vdash \forall x~ q\at{x}$
5. $\forall x~ p\at{x} \land q\at{x} \vdash \forall x~ p\at{x}$
6. $\forall x~ p\at{x} \land q\at{x} \dashv\vdash \forall x~ p\at{x} \land \forall x~ q\at{x}$
7. $\forall x~ p\at{x} \lor q\at{x}, \forall x~ \neg p\at{x}\vdash \forall x~ q\at{x}$

Introdução Existencial: $\ndIQE$.

8. $p\at{a}, \forall x~ p\at{x} \to q\at{x}\vdash \exists x~ q\at{x}$

Eliminação Existencial: $\ndEQE$.

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

9. $\exists x~ p\at{x}, \forall x~ p\at{x} \to q\at{x}\vdash \exists x~ q\at{x}$
10. $\forall x~ p\at{x} \dashv\vdash \forall y~ p\at{y}$
11. $\exists x~ p\at{x} \dashv\vdash \exists y~ p\at{y}$
12. $\forall xy~ p\at{x,y} \dashv\vdash \forall yx~ p\at{x,y}$
13. $\exists xy~ p\at{x,y} \dashv\vdash \exists yx~ p\at{x,y}$
14. $\exists x~ p\at{x} \dashv\vdash \exists xy~ p\at{x} \land p\at{y}$
15. $\exists x\forall y~ p\at{x,y} \vdash \forall y\exists x~ p\at{x,y}$
16. $\forall x~ p\at{x} \dashv\vdash \neg \exists x~ \neg p\at{x}$
17. $\exists x~ p\at{x} \dashv\vdash \neg \forall x~ \neg p\at{x}$

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

18. $\forall x~ s \to p\at{x} \dashv\vdash s \to \forall x~ p\at{x}$
19. $\forall x~ s \land p\at{x} \dashv\vdash s \land \forall x~ p\at{x}$
20. $\forall x~ s \lor p\at{x} \dashv\vdash s \lor \forall x~ p\at{x}$
21. $\exists x~ s \lor p\at{x} \dashv\vdash s \lor \exists x~ p\at{x}$
22. $\exists x~ s \land p\at{x} \dashv\vdash s \land \exists x~ p\at{x}$
23. $\exists x~ \del{p\at{x} \to s} \dashv\vdash \del{\forall x~ p\at{x}}\to s$
24. $\forall x~ \del{p\at{x} \to s} \dashv\vdash \del{\exists x~ p\at{x}}\to s$

Introdução da Igualdade: $\ndIEqual$.

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

Eliminação da Igualdade: $\ndEEqual$.

27. $\vdash \forall x~ x=x$
28. $\vdash \forall xy~ x=y \to y = x$
29. $\vdash \forall xyz~ \del{x=y \land y = x}\to x = z$
30. $\vdash \forall xyuv~ \del{x = u \land y = v} \to \del{r\at{x,y} \liff r\at {u,v}}$
31. $\vdash \forall xyuv~ \del{x = u \land y = v} \to \del{f\at{x,y} = f\at {u,v}}$
32. $p\at{a} \dashv\vdash \exists x~ x = a \land p\at{x}$
33. $\forall x~ p\at{x}\to\del{x = a \lor x = b}, \exists x~ p\at{x}\land q\at{x} \vdash q\at{a} \lor q\at{b}$
34. $p\at{a} \dashv\vdash \forall x~ x = a \to p\at{x}$
35. $\vdash \forall xyz~ \del{x = y \land y = z} \to x = y$.

Consequência Semântica

Exercício 7 Senhor dos Anéis $$ \begin{array}{ll} \cat{U} & \cbr{\lit{Legolas}, \lit{Aragorn}} \cr a^v & \cbr{\lit{Legolas}, \lit{Aragorn}} \cr b^v & \cbr{\lit{Legolas}} \cr n^v & \emptyset \cr c^v & \lit{Aragorn} \cr \end{array} $$

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

1. $b\at{c}$
2. $a\at{c} \liff \neg n\at{c}$
3. $\forall x~ a\at{x}$
4. $n\at{c} \to \del{a\at{c} \lor b\at{c}}$
5. $\forall x~ \neg b\at{x}$
6. $\exists x~ a\at{x} \land b\at{x}$
7. $\exists x~ a\at{x} \to n\at{x}$
8. $\exists x~ b\at{x} \to \forall x~ a\at{x}$

Exercício 8 Alien

$$ \begin{array}{ll} \cat{U} & \cbr{\lit{Ripley}, \lit{Dallas}, \lit{Kane}} \cr h^v & \cbr{\lit{Ripley}, \lit{Dallas}, \lit{Kane}} \cr w^v & \cbr{\lit{Ripley}, \lit{Dallas}} \cr r^v & \cbr{ \del{\lit{Ripley}, \lit{Dallas}}, \del{\lit{Dallas}, \lit{Kane}}, \del{\lit{Kane}, \lit{Ripley}} } \cr m^v & \lit{Kane} \cr \end{array} $$

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

1. $\exists x~ r\at{x, m} \land r\at{m, x}$
2. $\forall x~ r\at{x, m} \lor r\at{m, x}$
3. $\forall x~ h\at{x} \liff w\at{x}$
4. $\forall x~ r\at{x, m} \to w\at{x}$
5. $\forall x~ w\at{x} \to \del{h\at{x} \land w\at{x}}$
6. $\exists x~ r\at{x, x}$
7. $\exists xy~ r\at{x, y}$
8. $\forall xy~ r\at{x, y}$
9. $\forall xy~ r\at{x, y} \lor r\at{y, x}$
10. $\forall xyz~ \del{r\at{x, y} \land r\at{y, z}}\to r\at{x,z}$

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 x~ p\at{x} \to q\at{x} \models \exists x~ q\at{x}$
2. $\forall x~ p\at{x} \to q\at{x}, \forall x~ p\at{x} \to r\at{x} \models \exists x~ q\at{x} \land r\at{x}$
3. $\exists x~p\at{x} \to q\at{x} \models \exists x~p\at{x}$
4. $p\at{a}, p\at{b}, p\at{c} \models \forall x~p\at{x}$
5. $p\at{a,b}, \exists x~ p\at{x, a} \models p\at{b,a}$
6. $\exists x~p\at{x} \land q\at{x}, \exists x~ q\at{x} \to \exists x~ r\at{x} \models \exists x~ p\at{x} \land r\at{x}$
7. $\forall x~p\at{x, a}, \forall x~ p\at{a, x} \models \forall x~ p\at{x, x}$
8. $\exists x~p\at{x} \land q\at{x}, \exists x~ \neg p\at{x}, \exists x~ \neg q\at{x} \models \exists x~ \neg p\at{x} \land \neg q\at{x}$
9. $p\at{a,b} \to \forall x~p\at{x, b}, \exists x~ p\at{x, b} \models p\at{b, b}$

Aplicações

Exercício 10 Linguagem das Árvores Genealógicas

• Partindo apenas das relações $\lit{Descendente}, \lit{Cônjuge}$ e $\lit{Feminina}$, defina as restantes relações e funções $$ \begin{gathered} \neut{Progenitor}_2, \neut{Irm}_2, \lit{Irmão}_2, \lit{Irmã}_2, \lit{Descendente}_2, \lit{Filha}_2, \cr \lit{Filho}_2, \lit{Cônjuge}_2, \lit{Marido}_2, \lit{Esposa}_2, \neut{Av}_2, \neut{Net}_2, \neut{Ti}_2 \end{gathered} $$
• Consulte a árvore genealógica dos deuses gregos nesta página da wikipédia e deduza quem são $\neut{}s~\neut{Net}s$ de $\lit{Phoebe}$, $\neut{}s~\neut{Cunhad}s$ de $\lit{Hestia}$, e $\neut{}s~\neut{Bisav}s$ de $\lit{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. $\fat{First}{\sbr{x|y}} = x$ e $\fat{Rest}{\sbr{x|y}} = y$.
3. $\fat{Find}{a, \sbr{x|y}}$ se e só se $a = x$ ou $\fat{Find}{a, y}$.
4. Duas listas são iguais se têm os mesmos elementos nas mesmas posições.
5. Defina a função $\fat{Append}{x,y}$ de acordo com as seguintes regras: $$ \begin{aligned} \fat{Append}{\sbr{~ }, z} &= z \cr \fat{Append}{\sbr{x | y}, z} &= \sbr{x | \fat{Append}{y,z}} \end{aligned} $$
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.