Lista De Exercicios lógica Para Computação

Exerc´ıcios

Obede¸ca `a seguinte seq¨uˆencia de prioridade ao fazer exerc´ıcios para a prova: primeiro os exerc´ıcios

da apostila, depois exerc´ıcios os marcados com (*) abaxio e, se houver tempo, os outros exerc´ıcios

desta lista.

1. (*) O que ´e uma linguagem de primeira ordem ?

2. Cite uma proposi¸c˜ao que pode ser expressa na l´ogica de primeira ordem mas n˜ao no c´alculo

proposicional.

3. Se levarmos a defini¸c˜ao de linguagem de primeira ordem estritamente, ´e 8x P(x) uma f´ormula

v´alida ?

4. (*) Explique o que ´e: a) uma meta-vari´avel; b) uma meta-f´ormula; c) um meta-teorema e d)

um esquema de prova.

5. (*) O que ´e uma teoria de primeira ordem.

6. (*) Quando dizemos que A ´e uma f´ormula, isto significa que A n˜ao possui vari´aveis livres ?

Quando dizemos que A(x) ´e uma f´ormula com vari´avel livre x, isto significa que x ´e a ´unica vari´avel

livre ?

7. Crie um conjunto de f´ormulas l´ogicas que caracterizem um conjunto de times de futebol qualquer

que est´a disputando um campeonato. N˜ao fa¸ca f´ormulas espec´ıficas que sirvam, por exemplo,

apenas para os times nacionais mais importantes.

8. Explique a frase: “um conjunto de f´ormulas l´ogicas comprimem informa¸c˜oes sobre uma parte

do mundo real”. Na sua explica¸c˜ao, explique porque as dedu¸c˜oes que podem ser feitas utilizando

as f´ormulas permitem comprimir uma grande quantidade de informa¸c˜ao em poucas f´ormulas.

9. (*) Fa¸ca um conjunto de f´ormulas