Slides 10

Prévia do material em texto

1
Matemática Discreta
Aula nº 10
Francisco Restivo
2006-03-31
2
Aritmética modular:
A relação congruência módulo n, definida no conjunto dos 
inteiros, é uma relação de equivalência
a ºn b se e só se a – b é um múltiplo de n
Os restos da divisão de a e de b por n são iguais.
Há n classes de equivalência distintas: [0], [1], ..., [n – 1]
Operações em Z / n:
Soma: [a] +n [b] = [a + b]
Multiplicação: [a] ´n [b] = [a.b]
321044
210433
104322
043211
432100
43210+
123404
241303
314202
432101
000000
43210x
2
3
Relação de ordem parcial:
É uma relação que é reflexiva, anti-simétrica e transitiva.
A relação no conjunto dos números reais xRy se e só se x £ y é
uma relação de ordem parcial:
É reflexiva (aRa), anti-simétrica (se aRb e bRa então a = b) e 
transitiva (se aRb e bRc então aRc).
A relação no conjunto dos números reais xRy se e só se x < y
não é: Não é reflexiva.
Outra relação de ordem parcial, no conjunto dos inteiros 
positivos: nRm se e só se n divide m (n | m)
Reflexiva: n | n
Anti-simétrica: se n | m e m | n, então n = m
Transitiva: se n | m e m | p então n | p (a prova é muito simples)
4
Teorema:
Qualquer subconjunto de um conjunto parcialmente ordenado é
um subconjunto parcialmente ordenado:
Se R for uma relação de ordem parcial em A e B um 
subconjunto de A, então S = R Ç (B ´ B) é uma relação de 
ordem parcial em B.
Elementos maximais e minimais:
A relação £ é uma relação de ordem parcial em qualquer 
subconjunto do conjunto dos números reais (teorema anterior).
No conjunto [0, 1], por exemplo, há um elemento que é o maior 
de todos (máximo) e um outro que é o menor de todos (mínimo). 
No entanto, no conjunto ]0, 1[ não há!
No conjunto de todos os subconjuntos próprios de {a, b, c} 
ordenado parcialmente pela relação Í há um elemento mínimo, 
mas não há um elemento máximo! {a, b}, {a, c}, {b, c} não são!
3
5
Máximo e mínimo:
Se A for um conjunto parcialmente ordenado pela relação R, o 
elemento máximo de A é o elemento a tal que "aÎA, aRa.
Se A for um conjunto parcialmente ordenado pela relação R, o 
elemento mínimo de A é o elemento ß tal que "aÎA, ßRa.
Máximal e mínimal:
Se A for um conjunto parcialmente ordenado pela relação R, um 
elemento maximal de A é qualquer elemento x tal que "aÎA, se 
xRa então a = x.
Se A for um conjunto parcialmente ordenado pela relação R, um 
elemento minimal de A é qualquer elemento y tal que "aÎA, se 
aRy então a = y.
Num certo sentido, não há elemento ‘maior’ que um elemento 
maximal nem há elemento ‘menor’ que um elemento minimal.
6
{a, b} {a, c} {b, c}
{a} {b} {c}
?
No conjunto de todos os subconjuntos próprios de {a, b, c} 
ordenado parcialmente pela relação Í, {a, b}, {a, c}, {b, c} são 
elementos maximais.
Teorema:
Num conjunto A parcialmente ordenado pela relação R, 
se houver elemento máximo de A então é elemento maximal e não 
há outros;
se houver elemento mínimo de A então é elemento minimal e não 
há outros.
4
7
Relação de ordem total (ou linear):
Se A for um conjunto parcialmente ordenado pela relação R, e 
satisfizer a lei da dicotomia
"a,bÎA, aRb Ú bRa
então diz-se que se trata de uma relação de ordem total.
Realmente, a lei da dicotomia implica que a relação é reflexiva, pelo que há
uma certa redundância nesta definição...
Exemplos:
A relação £ no conjunto dos inteiros é uma relação de ordem total.
A relação divide no conjunto A = {1, 2, 3, 4, 6, 12} dos divisores de 
12 não é uma relação de ordem total: 2 e 3, por exemplo, não se 
relacionam. 
Alguns subconjuntos de A são-no: {1, 2, 4, 12}, {1, 3, 6, 12} dizem-
se cadeias.
8
Diagramas de Hasse:
Num conjunto A parcialmente ordenado pela relação R, diz-se que 
o elemento b cobre o elemento a se aRb e não existe nenhum 
elemento c tal que aRc e cRb:
"xÎA, (aRx Ù xRb) ® (a = x Ú x = b) 
O diagrama de Hasse representa esta propriedade: um elemento 
num nível superior cobre o de nível inferior.
Exemplo:
O conjunto {1, 2, 3, 4, 5, 6} ordenado pela divisibilidade.
4 6
2 3 5
1
5
9
Teorema:
Um conjunto A parcialmente ordenado contem pelo menos um elemento 
minimal. Se for único, é o elemento mínimo.
Do mesmo modo, Um conjunto A parcialmente ordenado contem pelo 
menos um elemento maximal. Se for único, é o elemento máximo.
Exemplo:
R = {(a,a), (b,b), (c,c), (p,p), (q,q), (x,x), (y,y), (a,p), (b,q), (c,q), 
(x,a), (x,b), (x,p), (x,q), (y,b), (y,c), (y,q)}
p q
a b c
x y
10
Aplicação às bases de dados relacionais:
Os dados são classificados em componentes (headings) e em 
atributos (fields). Cada atributo tem um tipo específico:
nome: String
endereço: Endereço
telefone: Inteiro
contribuição: Quantia
data: Data
Definição:
Sejam A1, A2, …, An uma colecção de atributos e Xi o conjunto 
de dados associado ao atributo Ai, do tipo Set(Ti).
Uma base de dados relacional com atributos A1, A2, …, An é um 
conjunto de relações entre os conjuntos Xi. Cada relação R Í
Xi1´Xi2´…´ Xim é uma tabela. Cada elemento é um registo e é
do tipo Ti1´Ti2´...´Tim.