관계의 합성과 폐포

직접 이동할 수 있는 곳과 여러 번 이동해서 도달할 수 있는 곳은 다릅니다. 관계의 성질을 바탕으로 두 단계 연결과 도달 가능성을 계산합니다.

합성은 중간 대상을 공유한다

R⊆A×B, S⊆B×C일 때 $S\circ R=\{(a,c)\mid\exists b\in B,\ aRb\land bSc\}$로 약속합니다. 오른쪽 R을 먼저 적용하고 왼쪽 S를 다음에 적용합니다. 자료마다 기호 약속이 다를 수 있으므로 문장 'R 다음 S'를 함께 확인합니다.

R={(1,a),(2,a),(2,b)}, S={(a,x),(b,y)}이면 1→a→x로 (1,x), 2→a→x로 (2,x), 2→b→y로 (2,y)를 얻습니다. (1,y)는 1에서 b로 가는 관계가 없어 들어가지 않습니다. $R^{-1}$은 순서쌍의 방향을 뒤집은 역관계이며 함수의 역함수 존재와는 다른 개념입니다.

R 다음 S를 따라 결과 쌍을 만듭니다

시작 원소 1의 R 관계를 찾는다. 중간 원소를 통해 한 쌍을 얻는다. 각 단계의 값과 전환 이유를 비교합니다.

이산수학 · 연결과 계산

R 다음 S를 따라 결과 쌍을 만듭니다

1에서 a로 가는 R과 a에서 x로 가는 S가 이어져 합성 S∘R에 (1,x)가 들어갑니다.

R 다음 S를 따라 결과 쌍을 만듭니다1에서 a로 가는 R과 a에서 x로 가는 S가 이어져 합성 S∘R에 (1,x)가 들어갑니다.

1

R

a

S

x

• 화살표: 순서쌍의 대응

위에서 아래로 R을 먼저, S를 다음에 읽습니다. 합성 결과는 1→x이며 중간 원소 a의 존재가 필요합니다. S∘R의 오른쪽 관계를 먼저 적용합니다.

이 예의 조건

• 본문과 전체 도표의 예를 따라 R에서 연결부터 합성 기록까지 진행합니다.

예의 값과 변화

관찰·상황	값·보충 정보	변화·이유
R에서 연결 시작 원소 1의 R 관계를 찾는다.	값·보충 정보 관계의 쌍 1: (1,a)∈R	변화·이유 중간 원소 a 선택
S에서 연결 같은 a에서 끝 원소를 찾는다.	값·보충 정보 관계의 쌍 1: (a,x)∈S	변화·이유 끝 원소 x 확인
합성 기록 중간 원소를 통해 한 쌍을 얻는다.	값·보충 정보 관계의 쌍 1: (1,x)∈S∘R 관계의 쌍 2: (1,y)는 없음	변화·이유 합성 결과에 (1,x) 기록

R 다음 S를 따라 결과 쌍을 만듭니다

시작 원소 1의 R 관계를 찾는다. 중간 원소를 통해 한 쌍을 얻는다. 각 단계의 값과 전환 이유를 비교합니다.

이산수학 · 연결과 계산

R 다음 S를 따라 결과 쌍을 만듭니다

1에서 a로 가는 R과 a에서 x로 가는 S가 이어져 합성 S∘R에 (1,x)가 들어갑니다.

R 다음 S를 따라 결과 쌍을 만듭니다1에서 a로 가는 R과 a에서 x로 가는 S가 이어져 합성 S∘R에 (1,x)가 들어갑니다.

1

R

a

S

x

• 화살표: 순서쌍의 대응

위에서 아래로 R을 먼저, S를 다음에 읽습니다. 합성 결과는 1→x이며 중간 원소 a의 존재가 필요합니다. S∘R의 오른쪽 관계를 먼저 적용합니다.

이 예의 조건

• 본문과 전체 도표의 예를 따라 R에서 연결부터 합성 기록까지 진행합니다.

예의 값과 변화

관찰·상황	값·보충 정보	변화·이유
R에서 연결 시작 원소 1의 R 관계를 찾는다.	값·보충 정보 관계의 쌍 1: (1,a)∈R	변화·이유 중간 원소 a 선택
S에서 연결 같은 a에서 끝 원소를 찾는다.	값·보충 정보 관계의 쌍 1: (a,x)∈S	변화·이유 끝 원소 x 확인
합성 기록 중간 원소를 통해 한 쌍을 얻는다.	값·보충 정보 관계의 쌍 1: (1,x)∈S∘R 관계의 쌍 2: (1,y)는 없음	변화·이유 합성 결과에 (1,x) 기록

폐포는 필요한 성질을 만족하는 최소 확장

R을 포함하면서 특정 성질을 만족하는 관계 중 가장 작은 관계를 해당 폐포라 합니다. 반사 폐포는 R에 모든 (a,a)를 추가합니다. 대칭 폐포는 $R\cup R^{-1}$입니다. 추이 폐포는 한 번 이상 R을 따라 도달하는 모든 쌍의 집합입니다.

A={1,2,3}, R={(1,2),(2,3)}에서 반사 폐포는 자기 쌍 세 개를 더한 5개이고, 대칭 폐포는 (2,1),(3,2)를 더한 4개입니다. 추이 폐포는 (1,3)을 더한 3개입니다. 추이성은 자기 쌍을 자동으로 요구하지 않습니다. 사이클 1→2→1이 있으면 두 단계로 1→1,2→2가 필요해지는 경우는 별도입니다.

$R^k$를 정확히 k번 이어진 관계라 하면 유한집합의 추이 폐포 $R^+=R\cup R^2\cup\cdots$입니다. 길이 0도 허용하는 반사·추이 폐포 $R^*$에는 모든 항등 쌍도 들어갑니다. '최소'는 원래 쌍을 지우지 않고 필요한 쌍만 추가한다는 뜻입니다.

다음 작은 절차는 추이 폐포를 얻습니다. 이어지는 (a,b),(b,c)가 있으면 (a,c)를 추가하고, 새 쌍이 생기지 않을 때까지 반복합니다. 유한 A에는 쌍이 최대 |A|²개라 이 과정이 종료합니다. 한 차례만 추가하고 끝내면 더 긴 경로를 놓칠 수 있습니다.

스스로 풀어보기

문제 1. A={1,2,3,4}, R={(1,2),(2,3),(3,4)}의 추이 폐포를 구하세요.

힌트: 두 단계와 세 단계 경로를 모두 찾습니다.

풀이: 원래 세 쌍에 (1,3),(2,4),(1,4)를 추가합니다. 최종 6개입니다. (1,4)는 처음 두 단계만 보면 안 보이지만 (1,3),(3,4)에서 필요합니다. 역방향이나 자기 쌍은 요구되지 않습니다.

문제 2. R={(a,b),(b,a)}가 A={a,b,c} 위에 있을 때 $R^+$와 $R^*$의 차이를 설명하세요.

풀이: 사이클 때문에 $R^+$={(a,b),(b,a),(a,a),(b,b)}입니다. c는 한 번 이상 이동할 경로가 없어 (c,c)가 없습니다. $R^*$는 여기에 (c,c)를 더합니다. 길이 0 경로를 허용하는지가 차이입니다.

합성 순서가 헷갈리면 두 화살표를 실제로 따라가세요. 행렬로 폐포를 계산하는 선택 심화는 관계 행렬, 동일 그룹을 만드는 조건은 동치관계에서 이어집니다.