[CS 1-2 | 이산수학] 추론 4주차

증명

• 수학적 진술의 참을 입증하는 유효한 논증
  
  
• 논증이란 하나의 결론으로 끝나는 일련의 진술
  
  
• 결론이 전제들의 참 값으로부터 유도될 수 있을 때 유효하다고 표현한다.
• 논증이 유효하다 <-> 그 논증의 모든 전제가 참이면서, 동시에 결론이 거짓일 수 없다.
  
  

추론 규칙

• 기존의 진술들로부터 새로운 진술을 도출하기 위해 유효한 논증을 구성하는 틀
• 수학적 진술의 참을 입증하는 기본도구

---

유효한 논증

• 논증이란, 명제들을 순차적으로 나열한 것이다.
  명제 논리에서 논증식이란, 명제 변수를 사용한 복합명제의 순열이다.
  전제에서 나와있는 어떤 명제든 명제 변수로 치환하고, 그 전제가 모두 참일 때 결론이 참이면 그 논증식은 유효하다고 한다.
  
  
• 논증을 분석하기 위해 명제를 명제 변수로 치환하는 것은 논증을 논증식으로 변환한 것
  (논증식이 유효함을 보임으로써 논증이 유효하다는 결론을 낼 수 있다.)

그럼 이제, 논증식이 유효함을 보일 수 있는 기법에 대해 알아보도록 하자!

 

 

추론 규칙 예제

• 긍정 논법

참인 전제들을 기반으로 결론이 참임을 입증하는 추론법
조건문 (->)을 이용해 추론

 

• 부정 논법

결론의 부정으로부터 그 전제의 부정을 유도하는 추론법이다.

조건문 (->)을 사용해 추론

 

• 가설적 삼단논법

가설에 기초한 여러 판단에서 시작하여 서로를 관련시킬 때 유효한 결론을 추출하는 추론법이다.

 

• 논리합 삼단논법

전제들의 참임을 이용해 새로운 진술의 진리 값을 추론

• 가산 논법

OR 연산자의 특성인 둘 중하나의 진리 값이 참이면
해당 논리표현은 참임을 이용한 추론법이다.

• 단순화 논법

AND 연산자의 특성인 둘의 모든 진리 값이 참일 때

해당 논리표현이 참임을 이용한 추론법이다.

 

• 논리곱 논법

참인 전제인 명제 변수로 AND 연산을 이용해 새로운 논리표현을 만드는 추론법이다.

 

• 융해법

논리합 삼단논법과 비슷한 추론전략이다.

 

 

추론 규칙

---

예제를 통해 "추론 규칙"을 이해

• 예제 )) "지금은 영하의 날씨이다. 그러므로 지금은 영하의 날씨이거나 비가 오고 있을 것이다."라는 논증은 어떤 추론 규칙에 근거하는 가?

"지금은 영하의 온도이다"를 p라 하고, "지금은 비가 오고 있을 것이다"를 q라 하면, 이 문장은 다음과 같다.

p | p or q

이 예제는 가산 규칙을 이용한 논증이다.

 

주어진 논증이 유효한지 판정하기 위해선,

1. 우선 전제가 어떤 영역인지를 판단한다.

2. 그리고, 주어진 전제에 적합한 추론규칙을 적용한다.
어떤 추론규칙을 적용할 지는 수많은 ㅎㅎ 경험을 통해 통달하면 된다!

3. 그런 다음, 최종적인 논증이 유효한 지 판단한다.

---

증명의 오류

• 증명에 있어서 오류가 발생하는 경우가 종종 있다.
• 불확정명제에 근거한 잘못된 추론 규칙 때문에 일어남.
  • 불확정명제란, 경우에 따라 참과 거짓의 값을 가질 수 있는 명제를 말한다.
    즉, "진리값이 참/거짓 중 하나로 판정짓기 어려운 명제들을 불확정명제라고 한다."
    
    
    

# 증명의 오류 종류

• 결론 단언의 오류
  • 두 명제 A(x) 와 B(x) 가 있는데
    A(x)가 참이면 B(x)가 참인데, B(x)가 참이라고 A(x)를 참이라고 생각하는 오류 입니다.
    역은 반드시 참이 될 수 없는거랑 같습니다
    
    
• 가정 부정의 오류
  • 두 명제 p, q가 있을 때, "p이면 q인데 p가 아니니까 q도 아니겠지?"
    이렇게 생각하는 겁니다.

---

한정기호를 사용하는 명제에 대한  "추론규칙 활용"

• 전칭 예시화
  • ∀xP(x)가 주어졌을 때 정의역에 속하는 임의의 원소 c에 대하여 P(c)가 참이라 하는 것
    
    
  • 예를 들어, "모든 여성은 현명하다"로부터, "리사는 현명하다"를 도출하는 것과 같다.
    여기서 리사는 모든 여성이라고 하는 정의역에 속하는 원소이다.

∀xP(x)가 참이므로, 임의의 원소 c에 대해 P(c)가 참이다.

 

• 전칭 일반화
  • 정의역에 속하는 모든 원소 c에 대하여 P(c)가 참이면 ∀xP(x)가 참이라 하는 것
  • 정의역에 속하는 임의의 c를 취하여 P(c)가 참임을 보임으로써 결론적으로 ∀xP(x)가 참임을 보인다.
    
    

정의역에 속하는 모든 원소 c에 대해 참임을 입증했으므로, ∀xP(x)가 참이다.

 

• 존재 예시화
  • ∃xP(x)가 참이라면, 그 정의역에 P(c)를 참으로 만드는 어떤 원소 c가 존재한다고 추론하는 것
    
    
  • 여기선, 임의의 c값을 취할 수 없다.
    
    
  • P(c)가 참인 c가 존재하는 것은 알지만 그게 무엇인지는 모른다.
    
    

∃xP(x)가 참이면, 어떤 원소 c에 대하여 P(c)가 참이다.

 

• 존재 일반화
  • 특정 요소 c에 대해 P(c)가 참이라면 ∃xP(x)가 참이라고 추론하는 것
    
    
  • 정의역에 P(c)가 참이 되게 하는 c가 존재한다면 ∃xP(x)가 참이라고 하는 것
    
    

어떤 원소 c에 대하여 P(c)이면, ∃xP(x)가 참이다.

 

# 한정기호를 사용하는 명제에 대한 "추론" 예제

 

 

---

한정화된 문장과 추론 규칙의 결합

• 전칭 예시화와 긍정 논법을 이용한 추론

 

• 전칭 예시화와 부정 논법을 이용한 추론

 

이처럼, 한정화 된 문장과 일반명제 문장을 추론할 때는
전칭 예시화로 일반명제로의 바꾸고,
추론규칙인 긍정논법, 부정논법을 사용해
새로운 진술의 진리값을 추론한다.

 

# 한정화 된 문장의 추론 규칙 예제