Uma relação binária r sobre dois universos A e B é:
Suponha que R é uma relação de A para B. Então R é um conjunto de pares ordenados onde cada primeiro elemento pertence a A e cada segundo elemento pertence a B. Isto é, para cada par (a,b), a ∈ A e b ∈ B. Então exatamente uma das seguintes afirmativas é verdadeira:
- (a,b) ∈ R: dizemos que “a é R-relacionado a b”, escrevendo aRb.
- (a,b)
∈R: dizemos que “a não é R-relacionado a b”, escrevendo aRb.
Exemplos:
- Sejam A = {1, 2, 3} e B = { x, y, z} , e seja R = {(1,y), (1,z), (3,y)}. Então R é uma relação de A para B, uma vez que R é um subconjunto de A x B. Com respeito a esta relação, 1Ry, 1Rz, 3Ry, mas 1
Rx, 2Rx, 2Ry, 2Rz, 3Rx, 3Rz. O domínio de R é {1.3} e a imagem é {y.z}.
- Seja A um conjunto qualquer. Uma relação importante em A é a relação de igualdade, {(a,a); a ∈ A}, que é usualmente denotada por =. Essa relação é também chamada de identidade ou relação diagonal em A e será também denotado por δ.
Outra definição
Uma relação binária R também pode ser definida como um trio ordenado (A, B, G) onde A e B são conjuntos arbitrários, e G é um subconjunto do produto cartesiano A×B. Os conjuntos A e B são chamados de domínio e codomínio da relação, respectivamente, e G é chamado de grafo.A Relação final corresponde a visualizar R como uma Função indicadora do conjunto de pares G. A ordem de cada par de G é importante: se a ? b, então aRb pode ser verdadeiro ou falso independentemente de bRa o ser.
Exemplos
- Numa relação P definida por:
- Suponha que existam 4 objetos: {carro, bola, boneca, bala} e quatro pessoas {João, Maria, Marcos, Pedro}.
- Suponha que João tem a bola, Maria tem a boneca, e Pedro tem o carro. Ninguém tem a bala e Marcos não tem nada.
- Então a relação binária R "pertence a" é dada como R = ({bola, carro, boneca, bala}, {João, Maria, Marcos, Pedro}, {(bola, João), (boneca, Maria), (carro, Pedro)}).
Tipos de relações binárias
Dada uma relação R ⊆ A×B, podemos classificá-la como:- Relação total
- Relação sobrejetora
- Relação funcional
- Relação injetora:
Uma relação é dita um monomorfismo se ela é total e injetora. Uma relação é dita um epimorfismo se ela é funcional e sobrejetora. Uma relação é dita um isomorfismo se ela é um monomorfismo e um epimorfismo.
Operações em relações binárias
Relações inversas
Seja R uma relação qualquer A×B. A inversa de R, denotada por R−1, é a relação de B×A consiste nos pares ordenados que, quando têm sua ordem revertida, pertencem a R, isto é,
Claramente, (R−1)−1 = R. Além disso o domínio e a imagem de R−1 são, respectivamente, iguais à imagem e ao domínio de R. Ademais, se R é uma relação em A, então R−1 também é uma relação em A.
Composição de relações
Relacionar elementos de A com elementos de B é destacar um subconjunto de AxB. Dadas R1 ⊆ A×B e R2 ⊆ B×C:A composição das relações R1 com R2, denotado por R2 ⋅ R1, é a relação
{(a,c): (∃b ∈B), com (a,b) ∈ R1 e (b,c) ∈ R2} ⊆ A×C
Exemplo: Sejam os conjuntos
A = {a, b, c}; B = {c, d, e} e C = {a, e}; e as relações R1 = {(a,c), (a,e), (b,c), (c,d)} e R2 = {(c,a), (d,a), (d,e), (e,e)}.
Então R2 ⋅ R1 = {(a,a), (a,e), (b,a), (c,a). (c,e)}.
Composição de Relações e Matrizes
Existe uma outra maneira de determinar R ⋅ S. Sejam Mr e Ms, respectivamente, as matrizes da relação R e S. Então,
Teorema: Sejam A, B, C e D conjuntos. Suponha que R é uma relação A×B, S é uma relação de B×C e T é uma relação de C×D. Então, (R ⋅ S) ⋅ T = R ⋅ (S ⋅ T). Ou seja, a composição de relações é associativa.
Prova: Para demonstrar o teorema é necessário mostrar que cada par ordenado em (R ⋅ S) ⋅ T pertence a R ⋅ (S ⋅ T) e vice-versa. Então:
Suponha que (a,d) pertence a (R ⋅ S) ⋅ T. Então, existe um c em C tal que (a,c) ∈ (R ⋅ S) e (c,d) ∈ T. Como (a,c) ∈ (R ⋅ S), existe b em B tal que (a,b) ∈ R e (b,c) ∈ S. Como (b,c) ∈ S e (c,d) ∈ T, temos (b,d) ∈ (S ⋅ T); como (a,b) ∈ R e (b,d) e S ⋅ T, temos (a,b) ∈ R ⋅ (S ⋅ T). Portanto, (R ⋅ S) ⋅ T ⊆ R ⋅ (S ⋅ T). De modo similar, R ⋅ (S ⋅ T)⊆ (R ⋅ S) ⋅ T. Ambas as inclusões provam que (R ⋅ S) ⋅ T = R ⋅ (S ⋅ T).
