Slides 07 0607

Prévia do material em texto

Matemática Discreta
Aula nº 7
Francisco Restivo
2007-03-15
2
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}? 15
3
Número de partições de um conjunto
O número de partições de um conjunto de n elementos é
conhecido por número de Bell.
Os primeiros números de Bell são
1, 2, 5, 15, 52, 203, 877, ...
Há uma fórmula recursiva para o cálculo do número de 
Bell
B4 = 1x1 + 3x1 + 3x2 + 1x5 = 15
4
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
5
Conjuntos tipificados
As operações definidas num conjunto requerem que as 
variáveis tenham um tipo pré-definido, e o seu resultado tem 
também um tipo definido:
Exemplo:
No conjunto dos inteiros, a operação ≤ requere dois inteiros e 
tem como resultado uma variável binária (booleana)
Inteiro, Inteiro→ Booleano
É a assinatura da operação.
A noção de tipo é muito importante em engenharia 
de software e em programação.
Alguns tipos comuns são Inteiro, Real, Booleano, 
String.
6
Assinaturas
Operações sobre o tipo Inteiro:
Adição _+_: Inteiro, Inteiro→ Inteiro
Subtracção _-_: Inteiro, Inteiro→ Inteiro
Multiplicação _x_: Inteiro, Inteiro→ Inteiro
Negação -_: Inteiro→ Inteiro
<, ≤, >, ≥ _<_: Inteiro, Inteiro→ Booleano
Divide _|_: Inteiro, Inteiro→ Booleano
Módulo |_|: Inteiro→ Inteiro
_ recebe um argumento
_+_ operação tipo infixo
-_ operação tipo prefixo
Pode repetir-se o exercício para os diferentes tipos.
7
Definição
Num conjunto tipificado, todos os elementos são do mesmo 
tipo:
{x: T | P(x)} conjunto de todos os elementos x do tipo T
tais que P(x) é verdade
{X: Real | x2 = 4} = {-2, 2}
Um conjunto cujos elementos são do tipo T diz-se 
do tipo Set[T]
A = {x: Pessoa | x foi PR de Portugal depois de 1974}
B = {x: Pessoa | x foi jogador do FCP campeão europeu}
C = {x: Pessoa | x nasceu em 11 de Janeiro}
A, B e C são do tipo Set[Pessoa]
8
Propriedades
A = {1, 2, 3} é do tipo A: Set[Inteiro]
P(A) = {Φ, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}} é do tipo 
Set[Set[Inteiro]]: é um conjunto de conjuntos de inteiros
O conjunto das cidades de Portugal? Assumimos 
a existência do tipo Cidade:
{x: Cidade | x está em Portugal}
Operações
As operações ∩, ∪ e - estão definidas em conjuntos tipificados
Intersecção _∩_: Set[T], Set[T] → Set[T]
Reunião _∪_: Set[T], Set[T] → Set[T]
Diferença _-_: Set[T], Set[T] → Set[T]
9
Mais assinaturas 
Subconjunto _⊆_: Set(T), Set(T) → Booleano
Pertença _∈_: T, Set(T) → Booleano
Conjunto potência P(_): Set(T) → Set(Set(T))
Cardinalidade |_|: Set(T) → Inteiro
Conjunto vazio pode ser tipificado
Φ ⊆ {1, 2, 3} implica que Φ é do tipo Set[Inteiro]
Verificação do tipo
Verificar para cada operação se a sua expressão respeita 
a respectiva assinatura
Pode ser no contexto de um programa de computador ou 
não
10
Exemplo
k, n, m: Inteiro
x, y: Real
P, Q: Booleano
Ana, Francisco: Pessoa
n ≥ m
(n ≥ m) + k
n + x
Ana MaisVelhaQue Francisco
n + Idade(Ana)
(x < y) ∨ (P → Q)
Idade(Ana) + 5 = Francisco
(x+y) ↔ (Francisco FilhoDe Ana)
11
Exemplo
k, n, m: Inteiro
x, y: Real
P, Q: Booleano
Ana, Francisco: Pessoa
n ≥ m sim
(n ≥ m) + k não
n + x não, mas... 1
Ana MaisVelhaQue Francisco sim
n + Idade(Ana) sim, se... 2
(x < y) ∨ (P → Q) sim
Idade(Ana) + 5 = Francisco não
(x+y) ↔ (Francisco FilhoDe Ana) não
1 se Inteiro for um subtipo de Real
2 depende da assinatura de Idade
12
Pré-condições e pós-condições
Numa operação, há o antes e o depois...
Pre-condições, têm de estar satisfeitas para ser possível 
realizar a operação
Pós-condições, verificam-se como resultado da operação
Exemplo: A divisão de números reais
Assinatura: _/_: Real, Real → Real
A assinatura não caracteriza completamente. Melhor é
_/_: x: Real, y: Real → r: Real
pre-condição: y ≠ 0
pós-condição: x = r x y
Não diz como é realizada a operação. Não interessa.
13
Problemas:
Está definido o tipo AnimalDoméstico.
Um animal doméstico tem um único dono (humano). Um humano 
pode possuir vários animais domésticos.
Assinaturas?
PertenceA(_)
DonoDe(_)
a: AnimalDoméstico
relação entre a e PertenceA(DonoDe(a))?
A operação TemAnimal: Pessoa → Booleano retorna V se a 
pessoa possui pelo menos um animal doméstico
pré- e pós-condições?
Uma operação f tem a assinatura 
f: a: AnimalDoméstico, b: AnimalDoméstico → Booleano
e a pós-condição 
f(a, b) ↔ ∃p: Pessoa p=DonoDe(a) ∧ p=DonoDe(b)
Descreva f.
	Matemática Discreta