연습 문제 해답
※ 전체 해답집은 교수님용이므로 학생들에게는 절대 유출되지 않도록 당부 드립니다.

이산수학의 개요

01
1. ×

2. ○

3. × (반대임)

1. (2)

2. (1)

3. (3)

4. (4)

4. ○

5. ○

5. (2)

1. 이산적이란 말은‘연결되지 않고 떨어져 있는’원소들로 구성된 것이라는
뜻이며, 디지털 시계나 디지털 컴퓨터에서 그 예를 찾을 수 있다.

2. 이산수학에서는 논리, 명제, 집합, 증명법, 관계, 함수, 그래프, 트리, 순열,
이산적 확률, 재귀적 관계, 행렬, 행렬식, 부울 대수, 오토마타, 형식 언어
등을 다룬다.

3. 아이디어 스케치 단계, 추상적 모델 구상 단계, 수학적 모델링, 문제 풀이 및
적용

4. 이산수학은 컴퓨터공학, 정보통신, 소프트웨어 등의 소위 정보기술
(Information Technology: IT) 분야에서 시스템을 설계하거나 컴퓨터를 이
용해서 문제를 해결하는 데 많이 이용한다. 또한 이산수학과 관련된 지식은
전자공학, 기계공학 등 여러 공학 분야에도 중요한 학문적 기반이 된다.

5. 수학적인 논리와 이산수학의 기초를 익혀 창의적인 사고의 폭을 넓히고, 공학
분야의 학습에 있어 전산 분야의 수학적 바탕을 확립한다. 또한 수학적 구조의
이해, 복잡한 현상들의 추상화, 추상적 모델의 개념적 이해 등을 들 수 있다.

501

연습 문제 해답

논리와 명제

02

1. × (단순히 그냥 값은 명제가 아님)
5. ○

6. × (모순 명제임)

1. (2)
7. (2)

2. (3)
8. (2)

2. ○

7. ○

3. (2)
9. (4)

4. (4)
10. (1)

3. ○

4. × (T이다)

8. × (모든 경우임)

5. (1)
11. (3)

6. (1)
12. (3)

1. (1) 명제가 아님 (2) 참 (3) 거짓 (4) 참
2. (1) p/q (2) p/~q (3) ~p/~q
3. (1) 지구는 둥글고 태양의 주위를 공전한다.
(2) 지구는 둥글지 않고, 태양의 주위를 공전하지 않으며, 달은 지구의 주위
를 공전한다.
(3) 지구가 둥글면 지구는 태양의 주위를 공전하고, 그러면 달은 지구의 주위
를 공전한다.

4.

p

q

p0q

~( p 0 q)

T
T

T
F

T
T

F
F

F

T

T

F

F

F

F

T

5. 각 경우의 진리표를 만들면
(a)

p

q

p/q

T

T

T
F

F
T

F

F

~p

T

F

F

F

F

F
F

T
T

F
T

T
F

T
T

F

T

T

T

T

~q

같은 값

502

~p 0 ~q

~( p / q)

연습 문제 해답

(b)

p

q

p0q

~( p 0 q)

~p

~q

~p / ~q

T

T

T

F

T
F

F
T

T
T

F
F

F

F

F

F
T

T
F

F
F

F

F

F

T

T

T

T

같은 값

6.

p

q

~p

~p / q

T

T

F

F

T
F

F
T

F
T

F
T

F

F

T

F

7. (1), (2)가 항진 명제이다.
8. (1)

~p

p 0 ~p

~( p 0 ~p)

F

T

F

F

(2)

p
T

T

T

F

p

q

p/q

~( p 0 q)

(p / q) / ~( p 0 q)

T

T

T

F

F

T

F

F

F

F

F

T

F

F

F

F

F

F

T

F

