방통대 2018-1 이산수학 기말시험 기출문제 풀이 및 해설

36. 다음 내용과 가장 관련이 깊은 것은? (4점)

 

 

“철수와 영희의 나이를 서로 더하면 55이고 철수의 나이에서 영희의 나이를 뺀 값은 5이라면 철수와 영희는 각각 몇 살일까요?” 라는 문제를 풀기 위해 철수와 영희의 나이를 각각 x와 y라고 하고 다음 연립방정식을 만족하는 자연수를 구한다.

x + y = 55
x - y = 5

① 기본
② 방법론
③ 도구
④ 추상화

 

 

정답: 4

해설: 정답은 추상화이다. 추상화는 복잡한 현실 문제를 단순화하여 수학적인 모델로 변환하는 과정을 의미한다. 주어진 문제에서 철수와 영희의 나이를 미지수 x와 y로 표현하고, 이를 바탕으로 연립방정식을 설정한 것은 실제 상황을 수학적 형태로 추상화한 예이다. 다른 선지인 기본, 방법론, 도구는 이 문맥에서 추상화의 정의나 적용과 직접적인 연관이 없다.

 

 

 

37. 다음 중 맞는 명제인 것은? (3점)
① 2x - 6 = 0
② 교실 안이 참 덥다.
③ 해는 동쪽에서 뜬다.
④ 오늘 기말시험 잘 보세요.

 

 

정답: 3

해설: 정답은 3번, 해는 동쪽에서 뜬다이다. 1번 2x - 6 = 0은 방정식으로 정답 여부를 판단할 수 없으며, 2번 교실 안이 참 덥다는 주관적인 느낌을 표현한 것이므로 명제로서의 정확성을 가지지 않는다. 4번 오늘 기말시험 잘 보세요는 바람이나 인사를 나타내는 문장이기 때문에 명제가 아니다. 반면, 3번 해는 동쪽에서 뜬다는 자연 현상을 기술한 객관적인 사실로, 올바른 명제이다.

 

 

 

38. 다음 중 거짓인 명제는? (3점)
① 한국의 수도가 서울이라면, 영국의 수도는 동경이다.
② 물이 섭씨 0도에서 끓는다면, 지구는 달을 공전한다. 
③ 오늘 날씨는 비가 오거나 비가 오지 않는다.
④ 1 + 2 + 3 + 4 = 10

 

 

 

 

정답: 1

해설: 정답은 1번이다. 이 명제는 조건이 참이라면 결론도 참이어야 하나, 한국의 수도는 서울이지만 영국의 수도는 동경이 아니라 런던이므로 거짓이다. 2번 명제는 섭씨 0도에서 물이 끓는다는 가정이 거짓이므로 이 명제의 참 거짓을 따질 필요가 없다. 3번 명제는 비가 오거나 오지 않는다는 항상 참인 명제이다. 4번은 수학적 계산을 통해 확인할 수 있으며, 실제 계산 결과는 10이므로 참이다.

 

 

 

 

39. 명제 p에 대해서 다음 중 항진명제인 것은? (4점)
① p
② p ∨ ~p
③ p ∨ F
④ p ∧ T

 

 

 

 

정답: 2

해설: 정답은 2번이다. 2번 선지인 \( p \lor \neg p \)는 배중률이라는 논리 법칙을 따르는 명제로, p가 참이든 거짓이든 항상 참이 되는 항진명제이다. 1번은 p의 참거짓에 따라 결과가 달라지므로 항진명제가 아니다. 3번 선지 \( p \lor F \)는 F가 거짓을 의미하므로 이 명제는 단순히 p와 같고, p의 참거짓에 따라 달라진다. 4번 선지 \( p \land T \)는 T가 참을 의미하여 이 명제 역시 p와 동일하게 작용하므로 p가 참일 때만 참이 된다. 따라서 항진명제는 2번 뿐이다.

 

 

 

40. 명제함수 \(P(x)\)가 \(x > 2\)이고 \(x\)의 정의역 \(D=\{1, 2, 3\}\) 일 때, \(\forall xP(x)\)와 \(\exists xP(x)\)의 진리값을 순서대로 적은 것은? (3점)
① F, F
② F, T
③ T, F
④ T, T

 

정답: 2

