[방송통신대학교] 2020년도 이산수학 2학년 출석 대체 시험 과제물

과제 내용

1. 다음 합성 명제가 서로 동치임을 보이시오 - ~(p∨(~p∧q)) ≡ (~p) ∧ (~q)

2. 두 홀수의 곱이 홀수임을 증명하시오.

3. 집합 A, B에 대해 |A| = a, |B| = b, |A∩B| = c 일 때, A∪B의 크기를 구하시오.

4. A가 임의의 n차 정방행렬일 때 다음을 증명하시오

• (1). A + A^T             
• (2). A – A^T

5. 집합 A ={ 0,1,2,3 } 에 대한 관계 R이 다음과 같을 때 서로 다른 동치류를 모두 찾으시오

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

---

과제 답

1번 문제

~(P ∨ (~P ∧ q)) ≡ ~P ∧ ~(~P ∧ q)

           ≡ ~P ∧ (~(~P) ∨ (~(q))              (드모르간 법칙)

           ≡ ~p ∧ (P ∨ ~q)

           ≡ (~P ∧ P) ∨ (~P ∧ ~q)            (분배법칙)

           ≡ F ∨ (~P ∧ ~q)

           ≡ (~P ∧ ~q) ∨ F           (교환법칙)

           ≡ (~P) ∧ (~q)

 

---

2번 문제

• n이 자연수라고 가정할 때 짝수의 경우 2n으로 정의를 할 수 있고 홀수의 경우 2n – 1 로 정의할 수 있다.
• 홀수와 홀수의 곱이 (2n - 1) X (2n - 1) 이라고 할 때 (2n – 1) X (2n – 1) = 4n^2 – 4n + 1이기 때문에 = 4n (n – 1) + 1에서 4n ( n – 1 )은 0과 짝수만이 나올 수 밖에 없다.
• 그렇기 때문에 결국 0과 짝수에 1을 더한 숫자는 반드시 홀수 이므로 두 홀수의 곱은 홀수이다.

---

3번 문제

[ A ] + [ B ] = [ A ] + [ B ] – [ A ∩ B ] 와 같다.

[ A ] = a, [ B ] = b, [ C ] = c 이므로 [ A ∪ B ] = a + b – c

---

4번 문제

(1). A + A^T              

(A + A^T) ^T = A^T + A 이며 전치를 하더라도 같은 행렬이 나온다. 그러므로 이는 대칭행렬이다.

 

(2). A – A^T

 (A - A^T)^ T = A^T – A = - (A – A^T) 이므로 이는 교대 행렬이다.

---

5번 문제

• 집합 X에 대해 대칭관계, 추이관계, 반사관계가 모두 성립할 때 이를 동치류라고 부른다.\
  • 대칭관계 – 임의의 x , y ∈ X, 만약 x ~ y 라면, y ~ x인 관계
  • 반사관계 – 임의의 x ∈ X, x ~ x인 관계
  • 추이관계 - 임의의 x , y, z ∈ X 만약 x ~ y 이고 y ~ z인 관계 x ~ z
• 문제의 집합 R의, (0,3)과 (3,0)은 대칭관계에 있는 동치류이고 (0,0)과 (1,1), (2,2), (3,3)은 반사관계에 있는 동치류이다.