제 2 절 항진명제와 모순명제
이 절에서는 명제에서 중요한 역할을 하는 항진명제와 모순명제에 대해 알아보 기로 하자. 항진명제와 모순명제는 명제 연산에서 항등원의 역할을 하기도 한 다.
정 의 1.23 모든 경우에 대해 항상 참인 명제를 항진명제(tautology)라
하고 “t”로 나타낸다.
모든 경우에 항상 거짓인 명제를 모순명제(contradiction)라 하고 “c”로 나 타낸다.
[[ 예 ]] 1.24 (1) 명제 p ∨ ∼ p는 항진명제이다. 따라서
p∨ ∼ p ≡ t.
(2) 명제 p ∧ ∼ p는 모순명제이다. 따라서
p∧ ∼ p ≡ c.
참 고 1.25 항진명제와 모순명제는 성분명제의 진리값과 상관이 없고 명제 자체가 가지고 있는 구조에 의해 결정된다. 예를 들어 항진명제
p∨ ∼ p 의 성분 p 대신에 r → s를 대입하여 얻어진 명제
(r → s) ∨ ∼ (r → s)
도 항진명제가 된다. 뿐만 아니라 p 대신 어떤 명제를 대입하여도 항진명제가 된다.
[[ 예 ]] 1.26 명제 [(p → q) → r]∨ ∼ [(p → q) → r]가 항진명제가 됨을 보 여라.
풀이. 항진 명제 p ∨ ∼ p 에서 p 대신에 (p → q) → r을 대치한 명제이므 로 항진명제가 된다.
정 의 1.27 조건문 P → Q가 항진명제가 될 때 “P 는 Q를 함
의(implies)한다”라고 하고
P =⇒ Q 로 나타낸다.
쌍조건문 P ↔ Q가 항진명제가 될 때 “P 는 Q와 동치(equivalent)이다”라 고 하고
P ⇐⇒ Q 로 나타낸다.
참 고 1.28 쌍조건문의 진리표를 살펴보면 P ↔ Q가 항진명제가 되려면 모든 경우에 대해 P 와 Q의 진리값이 일치하여야 한다.
따라서 P ⇐⇒ Q와 P ≡ Q는 같은 의미가 된다.
참 고 1.29 명제 P, Q에 대해 아래 네 가지 사실은 모두 같은 의미이다.
(1) P =⇒ Q
(2) P → Q가 항진명제이다.
(3) ∼ P ∨ Q가 항진명제이다.
(4) P ∧ ∼ Q가 모순명제이다.(∵ 예제 1.17)
정 의 1.30 P =⇒ Q일 때 P 를 Q가 되기 위한충분조건(sufficient con-
dition)이라 하고, Q를 P 가 되기 위한 필요조건(necessary condition)이 라 한다. 필요조건과 충분조건이 동시에 될 때 필요충분조건(necessary and sufficient condition)이라 한다.
참 고 1.31 P ⇐⇒ Q일 때, P 는 Q가 되기 위한 필요충분조건이다.
정 리 1.32 임의의 명제에 대해 아래 사실이 성립한다.
(1) 합의 법칙(law of addition) p =⇒ p ∨ q.
(2) 단순화법칙(law of simplification) p ∧ q =⇒ p, p ∧ q =⇒ q.
(3) 추이법칙(transitive law)
(p→ q) ∧ (q → r) =⇒ p → r.
(4) 선언지제거법(disjunctive syllogism) (p ∨ q) ∧ ∼ p =⇒ q,
(p ∨ q) ∧ ∼ q =⇒ p.
(5) 삼단긍정법(modus ponens)
(p→ q) ∧ p =⇒ q.
(6) 삼단부정법(modus tollens) (p→ q) ∧ ∼ q =⇒∼ p.
증명. 대응하는 조건문 명제가 항진명제임을 보이면 된다. 즉, (4)의 경우 명 제 (p ∨ q) ∧ ∼ p → q가 항진명제임을 보이면 된다.