Slides 04 0607

Prévia do material em texto

Matemática Discreta
Aula nº 4
Francisco Restivo
2007-03-07
2
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!
3
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.
4
A prova:
V(x): x tem olhos verdes
C(x): x é de confiar
a: António
1. ∀x [V(x) → ¬C(x)] Premissa
2. V(a) Premissa
---
3. V(a) → ¬C(a) Especificação universal (1)
4. ¬C(a) Modus ponens (3, 2)
Outro exemplo:
Todos os estudantes vão a festas. Alguns estudantes falam 
muito alto. Então há estudantes que falam muito alto e que vão 
a festas.
5
A prova:
E(x): x é estudante
F(x): x vai a festas
A(x): x fala muito alto
1. ∀x [E(x) → F(x)] Premissa
2. ∃x [E(x) ∧ A(x)] Premissa
---
3. E(a) ∧ A(a) Especificação existencial (2)
4. E(a) → F(a) Especificação universal (1)
5. E(a) Simplificação (3)
6. F(a) Modus ponens (5, 4)
7. A(a) Simplificação (3)
8. A(a) ∧ F(a) De 6 e 7
9. ∃x [A(x) ∧ F(x)] Generalização existencial (8)
6
Outro exemplo:
Alguns macacos comem bananas. Os macacos são 
primatas. Então, alguns primatas comem bananas.
M(x): x é macaco
P(x): x é primata
B(x): x come bananas
1. ∃x (M(x) ∧ B(x)) Premissa
2. ∀x (M(x) → P(x)) Premissa
---
3. M(a) ∧ B(a) Especificação existencial (1)
4. M(a) Simplificação (3)
5. M(a) → P(a) Especificação universal (2)
6. P(a) Modus ponens (4, 5)
7. B(a) Simplificação (3)
8. P(a) ∧ B(a) (6, 7)
9. ∃x (P(x) ∧ B(x)) Generalização existencial (8)
7
Teoria matemática:
Termos não definidos
Axiomas: proposições que não se provam
Definições
Teoremas: proposições que se provam
Provas
Teoria dos blogues e dos clogues:
Termos não definidos: blogue, clogue, terminar
Axioma 1: cada blogue termina pelo menos um clogue
Axioma 2: para cada clogue, há exactamente dois blogues
que o terminam
Axioma 3: há exactamente cinco blogues
Teorema: há pelo menos três clogues
8
Um modelo dá jeito!
Teoria dos blogues e dos clogues:
Termos não definidos: blogue, clogue, terminar
Axioma 1: cada blogue termina menos um clogue
Axioma 2: para cada clogue, há exactamente dois blogues
que o terminam
Axioma 3: há exactamente cinco blogues
Pode ser...
9
Permite pensar melhor...
Também pode ser!
10
Agora já será fácil provar o teorema!
Teorema: há pelo menos três clogues
11
Prova:
(A1 ∧ A2 ∧ A3 ∧ ... ∧ An) ├ T
(A1 ∧ A2 ∧ A3 ∧ ... ∧ An ∧ T1 ∧ T2 ∧ T3 ∧ ... ∧ Tm) ├ T
Teoremas:
Proposição universal: ∀x T(x)
Proposição condicional: P ⇒ Q
(A1 ∧ A2 ∧ A3 ∧ ... ∧ An ∧ T1 ∧ T2 ∧ T3 ∧ ... ∧ Tm ∧ P) ├ Q
Tipos de prova:
Prova directa: P ⇒ Q
Prova pela contrapositiva: ¬Q ⇒ ¬P
Prova por contradição: P ≡ ¬P ⇒ f
Prova da proposição bicondicional
Prova por contra-exemplo: ¬∀x P(x) ≡ ∃x ¬P(x)
12
Prova directa:
Se um inteiro n é par, então n2 é par
1. n par um inteiro par qualquer
2. ∃m n=2m, m inteiro definição de par
3. n2=(2m)2
4. n2=2(2m2)
5. n2 é um inteiro par
6. ∀n par: n2 é um inteiro par generalização universal (1)
Prova pela contra-positiva:
Se para um inteiro n, n2 é par, então n é par
1. n ímpar um inteiro ímpar qualquer
2. ∃m n=2m+1, m inteiro definição de ímpar
3. n2=(2m+1)2
4. n2=2(2m2+2m) + 1
5. n2 é um inteiro ímpar
6. n2 par → n par contra-positiva (1 ... 5)
7. ∀n: n2 par → n par generalização universal (1)
13
Indução matemática:
S(n) é uma proposição respeitante ao inteiro positivo n. Se
1. S(1) é verdade
2. S(k) é verdade → S(k+1) é verdade
então S(n) é verdade para qualquer inteiro positivo n.
Segunda formulação:
S(n) é uma proposição respeitante ao inteiro positivo n. Se
1. S(1) é verdade
2. (S(1) ∧ S(2) ∧ ... ∧ S(k)) é verdade → S(k+1) é verdade
então S(n) é verdade para qualquer inteiro positivo n.
Definição indutiva:
definir A1, A2, ..., Ar
para k>r, ´definir Ak em função de A1, A2, ... Ak-1
14
Provar que para qualquer n inteiro positivo 5n-1 é divisível por 4:
1. n=1: 5n-1=5-1=4 é múltiplo de 4
2. Se é verdade para n = k
5k-1 é multiplo de 4
∃m: 5k-1=4m
5(5k-1)=5(4m)
5k+1-5=5(4m)
5k+1-1=5(4m)+4
5k+1-1=(5m+1)4
5k+1-1 é múltiplo de 4
é verdade para n = k + 1
	Matemática Discreta