A maior rede de estudos do Brasil

Grátis
83 pág.
Aula 2 - Relações

Pré-visualização | Página 1 de 6

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ática