Discrete Mathematics

주교재

Kenneth H. Rosen,"이산수학(7판)",공은배 등 7인 공역,한국맥그로힐,2012

과제 #1

1.1절 연습문제 1,3,8,11,12,16,20,27,31,35,36

과제 #2

1.3절 연습문제  1,3,4,5,6,9,14,16,24,35

과제 #3

1.4절 연습문제  5,11,16,20,25,30,35,49,51

과제 #4

1.5절 연습문제  26,28,30,39,45

과제 #5

2.1절 연습문제  7,9,14,20,21,27,32,34,43

과제 #6

2.2절 연습문제  28, 32, 38, 48, 51

Quiz #1 

13:30-14:00 07-APR-2014

과제

2.4 22번 문제는 아래내용으로 정정합니다.

b) What will the salary of this employee be in 2017? 

과제 #7

2.3절 연습문제  8, 14, 22, 30, 36, 42, 67

---------------------------------------------------------------

1.3절 연습문제 풀이

1.3-(14)

(¬p ∧ (p → q )) → ¬q   ≡ ¬(¬p ∧ (p → q)) ∨ ¬q     예제 3 적용  

                                    ≡ ¬(¬p ∧ (¬p ∨ q)) ∨ ¬q   예제 3 적용  

                                    ≡ (p ∨ (p ∧ ¬q)) ∨ ¬q        이중 부정법칙 적용

                                    ≡ p ∨ ¬q                            흡수법칙 적용

p가 false이고 q가 true 이면 false이므로 항진이 아니다.

1.3-(16)

p ↔ q  ≡ (p → q)∧(q → p)                             정의 적용

            ≡ (¬p ∨ q) ∧ (¬q ∨ p)                       예제 3 적용    

            ≡ [(¬p ∨ q) ∧ ¬q] ∨ [(¬p ∨ q) ∧ p]    제 2 분배법칙 적용     

            ≡ [(¬p ∧ ¬q) ∨ (q ∧ ¬q)] ∨ [(¬p ∧ p) ∨ (q ∧ p)]    제 2 분배법칙 적용     

            ≡ [(¬p ∧ ¬q) ∨ F] ∨ [F ∨ (q ∧ p)]    부정법칙 적용     

            ≡ [(¬p ∧ ¬q)] ∨ [(q ∧ p)] 

            ≡ (p ∧ q) ∨ (¬p ∧ ¬q)                     교환법칙 적용

따라서 동치이다.

---------------------------------------------------------------

1.4절 연습문제 풀이

49번 문제

이해를 돕고자 implies를 다음과 같이 변환하겠습니다.

(a)번 문제

∀x(P(x) → A) ≡ ∃xP(x) → A

∀x(¬P(x) ∨ A) ≡ ¬∃xP(x) ∨ A

A는 true 또는 false 를 가질 수 있으므로, 우선 A가 false 라면,

∀x(¬P(x) ∨ F) ≡ ¬∃xP(x) ∨ F

즉,

∀x(¬P(x)) ≡ ¬∃xP(x)

동치입니다.

한편, A가 true 라면,

∀x(¬P(x) ∨ T) ≡ ¬∃xP(x) ∨ T

T ≡ T

동치입니다.

(b)번 문제도 (a)번 문제와 유사하게 풀어보세요.

51번 문제 

예를 들어 P(x)가 양수

Q(x)가 음수이고, 정수라는 정의역이라면,

∃xP (x) ∧ ∃xQ(x) 는 true 이지만,

∃x(P (x) ∧ Q(x)) 는 false 입니다.

즉, 논리적으로 동치가 아닙니다.

과제 #8

2.4절 연습문제  4, 10, 16, 18, 22, 26, 30, 32, 34, 43

과제 #9

2.6절 연습문제  2, 4, 6, 10, 20, 26, 28

---------------------------------------------------------------

중간고사 : 4월 24일 (목) 09:00

과제 #10

3.1절 연습문제  3, 6, 7, 10, 14, 16, 18, 20, 34, 38, 52

과제 #11

3.3절 연습문제  2, 4, 5, 7, 15, 16, 18, 19

4.4 연습문제 풀이

38-(b)

중국 나머지 정리를 이용하여, 

x = 3^302, m = (5)(7)(11)

a1 = 4, M1 = (7)(11)

a2 = 2, M2 = (5)(11)

a3 = 9, M3 = (5)(7)

Mk*yk ≡ 1 (mod mk)

y1 = 3, 

y2 = 6,

y3 = 6,

이제 x = 3^302 =

4(7)(11)(3) + 2(5)(11)(6) + 9(5)(7)(6) (mod 385)

≡924 + 660 + 1890 (mod 385)

≡154 + 275 + 350 (mod 385)

≡9 (mod 385)