신흥철 교수의 이산 수학 3, 4 강: 한정자, 논리, 2장 증명

 1장 명제 

3. 변수를 포함한 명제와 한정자

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

명제는 참과 거짓으로 판별할 수 있는 문장, 수식이다. 그런데 변수를 포함한 문장이 되려면 명제가 되려면 명제를 참이나 거짓으로 판별할 수 있는 변수의 범위(한정자, Quantifier)가 지정되어야 한다. 명제에 포함되된 변수가 속하게 될 범위를 논의 영역(Universe of Discourse - D)이라고 한다. 그리고 이 논의 영역 D에 속하는 변수 x를 포함하여 진릿값을 판별할 수 있는 문장이나 수식을 명제 함수(Propositional Function - P(x))라고 한다.

 

예제) 명제함수 P(x,y)가 x = 2y일 때, P(1,2)와 P(2,1)의 진릿값은?

P(1,2) 1 != 2 * 2 (거짓)

P(2,1) 2 == 1* 2 (참) 

값을 한정하니 참, 거짓이 지정된다.

 

한정자(Quantifier) 

논의 영역 안에서 정의된 범위를 한정자라고 한다.

• 전체 한정자(전칭 기호, Universal Quantifier) ∀
  논의 영역에 속하는 모든 값
  ∀xP(x): '논의영역 U에 속하는 모든 x에 대해 P(x)는 참'이라는 명제
  논의영역의 모든 원소에 대해 만족할 경우에만 참
• 존재 한정자(존재기호, Existential Quanrifier) ∃
  논의 영역에 속하는 어떤 값
  ∃xP(x) : '논의 영역 U에 속하는 어떤 x에 대해 P(x)의 참'이라는 명제
  논의영역의 원소 중 하나라도 만족할 경우에는 참이 된다.

예제) p = {x|0,x<=4, x는 양의 정수}인 논의 영역에 대하여 명제함수 P(x)가 x**2<10일때 다음 명제의 진릿값은?

1.∀xP(x)  2. ∃xP(x)

논의영역 D = {1,2,3,4}

1. 모든 x에 대하여 참인지를 확인하기 위해 참을 만족시켜주지 않는 특정 x값을 찾는다.

 P(4) = 16 > 10이므로 거짓

2. 어떤 x에 대하여 참인지를 확인하기 위해 참을 만족시키는 특정 x값만 찾는다.

P(1), P(2), P(3) < 10이므로 참

 

예제) 실수 x,y에 대해 명제함수 P(x,y)는 x**2< y**2일때 다음 명제의 진릿값은?

1.∀x∃yP(x,y)  2. ∃x∀yP(x,y)

1. 모든 x에 대해 P(x,y)를 만족하는 y가 하나라도 있으면 진릿값은 참

모든 |x|<|y|를 만족하는 y가 적어도 하나는 있으므로 주어진 명제는 참

2. 모든 y에 대해 P(x,y)를 만족하는 x가 하나라도 있으면 진릿값은 참

y = 0일때 |x|<|y|를 만족하는 x가 있을 수 없으므로 거짓

*모든 변수 값에 대하여-> 반례찾기
*어떤 변수 값에 대하여-> 그것을 만족시키는 변수 값을 찾기

---

4. 논리

논리와 추론

• 추론(interence)
  어떤 명제(전제)가 참인 것을 근거 하여 다른 명제(결론)가 참임을 유도하는 방식
  ex) [전제] 학생들은 학교에서 공부를 한다.
        [전제] 영희는 학생이다.
        [결론] ∴ 영희는 학교에서 공부를 한다.
  위의 전제 중 하나라도 거짓이 있다면 결론 유도 불가
• 정당한 추론(유효 추론)
  주어진 전제(참)에 의해 유도한 결론이 참인 추론
• 부당한 추론(허위 추론)
  주어진 전제(참)에 의해 유도된 결론이 거짓인 추론

