p1-2011.2

Prévia do material em texto

Universidade Federal de Pernambuco (UFPE)
Centro de Informa´tica (CIn) - Graduac¸a˜o em Engenharia da Computac¸a˜o
Lo´gica para Computac¸a˜o (IF673)
2o Semestre de 2011 - 1a Prova - 06 de Outubro de 2011
1. (1,5) Defina indutivamente o conjunto de todas as cadeias bina´rias que teˆm um
tamanho ı´mpar, identificando: (i) base da induc¸a˜o; (ii) func¸a˜o(o˜es) geradora(s);
(iii) maior conjunto indutivo. Diga (argumentando apropriadamente) se o conjunto
definido e´ livremente gerado.
2. (2,0) Mostre, por induc¸a˜o, que em toda fo´rmula A da lo´gica proposicional, a
quantidade de subfo´rmulas e´ no ma´ximo 2n+ 1, onde n e´ o nu´mero de conectivos
de A. (Obs.: Defina recursivamente as func¸o˜es necessa´rias para a formalizac¸a˜o do
problema)
3. (1,0) Prove que, para todo conjunto Γ de proposic¸o˜es, e toda proposic¸a˜o ϕ,
Γ ∪ {ϕ} e´ inconsistente se e somente se Γ |= ¬ϕ.
4. (3,0)
4.1) Verifique, usando (i) me´todo da resoluc¸a˜o; (ii) deduc¸a˜o natural se:
A→ B |= (C ∨A) → (C ∨B).
4.2) Uma fo´rmula ϕ e´ dita independente de um conjunto Γ de fo´rmulas se Γ 6|= ϕ
e Γ 6|= ¬ϕ. Determine, usando tableux analı´tico se A → B e´ independente de
{A→ (C ∧ ¬B), (C ∧ ¬B) → A, B → C}.
5. (1,5) Examine a seguinte a´rvore de prova em deduc¸a˜o natural e diga se esta´
na forma normal. Em caso negativo, identifique as redundaˆncias (mostrando em
cada caso qual(is) e´(sa˜o) a(s) fo´rmula(s) ma´xima(s)), e aplique o procedimento de
normalizac¸a˜o para obter sua forma normal:
[A ∧B]
A
[A ∧B]
B
A ∧B
A
[A]
A ∨ C [(A ∨ C) → B]
B
A→ B
B
((A ∨ C) → B) → B
(A ∧B) → (((A ∨ C) → B) → B)
6. (1,0)
6.1) Explique o teorema da extensa˜o homomo´rfica u´nica, mostrando a sua aplicac¸a˜o
na lo´gica proposicional.
6.2) Que propriedade um sistema dedutivo deve ter para garantir que na˜o haja
deduc¸o˜es de fo´rmulas inva´lidas? Explique como definimos formalmente essa pro-
priedade.
EXTRA (1,0) (SOMENTEPARAQUEMFALTOUUMAMINI-PROVA)
Use induc¸a˜o para mostrar que para toda fo´rmula A da lo´gica proposicional, o posto
de A e´ no ma´ximo igual a` quantidade de subfo´rmulas de A.