방송대 방통대 이산수학 6강 - 관계 - 요약 노트 시험족보 예상문제 - 올에이클래스

이산수학 6강 - 관계

곱집합의 부분집합으로 정의되는 관계의 의미를 이해하고, 순서쌍으로 주어진 관계를 화살표 도표·방향그래프·부울행렬로 표현하는 방법을 학습한다. 반사적·대칭적·추이적 성질을 판별한 뒤 역관계, 합성관계, 동치관계와 동치류까지 체계적으로 정리한다.

1. 곱집합과 관계의 정의

곱집합

집합 A와 B의 곱집합(Cartesian product) A×B는 A의 원소를 첫 번째 성분으로, B의 원소를 두 번째 성분으로 갖는 모든 순서쌍의 집합이다.

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

순서쌍에서는 성분의 위치가 중요하다. 일반적으로 (a,b)와 (b,a)는 서로 다르며, 따라서 A×B와 B×A도 보통 같지 않다. 관계는 이 곱집합 안에서 특정 조건을 만족하는 순서쌍만 골라 만든다.

이항관계

집합 X에서 집합 Y로의 이항관계(binary relation) R은 곱집합 X×Y의 부분집합이다. 즉 R⊆X×Y이다. (x,y)∈R이면 “x는 y와 R의 관계가 있다”라고 읽고 xRy로도 표기한다.

출발 집합과 도착 집합이 같아 X=Y이면 R을 X에서의 관계라고 한다. 이 경우 R⊆X×X이며, 관계의 반사성·대칭성·추이성을 논할 수 있다.

X에서 Y로의 관계는 X×Y의 부분집합이고, X에서의 관계는 X×X의 부분집합이다.

2. 관계를 순서쌍으로 나타내기

수강관계의 사례

학생 집합 X={민수, 영수, 영이, 소담}과 과목 집합 Y={C언어, 알고리즘, 그래픽스, 네트워크}가 있다고 하자. 어떤 학생이 어떤 과목을 수강하는지를 관계 R로 나타내면, 표에서 표시된 학생과 과목의 조합을 순서쌍으로 나열할 수 있다.

R={(민수,C언어), (민수,알고리즘), (민수,그래픽스), (영수,알고리즘), (영수,네트워크), (영이,알고리즘), (영이,그래픽스), (소담,C언어), (소담,그래픽스), (소담,네트워크)}

각 순서쌍의 첫 성분은 반드시 학생 집합에서, 둘째 성분은 과목 집합에서 선택된다. 관계는 가능한 모든 조합이 아니라 실제 수강이라는 조건을 만족하는 조합만 포함한다.

조건으로 정의한 관계

관계를 원소의 나열 대신 조건으로 나타낼 수도 있다. 실수 a와 b에 대하여 b=|a|인 순서쌍들의 관계를 생각하면 (-1,1)∈R이지만 (1,-1)∉R이다. 이를 좌표평면에 나타내면 y=|x|의 그래프가 된다.

관계의 포함 여부는 순서쌍이 관계의 정의 조건을 만족하는지로 판단한다. 두 성분의 순서를 바꾸면 조건이 달라질 수 있으므로 반드시 순서를 확인해야 한다.

3. 화살표 도표

표현 원리

화살표 도표는 출발 집합 X와 도착 집합 Y를 따로 표시하고, (x,y)∈R일 때 x에서 y로 화살표를 그린다. 어떤 원소들이 관계를 맺는지 직관적으로 확인할 수 있는 표현이다.

강의의 예에서 A={1,2,3,4}, B={-1,0,1,2}이다. 관계 R이 y>x를 만족하는 순서쌍이라면 가능한 화살표는 1→2 하나이다. S={(x,y)∈A×B | x=y}라면 두 집합에 공통으로 있는 1과 2에서 각각 같은 값으로 화살표가 연결된다.

T={(3,0),(2,0),(1,0)}이라면 A의 1, 2, 3에서 B의 0으로 화살표 세 개를 그린다. 순서쌍을 하나씩 읽어 첫 성분을 출발점, 둘째 성분을 도착점으로 대응시키면 된다.

화살표 도표를 읽는 방법