유효추론과 허위추론의 예

p -> q :비가오면 우산을 갖고 간다.

p : 비가온다. 

q : 우산을 갖고 간다. q

p->q & p ∴ q 

위의 명제에 대한 진리표는 다음과 같다.

전제	결론	전제
p	q	p->q
T	T	T
T	F	F
F	T	T
F	F	T

[전제1] p-> q [전제2] p  둘다 참일떄 결론 q까지 참이므로 유효추론

 

p -> q & q ∴ p

위의 명제에 대한 진리표는 다음과 같다.

결론	전제	전제
p	q	p->q
T	T	T
T	F	F
F	T	T
F	F	T

[전제1] p->q [전제2] q  둘 다 참일 때 결론 q가 참이 아닐수도 있으므로 허위추론

논리적 추론 법칙

법칙 이름	추론 법칙	항진 명제
논리곱	p & q  ∴ p^q	없음
선언적 부가	p  ∴ pvq	p->(pvq)
단순화	p^q  ∴ p (q)	(p^q)->p (q)
긍정논법	p & p->q  ∴ q	[p^(p->q)] -> q
부정논법	~q & p->q  ∴ ~p	[~q^(p->q)] -> ~p
선언적 삼단논법 또는 소거	pvq & ~p  ∴ q	[(pvq)^ ~p] -> q
가설적 삼단 논법 또는 추이	p->q & q->r ∴ p->r	[(p-> q)^(q->r)]->(p->r)

예제) 논리적 추론법칙을 이용하여 다음 추론의 결론이 참인지 판별하시오

A: (~pv~q)-> ~r

B: ~r->~s

C: s

∴ q

 

D: (~pv~q)-> ~s (가설적 삼단논법)

E: (~(~pv~q) (부정논법)

F: p^q (드모르간 법칙)

단순화 법칙에 의해 q가 유도된다.

∴ q: (전제가 참이면) 추론의 결론은 항상 참이 된다.

---

2장 증명

1. 증명의 정의

공리(Axiom)

• 별도의 증명 없이 참(T)으로 이용되는 명제 (무증명 명제)
• [예] 실수 a,b에 대해 a = b이면 a + 1 = b + 1이다.

정의(Definition)

• 논의의 대상을 보편화하기 위해 사용하는 용어 또는 기호의 의미를 확실하게 규정한 문장이나 식
• [예] '명제'의 정의 : 참이나 거짓으로 판별할 수 있는 문장 또는 수식

정리(Theorem)

• 공리와 정의를 통해 참으로 확인된 명제

증명(Proof)

• 하나의 명제가 참임을 확인하는 과정

---

2. 직접증명법 (Direct Proof)

함축 명제 p->q가 참이 됨을 증명하는 방법

 

[예제] 정수 n이 3의 배수면, n**3도 3의 배수임을 증명하라.

 

-  p: 정수 n이 3의 배수이다.

-  q: n**3은 3의 배수이다.

-  p->q : 정수 n이 3의 배수이면, n**3은 3의 배수이다.

n이 3의 배수이므로 n = 3k(k∈Z)이고

n**3= (3k)**3 = 27k**3 = 3(9k**3)이므로 n**3은 3의 배수

∴ 함축명제 p->q는 참(T). Q.E.D("이것이 보여져야 할 것이었다" 라틴어의 약자, 증명 종료를 뜻함)

---

3. 간접증명법 (Indirect Proof)

함축 명제 p->q를 다양한 형태로 변형하여 증명하는 방법

 

대우 증명법 ~q -> ~p

함축 명제 p->q가 대우 ~q->~p가 동치임을 이요하여 증명하는 방법

 

예제) n**3이 3의 배수가 아니면 정수 n이 3의 배수가 아님을 대우증명법으로 증명하라

 

p: n**3이 3의 배수가 아니다.

q: 정수 n이 3의 배수가 아니다

~p: n**3이 3의 배수다

