명동 스터디_이산수학_5(관계)

명동 스터디 : 기초를 숙련한지 너무 오래되어 컴퓨터공학부 커리큘럼의 필수 과목과 관련된 공부를 통해 기초를 숙련하고 숙련된 기초를 통해 프로젝트 진행을 하기 위한 4명의 스터디 모임

 

기원 : ki-w0n.tistory.com

백범 : https://long-shift-6b9.notion.site/dbf9ea3ec9fd49379e43c127e470123a

찬형 : https://memo.chanhyung.kim/407d7b36c9204fb3813a42eac8674897

병묵 : https://manso98.notion.site/23723aa1c0bb44828b52fc57efa6639e

 

명동 스터디 첫번째 커리큘럼 일정(2024.07.29 ~2024.11.16)

- 컴퓨터 과학 기초(07.09 ~ 07.21)
- 이산수학(07.29 ~ 08.17)

- 자료 구조(08.19 ~ 09.07)

- 컴퓨터 구조(09.09 ~ 10.12)

- DB(10.07 ~ 10.26)
- 네트워크(10.28 ~ 11.16)

 

목차

 

---

---

관계의 개념

다음 그림과 같은 자료 집합이 존재하고, 각 집합의 정보들은 중복되지 않으며 수업 정보, 학생 정보, 교수 정보는 각각의 데이터를 갖기도 하지만 연관 관계를 갖기도 한다. 전자전공의 박교수는 2학년의 김학생의 담당 교수일수도 있고, 통신전공의 정보통신개론 수업을 듣는 1학년 최학생이 될 수도 있다. 이러한 관계는 데이터베이스를 효율적으로 사용하고 자료들을 중복없이 통합된 집합으로 구조화 할 수 있다.

 

 

이항관계

집합 A와 B가 있을때, 집합 A->B로 가는 관계로 R을 A X B의 부분 집합

R:={(a,b)|a∈A,b∈B}⊆A×B

 

위 그림에서 A를 정의역(Domain) B를 공역(Codomain)이라고 합니다.

치역(Range) = {b∈B|(a,b)∈R}로 집합 A에서 집합 B로가는 이항관계 R에 속한 함수의 모든 출력값의 집합입니다.

 

관계의 표현

이러한 관계는 위의 그림처럼 화살표 도표 뿐 아니라 좌표 도표, 방향 그래프, 관계 행렬 등을 표현이 가능합니다.

 

---

 

관계의 성질

반사관계

모든 a∈A에 대해 (a,a)∈R(=aRa)

비반사관계

모든 a∈A에 대해 (a,a)∉R(=aRa)

 

대칭관계

어떤 a,b∈A에 대하여 (a,b)∈R이면 (b,a)∈R인 관계

 

반대칭관계

어떤 a,b∈A에 대하여 (a,b)∈R일 때 a = b이고, a ≠ b이면 (b,a)∉R인 관계

 

관계의 합성

R : A<->B, S : B<->C라고 할때 R과 S를 합성관계라고 합니다.

 

동치/부분 순서 관계

• 동치 관계
  반사성, 대칭성, 추이성을 모두 가지는 관계를 동치 관계라고 합니다.
  - 반사성: (a,a)∈R
  - 대칭성: (a,b)∈R\then(b,a)∈R
  - 추이성: (a,b)∈R∧(b,c)∈R\then(a,c)∈R
  
• 부분 순서 관계
  반사성, 반대칭성, 추이성을 갖는 관계를 부분 순서 관계라고 합니다.
  - 반사관계 : ∀x∈N, x≤x
  - 반대칭관계 : ∀x,y∈N, x≤y∧y≤x\thenx=y
  - 추이관계 : x,y,z∈N, x≤y∧y≤x\thenx≤z