Buscar

Relações em Conjunto

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 57 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 57 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 9, do total de 57 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

Prévia do material em texto

Relações
Renato Ramos da Silva
Universidade Federal de Lavras
renato.ramos@dcc.ufla.br
5 de outubro de 2015
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 1 / 49
Overview
1 Introdução
2 Relações em Conjunto
3 Representação de relações
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 2 / 49
Combinando Relações
Sejam os conjuntos
1 A = {1, 2, 3}
2 B = {1, 2, 3, 4}
As relações de A em B
1 R1 = {(1, 1), (2, 2), (3, 3)}
2 R2 = {(1, 1), (1, 2), (1, 3), (1, 4)}
As operações sobre as relações
R1 ∪ R2 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (3, 3)}
R1 ∩ R2 = {(1, 1)}
R1 − R2 = {(2, 2), (3, 3)}
R2 − R1 = {(1, 2), (1, 3), (1, 4)}
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 3 / 49
Exemplo
Exemplo
Seja R1 a relação “menor que” sobre os conjuntos dos reais e R2 a
relação “maior que” sobre o mesmo conjunto.
Assim
R1 = {(x , y)|x < y}
R2 = {(x , y)|x > y}
Encontre R1 ∪ R2,R1 ∩ R2,R1 − R2,R2 − R1 e R2 ⊕ R1.
R1 ∪ R2 = {(x , y)|x < y ou x > y} = {(x , y)|x 6= y}
R1 ∩ R2 = ∅
R1 − R2 = R1
R2 − R1 = R2
R1 ⊕ R2 = R1 ∪ R2 − R1 ∩ R2 = {(x , y)|x 6= y}
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 4 / 49
Exemplo
Exemplo
Seja R1 a relação “menor que” sobre os conjuntos dos reais e R2 a
relação “maior que” sobre o mesmo conjunto.
Assim
R1 = {(x , y)|x < y}
R2 = {(x , y)|x > y}
Encontre R1 ∪ R2,R1 ∩ R2,R1 − R2,R2 − R1 e R2 ⊕ R1.
R1 ∪ R2 = {(x , y)|x < y ou x > y} = {(x , y)|x 6= y}
R1 ∩ R2 = ∅
R1 − R2 = R1
R2 − R1 = R2
R1 ⊕ R2 = R1 ∪ R2 − R1 ∩ R2 = {(x , y)|x 6= y}
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 4 / 49
Exemplo
Exemplo
Seja R1 a relação “menor que” sobre os conjuntos dos reais e R2 a
relação “maior que” sobre o mesmo conjunto.
Assim
R1 = {(x , y)|x < y}
R2 = {(x , y)|x > y}
Encontre R1 ∪ R2,R1 ∩ R2,R1 − R2,R2 − R1 e R2 ⊕ R1.
R1 ∪ R2 = {(x , y)|x < y ou x > y} = {(x , y)|x 6= y}
R1 ∩ R2 = ∅
R1 − R2 = R1
R2 − R1 = R2
R1 ⊕ R2 = R1 ∪ R2 − R1 ∩ R2 = {(x , y)|x 6= y}
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 4 / 49
Exemplo
Exemplo
Seja R1 a relação “menor que” sobre os conjuntos dos reais e R2 a
relação “maior que” sobre o mesmo conjunto.
Assim
R1 = {(x , y)|x < y}
R2 = {(x , y)|x > y}
Encontre R1 ∪ R2,R1 ∩ R2,R1 − R2,R2 − R1 e R2 ⊕ R1.
R1 ∪ R2 = {(x , y)|x < y ou x > y} = {(x , y)|x 6= y}
R1 ∩ R2 = ∅
R1 − R2 = R1
R2 − R1 = R2
R1 ⊕ R2 = R1 ∪ R2 − R1 ∩ R2 = {(x , y)|x 6= y}
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 4 / 49
Exemplo
Exemplo
Seja R1 a relação “menor que” sobre os conjuntos dos reais e R2 a
relação “maior que” sobre o mesmo conjunto.
Assim
R1 = {(x , y)|x < y}
R2 = {(x , y)|x > y}
Encontre R1 ∪ R2,R1 ∩ R2,R1 − R2,R2 − R1 e R2 ⊕ R1.
R1 ∪ R2 = {(x , y)|x < y ou x > y} = {(x , y)|x 6= y}
R1 ∩ R2 = ∅
R1 − R2 = R1
R2 − R1 = R2
R1 ⊕ R2 = R1 ∪ R2 − R1 ∩ R2 = {(x , y)|x 6= y}
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 4 / 49
Exemplo
Exemplo
Seja R1 a relação “menor que” sobre os conjuntos dos reais e R2 a
relação “maior que” sobre o mesmo conjunto.
Assim
R1 = {(x , y)|x < y}
R2 = {(x , y)|x > y}
Encontre R1 ∪ R2,R1 ∩ R2,R1 − R2,R2 − R1 e R2 ⊕ R1.
R1 ∪ R2 = {(x , y)|x < y ou x > y} = {(x , y)|x 6= y}
R1 ∩ R2 = ∅
R1 − R2 = R1
R2 − R1 = R2
R1 ⊕ R2 = R1 ∪ R2 − R1 ∩ R2 = {(x , y)|x 6= y}
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 4 / 49
Composta
Definição
Seja R uma relação de A em B e S uma relação de B em C.
A composta de R e S é a relação que consiste dos pares ordenados
(a, c), tal que a ∈ A e c ∈ C e para a qual existe um elemento b ∈ B
de forma que (a, b) ∈ R e (b, c) ∈ S .
A composição de R e S e denotada por S ◦ R
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 5 / 49
Exemplo
Qual é a composição de R e S sabendo que
R = {(1, 1), (1, 4), (2, 3), (3, 1), (3, 4)}
S = {(1, 0), (2, 0), (3, 1), (3, 2), (4, 1)}
S ◦ R = {(1, 0), (1, 1), (2, 1), (2, 2), (3, 0), (3, 1)}
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 6 / 49
Exemplo
Qual é a composição de R e S sabendo que
R = {(1, 1), (1, 4), (2, 3), (3, 1), (3, 4)}
S = {(1, 0), (2, 0), (3, 1), (3, 2), (4, 1)}
S ◦ R = {(1, 0), (1, 1), (2, 1), (2, 2), (3, 0), (3, 1)}
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 6 / 49
Relações binárias
Definição
Sejam X e Y dois conjuntos.
Uma relação entre X e Y é um subconjunto de produto cartesiano
X × Y .
No caso de X = Y, a uma relação R X × X entre X e X chama-se
relação (binária) sobre X.
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 7 / 49
Relações sobre mesmo conjunto
Definição
Seja R uma relação sobre um conjunto A. As potências Rn, n = 1, 2, 3, ...,
são definidas recursivamente por
R1 = R e Rn+1 = Rn ◦ R
Assim,
R3 = R2 ◦ R = (R ◦ R) ◦ R
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 8 / 49
Exemplo
Seja R = {(1, 1), (2, 1)(3, 2), (4, 3)}
Encontre as potências Rn, n=1,2,3,..
R2 = {(1, 1), (2, 1)(3, 1), (4, 2)}
R3 = {(1, 1), (2, 1)(3, 1), (4, 1)}
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 9 / 49
Exemplo
Seja R = {(1, 1), (2, 1)(3, 2), (4, 3)}
Encontre as potências Rn, n=1,2,3,..
R2 = {(1, 1), (2, 1)(3, 1), (4, 2)}
R3 = {(1, 1), (2, 1)(3, 1), (4, 1)}
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 9 / 49
Exemplo
Seja R = {(1, 1), (2, 1)(3, 2), (4, 3)}
Encontre as potências Rn, n=1,2,3,..
R2 = {(1, 1), (2, 1)(3, 1), (4, 2)}
R3 = {(1, 1), (2, 1)(3, 1), (4, 1)}
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 9 / 49
Propriedade de Relações
Reflexiva
Uma relação R em um conjunto A é chamada de reflexiva se (a, a) ∈ R
para o elemento a ∈ A
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 10 / 49
Propriedade de Relações
Exemplo
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}
R2 = {(1, 1), (1, 2), (2, 1)}
R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)}
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}
R5 =
{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}
R6 = {(3, 4)}
Qual dessas relações é reflexiva?
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 11 / 49
Propriedade de Relações
Exemplo
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}
R2 = {(1, 1), (1, 2), (2, 1)}
R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)}
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}
R5 =
{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}
R6 = {(3, 4)}
Qual dessas relações é reflexiva?
R3 e R5
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 12 / 49
Propriedade de Relações
Simétrica
Uma relação R em um conjunto A é chamada de simétrica se (b, a) ∈ R
sempre que (a, b) ∈ R , para quaisquer a, b ∈ R
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 13 / 49
Propriedade de Relações
Exemplo
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}
R2 = {(1, 1), (1, 2), (2, 1)}
R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)}
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}
R5 =
{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}
R6 = {(3, 4)}
Qual dessas relações é simétrica?
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 14 / 49
Propriedade de Relações
Exemplo
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}
R2 = {(1, 1), (1, 2), (2, 1)}
R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)}
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}
R5 =
{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4),(3, 3), (3, 4), (4, 4)}
R6 = {(3, 4)}
Qual dessas relações é simétrica? R2 e R3
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 15 / 49
Propriedade de Relações
Anti-Simétrica
Uma relação R em um conjunto A tal que para quaisquer a, b ∈ A, se
(a, b) ∈ R e (b, a) ∈ R , então a=b é chamada de anti-simétrica
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 16 / 49
Propriedade de Relações
Exemplo
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}
R2 = {(1, 1), (1, 2), (2, 1)}
R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)}
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}
R5 =
{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}
R6 = {(3, 4)}
Qual dessas relações é anti-simétrica?
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 17 / 49
Propriedade de Relações
Exemplo
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}
R2 = {(1, 1), (1, 2), (2, 1)}
R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)}
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}
R5 =
{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}
R6 = {(3, 4)}
Qual dessas relações é anti-simétrica? R4, R5 e R6
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 18 / 49
Propriedade de Relações
Assimétrica
Uma relação R em um conjunto A é chamada de assimétrica se (a, b) ∈ R
e (b, a) 6∈ R , para quaisquer a, b ∈ A.
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 19 / 49
Propriedade de Relações
Exemplo
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}
R2 = {(1, 1), (1, 2), (2, 1)}
R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)}
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}
R5 =
{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}
R6 = {(3, 4)}
Qual dessas relações é assimétrica?
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 20 / 49
Propriedade de Relações
Exemplo
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}
R2 = {(1, 1), (1, 2), (2, 1)}
R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)}
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}
R5 =
{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}
R6 = {(3, 4)}
Qual dessas relações é assimétrica? R4 e R6
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 21 / 49
Propriedade de Relações
Transitiva
Uma relação R em um conjunto A é chamada de transitiva se, sempre que
(a, b) ∈ R e (b, c) ∈ R , então (a, c) ∈ R para todo a, b, c ∈ A.
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 22 / 49
Propriedade de Relações
Exemplo
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}
R2 = {(1, 1), (1, 2), (2, 1)}
R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)}
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}
R5 =
{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}
R6 = {(3, 4)}
Qual dessas relações é transitiva?
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 23 / 49
Propriedade de Relações
Exemplo
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}
R2 = {(1, 1), (1, 2), (2, 1)}
R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)}
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}
R5 =
{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}
R6 = {(3, 4)}
Qual dessas relações é transitiva? R4, R5 e R6
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 24 / 49
Formas de representar
Formas de representar uma relação
Através de matriz de adjacências
Através de diagramas
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 25 / 49
Matriz de adjacências
A matriz de adjacências de R é a matriz A = [aij ]n×n ∈ Mn×n({0, 1})
definida por
aij =
{
1 se (xi , xj) ∈ R
0 se (xi , xj) 6∈ R
nota
Note-se a importância da indexação dos elementos de X, para a construção
da matriz A.
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 26 / 49
Matriz de adjacências
Exemplo
Suponha que A = {1, 2, 3} e B ={1, 2}. Seja R a relação de A para B que
contém (a,b) se a ∈ A, b ∈ B e a > b. Qual é a matriz de adjacência que
representa a relação R se a1 = 1, a2 = 2 e a3 = 3, e b1 = 1 e b2 = 2?
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 27 / 49
Matriz de adjacências
Exemplo
Suponha que A = {1, 2, 3} e B ={1, 2}. Seja R a relação de A para B que
contém (a,b) se a ∈ A, b ∈ B e a > b. Qual é a matriz de adjacência que
representa a relação R se a1 = 1, a2 = 2 e a3 = 1, e b1 = 1 e b2 = 2?
solução
R = {(2, 1), (3, 1), (3, 2)}
MR =
0 01 0
1 1

Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 28 / 49
Diagrama
Exemplo
Os elementos de X são pontos do diagrama.
Dois pontos deste diagrama xi e xj estão unidos por uma seta de xi
para xj se o par (xi , xj) ∈ R .
Esquematicamente tem-se, se (xi , xj) ∈ R
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 29 / 49
Diagrama
Exemplo
X={1, 2, 3, 4}
R=(x , y) ∈ X 2 : x + y ≤ 5, foi visto que
R=(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (4, 1)
A Matrix de adjacência R é:
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 30 / 49
Diagrama
Exemplo
X={1, 2, 3, 4}
R=(x , y) ∈ X 2 : x + y ≤ 5, foi visto que
R=(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (4, 1)
A Matrix de adjacência R é:
MR =

1 1 1 1
1 1 1 0
1 1 0 0
1 0 0 0

Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 31 / 49
Diagrama
Exemplo
X={1, 2, 3, 4}
R=(x , y) ∈ X 2 : x + y ≤ 5, foi visto que
R=(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (4, 1)
E o diagrama de R é:
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 32 / 49
Diagrama
Exemplo
X={1, 2, 3, 4}
R=(x , y) ∈ X 2 : x + y ≤ 5, foi visto que
R=(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (4, 1)
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 33 / 49
Classificação de Relaçõs Binárias
S
ejam X um conjunto e R uma relação binária sobre X
Diz-se que R é uma relação
Reflexiva
Se xRx, para qualquer x ∈ X
Simétrica
Se xRy implica em yRx, para quaisquer
x , y ∈ X
Anti-simétrica
Se xRy e yRx implica x=y, para quaisquer
x , y ∈ X
Transitiva
Se xRy e yRz implica xRz, para quaisquer
x , y , z ∈ X
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 34 / 49
Fecho
Seja R uma relação sobre um conjunto.
R pode ou não possuir algumas propriedades P, tais como:
Reflexividade
Simetria
Transitividade
Uma relação S é o fecho de uma relação R com propriedade P se
S tem a propriedade P;
R ⊆ S ;
S é subconjunto de qualquer outra relação que inclua R e tenha a
propriedade P.
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 35 / 49
Fecho Reflexivo
A relação R={(1, 1), (1, 2), (2, 1), (3, 2)} sobre o conjunto A=1,2,3
não é reflexiva.
É possível construir uma relação reflexiva contendo R que seja a
menor possível?
Isso pode ser feito adicionando (2,2) e (3,3) a R.
Claramente, essa nova relação contém R e é reflexiva.
É chamada de fecho reflexivo de R.
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 36 / 49
Fecho Reflexivo
Exemplo
Qual é o fecho reflexivo de R = {(a, b)|a < b}, sobre o conjunto dos
inteiros?
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 37 / 49
Fecho Reflexivo
Exemplo
Qual é o fecho reflexivo de R = {(a, b)|a < b}, sobre o conjunto dos
inteiros?
ExemploO fecho reflexivo de R é
R ∪4 = {(a, b)|a < b} ∪ {(a, a)|a ∈ Z} = {(a, b)|a ≤ b}
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 38 / 49
Fecho Simétrico
A relação R={(1, 1), (1, 2), (2, 2), (2, 3), (3, 1), (3, 2)} sobre o
conjunto A=1,2,3 não é simétrica.
Como é possível construir uma relação simétrica contendo R que seja
a menor possível?
Isso pode ser feito adicionando (2,1) e (1,3) a R.
Essa nova relação é o fecho simétrico de R.
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 39 / 49
Fecho Simétrico
O feche simétrico de uma relação pode ser construído a partir da
união da relação com sua inversa.
Assim, R ∪ R−1 é o fecho simétrico de R
Sabendo que R−1 = {(a, b)|(b, a) ∈ R
Essa nova relação é o fecho simétrico de R.
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 40 / 49
Fecho Simétrico
Exemplo
Qual é o fecho simétrico da relação R = {(a, b)|a > b}, sobre o conjunto
dos inteiros positivos?
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 41 / 49
Fecho Simétrico
Exemplo
Qual é o fecho simétrico da relação R = {(a, b)|a > b}, sobre o conjunto
dos inteiros positivos?
Exemplo
O fecho simétrico da relação R é
R ∪ R−1 = {(a, b)|a > b} ∪ {(b, a)|a < b} = {(a, b)|a 6= b}
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 42 / 49
Fecho Transitivo
Suponha uma relação não transitiva R={(1, 3), (1, 4), (2, 1), (3, 2)}
sobre o conjunto A=1,2,3,4.
Ao inserir todos os pares (a,c), de forma que os (a,b) e (b,c)
pertençam a R, tem-se uma relação transitiva?
Os pares (a,c) são: (1,2),(2,3),(2,4) e (3,1).
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 43 / 49
Fecho Transitivo
Suponha uma relação não transitiva R={(1, 3), (1, 4), (2, 1), (3, 2)}
sobre o conjunto A=1,2,3,4.
Ao inserir todos os pares (a,c), de forma que os (a,b) e (b,c)
pertençam a R, tem-se uma relação transitiva?
Os pares (a,c) são: (1,2),(2,3),(2,4) e (3,1).
Adicionando esses pares não será produzido uma relação transitiva.
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 44 / 49
Fecho Transitivo
Teorema
O fecho transitivo de uma relação R é igual a R∗
R∗ =
∞⋃
n=1
An
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 45 / 49
Fecho Simétrico
Exemplo
Seja a relação R=(a,a),(a,b),(b,c),(c,c) sobre o conjunto A=a,b,c.
Encontre:
Fecho reflexivo de R;
Fecho simétrico de R;
Fecho transitivo de R.
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 46 / 49
Fecho Simétrico
Exemplo
Seja a relação R=(a,a),(a,b),(b,c),(c,c) sobre o conjunto A=a,b,c.
Encontre:
Fecho reflexivo de R;
Fecho simétrico de R;
Fecho transitivo de R.
Resposta
R ∪ {(b, b)}
R ∪ {(b, a), (c , b)}
R2 = {(a, a), (a, b), (a, c), (b, c), (c , c)}
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 47 / 49
Fecho Simétrico
Teorema
Seja MR a matriz zero-um da relação R sobre um conjunto com n
elementos.
Assim, a matriz do fecho transitivo de R∗ é
MR∗ = MR ∪M2R ∪M3R . . . ∪MnR
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 48 / 49
The End
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 49 / 49
	Introdução
	Relações em Conjunto
	Representação de relações

Outros materiais