Slides 03

Prévia do material em texto

1
Matemática Discreta
Aula nº 3
Francisco Restivo
2006-03-09
2
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
2
3
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)
4
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
3
5
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)
6
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
4
7
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)
Outro exemplo:
Se o Deco joga então Portugal é campeão.
Contrária: Se Portugal é campeão então o Deco joga.
Inversa: Se o Deco não joga então Portugal não é campeão.
Contrapositiva: Se Portugal não é campeão então o Deco não joga.
Quais são as proposições logicamente equivalentes?
Proposição dual?
p Ù (q Ú ¬p) º p Ù q
8
Argumentos:
Um argumento é constituído por um conjunto de proposições, 
chamadas premissas, e por uma outra proposição, chamada 
conclusão.
Um argumento é válido se a conclusão é uma consequência 
lógica da conjunção das premissas:
P1 Ù P2 Ù P3 Ù ... + Q
(P1 Ù P2 Ù P3 Ù ...) ® Q é um tautologia.
p: o cão morde o gato
q: o gato não gosta do cão
P1: p ® q
P2: p
Q: q
É válido?