해설: 해설: 명제함수 \(P(x)\)는 \(x > 2\)를 만족해야 참이다. 주어진 정의역 \(D=\{1, 2, 3\}\)에서 \(x > 2\)를 만족하는 \(x\)는 3 하나뿐이다. 따라서, \(\forall xP(x)\) 즉 모든 \(x\)에 대해 \(P(x)\)가 참이어야 하나 1과 2에서 거짓이므로 전체 명제는 거짓이다. 반면, \(\exists xP(x)\)는 적어도 하나의 \(x\)에서 \(P(x)\)가 참이면 되므로, \(x=3\)에서 참이기 때문에 이 명제는 참이다. 결과적으로 진리값은 차례로 F, T 이므로 정답은 2이다.

 

 

 

41. 모든 실수 \(x, y\)에 대해 \(x > y\)이면 \(x^2 > y^2\)에 대한 반례를 보이는 곳은 어느 것인가? (3점)
① \(x = 1\), \(y = 0\)
② \(x = 0\), \(y = 1\)
③ \(x = -1\), \(y = 0\)
④ \(x = 0\), \(y = -1\)

 

 

 

 

정답: 4

해설: 정답은 4번이다. 이 문제에서는 \(x > y\)일 때 \(x^2 > y^2\)가 항상 성립하지 않는 반례를 찾는 것이 목표다. 4번 선지에서 \(x = 0\), \(y = -1\)을 보면 \(x\)가 \(y\)보다 크다는 조건은 만족하지만, \(x^2 = 0^2 = 0\)이고 \(y^2 = (-1)^2 = 1\)이므로 \(x^2 > y^2\)가 성립하지 않는다. 다른 선지들을 살펴보면, 1번과 3번은 \(x^2 > y^2\)가 성립하고, 2번은 \(x > y\)의 조건 자체가 만족되지 않는다. 따라서 4번이 정답인 유일한 반례이다.

 

 

 

42. 다음 정의에서 사용된 증명 방법은 무엇인가? (3점)

 

 

“어떤 수 \(x\)에 \(x\)를 더한 것이 다시 \(x\)이면 \(x\)는 \(0\)이다.”라고 정의한다.
가설은 \(x + x = x\)이고, 결론은 \(x = 0\)이다. 증명을 위하여 \(x + x = x\)이고 \(x \neq 0\)라고 가정하자. 그러면 \(2x = x\)이고 \(x \neq 0\)이다. \(x \neq 0\)이므로 \(2x = x\)의 양변을 나누면 \(2 = 1\)이라는 그릇된 결론을 얻는다. 따라서 \((x + x = x) \Rightarrow (x = 0)\)이다.

① 모순증명법
② 반례증명법
③ 직접증명법
④ 수학적 귀납법

 

 

 

정답: 1

해설: 정답은 모순증명법이다. 이 증명 방법은 일반적으로 가정에서 시작하여 그 가정이 불가능하거나 모순을 일으키는 결과를 이끌어내어 원래의 주장이 참임을 보이는 방식이다. 문제에서는 \(x + x = x\)라는 가정하에 \(x \neq 0\)을 가정했을 때, \(2x = x\)에서 \(2 = 1\)이라는 불가능한 결과를 얻는다. 이러한 불가능한 결과는 \(x \neq 0\)이라는 가정이 틀렸음을 보여주며, 따라서 \(x = 0\)이라는 결론에 도달한다. 반례증명법, 직접증명법, 수학적 귀납법과는 달리, 모순증명법은 원래의 가정을 부정하는 가정에서 출발하여 모순을 찾아내는 것이 특징이다.

 

 

 

43. 집합 A = {a, b}, B = {c, d, e}에 대해 다음 서술 중 부적절한 것은? (3점)
① A와 B는 서로소이다.
② {{c, d}, {e}}는 B의 분할이다.
③ A의 멱집합 P(A)는 P(A) = {{a}, {b}, {a, b}}이다.
④ B의 멱집합 P(B)는 원소가 2^|B| = 2^3 = 8개이다.

 

 

 

 

정답: 3

해설: 정답 3번은 잘못되었다. 집합 A의 멱집합 P(A)는 모든 부분집합을 포함해야 한다. 올바른 P(A)는 공집합을 포함한 {∅, {a}, {b}, {a, b}}이다. 선지에서는 공집합을 누락하고 있어 부적절하다. 다른 선지들은 올바른 사실을 나타낸다. ①번에서 집합 A와 B는 공통 원소가 없으므로 서로소이다. ②번에서 주어진 {{c, d}, {e}}는 B의 모든 원소를 포함하고 있으며, 중복되지 않으므로 B의 올바른 분할이다. ④번에서 B의 멱집합은 원소의 수가 2의 |B| 제곱이므로, 2^3 = 8개가 맞다.

 

 

 

