Slide Relações-2021 2

Matemática Discreta Relações Professora: Lílian de Oliveira Carneiro Universidade Federal do Ceará Campus de Crateús Agosto de 2021 1 Introdução 2 Produto Cartesiano 3 Relações e suas Propriedades 4 Operações com Relações 5 Relações de Equivalências Relações Introdução Ligações entre elementos de conjuntos ocorrem em muitos contextos As ligações entre os elementos de conjuntos são representadas usando uma estrutura chamada de relação Relações podem ser usadas para resolver tais problemas: Quais pares de cidades são ligados por linhas aéreas em uma rede? Elaboração de um modo útil de armazenar informação em bancos de dados computacionais Relações Introdução Ligações entre elementos de conjuntos ocorrem em muitos contextos As ligações entre os elementos de conjuntos são representadas usando uma estrutura chamada de relação Relações podem ser usadas para resolver tais problemas: Quais pares de cidades são ligados por linhas aéreas em uma rede? Elaboração de um modo útil de armazenar informação em bancos de dados computacionais Relações Introdução Ligações entre elementos de conjuntos ocorrem em muitos contextos As ligações entre os elementos de conjuntos são representadas usando uma estrutura chamada de relação Relações podem ser usadas para resolver tais problemas: Quais pares de cidades são ligados por linhas aéreas em uma rede? Elaboração de um modo útil de armazenar informação em bancos de dados computacionais Relações Introdução Ligações entre elementos de conjuntos ocorrem em muitos contextos As ligações entre os elementos de conjuntos são representadas usando uma estrutura chamada de relação Relações podem ser usadas para resolver tais problemas: Quais pares de cidades são ligados por linhas aéreas em uma rede? Elaboração de um modo útil de armazenar informação em bancos de dados computacionais Relações Introdução Ligações entre elementos de conjuntos ocorrem em muitos contextos As ligações entre os elementos de conjuntos são representadas usando uma estrutura chamada de relação Relações podem ser usadas para resolver tais problemas: Quais pares de cidades são ligados por linhas aéreas em uma rede? Elaboração de um modo útil de armazenar informação em bancos de dados computacionais Produto Cartesiano Definição Dados dois conjuntos A e B não vazios, definimos o produto cartesiano entre A e B, denotado por A × B, como o conjunto de todos os pares ordenados da forma (x, y) onde x ∈ A e y ∈ B. Simbolicamente: A × B = {(x, y)|x ∈ A e y ∈ B} O símbolo A × B lê-se “A cartesiano B” ou produto cartesiano de “A por B” Se A = ∅ ou B = ∅, por definição: A × B = ∅ = B × A e ∅ × ∅ = ∅ Produto Cartesiano Definição Dados dois conjuntos A e B não vazios, definimos o produto cartesiano entre A e B, denotado por A × B, como o conjunto de todos os pares ordenados da forma (x, y) onde x ∈ A e y ∈ B. Simbolicamente: A × B = {(x, y)|x ∈ A e y ∈ B} O símbolo A × B lê-se “A cartesiano B” ou produto cartesiano de “A por B” Se A = ∅ ou B = ∅, por definição: A × B = ∅ = B × A e ∅ × ∅ = ∅ Produto Cartesiano Definição Dados dois conjuntos A e B não vazios, definimos o produto cartesiano entre A e B, denotado por A × B, como o conjunto de todos os pares ordenados da forma (x, y) onde x ∈ A e y ∈ B. Simbolicamente: A × B = {(x, y)|x ∈ A e y ∈ B} O símbolo A × B lê-se “A cartesiano B” ou produto cartesiano de “A por B” Se A = ∅ ou B = ∅, por definição: A × B = ∅ = B × A e ∅ × ∅ = ∅ Produto Cartesiano Definição Dados dois conjuntos A e B não vazios, definimos o produto cartesiano entre A e B, denotado por A × B, como o conjunto de todos os pares ordenados da forma (x, y) onde x ∈ A e y ∈ B. Simbolicamente: A × B = {(x, y)|x ∈ A e y ∈ B} O símbolo A × B lê-se “A cartesiano B” ou produto cartesiano de “A por B” Se A = ∅ ou B = ∅, por definição: A × B = ∅ = B × A e ∅ × ∅ = ∅ Produto Cartesiano Definição Dados dois conjuntos A e B não vazios, definimos o produto cartesiano entre A e B, denotado por A × B, como o conjunto de todos os pares ordenados da forma (x, y) onde x ∈ A e y ∈ B. Simbolicamente: A × B = {(x, y)|x ∈ A e y ∈ B} O símbolo A × B lê-se “A cartesiano B” ou produto cartesiano de “A por B” Se A = ∅ ou B = ∅, por definição: A × B = ∅ = B × A e ∅ × ∅ = ∅ Produto Cartesiano Definição Exemplos. Se A = {1, 2, 3} e B = {1, 2}, então: A × B = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 1), (3, 2)} Produto Cartesiano Definição Exemplos. Se A = {1, 2, 3} e B = {1, 2}, então: A × B = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 1), (3, 2)} Produto Cartesiano Definição Exemplos. Se A = {1, 2, 3} e B = {1, 2}, então: A × B = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 1), (3, 2)} Produto Cartesiano Definição Exemplos. Se A = {1, 2, 3} e B = {1, 2}, então: B × A = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 2)} Produto Cartesiano Definição Exemplos. Se A = {1, 2, 3} e B = {1, 2}, então: B × A = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 2)} Produto Cartesiano Definição Exemplos. Se A = {1, 2, 3} e B = {1, 2}, então: B × A = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 2)} Produto Cartesiano Definição Exemplos. Se A = {2, 3}, então: A × A = A2 = {(2, 2), (2, 3), (3, 2), (3, 3)} Produto Cartesiano Definição Exemplos. Se A = {2, 3}, então: A × A = A2 = {(2, 2), (2, 3), (3, 2), (3, 3)} Produto Cartesiano Definição Exemplos. Se A = {x ∈ R|1 ≤ x ≤ 3} e B = {x ∈ R|1 ≤ x ≤ 5}, então: A × B = {(x, y) ∈ R|1 ≤ x ≤ 3 e 1 ≤ y ≤ 5} Produto Cartesiano Definição Exemplos. Se A = {x ∈ R|1 ≤ x ≤ 3} e B = {x ∈ R|1 ≤ x ≤ 5}, então: A × B = {(x, y) ∈ R|1 ≤ x ≤ 3 e 1 ≤ y ≤ 5} Produto Cartesiano Definição Exemplos. Se A = {x ∈ R|1 ≤ x ≤ 3} e B = {x ∈ R|1 ≤ x ≤ 5}, então: A × B = {(x, y) ∈ R|1 ≤ x ≤ 3 e 1 ≤ y ≤ 5} Produto Cartesiano Propriedades Se A ̸= B, então A × B ̸= B × A Se A e B são conjuntos finitos com m e n elementos, respectivamente, entanto A × B é um conjunto com m · n elementos Se A ou B for infinito e nenhum deles vazio, então A × B é um conjunto infinito Produto Cartesiano Propriedades Se A ̸= B, então A × B ̸= B × A Se A e B são conjuntos finitos com m e n elementos, respectivamente, entanto A × B é um conjunto com m · n elementos Se A ou B for infinito e nenhum deles vazio, então A × B é um conjunto infinito Produto Cartesiano Propriedades Se A ̸= B, então A × B ̸= B × A Se A e B são conjuntos finitos com m e n elementos, respectivamente, entanto A × B é um conjunto com m · n elementos Se A ou B for infinito e nenhum deles vazio, então A × B é um conjunto infinito Relações e suas Propriedades Relações Binárias 🔹 Sejam A e B dois conjuntos. Uma relação binária de A em B é um subconjunto de A × B Relações e suas Propriedades Relações Binárias 🔹 Sejam A e B dois conjuntos. Uma relação binária de A em B é um subconjunto de A × B 🔹 Exemplo. Seja A = {1, 2, 3, 4, 5} e B = {1, 2, 3, 4} quais são os elementos da relação R = {(x, y)|x < y}? Relações e suas Propriedades Relações Binárias 🔹 Sejam A e B dois conjuntos. Uma relação binária de A em B é um subconjunto de A × B 🔹 Exemplo. Seja A = {1, 2, 3, 4, 5} e B = {1, 2, 3, 4} quais são os elementos da relação R = {(x, y)|x < y}? 🔸 Temos que: Relações e suas Propriedades Relações Binárias • Sejam A e B dois conjuntos. Uma relação binária de A em B é um subconjunto de A × B • Exemplo. Seja A = {1, 2, 3, 4, 5} e B = {1, 2, 3, 4} quais são os elementos da relação R = {(x, y)|x < y}? • Temos que: A × B = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4), (4, 1), (4, 2), (4, 3), (4, 4), (5, 1), (5, 2), (5, 3), (5, 4) } • Os elementos da relação R são: Relações e suas Propriedades Relações Binárias • Sejam A e B dois conjuntos. Uma relação binária de A em B é um subconjunto de A × B • Exemplo. Seja A = {1, 2, 3, 4, 5} e B = {1, 2, 3, 4} quais são os elementos da relação R = {(x, y)|x < y}? • Temos que: A × B = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4), (4, 1), (4, 2), (4, 3), (4, 4), (5, 1), (5, 2), (5, 3), (5, 4) } • Os elementos da relação R são: R = { (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4) } Relações e suas Propriedades Relações Binárias • Sejam A e B dois conjuntos. Uma relação binária de A em B é um subconjunto de A × B Relações e suas Propriedades Relações Binárias • Sejam A e B dois conjuntos. Uma relação binária de A em B é um subconjunto de A × B • Exemplo. Seja A = {1, 2, 3} e B = {2, 4, 6, 10} quais são os elementos da relação R = {(x, y) : x | y}? Relações e suas Propriedades Relações Binárias • Sejam A e B dois conjuntos. Uma relação binária de A em B é um subconjunto de A × B • Exemplo. Seja A = {1, 2, 3} e B = {2, 4, 6, 10} quais são os elementos da relação R = {(x, y) : x | y}? • Temos que: Relações e suas Propriedades Relações Binárias • Sejam A e B dois conjuntos. Uma relação binária de A em B é um subconjunto de A × B • Exemplo. Seja A = {1, 2, 3} e B = {2, 4, 6, 10} quais são os elementos da relação R = {(x, y) : x | y}? • Temos que: A × B = { (1, 2), (1, 4), (1, 6), (1, 10) (2, 2), (2, 4), (2, 6), (2, 10) (3, 2), (3, 4), (3, 6), (3, 10) } • Os elementos da relação R são: Relações e suas Propriedades Relações Binárias Sejam A e B dois conjuntos. Uma relação binária de A em B é um subconjunto de A \times B Exemplo. Seja A = \{1, 2, 3\} e B = \{2, 4, 6, 10\} quais são os elementos da relação R = \{(x, y) : x | y\}? Temos que: \{(1, 2), (1, 4), (1, 6), (1, 10), (2, 2), (2, 4), (2, 6), (2, 10), (3, 2), (3, 6), (3, 10)\} Os elementos da relação R são: R = \{ (1, 2), (1, 4), (1, 6), (1, 10), (2, 2), (2, 4), (2, 6), (2, 10), (3, 6) \} Relações e suas Propriedades Relações n-Árias Sejam A1, A2, · · · , An conjuntos. Uma relação n-ária nesses conjuntos é um subconjunto de A1 × A2 × · · · × An Os conjuntos A1, A2, · · · , An são chamados domínios da relação e n é chamado de seu grau Exemplo. Seja R a relação R = {(a, b, c) ∈ Z × Z × Z : a,b e c formam uma P.A.} Observe que (a, b, c) ∈ R se, e somente se, exite k ∈ Z tal que b = a + k e c = a + 2k (1, 3, 5) ∈ R, pois 3 = 1 + 2 e 5 = 3 + 2 · 2 (2, 5, 9) /∈ R, pois as razões são diferentes: 5 − 2 = 3 e 9 − 5 = 4 Relações e suas Propriedades Relações n-Árias Sejam A1, A2, · · · , An conjuntos. Uma relação n-ária nesses conjuntos é um subconjunto de A1 × A2 × · · · × An Os conjuntos A1, A2, · · · , An são chamados domínios da relação e n é chamado de seu grau Exemplo. Seja R a relação R = {(a, b, c) ∈ Z × Z × Z : a,b e c formam uma P.A.} Observe que (a, b, c) ∈ R se, e somente se, exite k ∈ Z tal que b = a + k e c = a + 2k (1, 3, 5) ∈ R, pois 3 = 1 + 2 e 5 = 3 + 2 · 2 (2, 5, 9) /∈ R, pois as razões são diferentes: 5 − 2 = 3 e 9 − 5 = 4 Relações e suas Propriedades Relações n-Árias Sejam A1, A2, · · · , An conjuntos. Uma relação n-ária nesses conjuntos é um subconjunto de A1 × A2 × · · · × An Os conjuntos A1, A2, · · · , An são chamados domínios da relação e n é chamado de seu grau Exemplo. Seja R a relação R = {(a, b, c) ∈ Z × Z × Z : a,b e c formam uma P.A.} Observe que (a, b, c) ∈ R se, e somente se, exite k ∈ Z tal que b = a + k e c = a + 2k (1, 3, 5) ∈ R, pois 3 = 1 + 2 e 5 = 3 + 2 · 2 (2, 5, 9) /∈ R, pois as razões são diferentes: 5 − 2 = 3 e 9 − 5 = 4 Relações e suas Propriedades Relações n-Árias Sejam A1, A2, · · · , An conjuntos. Uma relação n-ária nesses conjuntos é um subconjunto de A1 × A2 × · · · × An Os conjuntos A1, A2, · · · , An são chamados domínios da relação e n é chamado de seu grau Exemplo. Seja R a relação R = {(a, b, c) ∈ Z × Z × Z : a,b e c formam uma P.A.} Observe que (a, b, c) ∈ R se, e somente se, exite k ∈ Z tal que b = a + k e c = a + 2k (1, 3, 5) ∈ R, pois 3 = 1 + 2 e 5 = 3 + 2 · 2 (2, 5, 9) /∈ R, pois as razões são diferentes: 5 − 2 = 3 e 9 − 5 = 4 Relações e suas Propriedades Relações n-Árias Sejam A1, A2, · · · , An conjuntos. Uma relação n-ária nesses conjuntos é um subconjunto de A1 × A2 × · · · × An Os conjuntos A1, A2, · · · , An são chamados domínios da relação e n é chamado de seu grau Exemplo. Seja R a relação R = {(a, b, c) ∈ Z × Z × Z : a,b e c formam uma P.A.} Observe que (a, b, c) ∈ R se, e somente se, exite k ∈ Z tal que b = a + k e c = a + 2k (1, 3, 5) ∈ R, pois 3 = 1 + 2 e 5 = 3 + 2 · 2 (2, 5, 9) /∈ R, pois as razões são diferentes: 5 − 2 = 3 e 9 − 5 = 4 Relações e suas Propriedades Relações n-Árias Sejam A1, A2, · · · , An conjuntos. Uma relação n-ária nesses conjuntos é um subconjunto de A1 × A2 × · · · × An Os conjuntos A1, A2, · · · , An são chamados domínios da relação e n é chamado de seu grau Exemplo. Seja R a relação R = {(a, b, c) ∈ Z × Z × Z : a,b e c formam uma P.A.} Observe que (a, b, c) ∈ R se, e somente se, exite k ∈ Z tal que b = a + k e c = a + 2k (1, 3, 5) ∈ R, pois 3 = 1 + 2 e 5 = 3 + 2 · 2 (2, 5, 9) /∈ R, pois as razões são diferentes: 5 − 2 = 3 e 9 − 5 = 4 Relações e suas Propriedades Relações n-Árias Sejam A1, A2, · · · , An conjuntos. Uma relação n-ária nesses conjuntos é um subconjunto de A1 × A2 × · · · × An Exemplo. Seja R a relação R = {(a, b, m) ∈ Z × Z × Z+ : a, b, m ∈ Z, m ≥ 1 e a ≡ b(mod m)} Observe que: (8, 2, 3), (−1, 9, 5), (14, 0, 7) ∈ R, pois 8 ≡ 2(mod 3), −1 ≡ 9(mod 5) e 14 ≡ 0(mod 7) (7, 2, 3), (−2, −8, 5), (11, 0, 6) /∈ R, pois 7 ̸≡ 2(mod 3), −2 ̸≡ −8(mod 5) e 11 ̸≡ 0(mod 6) Relações e suas Propriedades Relações n-Árias Sejam A1, A2, · · · , An conjuntos. Uma relação n-ária nesses conjuntos é um subconjunto de A1 × A2 × · · · × An Exemplo. Seja R a relação R = {(a, b, m) ∈ Z × Z × Z+ : a, b, m ∈ Z, m ≥ 1 e a ≡ b(mod m)} Observe que: (8, 2, 3), (−1, 9, 5), (14, 0, 7) ∈ R, pois 8 ≡ 2(mod 3), −1 ≡ 9(mod 5) e 14 ≡ 0(mod 7) (7, 2, 3), (−2, −8, 5), (11, 0, 6) /∈ R, pois 7 ̸≡ 2(mod 3), −2 ̸≡ −8(mod 5) e 11 ̸≡ 0(mod 6) Relações e suas Propriedades Relações n-Árias Sejam A1, A2, · · · , An conjuntos. Uma relação n-ária nesses conjuntos é um subconjunto de A1 × A2 × · · · × An Exemplo. Seja R a relação R = {(a, b, m) ∈ Z × Z × Z+ : a, b, m ∈ Z, m ≥ 1 e a ≡ b(mod m)} Observe que: (8, 2, 3), (−1, 9, 5), (14, 0, 7) ∈ R, pois 8 ≡ 2(mod 3), −1 ≡ 9(mod 5) e 14 ≡ 0(mod 7) (7, 2, 3), (−2, −8, 5), (11, 0, 6) /∈ R, pois 7 ̸≡ 2(mod 3), −2 ̸≡ −8(mod 5) e 11 ̸≡ 0(mod 6) Relações e suas Propriedades Relações n-Árias Sejam A1, A2, · · · , An conjuntos. Uma relação n-ária nesses conjuntos é um subconjunto de A1 × A2 × · · · × An Exemplo. Seja R a relação R = {(a, b, m) ∈ Z × Z × Z+ : a, b, m ∈ Z, m ≥ 1 e a ≡ b(mod m)} Observe que: (8, 2, 3), (−1, 9, 5), (14, 0, 7) ∈ R, pois 8 ≡ 2(mod 3), −1 ≡ 9(mod 5) e 14 ≡ 0(mod 7) (7, 2, 3), (−2, −8, 5), (11, 0, 6) /∈ R, pois 7 ̸≡ 2(mod 3), −2 ̸≡ −8(mod 5) e 11 ̸≡ 0(mod 6) Relações e suas Propriedades Relações n-Árias Sejam A1, A2, · · · , An conjuntos. Uma relação n-ária nesses conjuntos é um subconjunto de A1 × A2 × · · · × An Exemplo. Seja R a relação R = {(a, b, m) ∈ Z × Z × Z+ : a, b, m ∈ Z, m ≥ 1 e a ≡ b(mod m)} Observe que: (8, 2, 3), (−1, 9, 5), (14, 0, 7) ∈ R, pois 8 ≡ 2(mod 3), −1 ≡ 9(mod 5) e 14 ≡ 0(mod 7) (7, 2, 3), (−2, −8, 5), (11, 0, 6) /∈ R, pois 7 ̸≡ 2(mod 3), −2 ̸≡ −8(mod 5) e 11 ̸≡ 0(mod 6) Relações e suas Propriedades Relações em um Conjunto Uma relação no conjunto A é uma relação de A em A Relações e suas Propriedades Relações em um Conjunto Uma relação no conjunto A é uma relação de A em A Em outras palavras, uma relação em um conjunto A é um subconjunto de A \times A = A^2 Exemplo. Seja R a relação R = \{(a, b) \in A^2 : a | b\}, com A = \{1, 2, 3, 4\}. Determine R. Relações e suas Propriedades Relações em um Conjunto Uma relação no conjunto A é uma relação de A em A Em outras palavras, uma relação em um conjunto A é um subconjunto de A × A = A² Exemplo. Seja R a relação R = {(a, b) ∈ A² : a | b}, com A = {1, 2, 3, 4}. Determine R. R = { (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4) } Analogamente, uma relação n-ária em um conjunto A é um subconjunto de Aⁿ Relações e suas Propriedades Relações em um Conjunto Quantas relações existem em um conjunto com n elementos? Uma relação em um conjunto A é um subconjunto de A × A Como A × A tem n2 elementos e um conjunto com n elementos tem 2n subconjuntos Existem 2n2 de A × A Logo, existem 2n2 relações em um conjunto com n elementos Exemplo. Existem 232 = 29 = 512 relações no conjunto {a, b, c} Relações e suas Propriedades Relações em um Conjunto Quantas relações existem em um conjunto com n elementos? Uma relação em um conjunto A é um subconjunto de A × A Como A × A tem n2 elementos e um conjunto com n elementos tem 2n subconjuntos Existem 2n2 de A × A Logo, existem 2n2 relações em um conjunto com n elementos Exemplo. Existem 232 = 29 = 512 relações no conjunto {a, b, c} Relações e suas Propriedades Relações em um Conjunto Quantas relações existem em um conjunto com n elementos? Uma relação em um conjunto A é um subconjunto de A × A Como A × A tem n2 elementos e um conjunto com n elementos tem 2n subconjuntos Existem 2n2 de A × A Logo, existem 2n2 relações em um conjunto com n elementos Exemplo. Existem 232 = 29 = 512 relações no conjunto {a, b, c} Relações e suas Propriedades Relações em um Conjunto Quantas relações existem em um conjunto com n elementos? Uma relação em um conjunto A é um subconjunto de A × A Como A × A tem n2 elementos e um conjunto com n elementos tem 2n subconjuntos Existem 2n2 de A × A Logo, existem 2n2 relações em um conjunto com n elementos Exemplo. Existem 232 = 29 = 512 relações no conjunto {a, b, c} Relações e suas Propriedades Propriedades das Relações Existem algumas propriedades que são usadas para classificar relações em um conjunto Definição: Seja R uma relação em um conjunto A 1. R é reflexiva se, e somente se, para todo x ∈ A, (x, x) ∈ R ou, equivalentemente, xRx 2. R é simétrica se, e somente se, para todo x, y ∈ A, se (x, y) ∈ R, então (y, x) ∈ R. Equivalentemente, se xRy, então yRx 3. R é transitiva se, e somente se, para todo x, y, z ∈ A, se (x, y) ∈ R e (y, z) ∈ R, então (x, z) ∈ R. Equivalentemente, se xRy e yRz, então xRz 4. R é antissimétrica se, e somente se, (a, b) ∈ R e (b, a) ∈ R implica que a = b Relações e suas Propriedades Propriedades das Relações Existem algumas propriedades que são usadas para classificar relações em um conjunto Definição: Seja R uma relação em um conjunto A 1. R é reflexiva se, e somente se, para todo x ∈ A, (x, x) ∈ R ou, equivalentemente, xRx 2. R é simétrica se, e somente se, para todo x, y ∈ A, se (x, y) ∈ R, então (y, x) ∈ R. Equivalentemente, se xRy, então yRx 3. R é transitiva se, e somente se, para todo x, y, z ∈ A, se (x, y) ∈ R e (y, z) ∈ R, então (x, z) ∈ R. Equivalentemente, se xRy e yRz, então xRz 4. R é antissimétrica se, e somente se, (a, b) ∈ R e (b, a) ∈ R implica que a = b Relações e suas Propriedades Propriedades das Relações Existem algumas propriedades que são usadas para classificar relações em um conjunto Definição: Seja R uma relação em um conjunto A 1. R é reflexiva se, e somente se, para todo x ∈ A, (x, x) ∈ R ou, equivalentemente, xRx 2. R é simétrica se, e somente se, para todo x, y ∈ A, se (x, y) ∈ R, então (y, x) ∈ R. Equivalentemente, se xRy, então yRx 3. R é transitiva se, e somente se, para todo x, y, z ∈ A, se (x, y) ∈ R e (y, z) ∈ R, então (x, z) ∈ R. Equivalentemente, se xRy e yRz, então xRz 4. R é antissimétrica se, e somente se, (a, b) ∈ R e (b, a) ∈ R implica que a = b Relações e suas Propriedades Propriedades das Relações Existem algumas propriedades que são usadas para classificar relações em um conjunto Definição: Seja R uma relação em um conjunto A 1. R é reflexiva se, e somente se, para todo x ∈ A, (x, x) ∈ R ou, equivalentemente, xRx 2. R é simétrica se, e somente se, para todo x, y ∈ A, se (x, y) ∈ R, então (y, x) ∈ R. Equivalentemente, se xRy, então yRx 3. R é transitiva se, e somente se, para todo x, y, z ∈ A, se (x, y) ∈ R e (y, z) ∈ R, então (x, z) ∈ R. Equivalentemente, se xRy e yRz, então xRz 4. R é antissimétrica se, e somente se, (a, b) ∈ R e (b, a) ∈ R implica que a = b Relações e suas Propriedades Propriedades das Relações Existem algumas propriedades que são usadas para classificar relações em um conjunto Definição: Seja R uma relação em um conjunto A 1. R é reflexiva se, e somente se, para todo x ∈ A, (x, x) ∈ R ou, equivalentemente, xRx 2. R é simétrica se, e somente se, para todo x, y ∈ A, se (x, y) ∈ R, então (y, x) ∈ R. Equivalentemente, se xRy, então yRx 3. R é transitiva se, e somente se, para todo x, y, z ∈ A, se (x, y) ∈ R e (y, z) ∈ R, então (x, z) ∈ R. Equivalentemente, se xRy e yRz, então xRz 4. R é antissimétrica se, e somente se, (a, b) ∈ R e (b, a) ∈ R implica que a = b Relações e suas Propriedades Propriedades das Relações Existem algumas propriedades que são usadas para classificar relações em um conjunto Definição: Seja R uma relação em um conjunto A 1. R é reflexiva se, e somente se, para todo x ∈ A, (x, x) ∈ R ou, equivalentemente, xRx 2. R é simétrica se, e somente se, para todo x, y ∈ A, se (x, y) ∈ R, então (y, x) ∈ R. Equivalentemente, se xRy, então yRx 3. R é transitiva se, e somente se, para todo x, y, z ∈ A, se (x, y) ∈ R e (y, z) ∈ R, então (x, z) ∈ R. Equivalentemente, se xRy e yRz, então xRz 4. R é antissimétrica se, e somente se, (a, b) ∈ R e (b, a) ∈ R implica que a = b Relações e suas Propriedades Representando Relações Podemos representar uma relação, em um conjunto finito, por meio de um grafo direcionado da seguinte maneira: Cada elemento do conjunto é representado por um ponto E cada par ordenado é representado usando um arco com sua direção indicada por uma flecha Relações e suas Propriedades Representando Relações Podemos representar uma relação, em um conjunto finito, por meio de um grafo direcionado da seguinte maneira: Cada elemento do conjunto é representado por um ponto E cada par ordenado é representado usando um arco com sua direção indicada por uma flecha Relações e suas Propriedades Representando Relações Podemos representar uma relação, em um conjunto finito, por meio de um grafo direcionado da seguinte maneira: Cada elemento do conjunto é representado por um ponto E cada par ordenado é representado usando um arco com sua direção indicada por uma flecha Relações e suas Propriedades Representando Relações Definição. Um grafo orientado ou digrafo, consiste em um conjunto V de vértices (ou nós) junto com um conjunto E de pares ordenados de elementos de V chamados de arestas (ou arcos). O vértice a é chamado vértice inicial de uma aresta (a, b) e o vértice b é chamado vértice final da aresta Uma aresta da forma (a, a) é representada usando um arco do vértice a que volte para ele mesmo Essa aresta é chamada de laço Exemplo. O grafo orientado com vértices a, b, c, d e arestas (a, b), (a, d), (b, b), (b, d), (c, a), (c, b), (d, b) é dado por: Relações e suas Propriedades Representando Relações Definição. Um grafo orientado ou digrafo, consiste em um conjunto V de vértices (ou nós) junto com um conjunto E de pares ordenados de elementos de V chamados de arestas (ou arcos). O vértice a é chamado vértice inicial de uma aresta (a, b) e o vértice b é chamado vértice final da aresta Uma aresta da forma (a, a) é representada usando um arco do vértice a que volte para ele mesmo Essa aresta é chamada de laço Exemplo. O grafo orientado com vértices a, b, c, d e arestas (a, b), (a, d), (b, b), (b, d), (c, a), (c, b), (d, b) é dado por: Relações e suas Propriedades Representando Relações Definição. Um grafo orientado ou digrafo, consiste em um conjunto V de vértices (ou nós) junto com um conjunto E de pares ordenados de elementos de V chamados de arestas (ou arcos). O vértice a é chamado vértice inicial de uma aresta (a, b) e o vértice b é chamado vértice final da aresta Uma aresta da forma (a, a) é representada usando um arco do vértice a que volte para ele mesmo Essa aresta é chamada de laço Exemplo. O grafo orientado com vértices a, b, c, d e arestas (a, b), (a, d), (b, b), (b, d), (c, a), (c, b), (d, b) é dado por: Relações e suas Propriedades Representando Relações Definição. Um grafo orientado ou digrafo, consiste em um conjunto V de vértices (ou nós) junto com um conjunto E de pares ordenados de elementos de V chamados de arestas (ou arcos). O vértice a é chamado vértice inicial de uma aresta (a, b) e o vértice b é chamado vértice final da aresta Uma aresta da forma (a, a) é representada usando um arco do vértice a que volte para ele mesmo Essa aresta é chamada de laço Exemplo. O grafo orientado com vértices a, b, c, d e arestas (a, b), (a, d), (b, b), (b, d), (c, a), (c, b), (d, b) é dado por: Relações e suas Propriedades Representando Relações O digrafo de uma relação sobre um conjunto pode ser utilizao para determinar se a relação possui algumas propriedades Para que uma relação sobre um conjunto A seja reflexiva o digrafo que representa a relação deve possuir um laço de cada nó para si mesmo O digrafo que representa uma relação simétrica possui, entre quaisquer dois nós, 0 ou 2 arcos, isto é, quaisquer dois nós ou não possuem arcos entre eles, ou, se possuem, tais arcos estão em ambas os sentidos Relações e suas Propriedades Representando Relações O digrafo de uma relação sobre um conjunto pode ser utilizao para determinar se a relação possui algumas propriedades Para que uma relação sobre um conjunto A seja reflexiva o digrafo que representa a relação deve possuir um laço de cada nó para si mesmo O digrafo que representa uma relação simétrica possui, entre quaisquer dois nós, 0 ou 2 arcos, isto é, quaisquer dois nós ou não possuem arcos entre eles, ou, se possuem, tais arcos estão em ambas os sentidos Relações e suas Propriedades Representando Relações O digrafo de uma relação sobre um conjunto pode ser utilizao para determinar se a relação possui algumas propriedades Para que uma relação sobre um conjunto A seja reflexiva o digrafo que representa a relação deve possuir um laço de cada nó para si mesmo O digrafo que representa uma relação simétrica possui, entre quaisquer dois nós, 0 ou 2 arcos, isto é, quaisquer dois nós ou não possuem arcos entre eles, ou, se possuem, tais arcos estão em ambas os sentidos Relações e suas Propriedades Representando Relações O digrafo de uma relação sobre um conjunto pode ser utilizao para determinar se a relação possui algumas propriedades Um digrafo representa uma relação transitiva se para cada par de vértices ocorre uma das seguintes possibilidades em relação aos arcos: não existe arco ligando o par de vértices; ou existe pelo menos um arco ligando diretamente os vértices e/ou existe um vértice intermediário que permite ligar o par de vértices Um grafo direcionado representa uma relação antissimétrica se para cada par de vértices ocorre uma das seguintes possibilidades em relação aos arcos: não existe arco ligando os vértices; ou entre os dois vértices existe exatamente um arco Relações e suas Propriedades Representando Relações O digrafo de uma relação sobre um conjunto pode ser utilizao para determinar se a relação possui algumas propriedades Um digrafo representa uma relação transitiva se para cada par de vértices ocorre uma das seguintes possibilidades em relação aos arcos: não existe arco ligando o par de vértices; ou existe pelo menos um arco ligando diretamente os vértices e/ou existe um vértice intermediário que permite ligar o par de vértices Um grafo direcionado representa uma relação antissimétrica se para cada par de vértices ocorre uma das seguintes possibilidades em relação aos arcos: não existe arco ligando os vértices; ou entre os dois vértices existe exatamente um arco Relações e suas Propriedades Representando Relações O digrafo de uma relação sobre um conjunto pode ser utilizao para determinar se a relação possui algumas propriedades Um digrafo representa uma relação transitiva se para cada par de vértices ocorre uma das seguintes possibilidades em relação aos arcos: não existe arco ligando o par de vértices; ou existe pelo menos um arco ligando diretamente os vértices e/ou existe um vértice intermediário que permite ligar o par de vértices Um grafo direcionado representa uma relação antissimétrica se para cada par de vértices ocorre uma das seguintes possibilidades em relação aos arcos: não existe arco ligando os vértices; ou entre os dois vértices existe exatamente um arco Relações e suas Propriedades Representando Relações O digrafo de uma relação sobre um conjunto pode ser utilizao para determinar se a relação possui algumas propriedades Um digrafo representa uma relação transitiva se para cada par de vértices ocorre uma das seguintes possibilidades em relação aos arcos: não existe arco ligando o par de vértices; ou existe pelo menos um arco ligando diretamente os vértices e/ou existe um vértice intermediário que permite ligar o par de vértices Um grafo direcionado representa uma relação antissimétrica se para cada par de vértices ocorre uma das seguintes possibilidades em relação aos arcos: não existe arco ligando os vértices; ou entre os dois vértices existe exatamente um arco Relações e suas Propriedades Representando Relações O digrafo de uma relação sobre um conjunto pode ser utilizao para determinar se a relação possui algumas propriedades Um digrafo representa uma relação transitiva se para cada par de vértices ocorre uma das seguintes possibilidades em relação aos arcos: não existe arco ligando o par de vértices; ou existe pelo menos um arco ligando diretamente os vértices e/ou existe um vértice intermediário que permite ligar o par de vértices Um grafo direcionado representa uma relação antissimétrica se para cada par de vértices ocorre uma das seguintes possibilidades em relação aos arcos: não existe arco ligando os vértices; ou entre os dois vértices existe exatamente um arco Relações e suas Propriedades Representando Relações O digrafo de uma relação sobre um conjunto pode ser utilizao para determinar se a relação possui algumas propriedades Um digrafo representa uma relação transitiva se para cada par de vértices ocorre uma das seguintes possibilidades em relação aos arcos: não existe arco ligando o par de vértices; ou existe pelo menos um arco ligando diretamente os vértices e/ou existe um vértice intermediário que permite ligar o par de vértices Um grafo direcionado representa uma relação antissimétrica se para cada par de vértices ocorre uma das seguintes possibilidades em relação aos arcos: não existe arco ligando os vértices; ou entre os dois vértices existe exatamente um arco Relações e suas Propriedades Representando Relações O digrafo de uma relação sobre um conjunto pode ser utilizao para determinar se a relação possui algumas propriedades Um digrafo representa uma relação transitiva se para cada par de vértices ocorre uma das seguintes possibilidades em relação aos arcos: não existe arco ligando o par de vértices; ou existe pelo menos um arco ligando diretamente os vértices e/ou existe um vértice intermediário que permite ligar o par de vértices Um grafo direcionado representa uma relação antissimétrica se para cada par de vértices ocorre uma das seguintes possibilidades em relação aos arcos: não existe arco ligando os vértices; ou entre os dois vértices existe exatamente um arco Relações e suas Propriedades Representando Relações O digrafo de uma relação sobre um conjunto pode ser utilizao para determinar se a relação possui algumas propriedades Um digrafo representa uma relação transitiva se para cada par de vértices ocorre uma das seguintes possibilidades em relação aos arcos: não existe arco ligando o par de vértices; ou existe pelo menos um arco ligando diretamente os vértices e/ou existe um vértice intermediário que permite ligar o par de vértices Um grafo direcionado representa uma relação antissimétrica se para cada par de vértices ocorre uma das seguintes possibilidades em relação aos arcos: não existe arco ligando os vértices; ou entre os dois vértices existe exatamente um arco Relações e suas Propriedades Representando Relações Outra maneira de representar relações é através de matrizes Relações e suas Propriedades Representando Relações Outra maneira de representar relações é através de matrizes Essa abordagem é interessante pois matrizes são uma forma apropriada de representar relações em programas de computador Relações e suas Propriedades Representando Relações Outra maneira de representar relações é através de matrizes Essa abordagem é interessante pois matrizes são uma forma apropriada de representar relações em programas de computador Seja R uma relação de A = {a1, a2, ⋯ , am} e B = {b1, b2, ⋯ , bn}. A relação R pode ser representada pela matriz MR = [mij] em que Relações e suas Propriedades Representando Relações Outra maneira de representar relações é através de matrizes Essa abordagem é interessante pois matrizes são uma forma apropriada de representar relações em programas de computador Seja R uma relação de A = {a1, a2, ⋯ , am} e B = {b1, b2, ⋯ , bn}. A relação R pode ser representada pela matriz MR = [mij] em que mij = { 1, se (ai, bj) ∈ R 0, se (ai, bj) ∉ R Relações e suas Propriedades Representando Relações Sejam 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 e b ∈ B e a > b Como R = {(2, 1), (3, 1), (3, 2)}, a matriz para R é MR =   0 0 1 0 1 1   Sejam A = {a1, a2, a2} e B = {b1, b2, b3, b4, b5}. Quais pares ordenados estão na relação R representada pela matriz MR =   0 1 0 0 0 1 0 1 1 0 1 0 1 0 0  ? Como R consiste nos pares ordenados (ai, bj), com mij = 1, segue que R = {(a1, b2), (a2, b1), (a2, b3), (a2, b4), (a3, b1), (a3, b3)} Relações e suas Propriedades Representando Relações Sejam 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 e b ∈ B e a > b Como R = {(2, 1), (3, 1), (3, 2)}, a matriz para R é MR =   0 0 1 0 1 1   Sejam A = {a1, a2, a2} e B = {b1, b2, b3, b4, b5}. Quais pares ordenados estão na relação R representada pela matriz MR =   0 1 0 0 0 1 0 1 1 0 1 0 1 0 0  ? Como R consiste nos pares ordenados (ai, bj), com mij = 1, segue que R = {(a1, b2), (a2, b1), (a2, b3), (a2, b4), (a3, b1), (a3, b3)} Relações e suas Propriedades Representando Relações Sejam 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 e b ∈ B e a > b Como R = {(2, 1), (3, 1), (3, 2)}, a matriz para R é MR =   0 0 1 0 1 1   Sejam A = {a1, a2, a2} e B = {b1, b2, b3, b4, b5}. Quais pares ordenados estão na relação R representada pela matriz MR =   0 1 0 0 0 1 0 1 1 0 1 0 1 0 0  ? Como R consiste nos pares ordenados (ai, bj), com mij = 1, segue que R = {(a1, b2), (a2, b1), (a2, b3), (a2, b4), (a3, b1), (a3, b3)} Relações e suas Propriedades Representando Relações Sejam 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 e b ∈ B e a > b Como R = {(2, 1), (3, 1), (3, 2)}, a matriz para R é MR =   0 0 1 0 1 1   Sejam A = {a1, a2, a2} e B = {b1, b2, b3, b4, b5}. Quais pares ordenados estão na relação R representada pela matriz MR =   0 1 0 0 0 1 0 1 1 0 1 0 1 0 0  ? Como R consiste nos pares ordenados (ai, bj), com mij = 1, segue que R = {(a1, b2), (a2, b1), (a2, b3), (a2, b4), (a3, b1), (a3, b3)} Relações e suas Propriedades Representando Relações Sejam 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 e b ∈ B e a > b Como R = {(2, 1), (3, 1), (3, 2)}, a matriz para R é MR =   0 0 1 0 1 1   Sejam A = {a1, a2, a2} e B = {b1, b2, b3, b4, b5}. Quais pares ordenados estão na relação R representada pela matriz MR =   0 1 0 0 0 1 0 1 1 0 1 0 1 0 0  ? Como R consiste nos pares ordenados (ai, bj), com mij = 1, segue que R = {(a1, b2), (a2, b1), (a2, b3), (a2, b4), (a3, b1), (a3, b3)} Relações e suas Propriedades Representando Relações Sejam 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 e b ∈ B e a > b Como R = {(2, 1), (3, 1), (3, 2)}, a matriz para R é MR =   0 0 1 0 1 1   Sejam A = {a1, a2, a2} e B = {b1, b2, b3, b4, b5}. Quais pares ordenados estão na relação R representada pela matriz MR =   0 1 0 0 0 1 0 1 1 0 1 0 1 0 0  ? Como R consiste nos pares ordenados (ai, bj), com mij = 1, segue que R = {(a1, b2), (a2, b1), (a2, b3), (a2, b4), (a3, b1), (a3, b3)} Relações e suas Propriedades Representando Relações A matriz de uma relação sobre um conjunto pode ser utilizada para determinar se a relação possui algumas propriedades Para que uma relação sobre um conjunto A seja reflexiva mii = 1. Ou seja, os elementos da diagonal principal devem ser iguais a 1 R é simétrica se, e somente se, mji = 1 sempre que mij = 1 e mji = 0 sempre que mij = 0, ou seja, (MR)T = MR Relações e suas Propriedades Representando Relações A matriz de uma relação sobre um conjunto pode ser utilizada para determinar se a relação possui algumas propriedades Para que uma relação sobre um conjunto A seja reflexiva mii = 1. Ou seja, os elementos da diagonal principal devem ser iguais a 1 R é simétrica se, e somente se, mji = 1 sempre que mij = 1 e mji = 0 sempre que mij = 0, ou seja, (MR)T = MR Relações e suas Propriedades Representando Relações A matriz de uma relação sobre um conjunto pode ser utilizada para determinar se a relação possui algumas propriedades Para que uma relação sobre um conjunto A seja reflexiva mii = 1. Ou seja, os elementos da diagonal principal devem ser iguais a 1 R é simétrica se, e somente se, mji = 1 sempre que mij = 1 e mji = 0 sempre que mij = 0, ou seja, (MR)T = MR Relações e suas Propriedades Representando Relações A matriz de uma relação sobre um conjunto pode ser utilizada para determinar se a relação possui algumas propriedades Para que uma relação sobre um conjunto A seja reflexiva mii = 1. Ou seja, os elementos da diagonal principal devem ser iguais a 1 R é simétrica se, e somente se, mji = 1 sempre que mij = 1 e mji = 0 sempre que mij = 0, ou seja, (MR)T = MR Relações e suas Propriedades Representando Relações A matriz de uma relação sobre um conjunto pode ser utilizada para determinar se a relação possui algumas propriedades Para que uma relação sobre um conjunto A seja reflexiva mii = 1. Ou seja, os elementos da diagonal principal devem ser iguais a 1 R é simétrica se, e somente se, mji = 1 sempre que mij = 1 e mji = 0 sempre que mij = 0, ou seja, (MR)T = MR Relações e suas Propriedades Representando Relações R é antissimétrica se, e somente se, (a, b) ∈ R e (b, a) ∈ R implica que a = b Consequentemente, R é antissimétrica se mij = 1, com i ̸= j, então mji = 0. A representação matricial MR correspondente desta relação terá o elemento mij = 1, com i ̸= j, mas com o termo mji não pertencendo a matriz Relações e suas Propriedades Representando Relações R é antissimétrica se, e somente se, (a, b) ∈ R e (b, a) ∈ R implica que a = b Consequentemente, R é antissimétrica se mij = 1, com i ̸= j, então mji = 0. A representação matricial MR correspondente desta relação terá o elemento mij = 1, com i ̸= j, mas com o termo mji não pertencendo a matriz Relações e suas Propriedades Representando Relações R é antissimétrica se, e somente se, (a, b) ∈ R e (b, a) ∈ R implica que a = b Consequentemente, R é antissimétrica se mij = 1, com i ̸= j, então mji = 0. A representação matricial MR correspondente desta relação terá o elemento mij = 1, com i ̸= j, mas com o termo mji não pertencendo a matriz Relações e suas Propriedades Representando Relações R é antissimétrica se, e somente se, (a, b) ∈ R e (b, a) ∈ R implica que a = b Consequentemente, R é antissimétrica se mij = 1, com i ̸= j, então mji = 0. A representação matricial MR correspondente desta relação terá o elemento mij = 1, com i ̸= j, mas com o termo mji não pertencendo a matriz Relações e suas Propriedades Representando Relações Seja R a relação sobre um conjunto que é representada pela matriz abaixo. R é reflexiva, simétrica e/ou antissimétrica? MR =   1 1 0 1 1 1 0 1 1   R é reflexiva, pois todos os elementos da diagonal principal são iguais a 1 R é simétrica, pois MR = (MR)T R não é antissimétrica, pois m21 = m12 Relações e suas Propriedades Representando Relações Seja R a relação sobre um conjunto que é representada pela matriz abaixo. R é reflexiva, simétrica e/ou antissimétrica? MR =   1 1 0 1 1 1 0 1 1   R é reflexiva, pois todos os elementos da diagonal principal são iguais a 1 R é simétrica, pois MR = (MR)T R não é antissimétrica, pois m21 = m12 Relações e suas Propriedades Representando Relações Seja R a relação sobre um conjunto que é representada pela matriz abaixo. R é reflexiva, simétrica e/ou antissimétrica? MR =   1 1 0 1 1 1 0 1 1   R é reflexiva, pois todos os elementos da diagonal principal são iguais a 1 R é simétrica, pois MR = (MR)T R não é antissimétrica, pois m21 = m12 Relações e suas Propriedades Representando Relações Seja R a relação sobre um conjunto que é representada pela matriz abaixo. R é reflexiva, simétrica e/ou antissimétrica? MR =   1 1 0 1 1 1 0 1 1   R é reflexiva, pois todos os elementos da diagonal principal são iguais a 1 R é simétrica, pois MR = (MR)T R não é antissimétrica, pois m21 = m12 Relações e suas Propriedades Representando Relações Seja R a relação sobre um conjunto que é representada pela matriz abaixo. R é reflexiva, simétrica e/ou antissimétrica? MR =   1 1 0 1 1 1 0 1 1   R é reflexiva, pois todos os elementos da diagonal principal são iguais a 1 R é simétrica, pois MR = (MR)T R não é antissimétrica, pois m21 = m12 Relações e suas Propriedades Representando Relações Seja S = {(1, 1), (1, 2), (1, 3)} a relação sobre um conjunto A = {1, 2, 3} que é representada pela matriz abaixo. S é reflexiva, simétrica e/ou antissimétrica? MS =   1 1 1 0 0 0 0 0 0   S não é reflexiva, pois (2, 2) /∈ S S não é simétrica, pois MS ̸= (MS)T S é antissimétrica, pois (1, 1), (1, 2), (1, 3) ∈ S, mas (2, 1), (3, 1) /∈ S e (1, 1) ∈ S, com a = b = 1 Relações e suas Propriedades Representando Relações Seja S = {(1, 1), (1, 2), (1, 3)} a relação sobre um conjunto A = {1, 2, 3} que é representada pela matriz abaixo. S é reflexiva, simétrica e/ou antissimétrica? MS =   1 1 1 0 0 0 0 0 0   S não é reflexiva, pois (2, 2) /∈ S S não é simétrica, pois MS ̸= (MS)T S é antissimétrica, pois (1, 1), (1, 2), (1, 3) ∈ S, mas (2, 1), (3, 1) /∈ S e (1, 1) ∈ S, com a = b = 1 Relações e suas Propriedades Representando Relações Seja S = {(1, 1), (1, 2), (1, 3)} a relação sobre um conjunto A = {1, 2, 3} que é representada pela matriz abaixo. S é reflexiva, simétrica e/ou antissimétrica? MS =   1 1 1 0 0 0 0 0 0   S não é reflexiva, pois (2, 2) /∈ S S não é simétrica, pois MS ̸= (MS)T S é antissimétrica, pois (1, 1), (1, 2), (1, 3) ∈ S, mas (2, 1), (3, 1) /∈ S e (1, 1) ∈ S, com a = b = 1 Relações e suas Propriedades Representando Relações Seja S = {(1, 1), (1, 2), (1, 3)} a relação sobre um conjunto A = {1, 2, 3} que é representada pela matriz abaixo. S é reflexiva, simétrica e/ou antissimétrica? MS =   1 1 1 0 0 0 0 0 0   S não é reflexiva, pois (2, 2) /∈ S S não é simétrica, pois MS ̸= (MS)T S é antissimétrica, pois (1, 1), (1, 2), (1, 3) ∈ S, mas (2, 1), (3, 1) /∈ S e (1, 1) ∈ S, com a = b = 1 Relações e suas Propriedades Representando Relações Seja S = {(1, 1), (1, 2), (1, 3)} a relação sobre um conjunto A = {1, 2, 3} que é representada pela matriz abaixo. S é reflexiva, simétrica e/ou antissimétrica? MS =   1 1 1 0 0 0 0 0 0   S não é reflexiva, pois (2, 2) /∈ S S não é simétrica, pois MS ̸= (MS)T S é antissimétrica, pois (1, 1), (1, 2), (1, 3) ∈ S, mas (2, 1), (3, 1) /∈ S e (1, 1) ∈ S, com a = b = 1 Relações e suas Propriedades Propriedades das Relações Exemplo: Seja A = {0, 1, 2, 3} e sejam R, S e T relações em A definidas como: R = {(0, 0), (0, 1), (0, 3), (1, 0), (1, 1), (2, 2), (3, 0), (3, 3)} S = {(0, 0), (0, 2), (0, 3), (2, 3)} T = {(0, 1), (2, 3)} R é reflexiva? Simétrica? Transitiva? S é reflexiva? Simétrica? Transitiva? T é reflexiva? Simétrica? Transitiva? Relações e suas Propriedades Propriedades das Relações Exemplo: Seja A = {0, 1, 2, 3} e sejam R, S e T relações em A definidas como: R = {(0, 0), (0, 1), (0, 3), (1, 0), (1, 1), (2, 2), (3, 0), (3, 3)} S = {(0, 0), (0, 2), (0, 3), (2, 3)} T = {(0, 1), (2, 3)} R é reflexiva? Simétrica? Transitiva? S é reflexiva? Simétrica? Transitiva? T é reflexiva? Simétrica? Transitiva? Relações e suas Propriedades Propriedades das Relações Exemplo: Seja A = {0, 1, 2, 3} e sejam R, S e T relações em A definidas como: R = {(0, 0), (0, 1), (0, 3), (1, 0), (1, 1), (2, 2), (3, 0), (3, 3)} S = {(0, 0), (0, 2), (0, 3), (2, 3)} T = {(0, 1), (2, 3)} R é reflexiva? Simétrica? Transitiva? S é reflexiva? Simétrica? Transitiva? T é reflexiva? Simétrica? Transitiva? Relações e suas Propriedades Propriedades das Relações Exemplo: Seja A = {0, 1, 2, 3} e sejam R, S e T relações em A definidas como: R = {(0, 0), (0, 1), (0, 3), (1, 0), (1, 1), (2, 2), (3, 0), (3, 3)} S = {(0, 0), (0, 2), (0, 3), (2, 3)} T = {(0, 1), (2, 3)} R é reflexiva? Simétrica? Transitiva? S é reflexiva? Simétrica? Transitiva? T é reflexiva? Simétrica? Transitiva? Relações e suas Propriedades Propriedades das Relações Exemplo: Seja A = {0, 1, 2, 3} e sejam R, S e T relações em A definidas como: R = {(0, 0), (0, 1), (0, 3), (1, 0), (1, 1), (2, 2), (3, 0), (3, 3)} S = {(0, 0), (0, 2), (0, 3), (2, 3)} T = {(0, 1), (2, 3)} R é reflexiva? Simétrica? Transitiva? S é reflexiva? Simétrica? Transitiva? T é reflexiva? Simétrica? Transitiva? Relações e suas Propriedades Propriedades das Relações Uma representação da relação R é dada por: R é reflexiva Há um loop em cada ponto da representação. Isto significa que cada elemento de A se relaciona consigo mesmo R é simétrica Em cada caso, tem-se uma flecha de partida e de chegada em cada elemento R não é transitiva Há uma seta saindo de 1 para 0, uma de 0 para 3, mas não tem uma seta de 1 para 3 Relações e suas Propriedades Propriedades das Relações Uma representação da relação R é dada por: R é reflexiva Há um loop em cada ponto da representação. Isto significa que cada elemento de A se relaciona consigo mesmo R é simétrica Em cada caso, tem-se uma flecha de partida e de chegada em cada elemento R não é transitiva Há uma seta saindo de 1 para 0, uma de 0 para 3, mas não tem uma seta de 1 para 3 Relações e suas Propriedades Propriedades das Relações Uma representação da relação R é dada por: R é reflexiva Há um loop em cada ponto da representação. Isto significa que cada elemento de A se relaciona consigo mesmo R é simétrica Em cada caso, tem-se uma flecha de partida e de chegada em cada elemento R não é transitiva Há uma seta saindo de 1 para 0, uma de 0 para 3, mas não tem uma seta de 1 para 3 Relações e suas Propriedades Propriedades das Relações Uma representação da relação R é dada por: R é reflexiva Há um loop em cada ponto da representação. Isto significa que cada elemento de A se relaciona consigo mesmo R é simétrica Em cada caso, tem-se uma flecha de partida e de chegada em cada elemento R não é transitiva Há uma seta saindo de 1 para 0, uma de 0 para 3, mas não tem uma seta de 1 para 3 Relações e suas Propriedades Propriedades das Relações Uma representação da relação S é dada por: S não é reflexiva Não há um loop em 1. Assim, (1, 1) /∈ S S não é simétrica Há uma flecha de 0 para 2, mas não há de 2 para 0 S é transitiva Para todo x, y, z ∈ A, se (x, y) ∈ S e (y, z) ∈ S, então (x, z) ∈ S Relações e suas Propriedades Propriedades das Relações Uma representação da relação S é dada por: S não é reflexiva Não há um loop em 1. Assim, (1, 1) /∈ S S não é simétrica Há uma flecha de 0 para 2, mas não há de 2 para 0 S é transitiva Para todo x, y, z ∈ A, se (x, y) ∈ S e (y, z) ∈ S, então (x, z) ∈ S Relações e suas Propriedades Propriedades das Relações Uma representação da relação S é dada por: S não é reflexiva Não há um loop em 1. Assim, (1, 1) /∈ S S não é simétrica Há uma flecha de 0 para 2, mas não há de 2 para 0 S é transitiva Para todo x, y, z ∈ A, se (x, y) ∈ S e (y, z) ∈ S, então (x, z) ∈ S Relações e suas Propriedades Propriedades das Relações Uma representação da relação S é dada por: S não é reflexiva Não há um loop em 1. Assim, (1, 1) /∈ S S não é simétrica Há uma flecha de 0 para 2, mas não há de 2 para 0 S é transitiva Para todo x, y, z ∈ A, se (x, y) ∈ S e (y, z) ∈ S, então (x, z) ∈ S Relações e suas Propriedades Propriedades das Relações Uma representação da relação T é dada por: T não é reflexiva Não há um loop em 0, por exemplo. Assim, (0, 0) /∈ T T não é simétrica (0, 1) ∈ T, mas (1, 0) /∈ T Relações e suas Propriedades Propriedades das Relações Uma representação da relação T é dada por: T não é reflexiva Não há um loop em 0, por exemplo. Assim, (0, 0) /∈ T T não é simétrica (0, 1) ∈ T, mas (1, 0) /∈ T Relações e suas Propriedades Propriedades das Relações Uma representação da relação T é dada por: T não é reflexiva Não há um loop em 0, por exemplo. Assim, (0, 0) /∈ T T não é simétrica (0, 1) ∈ T, mas (1, 0) /∈ T Relações e suas Propriedades Propriedades das Relações Uma representação da relação T é dada por: T é transitiva A condição de transitividade diz que para todo x, y, z ∈ A, se (x, y) ∈ T e (y, z) ∈ T, então (x, z) ∈ T A única maneira disto ser falsa é se existirem x, y, z ∈ A tais que (x, y) ∈ T e (y, z) ∈ T, mas (x, z) /∈ T Mas os únicos elementos em T são (0, 1) e (2, 3), e estes não têm o potencial de se relacionar. Portanto, a hipótese nunca é verdadeira Assim, é impossível T ser não transitiva Portanto, T é transitiva Relações e suas Propriedades Propriedades das Relações Uma representação da relação T é dada por: T é transitiva A condição de transitividade diz que para todo x, y, z ∈ A, se (x, y) ∈ T e (y, z) ∈ T, então (x, z) ∈ T A única maneira disto ser falsa é se existirem x, y, z ∈ A tais que (x, y) ∈ T e (y, z) ∈ T, mas (x, z) /∈ T Mas os únicos elementos em T são (0, 1) e (2, 3), e estes não têm o potencial de se relacionar. Portanto, a hipótese nunca é verdadeira Assim, é impossível T ser não transitiva Portanto, T é transitiva Relações e suas Propriedades Propriedades das Relações Uma representação da relação T é dada por: T é transitiva A condição de transitividade diz que para todo x, y, z ∈ A, se (x, y) ∈ T e (y, z) ∈ T, então (x, z) ∈ T A única maneira disto ser falsa é se existirem x, y, z ∈ A tais que (x, y) ∈ T e (y, z) ∈ T, mas (x, z) /∈ T Mas os únicos elementos em T são (0, 1) e (2, 3), e estes não têm o potencial de se relacionar. Portanto, a hipótese nunca é verdadeira Assim, é impossível T ser não transitiva Portanto, T é transitiva Relações e suas Propriedades Propriedades das Relações Uma representação da relação T é dada por: T é transitiva A condição de transitividade diz que para todo x, y, z ∈ A, se (x, y) ∈ T e (y, z) ∈ T, então (x, z) ∈ T A única maneira disto ser falsa é se existirem x, y, z ∈ A tais que (x, y) ∈ T e (y, z) ∈ T, mas (x, z) /∈ T Mas os únicos elementos em T são (0, 1) e (2, 3), e estes não têm o potencial de se relacionar. Portanto, a hipótese nunca é verdadeira Assim, é impossível T ser não transitiva Portanto, T é transitiva Relações e suas Propriedades Propriedades das Relações Uma representação da relação T é dada por: T é transitiva A condição de transitividade diz que para todo x, y, z ∈ A, se (x, y) ∈ T e (y, z) ∈ T, então (x, z) ∈ T A única maneira disto ser falsa é se existirem x, y, z ∈ A tais que (x, y) ∈ T e (y, z) ∈ T, mas (x, z) /∈ T Mas os únicos elementos em T são (0, 1) e (2, 3), e estes não têm o potencial de se relacionar. Portanto, a hipótese nunca é verdadeira Assim, é impossível T ser não transitiva Portanto, T é transitiva Operações com Relações Combinando Relações Seja A = {1, 2, 3} e B = {1, 2, 3, 4}. As relações R1 = {(1, 1), (2, 2), (3, 3)} e R2 = {(1, 1), (1, 2), (1, 3), (1, 4)} podem ser combinadas para obtermos novas relações: 1 R1 ∪ R2 = {(1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (1, 4)} 2 R1 ∩ R2 = {(1, 1)} 3 R1 − R2 = {(2, 2), (3, 3)} Seja R1 = {(x, y) ∈ R2|x < y} e R2 = {(x, y) ∈ R2|x > y} relações sobre R. Determine R1 ∪ R2, R1 ∩ R2, R1 − R2 e R2 − R1 1 (x, y) ∈ R1 ∪ R2 se, e somente se, (x, y) ∈ R1 ou (x, y) ∈ R2, ou seja, (x, y) ∈ R1 ∪ R2 se, e somente se, x < y ∨ x > y e, portanto, R1 ∪ R2 = {(x, y)|x ̸= y} 2 R1 ∩ R2 = ∅, pois é impossível que x < y ∧ x > y 3 R1 − R2 = R1 4 R2 − R1 = R2 Operações com Relações Combinando Relações Seja A = {1, 2, 3} e B = {1, 2, 3, 4}. As relações R1 = {(1, 1), (2, 2), (3, 3)} e R2 = {(1, 1), (1, 2), (1, 3), (1, 4)} podem ser combinadas para obtermos novas relações: 1 R1 ∪ R2 = {(1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (1, 4)} 2 R1 ∩ R2 = {(1, 1)} 3 R1 − R2 = {(2, 2), (3, 3)} Seja R1 = {(x, y) ∈ R2|x < y} e R2 = {(x, y) ∈ R2|x > y} relações sobre R. Determine R1 ∪ R2, R1 ∩ R2, R1 − R2 e R2 − R1 1 (x, y) ∈ R1 ∪ R2 se, e somente se, (x, y) ∈ R1 ou (x, y) ∈ R2, ou seja, (x, y) ∈ R1 ∪ R2 se, e somente se, x < y ∨ x > y e, portanto, R1 ∪ R2 = {(x, y)|x ̸= y} 2 R1 ∩ R2 = ∅, pois é impossível que x < y ∧ x > y 3 R1 − R2 = R1 4 R2 − R1 = R2 Operações com Relações Combinando Relações Seja A = {1, 2, 3} e B = {1, 2, 3, 4}. As relações R1 = {(1, 1), (2, 2), (3, 3)} e R2 = {(1, 1), (1, 2), (1, 3), (1, 4)} podem ser combinadas para obtermos novas relações: 1 R1 ∪ R2 = {(1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (1, 4)} 2 R1 ∩ R2 = {(1, 1)} 3 R1 − R2 = {(2, 2), (3, 3)} Seja R1 = {(x, y) ∈ R2|x < y} e R2 = {(x, y) ∈ R2|x > y} relações sobre R. Determine R1 ∪ R2, R1 ∩ R2, R1 − R2 e R2 − R1 1 (x, y) ∈ R1 ∪ R2 se, e somente se, (x, y) ∈ R1 ou (x, y) ∈ R2, ou seja, (x, y) ∈ R1 ∪ R2 se, e somente se, x < y ∨ x > y e, portanto, R1 ∪ R2 = {(x, y)|x ̸= y} 2 R1 ∩ R2 = ∅, pois é impossível que x < y ∧ x > y 3 R1 − R2 = R1 4 R2 − R1 = R2 Operações com Relações Combinando Relações Seja A = {1, 2, 3} e B = {1, 2, 3, 4}. As relações R1 = {(1, 1), (2, 2), (3, 3)} e R2 = {(1, 1), (1, 2), (1, 3), (1, 4)} podem ser combinadas para obtermos novas relações: 1 R1 ∪ R2 = {(1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (1, 4)} 2 R1 ∩ R2 = {(1, 1)} 3 R1 − R2 = {(2, 2), (3, 3)} Seja R1 = {(x, y) ∈ R2|x < y} e R2 = {(x, y) ∈ R2|x > y} relações sobre R. Determine R1 ∪ R2, R1 ∩ R2, R1 − R2 e R2 − R1 1 (x, y) ∈ R1 ∪ R2 se, e somente se, (x, y) ∈ R1 ou (x, y) ∈ R2, ou seja, (x, y) ∈ R1 ∪ R2 se, e somente se, x < y ∨ x > y e, portanto, R1 ∪ R2 = {(x, y)|x ̸= y} 2 R1 ∩ R2 = ∅, pois é impossível que x < y ∧ x > y 3 R1 − R2 = R1 4 R2 − R1 = R2 Operações com Relações Combinando Relações Seja A = {1, 2, 3} e B = {1, 2, 3, 4}. As relações R1 = {(1, 1), (2, 2), (3, 3)} e R2 = {(1, 1), (1, 2), (1, 3), (1, 4)} podem ser combinadas para obtermos novas relações: 1 R1 ∪ R2 = {(1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (1, 4)} 2 R1 ∩ R2 = {(1, 1)} 3 R1 − R2 = {(2, 2), (3, 3)} Seja R1 = {(x, y) ∈ R2|x < y} e R2 = {(x, y) ∈ R2|x > y} relações sobre R. Determine R1 ∪ R2, R1 ∩ R2, R1 − R2 e R2 − R1 1 (x, y) ∈ R1 ∪ R2 se, e somente se, (x, y) ∈ R1 ou (x, y) ∈ R2, ou seja, (x, y) ∈ R1 ∪ R2 se, e somente se, x < y ∨ x > y e, portanto, R1 ∪ R2 = {(x, y)|x ̸= y} 2 R1 ∩ R2 = ∅, pois é impossível que x < y ∧ x > y 3 R1 − R2 = R1 4 R2 − R1 = R2 Operações com Relações Combinando Relações Seja A = {1, 2, 3} e B = {1, 2, 3, 4}. As relações R1 = {(1, 1), (2, 2), (3, 3)} e R2 = {(1, 1), (1, 2), (1, 3), (1, 4)} podem ser combinadas para obtermos novas relações: 1 R1 ∪ R2 = {(1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (1, 4)} 2 R1 ∩ R2 = {(1, 1)} 3 R1 − R2 = {(2, 2), (3, 3)} Seja R1 = {(x, y) ∈ R2|x < y} e R2 = {(x, y) ∈ R2|x > y} relações sobre R. Determine R1 ∪ R2, R1 ∩ R2, R1 − R2 e R2 − R1 1 (x, y) ∈ R1 ∪ R2 se, e somente se, (x, y) ∈ R1 ou (x, y) ∈ R2, ou seja, (x, y) ∈ R1 ∪ R2 se, e somente se, x < y ∨ x > y e, portanto, R1 ∪ R2 = {(x, y)|x ̸= y} 2 R1 ∩ R2 = ∅, pois é impossível que x < y ∧ x > y 3 R1 − R2 = R1 4 R2 − R1 = R2 Operações com Relações Combinando Relações Seja A = {1, 2, 3} e B = {1, 2, 3, 4}. As relações R1 = {(1, 1), (2, 2), (3, 3)} e R2 = {(1, 1), (1, 2), (1, 3), (1, 4)} podem ser combinadas para obtermos novas relações: 1 R1 ∪ R2 = {(1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (1, 4)} 2 R1 ∩ R2 = {(1, 1)} 3 R1 − R2 = {(2, 2), (3, 3)} Seja R1 = {(x, y) ∈ R2|x < y} e R2 = {(x, y) ∈ R2|x > y} relações sobre R. Determine R1 ∪ R2, R1 ∩ R2, R1 − R2 e R2 − R1 1 (x, y) ∈ R1 ∪ R2 se, e somente se, (x, y) ∈ R1 ou (x, y) ∈ R2, ou seja, (x, y) ∈ R1 ∪ R2 se, e somente se, x < y ∨ x > y e, portanto, R1 ∪ R2 = {(x, y)|x ̸= y} 2 R1 ∩ R2 = ∅, pois é impossível que x < y ∧ x > y 3 R1 − R2 = R1 4 R2 − R1 = R2 Operações com Relações Combinando Relações Seja A = {1, 2, 3} e B = {1, 2, 3, 4}. As relações R1 = {(1, 1), (2, 2), (3, 3)} e R2 = {(1, 1), (1, 2), (1, 3), (1, 4)} podem ser combinadas para obtermos novas relações: 1 R1 ∪ R2 = {(1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (1, 4)} 2 R1 ∩ R2 = {(1, 1)} 3 R1 − R2 = {(2, 2), (3, 3)} Seja R1 = {(x, y) ∈ R2|x < y} e R2 = {(x, y) ∈ R2|x > y} relações sobre R. Determine R1 ∪ R2, R1 ∩ R2, R1 − R2 e R2 − R1 1 (x, y) ∈ R1 ∪ R2 se, e somente se, (x, y) ∈ R1 ou (x, y) ∈ R2, ou seja, (x, y) ∈ R1 ∪ R2 se, e somente se, x < y ∨ x > y e, portanto, R1 ∪ R2 = {(x, y)|x ̸= y} 2 R1 ∩ R2 = ∅, pois é impossível que x < y ∧ x > y 3 R1 − R2 = R1 4 R2 − R1 = R2 Operações com Relações Combinando Relações Seja A = {1, 2, 3} e B = {1, 2, 3, 4}. As relações R1 = {(1, 1), (2, 2), (3, 3)} e R2 = {(1, 1), (1, 2), (1, 3), (1, 4)} podem ser combinadas para obtermos novas relações: 1 R1 ∪ R2 = {(1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (1, 4)} 2 R1 ∩ R2 = {(1, 1)} 3 R1 − R2 = {(2, 2), (3, 3)} Seja R1 = {(x, y) ∈ R2|x < y} e R2 = {(x, y) ∈ R2|x > y} relações sobre R. Determine R1 ∪ R2, R1 ∩ R2, R1 − R2 e R2 − R1 1 (x, y) ∈ R1 ∪ R2 se, e somente se, (x, y) ∈ R1 ou (x, y) ∈ R2, ou seja, (x, y) ∈ R1 ∪ R2 se, e somente se, x < y ∨ x > y e, portanto, R1 ∪ R2 = {(x, y)|x ̸= y} 2 R1 ∩ R2 = ∅, pois é impossível que x < y ∧ x > y 3 R1 − R2 = R1 4 R2 − R1 = R2 Operações com Relações Combinando Relações Há uma outra maneira de combinar relações que é análoga à composição de funções Definição. Seja R uma relação de A em B e S uma relação de B em C. A composição de R e S, denotada por S ◦ R, é a relação que consiste dos pares ordenados (a, c), onde a ∈ A, c ∈ C, de forma que existe um elemento b ∈ B tal que (a, b) ∈ R e (b, c) ∈ S Exemplo. Encontre S ◦ R, onde R é uma relação de A = {1, 2, 3} em B = {1, 2, 3, 4}, S é uma relação de B = {1, 2, 3, 4} em C = {0, 1, 2} definidas por R = {(1, 1), (1, 4), (2, 3), (3, 1), (3, 4)} e S = {(1, 0), (2, 0), (3, 1), (3, 2), (4, 1)} 1 S ◦ R = {(1, 0), (1, 1), (2, 1), (2, 2), (3, 0), (3, 1)} Operações com Relações Combinando Relações Há uma outra maneira de combinar relações que é análoga à composição de funções Definição. Seja R uma relação de A em B e S uma relação de B em C. A composição de R e S, denotada por S ◦ R, é a relação que consiste dos pares ordenados (a, c), onde a ∈ A, c ∈ C, de forma que existe um elemento b ∈ B tal que (a, b) ∈ R e (b, c) ∈ S Exemplo. Encontre S ◦ R, onde R é uma relação de A = {1, 2, 3} em B = {1, 2, 3, 4}, S é uma relação de B = {1, 2, 3, 4} em C = {0, 1, 2} definidas por R = {(1, 1), (1, 4), (2, 3), (3, 1), (3, 4)} e S = {(1, 0), (2, 0), (3, 1), (3, 2), (4, 1)} 1 S ◦ R = {(1, 0), (1, 1), (2, 1), (2, 2), (3, 0), (3, 1)} Operações com Relações Combinando Relações Há uma outra maneira de combinar relações que é análoga à composição de funções Definição. Seja R uma relação de A em B e S uma relação de B em C. A composição de R e S, denotada por S ◦ R, é a relação que consiste dos pares ordenados (a, c), onde a ∈ A, c ∈ C, de forma que existe um elemento b ∈ B tal que (a, b) ∈ R e (b, c) ∈ S Exemplo. Encontre S ◦ R, onde R é uma relação de A = {1, 2, 3} em B = {1, 2, 3, 4}, S é uma relação de B = {1, 2, 3, 4} em C = {0, 1, 2} definidas por R = {(1, 1), (1, 4), (2, 3), (3, 1), (3, 4)} e S = {(1, 0), (2, 0), (3, 1), (3, 2), (4, 1)} 1 S ◦ R = {(1, 0), (1, 1), (2, 1), (2, 2), (3, 0), (3, 1)} Operações com Relações Combinando Relações Há uma outra maneira de combinar relações que é análoga à composição de funções Definição. Seja R uma relação de A em B e S uma relação de B em C. A composição de R e S, denotada por S ◦ R, é a relação que consiste dos pares ordenados (a, c), onde a ∈ A, c ∈ C, de forma que existe um elemento b ∈ B tal que (a, b) ∈ R e (b, c) ∈ S Exemplo. Encontre S ◦ R, onde R é uma relação de A = {1, 2, 3} em B = {1, 2, 3, 4}, S é uma relação de B = {1, 2, 3, 4} em C = {0, 1, 2} definidas por R = {(1, 1), (1, 4), (2, 3), (3, 1), (3, 4)} e S = {(1, 0), (2, 0), (3, 1), (3, 2), (4, 1)} 1 S ◦ R = {(1, 0), (1, 1), (2, 1), (2, 2), (3, 0), (3, 1)} Operações com Relações Combinando Relações Definição. Seja R uma relação em um conjunto A. As potências Rn, n = 1, 2, · · · , são definidas recursivamente por R1 = R e Rn+1 = Rn ◦ R Exemplo. Seja R = {(1, 1), (2, 1), (3, 2), (4, 3)}. Encontre as potências Rn, n = 2, 3, 4, · · · 1 R2 = R ◦ R = {(1, 1), (2, 1), (3, 1), (4, 2)} 2 R3 = R2 ◦ R = {(1, 1), (2, 1), (3, 1), (4, 1)} 3 R4 = R3 ◦ R = {(1, 1), (2, 1), (3, 1), (4, 2)} = R3 4 Note que Rn = R3 para n = 5, 6, 7, · · · Teorema. A relação R em um conjunto A é transitiva se, e somente se, Rn ⊂ R para n = 2, 3, 4, · · · Operações com Relações Combinando Relações Definição. Seja R uma relação em um conjunto A. As potências Rn, n = 1, 2, · · · , são definidas recursivamente por R1 = R e Rn+1 = Rn ◦ R Exemplo. Seja R = {(1, 1), (2, 1), (3, 2), (4, 3)}. Encontre as potências Rn, n = 2, 3, 4, · · · 1 R2 = R ◦ R = {(1, 1), (2, 1), (3, 1), (4, 2)} 2 R3 = R2 ◦ R = {(1, 1), (2, 1), (3, 1), (4, 1)} 3 R4 = R3 ◦ R = {(1, 1), (2, 1), (3, 1), (4, 2)} = R3 4 Note que Rn = R3 para n = 5, 6, 7, · · · Teorema. A relação R em um conjunto A é transitiva se, e somente se, Rn ⊂ R para n = 2, 3, 4, · · · Operações com Relações Combinando Relações Definição. Seja R uma relação em um conjunto A. As potências Rn, n = 1, 2, · · · , são definidas recursivamente por R1 = R e Rn+1 = Rn ◦ R Exemplo. Seja R = {(1, 1), (2, 1), (3, 2), (4, 3)}. Encontre as potências Rn, n = 2, 3, 4, · · · 1 R2 = R ◦ R = {(1, 1), (2, 1), (3, 1), (4, 2)} 2 R3 = R2 ◦ R = {(1, 1), (2, 1), (3, 1), (4, 1)} 3 R4 = R3 ◦ R = {(1, 1), (2, 1), (3, 1), (4, 2)} = R3 4 Note que Rn = R3 para n = 5, 6, 7, · · · Teorema. A relação R em um conjunto A é transitiva se, e somente se, Rn ⊂ R para n = 2, 3, 4, · · · Operações com Relações Combinando Relações Definição. Seja R uma relação em um conjunto A. As potências Rn, n = 1, 2, · · · , são definidas recursivamente por R1 = R e Rn+1 = Rn ◦ R Exemplo. Seja R = {(1, 1), (2, 1), (3, 2), (4, 3)}. Encontre as potências Rn, n = 2, 3, 4, · · · 1 R2 = R ◦ R = {(1, 1), (2, 1), (3, 1), (4, 2)} 2 R3 = R2 ◦ R = {(1, 1), (2, 1), (3, 1), (4, 1)} 3 R4 = R3 ◦ R = {(1, 1), (2, 1), (3, 1), (4, 2)} = R3 4 Note que Rn = R3 para n = 5, 6, 7, · · · Teorema. A relação R em um conjunto A é transitiva se, e somente se, Rn ⊂ R para n = 2, 3, 4, · · · Operações com Relações Combinando Relações Definição. Seja R uma relação em um conjunto A. As potências Rn, n = 1, 2, · · · , são definidas recursivamente por R1 = R e Rn+1 = Rn ◦ R Exemplo. Seja R = {(1, 1), (2, 1), (3, 2), (4, 3)}. Encontre as potências Rn, n = 2, 3, 4, · · · 1 R2 = R ◦ R = {(1, 1), (2, 1), (3, 1), (4, 2)} 2 R3 = R2 ◦ R = {(1, 1), (2, 1), (3, 1), (4, 1)} 3 R4 = R3 ◦ R = {(1, 1), (2, 1), (3, 1), (4, 2)} = R3 4 Note que Rn = R3 para n = 5, 6, 7, · · · Teorema. A relação R em um conjunto A é transitiva se, e somente se, Rn ⊂ R para n = 2, 3, 4, · · · Operações com Relações Combinando Relações Definição. Seja R uma relação em um conjunto A. As potências Rn, n = 1, 2, · · · , são definidas recursivamente por R1 = R e Rn+1 = Rn ◦ R Exemplo. Seja R = {(1, 1), (2, 1), (3, 2), (4, 3)}. Encontre as potências Rn, n = 2, 3, 4, · · · 1 R2 = R ◦ R = {(1, 1), (2, 1), (3, 1), (4, 2)} 2 R3 = R2 ◦ R = {(1, 1), (2, 1), (3, 1), (4, 1)} 3 R4 = R3 ◦ R = {(1, 1), (2, 1), (3, 1), (4, 2)} = R3 4 Note que Rn = R3 para n = 5, 6, 7, · · · Teorema. A relação R em um conjunto A é transitiva se, e somente se, Rn ⊂ R para n = 2, 3, 4, · · · Operações com Relações Combinando Relações Definição. Seja R uma relação em um conjunto A. As potências Rn, n = 1, 2, · · · , são definidas recursivamente por R1 = R e Rn+1 = Rn ◦ R Exemplo. Seja R = {(1, 1), (2, 1), (3, 2), (4, 3)}. Encontre as potências Rn, n = 2, 3, 4, · · · 1 R2 = R ◦ R = {(1, 1), (2, 1), (3, 1), (4, 2)} 2 R3 = R2 ◦ R = {(1, 1), (2, 1), (3, 1), (4, 1)} 3 R4 = R3 ◦ R = {(1, 1), (2, 1), (3, 1), (4, 2)} = R3 4 Note que Rn = R3 para n = 5, 6, 7, · · · Teorema. A relação R em um conjunto A é transitiva se, e somente se, Rn ⊂ R para n = 2, 3, 4, · · · Operações com Relações Combinando Relações Definição. Seja R uma relação em um conjunto A. As potências Rn, n = 1, 2, · · · , são definidas recursivamente por R1 = R e Rn+1 = Rn ◦ R Exemplo. Seja R = {(1, 1), (2, 1), (3, 2), (4, 3)}. Encontre as potências Rn, n = 2, 3, 4, · · · 1 R2 = R ◦ R = {(1, 1), (2, 1), (3, 1), (4, 2)} 2 R3 = R2 ◦ R = {(1, 1), (2, 1), (3, 1), (4, 1)} 3 R4 = R3 ◦ R = {(1, 1), (2, 1), (3, 1), (4, 2)} = R3 4 Note que Rn = R3 para n = 5, 6, 7, · · · Teorema. A relação R em um conjunto A é transitiva se, e somente se, Rn ⊂ R para n = 2, 3, 4, · · · Operações com Relações Operações Booleanas Operadores booleanos sobre matrizes podem ser utilizados para calcular a união e a interseção entre duas relações Definição. Sejam duas relações R e S, representadas por duas matrizes MR e MS, respectivamente. Temos: MR∪S = MR ∨ MS e MR∩S = MR ∧ MS Exemplo. Sejam R e S relações sobre A representadas pelas matrizes MR =   1 0 1 1 0 0 0 1 0   MS =   1 0 1 0 1 1 1 0 0  . Temos: MR∪S =   1 0 1 1 1 1 1 1 0   MR∩S =   1 0 1 0 0 0 0 0 0   Operações com Relações Operações Booleanas Operadores booleanos sobre matrizes podem ser utilizados para calcular a união e a interseção entre duas relações Definição. Sejam duas relações R e S, representadas por duas matrizes MR e MS, respectivamente. Temos: MR∪S = MR ∨ MS e MR∩S = MR ∧ MS Exemplo. Sejam R e S relações sobre A representadas pelas matrizes MR =   1 0 1 1 0 0 0 1 0   MS =   1 0 1 0 1 1 1 0 0  . Temos: MR∪S =   1 0 1 1 1 1 1 1 0   MR∩S =   1 0 1 0 0 0 0 0 0   Operações com Relações Operações Booleanas Operadores booleanos sobre matrizes podem ser utilizados para calcular a união e a interseção entre duas relações Definição. Sejam duas relações R e S, representadas por duas matrizes MR e MS, respectivamente. Temos: MR∪S = MR ∨ MS e MR∩S = MR ∧ MS Exemplo. Sejam R e S relações sobre A representadas pelas matrizes MR =   1 0 1 1 0 0 0 1 0   MS =   1 0 1 0 1 1 1 0 0  . Temos: MR∪S =   1 0 1 1 1 1 1 1 0   MR∩S =   1 0 1 0 0 0 0 0 0   Operações com Relações Operações Booleanas Operadores booleanos sobre matrizes podem ser utilizados para calcular a união e a interseção entre duas relações Definição. Sejam duas relações R e S, representadas por duas matrizes MR e MS, respectivamente. Temos: MR∪S = MR ∨ MS e MR∩S = MR ∧ MS Exemplo. Sejam R e S relações sobre A representadas pelas matrizes MR =   1 0 1 1 0 0 0 1 0   MS =   1 0 1 0 1 1 1 0 0  . Temos: MR∪S =   1 0 1 1 1 1 1 1 0   MR∩S =   1 0 1 0 0 0 0 0 0   Operações com Relações Operações Booleanas Operadores booleanos sobre matrizes podem ser utilizados para calcular a união e a interseção entre duas relações Definição. Sejam duas relações R e S, representadas por duas matrizes MR e MS, respectivamente. Temos: MR∪S = MR ∨ MS e MR∩S = MR ∧ MS Exemplo. Sejam R e S relações sobre A representadas pelas matrizes MR =   1 0 1 1 0 0 0 1 0   MS =   1 0 1 0 1 1 1 0 0  . Temos: MR∪S =   1 0 1 1 1 1 1 1 0   MR∩S =   1 0 1 0 0 0 0 0 0   Operações com Relações Operações Booleanas Operadores booleanos sobre matrizes podem ser utilizados para calcular a união e a interseção entre duas relações Definição. Sejam duas relações R e S, representadas por duas matrizes MR e MS, respectivamente. Temos: MR∪S = MR ∨ MS e MR∩S = MR ∧ MS Exemplo. Sejam R e S relações sobre A representadas pelas matrizes MR =   1 0 1 1 0 0 0 1 0   MS =   1 0 1 0 1 1 1 0 0  . Temos: MR∪S =   1 0 1 1 1 1 1 1 0   MR∩S =   1 0 1 0 0 0 0 0 0   Operações com Relações Operações Booleanas A matriz de uma composição pode ser obtida usando o produto booleano de matrizes Definição. Sejam A e B matrizes zero-um de ordem m × k e k × n, respectivamente. O produto booleano de A e B, denotado por A ⊙ B = [cij], é uma matriz m × n tal que cij = (ai1 ∧ b1j) ∨ (ai2 ∧ b2j) ∨ · · · ∨ (aik ∧ bkj) Note que o produto booleano é análogo ao produto usual de matrizes, mas com a operação ∨ no lugar da adição e a operação ∧ no lugar da multiplicação Da definição de produto booleano segue que: MS◦R = MR ⊙ MS Operações com Relações Operações Booleanas A matriz de uma composição pode ser obtida usando o produto booleano de matrizes Definição. Sejam A e B matrizes zero-um de ordem m × k e k × n, respectivamente. O produto booleano de A e B, denotado por A ⊙ B = [cij], é uma matriz m × n tal que cij = (ai1 ∧ b1j) ∨ (ai2 ∧ b2j) ∨ · · · ∨ (aik ∧ bkj) Note que o produto booleano é análogo ao produto usual de matrizes, mas com a operação ∨ no lugar da adição e a operação ∧ no lugar da multiplicação Da definição de produto booleano segue que: MS◦R = MR ⊙ MS Operações com Relações Operações Booleanas A matriz de uma composição pode ser obtida usando o produto booleano de matrizes Definição. Sejam A e B matrizes zero-um de ordem m × k e k × n, respectivamente. O produto booleano de A e B, denotado por A ⊙ B = [cij], é uma matriz m × n tal que cij = (ai1 ∧ b1j) ∨ (ai2 ∧ b2j) ∨ · · · ∨ (aik ∧ bkj) Note que o produto booleano é análogo ao produto usual de matrizes, mas com a operação ∨ no lugar da adição e a operação ∧ no lugar da multiplicação Da definição de produto booleano segue que: MS◦R = MR ⊙ MS Operações com Relações Operações Booleanas A matriz de uma composição pode ser obtida usando o produto booleano de matrizes Definição. Sejam A e B matrizes zero-um de ordem m × k e k × n, respectivamente. O produto booleano de A e B, denotado por A ⊙ B = [cij], é uma matriz m × n tal que cij = (ai1 ∧ b1j) ∨ (ai2 ∧ b2j) ∨ · · · ∨ (aik ∧ bkj) Note que o produto booleano é análogo ao produto usual de matrizes, mas com a operação ∨ no lugar da adição e a operação ∧ no lugar da multiplicação Da definição de produto booleano segue que: MS◦R = MR ⊙ MS Operações com Relações Operações Booleanas A matriz de uma composição pode ser obtida usando o produto booleano de matrizes Definição. Sejam A e B matrizes zero-um de ordem m × k e k × n, respectivamente. O produto booleano de A e B, denotado por A ⊙ B = [cij], é uma matriz m × n tal que cij = (ai1 ∧ b1j) ∨ (ai2 ∧ b2j) ∨ · · · ∨ (aik ∧ bkj) Note que o produto booleano é análogo ao produto usual de matrizes, mas com a operação ∨ no lugar da adição e a operação ∧ no lugar da multiplicação Da definição de produto booleano segue que: MS◦R = MR ⊙ MS Operações com Relações Operações Booleanas A matriz de uma composição pode ser obtida usando o produto booleano de matrizes Definição. Sejam A e B matrizes zero-um de ordem m × k e k × n, respectivamente. O produto booleano de A e B, denotado por A ⊙ B = [cij], é uma matriz m × n tal que cij = (ai1 ∧ b1j) ∨ (ai2 ∧ b2j) ∨ · · · ∨ (aik ∧ bkj) Note que o produto booleano é análogo ao produto usual de matrizes, mas com a operação ∨ no lugar da adição e a operação ∧ no lugar da multiplicação Da definição de produto booleano segue que: MS◦R = MR ⊙ MS Operações com Relações Operações Booleanas Exemplo. Encontre a matriz que representa S ◦ R, quando as matrizes que representam R e S são MR =   1 0 1 1 1 0 0 0 0   MS =   0 1 0 0 0 1 1 0 1   A matriz para S ◦ R é MS◦R = MR ◦ MS =   1 1 1 0 1 1 0 0 0   A matriz que representa a composição de duas relações pode ser usada oara encontrar MRn = M[n] R Operações com Relações Operações Booleanas Exemplo. Encontre a matriz que representa S ◦ R, quando as matrizes que representam R e S são MR =   1 0 1 1 1 0 0 0 0   MS =   0 1 0 0 0 1 1 0 1   A matriz para S ◦ R é MS◦R = MR ◦ MS =   1 1 1 0 1 1 0 0 0   A matriz que representa a composição de duas relações pode ser usada oara encontrar MRn = M[n] R Operações com Relações Operações Booleanas Exemplo. Encontre a matriz que representa S ◦ R, quando as matrizes que representam R e S são MR =   1 0 1 1 1 0 0 0 0   MS =   0 1 0 0 0 1 1 0 1   A matriz para S ◦ R é MS◦R = MR ◦ MS =   1 1 1 0 1 1 0 0 0   A matriz que representa a composição de duas relações pode ser usada oara encontrar MRn = M[n] R Operações com Relações Operações Booleanas Exemplo. Encontre a matriz que representa S ◦ R, quando as matrizes que representam R e S são MR =   1 0 1 1 1 0 0 0 0   MS =   0 1 0 0 0 1 1 0 1   A matriz para S ◦ R é MS◦R = MR ◦ MS =   1 1 1 0 1 1 0 0 0   A matriz que representa a composição de duas relações pode ser usada oara encontrar MRn = M[n] R Operações com Relações Operações Booleanas Exemplo. Encontre a matriz que representa S ◦ R, quando as matrizes que representam R e S são MR =   1 0 1 1 1 0 0 0 0   MS =   0 1 0 0 0 1 1 0 1   A matriz para S ◦ R é MS◦R = MR ◦ MS =   1 1 1 0 1 1 0 0 0   A matriz que representa a composição de duas relações pode ser usada oara encontrar MRn = M[n] R Relações e suas Propriedades Matriz de uma Relação Transitiva Seja R ⊆ A × A uma relação transitiva, isto é Se (a, b) ∈ R e (b, c) ∈ R, então (a, c) ∈ R E isto é a composição R ◦ R e R ◦ R ⊆ R Proposição. Se R é uma relação transitiva de A2 e MR é a sua representação matricial, então Mn R ⊆ MR, ∀n ∈ N Se para algum n, Mn R ⊈ MR, então R não é uma relação transitiva Relações e suas Propriedades Matriz de uma Relação Transitiva Seja R ⊆ A × A uma relação transitiva, isto é Se (a, b) ∈ R e (b, c) ∈ R, então (a, c) ∈ R E isto é a composição R ◦ R e R ◦ R ⊆ R Proposição. Se R é uma relação transitiva de A2 e MR é a sua representação matricial, então Mn R ⊆ MR, ∀n ∈ N Se para algum n, Mn R ⊈ MR, então R não é uma relação transitiva Relações e suas Propriedades Matriz de uma Relação Transitiva Seja R ⊆ A × A uma relação transitiva, isto é Se (a, b) ∈ R e (b, c) ∈ R, então (a, c) ∈ R E isto é a composição R ◦ R e R ◦ R ⊆ R Proposição. Se R é uma relação transitiva de A2 e MR é a sua representação matricial, então Mn R ⊆ MR, ∀n ∈ N Se para algum n, Mn R ⊈ MR, então R não é uma relação transitiva Relações e suas Propriedades Matriz de uma Relação Transitiva Seja R ⊆ A × A uma relação transitiva, isto é Se (a, b) ∈ R e (b, c) ∈ R, então (a, c) ∈ R E isto é a composição R ◦ R e R ◦ R ⊆ R Proposição. Se R é uma relação transitiva de A2 e MR é a sua representação matricial, então Mn R ⊆ MR, ∀n ∈ N Se para algum n, Mn R ⊈ MR, então R não é uma relação transitiva Relações e suas Propriedades Matriz de uma Relação Transitiva Seja R ⊆ A × A uma relação transitiva, isto é Se (a, b) ∈ R e (b, c) ∈ R, então (a, c) ∈ R E isto é a composição R ◦ R e R ◦ R ⊆ R Proposição. Se R é uma relação transitiva de A2 e MR é a sua representação matricial, então Mn R ⊆ MR, ∀n ∈ N Se para algum n, Mn R ⊈ MR, então R não é uma relação transitiva Relações e suas Propriedades Matriz de uma Relação Transitiva Seja R ⊆ A × A uma relação transitiva, isto é Se (a, b) ∈ R e (b, c) ∈ R, então (a, c) ∈ R E isto é a composição R ◦ R e R ◦ R ⊆ R Proposição. Se R é uma relação transitiva de A2 e MR é a sua representação matricial, então Mn R ⊆ MR, ∀n ∈ N Se para algum n, Mn R ⊈ MR, então R não é uma relação transitiva Relações e suas Propriedades Matriz de uma Relação Transitiva Seja R ⊆ A × A uma relação transitiva, isto é Se (a, b) ∈ R e (b, c) ∈ R, então (a, c) ∈ R E isto é a composição R ◦ R e R ◦ R ⊆ R Proposição. Se R é uma relação transitiva de A2 e MR é a sua representação matricial, então Mn R ⊆ MR, ∀n ∈ N Se para algum n, Mn R ⊈ MR, então R não é uma relação transitiva Relações e suas Propriedades Matriz de uma Relação Transitiva Mostre que a relação R sobre A = {1, 2, 3} dada pela matriz MR = [ 1 1 1 0 0 1 0 0 1 ] é transitiva Relações e suas Propriedades Matriz de uma Relação Transitiva Mostre que a relação R sobre A = {1, 2, 3} dada pela matriz M_R = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \end{bmatrix} é transitiva Como M_R^2 = M_R \circ M_R = M_R e, portanto, M_R^2 \subseteq M_R, temos que a relação é transitiva Fechos de Relações Fechos de uma Relação Se uma relação R em um conjunto A não possui certa propriedade, podemos tentar estender R a fim de obter uma relação R∗ em A que tenha a propriedade desejada A nova relação R∗ conterá todos os pares ordenados que R contém mais os pares ordenados adicionais necessários para que a propriedade desejada se verifique Portanto, R ⊆ R∗ Naturalmente, deseja-se adicionar o menor número de pares possível, de modo a obter a menor relação R∗ sobre A que possui a propriedade deseja Se R∗ é a menor relação que possui a propriedade deseja, então R∗ chamada de fecho de R com respeito à propriedade em questão Fechos de Relações Fechos de uma Relação Se uma relação R em um conjunto A não possui certa propriedade, podemos tentar estender R a fim de obter uma relação R∗ em A que tenha a propriedade desejada A nova relação R∗ conterá todos os pares ordenados que R contém mais os pares ordenados adicionais necessários para que a propriedade desejada se verifique Portanto, R ⊆ R∗ Naturalmente, deseja-se adicionar o menor número de pares possível, de modo a obter a menor relação R∗ sobre A que possui a propriedade deseja Se R∗ é a menor relação que possui a propriedade deseja, então R∗ chamada de fecho de R com respeito à propriedade em questão Fechos de Relações Fechos de uma Relação Se uma relação R em um conjunto A não possui certa propriedade, podemos tentar estender R a fim de obter uma relação R∗ em A que tenha a propriedade desejada A nova relação R∗ conterá todos os pares ordenados que R contém mais os pares ordenados adicionais necessários para que a propriedade desejada se verifique Portanto, R ⊆ R∗ Naturalmente, deseja-se adicionar o menor número de pares possível, de modo a obter a menor relação R∗ sobre A que possui a propriedade deseja Se R∗ é a menor relação que possui a propriedade deseja, então R∗ chamada de fecho de R com respeito à propriedade em questão Fechos de Relações Fechos de uma Relação Se uma relação R em um conjunto A não possui certa propriedade, podemos tentar estender R a fim de obter uma relação R∗ em A que tenha a propriedade desejada A nova relação R∗ conterá todos os pares ordenados que R contém mais os pares ordenados adicionais necessários para que a propriedade desejada se verifique Portanto, R ⊆ R∗ Naturalmente, deseja-se adicionar o menor número de pares possível, de modo a obter a menor relação R∗ sobre A que possui a propriedade deseja Se R∗ é a menor relação que possui a propriedade deseja, então R∗ chamada de fecho de R com respeito à propriedade em questão Fechos de Relações Fechos de uma Relação Se uma relação R em um conjunto A não possui certa propriedade, podemos tentar estender R a fim de obter uma relação R∗ em A que tenha a propriedade desejada A nova relação R∗ conterá todos os pares ordenados que R contém mais os pares ordenados adicionais necessários para que a propriedade desejada se verifique Portanto, R ⊆ R∗ Naturalmente, deseja-se adicionar o menor número de pares possível, de modo a obter a menor relação R∗ sobre A que possui a propriedade deseja Se R∗ é a menor relação que possui a propriedade deseja, então R∗ chamada de fecho de R com respeito à propriedade em questão Fechos de Relações Fechos de uma Relação Definição. Seja A um conjunto, R uma relação binária em A e seja p uma propriedade. O fecho de R é a relação binária R∗ em A que possui a propriedade p e satisfaz as seguintes condições: R∗ possui a propriedade p; R ⊆ R∗; S é uma outra relação qualquer que contém R e satisfaz a propriedade p, então R∗ ⊆ S Podemos definir os seguintes fechos Reflexivo Simétrico Transitivo de uma relação em um conjunto Naturalmente, se a relação já realiza uma propriedade, ela é seu próprio fecho com respeito a esta propriedade Fechos de Relações Fechos de uma Relação Definição. Seja A um conjunto, R uma relação binária em A e seja p uma propriedade. O fecho de R é a relação binária R∗ em A que possui a propriedade p e satisfaz as seguintes condições: R∗ possui a propriedade p; R ⊆ R∗; S é uma outra relação qualquer que contém R e satisfaz a propriedade p, então R∗ ⊆ S Podemos definir os seguintes fechos Reflexivo Simétrico Transitivo de uma relação em um conjunto Naturalmente, se a relação já realiza uma propriedade, ela é seu próprio fecho com respeito a esta propriedade Fechos de Relações Fechos de uma Relação Definição. Seja A um conjunto, R uma relação binária em A e seja p uma propriedade. O fecho de R é a relação binária R∗ em A que possui a propriedade p e satisfaz as seguintes condições: R∗ possui a propriedade p; R ⊆ R∗; S é uma outra relação qualquer que contém R e satisfaz a propriedade p, então R∗ ⊆ S Podemos definir os seguintes fechos Reflexivo Simétrico Transitivo de uma relação em um conjunto Naturalmente, se a relação já realiza uma propriedade, ela é seu próprio fecho com respeito a esta propriedade Fechos de Relações Fechos de uma Relação Definição. Seja A um conjunto, R uma relação binária em A e seja p uma propriedade. O fecho de R é a relação binária R∗ em A que possui a propriedade p e satisfaz as seguintes condições: R∗ possui a propriedade p; R ⊆ R∗; S é uma outra relação qualquer que contém R e satisfaz a propriedade p, então R∗ ⊆ S Podemos definir os seguintes fechos Reflexivo Simétrico Transitivo de uma relação em um conjunto Naturalmente, se a relação já realiza uma propriedade, ela é seu próprio fecho com respeito a esta propriedade Fechos de Relações Fechos de uma Relação Definição. Seja A um conjunto, R uma relação binária em A e seja p uma propriedade. O fecho de R é a relação binária R∗ em A que possui a propriedade p e satisfaz as seguintes condições: R∗ possui a propriedade p; R ⊆ R∗; S é uma outra relação qualquer que contém R e satisfaz a propriedade p, então R∗ ⊆ S Podemos definir os seguintes fechos Reflexivo Simétrico Transitivo de uma relação em um conjunto Naturalmente, se a relação já realiza uma propriedade, ela é seu próprio fecho com respeito a esta propriedade Fechos de Relações Fechos de uma Relação Definição. Seja A um conjunto, R uma relação binária em A e seja p uma propriedade. O fecho de R é a relação binária R∗ em A que possui a propriedade p e satisfaz as seguintes condições: R∗ possui a propriedade p; R ⊆ R∗; S é uma outra relação qualquer que contém R e satisfaz a propriedade p, então R∗ ⊆ S Podemos definir os seguintes fechos Reflexivo Simétrico Transitivo de uma relação em um conjunto Naturalmente, se a relação já realiza uma propriedade, ela é seu próprio fecho com respeito a esta propriedade Fechos de Relações Fechos de uma Relação Definição. Seja A um conjunto, R uma relação binária em A e seja p uma propriedade. O fecho de R é a relação binária R∗ em A que possui a propriedade p e satisfaz as seguintes condições: R∗ possui a propriedade p; R ⊆ R∗; S é uma outra relação qualquer que contém R e satisfaz a propriedade p, então R∗ ⊆ S Podemos definir os seguintes fechos Reflexivo Simétrico Transitivo de uma relação em um conjunto Naturalmente, se a relação já realiza uma propriedade, ela é seu próprio fecho com respeito a esta propriedade Fechos de Relações Fechos de uma Relação Exemplo. Seja A = {1, 2, 3} e seja R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)} Note que R não é reflexiva O fecho de R com respeito à reflexividade é: R∗ = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (2, 2), (3, 3)} Ou R∗ = R ∪ ∆, em que ∆ = {(2, 2), (3, 3)} Observe que os elementos em ∆ são os únicos pares da forma (x, x), com x ∈ A, que não estão em R Note que R∗ é reflexiva e contém R Além disso, qualquer relação reflexiva em A deve conter os novos pares ordenados que incluímos: (2, 2) e (3, 3) de forma que não pode haver relação reflexiva menor do que esta Ou seja, qualquer relação reflexiva contendo R deve conter a relação R∗ Fechos de Relações Fechos de uma Relação Exemplo. Seja A = {1, 2, 3} e seja R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)} Note que R não é reflexiva O fecho de R com respeito à reflexividade é: R∗ = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (2, 2), (3, 3)} Ou R∗ = R ∪ ∆, em que ∆ = {(2, 2), (3, 3)} Observe que os elementos em ∆ são os únicos pares da forma (x, x), com x ∈ A, que não estão em R Note que R∗ é reflexiva e contém R Além disso, qualquer relação reflexiva em A deve conter os novos pares ordenados que incluímos: (2, 2) e (3, 3) de forma que não pode haver relação reflexiva menor do que esta Ou seja, qualquer relação reflexiva contendo R deve conter a relação R∗ Fechos de Relações Fechos de uma Relação Exemplo. Seja A = {1, 2, 3} e seja R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)} Note que R não é reflexiva O fecho de R com respeito à reflexividade é: R∗ = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (2, 2), (3, 3)} Ou R∗ = R ∪ ∆, em que ∆ = {(2, 2), (3, 3)} Observe que os elementos em ∆ são os únicos pares da forma (x, x), com x ∈ A, que não estão em R Note que R∗ é reflexiva e contém R Além disso, qualquer relação reflexiva em A deve conter os novos pares ordenados que incluímos: (2, 2) e (3, 3) de forma que não pode haver relação reflexiva menor do que esta Ou seja, qualquer relação reflexiva contendo R deve conter a relação R∗ Fechos de Relações Fechos de uma Relação Exemplo. Seja A = {1, 2, 3} e seja R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)} Note que R não é reflexiva O fecho de R com respeito à reflexividade é: R∗ = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (2, 2), (3, 3)} Ou R∗ = R ∪ ∆, em que ∆ = {(2, 2), (3, 3)} Observe que os elementos em ∆ são os únicos pares da forma (x, x), com x ∈ A, que não estão em R Note que R∗ é reflexiva e contém R Além disso, qualquer relação reflexiva em A deve conter os novos pares ordenados que incluímos: (2, 2) e (3, 3) de forma que não pode haver relação reflexiva menor do que esta Ou seja, qualquer relação reflexiva contendo R deve conter a relação R∗ Fechos de Relações Fechos de uma Relação Exemplo. Seja A = {1, 2, 3} e seja R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)} Note que R não é reflexiva O fecho de R com respeito à reflexividade é: R∗ = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (2, 2), (3, 3)} Ou R∗ = R ∪ ∆, em que ∆ = {(2, 2), (3, 3)} Observe que os elementos em ∆ são os únicos pares da forma (x, x), com x ∈ A, que não estão em R Note que R∗ é reflexiva e contém R Além disso, qualquer relação reflexiva em A deve conter os novos pares ordenados que incluímos: (2, 2) e (3, 3) de forma que não pode haver relação reflexiva menor do que esta Ou seja, qualquer relação reflexiva contendo R deve conter a relação R∗ Fechos de Relações Fechos de uma Relação Exemplo. Seja A = {1, 2, 3} e seja R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)} Note que R não é reflexiva O fecho de R com respeito à reflexividade é: R∗ = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (2, 2), (3, 3)} Ou R∗ = R ∪ ∆, em que ∆ = {(2, 2), (3, 3)} Observe que os elementos em ∆ são os únicos pares da forma (x, x), com x ∈ A, que não estão em R Note que R∗ é reflexiva e contém R Além disso, qualquer relação reflexiva em A deve conter os novos pares ordenados que incluímos: (2, 2) e (3, 3) de forma que não pode haver relação reflexiva menor do que esta Ou seja, qualquer relação reflexiva contendo R deve conter a relação R∗ Fechos de Relações Fechos de uma Relação Exemplo. Seja A = {1, 2, 3} e seja R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)} Note que R não é reflexiva O fecho de R com respeito à reflexividade é: R∗ = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (2, 2), (3, 3)} Ou R∗ = R ∪ ∆, em que ∆ = {(2, 2), (3, 3)} Observe que os elementos em ∆ são os únicos pares da forma (x, x), com x ∈ A, que não estão em R Note que R∗ é reflexiva e contém R Além disso, qualquer relação reflexiva em A deve conter os novos pares ordenados que incluímos: (2, 2) e (3, 3) de forma que não pode haver relação reflexiva menor do que esta Ou seja, qualquer relação reflexiva contendo R deve conter a relação R∗ Fechos de Relações Fechos de uma Relação Exemplo. Seja A = {1, 2, 3} e seja R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)} Note que R não é reflexiva O fecho de R com respeito à reflexividade é: R∗ = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (2, 2), (3, 3)} Ou R∗ = R ∪ ∆, em que ∆ = {(2, 2), (3, 3)} Observe que os elementos em ∆ são os únicos pares da forma (x, x), com x ∈ A, que não estão em R Note que R∗ é reflexiva e contém R Além disso, qualquer relação reflexiva em A deve conter os novos pares ordenados que incluímos: (2, 2) e (3, 3) de forma que não pode haver relação reflexiva menor do que esta Ou seja, qualquer relação reflexiva contendo R deve conter a relação R∗ Fechos de Relações Fechos de uma Relação Exemplo. Seja A = {1, 2, 3} e seja R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)} Note que R não é reflexiva O fecho de R com respeito à reflexividade é: R∗ = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (2, 2), (3, 3)} Ou R∗ = R ∪ ∆, em que ∆ = {(2, 2), (3, 3)} Observe que os elementos em ∆ são os únicos pares da forma (x, x), com x ∈ A, que não estão em R Note que R∗ é reflexiva e contém R Além disso, qualquer relação reflexiva em A deve conter os novos pares ordenados que incluímos: (2, 2) e (3, 3) de forma que não pode haver relação reflexiva menor do que esta Ou seja, qualquer relação reflexiva contendo R deve conter a relação R∗ Fechos de Relações Fechos de uma Relação Exemplo. Seja A = {1, 2, 3} e seja R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)} Note que R não é simétrica O fecho de R com respeito à simetria é: R∗ = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (2, 1), (3, 2)} Note que R∗ é simétrica e contém R Além disso, qualquer relação simétrica em A deve conter os novos pares ordenados que incluímos: (2, 1) e (3, 2) de forma que não pode haver relação simétrica menor do que esta Ou seja, qualquer relação simétrica contendo R deve conter a relação R∗ Para os fechos reflexivo e simétrico, temos apenas que verificar os pares já em R a fim de encontrar quais pares precisamos incluir Fechos de Relações Fechos de uma Relação Exemplo. Seja A = {1, 2, 3} e seja R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)} Note que R não é simétrica O fecho de R com respeito à simetria é: R∗ = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (2, 1), (3, 2)} Note que R∗ é simétrica e contém R Além disso, qualquer relação simétrica em A deve conter os novos pares ordenados que incluímos: (2, 1) e (3, 2) de forma que não pode haver relação simétrica menor do que esta Ou seja, qualquer relação simétrica contendo R deve conter a relação R∗ Para os fechos reflexivo e simétrico, temos apenas que verificar os pares já em R a fim de encontrar quais pares precisamos incluir Fechos de Relações Fechos de uma Relação Exemplo. Seja A = {1, 2, 3} e seja R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)} Note que R não é simétrica O fecho de R com respeito à simetria é: R∗ = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (2, 1), (3, 2)} Note que R∗ é simétrica e contém R Além disso, qualquer relação simétrica em A deve conter os novos pares ordenados que incluímos: (2, 1) e (3, 2) de forma que não pode haver relação simétrica menor do que esta Ou seja, qualquer relação simétrica contendo R deve conter a relação R∗ Para os fechos reflexivo e simétrico, temos apenas que verificar os pares já em R a fim de encontrar quais pares precisamos incluir Fechos de Relações Fechos de uma Relação Exemplo. Seja A = {1, 2, 3} e seja R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)} Note que R não é simétrica O fecho de R com respeito à simetria é: R∗ = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (2, 1), (3, 2)} Note que R∗ é simétrica e contém R Além disso, qualquer relação simétrica em A deve conter os novos pares ordenados que incluímos: (2, 1) e (3, 2) de forma que não pode haver relação simétrica menor do que esta Ou seja, qualquer relação simétrica contendo R deve conter a relação R∗ Para os fechos reflexivo e simétrico, temos apenas que verificar os pares já em R a fim de encontrar quais pares precisamos incluir Fechos de Relações Fechos de uma Relação Exemplo. Seja A = {1, 2, 3} e seja R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)} Note que R não é simétrica O fecho de R com respeito à simetria é: R∗ = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (2, 1), (3, 2)} Note que R∗ é simétrica e contém R Além disso, qualquer relação simétrica em A deve conter os novos pares ordenados que incluímos: (2, 1) e (3, 2) de forma que não pode haver relação simétrica menor do que esta Ou seja, qualquer relação simétrica contendo R deve conter a relação R∗ Para os fechos reflexivo e simétrico, temos apenas que verificar os pares já em R a fim de encontrar quais pares precisamos incluir Fechos de Relações Fechos de uma Relação Exemplo. Seja A = {1, 2, 3} e seja R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)} Note que R não é simétrica O fecho de R com respeito à simetria é: R∗ = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (2, 1), (3, 2)} Note que R∗ é simétrica e contém R Além disso, qualquer relação simétrica em A deve conter os novos pares ordenados que incluímos: (2, 1) e (3, 2) de forma que não pode haver relação simétrica menor do que esta Ou seja, qualquer relação simétrica contendo R deve conter a relação R∗ Para os fechos reflexivo e simétrico, temos apenas que verificar os pares já em R a fim de encontrar quais pares precisamos incluir Fechos de Relações Fechos de uma Relação Exemplo. Seja A = {1, 2, 3} e seja R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)} Note que R não é simétrica O fecho de R com respeito à simetria é: R∗ = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (2, 1), (3, 2)} Note que R∗ é simétrica e contém R Além disso, qualquer relação simétrica em A deve conter os novos pares ordenados que incluímos: (2, 1) e (3, 2) de forma que não pode haver relação simétrica menor do que esta Ou seja, qualquer relação simétrica contendo R deve conter a relação R∗ Para os fechos reflexivo e simétrico, temos apenas que verificar os pares já em R a fim de encontrar quais pares precisamos incluir Fechos de Relações Fechos de uma Relação Exemplo. Seja A = {1, 2, 3} e seja R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)} Note que R não é simétrica O fecho de R com respeito à simetria é: R∗ = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (2, 1), (3, 2)} Note que R∗ é simétrica e contém R Além disso, qualquer relação simétrica em A deve conter os novos pares ordenados que incluímos: (2, 1) e (3, 2) de forma que não pode haver relação simétrica menor do que esta Ou seja, qualquer relação simétrica contendo R deve conter a relação R∗ Para os fechos reflexivo e simétrico, temos apenas que verificar os pares já em R a fim de encontrar quais pares precisamos incluir Fechos de Relações Fechos de uma Relação Exemplo. Seja A = {1, 2, 3} e seja R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)} Note que R não é transitiva O fecho transitivo demanda uma série de passos para ser encontrado Verificando os pares ordenados de R, vemos que precisamos incluir (3, 2) (devido aos pares (3, 1) e (1, 2)) Precisamos incluir (3, 3) (devido aos pares (3, 1) e (1, 3)) Precisamos incluir (2, 1) (devido aos pares (2, 3) e (3, 1)) Isto nos dá a relação: {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (3, 2), (3, 3), (2, 1)} No entanto, esta relação ainda não é transitiva Fechos de Relações Fechos de uma Relação Exemplo. Seja A = {1, 2, 3} e seja R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)} Note que R não é transitiva O fecho transitivo demanda uma série de passos para ser encontrado Verificando os pares ordenados de R, vemos que precisamos incluir (3, 2) (devido aos pares (3, 1) e (1, 2)) Precisamos incluir (3, 3) (devido aos pares (3, 1) e (1, 3)) Precisamos incluir (2, 1) (devido aos pares (2, 3) e (3, 1)) Isto nos dá a relação: {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (3, 2), (3, 3), (2, 1)} No entanto, esta relação ainda não é transitiva Fechos de Relações Fechos de uma Relação Exemplo. Seja A = {1, 2, 3} e seja R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)} Note que R não é transitiva O fecho transitivo demanda uma série de passos para ser encontrado Verificando os pares ordenados de R, vemos que precisamos incluir (3, 2) (devido aos pares (3, 1) e (1, 2)) Precisamos incluir (3, 3) (devido aos pares (3, 1) e (1, 3)) Precisamos incluir (2, 1) (devido aos pares (2, 3) e (3, 1)) Isto nos dá a relação: {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (3, 2), (3, 3), (2, 1)} No entanto, esta relação ainda não é transitiva Fechos de Relações Fechos de uma Relação Exemplo. Seja A = {1, 2, 3} e seja R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)} Note que R não é transitiva O fecho transitivo demanda uma série de passos para ser encontrado Verificando os pares ordenados de R, vemos que precisamos incluir (3, 2) (devido aos pares (3, 1) e (1, 2)) Precisamos incluir (3, 3) (devido aos pares (3, 1) e (1, 3)) Precisamos incluir (2, 1) (devido aos pares (2, 3) e (3, 1)) Isto nos dá a relação: {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (3, 2), (3, 3), (2, 1)} No entanto, esta relação ainda não é transitiva Fechos de Relações Fechos de uma Relação Exemplo. Seja A = {1, 2, 3} e seja R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)} Note que R não é transitiva O fecho transitivo demanda uma série de passos para ser encontrado Verificando os pares ordenados de R, vemos que precisamos incluir (3, 2) (devido aos pares (3, 1) e (1, 2)) Precisamos incluir (3, 3) (devido aos pares (3, 1) e (1, 3)) Precisamos incluir (2, 1) (devido aos pares (2, 3) e (3, 1)) Isto nos dá a relação: {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (3, 2), (3, 3), (2, 1)} No entanto, esta relação ainda não é transitiva Fechos de Relações Fechos de uma Relação Exemplo. Seja A = {1, 2, 3} e seja R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)} Note que R não é transitiva O fecho transitivo demanda uma série de passos para ser encontrado Verificando os pares ordenados de R, vemos que precisamos incluir (3, 2) (devido aos pares (3, 1) e (1, 2)) Precisamos incluir (3, 3) (devido aos pares (3, 1) e (1, 3)) Precisamos incluir (2, 1) (devido aos pares (2, 3) e (3, 1)) Isto nos dá a relação: {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (3, 2), (3, 3), (2, 1)} No entanto, esta relação ainda não é transitiva Fechos de Relações Fechos de uma Relação Exemplo. Seja A = {1, 2, 3} e seja R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)} Note que R não é transitiva O fecho transitivo demanda uma série de passos para ser encontrado Verificando os pares ordenados de R, vemos que precisamos incluir (3, 2) (devido aos pares (3, 1) e (1, 2)) Precisamos incluir (3, 3) (devido aos pares (3, 1) e (1, 3)) Precisamos incluir (2, 1) (devido aos pares (2, 3) e (3, 1)) Isto nos dá a relação: {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (3, 2), (3, 3), (2, 1)} No entanto, esta relação ainda não é transitiva Fechos de Relações Fechos de uma Relação Exemplo. Seja A = {1, 2, 3} e seja R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)} Note que R não é transitiva O fecho transitivo demanda uma série de passos para ser encontrado Verificando os pares ordenados de R, vemos que precisamos incluir (3, 2) (devido aos pares (3, 1) e (1, 2)) Precisamos incluir (3, 3) (devido aos pares (3, 1) e (1, 3)) Precisamos incluir (2, 1) (devido aos pares (2, 3) e (3, 1)) Isto nos dá a relação: {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (3, 2), (3, 3), (2, 1)} No entanto, esta relação ainda não é transitiva Fechos de Relações Fechos de uma Relação Isto nos dá a relação: {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (3, 2), (3, 3), (2, 1)} No entanto, esta relação ainda não é transitiva Pois, devido ao novo par (2, 1) e ao par original (1, 2), devemos incluir o par (2, 2) Isto nos dá a relação: {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (3, 2), (3, 3), (2, 1), (2, 2)} que é transitiva e é também a menor relação transitiva que contém R Uma maneira de determinar o fecho transitivo de uma relação é verificar os pares ordenados na relação original, incluir novos pares se necessário, verificar a relação obtida, incluindo novos pares se necessário e assim por diante, até que tenhamos obtido uma relação transitiva Fechos de Relações Fechos de uma Relação Isto nos dá a relação: {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (3, 2), (3, 3), (2, 1)} No entanto, esta relação ainda não é transitiva Pois, devido ao novo par (2, 1) e ao par original (1, 2), devemos incluir o par (2, 2) Isto nos dá a relação: {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (3, 2), (3, 3), (2, 1), (2, 2)} que é transitiva e é também a menor relação transitiva que contém R Uma maneira de determinar o fecho transitivo de uma relação é verificar os pares ordenados na relação original, incluir novos pares se necessário, verificar a relação obtida, incluindo novos pares se necessário e assim por diante, até que tenhamos obtido uma relação transitiva Fechos de Relações Fechos de uma Relação Isto nos dá a relação: {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (3, 2), (3, 3), (2, 1)} No entanto, esta relação ainda não é transitiva Pois, devido ao novo par (2, 1) e ao par original (1, 2), devemos incluir o par (2, 2) Isto nos dá a relação: {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (3, 2), (3, 3), (2, 1), (2, 2)} que é transitiva e é também a menor relação transitiva que contém R Uma maneira de determinar o fecho transitivo de uma relação é verificar os pares ordenados na relação original, incluir novos pares se necessário, verificar a relação obtida, incluindo novos pares se necessário e assim por diante, até que tenhamos obtido uma relação transitiva Fechos de Relações Fechos de uma Relação Isto nos dá a relação: {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (3, 2), (3, 3), (2, 1)} No entanto, esta relação ainda não é transitiva Pois, devido ao novo par (2, 1) e ao par original (1, 2), devemos incluir o par (2, 2) Isto nos dá a relação: {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (3, 2), (3, 3), (2, 1), (2, 2)} que é transitiva e é também a menor relação transitiva que contém R Uma maneira de determinar o fecho transitivo de uma relação é verificar os pares ordenados na relação original, incluir novos pares se necessário, verificar a relação obtida, incluindo novos pares se necessário e assim por diante, até que tenhamos obtido uma relação transitiva Fechos de Relações Fechos de uma Relação Isto nos dá a relação: {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (3, 2), (3, 3), (2, 1)} No entanto, esta relação ainda não é transitiva Pois, devido ao novo par (2, 1) e ao par original (1, 2), devemos incluir o par (2, 2) Isto nos dá a relação: {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3), (3, 2), (3, 3), (2, 1), (2, 2)} que é transitiva e é também a menor relação transitiva que contém R Uma maneira de determinar o fecho transitivo de uma relação é verificar os pares ordenados na relação original, incluir novos pares se necessário, verificar a relação obtida, incluindo novos pares se necessário e assim por diante, até que tenhamos obtido uma relação transitiva Fechos de Relações Fechos de uma Relação Seja A = {0, 1, 2, 3} e considere a relação R = {(0, 1), (1, 2), (2, 3)} definida em A. Determine o fecho transitivo de R Hipótese Conclusão (0, 1) e (1, 2) (0, 2)∗ (1, 2) e (2, 3) (1, 3)∗ (0, 2) e (2, 3) (0, 3)∗ ∗ Não faz parte da relação original R∗ = {(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)} Fechos de Relações Fechos de uma Relação Seja A = {0, 1, 2, 3} e considere a relação R = {(0, 1), (1, 2), (2, 3)} definida em A. Determine o fecho transitivo de R Hipótese Conclusão (0, 1) e (1, 2) (0, 2)∗ (1, 2) e (2, 3) (1, 3)∗ (0, 2) e (2, 3) (0, 3)∗ ∗ Não faz parte da relação original R∗ = {(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)} Fechos de Relações Fechos de uma Relação Seja A = {0, 1, 2, 3} e considere a relação R = {(0, 1), (1, 2), (2, 3)} definida em A. Determine o fecho transitivo de R Hipótese Conclusão (0, 1) e (1, 2) (0, 2)∗ (1, 2) e (2, 3) (1, 3)∗ (0, 2) e (2, 3) (0, 3)∗ ∗ Não faz parte da relação original R∗ = {(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)} Fechos de Relações Fechos Transitivo de uma Relação Teorema. O fecho transitivo de uma relação R é igual a R^*, em que R^* = \bigcup_{n=1}^{\infty} R^n Fechos de Relações Fechos Transitivo de uma Relação Teorema. O fecho transitivo de uma relação R é igual a R^*, em que R^* = \bigcup_{n=1}^{\infty} R^n Seja A um conjunto com |A| = n e seja R uma relação sobre A, então Fechos de Relações Fechos Transitivo de uma Relação Teorema. O fecho transitivo de uma relação R é igual a R*, em que R* = \bigcup_{n=1}^{\infty} R^n Seja A um conjunto com |A| = n e seja R uma relação sobre A, então R* = R \cup R^2 \cup R^3 \cup \ldots \cup R^n Fechos de Relações Fechos Transitivo de uma Relação Teorema. O fecho transitivo de uma relação R é igual a R*, em que R* = \bigcup_{n=1}^{\infty} R^n Seja A um conjunto com |A| = n e seja R uma relação sobre A, então R* = R \cup R^2 \cup R^3 \cup \ldots \cup R^n Potências de R maiores do que n não são necessárias para computar R* Fechos de Relações Fechos Transitivo de uma Relação Teorema. O fecho transitivo de uma relação R é igual a R*, em que R* = \bigcup_{n=1}^{\infty} R^n Seja A um conjunto com |A| = n e seja R uma relação sobre A, então R* = R \cup R^2 \cup R^3 \cup \ldots \cup R^n Potências de R maiores do que n não são necessárias para computar R* Seja M_R a matriz zero-um da relação R sobre um conjunto com n elementos. Assim, a matriz do fecho transitivo de R* é Fechos de Relações Fechos Transitivo de uma Relação • Teorema. O fecho transitivo de uma relação R é igual a R*, em que R* = ⋃∞n=1 Rn • Seja A um conjunto com |A| = n e seja R uma relação sobre A, então R* = R ∪ R² ∪ R³ ∪ ⋯ ∪ Rn • Potências de R maiores do que n não são necessárias para computar R* • Seja MR a matriz zero-um da relação R sobre um conjunto com n elementos. Assim, a matriz do fecho transitivo de R* é M*R = MR ∨ M[2]R ∨ M[3]R ∨ ⋯ ∨ M[n]R Fechos de Relações Fechos Transitivo de uma Relação Exemplo. Seja A = {1, 2, 3, 4} e uma relação binária R definida como R = {(1, 2), (2, 1), (2, 3), (3, 4)}. Determine o fecho transitivo de R MR =   0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0   M2 R =   1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0   M3 R =   0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0   M4 R =   1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0   M∗ R = MR ∨ M2 R ∨ M3 R ∨ M4 R =   1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 0   Fechos de Relações Fechos Transitivo de uma Relação Exemplo. Seja A = {1, 2, 3, 4} e uma relação binária R definida como R = {(1, 2), (2, 1), (2, 3), (3, 4)}. Determine o fecho transitivo de R MR =   0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0   M2 R =   1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0   M3 R =   0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0   M4 R =   1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0   M∗ R = MR ∨ M2 R ∨ M3 R ∨ M4 R =   1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 0   Fechos de Relações Fechos Transitivo de uma Relação Exemplo. Seja A = {1, 2, 3, 4} e uma relação binária R definida como R = {(1, 2), (2, 1), (2, 3), (3, 4)}. Determine o fecho transitivo de R MR =   0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0   M2 R =   1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0   M3 R =   0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0   M4 R =   1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0   M∗ R = MR ∨ M2 R ∨ M3 R ∨ M4 R =   1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 0   Ordens Parciais Ordens Parciais Com frequência usamos relações para ordenar alguns ou todos os elementos Ordenamos palavras usando a relação que contém pares de palavras (x, y), em que x vem antes de y no dicionário Ordenamos o conjunto dos inteiros usando a relação que contém os pares (x, y) em que x menor que y Definição. Uma relação em um conjunto S é chamada de ordenação parcial ou de ordem parcial se for reflexiva, antissimétrica e transitiva. Um conjunto S junto com uma ordenação parcial R é denominado um conjunto parcialmente ordenado ou poset e é indicado por (S, R) Os membros de S são chamados de elementos do poset Seja R uma relação binária no conjunto S. Então R é dita antissimétrica se, e somente se, ∀x, ∀y ∈ S, se (a, b) ∈ R e (b, a) ∈ R, então a = b Ordens Parciais Ordens Parciais Com frequência usamos relações para ordenar alguns ou todos os elementos Ordenamos palavras usando a relação que contém pares de palavras (x, y), em que x vem antes de y no dicionário Ordenamos o conjunto dos inteiros usando a relação que contém os pares (x, y) em que x menor que y Definição. Uma relação em um conjunto S é chamada de ordenação parcial ou de ordem parcial se for reflexiva, antissimétrica e transitiva. Um conjunto S junto com uma ordenação parcial R é denominado um conjunto parcialmente ordenado ou poset e é indicado por (S, R) Os membros de S são chamados de elementos do poset Seja R uma relação binária no conjunto S. Então R é dita antissimétrica se, e somente se, ∀x, ∀y ∈ S, se (a, b) ∈ R e (b, a) ∈ R, então a = b Ordens Parciais Ordens Parciais Com frequência usamos relações para ordenar alguns ou todos os elementos Ordenamos palavras usando a relação que contém pares de palavras (x, y), em que x vem antes de y no dicionário Ordenamos o conjunto dos inteiros usando a relação que contém os pares (x, y) em que x menor que y Definição. Uma relação em um conjunto S é chamada de ordenação parcial ou de ordem parcial se for reflexiva, antissimétrica e transitiva. Um conjunto S junto com uma ordenação parcial R é denominado um conjunto parcialmente ordenado ou poset e é indicado por (S, R) Os membros de S são chamados de elementos do poset Seja R uma relação binária no conjunto S. Então R é dita antissimétrica se, e somente se, ∀x, ∀y ∈ S, se (a, b) ∈ R e (b, a) ∈ R, então a = b Ordens Parciais Ordens Parciais Com frequência usamos relações para ordenar alguns ou todos os elementos Ordenamos palavras usando a relação que contém pares de palavras (x, y), em que x vem antes de y no dicionário Ordenamos o conjunto dos inteiros usando a relação que contém os pares (x, y) em que x menor que y Definição. Uma relação em um conjunto S é chamada de ordenação parcial ou de ordem parcial se for reflexiva, antissimétrica e transitiva. Um conjunto S junto com uma ordenação parcial R é denominado um conjunto parcialmente ordenado ou poset e é indicado por (S, R) Os membros de S são chamados de elementos do poset Seja R uma relação binária no conjunto S. Então R é dita antissimétrica se, e somente se, ∀x, ∀y ∈ S, se (a, b) ∈ R e (b, a) ∈ R, então a = b Ordens Parciais Ordens Parciais Com frequência usamos relações para ordenar alguns ou todos os elementos Ordenamos palavras usando a relação que contém pares de palavras (x, y), em que x vem antes de y no dicionário Ordenamos o conjunto dos inteiros usando a relação que contém os pares (x, y) em que x menor que y Definição. Uma relação em um conjunto S é chamada de ordenação parcial ou de ordem parcial se for reflexiva, antissimétrica e transitiva. Um conjunto S junto com uma ordenação parcial R é denominado um conjunto parcialmente ordenado ou poset e é indicado por (S, R) Os membros de S são chamados de elementos do poset Seja R uma relação binária no conjunto S. Então R é dita antissimétrica se, e somente se, ∀x, ∀y ∈ S, se (a, b) ∈ R e (b, a) ∈ R, então a = b Ordens Parciais Ordens Parciais Com frequência usamos relações para ordenar alguns ou todos os elementos Ordenamos palavras usando a relação que contém pares de palavras (x, y), em que x vem antes de y no dicionário Ordenamos o conjunto dos inteiros usando a relação que contém os pares (x, y) em que x menor que y Definição. Uma relação em um conjunto S é chamada de ordenação parcial ou de ordem parcial se for reflexiva, antissimétrica e transitiva. Um conjunto S junto com uma ordenação parcial R é denominado um conjunto parcialmente ordenado ou poset e é indicado por (S, R) Os membros de S são chamados de elementos do poset Seja R uma relação binária no conjunto S. Então R é dita antissimétrica se, e somente se, ∀x, ∀y ∈ S, se (a, b) ∈ R e (b, a) ∈ R, então a = b Ordens Parciais Ordens Parciais Exemplo. Mostre que a relação “maior que ou igual a”(≥) é uma ordem parcial no conjunto dos inteiros Como a ≥ a, ∀a ∈ Z, ≥ é reflexiva Se a ≥ b e b ≥ a, então a = b. Logo, ≥ é antissimétrica Se a ≥ b e b ≥ c, então a ≥ c. Logo, ≥ é transitiva Portanto, ≥ é uma ordem parcial no conjunto dos inteiros Exemplo. A relação “divide”(|) é uma ordem parcial no conjunto dos inteiros positivos Vimos que esta relação é reflexiva, antissimétrica e transitiva Logo, (Z∗ +, |) é um poset Ordens Parciais Ordens Parciais Exemplo. Mostre que a relação “maior que ou igual a”(≥) é uma ordem parcial no conjunto dos inteiros Como a ≥ a, ∀a ∈ Z, ≥ é reflexiva Se a ≥ b e b ≥ a, então a = b. Logo, ≥ é antissimétrica Se a ≥ b e b ≥ c, então a ≥ c. Logo, ≥ é transitiva Portanto, ≥ é uma ordem parcial no conjunto dos inteiros Exemplo. A relação “divide”(|) é uma ordem parcial no conjunto dos inteiros positivos Vimos que esta relação é reflexiva, antissimétrica e transitiva Logo, (Z∗ +, |) é um poset Ordens Parciais Ordens Parciais Exemplo. Mostre que a relação “maior que ou igual a”(≥) é uma ordem parcial no conjunto dos inteiros Como a ≥ a, ∀a ∈ Z, ≥ é reflexiva Se a ≥ b e b ≥ a, então a = b. Logo, ≥ é antissimétrica Se a ≥ b e b ≥ c, então a ≥ c. Logo, ≥ é transitiva Portanto, ≥ é uma ordem parcial no conjunto dos inteiros Exemplo. A relação “divide”(|) é uma ordem parcial no conjunto dos inteiros positivos Vimos que esta relação é reflexiva, antissimétrica e transitiva Logo, (Z∗ +, |) é um poset Ordens Parciais Ordens Parciais Exemplo. Mostre que a relação “maior que ou igual a”(≥) é uma ordem parcial no conjunto dos inteiros Como a ≥ a, ∀a ∈ Z, ≥ é reflexiva Se a ≥ b e b ≥ a, então a = b. Logo, ≥ é antissimétrica Se a ≥ b e b ≥ c, então a ≥ c. Logo, ≥ é transitiva Portanto, ≥ é uma ordem parcial no conjunto dos inteiros Exemplo. A relação “divide”(|) é uma ordem parcial no conjunto dos inteiros positivos Vimos que esta relação é reflexiva, antissimétrica e transitiva Logo, (Z∗ +, |) é um poset Ordens Parciais Ordens Parciais Exemplo. Mostre que a relação “maior que ou igual a”(≥) é uma ordem parcial no conjunto dos inteiros Como a ≥ a, ∀a ∈ Z, ≥ é reflexiva Se a ≥ b e b ≥ a, então a = b. Logo, ≥ é antissimétrica Se a ≥ b e b ≥ c, então a ≥ c. Logo, ≥ é transitiva Portanto, ≥ é uma ordem parcial no conjunto dos inteiros Exemplo. A relação “divide”(|) é uma ordem parcial no conjunto dos inteiros positivos Vimos que esta relação é reflexiva, antissimétrica e transitiva Logo, (Z∗ +, |) é um poset Ordens Parciais Ordens Parciais Exemplo. Mostre que a relação “maior que ou igual a”(≥) é uma ordem parcial no conjunto dos inteiros Como a ≥ a, ∀a ∈ Z, ≥ é reflexiva Se a ≥ b e b ≥ a, então a = b. Logo, ≥ é antissimétrica Se a ≥ b e b ≥ c, então a ≥ c. Logo, ≥ é transitiva Portanto, ≥ é uma ordem parcial no conjunto dos inteiros Exemplo. A relação “divide”(|) é uma ordem parcial no conjunto dos inteiros positivos Vimos que esta relação é reflexiva, antissimétrica e transitiva Logo, (Z∗ +, |) é um poset Ordens Parciais Ordens Parciais Exemplo. Mostre que a relação “maior que ou igual a”(≥) é uma ordem parcial no conjunto dos inteiros Como a ≥ a, ∀a ∈ Z, ≥ é reflexiva Se a ≥ b e b ≥ a, então a = b. Logo, ≥ é antissimétrica Se a ≥ b e b ≥ c, então a ≥ c. Logo, ≥ é transitiva Portanto, ≥ é uma ordem parcial no conjunto dos inteiros Exemplo. A relação “divide”(|) é uma ordem parcial no conjunto dos inteiros positivos Vimos que esta relação é reflexiva, antissimétrica e transitiva Logo, (Z∗ +, |) é um poset Ordens Parciais Ordens Parciais Exemplo. Mostre que a relação “maior que ou igual a”(≥) é uma ordem parcial no conjunto dos inteiros Como a ≥ a, ∀a ∈ Z, ≥ é reflexiva Se a ≥ b e b ≥ a, então a = b. Logo, ≥ é antissimétrica Se a ≥ b e b ≥ c, então a ≥ c. Logo, ≥ é transitiva Portanto, ≥ é uma ordem parcial no conjunto dos inteiros Exemplo. A relação “divide”(|) é uma ordem parcial no conjunto dos inteiros positivos Vimos que esta relação é reflexiva, antissimétrica e transitiva Logo, (Z∗ +, |) é um poset Ordens Parciais Ordens Parciais Exemplo. Mostre que a relação “maior que ou igual a”(≥) é uma ordem parcial no conjunto dos inteiros Como a ≥ a, ∀a ∈ Z, ≥ é reflexiva Se a ≥ b e b ≥ a, então a = b. Logo, ≥ é antissimétrica Se a ≥ b e b ≥ c, então a ≥ c. Logo, ≥ é transitiva Portanto, ≥ é uma ordem parcial no conjunto dos inteiros Exemplo. A relação “divide”(|) é uma ordem parcial no conjunto dos inteiros positivos Vimos que esta relação é reflexiva, antissimétrica e transitiva Logo, (Z∗ +, |) é um poset Ordens Parciais Ordens Parciais Exemplo. Mostre que a relação “maior que ou igual a”(≥) é uma ordem parcial no conjunto dos inteiros Como a ≥ a, ∀a ∈ Z, ≥ é reflexiva Se a ≥ b e b ≥ a, então a = b. Logo, ≥ é antissimétrica Se a ≥ b e b ≥ c, então a ≥ c. Logo, ≥ é transitiva Portanto, ≥ é uma ordem parcial no conjunto dos inteiros Exemplo. A relação “divide”(|) é uma ordem parcial no conjunto dos inteiros positivos Vimos que esta relação é reflexiva, antissimétrica e transitiva Logo, (Z∗ +, |) é um poset Ordens Parciais Ordens Parciais Exemplo. Mostre que a relação de inclusão (⊆) é uma ordem parcial no conjunto das partes de um conjunto S Como A ⊆ A sempre que A é um subconjunto de S, ⊆ reflexiva Se A ⊆ B e B ⊆ A, então A = B. Logo, ⊆ é antissimétrica Se A ⊆ B e B ⊆ C, então A ⊆ C. Logo, ⊆ é transitiva Portanto, ⊆ é uma ordem parcial no conjunto das partes de S Em poset diferentes são usados símbolos diferentes, tais como ≤, ⊆, |, para ordem parcial Entretanto precisamos de um símbolo que possa ser usado quando discutirmos a relação de ordem em um poset arbitrário Em geral, a indicação a ≼ b é usada para denotar que (a, b) ∈ R em um poset arbitrário (S, R) A notação a ≺ b significa que a ≼ b, mas a ̸= b Dizemos que “a é menor que b” ou “b é maior que a” se a ≺ b Ordens Parciais Ordens Parciais Exemplo. Mostre que a relação de inclusão (⊆) é uma ordem parcial no conjunto das partes de um conjunto S Como A ⊆ A sempre que A é um subconjunto de S, ⊆ reflexiva Se A ⊆ B e B ⊆ A, então A = B. Logo, ⊆ é antissimétrica Se A ⊆ B e B ⊆ C, então A ⊆ C. Logo, ⊆ é transitiva Portanto, ⊆ é uma ordem parcial no conjunto das partes de S Em poset diferentes são usados símbolos diferentes, tais como ≤, ⊆, |, para ordem parcial Entretanto precisamos de um símbolo que possa ser usado quando discutirmos a relação de ordem em um poset arbitrário Em geral, a indicação a ≼ b é usada para denotar que (a, b) ∈ R em um poset arbitrário (S, R) A notação a ≺ b significa que a ≼ b, mas a ̸= b Dizemos que “a é menor que b” ou “b é maior que a” se a ≺ b Ordens Parciais Ordens Parciais Exemplo. Mostre que a relação de inclusão (⊆) é uma ordem parcial no conjunto das partes de um conjunto S Como A ⊆ A sempre que A é um subconjunto de S, ⊆ reflexiva Se A ⊆ B e B ⊆ A, então A = B. Logo, ⊆ é antissimétrica Se A ⊆ B e B ⊆ C, então A ⊆ C. Logo, ⊆ é transitiva Portanto, ⊆ é uma ordem parcial no conjunto das partes de S Em poset diferentes são usados símbolos diferentes, tais como ≤, ⊆, |, para ordem parcial Entretanto precisamos de um símbolo que possa ser usado quando discutirmos a relação de ordem em um poset arbitrário Em geral, a indicação a ≼ b é usada para denotar que (a, b) ∈ R em um poset arbitrário (S, R) A notação a ≺ b significa que a ≼ b, mas a ̸= b Dizemos que “a é menor que b” ou “b é maior que a” se a ≺ b Ordens Parciais Ordens Parciais Exemplo. Mostre que a relação de inclusão (⊆) é uma ordem parcial no conjunto das partes de um conjunto S Como A ⊆ A sempre que A é um subconjunto de S, ⊆ reflexiva Se A ⊆ B e B ⊆ A, então A = B. Logo, ⊆ é antissimétrica Se A ⊆ B e B ⊆ C, então A ⊆ C. Logo, ⊆ é transitiva Portanto, ⊆ é uma ordem parcial no conjunto das partes de S Em poset diferentes são usados símbolos diferentes, tais como ≤, ⊆, |, para ordem parcial Entretanto precisamos de um símbolo que possa ser usado quando discutirmos a relação de ordem em um poset arbitrário Em geral, a indicação a ≼ b é usada para denotar que (a, b) ∈ R em um poset arbitrário (S, R) A notação a ≺ b significa que a ≼ b, mas a ̸= b Dizemos que “a é menor que b” ou “b é maior que a” se a ≺ b Ordens Parciais Ordens Parciais Exemplo. Mostre que a relação de inclusão (⊆) é uma ordem parcial no conjunto das partes de um conjunto S Como A ⊆ A sempre que A é um subconjunto de S, ⊆ reflexiva Se A ⊆ B e B ⊆ A, então A = B. Logo, ⊆ é antissimétrica Se A ⊆ B e B ⊆ C, então A ⊆ C. Logo, ⊆ é transitiva Portanto, ⊆ é uma ordem parcial no conjunto das partes de S Em poset diferentes são usados símbolos diferentes, tais como ≤, ⊆, |, para ordem parcial Entretanto precisamos de um símbolo que possa ser usado quando discutirmos a relação de ordem em um poset arbitrário Em geral, a indicação a ≼ b é usada para denotar que (a, b) ∈ R em um poset arbitrário (S, R) A notação a ≺ b significa que a ≼ b, mas a ̸= b Dizemos que “a é menor que b” ou “b é maior que a” se a ≺ b Ordens Parciais Ordens Parciais Exemplo. Mostre que a relação de inclusão (⊆) é uma ordem parcial no conjunto das partes de um conjunto S Como A ⊆ A sempre que A é um subconjunto de S, ⊆ reflexiva Se A ⊆ B e B ⊆ A, então A = B. Logo, ⊆ é antissimétrica Se A ⊆ B e B ⊆ C, então A ⊆ C. Logo, ⊆ é transitiva Portanto, ⊆ é uma ordem parcial no conjunto das partes de S Em poset diferentes são usados símbolos diferentes, tais como ≤, ⊆, |, para ordem parcial Entretanto precisamos de um símbolo que possa ser usado quando discutirmos a relação de ordem em um poset arbitrário Em geral, a indicação a ≼ b é usada para denotar que (a, b) ∈ R em um poset arbitrário (S, R) A notação a ≺ b significa que a ≼ b, mas a ̸= b Dizemos que “a é menor que b” ou “b é maior que a” se a ≺ b Ordens Parciais Ordens Parciais Exemplo. Mostre que a relação de inclusão (⊆) é uma ordem parcial no conjunto das partes de um conjunto S Como A ⊆ A sempre que A é um subconjunto de S, ⊆ reflexiva Se A ⊆ B e B ⊆ A, então A = B. Logo, ⊆ é antissimétrica Se A ⊆ B e B ⊆ C, então A ⊆ C. Logo, ⊆ é transitiva Portanto, ⊆ é uma ordem parcial no conjunto das partes de S Em poset diferentes são usados símbolos diferentes, tais como ≤, ⊆, |, para ordem parcial Entretanto precisamos de um símbolo que possa ser usado quando discutirmos a relação de ordem em um poset arbitrário Em geral, a indicação a ≼ b é usada para denotar que (a, b) ∈ R em um poset arbitrário (S, R) A notação a ≺ b significa que a ≼ b, mas a ̸= b Dizemos que “a é menor que b” ou “b é maior que a” se a ≺ b Ordens Parciais Ordens Parciais Exemplo. Mostre que a relação de inclusão (⊆) é uma ordem parcial no conjunto das partes de um conjunto S Como A ⊆ A sempre que A é um subconjunto de S, ⊆ reflexiva Se A ⊆ B e B ⊆ A, então A = B. Logo, ⊆ é antissimétrica Se A ⊆ B e B ⊆ C, então A ⊆ C. Logo, ⊆ é transitiva Portanto, ⊆ é uma ordem parcial no conjunto das partes de S Em poset diferentes são usados símbolos diferentes, tais como ≤, ⊆, |, para ordem parcial Entretanto precisamos de um símbolo que possa ser usado quando discutirmos a relação de ordem em um poset arbitrário Em geral, a indicação a ≼ b é usada para denotar que (a, b) ∈ R em um poset arbitrário (S, R) A notação a ≺ b significa que a ≼ b, mas a ̸= b Dizemos que “a é menor que b” ou “b é maior que a” se a ≺ b Ordens Parciais Ordens Parciais Exemplo. Mostre que a relação de inclusão (⊆) é uma ordem parcial no conjunto das partes de um conjunto S Como A ⊆ A sempre que A é um subconjunto de S, ⊆ reflexiva Se A ⊆ B e B ⊆ A, então A = B. Logo, ⊆ é antissimétrica Se A ⊆ B e B ⊆ C, então A ⊆ C. Logo, ⊆ é transitiva Portanto, ⊆ é uma ordem parcial no conjunto das partes de S Em poset diferentes são usados símbolos diferentes, tais como ≤, ⊆, |, para ordem parcial Entretanto precisamos de um símbolo que possa ser usado quando discutirmos a relação de ordem em um poset arbitrário Em geral, a indicação a ≼ b é usada para denotar que (a, b) ∈ R em um poset arbitrário (S, R) A notação a ≺ b significa que a ≼ b, mas a ̸= b Dizemos que “a é menor que b” ou “b é maior que a” se a ≺ b Ordens Parciais Ordens Parciais Exemplo. Mostre que a relação de inclusão (⊆) é uma ordem parcial no conjunto das partes de um conjunto S Como A ⊆ A sempre que A é um subconjunto de S, ⊆ reflexiva Se A ⊆ B e B ⊆ A, então A = B. Logo, ⊆ é antissimétrica Se A ⊆ B e B ⊆ C, então A ⊆ C. Logo, ⊆ é transitiva Portanto, ⊆ é uma ordem parcial no conjunto das partes de S Em poset diferentes são usados símbolos diferentes, tais como ≤, ⊆, |, para ordem parcial Entretanto precisamos de um símbolo que possa ser usado quando discutirmos a relação de ordem em um poset arbitrário Em geral, a indicação a ≼ b é usada para denotar que (a, b) ∈ R em um poset arbitrário (S, R) A notação a ≺ b significa que a ≼ b, mas a ̸= b Dizemos que “a é menor que b” ou “b é maior que a” se a ≺ b Ordens Parciais Ordens Parciais Exemplo. Mostre que a relação de inclusão (⊆) é uma ordem parcial no conjunto das partes de um conjunto S Como A ⊆ A sempre que A é um subconjunto de S, ⊆ reflexiva Se A ⊆ B e B ⊆ A, então A = B. Logo, ⊆ é antissimétrica Se A ⊆ B e B ⊆ C, então A ⊆ C. Logo, ⊆ é transitiva Portanto, ⊆ é uma ordem parcial no conjunto das partes de S Em poset diferentes são usados símbolos diferentes, tais como ≤, ⊆, |, para ordem parcial Entretanto precisamos de um símbolo que possa ser usado quando discutirmos a relação de ordem em um poset arbitrário Em geral, a indicação a ≼ b é usada para denotar que (a, b) ∈ R em um poset arbitrário (S, R) A notação a ≺ b significa que a ≼ b, mas a ̸= b Dizemos que “a é menor que b” ou “b é maior que a” se a ≺ b Ordens Parciais Ordens Parciais Exemplo. Mostre que a relação de inclusão (⊆) é uma ordem parcial no conjunto das partes de um conjunto S Como A ⊆ A sempre que A é um subconjunto de S, ⊆ reflexiva Se A ⊆ B e B ⊆ A, então A = B. Logo, ⊆ é antissimétrica Se A ⊆ B e B ⊆ C, então A ⊆ C. Logo, ⊆ é transitiva Portanto, ⊆ é uma ordem parcial no conjunto das partes de S Em poset diferentes são usados símbolos diferentes, tais como ≤, ⊆, |, para ordem parcial Entretanto precisamos de um símbolo que possa ser usado quando discutirmos a relação de ordem em um poset arbitrário Em geral, a indicação a ≼ b é usada para denotar que (a, b) ∈ R em um poset arbitrário (S, R) A notação a ≺ b significa que a ≼ b, mas a ̸= b Dizemos que “a é menor que b” ou “b é maior que a” se a ≺ b Ordens Parciais Ordens Total Definição. Se (S, ≼) é um poset e quaisquer dois elementos de S são comparáveis, S é chamado de conjunto totalmente ordenado ou linearmente ordenado, e ≼ será chamada de ordem total e ordem linear Exemplo. No poset (Z+, |), os inteiros 3 e 9 são comparáveis, mas os inteiros 5 e 7 são incomparáveis, pois 5 ∤ 7 e 7 ∤ 5 O adjetivo “parcial” é usado para descrever as ordens parciais porque pares de elementos podem ser incomparáveis Quando quaisquer dois elementos no conjunto forem comparáveis, a relação é chamada de ordem total ou ordem linear Um conjunto totalmente ordenado também é chamado de cadeia Ordens Parciais Ordens Total Definição. Se (S, ≼) é um poset e quaisquer dois elementos de S são comparáveis, S é chamado de conjunto totalmente ordenado ou linearmente ordenado, e ≼ será chamada de ordem total e ordem linear Exemplo. No poset (Z+, |), os inteiros 3 e 9 são comparáveis, mas os inteiros 5 e 7 são incomparáveis, pois 5 ∤ 7 e 7 ∤ 5 O adjetivo “parcial” é usado para descrever as ordens parciais porque pares de elementos podem ser incomparáveis Quando quaisquer dois elementos no conjunto forem comparáveis, a relação é chamada de ordem total ou ordem linear Um conjunto totalmente ordenado também é chamado de cadeia Ordens Parciais Ordens Total Definição. Se (S, ≼) é um poset e quaisquer dois elementos de S são comparáveis, S é chamado de conjunto totalmente ordenado ou linearmente ordenado, e ≼ será chamada de ordem total e ordem linear Exemplo. No poset (Z+, |), os inteiros 3 e 9 são comparáveis, mas os inteiros 5 e 7 são incomparáveis, pois 5 ∤ 7 e 7 ∤ 5 O adjetivo “parcial” é usado para descrever as ordens parciais porque pares de elementos podem ser incomparáveis Quando quaisquer dois elementos no conjunto forem comparáveis, a relação é chamada de ordem total ou ordem linear Um conjunto totalmente ordenado também é chamado de cadeia Ordens Parciais Ordens Total Definição. Se (S, ≼) é um poset e quaisquer dois elementos de S são comparáveis, S é chamado de conjunto totalmente ordenado ou linearmente ordenado, e ≼ será chamada de ordem total e ordem linear Exemplo. No poset (Z+, |), os inteiros 3 e 9 são comparáveis, mas os inteiros 5 e 7 são incomparáveis, pois 5 ∤ 7 e 7 ∤ 5 O adjetivo “parcial” é usado para descrever as ordens parciais porque pares de elementos podem ser incomparáveis Quando quaisquer dois elementos no conjunto forem comparáveis, a relação é chamada de ordem total ou ordem linear Um conjunto totalmente ordenado também é chamado de cadeia Ordens Parciais Ordens Total Definição. Se (S, ≼) é um poset e quaisquer dois elementos de S são comparáveis, S é chamado de conjunto totalmente ordenado ou linearmente ordenado, e ≼ será chamada de ordem total e ordem linear Exemplo. No poset (Z+, |), os inteiros 3 e 9 são comparáveis, mas os inteiros 5 e 7 são incomparáveis, pois 5 ∤ 7 e 7 ∤ 5 O adjetivo “parcial” é usado para descrever as ordens parciais porque pares de elementos podem ser incomparáveis Quando quaisquer dois elementos no conjunto forem comparáveis, a relação é chamada de ordem total ou ordem linear Um conjunto totalmente ordenado também é chamado de cadeia Ordens Parciais Ordens Total Exemplo. O poset (Z, ≤) é totalmente ordenado, pois a ≤ b ou b ≤ a sempre que a e b forem inteiros Exemplo. O poset (Z+, |) não é totalmente ordenado, pois contém elementos não comparáveis Definição. (S, ≼) é um conjunto bem-ordenado se for um poset tal que ≼ seja uma ordem total e todo subconjunto não vazio de S tenha um menor elemento O conjunto A = {1, 3, 5, 7, · · · } dos inteiros positivos ímpares é um subconjunto não vazio de Z+ e possui o elemento mínimo (minA = 1) O conjunto P = {2, 3, 5, 7, 11, · · · } dos inteiros positivos primos é um subconjunto não vazio de Z+ e possui o elemento mínimo (minP = 2) Ordens Parciais Ordens Total Exemplo. O poset (Z, ≤) é totalmente ordenado, pois a ≤ b ou b ≤ a sempre que a e b forem inteiros Exemplo. O poset (Z+, |) não é totalmente ordenado, pois contém elementos não comparáveis Definição. (S, ≼) é um conjunto bem-ordenado se for um poset tal que ≼ seja uma ordem total e todo subconjunto não vazio de S tenha um menor elemento O conjunto A = {1, 3, 5, 7, · · · } dos inteiros positivos ímpares é um subconjunto não vazio de Z+ e possui o elemento mínimo (minA = 1) O conjunto P = {2, 3, 5, 7, 11, · · · } dos inteiros positivos primos é um subconjunto não vazio de Z+ e possui o elemento mínimo (minP = 2) Ordens Parciais Ordens Total Exemplo. O poset (Z, ≤) é totalmente ordenado, pois a ≤ b ou b ≤ a sempre que a e b forem inteiros Exemplo. O poset (Z+, |) não é totalmente ordenado, pois contém elementos não comparáveis Definição. (S, ≼) é um conjunto bem-ordenado se for um poset tal que ≼ seja uma ordem total e todo subconjunto não vazio de S tenha um menor elemento O conjunto A = {1, 3, 5, 7, · · · } dos inteiros positivos ímpares é um subconjunto não vazio de Z+ e possui o elemento mínimo (minA = 1) O conjunto P = {2, 3, 5, 7, 11, · · · } dos inteiros positivos primos é um subconjunto não vazio de Z+ e possui o elemento mínimo (minP = 2) Ordens Parciais Ordens Total Exemplo. O poset (Z, ≤) é totalmente ordenado, pois a ≤ b ou b ≤ a sempre que a e b forem inteiros Exemplo. O poset (Z+, |) não é totalmente ordenado, pois contém elementos não comparáveis Definição. (S, ≼) é um conjunto bem-ordenado se for um poset tal que ≼ seja uma ordem total e todo subconjunto não vazio de S tenha um menor elemento O conjunto A = {1, 3, 5, 7, · · · } dos inteiros positivos ímpares é um subconjunto não vazio de Z+ e possui o elemento mínimo (minA = 1) O conjunto P = {2, 3, 5, 7, 11, · · · } dos inteiros positivos primos é um subconjunto não vazio de Z+ e possui o elemento mínimo (minP = 2) Ordens Parciais Ordens Total Exemplo. O poset (Z, ≤) é totalmente ordenado, pois a ≤ b ou b ≤ a sempre que a e b forem inteiros Exemplo. O poset (Z+, |) não é totalmente ordenado, pois contém elementos não comparáveis Definição. (S, ≼) é um conjunto bem-ordenado se for um poset tal que ≼ seja uma ordem total e todo subconjunto não vazio de S tenha um menor elemento O conjunto A = {1, 3, 5, 7, · · · } dos inteiros positivos ímpares é um subconjunto não vazio de Z+ e possui o elemento mínimo (minA = 1) O conjunto P = {2, 3, 5, 7, 11, · · · } dos inteiros positivos primos é um subconjunto não vazio de Z+ e possui o elemento mínimo (minP = 2) Ordens Parciais Diagrama de Hasse Muitas arestas em um grafo orientado para um poset finito não precisam ser mostradas porque elas devem estar presentes Exemplo. Considere o grafo orientado para a ordem parcial {(a, b)|a ≤ b} no conjunto {1, 2, 3, 4} Como esta relação é de ordem parcial, ela é reflexiva e seu grafo orientado tem laço em todos os vértices Ordens Parciais Diagrama de Hasse Muitas arestas em um grafo orientado para um poset finito não precisam ser mostradas porque elas devem estar presentes Exemplo. Considere o grafo orientado para a ordem parcial {(a, b)|a ≤ b} no conjunto {1, 2, 3, 4} Como esta relação é de ordem parcial, ela é reflexiva e seu grafo orientado tem laço em todos os vértices Ordens Parciais Diagrama de Hasse Muitas arestas em um grafo orientado para um poset finito não precisam ser mostradas porque elas devem estar presentes Exemplo. Considere o grafo orientado para a ordem parcial {(a, b)|a ≤ b} no conjunto {1, 2, 3, 4} Como esta relação é de ordem parcial, ela é reflexiva e seu grafo orientado tem laço em todos os vértices Ordens Parciais Diagrama de Hasse Consequentemente, não precisamos mostrar esses laços, pois eles devem estar presentes Como uma ordem é parcial é transitiva, não precisamos mostrar as arestas que devem estar presentes por causa da transitividade E se supormos que todas as arestas estão apontadas “para cima”, não precisamos mostrar o sentido das arestas Ordens Parciais Diagrama de Hasse Consequentemente, não precisamos mostrar esses laços, pois eles devem estar presentes Como uma ordem é parcial é transitiva, não precisamos mostrar as arestas que devem estar presentes por causa da transitividade E se supormos que todas as arestas estão apontadas “para cima”, não precisamos mostrar o sentido das arestas Ordens Parciais Diagrama de Hasse Consequentemente, não precisamos mostrar esses laços, pois eles devem estar presentes Como uma ordem é parcial é transitiva, não precisamos mostrar as arestas que devem estar presentes por causa da transitividade E se supormos que todas as arestas estão apontadas “para cima”, não precisamos mostrar o sentido das arestas Ordens Parciais Diagrama de Hasse Como uma ordem é parcial é transitiva, não precisamos mostrar as arestas que devem estar presentes por causa da transitividade E se supormos que todas as arestas estão apontadas “para cima”, não precisamos mostrar o sentido das arestas O diagrama resultante contém informação suficiente para encontrar a ordem parcial Este diagrama é chamado de diagrama de Hasse Ordens Parciais Diagrama de Hasse Como uma ordem é parcial é transitiva, não precisamos mostrar as arestas que devem estar presentes por causa da transitividade E se supormos que todas as arestas estão apontadas “para cima”, não precisamos mostrar o sentido das arestas O diagrama resultante contém informação suficiente para encontrar a ordem parcial Este diagrama é chamado de diagrama de Hasse Ordens Parciais Elementos Maximais e Minimais Elemento Maximal. a é maximal no poset (S, ⪯) se não existir nenhum b ∈ S tal que a ≺ b Ou seja, a é maximal se ele não for menor do que nenhum elemento no poset Elemento Minimal. a é minimal no poset (S, ⪯) se não existir nenhum b ∈ S tal que b ≺ a Ou seja, a é minimal se ele não for maior do que nenhum elemento no poset Ordens Parciais Elementos Maximais e Minimais Elemento Maximal. a é maximal no poset (S, ⪯) se não existir nenhum b ∈ S tal que a ≺ b Ou seja, a é maximal se ele não for menor do que nenhum elemento no poset Elemento Minimal. a é minimal no poset (S, ⪯) se não existir nenhum b ∈ S tal que b ≺ a Ou seja, a é minimal se ele não for maior do que nenhum elemento no poset Ordens Parciais Elementos Maximais e Minimais Elemento Maximal. a é maximal no poset (S, ⪯) se não existir nenhum b ∈ S tal que a ≺ b Ou seja, a é maximal se ele não for menor do que nenhum elemento no poset Elemento Minimal. a é minimal no poset (S, ⪯) se não existir nenhum b ∈ S tal que b ≺ a Ou seja, a é minimal se ele não for maior do que nenhum elemento no poset Ordens Parciais Elementos Maximais e Minimais Elemento Maximal. a é maximal no poset (S, ⪯) se não existir nenhum b ∈ S tal que a ≺ b Ou seja, a é maximal se ele não for menor do que nenhum elemento no poset Elemento Minimal. a é minimal no poset (S, ⪯) se não existir nenhum b ∈ S tal que b ≺ a Ou seja, a é minimal se ele não for maior do que nenhum elemento no poset Ordens Parciais Elementos Maximais e Minimais Exemplo. Quais elementos do poset ({2, 4, 5, 10, 12, 20, 25}, |) são maximais e quais são minimais? O diagrama de Hasse para este poset é o seguinte: O diagrama mostra que os elementos maximais são 12, 20 e 25 Os elementos minimais são 2 e 5 Observe que um poset pode ter mais de um elemento maximal e mais de um elemento minimal Ordens Parciais Elementos Maximais e Minimais Exemplo. Quais elementos do poset ({2, 4, 5, 10, 12, 20, 25}, |) são maximais e quais são minimais? O diagrama de Hasse para este poset é o seguinte: O diagrama mostra que os elementos maximais são 12, 20 e 25 Os elementos minimais são 2 e 5 Observe que um poset pode ter mais de um elemento maximal e mais de um elemento minimal Ordens Parciais Elementos Maximais e Minimais Exemplo. Quais elementos do poset ({2, 4, 5, 10, 12, 20, 25}, |) são maximais e quais são minimais? O diagrama de Hasse para este poset é o seguinte: O diagrama mostra que os elementos maximais são 12, 20 e 25 Os elementos minimais são 2 e 5 Observe que um poset pode ter mais de um elemento maximal e mais de um elemento minimal Ordens Parciais Elementos Maximais e Minimais Exemplo. Quais elementos do poset ({2, 4, 5, 10, 12, 20, 25}, |) são maximais e quais são minimais? O diagrama de Hasse para este poset é o seguinte: O diagrama mostra que os elementos maximais são 12, 20 e 25 Os elementos minimais são 2 e 5 Observe que um poset pode ter mais de um elemento maximal e mais de um elemento minimal Ordens Parciais Elementos Maximais e Minimais Exemplo. Quais elementos do poset ({2, 4, 5, 10, 12, 20, 25}, |) são maximais e quais são minimais? O diagrama de Hasse para este poset é o seguinte: O diagrama mostra que os elementos maximais são 12, 20 e 25 Os elementos minimais são 2 e 5 Observe que um poset pode ter mais de um elemento maximal e mais de um elemento minimal Ordens Parciais Elementos Maximais e Minimais Exemplo. Quais elementos do poset ({2, 4, 5, 10, 12, 20, 25}, |) são maximais e quais são minimais? O diagrama de Hasse para este poset é o seguinte: O diagrama mostra que os elementos maximais são 12, 20 e 25 Os elementos minimais são 2 e 5 Observe que um poset pode ter mais de um elemento maximal e mais de um elemento minimal Ordens Parciais Elementos Maximais e Minimais Algumas vezes, existe um elemento em um poset que é maior do que todos os outros elementos Este elemento é chamado de maior elemento (ou máximo) a é o maior elemento do poset (S, ≼) se b ≼ a, ∀b ∈ S O maior elemento, se existir, é único Do mesmo modo, um elemento é chamado de menor (ou mínimo) se ele for menor do que todos os outros elementos no poset a é o menor elemento de (S, ≼) se a ≼ b, ∀b ∈ S O menor elemento, se existir, é único Exemplo. Existem um maior e um menor elemento no poset (Z+, |)? 1 é o menor elemento de (Z+), pois 1 | n, ∀n ∈ Z+ Como não existe nenhum inteiro que seja divisível por todos os inteiros positivos, não existe o maior elemento Ordens Parciais Elementos Maximais e Minimais Algumas vezes, existe um elemento em um poset que é maior do que todos os outros elementos Este elemento é chamado de maior elemento (ou máximo) a é o maior elemento do poset (S, ≼) se b ≼ a, ∀b ∈ S O maior elemento, se existir, é único Do mesmo modo, um elemento é chamado de menor (ou mínimo) se ele for menor do que todos os outros elementos no poset a é o menor elemento de (S, ≼) se a ≼ b, ∀b ∈ S O menor elemento, se existir, é único Exemplo. Existem um maior e um menor elemento no poset (Z+, |)? 1 é o menor elemento de (Z+), pois 1 | n, ∀n ∈ Z+ Como não existe nenhum inteiro que seja divisível por todos os inteiros positivos, não existe o maior elemento Ordens Parciais Elementos Maximais e Minimais Algumas vezes, existe um elemento em um poset que é maior do que todos os outros elementos Este elemento é chamado de maior elemento (ou máximo) a é o maior elemento do poset (S, ≼) se b ≼ a, ∀b ∈ S O maior elemento, se existir, é único Do mesmo modo, um elemento é chamado de menor (ou mínimo) se ele for menor do que todos os outros elementos no poset a é o menor elemento de (S, ≼) se a ≼ b, ∀b ∈ S O menor elemento, se existir, é único Exemplo. Existem um maior e um menor elemento no poset (Z+, |)? 1 é o menor elemento de (Z+), pois 1 | n, ∀n ∈ Z+ Como não existe nenhum inteiro que seja divisível por todos os inteiros positivos, não existe o maior elemento Ordens Parciais Elementos Maximais e Minimais Algumas vezes, existe um elemento em um poset que é maior do que todos os outros elementos Este elemento é chamado de maior elemento (ou máximo) a é o maior elemento do poset (S, ≼) se b ≼ a, ∀b ∈ S O maior elemento, se existir, é único Do mesmo modo, um elemento é chamado de menor (ou mínimo) se ele for menor do que todos os outros elementos no poset a é o menor elemento de (S, ≼) se a ≼ b, ∀b ∈ S O menor elemento, se existir, é único Exemplo. Existem um maior e um menor elemento no poset (Z+, |)? 1 é o menor elemento de (Z+), pois 1 | n, ∀n ∈ Z+ Como não existe nenhum inteiro que seja divisível por todos os inteiros positivos, não existe o maior elemento Ordens Parciais Elementos Maximais e Minimais Algumas vezes, existe um elemento em um poset que é maior do que todos os outros elementos Este elemento é chamado de maior elemento (ou máximo) a é o maior elemento do poset (S, ≼) se b ≼ a, ∀b ∈ S O maior elemento, se existir, é único Do mesmo modo, um elemento é chamado de menor (ou mínimo) se ele for menor do que todos os outros elementos no poset a é o menor elemento de (S, ≼) se a ≼ b, ∀b ∈ S O menor elemento, se existir, é único Exemplo. Existem um maior e um menor elemento no poset (Z+, |)? 1 é o menor elemento de (Z+), pois 1 | n, ∀n ∈ Z+ Como não existe nenhum inteiro que seja divisível por todos os inteiros positivos, não existe o maior elemento Ordens Parciais Elementos Maximais e Minimais Algumas vezes, existe um elemento em um poset que é maior do que todos os outros elementos Este elemento é chamado de maior elemento (ou máximo) a é o maior elemento do poset (S, ≼) se b ≼ a, ∀b ∈ S O maior elemento, se existir, é único Do mesmo modo, um elemento é chamado de menor (ou mínimo) se ele for menor do que todos os outros elementos no poset a é o menor elemento de (S, ≼) se a ≼ b, ∀b ∈ S O menor elemento, se existir, é único Exemplo. Existem um maior e um menor elemento no poset (Z+, |)? 1 é o menor elemento de (Z+), pois 1 | n, ∀n ∈ Z+ Como não existe nenhum inteiro que seja divisível por todos os inteiros positivos, não existe o maior elemento Ordens Parciais Elementos Maximais e Minimais Algumas vezes, existe um elemento em um poset que é maior do que todos os outros elementos Este elemento é chamado de maior elemento (ou máximo) a é o maior elemento do poset (S, ≼) se b ≼ a, ∀b ∈ S O maior elemento, se existir, é único Do mesmo modo, um elemento é chamado de menor (ou mínimo) se ele for menor do que todos os outros elementos no poset a é o menor elemento de (S, ≼) se a ≼ b, ∀b ∈ S O menor elemento, se existir, é único Exemplo. Existem um maior e um menor elemento no poset (Z+, |)? 1 é o menor elemento de (Z+), pois 1 | n, ∀n ∈ Z+ Como não existe nenhum inteiro que seja divisível por todos os inteiros positivos, não existe o maior elemento Ordens Parciais Elementos Maximais e Minimais Algumas vezes, existe um elemento em um poset que é maior do que todos os outros elementos Este elemento é chamado de maior elemento (ou máximo) a é o maior elemento do poset (S, ≼) se b ≼ a, ∀b ∈ S O maior elemento, se existir, é único Do mesmo modo, um elemento é chamado de menor (ou mínimo) se ele for menor do que todos os outros elementos no poset a é o menor elemento de (S, ≼) se a ≼ b, ∀b ∈ S O menor elemento, se existir, é único Exemplo. Existem um maior e um menor elemento no poset (Z+, |)? 1 é o menor elemento de (Z+), pois 1 | n, ∀n ∈ Z+ Como não existe nenhum inteiro que seja divisível por todos os inteiros positivos, não existe o maior elemento Ordens Parciais Elementos Maximais e Minimais Algumas vezes, existe um elemento em um poset que é maior do que todos os outros elementos Este elemento é chamado de maior elemento (ou máximo) a é o maior elemento do poset (S, ≼) se b ≼ a, ∀b ∈ S O maior elemento, se existir, é único Do mesmo modo, um elemento é chamado de menor (ou mínimo) se ele for menor do que todos os outros elementos no poset a é o menor elemento de (S, ≼) se a ≼ b, ∀b ∈ S O menor elemento, se existir, é único Exemplo. Existem um maior e um menor elemento no poset (Z+, |)? 1 é o menor elemento de (Z+), pois 1 | n, ∀n ∈ Z+ Como não existe nenhum inteiro que seja divisível por todos os inteiros positivos, não existe o maior elemento Ordens Parciais Elementos Maximais e Minimais Algumas vezes, existe um elemento em um poset que é maior do que todos os outros elementos Este elemento é chamado de maior elemento (ou máximo) a é o maior elemento do poset (S, ≼) se b ≼ a, ∀b ∈ S O maior elemento, se existir, é único Do mesmo modo, um elemento é chamado de menor (ou mínimo) se ele for menor do que todos os outros elementos no poset a é o menor elemento de (S, ≼) se a ≼ b, ∀b ∈ S O menor elemento, se existir, é único Exemplo. Existem um maior e um menor elemento no poset (Z+, |)? 1 é o menor elemento de (Z+), pois 1 | n, ∀n ∈ Z+ Como não existe nenhum inteiro que seja divisível por todos os inteiros positivos, não existe o maior elemento Relações de Equivalências Relações de Equivalências Uma relação em um conjunto A é denominada uma relação de equivalência se for reflexiva, simétrica e transitiva Dois elementos a e b que estão relacionados por uma relação de equivalência são denominados equivalentes Notação: a ∼ b Exemplo. A congruência módulo m, m ∈ Z∗ + é uma relação de equivalência no conjunto dos inteiros De fato, mostramos em Teoria dos Números que: a ≡ b(mod m) Se a ≡ b(mod m), então b ≡ a(mod m) Se a ≡ b(mod m) e b ≡ c(mod m), então a ≡ c(mod m) Ou seja, a congruência módulo m é reflexiva, simétrica e transitiva e, portanto, é uma relação de equivalência Relações de Equivalências Relações de Equivalências Uma relação em um conjunto A é denominada uma relação de equivalência se for reflexiva, simétrica e transitiva Dois elementos a e b que estão relacionados por uma relação de equivalência são denominados equivalentes Notação: a ∼ b Exemplo. A congruência módulo m, m ∈ Z∗ + é uma relação de equivalência no conjunto dos inteiros De fato, mostramos em Teoria dos Números que: a ≡ b(mod m) Se a ≡ b(mod m), então b ≡ a(mod m) Se a ≡ b(mod m) e b ≡ c(mod m), então a ≡ c(mod m) Ou seja, a congruência módulo m é reflexiva, simétrica e transitiva e, portanto, é uma relação de equivalência Relações de Equivalências Relações de Equivalências Uma relação em um conjunto A é denominada uma relação de equivalência se for reflexiva, simétrica e transitiva Dois elementos a e b que estão relacionados por uma relação de equivalência são denominados equivalentes Notação: a ∼ b Exemplo. A congruência módulo m, m ∈ Z∗ + é uma relação de equivalência no conjunto dos inteiros De fato, mostramos em Teoria dos Números que: a ≡ b(mod m) Se a ≡ b(mod m), então b ≡ a(mod m) Se a ≡ b(mod m) e b ≡ c(mod m), então a ≡ c(mod m) Ou seja, a congruência módulo m é reflexiva, simétrica e transitiva e, portanto, é uma relação de equivalência Relações de Equivalências Relações de Equivalências Uma relação em um conjunto A é denominada uma relação de equivalência se for reflexiva, simétrica e transitiva Dois elementos a e b que estão relacionados por uma relação de equivalência são denominados equivalentes Notação: a ∼ b Exemplo. A congruência módulo m, m ∈ Z∗ + é uma relação de equivalência no conjunto dos inteiros De fato, mostramos em Teoria dos Números que: a ≡ b(mod m) Se a ≡ b(mod m), então b ≡ a(mod m) Se a ≡ b(mod m) e b ≡ c(mod m), então a ≡ c(mod m) Ou seja, a congruência módulo m é reflexiva, simétrica e transitiva e, portanto, é uma relação de equivalência Relações de Equivalências Relações de Equivalências Uma relação em um conjunto A é denominada uma relação de equivalência se for reflexiva, simétrica e transitiva Dois elementos a e b que estão relacionados por uma relação de equivalência são denominados equivalentes Notação: a ∼ b Exemplo. A congruência módulo m, m ∈ Z∗ + é uma relação de equivalência no conjunto dos inteiros De fato, mostramos em Teoria dos Números que: a ≡ b(mod m) Se a ≡ b(mod m), então b ≡ a(mod m) Se a ≡ b(mod m) e b ≡ c(mod m), então a ≡ c(mod m) Ou seja, a congruência módulo m é reflexiva, simétrica e transitiva e, portanto, é uma relação de equivalência Relações de Equivalências Relações de Equivalências Uma relação em um conjunto A é denominada uma relação de equivalência se for reflexiva, simétrica e transitiva Dois elementos a e b que estão relacionados por uma relação de equivalência são denominados equivalentes Notação: a ∼ b Exemplo. A congruência módulo m, m ∈ Z∗ + é uma relação de equivalência no conjunto dos inteiros De fato, mostramos em Teoria dos Números que: a ≡ b(mod m) Se a ≡ b(mod m), então b ≡ a(mod m) Se a ≡ b(mod m) e b ≡ c(mod m), então a ≡ c(mod m) Ou seja, a congruência módulo m é reflexiva, simétrica e transitiva e, portanto, é uma relação de equivalência Relações de Equivalências Relações de Equivalências Uma relação em um conjunto A é denominada uma relação de equivalência se for reflexiva, simétrica e transitiva Dois elementos a e b que estão relacionados por uma relação de equivalência são denominados equivalentes Notação: a ∼ b Exemplo. A congruência módulo m, m ∈ Z∗ + é uma relação de equivalência no conjunto dos inteiros De fato, mostramos em Teoria dos Números que: a ≡ b(mod m) Se a ≡ b(mod m), então b ≡ a(mod m) Se a ≡ b(mod m) e b ≡ c(mod m), então a ≡ c(mod m) Ou seja, a congruência módulo m é reflexiva, simétrica e transitiva e, portanto, é uma relação de equivalência Relações de Equivalências Relações de Equivalências Uma relação em um conjunto A é denominada uma relação de equivalência se for reflexiva, simétrica e transitiva Dois elementos a e b que estão relacionados por uma relação de equivalência são denominados equivalentes Notação: a ∼ b Exemplo. A congruência módulo m, m ∈ Z∗ + é uma relação de equivalência no conjunto dos inteiros De fato, mostramos em Teoria dos Números que: a ≡ b(mod m) Se a ≡ b(mod m), então b ≡ a(mod m) Se a ≡ b(mod m) e b ≡ c(mod m), então a ≡ c(mod m) Ou seja, a congruência módulo m é reflexiva, simétrica e transitiva e, portanto, é uma relação de equivalência Relações de Equivalências Relações de Equivalências Uma relação em um conjunto A é denominada uma relação de equivalência se for reflexiva, simétrica e transitiva Dois elementos a e b que estão relacionados por uma relação de equivalência são denominados equivalentes Notação: a ∼ b Exemplo. A congruência módulo m, m ∈ Z∗ + é uma relação de equivalência no conjunto dos inteiros De fato, mostramos em Teoria dos Números que: a ≡ b(mod m) Se a ≡ b(mod m), então b ≡ a(mod m) Se a ≡ b(mod m) e b ≡ c(mod m), então a ≡ c(mod m) Ou seja, a congruência módulo m é reflexiva, simétrica e transitiva e, portanto, é uma relação de equivalência Classes de Equivalência Classes de Equivalência Sejam A um conjunto e R uma relação de equivalência em A. Para cada elemento de a ∈ A, chama-se classe de equivalência de a o conjunto C(a) = {x ∈ A|x ∼ a} Exemplo. No conjunto Zm = {0, 1, · · · , m − 1} as classes de equivalência são as classes de congruência 0, 1, · · · , m − 1, em que 0 = {0, ±m, ±2m, · · · } 1 = {1, 1 ± m, 1 ± 2m, · · · } · · · · · · · · · · · · · · · · · · · · · m − 1 = {m − 1, m − 1 ± m, m − 1 ± 2m, · · · } Classes de Equivalência Classes de Equivalência Sejam A um conjunto e R uma relação de equivalência em A. Para cada elemento de a ∈ A, chama-se classe de equivalência de a o conjunto C(a) = {x ∈ A|x ∼ a} Exemplo. No conjunto Zm = {0, 1, · · · , m − 1} as classes de equivalência são as classes de congruência 0, 1, · · · , m − 1, em que 0 = {0, ±m, ±2m, · · · } 1 = {1, 1 ± m, 1 ± 2m, · · · } · · · · · · · · · · · · · · · · · · · · · m − 1 = {m − 1, m − 1 ± m, m − 1 ± 2m, · · · } Classes de Equivalência Classes de Equivalência Sejam A um conjunto e R uma relação de equivalência em A. Para cada elemento de a ∈ A, chama-se classe de equivalência de a o conjunto C(a) = {x ∈ A|x ∼ a} Exemplo. No conjunto Zm = {0, 1, · · · , m − 1} as classes de equivalência são as classes de congruência 0, 1, · · · , m − 1, em que 0 = {0, ±m, ±2m, · · · } 1 = {1, 1 ± m, 1 ± 2m, · · · } · · · · · · · · · · · · · · · · · · · · · m − 1 = {m − 1, m − 1 ± m, m − 1 ± 2m, · · · } Classes de Equivalência Classes de Equivalência Sejam A um conjunto e R uma relação de equivalência em A. Para cada elemento de a ∈ A, chama-se classe de equivalência de a o conjunto C(a) = {x ∈ A|x ∼ a} Exemplo. No conjunto Zm = {0, 1, · · · , m − 1} as classes de equivalência são as classes de congruência 0, 1, · · · , m − 1, em que 0 = {0, ±m, ±2m, · · · } 1 = {1, 1 ± m, 1 ± 2m, · · · } · · · · · · · · · · · · · · · · · · · · · m − 1 = {m − 1, m − 1 ± m, m − 1 ± 2m, · · · } Classes de Equivalência Classes de Equivalência Sejam A um conjunto e R uma relação de equivalência em A. Para cada elemento de a ∈ A, chama-se classe de equivalência de a o conjunto C(a) = {x ∈ A|x ∼ a} Exemplo. No conjunto Zm = {0, 1, · · · , m − 1} as classes de equivalência são as classes de congruência 0, 1, · · · , m − 1, em que 0 = {0, ±m, ±2m, · · · } 1 = {1, 1 ± m, 1 ± 2m, · · · } · · · · · · · · · · · · · · · · · · · · · m − 1 = {m − 1, m − 1 ± m, m − 1 ± 2m, · · · } Classes de Equivalência Classes de Equivalência Sejam A um conjunto e R uma relação de equivalência em A. Para cada elemento de a ∈ A, chama-se classe de equivalência de a o conjunto C(a) = {x ∈ A|x ∼ a} Exemplo. No conjunto Zm = {0, 1, · · · , m − 1} as classes de equivalência são as classes de congruência 0, 1, · · · , m − 1, em que 0 = {0, ±m, ±2m, · · · } 1 = {1, 1 ± m, 1 ± 2m, · · · } · · · · · · · · · · · · · · · · · · · · · m − 1 = {m − 1, m − 1 ± m, m − 1 ± 2m, · · · } Classes de Equivalência Classes de Equivalência Sejam A um conjunto e R uma relação de equivalência em A. Para cada elemento de a ∈ A, chama-se classe de equivalência de a o conjunto C(a) = {x ∈ A|x ∼ a} Exemplo. Quais as classes de equivalência de 0 e 1 na congruência módulo 4? A classe de equivalência de 0 é: 0 = {· · · , −12, −8, −4, 0, 4, 8, 12 · · · } A classe de equivalência de 1 é: 1 = {· · · , −11, −7, −3, 1, 5, 9, 13 · · · } Classes de Equivalência Classes de Equivalência Sejam A um conjunto e R uma relação de equivalência em A. Para cada elemento de a ∈ A, chama-se classe de equivalência de a o conjunto C(a) = {x ∈ A|x ∼ a} Exemplo. Quais as classes de equivalência de 0 e 1 na congruência módulo 4? A classe de equivalência de 0 é: 0 = {· · · , −12, −8, −4, 0, 4, 8, 12 · · · } A classe de equivalência de 1 é: 1 = {· · · , −11, −7, −3, 1, 5, 9, 13 · · · } Classes de Equivalência Classes de Equivalência Sejam A um conjunto e R uma relação de equivalência em A. Para cada elemento de a ∈ A, chama-se classe de equivalência de a o conjunto C(a) = {x ∈ A|x ∼ a} Exemplo. Quais as classes de equivalência de 0 e 1 na congruência módulo 4? A classe de equivalência de 0 é: 0 = {· · · , −12, −8, −4, 0, 4, 8, 12 · · · } A classe de equivalência de 1 é: 1 = {· · · , −11, −7, −3, 1, 5, 9, 13 · · · } Classes de Equivalência Classes de Equivalência Sejam A um conjunto e R uma relação de equivalência em A. Para cada elemento de a ∈ A, chama-se classe de equivalência de a o conjunto C(a) = {x ∈ A|x ∼ a} Exemplo. Quais as classes de equivalência de 0 e 1 na congruência módulo 4? A classe de equivalência de 0 é: 0 = {· · · , −12, −8, −4, 0, 4, 8, 12 · · · } A classe de equivalência de 1 é: 1 = {· · · , −11, −7, −3, 1, 5, 9, 13 · · · } Classes de Equivalência Classes de Equivalência Sejam A um conjunto e R uma relação de equivalência em A. Para cada elemento de a ∈ A, chama-se classe de equivalência de a o conjunto C(a) = {x ∈ A|x ∼ a} Exemplo. Quais as classes de equivalência de 0 e 1 na congruência módulo 4? A classe de equivalência de 0 é: 0 = {· · · , −12, −8, −4, 0, 4, 8, 12 · · · } A classe de equivalência de 1 é: 1 = {· · · , −11, −7, −3, 1, 5, 9, 13 · · · } Classes de Equivalência Classes de Equivalência Exemplo. Seja R = {(a, b) ∈ Z2|a = b ou a = −b}. Qual a classe de equivalência de um inteiro a para a relação de equivalência R? Como um inteiro é equivalente a ele mesmo e a seu oposto nesta relação de equivalência, temos: C(a) = {−a, a} Note que C(a) contém dois inteiros distintos, a menos que a = 0 C(7) = {−7, 7} C(7) = {−5, 5} C(0) = {0} Classes de Equivalência Classes de Equivalência Exemplo. Seja R = {(a, b) ∈ Z2|a = b ou a = −b}. Qual a classe de equivalência de um inteiro a para a relação de equivalência R? Como um inteiro é equivalente a ele mesmo e a seu oposto nesta relação de equivalência, temos: C(a) = {−a, a} Note que C(a) contém dois inteiros distintos, a menos que a = 0 C(7) = {−7, 7} C(7) = {−5, 5} C(0) = {0} Classes de Equivalência Classes de Equivalência Exemplo. Seja R = {(a, b) ∈ Z2|a = b ou a = −b}. Qual a classe de equivalência de um inteiro a para a relação de equivalência R? Como um inteiro é equivalente a ele mesmo e a seu oposto nesta relação de equivalência, temos: C(a) = {−a, a} Note que C(a) contém dois inteiros distintos, a menos que a = 0 C(7) = {−7, 7} C(7) = {−5, 5} C(0) = {0} Classes de Equivalência Classes de Equivalência Exemplo. Seja R = {(a, b) ∈ Z2|a = b ou a = −b}. Qual a classe de equivalência de um inteiro a para a relação de equivalência R? Como um inteiro é equivalente a ele mesmo e a seu oposto nesta relação de equivalência, temos: C(a) = {−a, a} Note que C(a) contém dois inteiros distintos, a menos que a = 0 C(7) = {−7, 7} C(7) = {−5, 5} C(0) = {0} Classes de Equivalência Classes de Equivalência Exemplo. Seja R = {(a, b) ∈ Z2|a = b ou a = −b}. Qual a classe de equivalência de um inteiro a para a relação de equivalência R? Como um inteiro é equivalente a ele mesmo e a seu oposto nesta relação de equivalência, temos: C(a) = {−a, a} Note que C(a) contém dois inteiros distintos, a menos que a = 0 C(7) = {−7, 7} C(7) = {−5, 5} C(0) = {0} Classes de Equivalência Classes de Equivalência Exemplo. Seja R = {(a, b) ∈ Z2|a = b ou a = −b}. Qual a classe de equivalência de um inteiro a para a relação de equivalência R? Como um inteiro é equivalente a ele mesmo e a seu oposto nesta relação de equivalência, temos: C(a) = {−a, a} Note que C(a) contém dois inteiros distintos, a menos que a = 0 C(7) = {−7, 7} C(7) = {−5, 5} C(0) = {0} Classes de Equivalência Classes de Equivalência Exemplo. Seja R = {(a, b) ∈ Z2|a = b ou a = −b}. Qual a classe de equivalência de um inteiro a para a relação de equivalência R? Como um inteiro é equivalente a ele mesmo e a seu oposto nesta relação de equivalência, temos: C(a) = {−a, a} Note que C(a) contém dois inteiros distintos, a menos que a = 0 C(7) = {−7, 7} C(7) = {−5, 5} C(0) = {0} Relações de Equivalência e Partições Relações de Equivalência e Partições Uma partição de um conjunto S é uma coleção de subconjuntos não vazios de S mutuamente disjuntos cuja união resulte S Teorema. Uma relação de equivalência em um conjunto S determina uma partição de S, e uma partição de S determina uma relação de equivalência em S Relações de Equivalência e Partições Relações de Equivalência e Partições Exemplo. A relação de equivalência em N dada por R = {(x, y) ∈ N2|x + y é par} particiona N em duas classes de equivalência: Se x é par, então para qualquer número par y, x + y é par e, portanto, y ∈ C(x) Se x é ímpar, então para qualquer número ímpar y, x + y é ímpar e, portanto, y ∈ C(x) Relações de Equivalência e Partições Relações de Equivalência e Partições Exemplo. A relação de equivalência em N dada por R = {(x, y) ∈ N2|x + y é par} particiona N em duas classes de equivalência: Se x é par, então para qualquer número par y, x + y é par e, portanto, y ∈ C(x) Se x é ímpar, então para qualquer número ímpar y, x + y é ímpar e, portanto, y ∈ C(x) Relações de Equivalência e Partições Relações de Equivalência e Partições Exemplo. A relação de equivalência em N dada por R = {(x, y) ∈ N2|x + y é par} particiona N em duas classes de equivalência: Se x é par, então para qualquer número par y, x + y é par e, portanto, y ∈ C(x) Se x é ímpar, então para qualquer número ímpar y, x + y é ímpar e, portanto, y ∈ C(x) Relações de Equivalência e Partições Relações de Equivalência e Partições Exemplo. A relação de equivalência em N dada por R = {(x, y) ∈ N2|x + y é par} particiona N em duas classes de equivalência: Se x é par, então para qualquer número par y, x + y é par e, portanto, y ∈ C(x) Se x é ímpar, então para qualquer número ímpar y, x + y é ímpar e, portanto, y ∈ C(x) Relações de Equivalência e Partições Relações de Equivalência e Partições Exemplo. A relação de equivalência em N dada por R = {(x, y) ∈ N2|x + y é par} particiona N em duas classes de equivalência: Se x é par, então para qualquer número par y, x + y é par e, portanto, y ∈ C(x) Se x é ímpar, então para qualquer número ímpar y, x + y é ímpar e, portanto, y ∈ C(x) Relações de Equivalência e Partições Relações de Equivalência e Partições Exemplo. A relação de equivalência em N dada por R = {(x, y) ∈ N2|x + y é par} particiona N em duas classes de equivalência: Se x é par, então para qualquer número par y, x + y é par e, portanto, y ∈ C(x) Se x é ímpar, então para qualquer número ímpar y, x + y é ímpar e, portanto, y ∈ C(x) CONTINUA... Matemática Discreta Relações Professora: Lílian de Oliveira Carneiro Universidade Federal do Ceará Campus de Crateús Agosto de 2021