Slides 06

Prévia do material em texto

1
Matemática Discreta
Aula nº 6
Francisco Restivo
2006-03-17
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
2
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.
3
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 = { } = F
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
|F | = 0
|{x: (x + 1)(x - 3) = 0}| = 2
|{1, 2, 3, 4, ...}| = ¥
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
F é um subconjunto de qualquer conjunto A: "A F Í 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}
5
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}
6
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)
7
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|