[이산수학] 명제와 논리

 

---

이산수학

저자

박주미 지음

출판사

한빛미디어 | 2011-08-29 출간

카테고리

컴퓨터/IT

책소개

논리적 사고를 높여주는 예제로 배우는『이산수학』. 컴퓨터 연산을...

---

 

˚ 명제

1. 명제(Proposition)

참(Ture)인지 거짓(False)인지를 명확하게 판별할 수 있는 문장이나 수식 : p,q,r, …로 표현

 

2. 진릿값(Truth Value)

참이나 거짓을 가르키는 말 : 0, 1

 

3. 논리 연산자(명제의 결합)

1) NOT    부정(Negation) : 'not p' or 'p의 부정'

문장 p가 명제일 때 ~p, ￢p도 명제.

2) AND    논리곱(Conjunction) : 'p and q' or 'p 그리고 q'

p, q 모두 T 일 때 p∧q는 T

3) OR    논리합(Disjunction) : 'p or q', 'p 또는 q'

p, q 모두 F 일 때만 F, p∨q

4) XOR     배타적 논리합(Exclusive OR) : 'p ⊕ q'

p, q 진릿값이 하나만 T일 때 T, 그 외는 모두 F

 

4. 합성 명제(명제의 합성)

1) 합성명제(Compound Proposition)

하나 이상의 명제들이 논리 연산자를 이용해 결합된 명제.

우선순위	논리 연산자
1  2  3	￢  ∨, ∧  →, ↔

2) 항진명제(Toutology)     T

합성명제를 구성하는 명제의 진릿값에 상관없이 합성명제의 진릿값이 항상 T인 명제.

3) 모순명제(Contradicion)    F

합성명제를 구성하는 명제의 진릿값에 상관없이 합성명제의 진릿값이 항상 F인 명제.

4) 사건명제(Contingency)

항진명제도, 모순명제도 아닌 명제.

 

5. 함축(조건명제)

1)함축(Implication) / 조건명제(Conditional Proposition)    p→q

"비가 오면 우산을 가지고 간다."는 "비가 온다"라는 조건과 "우산을 가지고 간다"라는 결론이 된다.

이와 같이 조건과 결론의 관계로 결합된 형태를 함축, 조건명제라고 한다.

˚ p implies q : p는 q를 함축한다.

˚ if p then q 또는 p only if q : p면 q다.

＊p가 T일 때 반드시 q가 T이면 "p is sufficient for q(p는 q의 충분조건이다)",

   "q is necessary for p(q는 p의 필요조건이다)"라고 하고 p⇒q로 표기한다.

[표] 함축 p→q의 진리표

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

 

2)쌍방조건명제(Biconditional) p↔q

p, q가 조건이면서 결론인 명제.

˚ p if and only of q : p면 q고, q면 p다.

* p⇒q와 같이 모두 T일 경우 p⇔q, q⇔p(q는 p의 필요충분조건)이다.

[표] 함축 p↔q의 진리표

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

 

6. 역, 이, 대우

역(Converse) : p→q의 역은 q→p

이(Inverse) : p→q의 이는 ￢p→￢q

대우(Contraposition) : p→q의 대우는 ￢q→￢p

[표] 함축 p→q의 역, 이, 대우 진리표

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

 

˚ 논리적 동치

1. 명제와 논리적 동치

1) 논리적 동치(Logical Equivalence)    p≡q

p, q의 진릿값이 서로 같은 경우

"p와 q는 같다", "p와 q의 진릿값은 같다"라고 읽는다.

2) 논리적 동치법칙

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

예제) 논리적 동치법칙을 이용해 합성명제 {p∧[￢(￢p∨q)]}∨(p∧q)≡p 가 동치임을 보여라.

풀이) {p∧[￢(￢p∨q)]}∨(p∧q)≡p

[p∧(￢(￢p)∧￢q)]∨(p∧q)≡p    드모르간의 법칙

[p∧(p∧￢q)]∨(p∧q)≡p    이중부정의 법칙

[(p∧p)∧￢q]∨(p∧q)≡p    결합법칙

(p∧￢q)∨(p∧q)≡p    멱등법칙

p∧(￢q∨q)≡p    분배법칙

p∧T≡p    부정법칙

p≡p    항등법칙

 

˚ 변수를 포함한 명제와 한정자

1. 명제함수

1) 명제함수(Propositional Function)    P(x)

논의영역 D에 속하는 변수 x를 포함하여 진릿값을 판별할 수 있는 문장.

2) 논의영역(Universe of Discourse)

명제에 포함된 변수 x가 속하게 될 범위

 

2. 한정자(Quantifier)

1) 전칭기호 or 전체한정자(Universal Quantifier)    ∀

논의영역에 속하는 모든 값을 의미

˚ 논의영역 U에 속하는 모든 x에 대해 명제 P(x)는 참 : ∀xP(x)

2) 존재기호 or 존재한정자(Existential Quantifier)    ∃

논의영역에 속하는 어떤 값을 의미

˚ 논의영역 U에 속하는 어떤 x에 대해 명제 p(x)는 참 : ∃xP(x)

 

예제) 다음 표현을 문장으로 서술하라.

(1) ￢(∀xP(x))    (2) ∃x(￢P(x))    (3) ∃x(∀yP(x,y))    (4) ∀x∀yP(x,y)

풀이)

(1) ￢(∀xP(x)) : 모든 x에 대해 P(x)를 만족하지 않는다.

(2) ∃x(￢P(x)) : P(x)가 성립하지 않는 어떤 x는 존재한다.

(3) ∃x(∀yP(x,y)) : 모든 y에 대해 P(x,)를 만족하는 어떤 x는 존재한다.

(4) ∀x∀yP(x,y) : 모든 x에 대해 모든 y가 P(x,y)를 만족한다.

 

˚ 논리

1. 논리와 추론

1) 추론(Inference)

기존의 명제들로부터 결과를 유도해 나가는 과정. 이때 명제들의 참값은 알고 있거나 가정된다

2) 가정 or 전제(Hypothesis), 결론(Conclusion)

근거가 되는 명제가 가정 또는 전제가 되고, 전제로부터 유도되는 명제를 결론이라 한다.

 

2. 정당한 추론(유효추론)

주어진 전제에 의해 유도된 결론이 T이면 "정당한 추론(유효추론)"이라 하고,

그렇지 않은 추론을 "부당한 추론(허위추론)"이라 한다.

 

3. 논리적 추론법칙

법칙 이름	추론법칙	항진명제
논리곱 (Conjunction)	p q ∴ p∧q	없음
선언적 부가 (Disjunctive Addition)	p ∴ p∨q	p→(p∨q)
단순화 (Simplication)	p∧q ∴ p	(p∧q)→p
긍정논법 (Modus Pnens)	p p→q  ∴ q	[p∧(p→q)]→q
부정논법 (Modus Tollens)	￢q p→q ∴￢p	[￢q∧(p→q)]→￢p
선언적 삼단논법 또는 소거 (Disjunctive Syllogism)	p∨q ￢p ∴q	[(p∨q)∧￢p]→q
가설적 삼단논법 또는 추이 (Hypothetical Syllogism)	p→q q→r ∴ p→r	[(p→q)∧(q→r)]→(p→r)

*항상 정당하기 때문에 어떠한 전제가 주어졌을 때 결론을 유도해내는 과정에서 사용할 수 있다.