Slides 05 0607

Prévia do material em texto

Matemática Discreta
Aula nº 5
Francisco Restivo
2007-03-08
2
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
3
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 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
então 5k+1-1 é múltiplo de 4
4
Pode provar-se pelo método da indução:
i) É verdade para n = 1
ii) Se for verdade para n = k então é verdade 
para n = k + 1
n = 1
n = k
n = k + 1
Provar que um quadrado com área 2nx2n pode 
ser coberto com peças em L como mostra a 
figura, sobrando um quadrado num dos vértices.
5
Teoria dos conjuntos:
Um conjunto é uma colecção de objectos. Os objectos são 
os elementos do conjunto.
Se o elemento a pertence ao conjunto B escreve-se
a∈B
Definição por listagem:
A = {Estádio do Dragão, 3, Vénus de Milo}
B = {1, 2, 3, 4, ...}
C = {2, 4, 6, ..., 20}
D = { } = Φ
Definição por um predicado:
E = {x: P(x)}
6
Igualdade de conjuntos:
Dois conjuntos são iguais se e só se contiverem os mesmos 
elementos:
A = B se ∀x (x∈A ↔ x∈B)
Conjuntos iguais:
{1, 2, 3, 4, 5} = {5, 4, 3, 2, 1}
{x: (x - 1)2 = 4} = {x: (x + 1)(x - 3) = 0} = {-1, 3}
Cardinalidade de um conjunto:
Número de elementos distintos do conjunto
|∅| = 0
|{x: (x + 1)(x - 3) = 0}| = 2
|{1, 2, 3, 4, ...}| = ∞
7
Subconjuntos:
O conjunto A é um subconjunto do conjunto B se todos os 
elementos de A forem elementos de B:
A ⊆ B se ∀x (x∈A → x∈B)
Subconjuntos próprios:
Um conjunto é subconjunto dele próprio: B ⊆ B
Todos os outros subconjuntos de B são subconjuntos 
próprios de B: A ⊂ B 
A ⊂ B se e só se A ⊆ B e A ≠ B
∅ é um subconjunto de qualquer conjunto A: ∀A (∅ ⊆ A)
Teorema:
Dois conjuntos A e B são iguais se e só se A ⊆ B e B ⊆ A
8
Conjunto universal:
O conjunto universal contem como subconjuntos todos os 
conjuntos de interesse ao nosso estudo. Exemplos
N = {0, 1, 2, 3, ...} – números naturais
Z = {..., -2, -1, 0, 1, 2, ...} – números inteiros
Q = {p / q: p, q ∈ Z e q ≠ 0} – números racionais
R – números reais
C = {x + iy: x, y ∈ R e i2 = -1} – números complexos
Problemas:
Quantos subconjuntos tem um conjunto A com n elementos?
A = {1, 2, 3, 4}. Determine a cardinalidade de 
{B: B ⊆ A e |B| = 2}
{B: B ⊆ A e {1, 2} ⊆ B}
9
Diagramas de Venn
A ⊂ B
B
A
1
4
7
3
2
59
0
8
6
A B
C
A = {1, 2, 3, 4, 7, 9}
B = {2, 3, 5, 6}
C = {0, 2, 5, 8, 9}
10
Intersecção de conjuntos
A ∩ B = {x: x ∈ A e x ∈ B}
11
Reunião de conjuntos
A ∪ B = {x: x ∈ A ou x ∈ B}
12
Outras operações
A - B = {x: x ∈ A e x ∉ B} = A ∩ ¬B¬A 
A – (B ∩ C)
13
Técnicas de contagem
Primeiro princípio:
Se os conjuntos A e B são disjuntos:
|A ∪ B| = |A| + |B|
Teorema:
Para dois conjuntos A e B finitos
|A ∪ B| = |A| + |B| - |A ∩ B|
14
Técnicas de contagem
Teorema:
Para três conjuntos A, B e C finitos
|A ∪ B ∪ C| = 
= |A| + |B| + |C| - |A ∩ B| - |B ∩ C| - |C ∩ A| + |A ∩ B ∩ C| 
15
Problema
Numa consulta a 1000 donos de casa, 275 possuíam 
computador, 455 um vídeo, 405 dois carros e 265 não 
possuíam computador nem vídeo nem dois carros. 
Sabendo que 145 possuíam um computador e um vídeo, 195 um 
vídeo e dois carros e 110 possuíam dois carros e um 
computador, determine quantos deles possuíam:
a. Um computador, um vídeo e dois carros.
b. Só o vídeo.
c. Dois carros, um vídeo e não computador.
d. Um vídeo, um computador e não dois carros.
1000-265=275+455+405-145-195-110+x ⇒ x=50
50
265
C V
D
	Matemática Discreta