p1-2012.2aGabarito

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  (R))  (Q)) é uma tautologia. Em caso negativo, 
encontre uma valoração que a refute. 
 
(( P  Q )  R)  ( (P  (R))  (Q))=0 
(( P  Q )  R)=1 
( (P  (R))  (Q))=0 
 (P  (R)) = 1 
(Q)=0 
Q=1 
P=1 
(R)=1 
R=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 X 
Q=0 X 
 
P=0 X 
PQ=0 
É uma tautologia, pois todos os 
ramos estão fechados. Não 
existe valoração que refute a 
fórmula. 
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ásulas: { 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 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 que possuem a mesma 
quantidade de zeros e 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). 
 Def. Indutiva: 
 A cadeia vazia P 
 Se x P então 01x, 10x,0x1, 1x0 e xx também P. 
 Conjunto base B={} 
 Funções geradoras: f1(x)=01x, f2(x)= 10x, f3(x)= 0x1, f4(x)= 1x0, f5(x)= xx 
 
b) Descreva em poucas palavras quais são o menor e o maior conjunto 
indutivo sob X e F. 
O menor conjunto é o próprio P e o maior é o conjunto de todas as 
cadeias binárias. 
 
c) O conjunto definido em (a) é livremente gerado? Justifique. 
Não pois existem cadeias que podem se geradas de modo diferente. Por 
exemplo f3() = 01 = f1() 
 
5. (1,0) Um meio somador com entradas A, B produz saídas S (a soma) e C (o 
carry) conforme a tabela-verdade: 
 
A B S C 
V V F V 
V F V F 
F V V F 
F F F F 
 
Ache as proposições que definem S e C em função de A e B. 
 
S= (AB) e C= 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) F 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 é completo, porém não é correto. 
b) V É 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 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 aquelas com o 
maior número de subfórmulas na derivação. 
e) F Dada uma proposição  e um conjunto de proposições , se  |=  então 
  {} é satisfatível.. 
f) F Se A  B é uma tautologia e A é satisfatível então B é uma tautologia.