Baixe o app para aproveitar ainda mais
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.
Compartilhar