이산수학_관계

7장 관계

학습목표

• 관계의 개념을 이해하고 표현.
• 관계의 성징을 이해하고 판별.
• 여러 관계를 합성하여 새로운 관계의 도출을 유도
• 관계가 특정 설징을 갖도록 만든다.
• 동치관계와 부분순서관계를 이해한다.

1. 관계의 개념

• 관계(Relation) : 집합 A,B가 있을 때 집합 A에서 집합 B로 가는 관계로 A X B의 부분집합
  • 정의역(Domain) : 집합 A에서 집합 B로 가는 이항관계 R에 속한 순서쌍의 첫 번째 원소가 포함되어 있는 집합 ,즉 집합 A
  • 공변역(Codomain) : 집합 A에서 집합 B로 가는 이항관계 R에 속한 순서쌍의 두 번째 원소가 포함되어 있는 집합, 즉 집합 B
  • 치역(Range) : 집합 A에서 집합 B로 가는 관계 R에 속한 순서쌍의 두 번째 원소들을 모아놓은 집합, 즉 공번역의 부분집합 정의역 : 돌을 던지는 사람 , 공번역 : 맞을 수 있는 사람 , 치역 : 맞은 사람
• n항 관계 : 집합 An이 있ㅇ르 때 A1 X A2 X … An의 부분집합 (관계가 이루어지는 집합이 셋 이상일 때)
• 역관계(Inverse Relation): 집합 A에서 집합 B로 가는 관계R이 있을 때 ,R에 대한 역관계
  • 관계 R에서의 정의역이 역관계에서는 공변역이 되고 , 관계 R에서의 공변역이 역관계에서는 정의역이 됨

2. 관계의 표현

• 화살표 선도를 이용한 관계 표기
  • 화살표 선도(Arrow Diagram) : 집합 A에서 집합 B로 가는 관계 R이 있을 때, 두 집합 원소 사이의 관계를
    화살표로 나타내는 방법.
  • 정의역에 해당하는 원소에서 시작하여 순서쌍의 뒤에 있는 공변역에 해당하는 원소로 향하는 화살로 표기.
• 좌표도표를 이용한 관계 표기
  • 좌표도표(Coordinate Diagram) : 집합 A에서 집합 B로 가는 관계 R이 있을 때,
    집합 A의 원소들을 x축, 집합 B의 원소들을 y축에 표시하여 관계 R을 좌표에 나타내는 방법
  • 관계 R에 대한 역관계는 관계 R의 공변역이었던 집합을 가로축으로 ,관계 R의 정의역이었던 집합을
    세로축으로 두어 순서쌍의 만나는 지점에 표시
• 관계행렬을 이용한 관계 표기
  • 관계행렬(Relation Matrix) : 집합 A에서 집합 B로 가는 관계R에 대한 nxm 행렬
  • 관계행렬은 관계 R의 정의역 원소를 행 , 공변역 원소를 열에 나열
  • 관계의 순서쌍에 해당하는 원소를 1로, 그렇지 않으면 0으로 표시
  • 역관계는 전치행렬의 관계가 있다.
• 방향그래프를 이용한 관계 표기
  • 방향그래프(Directed Graph) : 하나의 집합 A에서 집합 A로 가는 관계 R을 꼭짓점과 화살표를 이용해 나타낸 그래프
  • 루프 : 원소에서 시작하여 그 원소로 끝나는 화살표가 그려짐

3. 관계의 성질

• 반사 성질과 관련된 관계
  • 반사관계(Reflexive Relation) : 집합 A에 대한 관계 R이 있을 때, 모든 원소에 대해 자신과 대응하는 순서쌍이 포함하 관계
    • 반사관계에 대한 관계행렬은 대각원소들이 모두 1로 표기된다.
  • 비반사관계(Irreflexive Realtion): 모든 원소에 대해 자신과 대응하는 순서쌍이 포함되어서는 안된다 .(하나라도 존재 하면 안됨)
    • 비반사관계에 대한 관계행렬은 대각원소들이 모두 0으로 표기된다.
• 대칭 성질과 관련된 관계
  • 대칭관계(Symmetric Relation) : 집합 A에 대한 관계 R이 있을 때, (a,b) = (b,a)
    • 대칭관계에 대한 관계행렬은 대각원소들을 기준으로 마주보는 원소들이 같다.
  • 반대칭관계(Asymmetric Relation) : 집합 A에 대한 관계 R이 있을 때 , (a,b) = (b,a)가 하나라도 포함되지 않는경우
    • 반대칭관계에 대한 관계행렬은 마주보는 원소가 서로 달라야 함 서로 0일 수도 있다.
