Slides 09 0607

Prévia do material em texto

Matemática Discreta
Aula nº 9
Francisco Restivo
2007-03-28
2
Relações e suas representações
Uma relação (binária) R entre (os conjuntos) A e B é um 
subconjunto do produto cartesiano A × B
R ⊆ A × B
Exemplos:
x é a Mãe de y 
x é maior que y
x é a capital de y
Representação:
R = {(a, b): a é a capital do País b}
a R b ↔ (a, b) ∈ R
A = {Porto, Lisboa, Madrid}
B = {Portugal, Espanha, Brasil}
R = {(Lisboa, Portugal), (Madrid, Espanha)}
3
Composição de relações:
A composição de R e S é uma relação S°R assim definida
a(S°R)c se e só se ∃b, aRb ∧ bRc
aRb bSc
a(S°R)c
Exemplo:
xRy se e só se x é a Mãe de y
xSy se e só se x é o Pai de y
Quais são as relações compostas S°R e R°S?
Avó paterna e avô materno
4
Composição de relações pelo produto das matrizes:
a(S°R)c se e só se ∃b, aRb ∧ bRc
00100
00121
00110
00100
00011
01001
00110
1000
0101
0001
=x
00100
00111
00110
5
Relação de equivalência:
É uma relação que é reflexiva, simétrica e transitiva.
Relações de equivalência e partições são conceitos relacionados.
Uma relação de equivalência, no conjunto das pessoas vivas:
xRy se e só se residem no mesmo País.
É reflexiva (aRa), simétrica (se aRb então bRa) e transitiva (se 
aRb e bRc então aRc).
A relação R divide o conjunto das pessoas vivas em partições, 
cada uma das quais corresponde a um País.
Numa relação R num conjunto A, classe de equivalência de um 
elemento x é o conjunto de todos os elementos de A que estão 
relacionados com x:
[x] = {y ∈ A: x R y}
6
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]
+ 0 1 2 3 4
0 0 1 2 3 4
1 1 2 3 4 0
2 2 3 4 0 1
3 3 4 0 1 2
4 4 0 1 2 3
x 0 1 2 3 4
0 0 0 0 0 0
1 0 1 2 3 4
2 0 2 4 1 3
3 0 3 1 4 2
4 0 4 3 2 1
7
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)
8
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!
9
Máximo e mínimo:
Se A for um conjunto parcialmente ordenado pela relação R, o 
elemento máximo de A é o elemento α tal que ∀a∈A, aRα.
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.
10
{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.
11
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.
12
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
13
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
14
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.
	Matemática Discreta