thumb|200px|Relação binária thumb|200px|Relação bináriaNa matemática e na lógica, uma relação binária ou 2-ária é uma relação entre dois elementos, sendo um conjunto de pares ordenados. As relações binárias são comuns em muitas áreas da matemática para definir conceitos como, por exemplo: "é múltiplo" e "maior que" da aritmética; "é congruente" da geometria; e outros.
uma Função (matemática) é um tipo especial de relação binária.
As relações binárias são utilizadas em vários campos da Matemática e na Ciência da computação.
Definição
Uma relação binária é uma comparação entre dois objetos tomados em uma ordem definida. Os objetos podem estar ou não relacionados de acordo com alguma regra. Toda relação é um conjunto de pares ordenados onde o primeiro elemento pertence ao conjunto de partida, e o segundo elemento pertence ao conjunto de chegada.
Uma relação binária r sobre dois conjuntos A e B é:
Em outras palavras, uma relação binária é definida como sendo um subconjunto do produto cartesiano entre os conjuntos A e conjunto B. Isto é, uma relação R é um conjunto de pares ordenados. Um subconjunto de A x A pode ser chamado simplesmente de relação binária em A.
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 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.
O domínio de uma relação R é o conjunto de todos os primeiros elementos de um par ordenado que pertence a R. A imagem de R é o conjunto dos segundos elementos. No caso descrito acima, o domínio é um subconjunto de A e a imagem é um subconjunto de B.
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 1Rx, 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 δ.
Endorrelação Se R é uma relação de um conjunto A para si mesmo, do tipo R : A → A, então dizemos que R é uma “endorrelação” ou “auto-relação”. Considerando o mesmo conjunto A e a mesma relação R : A → A, podemos escrever a endorrelação como ⟨A, R⟩, sendo esta outra forma de notação.
Podemos tomar como exemplos de endorrelações, as relações abaixo:
Se A = {0, 1, 2}, a relação “menor que” de A em A será R = {(0, 1), (0, 2), (1, 2)}. Se B = {1, 2}, a relação R = {(x,y) BB | x + y = ímpar} será R = {(1, 2), (2, 1)}. Se C = {a, b}, a relação ⟨C, =⟩ será um conjunto R = {(a, a), (b, b)}. Se D = {1, 2, 3}, a relação D D será um conjunto R = {(1, 1), (2, 1), (2, 2), (3, 1), (3, 2), (3, 3)}.
Grafos O grafo é um ramo importante da matemática discreta (ver Teoria dos grafos). Podemos observar os grafos de maneira clara a partir de endorrelações. Dessa maneira, toda relação R: A A pode ser representada como um grafo com arestas ligando cada par ordenado (a,b) com origem em a destino em b. Assim:
Cada elemento do conjunto A é representado por um vértice do grafo. Cada par ordenado (a,b) no grafo é representado por uma aresta (setas) de a para b.
miniaturadaimagem|Figura 1 Tomemos como exemplo o primeiro exemplo dado em endorrelações. Se A = {0, 1, 2}, a relação “menor que” de A em A será R = {(0, 1), (0, 2), (1, 2)}. Logo, teremos um grafo configurado da seguinte maneira (ver figura 1).
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:
ou seja, P = {(2,0), (1, 1), (0, 2)}, P(0,2) é verdadeiro, já P(-1,3) é falso;
As relações de igualdade e diferença: a = a e b ? c; 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
Ou seja, todo elemento de A se relaciona com algum de B.
Relação sobrejetora
É o inverso da total, todo elemento de B é relacionado com algum de A.
Relação funcional
Ou seja, um elemento de A não pode se relacionar com mais de um elemento de B.
Relação injetora:
O contrário da funcional: um elemento de B não pode ser relacionado com dois ou mais elementos de A diferentes.
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.
Se existir um isomorfismo entre dois conjuntos, podemos chamá-los de “conjuntos isomorfos”.
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 é,
Por exemplo, a inversa da relação R = {(1, y), (1, z), (3, y)} é a seguinte: R−1 = {(y, 1), (z, 1), (y, 3)}.
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 Se considerarmos A, B e C conjuntos e as relações R: A B e S: B C, a composição de R e S (que pode ser denotada por RS: A C) será tal que (a A)(b B)(c C)[aRb bSc a(RS)c]. Ou seja, composição de R e S será um conjunto RS tal que os pares ordenados de RS serão pares (a,c) desde que a esteja relacionado com b e b esteja relacionado com c.
A melhor maneira de observarmos uma composição de relações é através do diagrama de setas ou de matrizes. miniaturadaimagem|Figura 2 Tomemos como exemplo os conjuntos A = {1,2,3,4}, B = {a,b,c,d} e C = {x, y, z} e as relações R = {(1, a), (2, d), (3, a), (3, b), (3, d)} de A para B e S = {(b, x), (b,z), (c, y), (d,z)} de B para C. A composição de R e S será, com o auxílio do diagrama de setas (ver figura 2) RS = {(3, x), (3,z), (2,z)}.
Matricialmente teremos a matriz de R como sendo = e a matriz de S como sendo =. A relação RS será a multiplicação entre as matrizes. Logo x=
Propriedades das relações binárias
Dada uma relação binária R sobre um conjunto A.
Considere a serviço de exemplo as seguintes cinco relações em um conjunto A = { 1, 2, 3, 4}:
R1 = {(1,1), (1,2), (2,3), (1,3), (4,4)}; R2 = {(1,1), (1,2), (2,1), (2,2), (3,3), (4,4)}; R3 = {(1,3), (2,1)}; R4 = ∅, a relação vazia; R5 = A×A, a relação universal.
Reflexividade
A relação R é dita reflexiva se todos os elementos se relacionam com si próprios.
Uma relação é irreflexiva se nenhum elemento se relaciona com si próprio.
Exemplos: A relação "ter o mesmo pai que" é reflexiva (pois todo mundo é filho de seu próprio pai). A relação "ser irmão de" é irreflexiva (pois ninguém é irmão de si próprio).
Dos exemplos citados, como A contém os quatro elementos, 1, 2, 3 e 4, uma relação R em A é reflexiva se contém os quatro pares (1,1), (2.2), (3.3), (4,4). Portanto, apenas R2 e a relação universal R5 são reflexivas. Note que R1 , R3 e R4 não são reflexivas, uma vez que, por exemplo, (2,2) não pertence a nenhuma delas.
Formalmente, a relação R é dita reflexiva se aRa para todo a ∈ A, isto é, se (a,a) ∈ R para todo a ∈ A.
Em um conjunto finito com n elementos existem 2n² relações binárias, das quais 2n²-n são reflexivas.
A matriz de uma relação reflexiva: a diagonal principal contém somente o valor verdadeiro (1). Grafo de uma relação reflexiva: em cada vértice do grafo deve haver um laço, Na matriz de uma relação irreflexiva a diagonal principal contém apenas o valor falso (0). Grafo de uma relação irreflexiva: em nenhum vértice do grafo pode haver um laço.
Simetria
Relação binária simétrica Uma relação binária é simétrica se a relação de a com b implica a relação de b com a.
Exemplo: A relação "a é irmão de b" é simétrica, pois, se a é irmão de b, então b é irmão de a.
Formalmente, uma relação binária é simétrica se qualquer aRb implica bRa. Em um conjunto finito com n elementos, há relações simétricas.
R1 não é simétrica já que (1,2) ∈ R1 mas (2,1) ∉ R1. R3 não é simétrica já que (1,3) ∈ R3 mas (3,1) ∉ R3 . As outras relações são simétricas.
Matriz de uma relação simétrica: a matriz é simétrica (MR = MT R ). Grafo de uma relação simétrica: entre dois vértices quaisquer, ou não existe aresta, ou existem duas arestas, uma em cada sentido
Relação binária anti-simétrica Uma relação anti-simétrica é tal que se aRb e bRa então a=b.
R2 não é anti-simétrica, já que (1,2) e (2,1) pertencem a R2 , mas 1 ≠ 2.
A matriz de uma relação anti-simétrica para qualquer célula verdadeira (1) em uma das metades da matriz, em relação à diagonal, a correspondente célula na outra metade é falsa (0). Grafo de uma relação anti-simétrica: entre dois vértices quaisquer, não há arestas nos dois sentidos.
Relação binária assimétrica Assimétrica é uma relação em que aRb implica que não bRa.
Analogamente, a relação universal R5 não é anti-simétrica. Todas as outras são anti-simétricas.
Note que as propriedades de simetria e anti-simetria não são mutuamente excludentes. Por exemplo, a relação R = {(1,3), (3,1), (2,3)} não é nem simétrica nem anti-simétrica. Por outro lado, a relação R' = {(1,1), (2,2)} é simétrica e anti-simétrica. Uma relação R que é simétrica e anti-simétrica ao mesmo tempo tem a propriedade que se xRy então x = y. Em um conjunto finito com n elementos existem apenas dessa relação.
Transitividade
Em uma relação transitiva, se a implica b, e b implica c, então a implica c.
Exemplo: Se a é irmão de b, e b é irmão de c, então a é irmão de c.
Formalmente, uma relação é dita transitiva se aRb e bRc implicam aRc. Se a relação for antitransitiva então aRb e bRc implicam que não é verdade aRc.
A relação R3 não é transitiva porque (2,1) e (1,3) ∈ R3, mas (2,3) ∉ R3 . Todas as outras relações são transitivas.
A propriedade de transitividade também pode ser expressa em termos da composição de relações. Para uma relação R em A, definimos R² = R⋅R e, mais geralmente, Rn = Rn-1⋅R, para n inteiro maior do que 1.
Teorema: a relação R é transitiva se e somente se , Rn ⊆ R para n ≥ 1.
Uma matriz de uma relação transitiva: matricialmente não se verifica nenhuma estrutura específica. Grafo de uma relação transitiva: sempre que uma aresta ligar um vértice A a um vértice B e o vértice B a um vértice C, então deve haver uma aresta de A para C.
Algumas outras propriedades
Relação total (ou linear, ou completa): para todo a e b em A é verdade que aRb ou bRa (ou ambos). Relação euclidiana: para todo a, b e c em A, é verdade que se aRb e aRc então bRc. Relação extensível (ou serial): para todo a em A, existe um b em A tal que aRb ou bRa. "Maior que” é uma relação extensível nos inteiros. Mas não é um relação extensível nos inteiros positivos, porque não existe um x nos inteiros positivos tal que 1>x.