Slides 06 0607

Prévia do material em texto

Matemática Discreta
Aula nº 6
Francisco Restivo
2007-03-14
2
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|
3
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| 
4
Problema:
Numa escola há 100 alunos. 65 alunos estudam Matemática, 45 
estudam Electrónica, 42 estudam Direito, 20 estudam 
Matemática e Electrónica, 25 estudam Matemática e Direito e 15 
estudam Electrónica e Direito.
Quantos alunos estudam as três disciplinas? E só Electronica?
x
D
25-x 15-x
20-x
20+x 10+x
2+x
65-(20-x)-(x-(25-x)=20+x
20+x+10+x+2+x+20-x+15-x+25-x+x=100
x=8
8 estudam as três disciplinas
18 estudam só electrónica
M E
5
Álgebra dos conjuntos (1)
Leis da Idempotência
A ∩ A = A
A ∪ A = A
Leis Comutativas
A ∩ B = B ∩ A
A ∪ B = B ∪ A 
Leis Associativas
(A ∩ B) ∩ C = A ∩ (B ∩ C)
(A ∪ B) ∪ C = A ∪ (B ∪ C) 
6
Álgebra dos conjuntos (2)
Leis da Absorção
A ∩ (A ∪ B) ≡ A
A ∪ (A ∩ B) ≡ A
Leis Distributivas
A ∩ (B ∪ C) ≡ (A ∩ B) ∪ (A ∩ C)
A ∪ (B ∩ C) ≡ (A ∪ B) ∩ (A ∪ C)
Leis de de Morgan
~(A ∪ B) ≡ ~A ∩ ~B
~(A ∩ B) ≡ ~A ∪ ~B
Lei da Involução
~(~A) ≡ A
7
Álgebra dos conjuntos (3)
Identidade
A ∪ ∅ ≡ A A ∩ U ≡ A
A ∪ U ≡ U A ∩ ∅ ≡ ∅
Complemento
A ∪ ~A ≡ U A ∩ ~A ≡ ∅
~∅ ≡ U ~U ≡ ∅
Princípio da Dualidade 
Se uma proposição é verdadeira, a 
sua dual também o é
Proposição dual
(∩, ∪, U, ∅) ⇔ (∪, ∩, ∅, U)
8
Famílias de conjuntos
Índices
I = {1, 2, 3, ..., n}
Z
R
Intersecção e união de famílias 
∪Ai = {x: ∃Ai, x ∈ Ai}
i∈I
∩Ai = {x: ∀Ai, x ∈ Ai}
i∈I
Famílias (conjuntos)
{Ai: i ∈ I} = {A1, A2, A3, ..., An}
{Ar: r ∈ Z+} = {A1, A2, A3, ...}
9
Conjunto potência
Conjunto de todos os subconjuntos de um conjunto
P(A) = {B: B ⊆ A}
Exemplo: 
A = {1, 2, {1}}
P(A) = {∅, {1}, {2}, {{1}}, {1, 2}, {1, {1}}, {2, {1}}, A}
Teoremas
A ⊆ B se e só se P(A) ⊆ P(B)
P(A) ∩ P(B) = P(A ∩ B)
P(A) ∪ P(B) = P(A ∪ B)
Se |A| = n então |P(A)| = 2n
10
Partição de um conjunto
Conjunto de subconjuntos não vazios de um conjunto 
que não se intersectam e cuja reunião é o conjunto dado
∪Si = A
i∈I
Si ∩ Sj = ∅, ∀i,j∈I, i≠j
A segunda condição: intersecção vazia dois a dois
A = {1, 2, 3}
A1 = {1, 2}, A2 = {2,3}, A3 = {1, 3}
não é uma partição de A
Não é suficiente que seja
A1 ∩ A2 ∩ A3 = ∅
Quantas partições há do conjunto {a, b, c, d}?
11
Há 15:
1 com quatro subconjuntos
6 com três subconjuntos
7 com dois subconjuntos
1 com um subconjunto
12
Produto cartesiano de dois conjuntos
O produto cartesiano de dois conjuntos X e Y é o 
conjunto XxY de pares ordenados de elementos (x, y) 
em que x ∈ X e y ∈ Y:
X x Y = {(x, y): x ∈ X ∧ y ∈ Y}
Se um dos conjuntos é vazio, o produto cartesiano 
também
•A
•B
•C
•(A,1)
•(B,1)
•(C,1)
•(A,2)
•(B,2)
•(C,2)
•1 •2
13
Produto cartesiano de dois conjuntos
O produto cartesiano dos conjuntos X1, X2, ..., Xn é o conjunto 
X1xX2x...xXn de n-tuplos ordenados de elementos (x1, x2, ..., xn) 
em que x1 ∈ X1, x2 ∈ X2, ..., xn ∈ Xn
X1 x X2 x ... Xn = {(x1, x2, ..., xn): xi ∈ Xi ∀i=1, 2, ...., n}
Teorema
|X1 x X2 x ... Xn| = |X1| x |X2| x ... |Xn|
Produtividade e distributividade
A x (X ∩ Y) = (A x X) ∩ (A x Y)
A x (X ∪ Y) = (A x X) ∪ (A x Y)
∀X, A ⊆ B se e só se (A x X) ⊆ (B x X)
	Matemática Discreta