p1-2012.2bGabarito

Prévia do material em texto

UFPE / CIn/ Engenharia da Computação GABARITO 
Lógica para Computação / Primeira Prova - 2012.2 - 26/02/2013 
1. (1,5) Verifique, usando o método dos tableaux analíticos, se a proposição 
 (( P  Q )  R)  ( (P  (Q))  (R)) é uma tautologia. Em caso negativo, 
encontre uma valoração que a refute. 
 
 (( P  Q )  R)  ( (P  (Q))  (R))=0 
 (( P  Q )  R) = 1 
 (P  (Q))  (R)= 0 
(P  (Q)) =1 
(R)= 0 
R=1 
P=1 
(Q) =1 
Q=0 
 
 
 
 
 
 
2. (2,0) Sabemos que muitas vezes ao provar um teorema na matemática da forma 
“A  B” é mais fácil usar a contrapositiva: “B  A” . Prove, usando dedução 
natural que essas duas fórmulas são equivalentes. Ou seja, você vai provar que i) 
(A  B)  (B  A) e ii) (B  A)  (A  B). Uma dessas fórmulas não é 
aceita pela lógica intuicionista. Qual delas? Por quê? 
 
i) [A] [AB] 
 B [B] 
 
 F 
 A 
 
 BA 
 
 (A  B)  (B  A) 
 
 
 
ii) [B] [BA] 
 A [A] 
 
 F 
 B 
 
 AB 
 
 (B  A)  (A  B) 
 
 
 
 
R=1 Aberto 
PQ=0 
P=0 X Q=0 Aberto 
 
Não é uma tautologia, pois 
existem ramos abertos. Uma 
valoração que refute a fórmula: 
R=1, P=1 e Q=0 
A segunda não é aceita pela 
lógica intuicionística porque 
usa a redução ao absurdo 
clássica. De B chega-se ao 
Falso e deduz-se B. 
 
3. (2,5) Verifique usando resolução e cálculo de sequentes se: 
 R, P  ((R)  Q) Ⱶ P  (Q  R) 
 
 
 
Resolução: Conjunto de cláusulas: { R, PRQ, P, QR } 
 R e QR = Q 
 PRQ e Q = PR 
 PR e P = R 
 R e R = cláusula vazia. 
 
Cálculo de sequentes: 
 
 R├ R 
R,R├ Q├ Q 
 P├P R, RQ ├ Q 
 R, P(RQ), P ├ Q R├ R 
 R,R, P(RQ), P ├ QR 
 R, P(RQ), P ├ QR 
R, P(RQ), P ├ P (QR) 
 
 
4. (1,5) Considere P como o conjunto das cadeias binárias nas quais a quantidade 
de zeros é o dobro da quantidade de uns. 
a) Dê uma definição indutiva para P e identifique o conjunto base (i.e. X) 
da geração indutiva e o conjunto de funções geradoras (i.e. F). 
ANULADA 
b) Descreva em poucas palavras quais são o menor e o maior conjunto 
indutivo sob X e F. 
Menor conjunto é o P e o maior é o conjunto de todas as cadeias 
binárias. 
c) O conjunto definido em (a) é livremente gerado? Justifique. 
 
5. (1,0) Um meio subtrator com entradas A, B produz saídas D (a diferença) e U (o 
underflow) conforme a tabela-verdade: 
 
A B D U 
V V F F 
V F V F 
F V V V 
F F F F 
 
Ache as proposições que definem D e U em função de A e B. 
D = (AB) e U = A  B 
 
 
6. (1,5) Para cada uma das afirmações abaixo, diga se é verdadeira ou falsa. 
(Atenção: uma resposta errada anula uma certa). 
a) V Em um dado sistema dedutivo X temos a garantia de construir as provas 
de modo que não haja falácias. Entretanto, alguns teoremas não podem ser 
provados. Isso significa que X é correto, porém não é completo. 
b) F Não é possível termos uma fórmula A da lógica proposicional que seja 
refutável e satisfatível ao mesmo tempo. 
c) V Se  |=  então    |= . Onde  e  são conjuntos de proposições 
e  uma poposição. 
d) F Dada uma proposição  e um conjunto de proposições , se  |=  
então   {} é satisfatível.. 
e) F Se A  B é uma tautologia e A é satisfatível então B é uma tautologia. 
f) V Durante o procedimento de normalização no sistema de dedução 
natural fórmulas máximas são retiradas. Fórmulas máximas são o resultado 
de uma regra de introdução e ao mesmo tempo premissa maior de uma 
regra de eliminação do mesmo conectivo.