Respostas de exercícios de lógica computacional

Prévia do material em texto

36 
AULA 11 - RESPOSTAS 
 
1) Demonstrar que os seguintes conjuntos de proposições são inconsistentes deduzindo uma contradição 
para cada um deles: 
a) q → p, ~ (p ˅ r), q ˅ r 
 1. q → p 
 2. ~ (p ˅ r) 
 3. q ˅ r . 
 4. ~ p ∧ ~ r 2: De Morgan 
 5. ~ p 4: Simp 
 6. ~ r 4: Simp 
 7. ~ q 5,1: M.T 
 8. r 7,3: S.D 
 9. ~ r ∧ r 6,8: Conjunção 
 
b) p ˅ ~ q, ~ (q → r), p → r 
 1. p ˅ ~q 
 2. ~ (q → r) 
 3. p → r . 
 4. ~ ( ~ q ˅ r) 2: Condicional 
 5. q ∧ ~ r 4: De Morgan 
 6. q 5: Simp 
 7. ~ r 5: Simp 
 8. ~ p 3,7: M.T 
 9. ~ q 8,1: S.D 
 10. q ∧ ~ q 6,9: Conjunção 
 
 c) ~ (p ˅ q), ~ q → r, ~ r ˅ s, ~ p → ~ s 
 1. ~ ( p v q) 
 2. ~ q → r 
 3. ~ r ˅ s 
 4. ~ p → ~ s . 
 5. ~ p ∧ ~ q 1: De Morgan 
 6. ~ p 5: Simp 
 7. ~ q 5: Simp 
 8. ~ s 4,6: M.P 
 9. ~ r 8,3: S.D 
 10. q 9,2: M.T 
 11. ~ q ∧ q 7,10: Conj. 
 
 
 
 
 
 
 
 37 
 d) p ˅ s → q, q → ~r, t → p, t ∧ r 
 1. p ˅ s → q 
2. q → ~ r 
3. t → p 
4. t ∧ r . 
5. t 4: Simp 
6. r 4: Simp 
7. ~ q 6,2: M.T 
8. p 3,5: M.P 
9. p ˅ s 8: Adição 
10. q 1,9: M.P 
11. ~ q ∧ q 7,10: Conjunção 
 
e) x = y → x < 4, x ≥ 4 v x < z, ~( x< z v x ≠ y) 
1. x = y → x < 4 1. p → q 
2. x > 4 v x < z 2. ~ q ˅ r 
3. ~(x < z v x ≠ y) 3. ~ (r ˅ ~ p) . 
 4. ~ r ∧ p 3: De Morgan 
 5. p 4: Simp 
 6. ~ r 4: Simp 
 7. q 1,5: Simp 
 8. ~ q 2,6: S.D 
 9. ~ q ∧ q 7,8: Conj 
 
 
f) x = 0 ↔ x + y = y, x > 1 ∧ x = 0, x + y = y → x ≤ 1 
 1. x = 0 ↔ x + y = y 1. p ↔ q 
 2. x > 1 ∧ x = 0 2. r ∧ p 
 3. x + y = y → x ≤ 1 3. q →~r 
 4. ( p → q) ∧ (q → r) 1: Bicondicional 
 5. p → q 4: Simp 
 6. r 2: Simp 
 7. P 2: Simp 
 8. ~ p 3,6: M.T 
 9. q 5,7: M.P 
 10. ~ q ∧ q 8,9: Conj 
 
 
 
 
 
 
 
 38 
g) x = y → x < z, x ≥ z ∧ (x = y v y < z), y < z → x < z 
1. x = y → x < z 1. p → q 
2. x ≥ z ∧ (x = z v y < z) 2. ~ q ∧ ( p ˅ r) 
3. y < z → x < z 3. r → q . 
 4. ~ q 2: Simp 
 5. p ˅ r 2: Simp 
 6. ~ p 1,4: M.T 
 7. r 5,6: S.D 
 8. q 3,7: M.P 
 9. ~ q ∧ q 4,8: Conj 
 
