Relações Binárias II

Prévia do material em texto

1
Matemática Discreta
Aula nº 9
Francisco Restivo
2006-03-30
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)}
2
3
Representações gráficas
A = B = {1, 2, 3, 4, 5, 6}
R = {(a, b): a divide b}
2 divide 4
grelha bidimensional 654321
x1
xx2
xx3
xxx4
xx5
xxxx6
A = {Deco, Figo, Lucho}
B = {Porto, Benfica, Barcelona}
R = {(a, b): a joga em b}
Deco joga no Barcelona
diagrama de setas
Deco
Figo
Lucho
Porto
Benfica
Barcelona
4
Representações gráficas
A = B = {1, 2, 3, 4, 5, 6}
R = {(a, b): a divide b}
3 divide 6
grafo orientado | digrafo
A = B = {1, 2, 3, 4, 5, 6}
R = {(a, b): a divide b}
a nas linhas e b nas colunas
3 divide 3 e 3 divide 6
matriz binária
1
6
2
3 4
5
ú
ú
ú
ú
ú
ú
ú
ú
û
ù
ê
ê
ê
ê
ê
ê
ê
ê
ë
é
100000
010000
001000
100100
101010
111111
3
5
Conjuntos tipificados
Se R é uma relação entre A e B
A: Set[S]
B: Set[T]
R: Set[S´T]
Exemplo:
Elementos de R?
{(a,c), (a,d), (a,e), (b,e), (c,a), (c,b), (d,c), (d,e), (e,a), (e,b)}
Matriz binária:
a
b c
e d
ú
ú
ú
ú
ú
ú
û
ù
ê
ê
ê
ê
ê
ê
ë
é
00011
10100
00011
10000
11100
6
Propriedades das relações:
Se R for uma relação num conjunto A, define-se
Reflexiva se e só se "aÎA, aRa
Simétrica se e só se "a,bÎA, aRb ® bRa
Anti-simétrica se e só se "a,bÎA, aRb Ù bRa ® a = b
Transitiva se e só se "a,b,cÎA, aRb Ù bRc ® a R c
Exemplo:
No conjunto dos números reais, xRy se e só se x £ y
Reflexiva? Sim
Simétrica? Não (contra-exemplo: x=1 e y=2)
Anti-simétrica? Sim
Transitiva? Sim
4
7
Outro exemplo:
A = {a, b, c, d}
R = {(a,a), (a,b), (a,c), (b,a), (b,b), (b,c), (b,d), (d,d)}
Reflexiva? Não: ¬(cRc)
Simétrica? Não: aRc mas ¬(cRa)
Anti-simétrica? Não: aRb e bRa mas a¹b
Transitiva? Não: aRb e bRd mas ¬(aRd)
Mais um exemplo:
Em Z+ ´ Z+, (a, b)R(c, d) se e só se a + d = b + c
Propriedades: Reflexiva, Simétrica, Transitiva
Anti-simétrica? (1, 2)R(2, 3) e (2, 3)R(1, 2) mas (1, 2)¹(2, 3)
8
Intersecção e união de relações:
Uma vez que uma relação é um conjunto, podemos definir a 
intersecção e a união de relações.
Se as relações R e S entre os conjuntos A e B são subconjuntos 
do conjunto A ´ B, então R Ç S e R È S também o são.
Propriedades:
Se R e S são reflexivas, então R Ç S e R È S também o são
Se R e S são simétricas, então R Ç S e R È S também o são
Se R e S são anti-simétricas, então R Ç S também o é, mas 
nada sabemos sobre R È S
Se R e S são transitivas, então R Ç S também o é, mas nada 
sabemos sobre R È S
5
9
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
10
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
11
Dois teoremas:
Numa relação de equivalência R num conjunto A,
"x,yÎA, [x] = [y] se e só se xRy
Numa relação de equivalência R num conjunto A não vazio, a 
família das classes de R-equivalência distintas é uma partição 
de A.
Exemplo:
No conjunto dos números reais, xRy se e só se têm a mesma 
parte inteira ëxû = ëyû
É uma relação de equivalência? Sim
Quais são as classes de equivalência?
{[n, n+1[: n Î Z}
Constituem uma partição? Sim
12
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]
Outro teorema:
Uma partição {Si: i Î I} de um conjunto A define uma relação de 
equivalência: xRy se e só se $i Î I, x,y Î Si