~q: 정수 n이 3의 배수다.

정수 n이 3의 배수이면 n**3이 3의 배수임을 아까 보였으므로 ~q->~p가 참

∴ 대우 p->q는 참(T). Q.E.D

 

모순 증명법 

함축 명제 p->q가 ~(~p^~q)와 동치임을 이용하여 증명하는 방법

p->q ≡ ~pvq

          ≡ ~pv~(~q)

          ≡ ~(p^~q)

 

p^~q가 거짓임을 보이면 된다.

 

예제) 정수 n이 3의 배수면, n**3도 3의 배수임을 모순 증명법으로 증명하라.

 

p: 정수 n이 3의 배수다.

q: n**3은 3의 배수다

p->q: 정수 ndl 3의 배수면, n**3은 3의 배수다

~q: n**3은 3의 배수가 아니다.

p^~q: n이 3의 배수고, n**3은 3의 배수가 아니다

n이 3의 배수이므로 n = 3k(k∈Z)이고,

n**3 = (3k)3 = 27k**3= 3(9k**3)이므로 n**3은 3의 배수

명제 p^~q이 거짓이므로 ~(p^~q)는 참

따라서 p->q 는 참

 

반례증명법(counter example 존재 증명)과 존재증명법

• 반례증명법 (Proof by Counter-Example) ∃x~P(x)
  명제에 모순이 되는 예를 찾아 증명하는 방법

예제) "모든 실수 a에 대해 (a+1)**2>=a**2이다"라는 명제의 참 거짓을 판단하라.

 

a= -1일 경우, (-1+1)**2 = 0 < 1=(-1)**2이므로 

모든 실수에 대해 (a+1)**2>=a**2이 성립하는 것은 아니다.

 

• 존재 증명법(Existence Proof) ∃xP(x)
  명제의 참이 되는 예를 찾아 증명하는 방법

예제) "어떤 실수 a에 대해 (a+1)**2 >= a**2이다"라는 명제의 참 거짓을 판단하라.

 

a = 1 인 경우 (1+1) **2 >= 1 = 1**2이므로 어떤 실수 a에 대해 (a+1)**2 >= a**2는 참이다

---

4. 수학적 귀납법(Mathematical Induction)

자연수 n에 관한 명제 P(n)이 모든 자연수 n에 대해 만족하는 것을 다음 세 단계의 과정으로 증명

• 기본과정: p(논의영역 초깃값)가 참임을 증명
• 귀납가정: 임의의 k에 대해 p(k)가 참이라고 가정
• 귀납단계: 기본과정과 귀납가정을 이용해 k+1에 대해 p(k+1)이 참임을 증명

예제) n>=1일때, n!>=2**(n-1)가 성립함을 증명하라.

 

p(n):  n!>=2**(n-1)

기본 과정) 초깃값 p(1) 1! = 1>=2**(i-1) = 2**0 = 1

귀납 가정) p(k): k!>=2**(k-1)의 성립을 가정

귀납 단계) p(k+1): (k+1)!>=2**(k+1-1)의 성립을 증명

                            (k+1)! = k!(k+1) >= 2**(k-1)(k+1)

                            (k>=1이므로)    >= 2**(k-1)*2 = 2**(k+1-1)

                            ∴  n>=1일 때, n!>=2**(n-1)이 성립 Q.E.D

 

예제) n-비트의 나열로 나타낼 수 있는 데이터의 최대 개수는 2**n임을 증명하라.

 

p(n): 2**n일때

기본 과정) p(1): 2**1= 2 (0또는 1)

귀납 가정) p(k): 2**k의 성립 가정

귀납 단계) p(K+1): 2**(k+1)의 성립 증명

                 2**(k+1) = 2 * 2**k는 2**k에 1비트를 더 붙인 길이

                2**k*2개의 데이터를 나타낼 수 이다.

                ∴ p(k+1) : 2**(k+1) 성립 Q.E.D