1. 출발 집합과 도착 집합의 원소를 구분하여 배치한다.
2. 관계에 포함된 각 순서쌍 (x,y)를 확인한다.
3. 첫 성분 x에서 둘째 성분 y로 화살표를 긋는다.
4. 화살표가 없는 조합은 관계에 포함되지 않는다.

4. 방향그래프

그래프와 방향그래프

그래프(graph)는 꼭지점(vertex)과 변(edge)으로 이루어진 도형이며 G=(V,E)로 나타낸다. 변이 방향을 가지면 방향그래프(directed graph), 방향을 가지지 않으면 무향그래프라고 한다.

한 집합 X에서의 관계 R는 방향그래프로 표현할 수 있다. 집합의 각 원소를 꼭지점으로 놓고 (x,y)∈R이면 x에서 y로 향하는 변을 그린다. (x,x)처럼 두 성분이 같으면 해당 꼭지점에서 출발해 자기 자신으로 돌아오는 고리 형태가 된다.

방향그래프의 예

A={1,2,3}이고 T={(1,1),(1,2),(2,1),(2,2),(3,1),(3,2)}라면 꼭지점은 1, 2, 3이다. 1과 2에는 각각 자기 자신으로 향하는 고리가 있고, 1과 2 사이에는 양방향 변이 있다. 또한 3에서 1과 2로 향하는 변이 있지만 반대 방향의 순서쌍이 없으면 1이나 2에서 3으로 향하는 변은 그리지 않는다.

방향그래프의 화살표 x→y는 정확히 순서쌍 (x,y)가 관계에 포함됨을 뜻한다. 반대 방향 y→x의 존재 여부는 별도로 확인해야 한다.

5. 부울행렬로 표현한 관계

부울행렬의 구성

X={x₁,x₂,…,xₘ}, Y={y₁,y₂,…,yₙ}일 때 X에서 Y로의 관계 R은 m×n 부울행렬 MR=[aij]로 나타낼 수 있다.

(xᵢ,yⱼ)∈R이면 aij=1, 포함되지 않으면 aij=0으로 둔다. 행은 출발 집합의 원소, 열은 도착 집합의 원소에 대응한다.

부울행렬의 예

A={1,2,3}, T={(1,1),(1,2),(2,1),(2,2),(3,1),(3,2)}이면 다음과 같다.

행 원소	열 1	열 2	열 3
1	1	1	0
2	1	1	0
3	1	1	0

예를 들어 첫째 행 셋째 열이 0인 것은 (1,3)∉T임을 뜻한다. 셋째 행 둘째 열이 1인 것은 (3,2)∈T임을 뜻한다. 순서쌍, 화살표, 행렬 원소는 모두 같은 관계 정보를 서로 다른 형태로 표현한다.

6. 관계의 반사적·대칭적·추이적 성질

반사적 관계

집합 A에서의 관계 R이 반사적(reflexive)이라는 것은 모든 a∈A에 대해 (a,a)∈R이라는 뜻이다. 방향그래프에서는 모든 꼭지점에 자기 고리가 있어야 한다. 단 하나의 원소라도 자기 자신과 관계를 맺지 않으면 반사적이지 않다.

대칭적 관계

대칭적(symmetric)이라는 것은 모든 a,b∈A에 대해 (a,b)∈R이면 반드시 (b,a)∈R인 성질이다. 방향그래프에서 서로 다른 두 꼭지점 사이에 한 방향의 화살표가 있으면 반대 방향 화살표도 있어야 한다. 자기 고리는 대칭성에 어긋나지 않는다.

추이적 관계

추이적(transitive)이라는 것은 (a,b)∈R이고 (b,c)∈R이면 (a,c)∈R인 성질이다. 즉 a에서 b를 거쳐 c에 도달하는 두 단계의 연결이 있으면 a에서 c로 직접 연결되는 관계도 있어야 한다.

성질	순서쌍 조건	방향그래프에서의 확인
반사적	모든 a에 대해 (a,a)∈R	모든 꼭지점에 자기 고리가 있음
대칭적	(a,b)∈R ⇒ (b,a)∈R	모든 화살표에 반대 방향 화살표가 있음
추이적	(a,b),(b,c)∈R ⇒ (a,c)∈R	길이 2의 연결마다 직접 연결도 있음

