Slides 03 0607

Prévia do material em texto

Matemática Discreta
Aula nº 3
Francisco Restivo
2007-03-01
2
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
3
Um 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?
Outro exemplo:
Se hoje não é domingo, então o supermercado está
aberto até à meia-noite.
Contrapositiva?
4
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?
5
Será válido o seguinte argumento?
P1: O João sai se e só se lavar a louça.
P2: Se o João sai então não vê televisão.
Q: Então ou vê televisão ou lava a louça, mas 
nunca as duas coisas.
Basta um contra-exemplo:
NÃO É VÁLIDO!
6
E este?
P1: Se há nuvens no céu, o Sol não brilha.
P2: Se o Sol não brilha, a temperatura desce.
Q: Se a temperatura não desce, não há nuvens no Céu.
7
Outra forma de verificar a validade do argumento?
P1: Se há nuvens no céu, o Sol não brilha.
P2: Se o Sol não brilha, a temperatura desce.
Q: Se a temperatura não desce, não há nuvens no Céu.
N → ¬B
¬B → D
¬D → B contrapositiva de 2
B → ¬N contrapositiva de 1
¬D → ¬N eliminação de → 4 em 3
silogismo hipotético
8
Lógica de predicados
Um predicado é uma propriedade de um ou vários objectos ou 
indivíduos.
Uma proposição é constituída por um sujeito e por um predicado.
Predicados representam-se com letras maiúsculas
B: joga bem
G: ganha
Objectos ou indivíduos representam-se com letras 
minúsculas
d: Deco
p: Portugal
B(d) → G(p)
Se Deco joga bem então Portugal ganha
9
Nomes
Numa proposição simples há um sujeito e um predicado: 
B(c): o Cristiano Ronaldo joga bem
c representa o nome de um sujeito concreto
Variáveis
Podemos usar uma variável x: B(x) 
não sabemos se esta proposição é verdadeira ou falsa!
Depende do valor concreto que x assumir.
Quantificadores
Quantificador universal: ∀x B(x) | para todos
Quantificador existencial: ∃x B(x) | existe pelo menos um
10
Exemplo:
Traduzir para linguagem lógica: Todos os ratos são cinzentos
Predicados: R e C
Tradução: ∀x [R(x) → C(x)]
Outro exemplo:
Traduzir para linguagem lógica: Alguns ratos são cinzentos
Predicados: R e C
Tradução: ∃x [R(x) ∧ C(x)]
Mais um exemplo:
Traduzir para linguagem lógica: Não há ratos verdes
Predicados: R e V
Tradução: ¬∃x [R(x) ∧ V(x)]
11
Predicados envolvendo dois sujeitos:
P(x, y): x + y = 7 | universo do discurso: os números reais
8 proposições diferentes:
∀x ∀y P(x, y) F ∀y ∀x P(x, y) F (equivalentes)
∃x ∃y P(x, y) V ∃y ∃x P(x, y) V (equivalentes)
∀x ∃y P(x, y) V ∃y ∀x P(x, y) F
∀y ∃x P(x, y) V ∃x ∀y P(x, y) F
Negação de funções proposicionais quantificadas:
¬∀x F(x) ≡ ∃x (¬F(x))
¬∃x F(x) ≡ ∀x (¬F(x))
Outras equivalências:
¬∀x (¬F(x)) ≡ ∃x F(x)
¬∃x (¬F(x)) ≡ ∀x F(x)
12
Exemplo:
M(x): x é mortal
C(x): x vive na cidade
Simbolizar as negações das seguintes proposições:
i) Todas as pessoas são imortais
ii) Algumas pessoas vivem na cidade
i) ∀x (¬M(x))
¬∀x (¬M(x)) ≡ ∃x M(x)
Algumas pessoas são mortais
ii) ∃x C(x)
¬ ∃x C(x) ≡ ∀x (¬C(x))
Todas as pessoas vivem fora da cidade
13
Outro exemplo:
P(x, y): x > y
Q(x, y): x ≤ y
R(x): x – 7 = 2
S(x): x > 9
Diga o valor lógico das seguintes proposições:
i) ∃x R(x) v
ii) ∀y (¬S(y)) f
iii) ∀x ∃y P(x, y) v
iv) ∃y ∀x Q(x, y) f
v) ∀x ∀y (P(x, y) ∨ Q(x, y)) v
vi) ∃x S(x) ∧ ¬∀x R(x) v
14
Argumentos em lógica de predicados:
Todos os que têm olhos verdes não são de confiar. O António 
tem olhos verdes. Logo, o António não é de confiar.
V(x): x tem olhos verdes
C(x): x é de confiar
a: António
∀x [V(x) → ¬C(x)]
V(a)
---
¬C(a)
Parece que sim. Como se prova?
Caminhando das premissas para a conclusão, 
dando passos inequívocos.
Que regras são válidas?
15
Regras de inferência para quantificadores:
Especificação universal: 
se ∀x F(x) é verdade, então F(a) é verdade para qualquer a
Generalização universal: 
se F(a) é verdade para qualquer a, então ∀x F(x) é verdade
Especificação existencial: 
se ∃x F(x) é verdade, então existe um elemento a tal que F(a) 
é verdade (este um não é arbitrário...)
Generalização existencial: 
se existe um elemento a tal que F(a) é verdade, então ∃x F(x) 
é verdade
Estas regras permitem eliminar ou introduzir os quantificadores 
nos nossos argumentos!
16
Outras regras de inferência:
(p ∧ q) ├ p Simplificação
(p ∧ q) ├ q Simplificação
p ├ (p ∨ q) Adição
((p ∨ q) ∧ ¬p) ├ q Silogismo disjuntivo
((p → q) ∧ p) ├ q Modus ponens
((p → q) ∧ ¬q) ├ ¬p Modus tollens
((p → q) ∧ (q → r) ├ (p → r) Silogismo hipotético
(p → q) ├ (p → (q ∧ p)) Absorção
Por vezes, requerem-se provas formais, com passos de prova 
elementares, irrefutáveis.
	Matemática Discreta