AP1-2011-1-EXTRA

Prévia do material em texto

Pontos Extra para AP1
Lo´gica para Computac¸a˜o
Davi Romero de Vasconcelos
05 de Outubro de 2011
Lo´gica para Computac¸a˜o Nota pontos
Nome:
1. (2.0) Formalize e solucione o seguinte problema, usando o Sistema de
Deduc¸a˜o Natural ou Tableau Semaˆntico.
(Problema do Crime) Uma pessoa comete um criem e ha´ quatro sus-
peitos: Maria, Joa˜o, Simone e Pedro. Ao serem interrogados eles fazem
as seguintes declarac¸o˜es:
• Maria: Joa˜o e´ o culpado;
• Joa˜o: Pedro e´ o culpado;
• Simone: Eu na˜o sou culpada;
• Pedro: Joa˜o mente quando diz que eu sou culpado.
Sabendo que somente um dos quatro diz a verdade, e´ poss´ıvel, somente
com esses dados saber quem foi o culpado? Caso afirmativo, quem foi o
culpado?
2. (1.0) Sabendo que o conjunto de derivac¸o˜es e´ definido como a seguir, defina
uma func¸a˜o que retorna o conjunto das Hipo´tese (na˜o descartadas) de uma
derivac¸a˜o.
Definic¸a˜o 1. O conjunto de derivac¸o˜es e´ o menor conjunto X tal que
(a) Uma fo´rmula ϕ ∈ LLP e´ uma derivac¸a˜o, i.e. ϕ ∈ X
(b) Se
D
ϕ
,D′
ψ
∈ X, enta˜o
D
ϕ
D′
ψ
ϕ ∧ ψ
∈ X
(c) Se
D
ϕ ∧ ψ ∈ X, enta˜o
D
ϕ ∧ ψ
ϕ
e
D
ϕ ∧ ψ
ψ
∈ X
(d) Se
ϕ
D
ψ
∈ X, enta˜o
[ϕ]
D
ψ
ϕ → ψ
∈ X
(e) Se Dϕ e D
′
ϕ → ψ ∈ X, enta˜o
D
ϕ
D′
ϕ → ψ
ψ
∈ X
(f) Se D⊥ ∈ X, enta˜o
D
⊥
ϕ
∈ X
(g) Se
¬ϕ
D
⊥
∈ X, enta˜o
[¬ϕ]
D
⊥
ϕ
∈ X
1