세 성질은 서로 독립적으로 판별한다. 반사적이면서 대칭적이지만 추이적이지 않을 수도 있고, 추이적이면서 반사적·대칭적이지 않을 수도 있다.

7. 부울행렬로 관계의 성질 판별하기

반사성과 주대각선

집합 A에서의 관계를 나타내는 부울행렬에서 (a,a)는 주대각선 원소에 해당한다. 따라서 관계가 반사적이려면 주대각선의 모든 원소가 1이어야 한다. 주대각선에 0이 하나라도 있으면 그 원소가 자기 자신과 관계를 맺지 않으므로 반사적이지 않다.

대칭성과 대칭행렬

(a,b)와 (b,a)는 부울행렬에서 주대각선을 기준으로 서로 마주 보는 위치에 놓인다. 관계가 대칭적일 필요충분조건은 관계행렬이 대칭행렬인 것이다. 즉 MR=MRT여야 한다.

추이성과 부울곱

부울행렬에서 두 단계 경로의 존재 여부는 관계행렬의 부울곱으로 확인한다. MR⊙MR에서 1이 된 위치는 어떤 중간 원소를 거쳐 연결되는 순서쌍을 뜻한다. 이 모든 위치가 원래 MR에서도 1이어야 관계가 추이적이다.

따라서 추이성은 MR⊙MR의 모든 1이 MR의 1에 포함되는지로 판단할 수 있다. 두 단계 연결이 있는데 직접 연결이 빠진 위치가 하나라도 있으면 추이적이지 않다.

강의 예제의 판별

A={1,2,3,4}에서 R={(1,1),(2,2),(3,3)}은 4의 자기 순서쌍이 없으므로 반사적이지 않지만 대칭적이고 추이적이다. S={(1,1),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}는 반사적·대칭적이지 않지만 추이적이다. T={(1,4),(2,3),(3,2),(4,1)}는 대칭적이지만 반사적·추이적이지 않다.

행렬에서는 주대각선으로 반사성, 전치행렬과의 일치로 대칭성, 부울제곱의 1이 원래 행렬에 포함되는지로 추이성을 판별한다.

8. 역관계

역관계의 정의

R이 집합 X에서 Y로의 관계일 때 역관계(inverse relation) R-1은 원래 관계의 모든 순서쌍에서 두 성분의 순서를 바꾼 관계이다.

R-1={(y,x) | (x,y)∈R} ⊆ Y×X

따라서 출발 집합과 도착 집합의 역할도 서로 바뀐다. 화살표 도표나 방향그래프에서는 모든 화살표의 방향을 반대로 바꾸는 것과 같다. 부울행렬에서는 행과 열을 바꾸므로 역관계의 행렬은 원래 관계행렬의 전치행렬이 된다.

역관계 구하기

A={1,2,3,4}, B={0,1,2,3}이고 R={(x,y) | y=x-1}이면 R={(1,0),(2,1),(3,2),(4,3)}이다. 각 순서쌍의 성분을 바꾸면 다음과 같다.

R-1={(0,1),(1,2),(2,3),(3,4)}

또 S={(1,2),(2,3),(3,0),(4,1)}이면 S-1={(2,1),(3,2),(0,3),(1,4)}이다.

9. 합성관계

합성관계의 정의

R이 A에서 B로의 관계이고 S가 B에서 C로의 관계라고 하자. 합성관계(composition relation) S∘R은 중간 원소 b∈B가 존재하여 (a,b)∈R이고 (b,c)∈S가 되는 모든 (a,c)의 집합이다.

S∘R={(a,c) | (a,b)∈R이고 (b,c)∈S인 b∈B가 존재}

표기 S∘R에서는 오른쪽의 R을 먼저 따라가고 그다음 S를 따라간다. 결과는 A에서 C로의 관계이며 S∘R⊆A×C이다.

순서쌍을 이용한 합성

A={a,b,c}, B={1,2,3}, C={x,y,z}이고 R={(a,1),(b,3),(c,1)}, S={(1,x),(2,y),(3,z)}라고 하자. a와 c는 R을 통해 1에 연결되고 1은 S를 통해 x에 연결된다. b는 3을 거쳐 z에 연결된다.