• 추이관계
  • 추이관계(Transitive Relation) : 집합 A에 대한 관계 R이 있을 때, 어떤 a,b,c가 A에 원소이고 a,b가 R의 원소이면서
    b,c가 R의 원소이면 a,c가 R의 원소인 관계

4. 합성관계

• 합성관계의 정의 : 두 개 이상의 관계를 합성하여 새로운 관계를 생성
  • 집합 A에서 집합 B로의 관계 R과 집합 B에서 집합 C로의 관계 S가 있을 때, 관계 R에 대해서 공변역이면서 관계 S에 대해서는 정의역인 집합 B가 있기 때문에 R과S는 합성이 가능하다.
  • 집합 A에서 집합 B로 가는 관계 R과 집합 C에서 집합 B로 가는 관계 S의 경우는 관계 R의 공변역과 관계S의 정의역이 같이 않으므로 합성관계가 성립될 수 없다.
  • 합성관계는 교환법칙이 성립하지 않는다.
• 합성관계의 거듭제곱
  • 집합 A={a1,a2,…am}에서 집합 B={b1,b2,…bn}으로 가는 관계 R은 mxn크기의 관계행렬 MR</h6> 로 작성
  • 집합 B에서 집합 C={c1,c2,…cs}로 가는 관계 S는 nxs크기의 관계행렬 M <h6>s</h6> 로 작성
  • 관계 SㆍR은 이 두 관계행렬 M<h6>R</h6>과 M<h6>s</h6>의 부울곱으로 구함
    • SㆍR = M<h6>s</h6> 。M<h6>R</h6> = M<h6>R</h6> ⊙ M<h6>s</h6>
• _추이관계와 거듭제곱의 관계_
  • 기수가 n인 집합 A에 대한 관계 R이 추이관계인 필요충분조건은 모든 양의 정수 n에 대하여 Rn이 R의 부분집합이다.
  • 즉 집합 A에 대한 관계행렬의 모든 n에 대해 R^n이 다시 R의 부분집합이면 R은 추이관계이다.

5. 관계의 폐포

• 폐포의 정의: 원래의 관계에 순서쌍 원소를 추가하여 특정 설징에 맞게 만든 것
  1. 반사폐포
  2. 대칭폐포
  3. 추이폐포
• 반사폐포 : 집합 A에 대해 관계 R을 포함하면서 반사관계를 갖는 관계 S
  • 반사관계는 주대각 원소가 모두 1이기 때문에 관계행렬을 그려서 주대각 원소가 1이 아닌 부분을 추가해주면 된다.
• 대칭폐포 : 집합 A에 대해 관계 R을 포함하면서 대칭관계를 갖는 관계 S
  • 대칭관계는 주대각 원소를 기준으로 마주보는 원소가 갖으므로 관계행렬을 이용하여 부족한 부분을 추가해주면 된다ㅓ.
• 추이폐포 : 집합 A에 대해 관계 R을 포함하면서 추이관계를 갖는 관계 S
  • 관계 R의 추이폐포는 연결관계로 만든다. MR V MR^2 V MR^3 V … MR^n (추이폐포의 관계행렬) _연결관계_ : 원소의 개수가 n인 집합 A에 대한 관계 R에 대하여 R* = R1UR2U…URn

6. 동치관계와 부분순서관계

• 동치관계
  • 동치는 “같다”라는 의미
  • 동치관계라는 것은 집합의 원소들이 “같다”는 것을 의미
  • 동치관계(Equivalence Relation) : 반사관계, 대칭관계, 추이관계가 모두 성립하는 관계
    1. 대각원소가 모두 1이다. → 반사관계
    2. 대각원소를 기준으로 마주보는 값이 같다. → 대칭관계
    3. 연결관계를 이용 모든 R의 모든 원소가 만족 → 추이관계
• 하세도표
  • 방향그래프와 부분순서관계의 성질을 이용하여 표기하는 방식
  • 루프를 생략하며 , 각각 원소들이 속하는 관계를 쌓아올려 최대/최소/극대/극소를 구할 수 있다.

• 이산수학
• 관계