명제(proposition)란 어떤 사고를 나타내는 문장 중에서 참(true)이나 거짓(false)을 객관적이고 명확하게 구분할 수 있는 문장이나 수학적 지식을 말한다.
명제는 통상 소문자로 표시하고 각각의 진리값(Truth value)을 가진다.
이때 명제는 T(true)와 F(false)의 2가지 진리값을 가지므로 이진 논리라고 한다.
논리 연산
단순 명제 : 하나의 문장이나 식으로 구성되어 있는 명제
ex) 개는 동물이다.
합성 명제 : 여러 개의 단순 명제들이 논리 연산자들로 연결되어 만들어진 명제
ex) 개는 동물이고, 사슴벌레는 곤충이다.
논리학에서의 논리 연산자
~ (부정, NOT)
∧ (논리곱, AND)
∨ (논리합, OR)
⊕ (배타적 논리합, Exclusive OR)
→ (조건, if ... then)
↔ (쌍방 조건, if and only if (iff))
부정(negation)의 진리표
| p | ~p | ~(~p) |
| T | F | T |
| F | T | F |
임의의 명제 p가 주어졌을때 그 명제에 대한 부정은 명제 p의 반대되는 진리값을 가진다.
기호로는 ~p라 쓰고 'not p 또는 p가 아니다'라고 읽는다.
논리곱(conjunction, AND)의 진리표
| p | q | p ∧ q |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
임의의 두 명제 p, q가 '그리고(AND)'로 연결되어 있을 때 명제 p, q의 논리곱(conjunction)은
p ∧ q 형태로 표시하며. 'p and q 또는 p 그리고 q'라고 읽는다.
논리곱은 해당하는 명제들이 모두 참인 경우에만 참의 진리값을 가지며
그렇지 않으면 거짓의 진리값을 가진다.
논리합(disjunction, OR)의 진리표
| p | q | p ∨ q |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
논리합의 표시는 p ∨ q 의 형태로 표시하며, p or q 또는 p 또는 q라고 읽는다.
두 명제의 논리합 p ∨ q는 두 명제가 모두 거짓인 경우에만 거짓의 진리값을 가진다.
배타적 논리합(Exclusive OR, XOR)의 진리표
| p | q | p ⊕ q |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
배타적 논리합의 진리값은 p와 q 두 명제 중에서 하나의 명제가 참이고 하나는 거짓일 때
참의 진리값을 가지고 그렇지 않으면 거짓의 진리값을 가진다.
조건(함축, implication)의 진리표
| p | q | p → q |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
조건 연산자를 함축(implication)이라고도 한다.
임의의 명제 p, q에 대해서 p이면 q라면
p는 q에 대한 조건으로써의 함축적인 의미를 지니고 있기 때문이다.
조건의 진리표에서는 p가 참일 때 q가 거짓인 경우에만 거짓이다.
조금 헷갈릴수가 있는데
내가 시험점수 90점을 넘기면 교수님이 A학점을 준다. 고 가정해보자.
1. 이때 내가 90점을 넘겨서 A학점을 받으면 이치에 어긋나지 않는다. (참)
2. 90점을 넘겼는데 교수님이 A학점을 주지 않으면 그것은 이치에 맞지 않는다. (거짓)
3. 90점을 못넘겼는데 교수님이 A학점을 주셨다. 이치에 어긋나는건 없다. (참)
4. 90점을 못넘겨서 A학점을 주시지 않으셨다. (참)
조건 연산자의 또 다른 풀이로는
a) p이면 q이다 ( if p, then q )
b) p는 q의 충분조건이다. (p is sufficient for q)
c) q는 p의 필요조건이다. (q is necessary for p)
d) p는 q를 함축한다. (p implies q)
p는 q의 충분조건이라는 의미는
q가 일어나기 위해서는 p가 어느정도 필요할 수는 있지만 그것이 절대적이지는 않다는 의미로 해석할 수 있다.
반면 q는 p의 필요조건이라 함은 p가 참인데 q가 거짓이면 그 진리 자체가 거짓이 된다.
따라서 q는 p의 필요조건이다. (p가 참이면 q가 반드시 성립해야해서 q는 p의 필요조건이다.)
쌍방 조건의 진리표
| p | q | p ↔ q |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
쌍방조건은 p이면 q이고, q이면 p이다. 라는 의미이다.
(p if and only if q, p는 만약에 그리고 오로지 q일 경우에만)
또한 p는 q의 필요충분조건이다. (p is necessary and sufficient for q)
(표로써도 이해는 가는데 사례를 찾기가 좀 어려운 것 같다.)
'했던것들 > 이산수학' 카테고리의 다른 글
| 프로그램의 입증 (0) | 2022.05.25 |
|---|---|
| 여러가지 증명법 (0) | 2022.05.25 |
| 연역법(deduction)과 귀납법(induction) (0) | 2022.05.25 |
| 집합(set) (0) | 2022.05.24 |
| 술어 논리(predicate logic) (0) | 2022.05.23 |
