# Operações e fechos de relações

Matrizes booleanas, composição, potências, fechos e provas com relações.

Página: https://resumos.rgo.pt/cadeiras/md/operacoes-relacoes/

Uma relação finita pode escrever-se como pares, desenhar-se como setas ou guardar-se numa matriz de zeros e uns. Estas representações dizem o mesmo, mas tornam visíveis aspetos diferentes. Assumimos as definições de relação e de quantificadores das duas lições anteriores. A composição procura uma ligação através de um objeto intermédio; o fecho transitivo procura qualquer sequência finita de ligações.

## Domínio ativo, imagem e inversa

Para $R\subseteq A\times B$, $A$ é o domínio declarado e $B$ o contradomínio. O **domínio ativo** e o **contradomínio ativo**, ou imagem da relação, são:

$$
\begin{aligned} \operatorname{dom}(R)&=\{a\in A:\exists b\in B,\ aRb\},\\ \operatorname{rng}(R)&=\{b\in B:\exists a\in A,\ aRb\}. \end{aligned}
$$

Com $A=\{1,2,3\}$, $B=\{a,b,c\}$ e $R=\{(1,a),(1,b),(2,b)\}$, temos $\operatorname{dom}(R)=\{1,2\}$ e $\operatorname{rng}(R)=\{a,b\}$.

A inversa troca os elementos de cada par: $R^{-1}=\{(b,a):aRb\}$. Não pressupõe que $R$ seja uma função. A identidade é $\operatorname{id}_A=\{(a,a):a\in A\}$.

União, interseção e diferença tratam as relações como conjuntos de pares. O complemento de $R$ depende do produto declarado: $\overline R=(A\times B)\setminus R$. A restrição a $A'\times B'$ é $R\cap(A'\times B')$.

## Matrizes booleanas

Ordena primeiro os elementos de $A$ e $B$. Na matriz $M_R$, a linha identifica a origem e a coluna identifica o destino:

$$
M_R[i,j]=\begin{cases}1,&a_iRb_j,\\0,&\text{caso contrário.}\end{cases}
$$

A inversa corresponde à transposta. Numa relação sobre um só conjunto:

*   Reflexividade exige 1 em toda a diagonal.
*   Irreflexividade exige 0 em toda a diagonal.
*   Simetria exige $M[i,j]=M[j,i]$.
*   Antissimetria impede que $M[i,j]$ e $M[j,i]$ sejam ambos 1 quando $i\ne j$. Podem ser ambos 0.

No exemplo abaixo, começa com $1R2$ e $2R3$. Falta $1R3$ para haver transitividade. Liga esse par, depois acrescenta a diagonal para obter uma ordem parcial. Se ligares também $3R1$, aparecem novas exigências de transitividade.

## Composição

Com $A=\{1,2\}$, $B=\{x,y\}$, $C=\{p\}$, sejam $R=\{(1,x),(2,y)\}$ e $S=\{(x,p),(y,p)\}$. A sequência $1RxSp$ liga 1 a $p$ através de $x$; $2RySp$ liga 2 a $p$ através de $y$. Logo, $S\circ R=\{(1,p),(2,p)\}$.