44. 전체집합 U = {1, 2, 3, 4, 5}와 U의 부분집합 A와 B가 각각 A = {1, 2, 3}, B = {2, 3, 4}일 때 다음 서술 중 옳은 것은? (4점)
① A ∪ B = {2, 3}
② A ∩ B = {1, 2, 3, 4}
③ A^c = {4}
④ A ⊕ B = {1, 4}

 

 

 

정답: 4

해설: 정답 4번은 집합 A와 B의 대칭차집합, 즉 A ⊕ B = (A - B) ∪ (B - A)를 의미한다. 여기서 A - B = {1}, B - A = {4}이므로, A ⊕ B = {1, 4}이다. 이는 선택지 4번과 일치한다. 다른 선택지에 대해서, ① A ∪ B는 A와 B의 합집합으로 {1, 2, 3, 4}가 맞으며 ② A ∩ B는 A와 B의 교집합으로 {2, 3}이 올바르고, ③ A^c는 A의 여집합이므로 U에서 A의 원소를 제외한 {4, 5}이다. 따라서 4번만 정확한 진술이다.

 

 

 

45. U가 전체집합이고 A, B, C가 U의 부분집합이라고 할 때 다음 중 옳은 것은? (4점)
① A∪(A∩B)=A
② (A^c)^c = A^c
③ A∩A^c=U
④ A∪(B∩C^c)=(A∪B)∩C^c

 

 

 

 

정답: 1

해설: 정답은 ①이다. 이는 집합의 기본 법칙 중 하나로, A와 (A∩B)의 합집합은 A 자체와 같다. 왜냐하면 A∩B는 A에 속하는 원소 중 B에도 속하는 원소들의 집합이므로, A에 이미 포함된 원소들만을 다시 포함하기 때문이다. 다른 선택지를 살펴보면, ②는 (A^c)^c가 A이어야 하지만 A^c로 잘못 표현되었고, ③에서 A∩A^c는 공집합이며 U가 아니며, ④는 합집합과 교집합의 분배 법칙에 의해 성립하지 않는다.

 

 

 

46. 다음 행렬 A를 나타내는 용어로서 부적절한 것은? (3점)
A = 
\begin{bmatrix}
5 & 0 & 0 \\
0 & 5 & 0 \\
0 & 0 & 5
\end{bmatrix}

① 대칭행렬
② 단위행렬
③ 스칼라행렬
④ 상삼각행렬

 

 

 

정답: 2

해설: 정답은 2번 단위행렬이다. 단위행렬은 주대각선의 모든 요소가 1이고 그 외의 요소는 0인 행렬을 의미한다. 행렬 A는 모든 주대각선 요소가 5이므로 단위행렬이 아니다. 1번 대칭행렬은 주대각선을 기준으로 대칭인 행렬로, 행렬 A가 이에 해당한다. 3번 스칼라행렬은 주대각선 상의 모든 요소가 동일하고 그 외 요소가 0인 행렬이며, 행렬 A는 이에 해당한다. 4번 상삼각행렬은 주대각선 이하의 모든 요소가 0인 행렬로, 행렬 A 역시 이 조건을 만족한다.

 

 

 

 

47. 다음 행렬 A와 B에 대해서 옳은 것은?

 

A = 
\begin{bmatrix}
1 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 1
\end{bmatrix}

 

 

B = 
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}

 

 

1) A + B = 2A

2) A - B = O

3) AB = A

4) B^T = A

 

 

정답: 3

해설: 해설: 행렬 A와 B의 곱 AB를 계산하면, 각각의 행렬의 행과 열을 곱하여 원소별로 더하는 연산을 통해 결괏값을 얻는다. B는 단위행렬이므로, 이를 A와 곱할 때 B의 각 열이 A의 각 행에 해당하는 원소와 곱해지게 되며, 이는 A의 각 원소가 그대로 유지된다는 것을 의미한다. 따라서 AB = A가 성립한다. 다른 선지를 살펴보면, A + B = 2A와 A - B = O는 두 행렬의 원소를 더하거나 빼보면 쉽게 성립하지 않음을 확인할 수 있다. 또한 B의 전치행렬 B^T는 B와 같으므로 A와는 다르다.

 

 

 

* (48~50) 다음은 집합 A = {1,2,3} 에서의 관계 R을 방향 그래프로 나타낸 것이다. 물음에 답하시오. 

 

 

 

 

48. 관계 R을 순서쌍의 집합으로 나타낸 것은? 

1) R = {  (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,3) }

2) R = { (1,1), (1,2), (2,1), (2,2), (3,1), (3,2) ,(3,3) }

