[패캠강의] 이산수학 - ch1. 집합과 논리, ch2. 증명

 

1. 집합

 

여러 원소들의 모임이다.

• 중복된 원소를 갖지 않는다.
• 순서를 갖지 않는다.

원소 나열법 : A = {1, 2, 3} / 조건제시법 : A = {x | 0 < x <= 10, x는 양의 정수}

 

집합 A에 속하는 원소의 개수는 |A|로 표기한다.

 

 

부분집합과 진부분집합

집합 A의 모든 원소가 집합 B에 포함될 때, 집합 A는 집합 B의 부분집합이라 한다.

집합 A가 집합 B의 부분집합이지만, A=B는 아닐 경우 A는 B의 진부분집합이라 한다.

 

서로소

집합 A와 집합 B에 공통으로 속한 원소가 하나도 없는 경우 집합 A와 집합 B는 서로소라고 한다.

 

 

---

 

2. 논리와 명제

 

논리 연산자

각 명제 p와 q에 대하여,

• p ∧ q : p and q, 논리곱
• p ∨ q : p or q, 논리합

 

명제

참이나 거짓을 판단할 수 있는 문장이나 수식

 

조건명제

p -> q, p가 가정이고 q가 결론이 되는 명제이다.

조건명제 p -> q의 진리값은 p가 거짓일 경우 항상 참이고, p가 참일 경우 q의 진리값과 일치한다.

즉 p가 거짓일 때 p -> q의 진리값은 항상 참으로 정의한다.

 

 

명제함수와 한정자(quantifier)

 

명제함수 P(x)

변수 x를 포함한 명제

ex) P(x)가 x + 1 = 0

 

전체한정자 ∀, for every

모든 값에 대하여 라고 표현할 때 쓴다.

∀xP(x) 는 다루는 모든 x에 대하여 참인 경우 참인 명제가 된다.

 

존재한정자 ∃, there exists

어떤 값이 존재하여 라고 표현할 때 쓴다.

∃xP(x)는 P(x)가 참이 되는 x가 하나라도 있을 경우 참인 명제가 된다.

 

 

---

3. 증명

 

용어

 

공리(Axiom)

별도의 증명없이 항상 참으로 이용되는 명제

 

정의(Definition)

용어 또는 기호의 의미를 확실하게 규정한 문장이나 식

ex) n! = n x (n-1) x ... x 1

 

정리(Theorem)

공리와 정의를 통해 참으로 확인된 명제

 

증명(Proof)

명제가 진리값을 확인하는 과정

 

 

증명방법

직접 증명

p -> q를 증명하기 위해서 p를 참이라 가정한 상태에서 q도 참임을 증명

 

ex) 짝수와 홀수를 더하면 홀수가 됨을 보여라

 

p: 숫자 m은 짝수이고 숫자 n은 홀수이다.

q: m+n은 홀수이다.

 

 

반례증명법

주어진 명제에 모순이 되는 예를 찾아서 명제가 거짓임을 증명

 

모순증명

결론을 부정하였을 때 모순이 발생함을 보여 결론이 성립함을 증명

ex) √2 는 무리수임을 증명

√2가 유리수 라면, 정의에 의해 √2 = a/b이며 a와 b는 서로 소이다.

a^2 = 2*b^2 이므로 a^2은 2의 배수이다. 따라서 a는 짝수이며, a = 2k라고 나타낼 수 있다.

그러면 4*k^2 = 2*b^2, 2*k^2 = b^2이므로 b^2도 2의 배수 이며, b도 짝수이다.

a, b 둘다 짝수인 것은 a와 b는 서로소라는 정의에 모순이다.

따라서 √2는 무리수이다.

 

동치증명

주어진 명제와 동치(대우)인 명제를 증명하여 본 명제가 참 임을 증명

 

 

 

수학적 귀납법

자연수 n에 대하여 정의된 명제함수 P(n)에 대하여 기본가정, 귀납가정이 참임을 보이는 증명

(1) 기본가정 : n=1일 때 , P(1)은 참이다.

(2) 귀납가정 : 어떤 자연수 k에 대하여 P(k)가 참일 경우, P(k+1)이 참임을 보인다.

 

자연수 n에 대하여 증명하므로, 이산수학에 알맞은 증명법이다.

 

ex) 자연수 n에 대해서 1부터 n까지의 합이 n(n+1)/2임을 증명

 

n=1 일때 1(1+1)/2 = 1 <참>

자연수 k에 대해 1부터 k까지의 합은 k(k+1)/2

1부터 k+1까지의 합은 k(k+1)/2 + (k+1)

이것은 (k+1)(k+2)/2 이다. <k+1에 대하여 참>

 

 

---

1. 패스트 캠퍼스 - 한 번에 끝내는 컴퓨터 공학 전공필수 & 인공지능 심화 초격차 패키지 Online.

Part2. 이산수학 - 강승현 강사님