Prova de Lógica Aplicada à Computação

Prévia do material em texto

— Escreva o seu nome e nu´mero de matr´ıcula em cada pa´gina da prova —
Prova de Lo´gica Aplicada a` Computac¸a˜o
Vivek Nigam
A prova e´ individual e deve ser respondida sem consulta a qualquer material.
Questa˜o 1.
1. Construa a tabela verdade da fo´rmula proposicional F abaixo:
((p ∨ q)⇒ (p ∧ q))⇒ q
2. F e´ uma tautologia? Justifique a sua resposta.
3. Existe uma interpretac¸a˜o que falsifica F? Caso afirmativo, construa esta interpretac¸a˜o.
Questa˜o 2. Prove formalmente que para todas as fo´rmulas proposicionais F e G, se F e´
equivalente a ¬G e F e´ satisfat´ıvel, mas na˜o uma tautologia, enta˜o G e´ satisfat´ıvel, mas na˜o
uma tautologia.
Dica: Use a notac¸a˜o de interpretac¸o˜es, por exemplo, I � H, onde I e´ uma interpretac¸a˜o
e H e´ uma fo´rmula.
Questa˜o 3. Considere a fo´rmula abaixo:
F = (p⇒ (q ⇒ r))⇒ ((p⇒ q)⇒ (p⇒ r))
1. Transforme em forma normal de negac¸a˜o a fo´rmula ¬F ;
2. Transforme em forma normal disjuntiva a fo´rmula ¬F ;
3. Prove que F e´ uma tautologia usando o me´todo de resoluc¸a˜o;
Questa˜o 4. Prove usando deduc¸a˜o natural que a fo´rmula proposicional abaixo e´ uma
tautologia:
(p⇒ (q ⇒ r))⇒ ((p⇒ q)⇒ (p⇒ r))
Questa˜o 5. Considere a interpretac¸a˜o I que interpreta os predicados p/1 e q/1 e a func¸a˜o
f/1 conforme descrito abaixo:
• O domı´nio de I e´ o conjunto dos nu´meros naturais N;
• pI = {n | n ∈ N e n e´ ı´mpar};
• qI = {0}
1
— Escreva o seu nome e nu´mero de matr´ıcula em cada pa´gina da prova —
• f I(n) =
{
n− 2 se n ≥ 2
0 caso contra´rio
Ache uma fo´rmula satisfat´ıvel F tal que I e´ um modelo da fo´rmula
∀x.[F ⇒ p(f(x))]
Justifique a sua resposta.
Questa˜o 6. Prove usando o Ca´lculo de Sequentes que a seguinte fo´rmula de primeira
ordem e´ uma tautologia:
∀x∀z[{[p(x)⇒ (∃y.q(y))] ∧ p(x) ∧ [(∃y.q(y))⇒ r(z)]} ⇒ r(z)]
Questa˜o Boˆnus. Dizemos que uma lo´gica e´ monotoˆnica se o seguinte e´ sempre va´lido: se
G e´ uma consequeˆncia lo´gica de um conjunto de fo´rmulas F1, . . . , Fn, enta˜o G tambe´m e´ uma
consequeˆncia lo´gica do conjunto de fo´rmulas F1, . . . , Fn, H, onde H e´ uma fo´rmula qualquer.
Ou seja em nossa notac¸a˜o:
Se F1, . . . , Fn � G enta˜o F1, . . . , Fn, H � G
Prove que a lo´gica de primeira ordem e´ monotoˆnica.
2