Aula 2 - Relações

Prévia do material em texto

Relações
Prof. Diego Brandão
Centro Federal de Educação Tecnológica Celso Suckow da Fonceca (CEFET/RJ)
Departamento Acadêmico de Informática (DEPIN)
22 de Março de 2019
(CEFET/RJ) Matemática Discreta 1 / 44
Roteiro
1 Relações matemáticas
2 Propriedades das relações
3 Grafo de uma endorelação
4 Relações de Ordem
5 Relações de equivalência
(CEFET/RJ) Matemática Discreta 2 / 44
Relação matemática
O conceito de relação matemática captura a ideia de que coisas estão
relacionadas. Serve para distinguir determinados pares ordenados de objetos
dos demais porque seus elementos satisfazem alguma relação que os
componentes dos demais pares, em geral, não satisfazem.
Exemplos de relações entre dois objetos são:
pessoa x é o pai de y, ou
carro x é maior do que y, ou
frutas x e y têm a mesma cor, ou
aluno x está matriculado na turma y com o professor z, ou
x2 + y2 = 4.
(CEFET/RJ) Matemática Discreta 3 / 44
Relação matemática
Exemplo
Se S = {1, 2, 3}, então S× S = {(1, 1),(1, 2), (1, 3), (2, 1), (2, 2), (2,3), (3, 1),
(3, 2), (3,3)}. Quais pares se distinguem pela propriedade de o
a) primeiro número ser igual ao segundo?
b) primeiro número ser menor do que o segundo?
Solução.
a) Os pares (1, 1), (2, 2), (3, 3) são os únicos pares que se distinguem em
S× S, i.e., os únicos pares ordenados cujas componentes são iguais.
b) Os pares (1, 2), (1, 3) e (2, 3) são os pares ordenados de S× S que se
distinguem dos demais por apresentarem tal propriedade.
(CEFET/RJ) Matemática Discreta 4 / 44
Relação matemática
Exemplo
Se S = {1, 2, 3}, então S× S = {(1, 1),(1, 2), (1, 3), (2, 1), (2, 2), (2,3), (3, 1),
(3, 2), (3,3)}. Quais pares se distinguem pela propriedade de o
a) primeiro número ser igual ao segundo?
b) primeiro número ser menor do que o segundo?
Solução.
a) Os pares (1, 1), (2, 2), (3, 3) são os únicos pares que se distinguem em
S× S, i.e., os únicos pares ordenados cujas componentes são iguais.
b) Os pares (1, 2), (1, 3) e (2, 3) são os pares ordenados de S× S que se
distinguem dos demais por apresentarem tal propriedade.
(CEFET/RJ) Matemática Discreta 4 / 44
Notação e descrição
No exemplo anterior, poderíamos selecionar os pares ordenados (x, y)
dizendo que x = y ou que x < y. Analogamente, a notação x𝜌y indica
que o par ordenado (x, y) satisfaz lação 𝜌.
Uma relação pode ser descrita com palavras ou simplesmente pela
enumeração dos pares ordenados que a satisfazem.
Normalmente, uma relação é definida por meio da descrição da relação,
em vez de listarmos todos os seus pares ordenados.
Isto porque a descrição nos fornece uma propriedade característica dos
elementos da relação; isto é, é um predicado binário que vale para certos
pares ordenados de S× S.
(CEFET/RJ) Matemática Discreta 5 / 44
Notação e descrição
Exemplo
Seja S = {1, 2, 4}. Então S× S = {(1,1), (1, 2), (1, 4), (2, 1), (2, 2), (2, 4), (4,
1), (4, 2), (4, 4)}.
Uma relação 𝜌 no conjunto S× S pode ser definida da seguinte forma:
x𝜌y se, e somente se, x = 12y.
De forma mais abreviada: x𝜌y↔ x = 12y.
Portanto (1, 2) e (2, 4) satisfazem 𝜌.
Alternativamente, podemos definir 𝜌 dizendo que {(1, 2), (2, 4)} é o
conjunto de pares ordenados que satisfazem 𝜌.
(CEFET/RJ) Matemática Discreta 6 / 44
Relação Binária em um Conjunto S
Relação Binária
Dados um conjunto S, uma relação binária em S é um subconjunto de S× S
(um conjunto de pares ordenados de elementos de S).
Exemplo
Seja S = {1, 2}. Então S× S = {(1, 1), (1, 2), (2, 1), (2, 2)}.
Uma das várias relações binárias em S× S é 𝜌, definida por
x𝜌y↔ x+ y for ímpar. Repare que (1, 2) ∈ 𝜌 e (2, 1) ∈ 𝜌.
Outra relação binária sobre em S× S é 𝜎 = {(1, 1), (2, 1)}. Neste caso,
1𝜎1 e 2𝜎1 são proposições verdadeiras, mas, por exemplo, 1𝜎2 não o é.
Repare também que, neste exemplo, 𝜎 não tem uma descrição verbal
óbvia.
(CEFET/RJ) Matemática Discreta 7 / 44
Relação n-ária
Relação n-ária
Dados os conjuntos S1, S2, . . . , Sn, uma relação n-ária em S1, S2, . . . , Sn
é um subconjunto de S1 × S2 × · · · × Sn.
Um caso especial de relação n-ária é uma relação unária 𝜌 em um
conjunto S, que é apenas um subconjunto particular de S.
Um elemento x ∈ S satisfaz 𝜌 se e somente se x pertencer ao subconjunto
particular.
(CEFET/RJ) Matemática Discreta 8 / 44
Relação n-ária
Relações n-árias em um conjunto S
São comuns relações n-árias, n ≤ 2, em que todos os conjuntos componentes
do produto cruzado são iguais ao mesmo conjunto S. Essas relações são
chamadas de relações no conjunto S.
Uma relação binária em um conjunto S é um subconjunto de S2.
Analogamente, uma relação n-ária em um conjunto S é um subconjunto
de Sn (um conjunto de n-uplas ordenadas de elementos de S).
Exemplo
Considere a relação 𝜌 definida por 𝜌 = {(x, y, z) ∈ N3 : x+ y+ z = 1}. Essa
é uma relação ternária (i.e., n-ária, com n = 3). De fato, os elementos de 𝜌 são
triplas ordenadas: 𝜌 = {(1, 0, 0), (0, 1, 0), (0, 0, 1)}.
(CEFET/RJ) Matemática Discreta 9 / 44
Tipos de relações
Se 𝜌 for uma relação binária em S× T , então 𝜌 consistirá em um conjunto de
pares ordenados da forma (s, t).
A primeira componente s e a segunda componente t podem ser
relacionadas diversas vezes na relação.
Uma relação é do tipo
um-para-um (ou injetiva ou biunívoca) se cada s e cada t aparecem
apenas uma vez na relação.
um-para-vários se algum s aparece mais de uma vez; isto é, se um s faz
par com mais de um t.
vários-para-um (ou unívoca) se algum t fizer par com mais de um s.
vários-para-vários se pelo menos um s fizer par com mais de um t e pelo
menos um t fizer par com mais de um s.
(CEFET/RJ) Matemática Discreta 10 / 44
Tipos de relações
A figura ilustra as quatro possibilidades. Perceba que nem todos os elementos
de S e de T precisam ser componentes de pares ordenados de 𝜌.
Fonte da figura: livro da Judith Gersting
(CEFET/RJ) Matemática Discreta 11 / 44
Operações sobre relações
Suponha que B é o conjunto de todas as relações binárias em um dado
conjunto S.
Se duas relações quaisquer 𝜌 e 𝜎 pertencem a B, então elas são
subconjuntos de S× S.
Como tal, podemos realizar as operações de união, interseção, e
complemento de conjuntos, que resultam em novos subconjuntos de
S× S, isto é, novas relações binárias, que denotamos por 𝜌 ∪ 𝜎, 𝜌 ∩ 𝜎 e
𝜌′, respectivamente.
Desta forma, temos que
x(𝜌 ∪ 𝜎)y↔ x𝜌y ou x𝜎y
x(𝜌 ∩ 𝜎)y↔ x𝜌y e x𝜎y
x𝜌′y↔ não x𝜌y
(CEFET/RJ) Matemática Discreta 12 / 44
Roteiro
1 Relações matemáticas
2 Propriedades das relações
3 Grafo de uma endorelação
4 Relações de Ordem
5 Relações de equivalência
(CEFET/RJ) Matemática Discreta 13 / 44
Propriedades das relações
Definição: Relações reflexivas, simétricas e transitivas e anti-simétricas
Uma relação binária em um conjunto S pode ter certas propriedades. Seja 𝜌
uma relação binária em um conjunto S. Então, 𝜌 possui a propriedade de ser
1 reflexiva sse (∀x)(x ∈ S→ (x, x) ∈ 𝜌)
2 simétrica sse (∀x)(∀y)(x ∈ S ∧ y ∈ S ∧ (x, y) ∈ 𝜌→ (y, x) ∈ 𝜌)
3 transitiva sse
(∀x)(∀y)(∀z)(x ∈ S∧y ∈ S∧ z ∈ S∧ (x, y) ∈ 𝜌∧ (y, z) ∈ 𝜌→ (x, z) ∈ 𝜌)
4 anti-simétrica sse
(∀x)(∀y)(x ∈ S ∧ y ∈ S ∧ (x, y) ∈ 𝜌 ∧ (y, x) ∈ 𝜌→ x = y)
(CEFET/RJ) Matemática Discreta 14 / 44
Propriedades das relações
Definição: Relações reflexivas, simétricas e transitivas e anti-simétricas
Uma relação binária em um conjunto S pode ter certas propriedades. Seja 𝜌
uma relação binária em um conjunto S. Então, 𝜌 possui a propriedade de ser
1 reflexiva sse (∀x)(x ∈ S→ (x, x) ∈ 𝜌)
2 simétrica sse (∀x)(∀y)(x ∈ S ∧ y ∈ S ∧ (x, y) ∈ 𝜌→ (y, x) ∈ 𝜌)
3 transitiva sse
(∀x)(∀y)(∀z)(x ∈ S∧y ∈ S∧ z ∈ S∧ (x, y) ∈ 𝜌∧ (y, z) ∈ 𝜌→ (x, z) ∈ 𝜌)
4 anti-simétrica sse
(∀x)(∀y)(x ∈ S ∧ y ∈ S ∧ (x, y) ∈ 𝜌 ∧ (y, x) ∈ 𝜌→ x = y)
(CEFET/RJ) MatemáticaDiscreta 14 / 44
Propriedades das relações
Definição: Relações reflexivas, simétricas e transitivas e anti-simétricas
Uma relação binária em um conjunto S pode ter certas propriedades. Seja 𝜌
uma relação binária em um conjunto S. Então, 𝜌 possui a propriedade de ser
1 reflexiva sse (∀x)(x ∈ S→ (x, x) ∈ 𝜌)
2 simétrica sse (∀x)(∀y)(x ∈ S ∧ y ∈ S ∧ (x, y) ∈ 𝜌→ (y, x) ∈ 𝜌)
3 transitiva sse
(∀x)(∀y)(∀z)(x ∈ S∧y ∈ S∧ z ∈ S∧ (x, y) ∈ 𝜌∧ (y, z) ∈ 𝜌→ (x, z) ∈ 𝜌)
4 anti-simétrica sse
(∀x)(∀y)(x ∈ S ∧ y ∈ S ∧ (x, y) ∈ 𝜌 ∧ (y, x) ∈ 𝜌→ x = y)
(CEFET/RJ) Matemática Discreta 14 / 44
Propriedades das relações
Definição: Relações reflexivas, simétricas e transitivas e anti-simétricas
Uma relação binária em um conjunto S pode ter certas propriedades. Seja 𝜌
uma relação binária em um conjunto S. Então, 𝜌 possui a propriedade de ser
1 reflexiva sse (∀x)(x ∈ S→ (x, x) ∈ 𝜌)
2 simétrica sse (∀x)(∀y)(x ∈ S ∧ y ∈ S ∧ (x, y) ∈ 𝜌→ (y, x) ∈ 𝜌)
3 transitiva sse
(∀x)(∀y)(∀z)(x ∈ S∧y ∈ S∧ z ∈ S∧ (x, y) ∈ 𝜌∧ (y, z) ∈ 𝜌→ (x, z) ∈ 𝜌)
4 anti-simétrica sse
(∀x)(∀y)(x ∈ S ∧ y ∈ S ∧ (x, y) ∈ 𝜌 ∧ (y, x) ∈ 𝜌→ x = y)
(CEFET/RJ) Matemática Discreta 14 / 44
Propriedades das relações
Definição: Relações reflexivas, simétricas e transitivas e anti-simétricas
Uma relação binária em um conjunto S pode ter certas propriedades. Seja 𝜌
uma relação binária em um conjunto S. Então, 𝜌 possui a propriedade de ser
1 reflexiva sse (∀x)(x ∈ S→ (x, x) ∈ 𝜌)
2 simétrica sse (∀x)(∀y)(x ∈ S ∧ y ∈ S ∧ (x, y) ∈ 𝜌→ (y, x) ∈ 𝜌)
3 transitiva sse
(∀x)(∀y)(∀z)(x ∈ S∧y ∈ S∧ z ∈ S∧ (x, y) ∈ 𝜌∧ (y, z) ∈ 𝜌→ (x, z) ∈ 𝜌)
4 anti-simétrica sse
(∀x)(∀y)(x ∈ S ∧ y ∈ S ∧ (x, y) ∈ 𝜌 ∧ (y, x) ∈ 𝜌→ x = y)
(CEFET/RJ) Matemática Discreta 14 / 44
Propriedades das relações
As propriedades podem ser interpretadas de maneira mais informal, conforme
a seguir.
Relações reflexivas, simétricas e transitivas
Reflexiva: todo x está relacionado a si mesmo.
Simétrica: se x está relacionado a y, então y está relacionado a x.
Transitiva: se x está relacionado a y, e se y está relacionado a z, então x
está relacionado a z.
Anti-simétrica: se x está relacionado a y e y está relacionado a x, então
x = y.
(CEFET/RJ) Matemática Discreta 15 / 44
Propriedades das relações
As propriedades podem ser interpretadas de maneira mais informal, conforme
a seguir.
Relações reflexivas, simétricas e transitivas
Reflexiva: todo x está relacionado a si mesmo.
Simétrica: se x está relacionado a y, então y está relacionado a x.
Transitiva: se x está relacionado a y, e se y está relacionado a z, então x
está relacionado a z.
Anti-simétrica: se x está relacionado a y e y está relacionado a x, então
x = y.
(CEFET/RJ) Matemática Discreta 15 / 44
Propriedades das relações
As propriedades podem ser interpretadas de maneira mais informal, conforme
a seguir.
Relações reflexivas, simétricas e transitivas
Reflexiva: todo x está relacionado a si mesmo.
Simétrica: se x está relacionado a y, então y está relacionado a x.
Transitiva: se x está relacionado a y, e se y está relacionado a z, então x
está relacionado a z.
Anti-simétrica: se x está relacionado a y e y está relacionado a x, então
x = y.
(CEFET/RJ) Matemática Discreta 15 / 44
Propriedades das relações
As propriedades podem ser interpretadas de maneira mais informal, conforme
a seguir.
Relações reflexivas, simétricas e transitivas
Reflexiva: todo x está relacionado a si mesmo.
Simétrica: se x está relacionado a y, então y está relacionado a x.
Transitiva: se x está relacionado a y, e se y está relacionado a z, então x
está relacionado a z.
Anti-simétrica: se x está relacionado a y e y está relacionado a x, então
x = y.
(CEFET/RJ) Matemática Discreta 15 / 44
Propriedades das relações
Exemplo
A relação 𝜌 de igualdade em um conjunto S, (x, y) ∈ 𝜌↔ x = y, tem três
propriedades, a saber:
1 para qualquer x ∈ S, x = x
2 para quaisquer x, y ∈ S, se x = y, então y = x. Isto é, tanto y𝜌x quanto
x𝜌y são proposições verdadeiras.
3 para quaisquer x, y, z ∈ S, se x = y e y = z, então x = z. Isto é,
(x, y) ∈ 𝜌 ∧ (y, z) ∈ 𝜌→ (x, z) ∈ 𝜌)
Essas três propriedades fazem da igualdade uma relação reflexiva, simétrica e
transitiva.
(CEFET/RJ) Matemática Discreta 16 / 44
Propriedades das relações
Exemplo
A relação 𝜌 de igualdade em um conjunto S, (x, y) ∈ 𝜌↔ x = y, tem três
propriedades, a saber:
1 para qualquer x ∈ S, x = x
2 para quaisquer x, y ∈ S, se x = y, então y = x. Isto é, tanto y𝜌x quanto
x𝜌y são proposições verdadeiras.
3 para quaisquer x, y, z ∈ S, se x = y e y = z, então x = z. Isto é,
(x, y) ∈ 𝜌 ∧ (y, z) ∈ 𝜌→ (x, z) ∈ 𝜌)
Essas três propriedades fazem da igualdade uma relação reflexiva, simétrica e
transitiva.
(CEFET/RJ) Matemática Discreta 16 / 44
Propriedades das relações
Exemplo
A relação 𝜌 de igualdade em um conjunto S, (x, y) ∈ 𝜌↔ x = y, tem três
propriedades, a saber:
1 para qualquer x ∈ S, x = x
2 para quaisquer x, y ∈ S, se x = y, então y = x. Isto é, tanto y𝜌x quanto
x𝜌y são proposições verdadeiras.
3 para quaisquer x, y, z ∈ S, se x = y e y = z, então x = z. Isto é,
(x, y) ∈ 𝜌 ∧ (y, z) ∈ 𝜌→ (x, z) ∈ 𝜌)
Essas três propriedades fazem da igualdade uma relação reflexiva, simétrica e
transitiva.
(CEFET/RJ) Matemática Discreta 16 / 44
Propriedades das relações
Exemplo
A relação 𝜌 de igualdade em um conjunto S, (x, y) ∈ 𝜌↔ x = y, tem três
propriedades, a saber:
1 para qualquer x ∈ S, x = x
2 para quaisquer x, y ∈ S, se x = y, então y = x. Isto é, tanto y𝜌x quanto
x𝜌y são proposições verdadeiras.
3 para quaisquer x, y, z ∈ S, se x = y e y = z, então x = z. Isto é,
(x, y) ∈ 𝜌 ∧ (y, z) ∈ 𝜌→ (x, z) ∈ 𝜌)
Essas três propriedades fazem da igualdade uma relação reflexiva, simétrica e
transitiva.
(CEFET/RJ) Matemática Discreta 16 / 44
Propriedades das relações
Exemplo
A relação 𝜌 de igualdade em um conjunto S, (x, y) ∈ 𝜌↔ x = y, tem três
propriedades, a saber:
1 para qualquer x ∈ S, x = x
2 para quaisquer x, y ∈ S, se x = y, então y = x. Isto é, tanto y𝜌x quanto
x𝜌y são proposições verdadeiras.
3 para quaisquer x, y, z ∈ S, se x = y e y = z, então x = z. Isto é,
(x, y) ∈ 𝜌 ∧ (y, z) ∈ 𝜌→ (x, z) ∈ 𝜌)
Essas três propriedades fazem da igualdade uma relação reflexiva, simétrica e
transitiva.
(CEFET/RJ) Matemática Discreta 16 / 44
Propriedades das relações
Exemplo
Considere a relação ≤ no conjunto N. Essa relação
é reflexiva porque, para qualquer x ∈ N, x ≤ x;
é transitiva porque, para quaisquer inteiros não-negativos x, y e z, se
x ≤ y e y ≤ z, então x ≤ z;
não é simétrica. Por exemplo, 3 ≤ 4 não implica 4 ≤ 3.
é anti-simétrica, pois, quaisquer que sejam os naturais x e y, se x ≤ y e
y ≤ x então x = y.
(CEFET/RJ) Matemática Discreta 17 / 44
Propriedades das relações
Exemplo
Considere a relação ≤ no conjunto N. Essa relação
é reflexiva porque, para qualquer x ∈ N, x ≤ x;
é transitiva porque, para quaisquer inteiros não-negativos x, y e z, se
x ≤ y e y ≤ z, então x ≤ z;
não é simétrica. Por exemplo, 3 ≤ 4 não implica 4 ≤ 3.
é anti-simétrica, pois, quaisquer que sejam os naturais x e y, se x ≤ y e
y ≤ x então x = y.
(CEFET/RJ) Matemática Discreta 17 / 44
Propriedades das relações
Exemplo
Considere a relação ≤ no conjunto N. Essa relação
é reflexiva porque, para qualquer x ∈ N, x ≤ x;
é transitiva porque, para quaisquer inteiros não-negativos x, y e z, se
x ≤ y e y ≤ z, então x ≤ z;
não é simétrica. Por exemplo, 3 ≤ 4 não implica 4 ≤ 3.
é anti-simétrica, pois, quaisquer que sejam os naturais x e y, se x ≤ y e
y ≤ x então x = y.
(CEFET/RJ) Matemática Discreta 17 / 44
Propriedades das relações
Exemplo
Considere a relação ≤ no conjunto N. Essa relação
é reflexiva porque, para qualquer x ∈ N, x ≤ x;
é transitiva porque,para quaisquer inteiros não-negativos x, y e z, se
x ≤ y e y ≤ z, então x ≤ z;
não é simétrica. Por exemplo, 3 ≤ 4 não implica 4 ≤ 3.
é anti-simétrica, pois, quaisquer que sejam os naturais x e y, se x ≤ y e
y ≤ x então x = y.
(CEFET/RJ) Matemática Discreta 17 / 44
Propriedades das relações
Exemplo
Considere a relação ≤ no conjunto N. Essa relação
é reflexiva porque, para qualquer x ∈ N, x ≤ x;
é transitiva porque, para quaisquer inteiros não-negativos x, y e z, se
x ≤ y e y ≤ z, então x ≤ z;
não é simétrica. Por exemplo, 3 ≤ 4 não implica 4 ≤ 3.
é anti-simétrica, pois, quaisquer que sejam os naturais x e y, se x ≤ y e
y ≤ x então x = y.
(CEFET/RJ) Matemática Discreta 17 / 44
Propriedades das relações
Exemplo
Seja S ∈ 𝒫(N). Defina uma relação binária 𝜌 em S por A𝜌B↔ A ⊆ B. Então
a relação 𝜌 é
reflexiva, porque todo conjunto é subconjunto de si próprio.
transitiva, porque se A é um subconjunto de B e B é um subconjunto de
C, então A é um subconjunto de C.
anti-simétrica, porque se A é subconjunto de B e B é um subconjunto de
A, então A e B são iguais.
Essa relação é simétrica?
(CEFET/RJ) Matemática Discreta 18 / 44
Propriedades das relações
Exemplo
Seja S ∈ 𝒫(N). Defina uma relação binária 𝜌 em S por A𝜌B↔ A ⊆ B. Então
a relação 𝜌 é
reflexiva, porque todo conjunto é subconjunto de si próprio.
transitiva, porque se A é um subconjunto de B e B é um subconjunto de
C, então A é um subconjunto de C.
anti-simétrica, porque se A é subconjunto de B e B é um subconjunto de
A, então A e B são iguais.
Essa relação é simétrica?
(CEFET/RJ) Matemática Discreta 18 / 44
Propriedades das relações
Exemplo
Seja S ∈ 𝒫(N). Defina uma relação binária 𝜌 em S por A𝜌B↔ A ⊆ B. Então
a relação 𝜌 é
reflexiva, porque todo conjunto é subconjunto de si próprio.
transitiva, porque se A é um subconjunto de B e B é um subconjunto de
C, então A é um subconjunto de C.
anti-simétrica, porque se A é subconjunto de B e B é um subconjunto de
A, então A e B são iguais.
Essa relação é simétrica?
(CEFET/RJ) Matemática Discreta 18 / 44
Propriedades das relações
Exemplo
Seja S ∈ 𝒫(N). Defina uma relação binária 𝜌 em S por A𝜌B↔ A ⊆ B. Então
a relação 𝜌 é
reflexiva, porque todo conjunto é subconjunto de si próprio.
transitiva, porque se A é um subconjunto de B e B é um subconjunto de
C, então A é um subconjunto de C.
anti-simétrica, porque se A é subconjunto de B e B é um subconjunto de
A, então A e B são iguais.
Essa relação é simétrica?
(CEFET/RJ) Matemática Discreta 18 / 44
Propriedades das relações
Exemplo
Seja S ∈ 𝒫(N). Defina uma relação binária 𝜌 em S por A𝜌B↔ A ⊆ B. Então
a relação 𝜌 é
reflexiva, porque todo conjunto é subconjunto de si próprio.
transitiva, porque se A é um subconjunto de B e B é um subconjunto de
C, então A é um subconjunto de C.
anti-simétrica, porque se A é subconjunto de B e B é um subconjunto de
A, então A e B são iguais.
Essa relação é simétrica?
(CEFET/RJ) Matemática Discreta 18 / 44
Propriedades das relações
Exemplo
Determine que propriedades (reflexividade, simetria, anti-simetria e
transitividade) as relações abaixo possuem.
a) ≤ (menor ou igual) em Z.
Solução. sim, não, sim, sim.
b) ⊆ em um conjunto C cujos elementos são conjuntos.
Solução. sim, não, sim, sim.
c) ⊥ (perpendicularidade) em um conjunto L de retas no plano.
Solução. não, sim, não, não.
d) ‖ (paralelismo) em um conjunto L de retas no plano.
Solução. não, sim, não, não.
e) | (divisibilidade) em N: x | y se existe z tal que xz = y.
Solução. sim, não, sim, sim.
(CEFET/RJ) Matemática Discreta 19 / 44
Propriedades das relações
Exemplo
Determine que propriedades (reflexividade, simetria, anti-simetria e
transitividade) as relações abaixo possuem.
a) ≤ (menor ou igual) em Z.
Solução. sim, não, sim, sim.
b) ⊆ em um conjunto C cujos elementos são conjuntos.
Solução. sim, não, sim, sim.
c) ⊥ (perpendicularidade) em um conjunto L de retas no plano.
Solução. não, sim, não, não.
d) ‖ (paralelismo) em um conjunto L de retas no plano.
Solução. não, sim, não, não.
e) | (divisibilidade) em N: x | y se existe z tal que xz = y.
Solução. sim, não, sim, sim.
(CEFET/RJ) Matemática Discreta 19 / 44
Propriedades das relações
Exemplo
Determine que propriedades (reflexividade, simetria, anti-simetria e
transitividade) as relações abaixo possuem.
a) ≤ (menor ou igual) em Z.
Solução. sim, não, sim, sim.
b) ⊆ em um conjunto C cujos elementos são conjuntos.
Solução. sim, não, sim, sim.
c) ⊥ (perpendicularidade) em um conjunto L de retas no plano.
Solução. não, sim, não, não.
d) ‖ (paralelismo) em um conjunto L de retas no plano.
Solução. não, sim, não, não.
e) | (divisibilidade) em N: x | y se existe z tal que xz = y.
Solução. sim, não, sim, sim.
(CEFET/RJ) Matemática Discreta 19 / 44
Propriedades das relações
Exemplo
Determine que propriedades (reflexividade, simetria, anti-simetria e
transitividade) as relações abaixo possuem.
a) ≤ (menor ou igual) em Z.
Solução. sim, não, sim, sim.
b) ⊆ em um conjunto C cujos elementos são conjuntos.
Solução. sim, não, sim, sim.
c) ⊥ (perpendicularidade) em um conjunto L de retas no plano.
Solução. não, sim, não, não.
d) ‖ (paralelismo) em um conjunto L de retas no plano.
Solução. não, sim, não, não.
e) | (divisibilidade) em N: x | y se existe z tal que xz = y.
Solução. sim, não, sim, sim.
(CEFET/RJ) Matemática Discreta 19 / 44
Propriedades das relações
Exemplo
Determine que propriedades (reflexividade, simetria, anti-simetria e
transitividade) as relações abaixo possuem.
a) ≤ (menor ou igual) em Z.
Solução. sim, não, sim, sim.
b) ⊆ em um conjunto C cujos elementos são conjuntos.
Solução. sim, não, sim, sim.
c) ⊥ (perpendicularidade) em um conjunto L de retas no plano.
Solução. não, sim, não, não.
d) ‖ (paralelismo) em um conjunto L de retas no plano.
Solução. não, sim, não, não.
e) | (divisibilidade) em N: x | y se existe z tal que xz = y.
Solução. sim, não, sim, sim.
(CEFET/RJ) Matemática Discreta 19 / 44
Propriedades das relações
Exemplo
Determine que propriedades (reflexividade, simetria, anti-simetria e
transitividade) as relações abaixo possuem.
a) ≤ (menor ou igual) em Z.
Solução. sim, não, sim, sim.
b) ⊆ em um conjunto C cujos elementos são conjuntos.
Solução. sim, não, sim, sim.
c) ⊥ (perpendicularidade) em um conjunto L de retas no plano.
Solução. não, sim, não, não.
d) ‖ (paralelismo) em um conjunto L de retas no plano.
Solução. não, sim, não, não.
e) | (divisibilidade) em N: x | y se existe z tal que xz = y.
Solução. sim, não, sim, sim.
(CEFET/RJ) Matemática Discreta 19 / 44
Propriedades das relações
Exemplo
Determine que propriedades (reflexividade, simetria, anti-simetria e
transitividade) as relações abaixo possuem.
a) ≤ (menor ou igual) em Z.
Solução. sim, não, sim, sim.
b) ⊆ em um conjunto C cujos elementos são conjuntos.
Solução. sim, não, sim, sim.
c) ⊥ (perpendicularidade) em um conjunto L de retas no plano.
Solução. não, sim, não, não.
d) ‖ (paralelismo) em um conjunto L de retas no plano.
Solução. não, sim, não, não.
e) | (divisibilidade) em N: x | y se existe z tal que xz = y.
Solução. sim, não, sim, sim.
(CEFET/RJ) Matemática Discreta 19 / 44
Propriedades das relações
Exemplo
Determine que propriedades (reflexividade, simetria, anti-simetria e
transitividade) as relações abaixo possuem.
a) ≤ (menor ou igual) em Z.
Solução. sim, não, sim, sim.
b) ⊆ em um conjunto C cujos elementos são conjuntos.
Solução. sim, não, sim, sim.
c) ⊥ (perpendicularidade) em um conjunto L de retas no plano.
Solução. não, sim, não, não.
d) ‖ (paralelismo) em um conjunto L de retas no plano.
Solução. não, sim, não, não.
e) | (divisibilidade) em N: x | y se existe z talque xz = y.
Solução. sim, não, sim, sim.
(CEFET/RJ) Matemática Discreta 19 / 44
Propriedades das relações
Exemplo
Determine que propriedades (reflexividade, simetria, anti-simetria e
transitividade) as relações abaixo possuem.
a) ≤ (menor ou igual) em Z.
Solução. sim, não, sim, sim.
b) ⊆ em um conjunto C cujos elementos são conjuntos.
Solução. sim, não, sim, sim.
c) ⊥ (perpendicularidade) em um conjunto L de retas no plano.
Solução. não, sim, não, não.
d) ‖ (paralelismo) em um conjunto L de retas no plano.
Solução. não, sim, não, não.
e) | (divisibilidade) em N: x | y se existe z tal que xz = y.
Solução. sim, não, sim, sim.
(CEFET/RJ) Matemática Discreta 19 / 44
Propriedades das relações
Exemplo
Determine que propriedades (reflexividade, simetria, anti-simetria e
transitividade) as relações abaixo possuem.
a) ≤ (menor ou igual) em Z.
Solução. sim, não, sim, sim.
b) ⊆ em um conjunto C cujos elementos são conjuntos.
Solução. sim, não, sim, sim.
c) ⊥ (perpendicularidade) em um conjunto L de retas no plano.
Solução. não, sim, não, não.
d) ‖ (paralelismo) em um conjunto L de retas no plano.
Solução. não, sim, não, não.
e) | (divisibilidade) em N: x | y se existe z tal que xz = y.
Solução. sim, não, sim, sim.
(CEFET/RJ) Matemática Discreta 19 / 44
Simetria vs anti-simetria
Tomando a negação da definição de anti-simetria,
(∀x)(∀y)(x ∈ S ∧ y ∈ S ∧ (x, y) ∈ 𝜌 ∧ (y, x) ∈ 𝜌→ x = y),
temos que uma relação 𝜌 definida em um conjunto S não é anti-simétrica sse,
∃ x, y ∈ S | (x, y) ∈ 𝜌 ∧ (y, x) ∈ 𝜌 ∧ x ̸= y.
Portanto, as propriedades de simetria e de anti-simetria não são mutuamente
excludentes.
Exemplo 1: a relação 𝜌 = {(1, 3), (3, 1), (2, 3)} não é simétrica nem
anti-simétrica.
Exemplo 2: a relação 𝜌 = {(1, 1), (2, 2)} é simétrica e anti-simétrica.
(CEFET/RJ) Matemática Discreta 20 / 44
Roteiro
1 Relações matemáticas
2 Propriedades das relações
3 Grafo de uma endorelação
4 Relações de Ordem
5 Relações de equivalência
(CEFET/RJ) Matemática Discreta 21 / 44
Grafo de uma endorelação
Dado um conjunto S qualquer, uma endorrelação é uma relação binária
definida sobre S× S.
Toda endorelação pode ser representada por um grafo. Para construir o grafo
de uma relação 𝜌:
crie um vértice para cada elemento de S;
adicione uma aresta de x para ele próprio se (x, x) ∈ 𝜌.
adicione uma aresta de x para y se (x, y) ∈ 𝜌;
(CEFET/RJ) Matemática Discreta 22 / 44
Grafo de uma relação
Exemplo
A relação R menor do que no conjunto de inteiros A = {1, 2, 3, 4} é o
conjunto {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}. R pode ser representada
pela seguinte grafo.
Fonte: http://www.cs.odu.edu/~toida/nerzic/content/relation/digraph_rep.html
(CEFET/RJ) Matemática Discreta 23 / 44
Representação Matricial de uma Relação
A representação de uma relação R : A→ B na forma de uma matriz é
importante para a implementação em um sistema computacional.
Dessa forma, seja A = {a1, a2, a3, ..., an} e B = {b1, b2, b3, ...bm}
R b1 b2 b3 ... bm
a1 V F F ... V
a2 F V F ... F
a3 V F V ... F
... ... ... ... ... ...
an V F V ... V
Se (ai, bi) ∈ R então a posição da matriz determinada pela linha i e coluna j
contém o valor lógico verdadeiro (V); caso contrário, contém o valor lógico
falso (F). Por simplicidade, utilizaremos os dígitos 0 e 1 no lugar de F e V,
respectivamente.
(CEFET/RJ) Matemática Discreta 24 / 44
Representação Matricial de uma Relação
Exemplo
A relação R igualdade no conjunto de inteiros A = {1, 2, 3, 4} é o conjunto
{(1, 1), (2, 2), (3, 3), (4, 4))}. R pode ser representada pela seguinte matriz.
= 1 2 3 4
1 1 0 0 0
2 0 1 0 0
3 0 0 1 0
4 0 0 0 1
(CEFET/RJ) Matemática Discreta 25 / 44
Roteiro
1 Relações matemáticas
2 Propriedades das relações
3 Grafo de uma endorelação
4 Relações de Ordem
5 Relações de equivalência
(CEFET/RJ) Matemática Discreta 26 / 44
Relações de ordem
Relações de ordem capturam o conceito ordem sobres os elementos de um
conjunto. Por exemplo, considere as relações ≤ (que estabelece uma ordem
sobre números inteiros) e ⊆ (que estabelece uma ordem sobre conjuntos).
Ordenar objetos de acordo com alguma regra traz estruturação para uma área
de estudo. Por exemplo, em Computação:
o algoritmo de busca binária é eficiente, mas pressupõe que elementos de
uma lista estejam ordenados;
muitos SGBDs armazenam coleções de informações em alguma ordem
(e.g., CPF, matrícula) para facilitar a consulta (conceito de índice em
SGBD);
(CEFET/RJ) Matemática Discreta 27 / 44
Relações de ordem
Definição: Relação de ordem parcial
Uma relação binária em um conjunto S que seja ao mesmo tempo reflexiva,
anti-simétrica e transitiva é chamada de relação de ordem parcial em S, ou
simplesmente ordem parcial em S.
Definição: Conjunto parcialmente ordenado
Se 𝜌 é uma ordem parcial em S, então o par ordenado (S, 𝜌) é chamado
de um conjunto parcialmente ordenado, ou simplesmente poset.
Sendo assim, um poset é composto por um conjunto S e por uma ordem
parcial sobre S.
Vamos denotar um poset arbitrário por (S,⪯). Em qualquer caso
particular, ⪯ tem um significado preciso como, por exemplo: menor ou
igual a, é subconjunto de, divide, etc.
(CEFET/RJ) Matemática Discreta 28 / 44
Relações de ordem
Exemplo
Considere a relação divide no conjunto dos números naturais, denotada por
x|y (relação de divisibilidade). Prove que esta é uma relação de ordem parcial
em N*.
(reflexiva) a|a para todo a ∈ N*, pois a = ka, quando k = 1.
(anti-simetria) Suponha que a = k1b, e que b = k2a. Sendo assim,
substituindo uma equação na outra, encontramos k1k2 = 1. Visto que
k1, k2 são naturais não-nulos, então k1 = k2 = 1, e portanto a = b.
(transitiva) se a|b e b|c, então b = k1a e c = k2b para inteiros k1, k2.
Sendo assim c = k1k2a, o que significa que a|c.
Repare que dois números naturais nem sempre são comparáveis por esta
ordem, como, por exemplo, 5 e 7 (nem 5 divide 7, nem 7 divide 5).
(CEFET/RJ) Matemática Discreta 29 / 44
Relações de ordem
Exemplo
Considere a relação divide no conjunto dos números naturais, denotada por
x|y (relação de divisibilidade). Prove que esta é uma relação de ordem parcial
em N*.
(reflexiva) a|a para todo a ∈ N*, pois a = ka, quando k = 1.
(anti-simetria) Suponha que a = k1b, e que b = k2a. Sendo assim,
substituindo uma equação na outra, encontramos k1k2 = 1. Visto que
k1, k2 são naturais não-nulos, então k1 = k2 = 1, e portanto a = b.
(transitiva) se a|b e b|c, então b = k1a e c = k2b para inteiros k1, k2.
Sendo assim c = k1k2a, o que significa que a|c.
Repare que dois números naturais nem sempre são comparáveis por esta
ordem, como, por exemplo, 5 e 7 (nem 5 divide 7, nem 7 divide 5).
(CEFET/RJ) Matemática Discreta 29 / 44
Relações de ordem
Exemplo
Considere a relação divide no conjunto dos números naturais, denotada por
x|y (relação de divisibilidade). Prove que esta é uma relação de ordem parcial
em N*.
(reflexiva) a|a para todo a ∈ N*, pois a = ka, quando k = 1.
(anti-simetria) Suponha que a = k1b, e que b = k2a. Sendo assim,
substituindo uma equação na outra, encontramos k1k2 = 1. Visto que
k1, k2 são naturais não-nulos, então k1 = k2 = 1, e portanto a = b.
(transitiva) se a|b e b|c, então b = k1a e c = k2b para inteiros k1, k2.
Sendo assim c = k1k2a, o que significa que a|c.
Repare que dois números naturais nem sempre são comparáveis por esta
ordem, como, por exemplo, 5 e 7 (nem 5 divide 7, nem 7 divide 5).
(CEFET/RJ) Matemática Discreta 29 / 44
Relações de ordem
Exemplo
Considere a relação divide no conjunto dos números naturais, denotada por
x|y (relação de divisibilidade). Prove que esta é uma relação de ordem parcial
em N*.
(reflexiva) a|a para todo a ∈ N*, pois a = ka, quando k = 1.
(anti-simetria) Suponha que a= k1b, e que b = k2a. Sendo assim,
substituindo uma equação na outra, encontramos k1k2 = 1. Visto que
k1, k2 são naturais não-nulos, então k1 = k2 = 1, e portanto a = b.
(transitiva) se a|b e b|c, então b = k1a e c = k2b para inteiros k1, k2.
Sendo assim c = k1k2a, o que significa que a|c.
Repare que dois números naturais nem sempre são comparáveis por esta
ordem, como, por exemplo, 5 e 7 (nem 5 divide 7, nem 7 divide 5).
(CEFET/RJ) Matemática Discreta 29 / 44
Relações de ordem
Definição: sucessores e predecessores
Seja (S,⪯) um conjunto parcialmente ordenado.
Se x ⪯ y, então, ou x = y ou x ̸= y.
Se x ⪯ y, mas x ̸= y, dizemos que x é um predecessor de y, e que y é um
sucessor de x.
Um dado y pode ter diversos predecessores, mas, se x ⪯ y e não há z tal
que x ⪯ z ⪯ y, então dizemos que x é um predecessor imediato de y.
Exemplo
Considere o poset ({2,3,4,12}, |).
O elemento 2 é predecessor de 4 e de 12.
O elemento 2 é predecessor imediato de 4.
O elemento 3 é predecessor imediato de 12.
(CEFET/RJ) Matemática Discreta 30 / 44
Relações de ordem
Definição: sucessores e predecessores
Seja (S,⪯) um conjunto parcialmente ordenado.
Se x ⪯ y, então, ou x = y ou x ̸= y.
Se x ⪯ y, mas x ̸= y, dizemos que x é um predecessor de y, e que y é um
sucessor de x.
Um dado y pode ter diversos predecessores, mas, se x ⪯ y e não há z tal
que x ⪯ z ⪯ y, então dizemos que x é um predecessor imediato de y.
Exemplo
Considere o poset ({2,3,4,12}, |).
O elemento 2 é predecessor de 4 e de 12.
O elemento 2 é predecessor imediato de 4.
O elemento 3 é predecessor imediato de 12.
(CEFET/RJ) Matemática Discreta 30 / 44
Ordem total
Definição: elementos incomparáveis
Considere uma relação 𝜌 sobre um conjunto S, e x, y ∈ S, x ̸= y. Os
elementos x e y são ditos incomparáveis sse (x, y) /∈ 𝜌 e (y, x) /∈ 𝜌.
Definição: Ordem total
Uma relação de ordem total é aquela que não possui pares de elementos
incomparáveis.
Exemplo
A relação ≥ em Z é uma relação de ordem (posto que é reflexiva,
anti-simétrica e transitiva). Além disso, dados dois inteiros a e b, é sempre
verdade que ou a ≥ b ou b ≥ a. Portanto, trata-se de uma relação de ordem
total sobre o conjunto dos inteiros.
(CEFET/RJ) Matemática Discreta 31 / 44
Diagrama de Hasse
Definição: Diagrama de Hasse
Um diagrama de Hasse é um grafo representa visualmente um conjunto
parcialmente ordenado.
Para construir o diagrama de Hasse para um poset (S, 𝜌):
crie o grafo dirigido para conjunto parcialmente ordenado;
remova todos os laços desse grafo;
redesenhe o grafo de tal forma que todas as setas apontem para cima;
remova as setas.
(CEFET/RJ) Matemática Discreta 32 / 44
Diagrama de Hasse
Exemplo
A figura (c) abaixo apresenta o diagrama de Hasse para o conjunto
parcialmente ordenado ({1, 2, 3, 4},≤).
Fonte da figura: [Rosen, 2012]
(CEFET/RJ) Matemática Discreta 33 / 44
Diagrama de Hasse
Exemplo
Considere o conjunto parcialmente ordenado (𝒫({x, y, z}),⊆). A figura
abaixo apresenta o grafo dirigido desse conjunto parcialmente ordenado.
Diagrama de Hasse correspondente:
(CEFET/RJ) Matemática Discreta 34 / 44
Diagrama de Hasse
Exemplo
Considere o conjunto parcialmente ordenado (𝒫({x, y, z}),⊆). A figura
abaixo apresenta o grafo dirigido desse conjunto parcialmente ordenado.
Diagrama de Hasse correspondente:
(CEFET/RJ) Matemática Discreta 34 / 44
Diagrama de Hasse
Exemplo
Considere o conjunto parcialmente ordenado ({1, 2, 3, 9, 18}, |). A figura
abaixo apresenta o grafo dirigido desse conjunto parcialmente ordenado.
Diagrama de Hasse correspondente ao conjunto parcialmente ordenado acima:
(CEFET/RJ) Matemática Discreta 35 / 44
Diagrama de Hasse
Exemplo
Considere o conjunto parcialmente ordenado ({1, 2, 3, 9, 18}, |). A figura
abaixo apresenta o grafo dirigido desse conjunto parcialmente ordenado.
Diagrama de Hasse correspondente ao conjunto parcialmente ordenado acima:
(CEFET/RJ) Matemática Discreta 35 / 44
Roteiro
1 Relações matemáticas
2 Propriedades das relações
3 Grafo de uma endorelação
4 Relações de Ordem
5 Relações de equivalência
(CEFET/RJ) Matemática Discreta 36 / 44
Relações de equivalência - introdução
Classificar e posicionar objetos semelhantes em grupos fornece uma maneira
de organizar a informação e concentrar a atenção sobre as semelhanças entre
objetos.
é por meio de relações de equivalência que a Matemática formaliza o conceito
de considerar um conjunto de objetos iguais de acordo com algum critério.
Uma relação de equivalência é uma espécie de igualdade generalizada, que
divide objetos de um conjunto em diferentes classes, e na qual objetos em
uma determinada classe são considerados iguais (equivalentes).
(CEFET/RJ) Matemática Discreta 37 / 44
Relações de equivalência - definição
Definição: Relação de Equivalência
Uma relação binária em um conjunto S que seja reflexiva, simétrica e
transitiva é chamada de uma relação de equivalência em S. Relações de
equivalência capturam a noção de que grupos de objetos são equivalentes
entre si, em algum contexto.
Exemplo
A seguir, uma lista de relações de equivalência.
(CEFET/RJ) Matemática Discreta 38 / 44
Relações de equivalência - definição
(CEFET/RJ) Matemática Discreta 39 / 44
Partição de um conjunto
Relações de equivalência podem ser utilizadas para construir partições de
conjuntos.
Partição de um conjunto
Uma partição de um conjunto A é uma coleção {Ai} de subconjuntos disjuntos
não vazios de A. Isto é,
1
⋃︀
i Ai = A, i.e., a união de todas partes resulta em A;
2 Ai ̸= ∅, para todo i;
3 Ai ∩ Aj = ∅, para todo i ̸= j.
(CEFET/RJ) Matemática Discreta 40 / 44
Relações de equivalência - partição de um conjunto
Três exemplos de partições de conjuntos:
Os números inteiros pares e ímpares são uma partição os inteiros em dois
distintos conjuntos.
Uma coleção de pessoas divididas em grupos de acordo com a primeira
letra em seu nome.
Um conjunto de estudantes em uma sala de aula divididos em homens e
mulheres. (Se não existem pessoas de um dos sexos, então a partição é o
próprio conjunto de estudantes.)
(CEFET/RJ) Matemática Discreta 41 / 44
Relações de equivalência - partição de um conjunto
Três exemplos de partições de conjuntos:
Os números inteiros pares e ímpares são uma partição os inteiros em dois
distintos conjuntos.
Uma coleção de pessoas divididas em grupos de acordo com a primeira
letra em seu nome.
Um conjunto de estudantes em uma sala de aula divididos em homens e
mulheres. (Se não existem pessoas de um dos sexos, então a partição é o
próprio conjunto de estudantes.)
(CEFET/RJ) Matemática Discreta 41 / 44
Relações de equivalência - partição de um conjunto
Três exemplos de partições de conjuntos:
Os números inteiros pares e ímpares são uma partição os inteiros em dois
distintos conjuntos.
Uma coleção de pessoas divididas em grupos de acordo com a primeira
letra em seu nome.
Um conjunto de estudantes em uma sala de aula divididos em homens e
mulheres. (Se não existem pessoas de um dos sexos, então a partição é o
próprio conjunto de estudantes.)
(CEFET/RJ) Matemática Discreta 41 / 44
Relações de equivalência - relação induzida
Relação induzida
Dada uma partição de um conjunto S, a relação binária R induzida por essa
partição é definida em S tal que, ∀x, y ∈ A, xRy↔ existe um subconjunto C da
partição tal que x e y estão em C.
Uma relação induzida por uma partição de um conjunto satisfaz as
propriedades de reflexividade, simetria e transitividade.
Exemplo
Seja A = {0, 1, 2, 3, 4} e considere a seguinte partição de S: {0, 3, 4}, {1},
{2}. Determine a relação R induzida por esta partição.
Solução. A relação é a seguinte:
R =
{(0, 0), (0, 3), (0, 4), (3, 0), (3, 3), (3, 4), (4, 0), (4, 3), (4, 4), (1,1), (2, 2)}
(CEFET/RJ) Matemática Discreta 42 / 44
Relações de equivalência - relação induzida
Relação induzida
Dada uma partição de um conjunto S, a relação binária R induzida por essa
partição é definida em S tal que, ∀x, y ∈ A, xRy↔ existe um subconjunto C da
partição tal que x e y estão em C.
Uma relação induzida por uma partição de um conjunto satisfaz as
propriedades de reflexividade, simetria e transitividade.
Exemplo
Seja A = {0, 1, 2, 3, 4} e considere a seguinte partição de S: {0, 3, 4}, {1},
{2}. Determine a relação R induzida por esta partição.
Solução. A relação é a seguinte:
R =
{(0, 0), (0, 3), (0, 4), (3, 0), (3, 3), (3, 4), (4, 0), (4, 3), (4, 4), (1, 1), (2, 2)}
(CEFET/RJ) Matemática Discreta 42 / 44
Relações de equivalência - classes de equivalência
Classes de equivalência
Uma relação de equivalência definida em um conjunto A, divide o conjunto
em subconjuntos disjuntos chamados classes de equivalência. Os elementos
de cada classe de equivalência são equivalentes entre si, e não equivalentes
com qualquer elemento de alguma outra classe de equivalência.
(CEFET/RJ) Matemática Discreta 43 / 44
Relações de equivalência - classes de equivalência
Exercício
Definimos dois números x, y ∈ Z como equivalentes se eles têm o mesmo
resto quando divididos por um número determinado, por exemplo 5, e
escrevemos x ≡ y (mod5). Mostre que esta é uma relação de equivalência e
encontre as classes de equivalência dessa relação. Lembrando que:
R = {(a, b)|a ≡ b(mod m)} ⇐⇒ m|(a− b)
Solução. Traduzindo o que queremos mostrar: Seja m um inteiro positivo
maior do que 1. Mostre que: R = {(a, b)|a ≡ b(mod m)}
1 Reflexividade: a ≡ a(mod m) pois a− a = 0 e m|0 =⇒ aRa
2 Simetria: se a ≡ b(mod m) =⇒ a− b = k.m =⇒ b− a =
(−k).m =⇒ b ≡ a(mod m) =⇒ aRb =⇒ bRa
3 Transitividade: suponha que a ≡ b(mod m) e b ≡ c(mod m), i.e. m
divide tanto (b− a) como (c− b), logo a− b = k.m e b− c = z.m
somando: (a− b) + (b− c) = k.m+ z.m =⇒ a− c = (k + z).m
=⇒ a ≡ c(mod m) portanto, aRb e bRc =⇒ aRc e R é transitiva.
(CEFET/RJ) Matemática Discreta 44 / 44
Relações de equivalência - classes de equivalência
Exercício
Definimos dois números x, y ∈ Z como equivalentes se eles têm o mesmo
resto quando divididos por um número determinado, por exemplo 5, e
escrevemos x ≡ y (mod5). Mostre que esta é uma relação de equivalência e
encontre as classes de equivalência dessa relação. Lembrando que:
R = {(a, b)|a ≡ b(mod m)} ⇐⇒ m|(a− b)
Solução. Traduzindo o que queremos mostrar: Seja m um inteiro positivo
maior do que 1. Mostre que: R = {(a, b)|a ≡ b(mod m)}
1 Reflexividade: a ≡ a(mod m) pois a− a = 0 e m|0 =⇒ aRa
2 Simetria: se a ≡ b(mod m) =⇒ a− b = k.m =⇒ b− a =
(−k).m =⇒ b ≡ a(mod m) =⇒ aRb =⇒ bRa
3 Transitividade: suponha que a ≡ b(mod m) e b ≡ c(mod m), i.e. m
divide tanto (b− a) como (c− b), logo a− b = k.m e b− c = z.m
somando: (a− b) + (b− c) = k.m+ z.m =⇒ a− c = (k + z).m
=⇒ a ≡ c(mod m) portanto, aRb e bRc =⇒ aRc e R é transitiva.
(CEFET/RJ) Matemática Discreta 44 / 44
	Relações matemáticas
	Propriedades das relações
	Grafo de uma endorelação
	Relações de Ordem
	Relações de equivalência