9. (1) ~(~p/~q)≡~(~p)0~(~q)
≡p0q
(2) ~(p"~q)≡~(~p0~q)
≡~(~p)/~(~q)
≡p/q

10. (1) 허위 추론이다. p q

~p "q

~p

⇒

T
T

T
F

T
T

F
F

⇒

F

T

T

T

F

F

F

T

503

연습 문제 해답

(2) 허위 추론이다. p q

~p "q

~q

T

⇒
⇒

T

F

T

F

T
T

F

T

T

F

F

F

F

T

11. ~(p"q)≡~(~p0q)
≡~(~p)/(~q)
≡p/~q

12.

T

: 조건 법칙
: 드 모르간의 법칙

p

q

p/q

p 0 (p / q)

p

T

T

T

T

T

T

F

F

T

T

F

T

F

F

F

F

F

F

F

F

13. (1) p0q≡~(~(p0~q))
≡~(~p/~q)
(2) p0q≡~(~(p/~q))
≡~(~p0~q)
>
14. (1) 0 Y3이므로 p(0)은 거짓

15. (1) 참

(2) 거짓

(2) 4 > 3이므로 p(-4)는 참

(3) 참

16. (1) p (x) : x < x + 1이라 하면, 6x p (x)
(2) p (x) : x 2 - 12x + 35 = 0이라 하면, 7x p (x)
(3) x : 국가들, p(x) : 올림픽에서 메달은 딴다. ~( 6x p (x))

17. (1) 모든 전산학과 학생들은 이산수학과 C언어를 수강한다.
(2) 전산학과 학생 중에 이산수학을 수강하거나 C언어를 수강하지 않는 학
생이 있다.

504

연습 문제 해답

(2) 6x (p (x) / q (x))

18. (1) 7x p (x)
19. (1)

p /p

~p

T

F

F

F

(2)

p

T

(3) ~( 6x p (x))

T

q /q

(p / p) / (q / q)

p0q

F

F

T

T

F

T

T

T

T

T

F

T

T

F

T

T

F

F

p

q

p /p

T

T

T

F

F
F

(3) p/q≡(pMq) M(pMq)

20. (1)

q

r

p "q

q"r

(p " q) ) (q " r)

T
T

T
T

T
F

T
T

T
F

T
F

T
T
F

F
F
T

T

F
F
T

T
T
T

F

F
T

F

T

F

F

F
T

T
T

T

F
T

F

(2)

p

F

F

T

T

T

F
T

F

p

q

p5q

~q

~p

~q " ~p

(p 5 q) " (~q " ~p)

T

T

F

F

F

T

T

T
F

F
T

T
T

T
F

F
T

F
T

F
T

F

F

F

T

T

T

T

21. (1) 허위 추론이다.

505

연습 문제 해답

p

q

r

p "~q

~r " q

T

T

T

F

T

F

T
T
T

T
F
F

F

F

T

T
F

T
T

T
T
F

⇒
⇒

F

T
T

T
F

T
T

T

F

T

T
T

⇒

F

F

T

T

T

T

F

F

F

T

F

T

⇒

p "~r

F
T

(2) 허위 추론이다. p q

r

p "q

~r " ~q

~p "r

T

T

T

T

T

T

T

T

F

T

F

T

T
T

F
F

T
F

F
F

T
T

T
T

F

T
T

T
F

T
T

T

F

F

T
F

⇒

F

F

T

T

T

T

⇒

F

F

F

T

T

F

⇒

⇒

22. ((p " q) 0 (p " r)) " (q 0 r)
+ ((~p 0 q) 0 (~p 0 r)) " (q 0 r)
+ (~p 0 (q 0 r)) " (q 0 r)
+ ~(~ p 0 (q 0 r)) 0 (q 0 r)
+ (p / ~( q 0 r)) 0 (q 0 r)
+ (p 0 (q 0 r)) / (~( q 0 r) 0 (q 0 r))
+ (p 0 (q 0 r) / T)
+ p 0 (q 0 r)

03

집합론

1. × (무수히 많으므로 무한 집합)

506

조건 법칙
멱등, 결합 법칙
조건 법칙
부정 법칙
분배 법칙
부정 법칙
항등 법칙

2. ○

3. ○

4. × (순서와 밀

연습 문제 해답

5. ○

접한 관계가 있다)

1. (4)
7. (2)

2. (4)
8. (4)

6. × (16개임)

3. (4)
9. (2)

4. (4)
10. (2)

7. ○

8. ○

5. (1)
6. (3)
11. (3)
12. (2)

1. {1, 3, 5, 7}의 4개임
2. A = {5, 10, 15, 20, 25}
3. (1) z

(2) {2, 3, 5, 7, 11, 13}

4. (1) 유한 집합

(2) 무한 집합

5. (1) {1, 2, 3, 5, 7, 9, 11}
6. (1) {2, 4, 6}

(2) {3, 5}

(2) {3}
(3) z

7. (1)

(4) {1, 2, 3, 4, 5, 6}
(2)
A

A
B

C

B

C

8. 5×3×5 = 75개
9. A×B={(1, 1), (1, 3), (2, 1), (2, 3)}
10. C = {y y ! N, 4y + 3 > 0}

D 1 A 1 C, D 1 B 1 C

11. z, {1}, {2}, {{3}}, {1, 2}, {2, {3}}, {1, {3}}, {1, 2, {3}}
12. A = 1, B = 8 또는
A = 2, B = 4 또는
A = 4, B = 2 또는
A = 8, B = 1

13. P({a, b})={z, {a}, {b}, {a, b}}
14. 수학, 영어를 신청한 학생의 집합을 각각 A, B라 하면

507

연습 문제 해답

n (A + B) = n (A) + n (B) - n (A , B) = 52 + 45 - 80 = 17
Ñ n (A + B c ) = n (A) - n (A + B) = 52 - 17 = 35

15. r1={{1}, {2, 3}} r2={{2}, {1, 3}} r3={{3}, {1, 2}} r4={{1}, {2}, {3}}

16. (1) A : 자료구조를 수강하는 학생의 집합
B : 컴퓨터구조를 수강하는 학생의 집합
C : 이산수학을 수강하는 학생의 집합
A = 48, B = 41, C = 40, A + B = 15, A + C = 12,
B + C = 13, A , B , C = 94
A+B+C = A,B,C - A - B - C + A+B
+ A+C + B+C
= 94 - 48 - 41 - 40 + 15 + 12 + 13
=5
(2) 두 과목만 수강하는 학생의 수는
A + B + A + C + B + C - 3 A + B + C = 15 + 12 + 13 - 15
= 25
(3) 한 과목만 수강하는 학생의 수는
94 - 25 - 5 = 64

17. (1) (A + B) , (A + B) = A + U
(2) (A , z) + (B , A) = A

18. (1) A + B 3 C

B-C3A
C

A

C
B

A

A+B

B

B-C

(2) (A + B 3 C)이므로 (A + B) 4 C 이다.
B - C = B + C 3 (B + (A + B) = B + (A , B) = B + A 3 A이다.
Ñ A + B 3 C 이면 B - C 3 A이다.

508

연습 문제 해답

04
1. ○
4. ○

1. (3)

증명법

2. × (답은 그 반대임) 3. × (처음 시작값은 n에 따라 다를 수 있다)
5. ○
6. × (p " q와 q " p를 모두 증명해야 함)
7. ○

2. (4)

3. (4)

4. (3)

5. (4)

1. 수학적 귀납법
(기초 단계) n=1일 때 좌변=우변=1
(귀납 가정) 만약 1+3+5+…+(2n+1)=n2이라고 가정하면
(귀납 단계) 1+3+5+…+(2n-1)+(2n+1)=n2+2n+1=(n+1)2

2. 집합 S에 대한 멱집합 P (S) = 2 2 임을 S 에 대한 수학적 귀납법으로 적용한
다. 즉, S = 0이면 S = z이다.
P (S) = 2 S = 2 2 = 2이다.
S = 1이면 P (S) = 2, 2 S = 2이다.
S = k일 때 P (S) = 2 S = 2 S 라고 한다면
S = k + 1이면 P (S) = 2 k + 1

3. n=1일 때 성립한다. n일 때 성립한다고 가정하면
(n+1)3+2(n+1)=n3+3n2+5n+3
=n3+2n+3n2+3n+3
=(n3+2n)+3(n2+n+1) [3의 배수]

4. 8 = 2 2이므로 과 같은 방법으로 적용하여 증명함
5. (n≥5에 대한 수학적 귀납법을 이용)
(기초 단계) n=5인 경우 25>52이므로 2n>n2이 성립한다.
(귀납 가정) 만약 n≥5일 때 2n>n2이라고 가정하면 2n+1>(n+1)2임을 보이면
된다.

509

연습 문제 해답

(귀납 단계) 2n+1=2∙ n
2
>2∙ 2 n 2
=n +n2
>n2+4n=n2+2n+2n
>n2+2n+1
=(n+1)2
따라서 n+1인 경우에도 위의 식이 성립한다.

6. 2x + 4y = 21이므로
2 (x + 2y) = 21
(x + 2y) = 21
2
여기서 21이 정수가 아니므로 x + 2y는 정수가 아니다.
2
따라서 x + 2y는 정수가 아니다.

7. n과 m이 각각 짝수이므로 n=2p, m=2q(p, q는 정수)가 나타날 수 있다.
따라서 n+m=2p+2q=2(p+q)이므로 n+m은 짝수이다.

8. 왼쪽과 오른쪽이 모두 양수이므로 양변을 제곱하여 뺀 값 x 2 + 2 x y + y 2 - x + y 2 $ 0이다. 따라서 성립한다.

9. |x|>|y|이므로 |x|2>|y|2이 된다. 또한 모든 수 z에 대해 |z|2=z2이다.
따라서 x2>y2이 된다.

10. 주어진 명제의 대우인‘a, b가 실수일 때 a ! 0 또는 b ! 0 이면, a 2 + b 2 ! 0’ 증명하면 된다.
를
a, b가 실수일 때 a ! 0 또는 b ! 0이면 a 2 > 0 또는 b 2 > 0이 되므로 a 2 + b 2 > 0 이다.
이것은 a 2 + b 2 = 0이라는 가정에 모순이다.
그러므로 a 2 + b 2 = 0이면 a=0이고 b=0이다.

11. x와 y가 모두 홀수인 경우 xy는 당연히 홀수가 된다. 역으로 xy가 홀수이면 x와 y가 각각 홀수인 경우밖에 없다. 따라서 두 명제는 동치이다.

12. 홀수는 어떤 정수 i에 대해 2i+1로 나타낼 수 있고, 짝수는 어떤 정수 j에 대
해 2j로 나타낼 수 있다. 주어진 명제에 의하면 (2i+1)2=2j이고 이는
4i2+4i+1=2j이다. 좌변은 2로 나누어 떨어지지 않는데 우변은 2로 나누어
떨어지므로 이것은 모순이다. 따라서 주어진 명제는 거짓이다.

510

연습 문제 해답

13. 두 정수의 제곱의 합이 정수가 아닌 예를 찾아보자. 가령 정수 3은 두 정수
의 제곱의 합으로 나타낼 수 없다는 것을 살펴보자. 이것을 보이기 위하여
3보다 크지 않은 제곱수는 02=0, 12=1뿐인데 0 또는 1로 된 2개 항의 합
으로 3을 만들 수 없다. 따라서 주어진 명제는 거짓이다.

14. n, m이 홀수이고, n+m이 짝수가 아니라고 가정하자. 즉, n+m이 홀수라고
할 때, 이 경우에는 n이나 m 중 하나가 홀수이고, 다른 하나는 반드시 짝수
여야 한다. 이것은 가정에 모순이 된다. 따라서 원래의 명제가 성립한다.

15. n은 짝수이고 m이 홀수일 때 n+m이 홀수가 아닌 짝수라고 가정하자. n+m
이 짝수가 되기 위해서는 n과 m이 모두 짝수이거나 n과 m이 둘 다 홀수인
경우 외에는 없다. 그러나 가정에서 n은 짝수이고 m이 홀수이므로 모순된
다. 따라서 주어진 명제가 성립한다.
1
1
16. 1 12 + 2 1 3 + g + (n + 1)( n + 2) + ; (n + 2)( n + 3) E
$
$
(n + 1)( n + 3) + 1
1
=n+1 +
=
n + 2 (n + 2)( n + 3)
(n + 2)( n + 3)
=

(n + 2) 2
= n+2
(n + 2)( n + 3) n + 3

17. (기초 단계) n=1일 때 왼쪽 1∙ 6의 배수
6은
(귀납 가정) n(n2+5)가 6의 배수라면
(귀납 단계) (n+1){(n+1)2+5}=(n+1)(n2+2n+6)
=(n+1)(n2+2n)+6(n+1)=n3+3n2+2n+6(n+1)
=n3+5n-3n2-3n+6(n+1)
=n(n2+5)-3n(n+1)+6(n+1) [6의 배수]

18. (기초 단계) n=1일 때 성립한다.
(귀납 가정) n일 때 식이 성립한다고 가정하면
(귀납 단계) (1 + 2 + g + n + n + 1) 2 = (1 + 2 + g + n) 2 + 2 (n + 1)
(1 + 2 + g + n) + (n + 1) 2 n (n + 1)
= 13 + 2 3 + g + n 3 + 2 (n + 1) $
+ (n + 1) 2
2
= 13 + 2 3 + g + n 3 + n (n + 1) 2 + (n + 1) 2
= 13 + 2 3 + g + n 3 + (n + 1) 3

511

연습 문제 해답

관계

05
1. × (9개이다)

2. ○

3. ○

4. × (동치 관계임)

5. ○

6. ○

7. × (반사 관계가 성립되지 않으므로 부분 순서 관계가 아니다)

8. ○

9. ○

10. ○

1. (4)
7. (2)

2. (3)
8. (2)

3. (1)
9. (4)

1. (1) a=7, b=3

4. (4)
10. (3)

5. (3)

6. (4)

(2) a=3, b=1

2. A = 3, B = 2이므로 A # B = 6이다.
3. B×B={(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}
4. (1) A×B={(1, a), (1, b), (1, c), (1, d), (2, a), (2, b), (2, c), (2, d), (3, a),
(3, b), (3, c), (3, d)}
(2) B×C={(a, 4), (a, 5), (b, 4), (b, 5), (c, 4), (c, 5), (d, 4), (d, 5)}

5. R-1={(1, 2), (2, 3), (3, 4), (4, 5), (5, 6)}
6. B가 A로 나누어 떨어진다’ 만족하는 관계를 구하면
‘
를
2 R 2 , 2 R 4 , 2 R 6 , 3 R 3 , 3 R 6 , 4 R 4이다.

7. (1)

(2)

1

1
5

2

2
5

3

3
4

512

4

연습 문제 해답

8. (1) I A R = R = {(1, 2), (1, 3), (2, 2), (3, 1), (4, 2)}
(2) R $ S = {(1, 3), (2, 3), (3, 1), (3, 3), (4, 3)}

9. (1) R={(a, c), (a, d), (b, b), (c, a), (c, c), (d, b), (d, d)}
(2) R={(a, a), (a, c), (a, d), (b, a), (b, d), (c, b), (d, d)}

10. (1)

(2)

(3)
1

5
4
3
2
1

2

1 2 3 4 5

5

3

4

1
R
1 S1
2 S0
S
M R = 3 S0
S
4 S0
S
5 S1
T

2
0
0
0
0
1

3
0
1
0
0
0

4
1
0
0
0
0

5
V
0W
1W
W
1W
W
0W
W
0W
X

11. (1) 1Ra, 2Rb, 3Rb, 1Rb이다.
(2) 정의역 = {1, 2, 3}, 치역 = {a, b}

12. (1) 대칭 관계 (2) 대칭 관계 (3) 반대칭 관계
13. 반사 관계, 대칭 관계, 반대칭 관계, 추이 관계가 성립한다.
14. (1) 반대칭, 추이 관계

(2) 대칭, 추이 관계
(3) 반사, 대칭, 추이 관계 (4) 반사, 대칭, 추이 관계

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

16. (3)과 (4)
17. {1, 2}∪{3, 4}∪{6}={1, 2, 3, 4, 6}≠S이므로 분할이 아니다.
18. 동치 관계임
19. 반사, 반대칭, 추이 관계가 모두 성립하므로 부분 순서 관계이다. 따라서 하
세 도표는 다음과 같다.
3
4

2
5
1

513

연습 문제 해답

20. R={(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3,
3), (3, 4), (3, 5), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (5, 3), (5, 4), (5,
5), (5, 6), (5, 7), (6, 4), (6, 5), (6, 6), (6, 7), (6, 8), (7, 5), (7, 6), (7,
7), (7, 8), (8, 6), (8, 7), (8, 8), (8, 9), (8, 10), (9, 7), (9, 8), (9, 9),
(9, 10), (10, 8), (10, 9), (10, 10)}

21. R*={(a, b), (a, c), (a, d), (b, b), (b, c), (b, d), (c, c), (c, d), (d, c), (d, d)}
22. 집합 A에서 집합 B로의 관계는 두 집합의 곱집합 A×B의 부분 집합의 개수
와 같다.
A×B＝{(a, 1), (a, 2), (b, 1), (b, 2)}
이므로 집합 A에서 집합 B로의 관계의 수는 24＝16개이고, 관계를 모두 나
타내면 다음과 같다. z {(a, 1)}
{(a, 2)}
{(b, 1)}
{(b, 2)}
{(a, 1), (a, 2)}
{(a, 1), (b, 1)}
{(a, 1), (b, 2)}
{(a, 2), (b, 1)}
{(a, 2), (b, 2)}
{(b, 1), (b, 2)}
{(a, 1), (a, 2), (b, 1)}
{(a, 1), (a, 2), (b, 2)} {(a, 1), (b, 1), (b, 2)} {(a, 2), (b, 1), (b, 2)}
{(a, 1), (a, 2), (b, 1), (b, 2)}

함수

06

1. × (1에 대해 x와 y가 동시에 대응함)
4. ○

5. ○

8. ○

9. ○

1. (4)
8. (4)

2. (1)
9. (2)

1. (1), (2)

514

2. ○

3. × (한 개의 결과임)

6. × ( f (R) ! R 이므로 전사 함수가 아님)

7. × (상수 함수임)

10. ×

3. (2)
4. (2)
10. (4)

5. (2)

6. (3)

7. (2)

연습 문제 해답

2. (3)
3. (1) b∈A에서 B로의 사상이 없으므로 함수가 아니다.
(2) c∈A에 대해 x와 z가 동시에 대응하므로 함수가 아니다.
(3) A의 모든 원소에서 B로 가는 사상이 존재하므로 함수이다.

4. 정의역=공변역=치역=R
5. (1) 함수 아님
(2) 함수, 정의역={a, b, c}, 공변역=치역={a, b, c}

6. 단사 함수이고 전사 함수이다.
7. A의 원소는 3개이므로 원소의 개수가 2개인 B에 모두 다르게 대응되는 경우
는 없다.

8. {(1, a), (2, a)}, {(1, a), (2, b)}, {(1, b), (2, b)}, {(1, b), (2, a)}
9. (1) 전단사 함수, Ran(f)=Z
(2) 단사 함수, Ran(f)={y|x, y∈Z, y=2x-3}

10. 전단사 함수, Ran(f)=R
11.
(1)

A

(2)

B

A

C g f
1

1

1

2

2

2

3
4

3

1

3

2

12.
(1)

A

(2)

A

A

A k h
1

1

1

1

2

2

2

2

3

3

3

3

13. (1) m≥n

(2) m = n

515

연습 문제 해답

14. (1) f % g = f (3x) = 3x - 1
(2) g % h = )

0, x 가 짝수일 때
3, x 가 홀수일 때

15. 함수 f가 전단사 함수이므로 역함수 f-1이 존재하며, f-1={(b, 1), (c, 2), (a, 3)}이다.

16. 3! = 6개
17. (1) (g�
f)(-1)=g(f(-1))=g(-1)=-1
(2) (f�
g)(-1)=f(g(-1))=f(-1)=-1
(3) (g�
f)(x)=g(x2-2)=2x2-3
(4) (f�
g)(x)=f(2x+1)=(2x+1)2-2=4x2+4x-1
(5) (g� g(x)=g�
f)�
f(x)(2x+1)=g((2x+1)2-2)=g(4x2+4x-1)
=2(4x2+4x-1)+1=8x2+8x-1
(6) (g� f(x)=g� 2-2)=g((x2-2)2-2)=g(x4-4x2+2)
f)�
f(x
=2(x4-4x2+2)+1=2x4-8x2+5

18. (1) f -1={(y, x) | 2x+3y=7}
(2) f -1={(y, x) | y=x3}
(3) f -1={(y, x) | ax+by=c, a!0}
(4) f -1={(y, x) | y=x4+x}

19. (g�
f)(x)=g(ax+b)=1-(ax+b)+(ax+b)2
=1-b+b2-ax+2abx+a2x2
=9x2-9x+3
∴a=3, b=-1 또는 a=-3, b=2

07

그래프

1. × (그 반대임)
6. ○

516

2. ○

3. × (오일러 경로임)

7. × (평면 그래프임)

8. ○

4. ○

9. × (2m이다)

5. ○
10. ○

연습 문제 해답

1. (1)

2. (3)

3. (1)

4. (3)

5. (4)

6. (2)

7. (2)

8. (4)

1. (2, 1), (3, 1), (3, 2)가 가능하다.
1

2

3

2. 두 정점 사이에 경로의 길이는 1이므로 반복되지 않을 경우에는 당연히
|V|-1 이하가 된다.

3. 1

2

3

주어진 그래프는 서로 떨어져 있으므로
연결된 그래프가 아니다.

4
5

6

4. v1 v2

v1� 사이클:�1, v2, v3, v1
기반�
v v1, v2, v1 v1, v1

v3

5.

A
B
C
D

A
R
S0
S1
S
S0
S
S0
T

B C D
V
1 1 1W
0 1 0W
W
1 0 0W
W
0 1 0W
X

517

연습 문제 해답

6.
1

2

3

7. A는 5차의 행렬이므로 G는 5개의 정점 v1, ..., v5를 갖는다. 그리고 aij=1이면 vi에서 vj를 연결선으로 이어 그리면 그래프는 다음과 같다. v1 v5

v4

v2 v3 8. (1)

a b c d e

f

(2)

a b c d e

f

a 0 1 0 0 0 1

a 0 1 1 0 1 1

b 1 0 1 0 0 1

b 1 0 1 0 0 0

c 0 1 0 1 0 0

c 1 1 0 1 0 1

d 0 0 1 0 1 1

d 0 0 1 0 1 0

e 0 0 0 1 0 1

e 1 0 0 1 0 1

f

9.

1 1 0 1 1 0

f

1 0 1 0 1 0

1 2 3 4 5 6
1 0 3 0 4 0 5
2 0 0 1 0 0 1
3 0 0 0 2 0 0
4 0 3 0 0 0 0
5 0 0 0 3 0 2
6 0 0 0 2 0 0

10. (1) v=4, e=6, f=4

(2) v=6, e=9, f=5
두 가지 경우 모두 v-e+f=2인 오일러 정리가 성립한다.

11. 홀수점이 12개이므로 최소한 6번이 필요하다.

518

연습 문제 해답

#
12. 8 2 7 = 28 개

13.

K4, 2

K5

14. G1은 오일러 그래프이고, G2는 해밀턴 그래프이다.
15. 모든 정점들이 짝수개의 차수를 가지지 않으므로 오일러 경로가 존재하지
않는다. 그러나 ECBADGFE의 해밀턴 순회는 존재한다.

16. (1)은 해밀턴 순회는 가지고 있으나 오일러 순회는 가지고 있지 않은 그래프
이고, (2)는 오일러 순회는 가지고 있으나 해밀턴 순회는 가지고 있지 않은
그래프이다.

17. 먼저 A로부터 가장 가까운 곳인 B로 이동한다. 그리고 B에서 마크하지 않
은 가장 가까운 도시는 거리가 7인 C가 선택된다. 그리고 C 도시에서 마크
되지 않은 가장 가까운 도시인 D를 선택한다. 그리고는 A로 돌아온다. 이
경우의 경로는 A, B, C, D의 순서가 되며, 총 거리는 12 + 7 + 11 + 18
=48이 된다.

18. EF 대신에 BF라야 동형 사상이 존재한다.
19. 1

4

2

E+={(1, 2), (2, 3), (4, 1), (4, 4),
(4, 2), (4, 3), (1, 3)}

3

519

연습 문제 해답

20.

a

b

R*={(a, b), (a, c), (a, d), (d, c),
(d, e), (a, a), (b, b), (c, c),
(d, d), (e, e), (a, e)}

d

c

R*는 주어진 순서쌍에다 자기 자신
을 나타내는 5개와 (a, e)를 추가한
다.

e

08
1. ○

2. ○

트리

3. × (항상 같다)

6. × (1개를 가질 수도 있다)

4. ○

5. × (m=n-1이다)

7. × (4개이다)

9. ○

10. ○

1. (1)

2. (3)

3. (2)

4. (2)

7. (1)

8. (2)

9. (1)

8. × (연결 리스트)

10. (2)

5. (3)

6. (3)

1. (1) D, H, I, F, J, K (2) A (3) A (4) B, A (5) H, I
2. 중순위 : 2, 1, 4, 3, 5
전순위 : 1, 2, 3, 4, 5
후순위 : 2, 4, 5, 3, 1

3. 중순위 : D, B, H, E, I, A, F, C, J, G, K
전순위 : A, B, D, E, H, I, C, F, G, J, K
후순위 : D, H, I, E, B, F, J, K, G, C, A

520

(6) E

(7) 2 (8) 3

연습 문제 해답

4. 중순위 : D, B, H, E, I, A, F, C, G
전순위 : A, B, D, E, H, I, C, F, G
후순위 : D, H, I, E, B, F, G, C, A

5. 완전 이진 트리는 높이가 k일 때 레벨 1부터 k-1까지는 모두 차 있고 레벨 k에서는 왼쪽 노드부터 차례로 차 있는 이진 트리이다.
포화 이진 트리는 잎 노드가 아닌 것들은 모두 2개씩의 자식 노드를 가지며
트리의 높이가 일정한 경우를 말한다.

6. 하나의 생성 트리를 만들면 다음과 같다. v2 v7

v5

v6

v1 v4 v3

7. bc, ce, bd, de 중 하나만을 제외해서 생성하는 트리는 4가지가 있다.
8. 8개
9.

b

c
3

a

5

2 d g
3

3 f 4

e

10. 두 가지 경우 동일한 연결
(1) sc, ac, cb, bt, bd의 순서로 연결
(2) bt, sc, ac, cb, bd의 순서로 연결 a b t s c d

11. 최단 거리는 (2)번 19, (3)번 15, (4)번 29, (5)번 29, (6)번 25

521

연습 문제 해답

12. 프림의 알고리즘의 경우 a로 시작할 경우 ab, bc, cd의 순서로 연결한다.
크루스칼의 알고리즘의 경우 bc, bd, ab의 순서로 연결한다.

13. ab, bd, de, bc, ef, cg의 순서로 연결
14. ce, eh, cd, eg, ef, cb, ad의 순서로 연결
15. 중순위 : A, /, B, **, C, *, D, +, E
전순위 : +, *, /, A, **, B, C, D, E
후순위 : A, B, C, **, /, D, *, E, + inorder(+) printf(+) �
⑧

inorder(*) inorder(/) inorder(A) printf(A) �
①

printf(D) �
⑦

inorder(**)

inorder(C)

printf(**) �
④

inorder(B)

printf(E) �
⑨

inorder(D)

printf(*) �
⑥

printf(/) �
②

inorder(E)

③ printf(B) �

printf(C) �
⑤

preorder(+) printf(+) �
①

preorder(*)

printf(*) �
②

preorder(/)

③ printf(/) �

preorder(A)

preorder(E) preorder(D) preorder(**)

printf(A) �
④

printf(**) �
⑤

printf(E) �
⑨

printf(D) �
⑧

preorder(B) printf(B) �
⑥

preorder(C) printf(C) �
⑦

postorder(+) postorder(*) postorder(/) postorder(A) printf(A) �
①

postorder(E)

postorder(D)

printf(*) �
⑦

postorder(**)

printf(/) �
⑤

postorder(B)

postorder(C)

③
②
printf(B) � printf(C) �

522

printf(D) �
⑥
printf(**) �
④

printf(+) �
⑨
printf(E) �
⑧

연습 문제 해답

16. 중순위 : 11, 7, 12, 4, 13, 8, 14, 2, 1, 5, 3, 9, 6, 10
전순위 : 1, 2, 4, 7, 11, 12, 8, 13, 14, 3, 5, 6, 9, 10
후순위 : 11, 12, 7, 13, 14, 8, 4, 2, 5, 9, 10, 6, 3, 1

17.

0
0

1.00

0.55

a: b: c: d: e: f: 1

0.28
1

0
0

0.16
1

1

0.45
0

1

0.07

0.09

0.12

0.22

0.23

0.27

a

b

c

d

e

f

0.07 :
0.09 :
0.12 :
0.22 :
0.23 :
0.27 :

0000�
0001�
001�
1 0�
11�
01

코드의 평균 길이 = 4×0.07 + 4×0.09 + 3×0.12�
+ 2×0.22 + 2×0.23 + 2×0.27�
= 2.44

순열, 이산적 확률, 재귀적 관계

09
1. ○

2. ○

4. ○

5. ○

7. ○

3. × (0≤P(A)≤1임)
1
8. ○ 9. × ( 8 임)

6. ○

1. (2)

2. (3)

3. (1)

6. (3)

7. (3)

1. (1) n

4. (1)

5. (1)

8. (4)

9. (4)

(2) n+1

4! = 12 (왜냐하면 S가 둘인 4개의 문자이기 때문이다)
2! 1! 1!
5!
= 60 (왜냐하면 P가 둘인 5개의 문자이기 때문이다)
(2)
2! 1! 1! 1! 1!

2. (1)

3. (1) 4!
2!

(2) 8!
2!2!

4. 5개에서 3개 택한 순열의 수와 같으므로 5P3=60(개)
7.6.5
5. (1) 7 C5 = 1.2 = 21

9.8
(2) 9 C7 = 1.2 = 36

523

연습 문제 해답

6. (1) 5 C3 = 5! = 10
5! 3!

(2) 10 C2 = 10! = 45
8! 2!

7 6 5
7. 8명으로부터 3명을 선택하는 경우이므로 7 C3 = 1 $$ 2 $$ 3 = 35가지이다.

8. 3명의 남자는 6 C3 방법으로 6명의 남자로부터 뽑힐 수 있고, 2명의 여자는
5 C2 방법으로 5명의 여자로부터 뽑힐 수 있으므로,
6 $ 5 $ 4 $ 5 $ 4 = 200 가지 방법으로 위원회를 구성할 수 있다.
6 C3 $ 5 C2 =
1$2$3 1$2
91
9. P (A) = 1 - P (AC ) = 1 - 125 = 216 이다.
216

10. 1, 4, 6, 4, 1
11. an = n2개
12. x3=2, x4=3, x5=5, x6=8, x7=13
13. x1 = 2, x2 = 1 x3 = 3x1 + 2x2 = 6 + 2 = 8 x4 = 3x2 + 2x3 = 3 + 16 = 19 x5 = 3x3 + 2x4 = 24 + 38 = 62
14. 여자를 1명도 선출하지 않는 경우는 4명의 위원을 모두 남자 중에서 선출하
는 경우이므로 20C4가지이고, 전체의 경우는
의 수는 다음과 같다.

구하는 경우

- 20C4가지

40C4

1 1 1 1
15. (1) 2 # 2 # 2 = 8

10

(1) 1 # 1 # 1 # 2 = 1
6 6 6 6 648

행렬과 행렬식

1. ○

2. ○

7. ○

524

40C4가지이므로

3. ×

4. × (원래의 행렬이 됨)

8. × (부호가 반대로 바뀐다)

5. ○

9. × (항상 같다)

6. ×
10. ○

연습 문제 해답

1. (4)

2. (4)

3. (2)

4. (4)

7. (3)

8. (1)

9. (3)

5. (3)

6. (1)

10. (1)

V
R
V
R
2 -2W
0
0W
A-B=S
1. A + B = S
S2
S2 - 2 W
W
S
W
S
4W
X
T
X
T
R
V
R
V
5 2W
S 23 34 W
2. AB = S
S15 10 W, BA = S - 6 - 8 W
S
W
S
W
T
X
T
X

3. (1) 3×3 행렬, 3×2 행렬 (2) 2, -5 (3) 2×3 행렬 (4) 4, 2
R
V R
V R
V
S 1 2 W # S 2 - 4 W = S0 0 W
4. A # B = S
W S
W S
S0 0 W S - 1
W
2 W S0 0 W
T
X T
X T
X
5. (1) 12 (2) 0
VT
R V
R
S 5W
S 1 - 1W R 1 2 1V
T
W
0W = S
6. (1) 7 5 - 1 4 A = S - 1W
(2) S 2
W S- 1 0 3 W
S
W
S
W
S
S 4W
S1
3W T
X
X
T X
T
7. (1) -2 (2) 8
8. (1) -5

(2) 24

(5) (1, 2)

(3) 0

9. |AB|=-132, |BA|=-132 그 이유는
|AB|=|BA|=|A|×|B|= 12×(-11) = -132
V
R
2W
V
R
S- 1
3 - 1W
3
3W
10. (1) S
(2) S 2
1W
W
S
S- 2
S
1W
S 3 -3W
X
T
X
T
V
R
S 2 - 1W
11. S
W
S- 1
1W
X
T
V
R
-2
1W
S
12. S 2 - 1 W
S 3
2W
X
T

525

연습 문제 해답

R
V
S 5 7 - 15 W
20 W
13. (1) AB = S - 12 0
S
W
S 17 7 - 35 W
T
X

14. (1) -20

(2) 5

15. (1) 27

R
V
30
33 W
S 27
(2) BA = S - 22 - 24 - 26 W
S
W
S - 27 - 30 - 33 W
T
X

(2) -120

(3) 4

(4) 16

부울 대수

11
1. ○

2. ○

3. × (같다)

4. ○

6. ○

7. ○

5. × (6 이하)

8. × (다른 값임)

1. (3)

2. (2)

3. (1)

4. (1)

5. (4)

6. (1)

7. (2)

8. (4)

9. (3)

10. (1)

1. (1) 1 (2) 1
2. (1) 1 (2) 0
3. (xy�
)+(x+y) =xy� y�
�
+x� =(x+x� y�
) =y�
4.

x

y

y�

x + y�

(x + y�
)x

0

0
1
0

1
0

1
0

0

0
1

1

1

0
1

1

1

0

1

1

=x(y+y�
)=x∙1=x
5. xy+xy�

526

연습 문제 해답

6. wx+(x� +(y+z�
z)�
)=wx+((x� +z�
)� )+(y+z�
)
=wx+(x+z�
)+(y+z�
)
=(wx+x)+z�
+(y+z�
)
=x+z�
+(y+z�
)
=x+(z� )+y
+z�
=x+z�
+y

드 모르간 법칙
보 법칙
결합 법칙
흡수 법칙
결합 법칙
멱등 법칙

7. a(b+a�
)
8. f(x, y)=x� y+xy 9. f(a, b, c)=a� c� bc+ab� +abc b� +a� c� 10. 간소화한 결과는 y가 된다. y x

0

1

0

1

1

1

11. (1)

x

y

(2)

1

1

1

1

bc 00

01

0

1

0

0

1

a

11

10
1

1

1

y
12. f(x, y, z)=xz+x� x yz 00

01

1

1

10

1

0

11

1

1

13. (1) y+xz� (2) xy+xw�
14.

a

bc 00

01

11

0

1

1

1

1

10

1

527

연습 문제 해답

15. x y z

16. (1) x y (2) x y z

w +y w +xyw
17. (1) f(x, y, z, w)=x� � ��
(2) f(x, y, z, w)=z� w+y� +y� z� w q rs+p qrs +pq r� rs+pqr� s+pqrs
18. f(p, q, r, s)=p�� � � �s+pq�

알고리즘을 통한 문제 해결

12
2
1. × (O(n )임)

2. ○

3. ○

6. ○

7. × (O(n)임)

8. ○

1. (2)

2. (1)

4. (3)

3. (2)

1. (1) 참
2. (1) 참

(2) 거짓

3. (1) O(log2n)

528

(2) 거짓

(2) O(n)

4. ○

5. × (상수임)

5. (3)

6. (1)

7. (3)

8. (1)

연습 문제 해답

3
4. (1) O(n )

(2) O(nlog2n)

5. (1) f(n)＜g(n)

(2) f(n)＜g(n)

6. (1) f(n)＜g(n)

(2) f(n)＜g(n)

7. (1) O(1)

(2) O(n)

8. O(log2n)
9. 30일 때 비교 횟수 : 3
21일 때 비교 횟수 : 4

10. 서로 간의 포함 관계가 없다.
11. (1)

(2)

12. (1)

(2)

529

연습 문제 해답

(3)

13.

21

4

92

34

1

47

18

40

i=0

4

21

34

1

47

18

40

92

1

4

21

1

34

18

40

47

92

2

4

1

21

18

34

40

47

92

3

1

4

18

21

34

40

47

92

4

1

4

18

21

34

40

47

92

5

1

4

18

21

34

40

47

92

6

1

4

18

21

34

40

47

92

오토마타, 형식 언어, 문법

13
1. ○

2. ○

3. × (반대임)

6. ○

7. × (형식 언어)

8. × (반대임)

1. (3)

2. (4)

4. (2)

3. (4)

1. (1) 5, elppa (2) 4, evol
2. (1) 맞음
3. (1) cba

530

(2) 아님
(2) abc

4. ○

5. ○

5. (3)

6. (4)

7. (1)

8. (2)

연습 문제 해답

4.

1

0
1
q0

q1
0

5. 0001과 01001은 DFA에 의해 인식된다.
6. 이 DFA는 많아야 세 개의 a를 포함하는 모든 스트링을 인식한다. 따라서 3
가지 모두의 스트링을 인식한다.

7. (1), (4)는 인식되고, (2), (3)은 기각된다.
8. a, (ab)a, ababa
9. 넌터미널 심볼: S, A, B

터미널 심볼: a, b, c

10. (1) 속한다. (2) 속하지 않는다.
11. S에서 A로 가고, 다시 B로 갈 때 터미널 심볼이 없으므로 생성되는 언어가
없다.

12. DFA M이 어떤 경우에도 인식하는 스트링이 없는 경우를 말한다.
13.

b

b a 14. R = {a, b}라고 할 때
(1)

a, b

b a 531

연습 문제 해답

(2)

a, b a, b

a, b

15.

0~9

q0

1~9

q1

0

q2

532