lista3Gab inf1009 PUCRIO Logica

Prévia do material em texto

Lógica para Computação
2016.1 – Lista 3
Profs. Cecilia Englander e Guilherme Lima
1. Verifique, através de tableaux, se as seguintes afirmações são verdadeiras ou falsas. Justifique sua resposta.
(a) A |= A→B
Solução: Falsa. Pelo tableaux abaixo, qualquer valoração v tal que v(A) = V e v(B) = F falsifica a fór-
mula A→ (A→B). Logo A 6|= A→B .
F(A→ (A→B))X1
V(A)
F(A→B)X2
V(A)
F(B)
(b) B |= A→B
Solução: Verdadeira. Pelo tableaux abaixo, não existe valoração que falsifica a fórmula B → (A → B).
Logo B |= A→B .
F(B→ (A→B))X1
V(B)
F(A→B)X2
V(A)
F(B)
×
(c) |= (A∨B)→ (A→¬B)
Solução: Falsa. Pelo tableaux abaixo, qualquer valoração v tal que v(A)= V e v(B)= F falsifica a fórmula.
Logo 6|= (A∨B)→ (A→¬B).
F((A∨B)→ (A→¬B))X1
V(A∨B)X2
F(A→¬B)X3
V(A)
F(A)
×
V(¬B)X4
F(B)
V (B)
F(A) V(¬B)X5
F(B)
×
(d) |= ((A∨B)∧¬A)→¬B
Solução: Falsa. Pelo tableaux abaixo, qualquer valoração v tal que v(A) = F e V (B) = V falsifica a fór-
mula. Logo 6|= ((A∨B)∧¬A)→¬B .
F(((A∨B)∧¬A)→¬B)X1
V((A∨B)∧¬A)X3
F(¬B)X2
V(B)
V(A∨B)X5
V(¬A)X4
F(A)
V(A)
×
V(B)
(e) |= (A∨¬B)→ (B ∧¬A)
Solução: Falsa. Pelo tableaux abaixo, qualquer valoração v tal que v(A) = V ou v(B) = F falsifica a fór-
mula. Logo 6|= (A∨¬B)→ (B ∧¬A).
F((A∨¬B)→ (B ∧¬A))X1
V(A∨¬B)X2
F(B ∧¬A)X4
V(A)
F(B) F(¬A)X5
V(A)
V(¬B)X3
F(B)
F(B) F(¬A)X6
V(A)
(f) B ∧¬A |= A∨¬B
Solução: Falsa. Pelo tableaux abaixo, qualquer valoração v tal que v(A) = F e v(B) = V falsifica a fór-
mula B ∧¬A→ A∨¬B . Logo B ∧¬A 6|= A∨¬B .
F(B ∧¬A→ A∨¬B)X1
V(B ∧¬A)X2
F(A∨¬B)X4
V(B)
V(¬A)X3
F(A)
F(A)
F(¬B)X5
V(B)
(g) A→B |= A∨B
Solução: Falsa. Pelo tableaux abaixo, qualquer valoração v tal que v(A) = F e v(B) = F falsifica a fór-
mula (A→B)→ (A∨B). Logo A→B 6|= A∨B .
F((A→B)→ (A∨B))X1
V(A→B)X3
F(A∨B)X2
F(A)
F(B)
F(A) V(B)
×
(h) A∧B ≡ A→B
Solução: Falsa. Pelo tableaux abaixo, qualquer valoração v tal que v(A)= F falsifica a fórmula (A∧B)↔
(A→B). Logo A∧B 6≡ A→B .
F(((A∧B)→ (A→B))∧ ((A→B)→ (A∧B)))X1
F((A∧B)→ (A→B))X2
V(A∧B)X4
F(A→B)X5
V(A)
V(B)
V(A)
F(B)
×
F((A→B)→ (A∧B))X3
V(A→B)X6
F(A∧B)X7
F(A)
F(A) F(B)
V(B)
F(A) F(B)
×
(i) |= ((A→B)∨ (B→ A))→ (C →C )
Solução: Verdadeira. Pelo tableaux abaixo, não existe valoração que falsifica a fórmula. Logo |= ((A→
B)∨ (B→ A))→ (C →C ).
F(((A→B)∨ (B→ A))→ (C →C ))X1
V((A→B)∨ (B→ A))
F(C →C )X2
V(C )
F(C )
×
(j) (A∧B)≡¬(A→¬B)
Solução: Verdadeira. Pelo tableaux abaixo, não existe valoração que falsifica a fórmula (A∧B)↔¬(A→
¬B). Logo A∧B ≡¬(A→¬B).
F(((A∧B)→¬(A→¬B))∧ (¬(A→¬B)→ (A∧B)))X1
F((A∧B)→¬(A→¬B))X2
V(A∧B)X4
F(¬(A→¬B))X5
V(A)
V(B)
V(A→¬B)
F(A)
×
V(¬(B))X6
F(B)
×
F(¬(A→¬B)→ (A∧B))X3
V(¬(A→¬B))X7
F(A∧B)X10
F(A→¬B)X8
V(A)
F(¬B)X9
V(B)
F(A)
×
F(B)
×
(k) (A→C )∨ (B→C ) |= (A∨B)→C
Solução: Falsa. Pelo tableaux abaixo, qualquer valoração v tal que v(A)= F, v(B)= V e v(C )= F falsifica
a fórmula ((A→C )∨ (B→C ))→ ((A∨B)→C ). Logo (A→C )∨ (B→C ) 6|= (A∨B)→C .
F(((A→C )∨ (B→C ))→ ((A∨B)→C ))X1
V((A→C )∨ (B→C ))X3
F((A∨B)→C )X2
V(A∨B)X6
F(C )
V(A→C )X4
F(A)
V(A)
×
V(B)
V(C )
×
V(B→C )X5
F(B)
V(A) V(B)
×
V(C )
×
(l) (¬A∨B)∧ (A∨¬B) |= ¬((A→B)→¬(B→ A))
Solução: Verdadeira. Pelo tableaux abaixo, não existe valoração que falsifica a fórmula ((¬A∨B)∧ (A∨
¬B))→¬((A→B)→¬(B→ A)). Logo (¬A∨B)∧ (A∨¬B) |= ¬((A→B)→¬(B→ A)).
F(((¬A∨B)∧ (A∨¬B))→¬((A→B)→¬(B→ A)))X1
V((¬A∨B)∧ (A∨¬B))X2
F(¬((A→B)→¬(B→ A)))X3
V(¬A∨B)X8
V(A∨¬B)X11
V((A→B)→¬(B→ A))X4
F(A→B)X5
V(A)
F(B)
V(¬A)X9
F(A)
×
V(B)
×
V(¬(B→ A))X6
F(B→ A)X7
V(B)
F(A)
V(¬A)X10
F(A)
V(A)
×
V(¬B)X12
F(B)
×
V(B)
V(A)
×
V(¬B)X13
F(B)
×
(m) |= A→ (((B ∧C )∧C )→ (D→ (A→B)∧ (A→D)))
Solução: Verdadeira. Pelo tableaux abaixo não existe valoração que falsifica a fórmula.
Logo |= A→ (((B ∧C )∧C )→ (D→ (A→B)∧ (A→D)))
F(A→ (((B ∧C )∧C )→ (D→ (A→B)∧ (A→D))))X1
V(A)
F(((B ∧C )∧C )→ (D→ (A→B)∧ (A→D)))X2
V((B ∧C )∧C )X3
F(D→ (A→B)∧ (A→D))X5
V(B ∧C )X4
V(C )
V(B)
V(C )
V(D)
F((A→B)∧ (A→D))X6
F(A→B)X7
V(A)
F(B)
×
F(A→D)X8
V(A)
F(D)
×
(n) |= (A→ (B→C ))→ ((A→B)→ (A→C ))
Solução: Verdadeira. Pelo tableaux abaixo, não existe valoração que falsifica a fórmula. Logo |= (A→
(B→C ))→ ((A→B)→ (A→C )).
F((A→ (B→C ))→ ((A→B)→ (A→C )))X1
V(A→ (B→C ))X4
F((A→B)→ (A→C ))X2
V(A→B)X6
F(A→C )X3
V(A)
F(C )
F(A)
×
V(B→C )X5
F(B)
F(A)
×
V(B)
×
V(C )
×
2. Um crime é cometido por uma e somente uma pessoa e há quatro suspeitos: Paulo, Rodrigo, Henrique e Felipe.
Interrogados eles fazem as seguintes declarações:
Felipe: Rodrigo mente quando diz que eu não sou inocente.
Paulo: Rodrigo não é inocente.
Henrique: Eu sou inocente.
Rodrigo: Felipe não é inocente.
Represente em lógica proposicional as sentenças acima. Com base nestas sentenças lógicas, mostre que se o
inspetor usar Tableaux irá concluir que se o Henrique for culpado então somente Felipe fala a verdade. Mostre o
Tableaux que suporta a conclusão do inspetor.
Solução: Usaremos ∗c para “∗ é culpado” e ∗v para “∗ fala a verdade”, em que ∗ é a primeira letra do nome
do suspeito.
Informações dadas na primeira frase do enunciado:
• Há quatro suspeitos: Paulo, Rodrigo, Henrique ou Felipe,
Pc ∨Rc ∨Hc ∨Fc .
• Um crime é cometido por uma e somente uma pessoa:
(Pc → (¬Rc ∧¬Hc ∧¬Fc ))
∧ (Rc → (¬Pc ∧¬Hc ∧¬Fc ))
∧ (Hc → (¬Rc ∧¬Pc ∧¬Fc ))
∧ (Fc → (¬Rc ∧¬Hc ∧¬Pc )) .
Informações dadas pelas falas dos suspeitos (em ordem):
• Hv ↔ (Fc →¬Rv )
• Pv ↔Rc
• Hv ↔¬Hc
• Rv ↔ Fc
Conclusão:
Hc → (Fv ∧¬Pv ∧¬Hv ∧¬Rv ) .
Mostrar que podemos concluir Hc → (Fv ∧¬Pv ∧¬Hv ∧¬Rv ) a partir das informações dadas na questão é o
mesmo que mostrar que a seguinte fórmula é tautologia:(
(Pc ∨Rc ∨Hc ∨Fc )
∧ (Pc → (¬Rc ∧¬Hc ∧¬Fc ))
∧ (Rc → (¬Pc ∧¬Hc ∧¬Fc ))
∧ (Hc → (¬Rc ∧¬Pc ∧¬Fc ))
∧ (Fc → (¬Rc ∧¬Hc ∧¬Pc ))
∧ (Hv ↔ (Fc →¬Rv ))
∧ (Pv ↔Rc )
∧ (Hv ↔¬Hc )
∧ (Rv ↔ Fc )
)
→ (Hc → (Fv ∧¬Pv ∧¬Hv ∧¬Rv ))
Para ver o tableaux, coloque a fórmula abaixo no provador do site http://www.umsu.de/logik/trees/:
((P_c\lor R_c\lor H_c\lor F_c)
\land(P_c\to (\lnot R_c\land \lnot H_c\land\lnot F_c))
\land(R_c\to (\lnot P_c\land \lnot H_c\land\lnot F_c))
\land(H_c\to (\lnot R_c\land \lnot P_c\land\lnot F_c))
\land(F_c\to (\lnot R_c\land \lnot H_c\land\lnot P_c))
\land(H_v\leftrightarrow (F_c\to \lnot R_v))
\land(P_v\leftrightarrow R_c)
\land(H_v\leftrightarrow\lnot H_c)
\land{(R_v\leftrightarrow F_c))
\to(H_c\to (F_v\land \lnot P_v\land \lnot H_v\land \lnot R_v))
3. Existem duas caixas, A e B. Um aviso na caixa A diz “O aviso na caixa B é falso e o ouro está na caixa B”. Um aviso
na caixa B diz “O aviso na caixa A é verdadeiro e o ouro está na caixa B”. Assumindo que existe ouro em uma das
caixas, qual delas contém o ouro? Justifique sua resposta em termos lógicos.
Solução: Usaremos ∗v para “o aviso na caixa ∗ é verdadeiro” e O∗ para “o ouro está na caixa ∗”. Temos três
premissas: Av ↔ (¬Bv ∧OB ), Bv ↔ (Av ∧OB ), e OA ∨OB (há ouro em uma das caixas). Para mostrar em qual
das caixas está o ouro, precisamos montar dois tableaux:
1. ((Av ↔ (¬Bv ∧OB ))∧ (Bv ↔ (Av ∧OB ))∧ (OA ∨OB ))→ A, e
2. ((Av ↔ (¬Bv ∧OB ))∧ (Bv ↔ (Av ∧OB ))∧ (OA ∨OB ))→B .
Se (1) fechar, não precisamos fazer (2) e concluímos que o ouro está na caixa A. Se (1) não fechar, concluímos
que o ouro não está na caixa A e fazemos (2). Se (2) tableaux também não fechar, então há algo errado! ;)
4. Considere as seguintes informações:
• Se o professor der um teste, então os alunos vão bem ou mal no teste.
• Se os alunos forem bem, então o professor vai achar que o teste estava fácil e ficará frustrado.
• Se os alunos forem mal, então o professor vai achar que os alunos não aprenderam nada de lógica e ficará
frustrado.
Queremos saberse podemos, a partir do texto, concluir que
1. Se o professor der um teste, então o professor ficará frustrado.
2. Se o professor não der um teste, então o professor não ficará frustrado.
Solução: Vamos usar os seguintes símbolos proposicionais:
P : “o professor dá um teste”
F : “o professor fica frustrado”
B : “os alunos vão bem no teste”
L : “os alunos aprenderam lógica”
T : “o teste está fácil”
Formalizando as três informações iniciais temos:
• P→ (B ∨¬B)
• B→ (T ∧F )
• ¬B→ (¬L∧F )
E as possíveis conclusões:
• P→ F
• ¬P→¬F
Precisamos fazer uma tableaux para cada possível conclusão:
• ((P→ (B ∨¬B))∧ (B→ (T ∧F ))∧ (¬B→ (¬L∧F )))→ (P→ F )
• ((P→ (B ∨¬B))∧ (B→ (T ∧F ))∧ (¬B→ (¬L∧F )))→ (¬P→¬F )
O que podemos concluir quando o tableaux fecha?
5. Refaça a lista 2 usando tableaux sempre que possível.
6. Mostre que o conjunto de conectivos {¬,∨} é completo. Ou seja, apresente fórmulas ϕ e ψ contendo apenas os
conectivos ‘¬’ e ‘∨’ tais que ϕ≡α∧β e ψ≡α→β. Justifique sua resposta usando tableaux.
Solução: ϕ=¬(¬α∨¬β) e ψ=¬α∨β, conforme demonstrado abaixo.
F(¬(¬α∨¬β)↔α∧β)X1
F(¬(¬α∨¬β)→α∧β)X2
V(¬(¬α∨¬β))X4
F(α∧β)X8
F(¬α∨¬β)X5
F(¬α)X6
F(¬β)X7
V(α)
V(β)
F(α)
×
F(β)
×
F(α∧β→¬(¬α∨¬β))X3
V(α∧β)X10
F(¬(¬α∨¬β))X9
V(¬α∨¬β)X11
V(α)
V(β)
V(¬α)X12
F(α)
×
V(¬β)X13
F(β)
×
F((¬α∨β)↔ (α→β))X1
F((¬α∨β)→ (α→β))X2
V(¬α∨β)X5
F(α→β)X4
V(α)
F(β)
V(¬α)X6
F(α)
×
V(β)
×
F((α→β)→ (¬α∨β))X3
V(α→β)X9
F(¬α∨β)X7
F(¬α)X8
F(β)
V(α)
F(α)
×
V(β)
×
7. Seja ‘|’ (leia-se “nand”) um conectivo binário tal que α | β ≡ ¬(α∧β). Mostre que o conjunto { | } contendo ape-
nas esse conectivo é completo. Ou seja, apresente fórmulas ϕ1, ϕ2, ϕ3, ϕ4 contendo apenas o conectivo ‘|’ tais
que ϕ1 ≡¬α, ϕ2 ≡α∧β, ϕ3 ≡α∨β, e ϕ4 ≡α→β. Justifique a sua resposta usando tableaux.
Solução:
ϕ1 =α |α≡¬(α∧α)≡¬α, conforme demonstrado abaixo.
F(¬(α∧α)↔¬α)X1
F(¬(α∧α)→¬α)X2
V(¬(α∧α))X3
F(¬α)X4
F(α∧α)X5
V(α)
F(α)
×
F(α)
×
F(¬α→¬(α∧α))X6
V(¬α)X7
F(¬(α∧α))X8
F(α)
V(α∧α)X9
V(α)
V(α)
×
ϕ2 = (α |β) | (α |β)≡¬(¬(α∧β)∧¬(α∧β))≡α∧β, conforme demonstrado abaixo.
F(¬(¬(α∧β)∧¬(α∧β))↔α∧β)X1
F(¬(¬(α∧β)∧¬(α∧β))→α∧β)X2
V(¬(¬(α∧β)∧¬(α∧β)))X3
F(α∧β)X9
F(¬(α∧β)∧¬(α∧β))X4
F(¬(α∧β))X5
V(α∧β)X6
V(α)
V(β)
F(α)
×
F(α)
×
F(¬(α∧β))X7
V(α∧β)X8
V(α)
V(β)
F(α)
×
F(α)
×
F(α∧β→¬(¬(α∧β)∧¬(α∧β)))X10
V(α∧β)X11
F(¬(¬(α∧β)∧¬(α∧β)))X12
V(α)
V(β)
V(¬(α∧β)∧¬(α∧β))X13
V(¬(α∧β))X14
V(¬(α∧β))
F(α∧β)X15
F(α)
×
F(β)
×
ϕ3 = (α |α) | (β |β)≡¬(¬(α∧α)∧¬(β∧β))≡α∨β, conforme demonstrado abaixo.
F(¬(¬(α∧α)∧¬(β∧β))↔α∨β)X1
F(¬(¬(α∧α)∧¬(β∧β))→α∨β)X2
V(¬(¬(α∧α)∧¬(β∧β)))X3
F(α∨β)X4
F(¬(α∧α)∧¬(β∧β))X5
F(α)
F(β)
F(¬(α∧α))X6
V(α∧α)X7
V(α)
V(α)
×
F(¬(β∧β))X8
V(β∧β)X9
V(β)
V(β)
×
F(α∨β→¬(¬(α∧α)∧¬(β∧β)))X10
V(α∨β)X17
F(¬(¬(α∧α)∧¬(β∧β)))X11
V(¬(α∧α)∧¬(β∧β))X12
V(¬(α∧α))X13
V(¬(β∧β))X14
F(α∧α)X15
F(β∧β)X16
F(α)
F(β)
V(α)
×
V(β)
×
F(β)
V(α)
×
V(β)
×
F(α)
F(β)
V(α)
×
V(β)
×
F(β)
V(α)
×
V(β)
×
ϕ4 = ((α |α) | (α |α)) | (β |β)≡¬(¬(¬(α∧α)∧¬(α∧α))∧¬(β∧β))≡α→β, conforme demonstrado abaixo.
F(¬(¬(¬(α∧α)∧¬(α∧α))∧¬(β∧β))↔ (α→β))X1
F(¬(¬(¬(α∧α)∧¬(α∧α))∧¬(β∧β))→ (α→β))X2
V(¬(¬(¬(α∧α)∧¬(α∧α))∧¬(β∧β)))X3
F(α→β)X4
F(¬(¬(α∧α)∧¬(α∧α))∧¬(β∧β))X5
V(α)
F(β)
F(¬(¬(α∧α)∧¬(α∧α)))X7
V(¬(α∧α)∧¬(α∧α))X8
V(¬(α∧α))X9
V(¬(α∧α))
F(α∧α)X10
F(α)
×
F(α)
×
F(¬(β∧β))X11
V(β∧β)X12
V(β)
V(β)
×
F((α→β)→¬(¬(¬(α∧α)∧¬(α∧α))∧¬(β∧β)))X13
V(α→β)X18
F(¬(¬(¬(α∧α)∧¬(α∧α))∧¬(β∧β)))X14
V(¬(¬(α∧α)∧¬(α∧α))∧¬(β∧β))X15
V(¬(¬(α∧α)∧¬(α∧α)))X16
V(¬(β∧β))X17
F(¬(α∧α)∧¬(α∧α))X20
F(β∧β)X19
F(α)
F(β)
F(¬(α∧α))X21
V(α∧α)X22
V(α)
V(α)
×
F(¬(α∧α))X23
V(α∧α)X24
V(α)
V(α)
×
F(β)
V(β)
F(β)
×
F(β)
×
8. Apresente possíveis regras de tableaux para o conectivo nand (|) do exercício anterior.
Solução:
V(α |β)
F(α) | F(β)
F(α |β)
V (α)
V (β)