h) x < y → x ≠ y, y > z → z ≥ y, x = y ∧ y > z, x < y ˅ z < y 
1. x < y → x ≠ y 1. p → q 
2. y > z → z ≥ y 2. r → s 
3. x = y ∧ y > z 3. ~q ∧ r 
4. x < y v z < y 4. p ˅ ~s . 
 5. ~ q 3: Simp 
 6. r 3: Simp 
 7. ~ p 1,5: M.T 
 8. s 4,7: M.P 
 9. ~ s 4,7: S.D 
 10. ~ s ∧ s 8,9: Conj. 
 
 
2) Demonstrar que os seguintes conjuntos de proposições são consistentes: 
a) p → q, q → r, ~r ˅ s 
F → V V →V ~V ˅ V V(V) = q, r, s 
 V V F ˅ V V(F) = p 
 V 
b) p → q, ~ q → r, p ˅ r 
V → V, ~ V → V, V ˅ V 
 V F → V V V (V) = p, q , r 
 
c) ~p ˅ ~q, ~p → r, ~r 
~V ˅~F, ~V →, ~F V (V)= p 
 F ˅ V F → F V V (F)= q,r 
 V V 
 
d) p → q, r → q, q → ~s 
V → V V → V V → ~F 
 V V V → V 
 V 
 
V(v) = p , q ,r 
V(F) = s 
 39 
e) x = y → x ≠ y, x , y ˅ x = y, x ≥ y → x < y 
p → ~ p, q, r ˅ p, s → t 
F → ~F V V ˅ F V → V 
F → V V V V(V) = q , r , s , t 
 V V(F) = p 
 
 
 
f) x = 2 ˅ x = 3, x≠2 ˅ x≠3 
p ˅ q, ~p ˅ ~q V(v) = q 
F ˅ V ~F ˅ ~V V(F) = p 
 V V ˅F 
 V 
 
3) Usar a Regra DC (Demonstração condicional) para mostrar que são válidos os seguintes argumentos: 
a) ~r v ~s, q → s | r → ~q 
 
1. ~ r ˅ ~ s 
2. q → s 
3. r . 
4. ~ s 1,3: S.D 
5. ~ q 2,4: M.T 
 
 
b) p → ~q, ~(r ∧ ~p) | q → ~r 
 
1. p → ~q 
2. ~(r ∧ p) 
3. q 
4. ~ r ˅ p 2: De Morgan 
5. ~ p 1,3: M.t 
6. ~ r 4,5: S.D 
 
 
c) r → t, t → ~s, ( r → ~s) → q | p → p ∧ q 
 
1. r → t 
2. t → ~s 
3. (r → ~s) → q 
4. p . 
5. r → ~s 1,2: S.H 
6. q 3,5: M.P 
7. p ∧ q 4,7: Conj 
 
 
 
 40 
d) p → q, r → p, s → r | s → q 
 
1. p → q 
2. r → p 
3. s → r 
4. s 
_______________ 
5. r → q 1,2: S.H 
6. s → q 3,5: S.H 
7. q 4,6: M.P 
 
 
e) ~p, ~r → q, ~s → p | ~( r ∧ s) → q 
 
1. ~p 
2. ~r → q 
3. ~s → p 
4. ~(r ∧ s) 
_________________ 
5. ~r ˅ ~s 4 De Morgan 
6. s 1,3: M.T 
7. ~r 5,6: S.D 
8. q 2,7: M.P 
 
 
f) p → ~q, ~r → q, ~s → ~q | p v ~s → r 
 
1. p → ~q 
2. ~r → q 
3. ~s → ~q 
4. p ˅ ~s 
_________________ 
5. ~q ˅ ~q 1,3,4: D.C 
6. ~q 5: Idempotência 
7. ~r 2,6: M.T 
 
 
g) ~p ˅ ~s, q → ~r, t → s ∧ r | t → ~ ( p ˅ q) 
1. ~p ˅ ~s 
2. q → ~r 
3. t → s ∧ r 
4. t 
__________________ 
5. s ∧ r 3,4: M.P 
6. s 5: Simp 
7. r 5: Simp 
8. ~q 2,7: M.T 
9. ~p 1,6: S.D 
10: ~p ∧ ~p 8,9: Conj 
11: ~ (p ˅ q) 10: De Morgan 
 
 41 
