Total
Search
1. 기본사항
1.1. 관계
•
집합 𝑿에서 집합 𝒀로의 (이항)관계 (binary relation)
R은 𝑿 × 𝒀 의 부분집합
•
(𝒙, 𝒚) ∈ 𝑹
⇒ 𝒙는 𝒚와 𝑹의 관계가 있다.
⇒ 𝒙𝑹𝒚로 표기
•
𝑿 = 𝒀이면 𝑹을 𝑿에서의 관계
예제
2. 관계의 표현
2.1. 화살표 도표
•
𝒙 ∈ 𝑿, 𝒚 ∈ 𝒀,
•
(𝒙, 𝒚) ∈ 𝑹
예제
2.2. 방향 그래프
•
그래프 : 점[꼭지점](vertex)과 선[변](edge)으로 이루어진 도형
•
G = (V, E)
•
방향그래프
◦
𝒙, 𝒚 ∈ 𝑿, (𝒙, 𝒚) ∈ 𝑹
예제
2.3. 부울행렬
•
𝑿 = {𝒙𝟏, 𝒙𝟐, ⋯, 𝒙𝒎 }
•
𝒀 = {𝒚𝟏, 𝒚𝟐, ⋯, 𝒚𝒏 }
•
𝒎 × 𝒏 부울행렬 𝑴𝑹 = 𝒂𝒊𝒋
예제
3. 관계의 성질
3.1. 성질의 종류
•
집합 A에서의 관계 R이
◦
반사적
▪
∀𝒂 ∈ 𝑨
▪
(𝒂, 𝒂) ∈ 𝑹
▪
예) (1,1), (2,2), (3,3) …
◦
대칭적
▪
∀𝒂, 𝒃 ∈ 𝑨
▪
𝒂, 𝒃 ∈ 𝑹 ⇒ (𝒃, 𝒂) ∈ 𝑹
◦
추이적
▪
∀𝒂, 𝒃, 𝒄 ∈ 𝑨
▪
((𝒂, 𝒃) ∈ 𝑹 ∧ (𝒃, 𝒄) ∈ 𝑹) ⇒ (𝒂, 𝒄) ∈ 𝑹
예제
3.2. 관계의 성질과 부울행렬
•
반사적
◦
∀𝒂 ∈ 𝑨, (𝒂, 𝒂) ∈ 𝑹
•
대칭적
◦
∀𝒂, 𝒃 ∈ 𝑨, 𝒂, 𝒃 ∈ 𝑹 ⇒ (𝒃, 𝒂) ∈ 𝑹
◦
즉, 대칭행렬
•
추이적
◦
∀𝒂, 𝒃, 𝒄 ∈ 𝑨, ((𝒂, 𝒃) ∈ 𝑹 ∧ (𝒃, 𝒄) ∈ 𝑹) ⇒ (𝒂, 𝒄) ∈ 𝑹
교재 설명
예제
4. 관계의 종류
4.1. 역관계
•
𝑿, 𝒀 ∶집합
•
𝑹 ∶𝑿에서 𝒀로의 관계
•
𝑹^−𝟏 ∶𝑹의 역관계(inverse relation)
•
𝑹^−𝟏 = {(𝒚, 𝒙) | (𝒙, 𝒚) ∈ 𝑹 } ⊂ 𝒀 × 𝑿
•
𝑹의 역관계는 순서만 바꿔주면 됨
예제
4.2. 합성관계
•
𝑨, 𝑩, 𝑪 ∶집합
•
𝑹 ∶𝑨에서 𝑩로의 관계
•
𝑺 ∶𝑩에서 𝑪로의 관계
•
𝑹과 𝐒의 합성관계(composition relation)
◦
𝑺 ∘ 𝑹 = {(𝒂, 𝒄) | 𝒂 ∈ 𝑨, 𝒃 ∈ 𝑩, 𝒄 ∈ 𝑪, (𝒂, 𝒃) ∈ 𝑹, (𝒃, 𝒄) ∈ 𝑺 }
◦
𝑺 ∘ 𝑹 ⊂ 𝑨 x 𝑪 (𝑨에서 𝑪로의 관계)
합성관계 예제
•
합성관계의 부울행렬 표현
◦
𝑨, 𝑩, 𝑪: 유한 집합 (|𝑨| = 𝒎, |𝑩| = 𝒏, |𝑪| = 𝒑)
◦
𝑹 ∶𝑨에서 𝑩로의 관계
◦
𝑺 ∶𝑩에서 𝐂로의 관계
◦
𝑺 ∘ 𝑹 ∶𝑨에서 𝑪로의 관계
▪
𝑴𝑹은 𝒎 × 𝒏 부울행렬,
▪
𝑴𝑺은 𝒏 × 𝒑 부울행렬,
▪
𝑴𝑺∘𝑹은 𝒎 × 𝒑 부울행렬
▪
𝑴𝑺∘𝑹 = 𝑴𝑹 ۨ⨀ 𝑴𝑺
예제
4.3. 동치관계
•
𝑹 ∶집합 𝑨에서 관계
•
𝑹이 반사적, 대칭적, 추이적이면 𝑹을 동치관계라고 부른다.
예제
4.4. 동치류
•
𝑨 ∶집합
•
𝑹 ∶𝑨에서의 동치관계
•
𝑨의 임의의 원소 𝒂에 대해서 [𝒂] = { 𝒙 ∈ 𝑨 | (𝒂, 𝒙) ∈ 𝑹 } 를 𝒂의 동치류라고 함
예제