이산수학이란
이산수학 강좌 1강 - 이산수학 개요 (Discrete Mathematics Tutorial For Beginners #1)
- 실수 같이 연속적인 성질이 있는 대상이 아닌 주로 정수, 그래프, 논리 연산 같이 서로 구분되는 값을 가지는 대상을 연구한다.
- 컴퓨터 알고리즘, 프로그래밍 언어, 암호학, 자동 이론 증명, 소프트웨어 개발 등의 문제를 다루는 데에 유용하다. 명제와 연산자
이산수학 강좌 2강 - 명제와 연산자 (Discrete Mathematics Tutorial For Beginners #2)
명제 : 진실 혹은 거짓
- 참(True) 혹은 거짓(False)으로 진리를 구분할 수 있는 문장
- 명제는 0 또는 1만을 가지는 컴퓨터 메모리처럼 항상 참과 거짓 둘 중 하나의 값만을 가진다.
- 여러 개의 명제를 조합할 수 있다.
- 라이언은 잘생겼다 ☞ 명제가 아니다. (참 거짓 규정이 힘들다 / 개개인의 주관이 개입)
- 2는 소수이다 ☞ 명제이다. (참)
- 코딩은 재미있다 ☞ 명제가 아니다. (참 거짓 규정이 힘들다 / 개개인의 주관이 개입)
- 모기는 식물이다 ☞ 명제이다. (거짓)
연산자 : 명제를 연산하기 위한 도구
- 이산수학의 기본 연산자로는 6가지가 있다.
- 각 연산자는 컴퓨터 분야에서 굉장히 많이 사용된다.
1. Not, 부정 ( ￢ )
- p : 참
- ￢p : 거짓
2. And, 논리곱 ( ^ )
- p, q 모두 참일 경우에만 p ^ q가 참이다. 그 외에는 모두 거짓이다.
p : 참, q : 참일 때,
p ^ q => 참
3. Or, 논리합 ( v )
- p, q 모두 거짓일 경우에만 p v q가 거짓이며, 그 외에는 모두 참이다.
p : 거짓, q : 거짓일 때,
p v q => 거짓
4. Exclusive or, 배타적 논리합 ( ⊕ )
- p와 q가 같다면, p ⊕ q => 거짓
p와 q가 다르다면, p ⊕ q => 참
5. Implication, 조건명제 ( → )
- 다음과 같은 표현은 모두 p -> q의 형태로 기호화 할 수 있다.
(만일) p이면 q이다.
p는 q의 충분조건이다.
q는 p의 필요조건이다.
- 자백한 증명 : q가 참일 때, p -> q는 p의 값과 관계없이 참이다.
- 무위의 증명 : p가 거짓일 때, p -> q는 q의 값과 관계없이 항상 참이다.
- 직접 증명 : p -> q가 참임을 가정하고, q가 참임을 타당한 추론으로 밝힌다.
- 간접증명 - 대우 : p -> q의 동치식 ~q -> ~p를 이용하여 증명한다.
즉, q가 거짓이라 가정 후, p가 거짓임을 타당한 추론에 의해 증명.
- 간접증명 - 모순에 의한 증명 : p -> q에서 p가 참이고 q가 거짓이면 모순이 생김을 보인다.
6. Biconditional, 쌍조건문 ( ↔ )
- p -> q 라는 명제와, q -> p라는 두 명제가 있을 때, 이 두 명제를 합하면
p -> q이고, q -> p이다. 라는 명제가 나온다. 이러한 것을 쌍조건문이라 한다..