exercicio-2

Prévia do material em texto

Lo´gica Aplicada a` Computac¸a˜o
Vivek Nigam
Exerc´ıcio 2
Exerc´ıcio 2-1. (dado em sala de aula!) Prove usando induc¸a˜o que para qualquer termo t e
substituic¸o˜es σ e τ temos que (tσ)τ = t(στ).
Exerc´ıcio 2-2. Um nu´mero primo e´ um nu´mero natural n tal que na˜o existem dois nu´mero
naturais diferentes de 1 cujo produto e´ igual a n. Defina uma interpretac¸a˜o I e uma fo´rmula F tal
que a fo´rmula abaixo e´ verdadeira:
∀x.(p(x) ⇔ F )
onde pI = {n | n e´ primo}.
Exerc´ıcio 2-3. Uma lo´gica e´ monotoˆnica se quando F1, . . . , Fn � G, enta˜o F1, . . . , Fn, Fn+1 � G.
Prove que a lo´gica de primeira ordem e´ monotoˆnica.
Exerc´ıcio 2-4. (dado em sala de aula!) Considere as fo´rmulas
∀x.∃y.F e ∃y.∀x.F
Essas duas fo´rmulas sa˜o equivalentes para qualquer fo´rmula F? Caso afirmativo prove, caso nega-
tive encontre uma interpretac¸a˜o que modele uma, mas na˜o a outra.
Exerc´ıcio 2-5. Prove que as regras ∀R (e ∃L) na˜o sa˜o corretas se a varia´vel usada no lugar da
varia´vel quantificada na˜o for nova, i.e., aparecer na conclusa˜o da regra.
Exerc´ıcio 2-6. (dado em sala de aula!) Explique o que diz o teorema de eliminac¸a˜o de cortes
e quais as suas consequeˆncias.