h) r → s, s → q, r ˅ ( s ∧ p) | ~ q → p ∧ s 
 
1. r → s 
2. s → q 
3. r ˅ (s ∧ p) 
4. ~ q 
_______________________ 
5. ( r ˅ s) ∧ (r ˅ p) 3: Dist 
6. r → q 1,2: S.H 
7. ~r 4,6: M.T 
8. r ˅ s 5: Simp 
9. r ˅ p 5: Simp 
10. s 7,8: S.D 
11. p 7,9: S.D 
12. p ∧ s 10,11: Conj 
 
i) r ˅ s, ~t → ~ p, r → ~ q | p ∧ q → s ∧ t 
1. r ˅ s 
2. ~t → ~ p 
3. r → ~ q 
4. p ∧ q 
___________________ 
5. p 4: Simp 
6. q 4: Simp 
7. t 2,5: M.T 
8. ~ r 3,6: M.T 
9. s 1,8: S.D 
10. s ∧ t 7,9: Conj. 
 
j) r → p, s → t, t → r | s → p ˅ q 
1. r → p 
2. s → t 
3. t → r 
4. s 
__________________ 
5. s → r 2,3: S.H 
6. r 4,5: M.P 
7. p 1,6: M.P 
8. p ˅ q 7: Adição 
 
k) q → p, t ˅ s, q ˅ ~s | ~ ( p ˅ r) → t 
1. q → p 
2. t ˅ s 
3. q ˅~s 
4. ~(p ˅ r) 
________________ 
5. ~ p ∧ ~r 4: De Morgan 
6. ~ p 5: Simp 
7. ~ q 1,6: M.T 
8. ~ s 3,7: S.D 
9. t 2,8: S.D 
 42 
l) p ˅ q → r, s → ~r ∧ ~t, s ˅ u | p → u 
1. p ˅ q →r 
2. s → ~r ∧ ~t 
3. s ˅ u 
4. p 
___________________ 
5. p ˅ q 4: Adição 
6. r 1,5: M.P 
7. r ˅ t 6: Adição 
8. s → ~ (r ˅ t) 2: De Morgan 
9. ~ s 7,8: M.T 
10. u 3,9: S.D 
 
m) p → q, r → t, s → r, p v s | ~q → t 
1. p → q 
2. r → t 
3. s → r 
4. p ˅ s 
5. ~ q 
__________________ 
6. q ˅ r 1,3,4: D.C 
7. r 5,6: S.D 
8. t 2,7: t 
 
n) p ˅ q, ~ r ˅ ~ q | ~ p → ~ r 
1. p ˅ q 
2. ~ r ˅~ q 
3. ~ p 
_____________ 
4. q 1,3: S.D 
5. ~ r 2,4: S.D 
 
o) ~ p ˅ ~ q, p ˅ (r ∧ s) | q → s 
1. ~ p ˅~ q 
2. p ˅ (r ∧ s) 
3. q 
_______________________ 
4. ~ p 1,3: S.D 
5. r ∧ s 2,4: S.D 
6. s 5: Simp 
 
 
p) p ∧ q → ~r ˅ ~s, r ∧ s | p → ~q 
1. p ∧ q → ~ r ˅~ s 
2. r ∧ s 
3. p 
___________________ 
4. p ∧ q → ~( r ∧ s) 1: De Morgan 
5. ~ (p ∧ q) 2,4: M.T 
6. ~ p ˅ ~ q 5: De Morgan 
7. ~ q 3,6: S.D 
 43 
q) p → q, p ˅ ~ r, ~ s ˅ t → r | ~ s → q 
1. p → q 
2. p ˅ ~ r 
3. ~ s ˅ t → r 
4. ~ s 
___________________ 
5. ~ s ˅ t 4 Adição 
6. r 3,5: M.P 
7. p 2,6: S.D 
8, q 1,7: M.P 
 
r) (p → q) ˅ r, s ˅ t → ~r, s ˅ (t ∧ u) | p → q 
1. (p → q) ˅ r 
2. s ˅ t → ~r 
3. s ˅ (t ∧ u) 
4. p 
__________________ 
5. ~ p ˅ q ˅ r 1: Condicional 
6. q ˅ r 4,5: S.D 
7. ( s ˅ t ) ∧ ( s ˅ u ) 3: Distributiva 
8. s ˅ t 7:Simp. 
9. ~r 2,8: M.P 
10. q 6,9: S.D 
 
