1. 이산수학 개요
이산수학(Discrete Mathematics) 개념
- 컴퓨터를 위한 수학
- 참과 거짓으로 살펴보는 컴퓨터 수학
이산수학을 배우는 이유
이산수학이란 불연속적인 숫자를 다루는 수학이다. 컴퓨터 내부적으로 0과 1만을 다루는 데 그러한 불연속적인 데이터 흐름을 다루기에 적합한 수학적 사고를 배양하는데 필수적인 강의라고 할 수 있다. 또한 이산수학에서는 다루는 내용이 자료구조, 알고리즘 등의 베이스가 되어 전체적인 컴퓨팅 사고력을 길러줄 것이다. 그리고 추후 수학적 귀납법 등의 다양한 기초 개념이 알고리즘에 반복적으로 출현하기 때문에 컴퓨터 과학의 베이스 학문 이라고 할 수 있다.
2. 명제
명제 (Proposition) 개념
- 진실 혹은 거짓을 말한다.
- 참(True)이나 거짓(False)으로 진리를 구분할 수 있는 문장
- 명제는 0또는 1만을 가지는 컴퓨터 메모리처럼 항상 참과 거짓 둘 중 하나의 값만을 가진다.
- 여러 개의 명제를 조합할 수 있다.
ex) 명제란 참 혹은 거짓으로 진리를 명확히 구분할 수 있는 문장입니다. 다음의 문장들이 명제인지 아닌지 확인하세요.
- 원빈은 잘생겼다. X
- 컴퓨터는 재미가 없다. X
- 11은 소수이다. O(참)
- 모기는 동물이다. O(참)
연산자로 명제 다루기
- 연산자는 명제를 연산하기 위한 도구
- 이산수학의 기본 연산자로는 6가지가 있다.
- 각 연산자는 컴퓨터 분야에서 굉장히 많이 사용된다.
- 합성명제 : 연산자를 이용해 여러 개의 명제를 합친 명제
- 조건명제 : 원인이 되는 명제와 결과가 되는 명제가 존제하는 명제
1. Not, 부정( ￢ )
거짓을 참으로,참을 거짓으로 바꿀수 있는 연산자로 p를 참이라 했을때 ￢p는 거짓이 된다.
| P | ￢P | ￢(￢P) |
| T | F | T |
| F | T | F |
2. And, 논리곱( ^ )
둘다 참값일 때만 참값을 가지는 연산자 그렇지 않은 경우 거짓이 된다.
| P | Q | P^Q |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
3. Or, 논리합( v )
둘중 하나라도 참이면 참값을 반환한다.
| P | Q | PvQ |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
4. Exclusive or, 베타적 논리합( ⊕ )
두 명제중 하나의 명제만 참일때 참인 결과값을 반환한다.
| P | Q | P⊕Q |
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
5. Implication, 조건문( → )
조건과 결과에 따른 흐름을 나타낼때 사용한다. 임의의 두 명제 (P,Q)에 대해서 P가 참이면 Q도 참이다.
즉, P가 참인데 Q가 거짓이면 거짓이되고, P가 거짓이면 Q가(참,거짓) 무엇이 되어도 참을 반환한다.
| P | Q | P→Q |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
6. Biconditional, 상호 조건문( ↔︎ )
임의의 두 명제(P,Q)에 대해서 P이면 Q이고, Q이면 P이다. 즉 두 명제가 동일한 진리값을 가질때 참이된다.
| P | Q | P↔︎Q |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
3. 역, 이, 대우
진리표 (Truth-Table) 개념
각 명제 사이의 관계식의 진릿값을 보여주는 표이다. 아무리 복잡한 합성 명제라도 진리표로 풀어낼 수 있다.
| P | Q | ~P | ~Q | P→Q | ~P→~Q | Q→P | ~Q→~P |
| T | T | F | F | T | T | T | T |
| T | F | F | T | F | T | T | F |
| F | T | T | F | T | F | F | T |
| F | F | T | T | T | T | T | T |
역, 이, 대우
- 역, 이, 대우는 조건명제에서 사용한다.
- 역, 이, 대우는 하나의 명제를 변형해 표현한다.
- 증명하기 어려운 명제는 대우를 이용해 증명할 수 있다.
- 대우가 참일때 원래 명제도 참이 되는 중요한 특성이 있다.
| P | Q | P→Q | Q→P | ￢P→￢Q | ￢Q→￢P |
| T | T | T | T | T | T |
| T | F | F | T | T | F |
| F | T | T | F | F | T |
| F | F | T | T | T | T |
4. 동치
동치 개념
- 두개의 명제값이 같은 논리값을 가지고 있을때 두 명제값을 동치라고 한다.
- 동치란 '논리적으로 일치한다'는 의미이다.
- 흔히 동치는 같은 의미를 가진 더 쉬운 명제를 발견하는 데 사용한다.
- 동치법칙에는 다양한 종류가 있다.
논리적 동치
| 논리적 동치 | 법칙 |
| P ^ T ≡ P P v F ≡ P |
항등 법칙(Identity Laws) |
| P v T ≡ T P ^ F ≡ F |
지배 법칙(Domination Laws) |
| P v P ≡ P P ^ P ≡ P |
멱등 법칙(Idempotent Laws) |
| ￢(￢P) ≡ P | 이중 부정 법칙(Double negation Laws) |
| P v Q ≡ Q v P P ^ Q ≡ Q ^ P |
교환 법칙(Communicative Laws) |
| (P v Q) v R ≡ P v (Q v R) | 결합 법칙(Associative Laws) |
| P v (Q ^ R) ≡ (P v Q) ^ (P v R) | 분배 법칙(Distributive Laws) |
| ￢ (P ^ Q) ≡ ￢P v ￢Q | 드모르간 법칙(De Morgan's Laws) |
| P v (P ^ Q) ≡ P | 흡수 법칙(Absorption Laws) |
| P v ￢P ≡ T | 부정 법칙(Negation Laws) |
