Relações Binárias em Conjuntos

Prévia do material em texto

Relações 
Relações Binárias 
• Sendo S = {1, 2, 3} o produto cartesiano de S² 
ou S x S = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 
3), (3, 1), (3, 2), (3, 3)}. 
• Se tivéssemos interessados em uma relação de 
igualdade, x = y, então (1, 1), (2, 2), (3, 3) 
seriam os elementos que escolheríamos. 
• Se estivéssemos interessados na relação de o 
primeiro número ser menor que o segundo, x < 
y, escolheríamos (1, 2), (1, 3), (2, 3) 
• A notação x ρ y indica que o par ordenado (x,y) 
satisfaz a relação ρ. 
• A relação ρ pode ser definida por palavras ou, 
simplesmente, listando-se os pares ordenados 
que satisfazem ρ. 
Exemplo 
• Para S = {1, 2, 4} no conjunto de S² pode-se 
definir uma relação ρ por x ρ y se, e somente se, 
x = y/2, abreviada como x ρ y ↔ x = y/2. 
Portanto, (1, 2) e (2, 4) satisfazem ρ, ou {(1, 2), 
(2, 4)} é o conjunto de pares ordenados que 
satisfazem ρ 
• A definição é que dado um conjunto S, uma 
relação binária em S é um subconjunto de S x S. 
• Agora que sabemos que uma relação binária ρ é 
um subconjunto, vemos que: 
x ρ y ↔ (x, y) ∈ ρ 
• Em geral, uma relação binária é definida por 
uma descrição da relação, ao invés da lista dos 
pares ordenados. 
• A descrição fornece uma caracterização dos 
elementos pertencentes à relação, isto é, é um 
predicado binário que é satisfeito por 
determinados pares ordenados. 
• Seja S = {1, 2} 
• Seja ρ uma relação tal que x ρ y ↔ x + y é 
ímpar. 
• Neste caso, (1, 2) ∈ ρ e (2, 1) ∈ ρ. 
• Suponha agora pro mesmo S uma outra 
relação definida por ρ = {(1, 1), (2, 1)} 
• Temos então que 1 ρ 1 e 2 ρ 1 são verdadeiras 
mas 1 ρ 2 não é, por exemplo. 
• Essa é relação que não parece ter uma 
descrição verbal óbvia, mas é uma relação 
binária. 
• As relações também podem ser definidas em 
conjuntos diferentes. 
• Dados conjuntos S e T, uma relação binária se S 
para T é um subconjunto de S x T. 
• Dados conjuntos S, T e U, uma relação ternária se 
S para T para U é um subconjunto de S x T x U. 
• Dados n conjuntos 𝑆1, 𝑆2, ..., 𝑆𝑛, n > 2, uma 
relação n-ária em 𝑆1 x 𝑆2x ...x 𝑆𝑛 é um 
subconjunto de 𝑆1 x 𝑆2x ...x 𝑆𝑛 
 
Exercício 
• Para cada uma das relações binárias ρ a seguir, 
definidas em ℕ, decida quais dos pares ordenados 
pertencem a ρ. 
a) x ρ y ↔ x + y < 7; (1, 3), (2, 5), (3, 3), (4, 4) 
 
b) x ρ y ↔ x = y + 2; (0, 2), (4, 2), (6, 3), (5, 3) 
 
c) x ρ y ↔ 2x + 3y = 10; (5, 0), (2, 2), (3, 1), (1, 3) 
 
d) x ρ y ↔ y é um quadrado perfeito; (1, 1), (4, 2), (3, 9), 
(25, 5) 
Exercício 
• Para cada uma das relações binárias ρ a seguir, 
definidas em ℕ, decida quais dos pares ordenados 
pertencem a ρ. 
a) x ρ y ↔ x + y < 7; (1, 3), (2, 5), (3, 3), (4, 4) 
 
b) x ρ y ↔ x = y + 2; (0, 2), (4, 2), (6, 3), (5, 3) 
 
c) x ρ y ↔ 2x + 3y = 10; (5, 0), (2, 2), (3, 1), (1, 3) 
 
