Mat Disc AULA02

Prévia do material em texto

Matemática Discreta - AULA02 - Prof. Rafael Matos 
 
Bibliografia utilizada: 
ROSEN, K. H. Matemática Discreta e suas aplicações. 
Capítulo I. 
 
Tema: 
Equivalências lógicas. Tautologia e contradição. Exercícios de fixação. 
 
Notas: 
 
Equivalências proposicionais 
 
Nas argumentações matemáticas, a substituição de uma proposição por outra com o 
mesmo valor-verdade é um passo importante, sendo largamente utilizados em sua 
composição. As substituições podem ser definidas como: tautologia, contradição e 
contingência. 
 
Tautologia 
 
Definida como uma proposição composta que é sempre ​verdadeira​, quaisquer que 
sejam os valores-verdade das proposições que nela ocorrem. 
 
p p¬ pp ⋁ ¬ 
F V V 
V F v 
Exemplo de Tautologia 
 
Contradição 
 
Definida como uma proposição composta que é sempre ​falsa​, quaisquer que sejam os 
valores-verdade das proposições que a compõem. 
 
p p¬ pp ⋀ ¬ 
F V F 
V F F 
Exemplo de Contradição 
 
Exemplos de tautologia e contradição podem facilmente ser criados a partir de uma única 
variável proposicional. 
 
Contingência 
 
Definida como uma proposição composta que não é uma tautologia, tampouco 
contradição. 
 
Equivalências lógicas 
 
Proposições compostas que possuem o mesmo valor-verdade em todos os possíveis casos 
são logicamente equivalentes, ou seja: 
 
Proposições ​p e ​q são logicamente equivalentes se for uma tautologia, também p ↔ q 
representado por ou . Uma forma de determinar a equivalência é por meio de p ≡ q p⇔ q 
tabelas-verdade, comparando os resultados de ambas. 
 
Leis de Morgan 
 
Demonstradas na metade do século XIX, as equivalências lógicas abaixo possuem 
Tabelas-Verdade iguais, o que permite que sejam chamadas de equivalências. 
 
1) (p ) p q¬ ⋀ q ≡ ¬ ⋁ ¬ 
A negação de uma conjunção é formada pela disjunção das negações das proposições 
componentes. 
Prova na forma de exercício 
 
2) (p ) p q¬ ⋁ q ≡ ¬ ⋀ ¬ 
A negação de uma disjunção é formada pela conjunção das negações das proposições 
componentes. 
 
p q p ⋁ q (p )¬ ⋁ q p¬ q¬ p q¬ ⋀ ¬ 
F F F V V V V 
F V V F V F F 
V F V F F V F 
V V V F F F F 
Tabela-Verdade de uma das Leis de Morgan 
 
Exercício: Provar pp → q ≡ ¬ ⋁ q 
 
 
 
Lista de equivalências 
 
Lembrando que: ​V - verdadeiro​ e ​F - falso 
 
Equivalências Nome 
 p ⋀ V ≡ p 
 p ⋁ F ≡ p 
Propriedades dos elementos neutros 
 p ⋁ V ≡ V 
 p ⋀ F ≡ F 
Propriedades de dominação 
 p ⋁ p ≡ p 
 p ⋀ p ≡ p 
Propriedades idempotentes 
(¬p) ¬ ≡ p Propriedade da dupla negação 
 p ⋁ q ≡ q ⋁ p 
 p ⋀ q ≡ q ⋀ p 
Propriedades comutativas 
p ) q )( ⋁ q ⋁ r ≡ p ⋁ ( ⋁ r 
p ) q )( ⋀ q ⋀ r ≡ p ⋀ ( ⋀ r 
Propriedades associativas 
q ) p ) p )p ⋁ ( ⋀ r ≡ ( ⋁ q ⋀ ( ⋁ r 
q ) p ) p )p ⋀ ( ⋁ r ≡ ( ⋀ q ⋁ ( ⋀ r 
Propriedades distributivas 
(p ) p q¬ ⋀ q ≡ ¬ ⋁ ¬ 
(p ) p q¬ ⋁ q ≡ ¬ ⋀ ¬ 
Leis de Morgan 
p ) p ⋁ ( ⋀ q ≡ p 
p ) p ⋀ ( ⋁ q ≡ p 
Propriedades de absorção 
p p ⋁ ¬ ≡ V 
p p ⋀ ¬ ≡ F 
Propriedades de negação 
 
 
Exercício: Provar as equivalências listadas 
 
 
 
Equivalências com Sentenças condicionais 
pp → q ≡ ¬ ⋁ q 
q pp → q ≡ ¬ → ¬ 
pp ⋁ q ≡ ¬ → q 
(p q)p ⋀ q ≡ ¬ → ¬ 
(p ) q¬ → q ≡ p ⋀ ¬ 
p ) p ) q )( → q ⋀ ( → r ≡ p → ( ⋀ r 
p ) q ) p )( → r ⋀ ( → r ≡ ( ⋁ q → r 
p ) p ) q )( → q ⋁ ( → r ≡ p → ( ⋁ r 
p ) q ) p )( → r ⋁ ( → r ≡ ( ⋀ q → r 
 
 
Equivalências com Sentenças Bicondicionais 
p ) q )p ↔ q ≡ ( → q ⋀ ( → p 
p qp ↔ q ≡ ¬ ↔ ¬ 
p ) ¬p q)p ↔ q ≡ ( ⋀ q ⋁ ( ⋀ ¬ 
(p ) q¬ ↔ q ≡ p ↔ ¬ 
 
Exercícios: Construir novas equivalências a partir das existentes. 
 
a) Mostrar que e são logicamente equivalentes;(p )¬ → q qp ⋀ ¬ 
b) Provar que é uma tautologia;p ) p )( ⋀ q → ( ⋁ q 
c) Mostrar que e são logicamente equivalentes;(p )¬ ↔ q qp ↔ ¬