RELAÇÕES BINÁRIAS
•
PARES ORDENADOS
◦ Um PAR ORDENADO, denotado por (x,y), é um par de elementos onde x é o
Primeiro elemento e y é o Segundo elemento do par
◦ A ordem é relevante em um par ordenado
◦ Logo, os conjuntos {a,b} e {b,a} são iguais, mas os pares ordenados (a,b) e
(b,a) são diferentes
◦ A representação de pontos em um plano cartesiano é um exemplo comum de
pares ordenados: o ponto (2,1) é diferente do ponto (1,2)
◦ Os pontos ordenados (x,y) e (z,w) são iguais somente se x = z e y = w
•
PRODUTO CARTESIANO
◦ Sejam A e B subconjuntos do conjunto universo S
◦ O Produto Cartesiano (ou produto cruzado) de A e B, denotado por A X B é o
conjunto definido por:
▪ A X B = { (x,y) | x ∈ A ⋀ y ∈ B }
◦ Ou seja, o Produto Cartesiano A X B é o conjunto de todos os pares ordenados
cujas primeiras coordenadas pertençam ao conjunto A e cujas segundas
coordenadas pertençam ao conjunto B
◦ O Produto Cartesiano NÃO É uma operação binária em P(S)
◦ Ele opera em um par ordenado de membros de P(S) e fornece um resultado
único
◦ O conjunto resultante não é, em geral, um subconjunto de S.
◦ Exemplo:
▪ Sejam S = {1, 2, 3, 4}, A = {1, 2} e B = {3, 4}
▪ P(S) = { ∅, {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}, {1,2,3},
{1,2,4}, {1,3,4}, {2,3,4}, {1,2,3,4} }
▪
A x B = { (1,3), (1,4), (2,3), (2,4) }
•
RELAÇÕES BINÁRIAS
◦ Deteminados pares ordenados de objetos em um conjunto de pares ordenados
se destacam dos demais porque seus elementos satisfazem alguma relação
que os componentes dos demais pares, em geral, não satisfazem.
◦ Exemplos:
▪ Sejam os conjuntos S = {1,2} e T = {2,3}
▪ O produto cartesiano é o conjunto S X T = {(1,2), (1,3), (2,2), (2,3)}
•
Relação de Igualdade:
◦ O conjunto de pares que atende essa relação é unitário, {(2,2)}
•
Relação formada pelos pares com primeiro número menor que o
segundo:
◦ {(1,2), (1,3), (2,3)}
◦
Uma Relação Binária pode ser descrita com palavras ou simplesmente pela
enumeração dos pares ordenados que a satisfazem:
▪ Sejam os conjuntos S = {1,2} e T = {2,3,4}
▪ S X T = { (1,2), (1,3), (1,4), (2,2), (2,3), (2,4) }
▪ Uma relação R definida por: x R y ↔ x = y/2, satisfeita pelos pares (1,2) e
(2,4), poderia também ser definida pela declaração que {(1,2), (2,4)} é o
conjunto dos pares ordenados que satisfazem R
◦
DEFINIÇÃO de Relação Binária
▪ Dados os conjuntos S e T, uma relação binária em S X T é um subconjunto
de S X T, definidos na declaração: x R y ↔ (x,y) ∈ R
▪ A descrição que fornece uma propriedade característica dos elementos da
relação é chamada é chamada de Predicado Binário da relação, a qual é
realizado por certos pares ordenados do produto cartesiano
▪ Sejam os conjuntos S = {1,2} e T = {2,3,4} e a relação binária R dada por:
•
x R y ↔ x + y é ímpar
•
R = {(1,2), (1,4), (2,3)}
◦
Para cada um dos pares ordenados das seguintes relações binárias em ℕ x ℕ,
determine quais dos pares ordeandos pertencem à relação binária R
▪ xRy↔x=y+1
(2,2), (2,3), (3,3), (3,2)
▪ x R y ↔ x divide y
(2,4), (2,5), (2,6)
▪ x R y ↔ x é ímpar
(2,3), (3,4), (4,5), (5,6)
◦
Uma Relação Binária em um conjunto S, também chamada Endorelação ou
Auto-relação, é um subconjunto de S2.
◦
Relação n-ária
▪ Dados os conjuntos S1, S2, ..., Sn. Uma relação n-ária em S1, S2, ..., Sn é
um subconjunto de S1x S2 x ... x Sn
▪ Uma relação n-ária em um conjunto S é um subconjunto de Sn.
◦
TIPOS de Relações Binárias em S x T
▪ Seja R uma relação binária em S x T, então R é um conjunto de pares
ordenados (s,t)
▪ Uma relação é um-para-um (ou INJETIVA, ou BIUNÍVOCA) se cada primeiro
componente s e cada segundo componente t aparecem apenas uma vez na
relação
▪
▪
▪
▪
Uma relação é um-para-vários se algum primeiro componente s aparece
mais de uma vez na relação
Uma relação é vários-para-um (ou UNÍVOCA) se algum segundo
componente t aparece mais de uma vez na relação
Uma relação é vários-para-vários se pelo menos um primeiro componente
s fizer par com mais de um segundo componente t e, pelo menos um
segundo componente t fizer par com mais de um primeiro componente s
◦
OPERAÇÕES sobre Relações Binárias
▪ Podemos realizar as operações de União, Interseção e Complemento de
Relações Binárias em S2 que resultam em novos subconjuntos de S x S, isto
é, novas relações binárias em S2.
•
x (R1 ⋃ R2) y ↔ (x R1 y) ⋁ (x R2 y)
•
x (R1 ⋂ R2) y ↔ (x R1 y) ⋀ (x R1 y)
•
x R' y ↔ Complemento de x R y
▪
◦
Sejam R1 e R2 duas relações binárias em ℕ definidas por:
•
x R1 y ↔ x = y e x R2 y ↔ x < y
•
R1 ⋃ R2 é definida por x (R1 ⋃ R2) y ↔ x ≤ y
•
R1' é definida por x R1 y ↔ x ≠ y
•
R2' é definida por x R2 y ↔ x ≥ y
•
O conjunto definido por R1 ⋂ R2 é ∅
IDENTIDADES das Relações Binárias
▪ Comutativa
•
R1 ⋃ R2 = R2 ⋃ R1
•
R1 ⋂ R2 = R2 ⋂ R1
▪ Associativa
•
(R1 ⋃ R2) ⋃ R3 = R1 ⋃ (R2 ⋃ R3)
•
(R1 ⋂ R2) ⋂ R3 = R1 ⋂ (R2 ⋂ R3)
▪ Distributiva
•
R1 ⋃ (R2 ⋂ R3) = (R1 ⋃ R2) ⋂ (R1 ⋃ R3)
•
R1 ⋂ (R2 ⋃ R3) = (R1 ⋂ R2) ⋃ (R1 ⋂ R3)
▪ Identidade
•
R⋃∅=R
•
R ⋂ S2 = R
▪ Complemento
•
R ⋃ R' = S2
•
R ⋂ R' = ∅
◦
PROPRIEDADES das Relações Binárias
▪ Relações Binárias em um conjunto S podem ter certas propriedades
▪ Seja R uma Relação Binária em S
▪
R é REFLEXIVA se (∀x) ( x ∈ S → (x,x) ∈ R )
•
Exemplo 1: Sejam as relações sobre o conjunto S = {1,2,3,4}
◦ R1= {(1,1), (1,2), (2,1), (2,2), (3,4), (4,1), (4,4)}
◦ R2 = {(1,1), (1,2),(2,1)}
◦ R3 = {(1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1), (4,4)}
◦ R4 = {(2,1), (3,1), (3,2), (4,1), (4,2), (4,3)}
◦ R5 = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,3), (3,4), (4,4)}
◦ R6 = {(3,4)}
◦ As relações R3 e R5 são Reflexivas, as demais não
•
Exemplo 2:
◦ A relação "divide" sobre o conjunto de inteiros positivos é Reflexiva,
pois qualquer inteiro positivo divide a si mesmo e vice-versa
•
Exemplo 3: Sejam as relações sobre o conjunto dos inteiros
◦ R1 = {(a,b) | a ≤ b}
◦ R2 = {(a,b) | a > b}
◦ R3 = {(a,b) | a = b ou a = -b}
◦ R4 = {(a,b) | a = b }
◦ R5 = {(a,b) | a = b + 1}
◦ R6 = {(a,b) | a + b ≤ 3}
◦ As relações R1, R3 e R4 são Reflexivas
▪
R é SIMÉTRICA se
•
(∀x) (∀y) [ ( (x ∈ S) ⋀ (y ∈ S) ⋀ (x,y) ∈ R ) → (y,x) ∈ R ]
•
As relações R2 e R3 do Exemplo 1 acima são Simétricas
•
A relação divide (exemplo 2) é Simétrica, pois para quaisquer inteiros x e
y, se x divide y, então y divide x apenas se x = y
•
As relações R3, R4 e R6 do Exemplo 3 acima são Simétricas (porque?)
▪
R é TRANSITIVA se
(∀x) (∀y) (∀z)
[ ( (x ∈ S) ⋀ (y ∈ S) ⋀ (z ∈ S) ⋀ (x,y) ∈ R ⋀ (y,z) ∈ R ) → (x,z) ∈ R ]
•
A relação ≤ no conjunto dos inteiros é Transitiva: se x≤y e y≤z, então x≤z
•
As relações R4, R5 e R6 do Exemplo 1 acima são Transitivas
•
A relação divide (exemplo 2) é Transitiva porque para quaisquer inteiros
x, y e z, se x divide y e y divide z, então x divide z
•
As relações R1, R2, R3 e R4 do Exemplo 3 acima são Transitivas
▪
▪
R é ANTI-SIMÉTRICA se
•
(∀x) (∀y) [ ( (x ∈ S) ⋀ (y ∈ S) ⋀ (x,y) ∈ R ⋀ (y,x) ∈ R) → y = x ]
•
As relações R4, R5 e R6 do exemplo 1 são Anti-simnétricas
•
As relações R1, R2, R4 e R5 do exemplo 3 são Anti-simétricas
▪
Exemplo 4
•
Seja a relação ≤ no conjunto ℕ.
•
Essa relação é Reflexiva porque para todo elemento de ℕ vai existir um
par (x,x). Ou seja, para qualquer inteiro não negativo x, x ≤ y é
verdadeira.
•
Essa relação é Anti-simétrica porque para todo par (x,y), o par simétrico
(y,x) vai acontecer apenas para x = y. Isto é, para todo elemento x e y de
ℕ, se x ≤ y e y ≤ x, então x = y
•
É uma relação Transitiva porque para todo elemento x, y e z de ℕ, se x
≤ y e y ≤ z, então x ≤ z
•
≤ NÃO é uma relação Simétrica. Não é verdade 2 ≤ 3 não implica 3 ≤ 2
▪
Exemplo 5
•
Seja S = P(ℕ), conjunto das partes dos números naturais
•
Seja uma relação binária ρ em S definida por A ρ B ↔ A ⊆ B
•
ρ É uma relação REFLEXIVA
◦ A relação é formada por todos os pares ordenados para os quais o
predicado binário A ⊆ B é verdadeiro
◦ Como A ⊆ A, para todo conjunto A que pertence a S, então o par
(A, A) pertence à relação ρ
•
ρ NÃO É uma relação SIMÉTRICA
◦ A relação é formada por todos os pares ordenados para os quais o
predicado binário A ⊆ B é verdadeiro, isto é, pares para os quais o
primeiro item é subconjunto do segundo item
◦ O fato de A ⊆ B não implica que B ⊆ A. Isso só é verdadeiro para A=B
•
ρ É uma relação TRANSITIVA
◦ Se os pares (A,B) e (B,C) pertencem naà relação, então o par (B,C)
também pertence, pois se A ⊆ B e B ⊆ C, então A ⊆ C
•
ρ É uma relação ANTI-SIMÉTRICA
◦ Como visto acima, O fato de A ⊆ B e B ⊆ A implica que A = B
▪
Exemplo 6
•
Seja S = {1,2,3}. As afirmações abaixo são verdadeiras:
•
Se uma relação R em S é reflexiva, os pare ordenados (1,2), (2,2) e (3,3)
devem pertencer a R
•
Se uma relação R em S é simétrica, não é possível dizer quais pares
ordenados pertencem à relação. Para uma relação ser simétrica, basta
que para cada par ordenado na relação exista também um par simétrico
•
Se uma relação R em S é simétrica e (a,b) ∈ R, então só podemos
afirmar que o par (b,a) ∈ R
•
Se uma relação R é anti-simétrica, e se (a,b) ∈ R e (b,a) ∈ R, então a=b,
logo podemos afirmar que (a,b) = (b,a)
•
A relação de igualdade (=) em S é simétrica e anti-simétrica:
◦ ∀(x,y) em R existe (y,x) e x = y
◦ Essa é a única relação que tem essas duas propriedades ao mesmo
tempo
◦
▪
Exemplo 7
•
Sejam S = ℕ e a relação binária definida por x R y ↔ x + y é par
•
R é Reflexiva: ∀(x) ∀(y) ∈ ℕ e x = y, x + y é par
•
R é Simétrica: ∀(x) ∀(y) ∈ ℕ, se x + y é par, então y + x é par
•
R é Transitiva: Para que x+y seja par, x e y são ambos pares ou
ímpares.
◦ Se x é par então y é par, logo z deve ser par para que y+z seja par,
então x+z também é par
◦ Se x é ímpar então y é ímpar, logo z deve ser ímpar para que y+z
seja par, então x+z também é par
◦ ∀(x) ∀(y) ∀(z) ∈ ℕ, se x + y é par e y+z é par, então x+z é par,
porque ou x, y e z são todos pares ou são todos ímpares
•
R Não é Anti-simétrica: ∃(x) ∃(y) ∈ ℕ, tal que x + y é par e y + x é par,
mas x ≠ y
(1 + 5 é par, 5 + 1 é par, mas 1 ≠ 5)
▪
Exemplo 8
•
Seja S = {1,2,3}. Seja R definida em S: R = {(1,2), (2,1),(1,3)}
•
R não é simétrica, pois (1,3) ∈ R, mas (3,1) ∉ R
•
R não é anti-simétrica, pois (1,2) ∈ R e (2,1) ∈ R, mas (1 ≠ 2)
▪
Exemplo 9
•
Seja S o conjunto de todas as linhas do plano e a relação binária definida
por x R y ↔ x é paralela a y ou x coincide com y
•
R é Reflexiva: o par (x,x) está presente para todas as retas do plano,
pois x é paralela a x e x coincide com x
•
R é Simétrica:
◦ se (x é paralela a y ou x coincide com y), então (y é paralela a x ou y
coincide com x)
•
R NÃO é Anti-simétrica: existem infinitas retas paralelas e coincidentes
•
R é Transitiva: ∀(x) ∀(y) ∀(z) ∈ S
◦ se (x é paralela a y ou x coincide com y) e (y é paralela a z ou y
coincide com z), então (x é paralela a z ou x coincide com z)
FECHO DE UMA RELAÇÃO (ou Fechamento de uma Relação)
▪ DEFINIÇÃO FORMAL: Uma Relação Binária R* em um Conjunto S é um
Fecho de uma relação R em S com respeito à propriedade P (Transitiva,
Simétrica ou Reflexiva se:
1. R* tem a propriedade P
2. R ⊆ R*
3. R* é um subconjunto de qualquer outra relação em S que inclui R e tem
a propriedade P
▪
▪
▪
A relação S = {1, 2, 3} e R uma relação binária definida pelo conjunto
•
R = {(1,1), (1,2), (1,3), (3,1), (2,3)}
R não é reflexiva, não é simétrica e não é transitiva.
Se uma relação R em um conjunto S não tem uma certa propriedade,
podemos tentar estender R para obter a relação R* em S que tenha a
propriedade.
▪
▪
▪
▪
▪
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
No exemplo acima, o fechamento de R em relação à REFLEXIVIDADE é
•
R* = {(1,1), (1,2), (1,3), (3,1), (2,3), (2,2), (3,3)}
No exemplo acima, o fechamento de R em relação à SIMETRIA é
•
R* = {(1,1), (1,2), (1,3), (3,1), (2,3), (2,1), (3,2)}
No exemplo acima, o fechamento de R em relação à TRANSITIVIDADE é
•
R* = {(1,1), (1,2), (1,3), (3,1), (2,3), (3,2), (3,3), (2,1)}
(passo 1)
•
R*= {(1,1), (1,2), (1,3), (3,1), (2,3), (3,2), (3,3), (2,1), (2,2)} (passo 2)
Essa maneira de determinar o fecho Transitivo de uma relação verificando
os pares ordenados na relação original, incluindo novos pares se
necessário, verificando a relação obtida, incluindo novos pares se
necessário e assim por diante, até obtermos a relação transitiva, é um
método de força bruta. O uso de algoritmos sobre grafos direcionados são
mais eficientes.