d) x ρ y ↔ y é um quadrado perfeito; (1, 1), (4, 2), (3, 9), 
(25, 5) 
Tipos de Relações 
• Um para um: cada x e cada y aparecem apenas uma 
vez na relação. 
 
• Um para muitos: algum x aparece mais de uma vez. 
 
• Muitos para um: algum y aparece mais de uma vez. 
 
• Muitos para muitos: algum x e algum y aparecem 
mais de uma vez. 
Exercício 
• Diga se cada uma das relações em ℕ a seguir é: um 
para um, um para muitos, muitos para um ou 
muitos para muitos. 
a) ρ = {(1,2), (1,4), (1,6), (2, 3), (4, 3)} 
Muitos para muitos 
b) ρ = {(9, 7), (6, 5), (3,6), (8, 5)} 
Muitos para um 
c) ρ = {(12, 5), (8,4), (6, 3), (7, 12)} 
Um para um 
d) ρ = {(2,7), (8,4), (2,5), (7,6), (10, 1)} 
Um para muitos 
Exercício 
• Diga se cada uma das relações em ℕ a seguir é: um 
para um, um para muitos, muitos para um ou 
muitos para muitos. 
a) ρ = {(1,2), (1,4), (1,6), (2, 3), (4, 3)} 
Muitos para muitos 
b) ρ = {(9, 7), (6, 5), (3,6), (8, 5)} 
Muitos para um 
c) ρ = {(12, 5), (8,4), (6, 3), (7, 12)} 
Um para um 
d) ρ = {(2,7), (8,4), (2,5), (7,6), (10, 1)} 
Um para muitos 
Exercício 
• Diga se cada uma das relações em ℕ a seguir é: um 
para um, um para muitos, muitos para um ou 
muitos para muitos. 
a) ρ = {(1,2), (1,4), (1,6), (2, 3), (4, 3)} 
Muitos para muitos 
b) ρ = {(9, 7), (6, 5), (3,6), (8, 5)} 
Muitos para um 
c) ρ = {(12, 5), (8,4), (6, 3), (7, 12)} 
Um para um 
d) ρ = {(2,7), (8,4), (2,5), (7,6), (10, 1)} 
Um para muitos 
Exercício 
• Diga se cada uma das relações em ℕ a seguir é: um 
para um, um para muitos, muitos para um ou 
muitos para muitos. 
a) ρ = {(1,2), (1,4), (1,6), (2, 3), (4, 3)} 
Muitos para muitos 
b) ρ = {(9, 7), (6, 5), (3,6), (8, 5)} 
Muitos para um 
c) ρ = {(12, 5), (8,4), (6, 3), (7, 12)} 
Um para um 
d) ρ = {(2,7), (8,4), (2,5), (7,6), (10, 1)} 
Um para muitos 
Exercício 
• Diga se cada uma das relações em ℕ a seguir é: um 
para um, um para muitos, muitos para um ou 
muitos para muitos. 
a) ρ = {(1,2), (1,4), (1,6), (2, 3), (4, 3)} 
Muitos para muitos 
b) ρ = {(9, 7), (6, 5), (3,6), (8, 5)} 
Muitos para um 
c) ρ = {(12, 5), (8,4), (6, 3), (7, 12)} 
Um para um 
d) ρ = {(2,7), (8,4), (2,5), (7,6), (10, 1)} 
Um para muitos 
Operações entre Relações 
• Sejam duas relações ρ e σ em S×S. 
• Como as relações são conjuntos, 
podemos definir as operações de 
união, interseção e complemento entre 
relações: 
– x (ρ ∪ σ) y ↔ x ρ y ou x σ y 
– x (ρ ∩ σ) y ↔ x ρ y e x σ y 
– x ρ’ y ↔ não x ρ y 
 
