UNIVERSIDADE FEDERAL DE
UBERLÂNDIA
Faculdade de Ciência da Computação
Disciplina : Lógica para Ciência da Computação 2 - 20 Semestre 2005
Professora : Sandra Aparecida de Amo
Lista de Exercı́cios no 3
EXERCÍCIOS SOBRE MÉTODO AXIOMÁTICO
Seja F uma fórmula cujas variáveis livres são {x1 ,x2 ,...,xn }. Uma interpretação I é chamada
um modelo de F se :
< x1 ← a1 >< x2 ← a2 > ... < xn ← an > I(F ) = V
para quaiquers a1 ,...,an ∈ U , onde U = dominio de I.
1. Seja F = R(x). Dê um modelo de F e uma interpretação que satisfaz F mas que não é
modelo de F .
2. Seja R um sı́mbolo de predicado binário. Dê um modelo da fórmula :
R(x,y) → R(y,x)
3. Mostre que a regra da Generalização é uma regra válida no sistema axiomático Par. Para
isto, você terá que mostrar que :
se I é modelo da fórmula A(x) então I é modelo da fórmula ∀xA(x).
4. Seja I uma interpretação tal que I(A(x)) = T. É verdade que I(∀xA(x)) = T? Se sua resposta for negativa, você acha que existe uma contradição com o item anterior? Explique.
5. Exercı́cio 2 página 230, itens (e),(f), (h), (l).
Uma fórmula F é consequência lógica de um conjunto de fórmulas Γ se todo modelo de
Γ é modelo de F .
Repare que utilizamos a palavra modelo e não interpretação.
6. Demonstre o Teorema da Correção em sua verso forte : se F é dedutivel do conjunto Γ de
fórmulas (Γ ` F ) então F é consequência lógica de Γ.
Mostre por indução no comprimento da prova Γ ` F , da mesma maneira como demonstramos o Teorema da Dedução em sala de aula.
1
7. Considere a seguinte regra de inferência:
Se A(x) então ∃xA(x).
(a) Mostre que esta regra é válida, isto é, se I é modelo de A(x) então I é modelo de
∃xA(x).
Conclua que A(x) ` ∃xA(x).
(b) Seja I uma interpretação tal que I(A(x)) = T. É verdade que I(∃xA(x)) = T? Veja
que sua resposta não depende em nada da resposta do item anterior !
8. Considere a seguinte regra de inferência:
Se ∀xA(x) então A(x).
(a) Mostre que esta regra é válida, isto é, se I é modelo de ∀xA(x) então I é modelo
de A(x).
(b) Seja I uma interpretação tal que I(∀xA(x)) = T. É verdade que I(A(x)) = V? Veja
que sua resposta não depende em nada da resposta do item anterior !
(c) Suponha que F e G são duas fórmulas tais que : toda interpretação satisfazendo G
também satisfaz G. Mostre que todo modelo satisfazendo F também satisfaz G.
9. Considere a seguinte regra de inferência:
Se ∃xA(x) então A(x).
(a) Esta regra é válida? Justifique sua resposta.
(b) Seja I uma interpretação tal que I(∃xA(x)) = T. É verdade que I(A(x)) = T? Veja
que sua resposta não depende em nada da resposta do item anterior !
10. Considere as seguintes regras válidas (cuja demonstração de validez foi dada nos exercı́cios
anteriores) :
(a) Se ∀xA(x) então A(x).
(b) Se A(x) então ∃xA(x).
Deduza estas regras no sistema axiomático Pa. Pelo Teorema da Completude você tem
certeza de que existe uma tal dedução. Justifique esta última frase.
2