Slides 05

Prévia do material em texto

1
Matemática Discreta
Aula nº 5
Francisco Restivo
2006-03-16
2
Regras de inferência para quantificadores:
Especificação do 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 do existencial: 
se $x F(x) é verdade, então existe um elemento a tal que F(a) 
é verdade
Generalização existencial: 
se existe um elemento a tal que F(a) é verdade, então $x F(x) 
é verdade
2
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
4
Uma 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 do universal (1)
4. ¬C(a) Modus ponens (3, 2)
O argumento é válido, uma vez que a veracidade 
de cada uma das proposições está garantida.
3
5
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 do existencial (1)
4. M(a) Simplificação (3)
5. M(a) ® P(a) Especificação do 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
6
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
4
7
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...
8
Permite pensar melhor...
Também pode ser!
5
9
Agora já será fácil provar o teorema!
Teorema: há pelo menos três clogues
10
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)
6
11
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)
12
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
7
13
Provar que para qualquer n inteiro positivo 5n-1 é divisível por 4:
1. k=1: 5k-1=5-1=4 é múltiplo de 4
2. Se 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