Propriedades de Relações 
• Seja ρ uma relação binária em S. 
• Então ρ pode ser: 
– reflexiva 
– simétrica 
– transitiva 
– anti-simétrica 
Relação Reflexiva 
• Seja ρ uma relação binária em S. 
• ρ é reflexiva se (∀x) (x ∈ S → (x,x) ∈ ρ) 
• Exemplos de relações reflexivas: 
– ρ em ℕ, tal que x ρ y ↔ x = y 
– ρ em ℕ tal que x ρ y ↔ x ≤ y 
 
 
• Lembrete: Todo x está relacionado a si mesmo. 
Relação Simétrica 
• Seja ρ uma relação binária em S. 
• ρ é simétrica se 
– (∀x) (∀y) ((x, y) ∈ ρ → (y, x) ∈ ρ) 
• Exemplos 
– ρ em ℕ, tal que x ρ y ↔ x = y, é simétrica 
– ρ em ℕ, tal que x ρ y ↔ x ≤ y, não é simétrica 
 
• Lembrete: Se x está relacionado a y, então y 
está relacionado a x. 
Relação Transitiva 
• Seja ρ uma relação binária em S. 
• ρ é transitiva se 
– (∀x)(∀y)(∀z) ((x,y) ∈ ρ ∧ (y,z) ∈ ρ → (x,z) ∈ ρ) 
• Exemplos de relações transitivas: 
– ρ em ℕ, tal que x ρ y ↔ x = y 
– ρ em ℕ tal que x ρ y ↔ x ≤ y 
 
• Lembrete: se x está relacionado a y e y está 
relacionado a z, então x está relacionado a z 
Relação Anti-Simétrica 
• Seja ρ uma relação binária em S. 
• ρ é anti-simétrica se 
– (∀x)(∀y) ((x,y) ∈ ρ ∧ (y,x) ∈ ρ → x = y) 
• Exemplo de relação anti-simétrica: 
– ρ em ℕ tal que x ρ y ↔ x ≤ y 
 
 
• Lembrete: se x está relacionado a y e y está 
relacionado a x, então x = y 
Exemplos 
• Uma relação pode ser simétrica e, ao mesmo 
tempo, anti-simétrica? 
– Sim, pode. A relação de igualdade 
• Uma relação pode não ser nem simétrica, nem 
anti-simétrica? 
– ρ = {(1,2), (2,1), (1,3)} em S={1,2,3} 
– ρ não é simétrica, pois (1,3) ∈ ρ, mas (3,1) ∉ ρ 
– ρ não é anti-simétrica, pois (1,2) ∈ ρ e (2,1) ∈ ρ, mas 
1≠2 
 
Exemplos 
• Uma relação pode ser simétrica e, ao mesmo 
tempo, anti-simétrica? 
– Sim, pode. A relação de igualdade 
• Uma relação pode não ser nem simétrica, nem 
anti-simétrica? 
– ρ = {(1,2), (2,1), (1,3)} em S={1,2,3} 
– ρ não é simétrica, pois (1,3) ∈ ρ, mas (3,1) ∉ ρ 
– ρ não é anti-simétrica, pois (1,2) ∈ ρ e (2,1) ∈ ρ, mas 
1≠2 
 
Exemplos 
• Uma relação pode ser simétrica e, ao mesmo 
tempo, anti-simétrica? 
– Sim, pode. A relação de igualdade 
• Uma relação pode não ser nem simétrica,nem 
anti-simétrica? 
– ρ = {(1,2), (2,1), (1,3)} em S={1,2,3} 
– ρ não é simétrica, pois (1,3) ∈ ρ, mas (3,1) ∉ ρ 
– ρ não é anti-simétrica, pois (1,2) ∈ ρ e (2,1) ∈ ρ, mas 
1≠2 
 
Fechos de Relações 
• Se uma relação ρ em um conjunto S não tem 
determinada propriedade, pode ser possível 
estender ρ a uma relação ρ* que tenha essa 
propriedade, tal que ρ ⊆ ρ*. 
• Se ρ* é o menor conjunto com essa 
propriedade, então ele é o fecho de ρ em 
relação a essa propriedade. 
• Podemos procurar o fecho reflexivo, fecho 
simétrico ou o fecho transitivo de uma relação 
em um dado conjunto. 
 