S∘R={(a,x),(b,z),(c,x)}

실수 관계 R={(a,b) | b=a+1}, S={(b,c) | c=b-5}에서는 중간값 b를 대입하면 c=(a+1)-5=a-4이므로 S∘R={(a,c) | c=a-4}이다.

부울행렬에 의한 합성

유한집합의 크기가 각각 |A|=m, |B|=n, |C|=p라면 MR은 m×n, MS는 n×p, MS∘R은 m×p 부울행렬이다. 합성관계의 행렬은 다음 부울곱으로 구한다.

MS∘R=MR⊙MS

합성의 순서는 매우 중요하다. S∘R은 R을 먼저 적용한 뒤 S를 적용하며, 행렬도 그 순서에 맞춰 MR과 MS를 부울곱한다.

10. 동치관계

동치관계의 세 조건

집합 A에서의 관계 R이 반사적이고, 대칭적이며, 추이적이면 동치관계(equivalence relation)라고 한다. 세 조건을 모두 만족해야 하며 하나라도 빠지면 동치관계가 아니다.

실수에서의 상등관계 =는 동치관계이다. 모든 실수 a에 대해 a=a이므로 반사적이고, a=b이면 b=a이므로 대칭적이다. 또한 a=b이고 b=c이면 a=c이므로 추이적이다.

동치관계가 아닌 사례

A={0,1,2,3}에서 작거나 같음 관계 ≤는 반사적이고 추이적이지만 대칭적이지 않다. 예를 들어 0≤1이라고 해서 1≤0인 것은 아니다. 따라서 ≤는 동치관계가 아니다.

정수에서 같은 나머지를 갖는 관계는 동치관계의 대표적인 사례이다. 예를 들어 a≡b (mod 3)는 a와 b를 3으로 나눈 나머지가 같다는 뜻이며 반사성, 대칭성, 추이성을 만족한다.

동치관계 = 반사적 + 대칭적 + 추이적이다. 반사적이고 추이적인 순서관계라도 대칭성이 없으면 동치관계가 아니다.

11. 동치류

동치류의 정의

R이 집합 A에서의 동치관계일 때, 원소 a∈A의 동치류(equivalence class) [a]는 a와 관계를 맺는 모든 원소의 집합이다.

[a]={x∈A | (a,x)∈R}

동치관계로 서로 연결된 원소들은 같은 동치류에 속한다. 같은 동치류에 속한 두 원소를 대표로 선택하면 두 동치류는 동일하고, 서로 다른 동치류는 원소를 공유하지 않는다.

동치류 구하기

A={0,1,2}이고 R={(0,0),(1,1),(1,2),(2,1),(2,2)}라고 하자. 이 관계는 반사적이고 대칭적이며 추이적이므로 동치관계이다.

[0]={0}
[1]={1,2}
[2]={1,2}

[1]과 [2]는 같은 집합이므로 서로 다른 동치류는 {0}과 {1,2} 두 개이다. 관계행렬에서는 서로 같은 동치류에 속한 원소들이 서로 모두 연결된 블록 형태로 나타난다.

12. 핵심 개념 정리

• 곱집합 A×B는 a∈A, b∈B인 모든 순서쌍 (a,b)의 집합이다.
• X에서 Y로의 관계 R은 X×Y의 부분집합이며, (x,y)∈R을 xRy로도 쓴다.
• 관계는 화살표 도표, 방향그래프, 부울행렬로 표현할 수 있다.
• 부울행렬에서는 관계에 포함된 순서쌍의 위치를 1, 포함되지 않은 위치를 0으로 나타낸다.
• 반사적 관계는 모든 (a,a)를 포함하고, 대칭적 관계는 (a,b)와 함께 (b,a)를 포함하며, 추이적 관계는 두 단계 연결에 대응하는 직접 연결을 포함한다.
• 역관계는 모든 순서쌍의 성분을 바꾸며, 그 행렬은 원래 관계행렬의 전치행렬이다.
• S∘R은 R을 먼저 적용하고 S를 적용하며, 행렬은 MR⊙MS로 구한다.
• 동치관계는 반사적·대칭적·추이적인 관계이고, 동치류 [a]는 a와 관계를 맺는 모든 원소의 집합이다.