s) (p → q) ∧ ~(r ∧ ~s), s → t ˅ u, ~ u | r → t 
1. (p → q) ∧ ~ ( r ∧ ~s) 
2. s → t ˅ u 
3. ~ u 
4. r 
___________________ 
5. ~(r ∧ ~s ) 1: Simp 
6. ~r ˅ s 5: De Morgan 
7. s 4,6: S.D 
8. t ˅ u 2,7: M.P 
9. t 3,8: S.D 
 
t) p ˅ ~ q, q, r → ~s, p → (~s ∧→ t) | ~t → ~r 
1. p ˅ ~q 
2. q 
3. r → ~s 
4. p → (~s → t) 
5. ~t 
__________________ 
6. p 1,2: S.D 
7. ~ s → t 4,6: M.P 
8. s 5,7: M.T 
9. ~ r 3,8: M.T 
 
 
 
 
 44 
4) Usar a Regra DI (Demonstração Indireta) para mostrar que são válidos os seguintes argumentos: 
a) ~(p ∧ q), p → r, q v ~r | ~p 
1. ~ (p ∧ q) 
2. p → r 
3. q ˅ ~r 
4. p 
___________________ 
5. ~ p ˅ ~ q 1: De Morgan 
6. ~ q 4,5: S.D 
7. r 2,4: M.P 
8. ~ r 3,6: S.D 
9. ~ r ∧ r 7,8: Conj. 
 
b) p → ~q, r → ~p, q ˅ r | ~p 
1. p → ~q 
2. r → ~p 
3. q ˅ r 
4. p 
_____________________ 
5. p → ~r 2: Contra positiva 
6. ~ p ˅ ~p 1,5,3: D.D 
7. ~ p 6: Idempotência 
8. ~ p ∧ p 7,4: Conj. 
 
 
 
c) ~(p ∧ q), ~r → q, ~p→ r | r 
1. ~(p ∧ q) 
2. ~r → q 
3. ~p → r 
4. ~r 
________________ 
5. q 2,4: M.P 
6. p 3,4: M.T 
7. p ∧ q 5,6: Conjunção 
8. (p ∧ q) ∧~(p ∧ q) 1,7: Conjunção 
 
d) p → q ˅ r, q → ~p, s → ~r | ~( p ∧ s) 
1. p → q ˅ r 
2. q → ~ p 
3. s → ~ r 
4. p ∧ s 
_____________ 
5. p 4: Simp 
6. s 4: Simp 
7. q ˅ r 1,5: M.P 
8. ~ r 3,6: M.P 
9. ~ q 5,2: M.T 
10. q 7,8: S.D 
11. ~ q ∧ q 9,10: Conj 
 
 45 
e) p ˅ q, p → ~r, q → s | ~r ˅ s 
1. p ˅ q 
2. p → ~r 
3. q → s 
4. ~(~r ˅ s) 
_________________ 
5. r ∧ ~s 4: De Morgan 
6. r 5: Simp. 
7. ~ s 5: Simp 
8. ~ p 2,6: M.T 
9. q 1,8: S.D 
10. s 3,9: M.P 
11. ~ s ∧ s 7,10: Conj. 
 
f) p ˅ q, s → ~p, ~(q ˅ r) | ~s 
1. p ˅ q 
2. s → ~p 
3. ~(q ˅ r) 
4. s 
____________________ 
5. ~ p ∧ ~ r 3: De Morgan 
6. ~ q 5: Simp 
7. p 1,6: S.D 
8. ~ s 2,7: M.T 
9. ~ s ∧ s 4,8: Conj 
 