3) R = { (1,1), (1,2), (1,3), (2,1), (2,2), (3,1), (3,3) }

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

 

 

정답: 3

 

 

 

49. 관계 R을 부울행렬로 나타낸 것은? 

 

 

 

정답: 4

 

 

 

 

 

50. 관계 R에 대한 설명으로 옳은 것은? 

1) 동치 관계이다.

2) 반사적이고 대칭적이나 추이적이지 않다.

3) 반사적이고 추이적이나 대칭적이지 않다.

4) 반사적이지만 대칭적이지도 추이적이지도 않다. 

 

 

 

정답: 2

해설: 관계 R은 (1,1), (1,2), (1,3), (2,1), (2,2), (3,1), (3,3)로 주어진다. 이 관계는 모든 원소가 자기 자신과 관계를 가지므로 반사적이다. (1,2)와 (2,1)이 존재하므로 대칭적이지만, (1,3)이 있고 (3,2)가 없어 추이적이지 않다. 다른 선지들을 살펴보면, 동치 관계는 반사적, 대칭적, 추이적이어야 하지만 R은 추이적이지 않다. 또한 반사적이고 추이적이나 대칭적이지 않음을 설명하는 선지는 R의 특성과 맞지 않는다. 따라서 R은 반사적이고 대칭적이나 추이적이지 않은 관계이다.

 

 

 

 

 

51. A = {1,2,3}, B={1,2,3} 일 때, A 에서 B로의 관계 R = {(1,a), (2,a), (3,b)}에 관한 설명으로 옳은 것은? 

1) R은 A에서 B로의 단사함수이다.

2) R은 A에서 B로의 전사함수이다.

3) R은 A에서 B로의 전단사함수이다.

4) R은 A에서 B로의 상수함수이다. 

 

 

 

정답: 1,2,3,4

 

 

 

 

52. 다음 중 옳은 것은? 

1) \( \lceil1.23 \rceil= 1 \)
2) \( \lfloor-0.917 \rfloor = -1 \)

3) 4! = 10

4) \( 97 \mod 5 = 3 \)

 

 

 

정답: 2

해설: 정답은 2번이다. 2번 선지에서 \( \lfloor-0.917 \rfloor = -1 \)은 올바른 표현이다. 바닥 함수 \( \lfloor x \rfloor \)는 x보다 크지 않은 가장 큰 정수를 반환하는데, -0.917의 경우 -1이 이에 해당한다. 반면, 1번의 \( \lceil1.23 \rceil= 1 \)은 올림 함수이므로 결과는 2가 되어야 하고, 3번의 4! = 10은 4의 계승(24)이므로 틀렸다. 4번의 \( 97 \mod 5 = 3 \)도 계산 결과는 2이므로 틀린 설명이다. 따라서 2번만이 올바른 설명이다.

 

 

 

53. 다음 부울식 중 옳은 것은? (2점)
① \( X + 0 = 0 \)
② \( X + \overline{X} = 0 \)
③ \( X(X + Y) = Y \)
④ \( X + YZ = (X + Y)(X + Z) \)

 

 

 

정답: 4

해설: 정답은 4번이다. 4번 선지에서의 부울식 \( X + YZ = (X + Y)(X + Z) \)는 부울 대수의 분배 법칙을 통해 동일함을 확인할 수 있다. 이 법칙에 따르면, \( (X + Y)(X + Z) \)는 \( XX + XZ + YX + YZ \)로 확장되고, 여기서 \( XX \)는 \( X \)와 같으며 \( XZ \)와 \( YX \)는 각각 \( XZ \), \( XY \)로 간소화할 수 있어 최종적으로 \( X + YZ \)가 된다. 다른 선지들을 살펴보면, ①번은 \( X + 0 = X \)가 정확하다. ②번은 \( X + \overline{X} = 1 \)이 올바르다. ③번의 경우 \( X(X + Y) = X \)로 단순화되므로 \( Y \)와는 같지 않다. 따라서 4번 선지가 유일하게 올바른 부울식을 제시하고 있다.

 

 

 

 

* (54~55) 다음 그래프 G에 대해 물음에 답하시오. 

 

 

 

 

54. 그래프 G와 관련된 서술 중 부적절한 것은? 

1) G는 V = {a, b, c}를 꼭지점의 집합으로 갖는다.

2) G는 방향 그래프가 아니다.

3) G는 단순그래프이다.

4) c의 차수는 3이다. 

 

 

 

정답: 3

해설: 단순그래프란 꼭지점의 집합 V와 변의 집합 E로 이루어진 G=(V,E)에 대해서, 루프나 병변을 가지지 않는 무향 그래프이다. 해당 그래프는 루프를 가지므로 단순그래프가 아니다. 

 

 

 

