Slides 02 0607

Prévia do material em texto

Matemática Discreta
Aula nº 2
Francisco Restivo
2007-02-28
2
condicional
p
V
V F F
F V V
F
q p → q
V V
F V
Condicional
p é o antecedente e q o consequente
Se p é verdadeiro então q é verdadeiro
(se p é falso a implicação é verdadeira, 
independentemente do valor de q):
Se chover hoje então vou ao cinema
se não chover, não sabemos…
3
Condição necessária e condição suficiente
p é condição suficiente para q 
q é condição necessária para p
condicional
p ¬p
V F
F
V
V
V F F
F V V
F
q ¬p ∨ q
V V
F V
Expressões equivalentes
p → q
¬p ∨ q
4
bicondicional
p
V
V F F
F V F
F
q p ↔ q
V V
F V
Bicondicional
É verdadeiro quando p e q são ambos 
verdadeiros ou ambos falsos
5
Condição necessária e suficiente
Se e só se ...
bicondicional
p q p∧q ¬p∧¬q
V F
F
F
V
F
F
F
V
F
V
F
V
V
F
F
(p∧q)∨(¬p∧¬q)
V
F
F
V
Expressões equivalentes
p ↔ q
(p ∧ q) ∨ (¬p ∧¬q)
6
Tautologia é uma proposição composta que é
sempre verdadeira, independentemente dos 
valores lógicos dos seus componentes
p ∨ ¬p
Contradição é uma proposição composta que é
sempre falsa, independentemente dos valores 
lógicos dos seus componentes
p ∧ ¬p
(p ∧ q) ∨ ¬(p ∧ q)
(p ∧ ¬q) ∧ (¬p ∨ q)
7
Equivalência lógica
Duas proposições são logicamente equivalentes 
se tiverem o mesmo valor lógico para todas as 
combinações de valores dos seus componentes
Implicação lógica
Uma proposição P implica uma proposição Q se 
sempre que P for verdadeira Q também o for 
¬p ∨ ¬q ≡ ¬(p ∧ q)
(¬p ∨ ¬q) ↔ ¬(p ∧ q) é uma tautologia
q ├ (p ∨ q)
q → (p ∨ q) é uma tautologia
8
Equivalências lógicas importantes (1)
Idempotência
p ∧ p ≡ p
p ∨ p ≡ p
Comutatividade
p ∧ q ≡ q ∧ p
p ∨ q ≡ q ∨ p (também para ∨)
p ↔ q ≡ q ↔ p
Associatividade
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r) (também para ∨)
(p ↔ q) ↔ r ≡ p ↔ (q ↔ r)
9
Equivalências lógicas importantes (2)
Absorção
p ∧ (p ∨ q) ≡ p
p ∨ (p ∧ q) ≡ p
Distributividade
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) 
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) 
Leis de de Morgan
¬(p ∨ q) ≡ ¬p ∧ ¬q
¬(p ∧ q) ≡ ¬p ∨ ¬q
Involução
¬(¬p) ≡ p
10
Equivalências lógicas importantes (3)
Identidade
p ∨ f ≡ p p ∧ v ≡ p
p ∨ v ≡ v p ∧ f ≡ f
Complemento
p ∨ ¬p ≡ v p ∧ ¬p ≡ f
¬f ≡ v ¬v ≡ f
Substituição 
Pode-se substituir uma proposição 
por outra logicamente equivalente
Dualidade
(∧, ∨, v, f) ⇔ (∨, ∧, f, v)
11
Exemplo:
Mostrar que (¬p ∧ q) ∨ ¬(p ∨ q) ≡ ¬p
(¬p ∧ q) ∨ ¬(p ∨ q) ≡ (¬p ∧ q) ∨ (¬p ∧ ¬q) (de Morgan)
≡ ¬p ∧ (q ∨ ¬q) (Distributividade)
≡ ¬p ∧ t (Complemento)
≡ ¬p (Identidade)
Proposições duais:
(p ∧ q) ∨ ¬p e (p ∨ q) ∧ ¬ p 
Se duas proposições são logicamente 
equivalentes , as suas duais também o são:
(¬p ∨ ¬q) ≡ ¬(p ∧ q) 
(¬p ∧ ¬q) ≡ ¬(p ∨ q)
12
Programa Boole:
procurar em LPL Software
há também os programas Fitch e Tarski World
13
Condicionais (p → q)
Proposição contrária: q → p
Proposição inversa: ¬p→ ¬q
Proposição contrapositiva: ¬q→ ¬p
Uma proposição condicional e a sua contrapositiva são logicamente equivalentes
A contrária e a inversa de uma proposição condicional são logicamente equivalentes
14
Outro exemplo:
Se o Quaresma joga então o Porto é campeão.
Contrária: 
Se o Porto é campeão então o Quaresma joga.
Inversa: 
Se o Quaresma não joga então o Porto não é campeão.
Contrapositiva: 
Se o Porto não é campeão então o Quaresma não joga.
Quais são as proposições logicamente equivalentes?
Mais um exemplo:
Se hoje não é domingo, então o supermercado está
aberto até à meia-noite.
	Matemática Discreta