Lógica Matemática e Algoritmos

∧ (p → q) → ¬ p c) ¬ p ∧ (p ∨ q) → q d) p ∧ q → p e) p → p ∨ q f) p → (q → p ∧ q) g) (p → q) ∧ (p → r) → (p → q ∧ r) h) (p → q) ∧ (q → r) → (p → r) i) (p → q) ∧ (¬ p → q) → q j) (p ∨ q → r) ↔ (p → r) ∧ (q → r) k) (p → q ∧ ¬ q) → ¬ p l) p ∧ ¬ p → q ˆ ´ 1.5. EQUIVALENCIA TAUTOLOGICA 43 m) p ∨ ¬ p n) ¬ (p ∨ ¬ p) 1.5 Equivalˆ encia Tautol´ ogica No Exemplo 27, uma mesma senten¸ca foi simbolizada de duas maneiras distintas. Vejamos um outro exemplo. Exemplo 55 A senten¸ca caso Jo˜ao a convide, caso Ricardo a convide, C´elia vai ao cinema pode ser simbolizada como p ∨ q → r, onde: p : (Jo˜ao convida C´elia) q : (Ricardo convida C´elia) r : (C´elia vai ao cinema). Mas, levando em conta que a senten¸ca quer dizer que se C´elia n˜ao foi ao cimema, nem Jo˜ao nem Ricardo a convidou, temos outra simboliza¸c˜ ao: ¬ r → ¬ p ∧ ¬ q. Surge, ent˜ ao, a quest˜ ao de decidir se duas simboliza¸c˜oes distintas expressam o mesmo conte´ udo. Esta quest˜ ao pode ser resolvida com uso das tabelas de verdade, mediante os conceitos a seguir. Defini¸ c˜ ao 1.22 Uma interpreta¸c˜ ao para duas senten¸cas simbolizadas α e β ´e uma atribui¸c˜ ao de valores de verdade ` as letras sentenciais que ocorrem em α e β. Exemplo 56 As senten¸cas simbolizadas p ∨ q → r e ¬ r ∨ ¬ p ∧ ¬ q possuem ocorrˆencias das senten¸cas atˆ omicas p, q e r. Logo, possuem oito interpreta¸c˜ oes. Defini¸ c˜ ao 1.23 Duas senten¸cas simbolizadas α e β s˜ ao tautologicamente equivalentes se, em cada interpreta¸c˜ ao para α…