aula2 Lógica Proposicional -Material Prof César

Prévia do material em texto

' $
LO´GICA PROPOSICIONAL
Prof. Ce´sar Francisco de Moura Couto
Matema´tica Discreta
& %
' $
CEFET-MG Lo´gica Proposicional
Introduc¸a˜o
• Definic¸a˜o 1:
– Tautologia e´ uma proposic¸a˜o composta que e´ sempre verdadeira, qualquer que seja os
valores-verdade das proposic¸o˜es que ocorrem nela.
– Contradic¸a˜o e´ uma proposic¸a˜o composta que e´ sempre falsa qualquer, que seja os
valores-verdade das proposic¸o˜es que ocorrem nela.
Tautologia e Contradic¸a˜o
p ¬p p ∨ ¬p p ∧ ¬p
V F V F
F V V F
Prof. Ce´sar Francisco de Moura Couto 1& %
' $
CEFET-MG Lo´gica Proposicional
Equivaleˆncias Lo´gicas
• Definic¸a˜o 2: As proposic¸o˜es p e q sa˜o chamadas de logicamente equivalentes (≡) se p↔ q
e´ uma tautologia.
• Mostre que ¬(p ∨ q) e ¬p ∧ ¬q sa˜o logicamente equivalentes. Uma das leis de De Morgan.
• Soluc¸a˜o:
¬(p ∨ q) e ¬p ∧ ¬q
p q (p ∨ q) ¬(p ∨ q) ¬p ¬q ¬p ∧ ¬q
V V V F F F F
V F V F F V F
F V V F V F F
F F F V V V V
Prof. Ce´sar Francisco de Moura Couto 2& %
' $
CEFET-MG Lo´gica Proposicional
Equivaleˆncias Lo´gicas
• Mostre que (p→ q) e ¬p ∨ q sa˜o logicamente equivalentes
• Soluc¸a˜o:
(p→ q) e ¬p ∨ q
p q ¬p ¬p ∨ q p→ q
V V F V V
V F F F F
F V V V V
F F V V V
Prof. Ce´sar Francisco de Moura Couto 3& %
' $
CEFET-MG Lo´gica Proposicional
Equivaleˆncias Lo´gicas
• Mostre que p ∨ (q ∧ r) e (p ∨ q) ∧ (p ∨ r) sa˜o logicamente equivalentes. Essa e´ a
propriedade distributiva da disjunc¸a˜o sobre a conjunc¸a˜o.
• Soluc¸a˜o:
p ∨ (q ∧ r) e (p ∨ q) ∧ (p ∨ r)
p q r q ∧ r p ∨ (q ∧ r) p ∨ q p ∨ r (p ∨ q) ∧ (p ∨ r)
V V V V V V V V
V V F F V V V V
V F V F V V V V
V F F F V V V V
F V V V V V V V
F V F F F V F F
F F V F F F V F
F F F F F F F F
Prof. Ce´sar Francisco de Moura Couto 4& %
' $
CEFET-MG Lo´gica Proposicional
Equivaleˆncias Lo´gicas
Equivaleˆncias Lo´gicas
Equivaleˆncias Nome
p ∧ V ≡ p Propriedades dos elementos neutros
p ∨ F ≡ p
p ∨ V ≡ V Propriedades de dominac¸a˜o
p ∧ F ≡ F
p ∨ p ≡ p Propriedades idempotentes
p ∧ p ≡ p
¬(¬p) ≡ p Propriedade da dupla negac¸a˜o
p ∨ q ≡ q ∨ p Propriedades comutativas
p ∧ q ≡ q ∧ p
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r) Propriedades associativas
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) Propriedades distributivas
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
¬(p ∧ q) ≡ ¬p ∨ ¬q Leis de De Morgan
¬(p ∨ q) ≡ ¬p ∧ ¬q
p ∨ (p ∧ q) ≡ p Propriedades de absorc¸a˜o
p ∧ (p ∨ q) ≡ p
p ∨ ¬p ≡ V Propriedades de negac¸a˜o
p ∧ ¬p ≡ F
Prof. Ce´sar Francisco de Moura Couto 5& %
' $
CEFET-MG Lo´gica Proposicional
Usando as Leis de De Morgan
• Expresse as negac¸o˜es de ”Miguel tem um celular e um laptop”e ”Rodrigo vai ao concerto ou
Carlos vai ao concerto”usando as leis de De Morgan.
• Soluc¸a˜o 1: ”Miguel na˜o tem celular ou na˜o tem um laptop.”
• Soluc¸a˜o 2: ”Rodrigo na˜o vai ao concerto e Carlos na˜o vai ao concerto.”
Prof. Ce´sar Francisco de Moura Couto 6& %
' $
CEFET-MG Lo´gica Proposicional
Construindo Novas Equivaleˆncias Lo´gicas
• Mostre que ¬(p→ q) e p ∧ ¬q sa˜o logicamente equivalentes usando equivaleˆncias lo´gicas.
• Soluc¸a˜o:
¬(p→ q) ≡ ¬(¬p ∨ q) pelo Exemplo anterior
≡ ¬(¬p) ∧ ¬q) pela segunda lei de De Morgan
≡ p ∧ ¬q pela propriedade da dupla negac¸a˜o
Prof. Ce´sar Francisco de Moura Couto 7& %
' $
CEFET-MG Lo´gica Proposicional
Construindo Novas Equivaleˆncias Lo´gicas
• Mostre que ¬(p ∨ (¬p ∧ q)) e ¬p ∧ ¬q sa˜o logicamente equivalentes usando equivaleˆncias
lo´gicas.
• Soluc¸a˜o:
¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬(¬p ∧ q) pela segunda lei de De Morgan
≡ ¬p ∧ [¬(¬p) ∨ ¬q] pela segunda lei de De Morgan
≡ ¬p ∧ (p ∨ ¬q) pela propriedade da dupla negac¸a˜o
≡ (¬p ∧ p) ∨ (¬p ∧ ¬q) pela segunda propriedade distributiva
≡ F ∨ (¬p ∧ ¬q) pois (¬p ∧ p) ≡ F
≡ (¬p ∧ ¬q) ∨ F pela propriedade comutativa para disjunc¸o˜es
≡ ¬p ∧ ¬q pela propriedade dos elementos neutros para F
Prof. Ce´sar Francisco de Moura Couto 8& %