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