관계 문제는 먼저 순서쌍의 출발과 도착을 확인하고, 이를 그래프나 행렬로 정확히 바꾼 뒤 필요한 성질을 판별하는 순서로 접근한다. 특히 반사성의 주대각선, 대칭성의 전치, 추이성의 두 단계 경로, 합성의 적용 순서를 구분하는 것이 핵심이다.

13. 예상문제 20선

1. 집합 X에서 집합 Y로의 관계 R에 대한 설명으로 옳은 것은?

① R=X×Y여야 한다. ② R은 Y×X의 원소이다. ③ R⊆X×Y이다. ④ X와 Y는 반드시 같은 집합이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
X에서 Y로의 이항관계는 곱집합 X×Y의 부분집합이다.

2. A={1,2}, B={a,b,c}일 때 A×B의 원소 개수는?

① 6개 ② 5개 ③ 3개 ④ 2개

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
첫 성분은 2가지, 둘째 성분은 3가지이므로 순서쌍은 2×3=6개이다.

3. 관계 R={(a,1),(b,2)}의 화살표 도표를 그리는 방법으로 옳은 것은?

① 1에서 a, 2에서 b로만 그린다. ② a와 b 사이에만 화살표를 그린다. ③ 모든 가능한 원소 쌍에 화살표를 그린다. ④ a→1과 b→2를 그린다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
순서쌍의 첫 성분이 출발점, 둘째 성분이 도착점이므로 각각 a→1, b→2가 된다.

4. 방향그래프에서 꼭지점 2에 자기 고리가 있다는 의미는?

① (1,2)가 관계에 포함된다. ② (2,2)가 관계에 포함된다. ③ 모든 원소가 2와 관계를 맺는다. ④ 2는 관계의 원소가 아니다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
자기 고리는 한 꼭지점에서 출발해 같은 꼭지점으로 돌아오므로 순서쌍 (2,2)를 나타낸다.

5. 부울행렬 MR에서 a23=1이 뜻하는 것은?

① (x₃,y₂)∉R ② (x₂,y₃)∈R ③ x₂=y₃가 항상 성립한다. ④ 관계의 원소가 23개이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
행 번호는 출발 원소, 열 번호는 도착 원소를 나타내며 값 1은 해당 순서쌍이 관계에 포함됨을 뜻한다.

6. 집합 A={1,2,3}에서 관계 R이 반사적이기 위한 조건은?

① (1,2),(2,3),(3,1)만 포함한다. ② 관계의 모든 순서쌍에서 두 성분이 달라야 한다. ③ 하나 이상의 자기 순서쌍만 포함하면 된다. ④ (1,1),(2,2),(3,3)을 모두 포함한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
반사적 관계는 집합의 모든 원소 a에 대해 (a,a)를 포함해야 한다.

7. 대칭적 관계에 대한 설명으로 옳은 것은?

① (a,b)∈R이면 (b,a)∈R이다. ② 모든 원소 a에 대해 (a,a)∈R이다. ③ (a,b),(b,c)∈R이면 (a,c)∈R이다. ④ 모든 순서쌍의 첫 성분과 둘째 성분이 같다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
대칭성은 관계에 있는 모든 순서쌍에 대해 성분을 바꾼 순서쌍도 관계에 포함되는 성질이다.

8. 관계 R={(1,2),(2,3)}가 추이적이 되기 위해 반드시 추가해야 할 순서쌍은?

① (2,1) ② (3,2) ③ (1,3) ④ (3,1)

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
1에서 2로, 2에서 3으로 연결되므로 추이성을 만족하려면 1에서 3으로의 직접 관계가 필요하다.

9. 부울행렬로 나타낸 관계가 대칭적일 필요충분조건은?

① 모든 원소가 1이다. ② 주대각선만 모두 1이다. ③ 행렬의 부울제곱이 영행렬이다. ④ MR=MRT이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
대칭 관계에서는 (a,b)와 (b,a)의 포함 여부가 같으므로 관계행렬이 전치행렬과 일치한다.

10. 부울행렬에서 관계가 반사적인지 확인하는 방법은?