g) p → ~ q, q ˅ ~ r, ~ (s ˅ ~ r) | ~ p 
1. p → ~ q 
2. q ˅ ~ r 
3. ~ (s ˅ ~ r) 
4. p 
____________________ 
5. ~ q 1,4: M.P 
6. ~ r 2,5: S.D 
7. s ˅ ~ r 6: Adição 
8. ~(s ˅ ~r) ∧ ( s ˅ ~ r) 3,7: Conjunção 
 
 
h) ~ p → ~ q, ~ p ˅ r, r → ~ s | ~ q ˅ ~ s 
1. ~ p → ~ p 
2. ~p ˅ r 
3. r → ~s 
4. ~(~q ˅ ~ s) 
________________ 
5. q ∧ s 4: De Morgan 
6. q 5: Simp. 
7. s 5: Simp. 
8. p 1,6: M.T 
9. ~ r 3,7: M.T 
10. r 2,8:S.D 
11. ~r ∧ r 9,10: Conj 
 46 
i) p ∧ q ↔ ~r, ~ r → ~ p, ~ q → ~ r | q 
1. p ∧ q ↔ ~ r 
2. ~ r → ~ p 
3. ~ q → ~ r 
4. ~ q 
__________________ 
5. (p ∧ q → ~ r) ∧ (~ r → p ∧ q) 1: Bicondicional 
6. ~ r → p ∧ q 5: Simplificação 
7. ~ r 3,4: M.P 
8. p ∧ q 6,7: M.P 
9. q 8: Simp 
10. ~ q ∧ q 4,9: Conj. 
 
 
j) ~p ˅ ~q, r ˅ s → p, q ˅ ~s, ~r | ~ (r ˅ s) 
1. ~p ˅ ~q 
2. r ˅ s → p 
3. q ˅ ~s 
4. ~ r 
5. r ˅ s 
___________________ 
6. s 4,5: S.D 
7. q 3,6: S.D 
8. p 2,5: M.P 
9. ~p 1,7: S.D 
10. ~p ∧ p 8,9: Conj. 
 
 
k) p ˅ q → r, ~ r, s → p | ~ s 
1. p ˅ q → r 
2. ~ r 
3. s → p 
4. s 
_____________________ 
5. ~( p ˅ q) 1,2; M.T 
6. ~p ∧ ~ p 5: De Morgan 
7. ~ p 6: Simp. 
8. p 3,4: M.P 
9. ~ p ∧ p 7,8: Conj. 
 
 
 
 
 47 
l) (p → q) ˅ r, s ˅ t → ~r, s ˅ (t ∧ u) | p → q 
1. ( p → q) ˅ r 
2. s ˅ t → ~r 
3. s ˅ (t ∧ u) 
4. p 
5. ~ q 
_____________________ 
6. ~ p ˅ q ˅ r 1: Condicional 
7. q ˅ r 4,6: S.D 
8. r 5,7: S.D 
9. ~ (s ˅ t) 8,2: M.T 
10. ~ s ∧ ~ t 9: De Morgan 
11. ~ s 10: Simp. 
12. ~ t 10: Simp. 
13. t ∧ u 3,11: S.D 
14. t 13: Simp. 
15. ~ t ∧ t 12,14: Conj. 
 
 
m) p → q, q ˅ r → s, ~s | ~p 
1. p → q 
2. q ˅ r → s 
3. ~ s 
4. p 
____________________ 
5. q 1,4: M.P 
6. q ˅ r 5: Adição 
7. s 2,6: M.P 
8. ~s ∧ s 3,7: Conj. 
 
 
n) (p → q) → r, r ˅ s → ~t, t | ~q 
1. ( p → q) → r 
2. r ˅ s → ~t 
3. t 
4. q 
____________________ 
5. ~r ∧ ~s 2,3: M.T 
6. ~r 5: Simp. 
7. ~(p → q) 1,6: M.T 
8. ~(~p ˅ q) 7: Condicional 
9. p ∧ ~q) 8: De Morgan 
10. ~q 9: Simp. 
11. ~q ∧ q 10,4; Conj. 
 
 
 
 48 