55. 그래프 G를 인접행렬로 표현한 것은? 

 

 

 

 

 

 

 

정답: 1

 

 

 

 

 

56. 다음 그래프 G에 관한 설명으로 부적절한 것은? 

 

 

1) G는 완전 그래프이다.

2) G는 정규 그래프이다.

3) G에는 오일러 투어가 존재한다. 

4) G에는 해밀턴 사이클이 존재한다. 

 

 

 

정답: 3

해설: 정규그래프란 그래프 G=(V,E)에 대해서, 모든 꼭지점들이 동일한 수의 이웃을 가질 경우, 정규 그래프라고 한다. 정규 그래프의 모든 꼭지점들은 동일한 차수를 가지게 되는데, 특히 각 꼭지점의 차수가 k라면 k- 정규 그래프라고 부른다. 완전그래프란 그래프에 속한 모든 꼭지점이 다른 꼭지점과 인접할 경우 완전 그래프라 한다. 해당그래프는 따라서 3-정규 그래프이다. 오일러 투어가 존재하기 위해서는 모든 꼭지점의 차수가 짝수여야 하는데, 해당 그래프는 홀수이므로 오일러 투어가 존재하지 않는다. 

 

 

 

 

57. 다음 트리 T에 관한 설명으로 옳은 것은? 

 

 

 

1) A는 B의 자식 노드이다.

2) A, B, E, F, Q는 형제 노드들이다.

3) T의 차수는 17이다.

4) T의 높이는 4이다. 

 

 

 

정답: 4

해설: 차수는 17이 아니라 가장 높은 노드의 차수이므로 4이다. 높이는 4가 맞다. 

 

 

 

58. 다음 설명 중 옳은 것은? 

1) 높이가 2인 이진 트리의 최대 노드 개수는 8개이다.

2) 4개의 노드를 가지는 이진 트리의 최대 높이는 3이다.

3) 7개의 노드를 가지는 이진 트리의 최소 높이는 3이다.

4) 높이가 3이고 16개의 노드를 가지는 완전 이진 트리가 존재한다. 

 

 

 

 

정답: 2

해설: 높이가 k인 이진트리가 가질 수 있는 최대 노드 수는 2^k+1 -1이다. 따라서 1번 선지에, 높이가 2인 경우 최대 노드 수는 7이다. n개의 노드를 갖는 이진트리의 최소 높이는 \( \lfloor log2n \rfloor \)이다. 따라서 3번 선지의 7개의 노드를 가지는 이진 트리의 최소 높이는 2이다. 4번 선지에, 높이가 3인 이진트리가 최대로 가질 수 있는 노드 개수는 2^4 -1 = 15이다. 정답 2번은 4개의 노드를 가진 이진 트리의 최대 높이가 3이 될 수 있다는 것이다. 이진 트리의 최대 높이는 각 노드가 하나의 자식만 가지는 경우에 달성된다. 따라서 4개의 노드로 구성된 이진 트리는 루트에서 시작하여 각 레벨마다 하나의 자식을 연결하면 세 번째 레벨까지 노드를 배치하여 경사 이진 트리를 구성하면 최대 높이가 3이 된다. 

 

 

59. x, y, z가 자연수일 때 x + y + z <= 5를 만족하는 경우의 수는?

1) 8

2) 9

3) 10

4) 11

 

 

정답: 3

해설: 정답은 10이다. 이 문제는 x, y, z가 자연수이며 세 수의 합이 5 이하가 되는 경우의 수를 찾는 조합 문제이다. 자연수의 최소값은 1이므로, x, y, z 각각을 1 이상으로 설정하고 조건을 만족하는 경우를 하나씩 세어보면 된다. 예를 들어, (1, 1, 1)은 합이 3이고, (1, 1, 2)와 (1, 2, 1), (2, 1, 1)은 각각 합이 4이며, (1, 1, 3), (1, 3, 1), (3, 1, 1)은 합이 5이다. 합이 4 이하인 다른 조합들을 추가하면 총 10개의 경우가 나온다. 

 

 

 

60. 다음 상태 전이도는 결정적 유한 오토마타를 표현하고 있다. 입력 문자열 10100에 대응하는 출력 문자열을 구한 것은? 

 

 

 

1) aabba

2) ababb

3) babaa

4) aabab

 

 

 

 

 

정답: 1

 

 

 

 

---

2018-1 이산수학 기말시험 기출문제.pdf

1.11MB