① 주대각선 원소가 모두 1인지 확인한다. ② 첫째 행 원소가 모두 0인지 확인한다. ③ 행과 열의 순서를 반대로 바꾼다. ④ 행렬의 모든 행이 서로 다른지 확인한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
주대각선 원소는 각 (a,a)의 포함 여부를 나타내므로 모두 1이어야 반사적이다.

11. R={(1,a),(2,b)}일 때 역관계 R-1은?

① {(1,b),(2,a)} ② {(a,1),(b,2)} ③ {(2,b),(1,a)} ④ {(a,2),(b,1)}

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
역관계는 원래 관계의 각 순서쌍에서 첫 성분과 둘째 성분을 서로 바꾼다.

12. 역관계의 부울행렬에 대한 설명으로 옳은 것은?

① 원래 행렬의 모든 0을 1로 바꾼다. ② 원래 행렬을 자기 자신과 부울곱한다. ③ 원래 관계행렬의 전치행렬이다. ④ 언제나 원래 행렬과 크기가 같다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
순서쌍의 두 성분을 바꾸면 행과 열의 역할이 바뀌므로 행렬을 전치한 결과가 된다.

13. 합성관계 S∘R의 적용 순서는?

① R을 먼저 적용하고 S를 적용한다. ② S만 적용하고 R은 적용하지 않는다. ③ S와 R을 반드시 동시에 적용한다. ④ S를 먼저 적용하고 R을 적용한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
S∘R은 오른쪽의 관계 R을 따라 중간 원소로 간 뒤 S를 따라가는 관계이다.

14. R={(a,1),(b,2)}, S={(1,x),(2,y)}일 때 S∘R은?

① {(1,a),(2,b)} ② {(x,a),(y,b)} ③ {(a,y),(b,x)} ④ {(a,x),(b,y)}

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
a는 1을 거쳐 x로, b는 2를 거쳐 y로 연결된다.

15. MR이 m×n, MS가 n×p일 때 MS∘R의 크기는?

① n×n ② p×m ③ m×p ④ m×n

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
합성관계는 A에서 C로의 관계이므로 행은 A의 크기 m, 열은 C의 크기 p이다.

16. 동치관계가 반드시 만족해야 하는 성질의 조합은?

① 반사적, 비대칭적, 추이적 ② 반사적, 대칭적, 추이적 ③ 대칭적, 추이적 두 성질만 ④ 반사적 한 성질만

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
동치관계는 반사성, 대칭성, 추이성을 모두 만족하는 관계로 정의한다.

17. 집합 {0,1,2,3}에서 ≤가 동치관계가 아닌 이유는?

① 반사적이지 않기 때문이다. ② 추이적이지 않기 때문이다. ③ 관계가 공집합이기 때문이다. ④ 대칭적이지 않기 때문이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
0≤1이지만 1≤0은 아니므로 대칭성을 만족하지 않는다.

18. 동치류 [a]의 정의로 옳은 것은?

① A에 속하지 않는 모든 원소의 집합 ② {x∈A | (a,x)∈R} ③ {x∈A | (a,x)∉R} ④ 관계 R에 포함된 순서쌍의 개수

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
[a]는 동치관계 R에서 a와 관계를 맺는 집합 A의 모든 원소로 구성된다.

19. A={0,1,2}, R={(0,0),(1,1),(1,2),(2,1),(2,2)}일 때 서로 다른 동치류는?

① {0}과 {1,2} ② {0,1}과 {2} ③ {0,2}과 {1} ④ {0,1,2} 하나뿐이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
[0]={0}이고 [1]=[2]={1,2}이므로 서로 다른 동치류는 두 개이다.

20. 관계의 추이성을 방향그래프에서 판별하는 설명으로 옳은 것은?

① 모든 꼭지점에 자기 고리만 있는지 확인한다. ② 모든 화살표의 반대 방향만 확인한다. ③ 두 단계 경로가 있을 때 같은 출발점과 도착점을 잇는 직접 화살표가 있는지 확인한다. ④ 꼭지점의 개수와 화살표의 개수가 같은지만 확인한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
a→b와 b→c가 있으면 추이성을 위해 a→c도 반드시 있어야 한다.