o) (p → q) ˅ (r ∧ s), ~ q | p → s 
1. (p → q) ˅ (r ∧s) 
2. ~ q 
3. p 
4. ~ s 
___________________ 
5. p ∧ ~q 2,3: Conj. 
6. ~(~p ˅ q) 5: De Morgan 
7. ~(p → q) 6: Condicional 
8. r ∧ s 1,7: S.D 
9. s 8: Simp 
10. ~s ∧ s 4,9: Conj. 
 
 
p) p → q, q ↔ s, t ˅ ( r ∧ ~s) | p → t 
1. p → q 
2. q ↔ s 
3. t ˅ (r ∧ ~s) 
4. p 
5. ~t 
_______________________ 
6. (q → s) ∧ (s → q) 2: Bi-condicional 
7. r ∧ ~s 3,5: S.D 
8. ~s 7: Simp. 
9. q → s 6: Simp 
10. ~ q 8,9: M.T 
11. ~ p 1,10: M.T 
12. ~ p ∧ p 4,11: Conj. 
 
 
q) ~p → ~q ˅ r, s ˅ (r → t), p → s, ~s| q → t 
1. ~p → ~ q ˅ r 
2. s ˅ (r → t) 
3. p → s 
4. ~ s 
5. q 
6. ~ t 
_____________________ 
7. ~ p 3,4: M.T 
8. ~ p ˅ r 1,7: M.P 
9. r 5,8: S.D 
10. r →t 2,4: S.D 
11. t 9,10: M.P 
12. ~ t ∧ t 6,11: Conj. 
 
 
 
 
 
 49 
r) ~(p → q) v (s → ~r), q ˅ s, p → ~s | ~ r˅~ s 
1. ~ ( p → q) ˅ (s → ~ r) 
2. q ˅ s 
3. p → ~ s 
4. ~(~ r ˅ ~s) 
___________________ 
5. r ∧ s 4: Simp. 
6. s 5: Simp. 
7. ~ p 6,3: M.T 
8. ~ p ˅ q 7 . Adição 
9. p → q 8: Condicional 
10. s → ~ r 1,9: S.D 
11. r 5: Simp. 
12. ~ s 10,11: M.T 
13. ~ s ∧ s 12,6: Conj. 
 
 
s) (~p → q) ∧ (r → s), p ↔ t ˅ ~s, r, ~t | q 
1. (~ p → q) ∧ (r → s) 
2. p ↔ t ˅ ~s 
3. r 
4. ~ t 
5. ~ q 
___________________________ 
6. ~p → q 1: Simp. 
7. p 6,5: M.T 
8. (p → t ˅ ~s) ∧ (t ˅ ~s → p) 2: Bicondicional 
9. p → t ˅ ~s 8: Simp. 
10. t ˅ ~s 7,9: M.P 
11. ~ s 4,10: S.D 
12. r → s 1: Simp. 
13. ~ r 11,12: M.T 
14. ~ r ∧ r 13,3: Conj. 
 
t) (p → q) ↔ (r ∧ s → t), p → q ∧ r, r, ~t | ~s 
1. (p → q) ↔ ( r ∧ s → t) 
2. p → q ∧ r 
3. r 
4. ~t 
5. s 
_____________________ 
6. ~p ˅ (q ∧ r) 2: Cond. 
7. (~p ˅ q) ∧ ( ~p v r) 6: Dist. 
8. ~p ˅ q 7: Simp. 
9. p → q 8: Condicional 
10. (p → q) → (r ∧ s →t) ∧ (r ∧ s → t) → (p→) 1: Bicondicional 
11. ( p → q) → (r ∧ s →t) 10: Simp. 
12. r ∧ s → t 9,11: M.P 
13. ~r ˅ ~s 4,12: M.T 
14. ~r 5,13: SD. 
15. ~r ˄ r 4,14: Conjunção 
 50 
 
 
u) ~(p → ~q) ((r ↔ s) ˅ t) , p. q, ~t | r → s 
1. ~(p →~q) →( ( r ↔ s) ˅ t ) 
2. p 
3. q 
4. ~ t 
5. r 
6. ~ s 
____________________________ 
7. p ∧ q 2,3: Conj. 
8. ~(~ p ˅ ~ q) 7: De Morgan 
9. ~( p → ~ q) 8: Condicional 
10. (r ↔ s) ˅ t 9,1: M.P 
11. r ↔ s 4,10: S.D 
12. (r → s) ∧ (s → r) 11: Bi-condicional 
13. r → s 12: Simp. 
14. ~ r 13,6: M.T 
15. ~ r ∧ r 14,5: Conjunção