[이산수학] 명제와 논리

논리연산자

---

• 논리곱(conjunction, AND, ∧): 명제 p, q에 대해서 'p 그리고 q'를 의미한다. 명제 p, q 모두 참(T)일 때만 결과가 참(T)인 연산이다.
• 논리합(disjunction, OR, ∨):  명제 p, q에 대해서 'p 또는 q'를 의미한다. 명제 p, q 중 하나라도 참(T)이면 결과가 참(T)인 연산이다.
• 부정(negation, NOT, ￢): 참(T)인 명제를 거짓(F)으로, 또는 그 반대로 바꾸는 연산이다.
• 배타적 논리합(exclusive or, XOR, ⊕): 두 명제 p, q의 진리값 중 하나만 참(T)일 때 결과가 참이고, 그 외에는 모두 결과가 거짓인 연산이다. p ⊕ q ≡ (￢p ∧ q) ∨ (p ∧￢q)이다. ≡는 논리적 동치라는 의미이다.
• 논리 함축(implication, →): 조건명제라고도 하며, 명제 p, q에 대해서 명제 p가 전제 또는 가정이고 명제 q가 결론 또는 결과인 명제이다. p→q를 'p이면 q이다' 또는 'p는 q를 함축한다'라고 한다. p→q ≡ ￢p ∨ q이다.

명제에서는 명제의 의미나 구조와 관계없이 오직 명제들의 진리값만을 다루기 때문에 논리 함축 p → q는 p와 q가 서로 연관이 없을지라도 임의의 두 명제를 결합할 수 있다. 자연 언어에서의 "~하면 ~한다."같이 가정과 결론 사이의 인과 관계를 나타내는 것과는 다르다. 논리함축의 진리표는 다음과 같다.

p	q	p→q
T	T	T
T	F	F
F	T	T
F	F	T

p가 참(T)이고 q가 거짓(F)일 때만 p→q는 거짓(F)이 된다.

• 역(converse): 조건명제 p→q에 대하여, q→p 형태의 명제이다.
• 대우(contraposition): 조건명제 p→q에 대하여, ￢q →￢p 형태의 명제이다.
• 이(inverse): 조건명제 p→q에 대하여, ￢p →￢q 형태의 명제이다.
• 동치(equivalence, ↔): 쌍방조건명제라고도 하며, 명제 p, q가 모두 전제이면서 동시에 결론인 명제이다. p와 q가 모두 참이거나 모두 거짓일 경우에만 참이 되고, 그 이외의 경우에는 모두 거짓이 된다. p↔q ≡ (p→q) ∧ (q→p)이다. 쌍방조건명제의 진리표는 다음과 같다.

p	q	p↔q
T	T	T
T	F	F
F	T	F
F	F	T

 

합성명제

---

논리 연산자의 우선순위는 다음과 같다.

우선순위	논리 연산자
1	￢ (부정)
2	∧ (논리곱)
3	∨ (논리합)
4	→ (논리함축)
5	↔ (쌍방조건명제)

연산자 우선순위와 결합법칙을 이용해 합성명제의 연산자의 우선순위를 정한다. 이를 따라 합성명제에 대해 진리표를 작성한다.

합성명제의 종류는 다음과 같다.

• 항진명제(tautology: T): 합성명제를 구성하는 단순명제의 진리값에 상관없이 합성명제의 진리값이 항상 참(T)인 명제이다.
• 모순명제(contradiction: F): 합성명제를 구성하는 단순명제의 진리값에 상관없이 합성명제의 진리값이 항상 거짓(F)인 명제이다.
• 사건명제(contingency): 항진명제 모순명제도 아닌 합성명제이다.

 

논리적 동치법칙

---

논리적 동치를 판별하는 방법으로는 진리표를 이용하는 방법과 논리적 동치법칙을 이용하는 방법이 있다. 진리표를 이용하면 모든 명제에 대해 동치인지 판별할 수 있지만 법칙을 알고 있으면 편리하게 동치인지 판별할 수 있다. 대표적인 논리적 동치 법칙은 다음과 같다.

논리적 동치		법칙
p∧True≡p	p∨False≡p	항등법칙 (Identity Laws)
p∧False≡False	p∨True≡True	지배법칙 (Domination Laws)
p∧¬p≡False	p∨¬p≡True	부정법칙 (Negation Laws)
¬(¬p)≡p		이중부정법칙 (Double Negation Law)
p∧p≡p	p∨p≡p	멱등법칙 (Idempotent Law)
p∧q≡q∧p	p∨q≡q∨p	교환법칙 (Commutative Laws)
(p∧q)∧r≡p∧(q∧r)	(p∨q)∨r≡p∨(q∨r)	결합법칙 (Associative Laws)
p∨(q∧r)≡(p∨q)∧(p∨r)	p∧(q∨r)≡(p∧q)∨(p∧r)	분배법칙 (Distributive Laws)
¬(p∧q)≡¬p∨¬q	¬(p∨q)≡¬p∧¬q	드 모르간의 법칙 (De Morgan's Laws)
p∧(p∨q)≡p	p∨(p∧q)≡p	흡수법칙 (Absorption Laws)
p→q≡¬p∨q		함축법칙 (Implication Laws)

 

추론

---

추론 또는 논증은 참(T)인 명제를 근거로 하여 다른 명제가 참(T)임을 유도하는 과정 또는 방식을 말한다. 추론의 전제는 결론의 근거가 되는 참(T)인 명제를 말하고 결론은 주어진 전제에 의해 유도된 최종적인 참(T)인 명제를 말한다.

추론의 종류에는 크게 두 가지가 있다.

• 유효추론 (Valid Inference): 진리값이 참(T)인 주어진 전제를 이용하여 유도한 결론이 모두 참(T)인 추론이다. 주어진 명제(가정과 전제)가 참이고 결론도 참인 추론을 말한다.
• 허위추론 (Fallacious Inference): 진리값이 참(T)인 주어진 전제를 이용하여 유도한 결론이 거짓(F)인 추론이다.

 

논리적 추론을 할 때 가장 기본 법칙은 다음과 같다.

법칙 이름	추론	항진명제
논리곱 (Conjunction)	p q ∴p∧q	(p∧q)→(p∧q)
선언적 부가 (Disjunctive Addition)	p ∴p∨q	p→(p∨q)
단순화 (Simplication)	p∧q ∴p (또는 q)	(p∧q)→p (또는 q)
긍정논법 (Modus Ponens)	p p→q ∴q	{p∧(p→q)}→q
부정논법 (Modus Tollens)	¬q p→q ∴¬p	{¬q∧(p→q)}→¬p
선언적 삼단논법 또는 소거 ( Disjunctive  Syllogism)	p∨q ¬q ∴p	{(p∨q)∧¬q} →p
가설적 삼단논법 또는 추이 (Hypothetical Syllogism)	p→q q→r ∴p→r	{(p→q)∧(q→r)} →(p→r)
구성적 양도 논법 (Constructive Dilemma)	(p→q)∧(r→s) p∨r ∴q∨s	[(p→q)∧(r→s)∧(p∨r)]→(q∨s)
파괴적 양도 논법 (Destructive Dilemma)	(p→q)∧(r→s) ¬q∨¬s ∴¬p∨¬r	[(p→q)∧(r→s)∧(¬q∨¬s)]→(¬p∨¬r)

 

궁금한 것이나 잘못된 것이 있다면 댓글에 남겨주세요!