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