![Composição S após R: 1 liga a x e 2 liga a y por R; x e y ligam a p por S; setas tracejadas de 1 e 2 para p.](https://resumos.rgo.pt/cadeiras/md/operacoes-relacoes/figura-1.svg)

As setas tracejadas são os pares obtidos; não são uma terceira relação usada como passo intermédio. A definição generaliza a procura de uma testemunha:

Se $R\subseteq A\times B$ e $S\subseteq B\times C$, então:

$$
S\circ R=R;S =\{(a,c):\exists b\in B,\ aRb\land bSc\}.
$$

Na escrita $S\circ R$, aplicamos primeiro $R$. Na escrita $R;S$, seguimos a ordem da esquerda para a direita. Confirma qual é a notação do enunciado.

Com $R=\{(1,a),(1,b),(2,b)\}$ e $S=\{(a,x),(b,x),(b,y)\}$:

$$
S\circ R=\{(1,x),(1,y),(2,x),(2,y)\}.
$$

O par $(1,x)$ tem duas testemunhas, $a$ e $b$, mas só aparece uma vez no conjunto. É a existência de uma ligação que conta, não o número de percursos.

O produto de matrizes é **booleano**: multiplicação passa a $\land$ e soma passa a $\lor$:

$$
M_{S\circ R}[i,k] =\bigvee_j(M_R[i,j]\land M_S[j,k]).
$$

A ordem matricial é $M_R$ seguida de $M_S$, porque as linhas são origens. Um produto aritmético pode contar percursos; para recuperar a relação, reduz os valores positivos a 1.

A composição é associativa, mas não é em geral comutativa. As identidades têm de ter o conjunto certo: $R\circ\operatorname{id}_A=R=\operatorname{id}_B\circ R$.

## Potências e transitividade

Para uma relação sobre $A$, $R^1=R$ e $R^{n+1}=R^n\circ R$. Podemos definir $R^0=\operatorname{id}_A$. O par $(a,b)$ pertence a $R^n$ se há uma sequência de **exatamente $n$ ligações** de $a$ a $b$.

Se $R=\{(1,2),(2,3),(3,4)\}$:

$$
R^2=\{(1,3),(2,4)\},\qquad R^3=\{(1,4)\},\qquad R^4=\emptyset.
$$

Uma relação é transitiva se e só se $R^2\subseteq R$. O quadrado contém precisamente os pares exigidos pela definição de transitividade.

A interseção de duas relações transitivas é transitiva: uma cadeia de dois pares na interseção pertence a ambas, e cada uma contém o par final. A união pode falhar: $\{(1,2)\}$ e $\{(2,3)\}$ são transitivas, mas a sua união não contém $(1,3)$.

## Fechos

Um **fecho** é a menor relação que contém $R$ e satisfaz a propriedade pretendida. Acrescentamos pares, não retiramos os pares iniciais.

$$
\begin{aligned} R_{\mathrm{ref}}&=R\cup\operatorname{id}_A,\\ R_{\mathrm{sim}}&=R\cup R^{-1},\\ R^+&=\bigcup_{n\ge1}R^n,\\ R^*&=\operatorname{id}_A\cup R^+. \end{aligned}
$$

$R^+$ é o fecho transitivo. $R^*$ é o fecho reflexivo e transitivo. Um ciclo pode colocar pares da diagonal em $R^+$: se $1R2$ e $2R1$, então $(1,1)\in R^2$. Não excluas automaticamente os laços do fecho transitivo.

Na relação inicial da matriz interativa, $R=\{(1,2),(2,3)\}$, há só um par a acrescentar:

| Estado | Pares presentes |
| --- | --- |
| Inicial | $(1,2),$ $(2,3)$ |
| Transitivo | $(1,2),$ $(2,3),$ $(1,3)$ |
| Reflexivo e transitivo | Os anteriores e $(1,1),$ $(2,2),$ $(3,3)$ |

No estado inicial, $1R2R3$ exige $(1,3)$, que ainda falta. Nos outros dois estados, nenhuma cadeia exige um par ausente.

O segundo estado é $R^+$: é transitivo e qualquer relação transitiva que contenha $R$ tem de conter $(1,3)$. O terceiro é $R^*$. Acrescentar a diagonal conserva transitividade, porque uma passagem por um laço não exige um destino novo.

Se $A$ tem $N$ elementos, basta unir $R^1,\ldots,R^N$. Um percurso mais longo repete vértices e pode encurtar-se. Para chegar do vértice a ele próprio com pelo menos uma ligação, pode ser preciso um ciclo de comprimento $N$; por isso não substituímos sempre o limite por $N-1$.

### Calcular o fecho de uma relação finita

No código, `M[i][j]` começa por indicar se o par $(A[i],A[j])$ pertence a $R$. Em cada passagem escolhemos um intermédio `A[k]`: se já podemos ir de `A[i]` a `A[k]` e daí a `A[j]`, acrescentamos a ligação de `A[i]` a `A[j]`. Depois de considerar todos os intermédios, a matriz representa $R^+$.

A relação inicial é a cadeia $1R2R3$ da tabela. Acrescenta `[3, 1]` à lista `R`, obtendo o ciclo do exercício «Um fecho transitivo deixa de ser antissimétrico». Antes de executar, prevê quais os pares novos, incluindo a diagonal. A saída identifica também um par de elementos distintos ligado nas duas direções, caso a antissimetria falhe.

**main.js**

```javascript
const A = [1, 2, 3];
const R = [
  [1, 2],
  [2, 3],
];

// Começamos só com R, sem acrescentar a diagonal.
const M = A.map((a) => A.map((b) => R.some(([x, y]) => x === a && y === b)));
for (let k = 0; k < A.length; k++) {
  for (let i = 0; i < A.length; i++) {
    for (let j = 0; j < A.length; j++) {
      M[i][j] = M[i][j] || (M[i][k] && M[k][j]);
    }
  }
}

const pares = [];
let opostos = null;
for (let i = 0; i < A.length; i++) {
  for (let j = 0; j < A.length; j++) {
    if (M[i][j]) pares.push(`(${A[i]},${A[j]})`);
    if (i < j && M[i][j] && M[j][i] && opostos === null) {
      opostos = [A[i], A[j]];
    }
  }
}
console.log(`R+ = {${pares.join(', ')}}`);
if (opostos === null) {
  console.log('Fecho antissimétrico: sim.');
} else {
  const [a, b] = opostos;
  console.log(`Fecho antissimétrico: não; (${a},${b}) e (${b},${a}).`);
}
```

Na cadeia, o único par novo é $(1,3)$ e não há pares opostos entre elementos distintos. No ciclo, qualquer vértice chega aos outros e regressa a si próprio, por isso aparecem os nove pares de $A\times A$. Os laços surgem pelos percursos, não por se ter acrescentado a identidade no início. O cálculo verifica esta relação finita; a justificação por caminhos explica por que o resultado é esse.

## Provar uma equivalência a partir de operações

Suponhamos que $R$ é total, $R^{-1}\subseteq R$ e $R^2\subseteq R$. **Total** significa aqui que cada $a\in A$ tem pelo menos um $b$ com $aRb$.

A inclusão $R^{-1}\subseteq R$ dá simetria: de $aRb$, temos $(b,a)\in R^{-1}$ e portanto $bRa$. $R^2\subseteq R$ dá transitividade.

Para reflexividade, escolhe um $a$ arbitrário. Pela totalidade existe $b$ com $aRb$; pela simetria, $bRa$; pela transitividade, $aRa$. Assim, $R$ é uma equivalência. Sem a totalidade, $R=\emptyset$ num conjunto não vazio satisfaria as outras condições e não seria reflexiva.

## Exercícios

Compor na ordem indicada

Em $A=\{1,2,3\}$, sejam $R=\{(1,2),(2,3)\}$ e $S=\{(2,1),(3,2)\}$. Calcula $S\circ R$ e $R\circ S$.

Pista

Em $S\circ R$, começa numa aresta de $R$ e continua numa de $S$.

Mais uma pista

As cadeias para $S\circ R$ são $1R2S1$ e $2R3S2$.

Solução

$S\circ R=\{(1,1),(2,2)\}$. Na outra ordem, as cadeias são $2S1R2$ e $3S2R3$, logo $R\circ S=\{(2,2),(3,3)\}$. A composição não é comutativa.

Confere a tua resposta:

*   Apliquei primeiro a relação da direita.
*   Listei os intermediários possíveis.
*   Obtive dois resultados diferentes.

Erros frequentes

Escrever o mesmo resultado nas duas ordens ignora quais são os elementos intermédios.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/operacoes-relacoes/#composi%C3%A7%C3%A3o)

Um fecho transitivo deixa de ser antissimétrico

Em $A=\{1,2,3\}$, $R=\{(1,2),(2,3),(3,1)\}$ é antissimétrica? E o seu fecho transitivo? Justifica.

Pista

Antissimetria só proíbe pares opostos entre elementos distintos.

Mais uma pista

No ciclo dirigido, percorre uma, duas ou três arestas.

Solução

$R$ é antissimétrica: não contém um par $(a,b)$ e o seu inverso para $a\ne b$. O ciclo permite chegar de qualquer vértice a qualquer outro e regressar à origem. Assim $R^+=A\times A$, que contém $(1,2)$ e $(2,1)$, logo não é antissimétrica.

No [cálculo do fecho finito](https://resumos.rgo.pt/cadeiras/md/operacoes-relacoes/#calcular-o-fecho-de-uma-rela%C3%A7%C3%A3o-finita), acrescenta `[3, 1]` à cadeia inicial. Confere os nove pares previstos pela justificação, depois retira essa aresta e explica por que desaparecem os laços.

Confere a tua resposta:

*   Conferi pares nas duas direções, não a ausência de laços.
*   Identifiquei caminhos entre quaisquer dois vértices.
*   Concluí que o fecho é A × A e falha antissimetria.

Erros frequentes

Antissimetria não significa ausência de ciclos de comprimento maior que 2. Acrescentar pares pode destruir a propriedade.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/operacoes-relacoes/#pot%C3%AAncias-e-transitividade)

Construir uma relação a partir de uma partição

Em $A=\{1,2,3,4\}$, usa a partição $\{\{1,3\},\{2\},\{4\}\}$ para construir uma equivalência. Lista os pares e calcula $R\circ R$, já definida na lição de operações de relações.

Pista

Dois elementos relacionam-se quando pertencem ao mesmo bloco.

Mais uma pista

Cada bloco $B$ contribui $B\times B$. Para a composição, usa reflexividade e transitividade.

Solução

$R=\{(1,1),(1,3),(3,1),(3,3),(2,2),(4,4)\}$. Pela transitividade, $R\circ R\subseteq R$. Pela reflexividade, qualquer $(a,b)\in R$ pode usar $b$ como intermédio, pois $(b,b)\in R$, logo $R\subseteq R\circ R$. Portanto $R\circ R=R$.

Confere a tua resposta:

*   Incluí os pares dentro de cada bloco.
*   Incluí todos os laços e as duas direções entre 1 e 3.
*   Concluí R composto com R igual a R e justifiquei as inclusões.

Erros frequentes

Não ligues elementos de blocos diferentes e não omitas os blocos com um só elemento.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/operacoes-relacoes/#composi%C3%A7%C3%A3o)

O fecho de uma função pode deixar de ser função

Em $\mathbb N=\{0,1,2,\ldots\}$, seja $R=\{(n,n+1):n\in\mathbb N\}$. É uma função $\mathbb N\to\mathbb N$? Determina $R^2$, a forma de $R^k$ para $k\ge1$ e $R^+$. O fecho continua a ser função? É uma ordem parcial ou uma ordem estrita?

Pista

Separa exatamente k passos de qualquer número positivo de passos. O fecho contém todas as potências, não apenas a primeira.

Solução

A relação inicial é a função sucessor: cada $n$ tem exatamente o destino $n+1$. Não é sobrejetiva porque 0 não é atingido.

$R^2=\{(n,n+2):n\in\mathbb N\}$. Em geral, $R^k=\{(n,n+k):n\in\mathbb N\}$: vale para $k=1$, e compor mais um sucessor acrescenta 1 ao destino. Portanto

$$
R^+=\{(n,m)\in\mathbb N^2:n<m\}.
$$

Uma sequência de $k\ge1$ passos dá $m=n+k>n$. Reciprocamente, para $m>n$ escolhemos $k=m-n$ passos, provando as duas inclusões.

O fecho é total mas não funcional: 0 tem os destinos 1 e 2, entre outros. É irreflexivo e transitivo pela desigualdade estrita, logo é uma ordem estrita total. Não é uma ordem parcial reflexiva, pois nenhum $(n,n)$ pertence ao fecho. Como o domínio é infinito, não usamos um limite finito $|A|$ para unir as potências.

Confere a tua resposta:

*   Determinei R² e a forma de Rⁿ.
*   Provei o fecho usando comprimentos positivos arbitrários.
*   Exibi uma origem com dois destinos no fecho.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/operacoes-relacoes/#pot%C3%AAncias-e-transitividade)