[Discrete Mathematics] p.1-11
○ 명제 (Propositions)
명제는 참과 거짓 중 하나를 나타내는 선언문이다. (A proposition is a declarative sentence that is either true or false)
논리의 기본적인 구성요소다.
● 올바른 명제 예시
1) The Sun is made of cheese.
2) 대한민국의 수도는 서울이다.
3) 1 + 2 = 3
4) 3 + 2 = 0
모두 올바른 명제의 예시다.
1번은 태양은 치즈로 만들어지지 않았으므로 분명히 거짓인 선언문이다.
2번은 대한민국의 수도는 서울이므로 참인 선언문이다.
3번은 참인 수식이므로 선언문이다.
4번은 거짓인 수식이므로 선언문이다.
수식도 선언문이다.
● 잘못된 명제 예시
5) Shut up!
6) 이거 얼마에요?
7) x + 3 = 5
8) x + y = z
모두 잘못된 명제의 예시다.
5번은 명령문이므로 참, 거짓이 없어 선언문이 아니다.
6번은 의문문이므로 참, 거짓이 없어 선언문이 아니다.
7번, 8번은 방정식으로 선언문이 아니다.
명령문과 의문문, 방정식은 선언문이 아니다.
또한 참과 거짓으로 구분할 수 없다면 역시 선언문이 아니다.
○ 명제 논리 (Propositional Logic)
명제를 다루는 논리를 명제 산술(Propositional calculus) 또는 명제 논리(Propositional logic)라고 한다.
명제 변수(또는 문장 변수, Propositional Variables)는 소문자 알파벳으로 표기한다. (p, q, r, s, ...)
참인 명제는 T로 나타내고, 거짓인 명제는 F로 나타낸다.
● 복합 명제 (Compound Propositions)
하나 또는 여러개의 명제를 조합하여 새로운 명제를 만든 것
논리적 연결과 다른 명제로 이루어져 있다.
논리 연산자를 이용하여 기존의 명제들로부터 만든다.
※ 논리 연산자(Connecter)
- 부정 (Negation) : ¬
- 논리곱 (Conjunction) : ∧
- 논리합 (Disjunction) : ∨
- 함축 (또는 조건문, Implication) : →
- 상호 함축 명제 (또는 상호 조건문, Biconditional statement) : ↔
● 부정 (Negation)
p가 명제라고 하면 p의 부정(negation)은 ¬p(또는p ̅, !p 등) 으로 표기된다.
"not p" 혹은 "p의 부정" 이라고 읽는다.
문장으로는 "It is not the case that p" 이다.
즉 ¬p의 진리값은 p의 반대가 된다.
※ 부정에 대한 진리표(truth table)
p가 T면 부정은 F, p가 F면 부정은 T이다.
예제)
명제 p가 "iPhone runs ios" 라면
p의 부정은 "It is not the case that iPhone runs ios" 이다.
물론 간단하게 "iPhone doesn't runs ios" 라고 표기해도 무방하다.
● 논리곱 (Conjunction)
p와 q가 명제라면, p와 q의 논리곱(conjunction)은 "p∧q" 으로 표기된다.
"p and q" 혹은 "p conjuction q" 라고 읽는다.
문장으로는 "p and q"이다.
논리곱은 p, q가 모두 참일 때만 참이며 그 외의 경우는 모두 거짓이다.
※ 논리곱에 대한 진리표(truth table)
p와 q가 모두 참이어야만 논리곱이 참이다.
예제)
명제 p가 "I am a boy"이고, q가 "It is sunny" 라면
p∧q는 "I am a boy and It is sunny" 이다.
● 논리합 (Disjunction)
p와 q가 명제라면, p와 q의 논리합(disjunction)은 "p∨q" 으로 표기된다.
"p or q" 혹은 "p disjuction q" 라고 읽는다.
문장으로는 "p or q"이다.
논리곱은 p, q가 모두 거짓일 때만 거짓이며 그 외의 경우는 모두 참이다.
※ 논리합에 대한 진리표(truth table)
p와 q가 모두 거짓이어야만 논리합이 거짓이다.
예제)
명제 p가 "I am a boy"이고, q가 "It is sunny" 라면
p∧q는 "I am a boy or It is sunny" 이다.
● 함축 (Implication)
p와 q가 명제라면, p와 q의 함축(Implication)은 "p→q" 으로 표기된다.
"p Implication q" 라고 읽는다.
문장으로는 "if p, then q"이다. (마지막에 다른 문장 표현 형태 소개)
논리곱은 p가 참이고 q가 거짓일 경우에 거짓이며, 그 외 다른 경우에는 모두 참이다.
이때 p를 가정(또는 전제, 전항)이라고 하며, q를 결론(또는 결과)라고 한다.
※ 함축에 대한 진리표(truth table)
p가 참이고, q가 거짓이어야만 함축이 거짓이다
예제)
명제 p가 "I am a boy"이고, q가 "It is sunny" 라면
p→q는 "if I am a boy, then It is sunny" 이다.
※다양한 함축 표현 (p→q)
- if p, then q
- p implies q
- if p, q
- p only if q
- p is sufficient for q
- q unless ¬p
- q when p
- q if p
- q when p
- q whenever p
- q follows from p
- q is necessary for p
- a necessary condition for p is q
- a sufficient condition for q is p
※역, 대우, 이 (converse, contra-positive, inverse)
p→q로 부터 새로운 조건문을 만들 수 있다.
● 역 (Converse)
p→q 의 역은 q→p이다. 위치를 바꿔주는 것이다.
● 대우 (Contrapositive)
p→q 의 대우는 ¬q→¬p이다. 위치를 바꿔준 뒤, 부정을 취해주는 것이다. (역+이)
● 이 (Inverse)
p→q 의 이는 ¬p→¬q 이다. 부정을 취해주는 것이다.
● 상호 함축 (Biconditional statement)
p와 q가 명제라면, p와 q의 상호 함축(Biconditional statement)은 "p↔q" 으로 표기된다.
문장으로는 "p if and only if q"이다.
상호 함축은 p와 q가 동일한 진리값을 가질 때 참이며, 그렇지 않을 경우는 거짓이다.
상호 조건문 또는 상호 함축명제라고도 불린다.
※ 상호 함축에 대한 진리표(truth table)
p와 q가 같아야 T, 다르면 F이다.
예제)
명제 p가 "I am a boy"이고, q가 "It is sunny" 라면
p↔q는 "I am a boy if and only if It is sunny" 이다.
※다양한 함축 표현 (p↔q)
- p is necessary and sufficient for q (p는 q의 필요충분 조건이다)
- if p then q, and conversely (만약 p이면 q이다. 그 반대도 성립한다)
- p if and only if q, p exactly when q
● 배타적 논리합 (Exclusive-or)
앞에서 본 5가지의 논리 연산자 외에도 다양한 연산자가 있다.
그 중에서 앞에서 본 or 은 포괄적 논리합(Inclusive or)이고
배타적 논리합(Exclusive or)도 존재한다
p와 q가 명제라면, p와 q의 배타적 논리합(Exclusive or)은 "p⨁q" 으로 표기된다.
배타적 논리합은 p와 q 중 어느 하나만이 참일 때 전체가 참이다.
즉, 둘 다 모두 참이거나 거짓이면 전체 명제는 거짓이다.
※ 상호 함축에 대한 진리표(truth table)