Definição Formal 
• Uma relação binária ρ* em um conjunto S é o 
fecho de uma relação ρ em relação à 
propriedade P se: 
1.ρ* tem a propriedade P; 
2.ρ ⊆ ρ*; 
3.ρ* é subconjunto de qualquer outra 
relação em S que inclua ρ e tenha a 
propriedade P . 
Exemplo 
Seja ρ = {(1,1), (1,2), (1,3), (3,1), (2,3)} uma 
relação em S = {1,2,3}. Determine os fechos 
reflexivo, simétrico e transitivo. 
• Fecho reflexivo é 
‣ {(1,1), (1,2), (1,3), (3,1), (2,3), (2,2), (3,3)} 
• Fecho em relação à simetria é 
‣ {(1,1), (1,2), (1,3), (3,1), (2,3), (2,1), (3,2)} 
• Fecho transitivo é 
‣ {(1,1), (1,2), (1,3), (3,1), (2,3), (3,2), (3,3), (2,1), (2,2)} 
Exemplo 
Seja ρ = {(1,1), (1,2), (1,3), (3,1), (2,3)} uma 
relação em S = {1,2,3}. Determine os fechos 
reflexivo, simétrico e transitivo. 
• Fecho reflexivo é 
‣ {(1,1), (1,2), (1,3), (3,1), (2,3), (2,2), (3,3)} 
• Fecho em relação à simetria é 
‣ {(1,1), (1,2), (1,3), (3,1), (2,3), (2,1), (3,2)} 
• Fecho transitivo é 
‣ {(1,1), (1,2), (1,3), (3,1), (2,3), (3,2), (3,3), (2,1), (2,2)} 
Exemplo 
Seja ρ = {(1,1), (1,2), (1,3), (3,1), (2,3)} uma 
relação em S = {1,2,3}. Determine os fechos 
reflexivo, simétrico e transitivo. 
• Fecho reflexivo é 
‣ {(1,1), (1,2), (1,3), (3,1), (2,3), (2,2), (3,3)} 
• Fecho em relação à simetria é 
‣ {(1,1), (1,2), (1,3), (3,1), (2,3), (2,1), (3,2)} 
• Fecho transitivo é 
‣ {(1,1), (1,2), (1,3), (3,1), (2,3), (3,2), (3,3), (2,1), (2,2)} 
Exemplo 
Seja ρ = {(1,1), (1,2), (1,3), (3,1), (2,3)} uma 
relação em S = {1,2,3}. Determine os fechos 
reflexivo, simétrico e transitivo. 
• Fecho reflexivo é 
‣ {(1,1), (1,2), (1,3), (3,1), (2,3), (2,2), (3,3)} 
• Fecho em relação à simetria é 
‣ {(1,1), (1,2), (1,3), (3,1), (2,3), (2,1), (3,2)} 
• Fecho transitivo é 
‣ {(1,1), (1,2), (1,3), (3,1), (2,3), (3,2), (3,3), (2,1)} 
Exemplo 
Seja ρ = {(1,1), (1,2), (1,3), (3,1), (2,3)} uma 
relação em S = {1,2,3}. Determine os fechos 
reflexivo, simétrico e transitivo. 
• Fecho reflexivo é 
‣ {(1,1), (1,2), (1,3), (3,1), (2,3), (2,2), (3,3)} 
• Fecho em relação à simetria é 
‣ {(1,1), (1,2), (1,3), (3,1), (2,3), (2,1), (3,2)} 
• Fecho transitivo é 
‣ {(1,1), (1,2), (1,3), (3,1), (2,3), (3,2), (3,3), (2,1), (2, 2)} 
Exercício 1 
• Sejam ρ e σ relações binárias em ℕ definidas por 
x ρ y ↔ “x divide y” 
x σ y ↔ 5x ≤ y 
• Decida quais dos pares ordenados satisfazem as 
relações correspondentes: 
 
Exercício 2 
• Classifique as relações binárias a seguir nos 
conjuntos S como: reflexivas, simétricas, 
antissimétricas e transitivas: 
 
 
Resposta 1 
• a. (2, 6), (3, 17), (0, 0) 
• b. (2, 12) 
• c. Nenhum 
• d. (1,1), (4, 8) 
Resposta 2 
• a. Reflexiva, transitiva 
• b. Reflexiva, simétrica, transitiva 
• c. Simétrica