Buscar

Slides 08

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 6 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 6 páginas

Prévia do material em texto

1
Matemática Discreta
Aula nº 8
Francisco Restivo
2006-03-24
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 = F , "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 = F
Quantas partições há do conjunto {a, b, c, d}? 15
2
3
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
4
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 pré-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.
3
5
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.
6
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]
4
7
Propriedades
A = {1, 2, 3} é do tipo A: Set[Inteiro]
P(A) = {F , {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]
8
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
F Í {1, 2, 3} implica que F é 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
5
9
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)
10
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
6
11
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 × y
Não diz como é realizada a operação. Não interessa.
12
Problema:
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: Person p=DonoDe(a) Ù p=DonoDe(b)
Descreva f.

Outros materiais