[이산 수학] 추론

추론

• 컴퓨터 시스템으로 구현한 것 중, 인간의 학습, 추론, 지각 등의 능력을 구현한 것이 인공지능(AI)인데, 인공지능은 이미 참(T)으로 판별된 명제와 반박할 수 없는 논리 규칙을 이용하여 새로운 참(T)인 명제를 정보로 획득하는 방식으로 지능을 높인다.
• 이처럼 참(T)인 명제와 논리 규칙을 이용하여 또 다른 참(T)인 명제를 유도해나가는 과정을 추론이라고 한다.

 

추론의 개념

추론(Inference) / 논증(Reasoning)

참(T)인 명제를 근거로 하여 다른 명제가 참(T)임을 유도하는 과정 또는 방식

 

전제(Hypothesis)와 결론(Conclusion)

• 추론에서 사용하는 명제는 추론의 근거로 사용하는 명제와 결론으로 나오는 명제로 구성된다.

① 전제(Hypothesis) : 결론의 근거가 되는 참(T)인 명제
② 결론(Conclusion) : 주어진 전제에 의해 유도된 최종적인 참(T)인 명제

 

유효 추론과 허위 추론

• 추론에서 전제로 사용되는 명제는 항상 참(T)이다.
• 그러나 참(T)인 명제를 전제로 추론한다고 해도 추론 과정의 오류 등으로 인해 결론이 거짓(F)이 될 수도 있다.
  • 결론이 거짓(F)인 추론은 올바른 추론이 아니므로 결론이 참(T)이 될 수 있도록 다른 전제를 이용하여 새로 추론해야 한다.
• 이처럼 추론의 결론이 참(T)이냐 아니냐는 그 추론이 정당한지 아닌지를 의미한다.

 

유효 추론(Valid Inference) / 정당한 추론

진릿값이 참(T)인 주어진 전제를 이용하여 유도한 결론이 모두 참(T)인 추론

 

허위 추론(Fallacious Inference) / 부당한 추론

진릿값이 참(T)인 주어진 전제를 이용하여 유도한 결론이 거짓(F)인 추론

 

• 추론에 사용하는 전제는 항상 참(T)인 명제여야 한다.
  • 이 명제를 이용하여 추론했을 때 결론의 진릿값이 모두 참(T)이면 그 추론은 정확하다고 판단하여 '유효 추론' 또는 '정당한 추론' 이라고 한다.
  • 결론의 진릿값이 하나라도 거짓(F)이면 정확하지 않은 추론이라고 판단하여 '허위 추론' 또는 '부당한 추론' 이라고 한다.

 

예

• 다음과 같이 2개의 전제 명제를 이용하여 결론을 얻은 추론이 있다고 하자.

전제 : 태양이 달보다 지구와 멀면 지구는 자전한다.
          태양은 달보다 지구와 멀다.
결론 :  지구는 자전한다.

• 위 추론에서 명제 `p` 를 '태양은 달보다 지구와 멀다', 명제 `q` 를 '지구는 자전한다'로 정의하여 추론을 기호화하고 진릿값을 구하면 다음과 같다.

전제		결론	$p→q$ $p$ $∴ q$
$p→q$	$p$	$q$
T	T	T
F	T	F
T	F	T
T	F	F

 

• 위의 표에서 빨간색으로 표시된 부분은 전제 명제 `p` 와 `p → q` 가 모두 참(T)인 경우로, 이 때 결론 `q` 또한 진릿값이 참(T)이다. 그러므로 이 추론은 유효 추론이다.
• 위 추론에서 명제 `p` 를 '태양은 달보다 지구와 멀다', 명제 `q` 를 '지구는 자전한다'로 정의하여 추론을 기호화하고 진릿값을 구하면 다음과 같다.

전제		결론	$p→q$ $q$ $∴ p$
$p→q$	$q$	$p$
T	T	T
F	F	F
T	T	F
T	F	F

 

• 위의 표에서 파란색으로 표시된 부분은 전제 명제 `p → q` 와 `q` 가 모두 참(T)인 경우로, 이 때 결론 `p` 의 진릿값들 중 거짓(F)이 있다. 따라서 이 추론은 허위 추론이다.
• 이와 같이 추론이 정당한지 부당한지 판단할 때는 전제에 해당하는 모든 명제의 진릿값들 중 참(T)인 경우에 대하여 결론이 모두 참(T)이어야만 유효 추론으로 정의할 수 있다.

 

예제 : 다음 추론이 정당한지 판별하라.

(a)

$p \lor (q \lor r)$

$\neg r$

$∴ p \lor q$

 

(b)
$p → q \lor \neg r$
$q → p \land r$
$∴ p → r$

 

(a)

`p`	`q`	`r`	$q \lor r$	전제		결론
				$p \lor (q \lor r)$	$\neg r$	$p \lor q$
T	T	T	T	T	F	T
T	T	F	T	T	T	T
T	F	T	T	T	F	T
T	F	F	F	T	T	T
F	T	T	T	T	F	T
F	T	F	T	T	T	T
F	F	T	T	T	F	F
F	F	F	F	F	T	F

빨간색으로 표시된 부분은 전체가 모두 참(T)인 경우이다. 이에 해당하는 결론도 모두 참(T) 이므로 이 추론은 정당하다. 

∴ 유효 추론

 

(b)

`p`	`q`	`r`	$\neg r$	$q \lor \neg r$	$p \land r$	전제		결론
						$p→q \lor \neg r$	$q → p \land r$	$p → r$
T	T	T	F	T	T	T	T	T
T	T	F	T	T	F	T	F	F
T	F	T	F	F	T	F	T	T
T	F	F	T	T	F	T	T	F★
F	T	T	F	T	F	T	F	T
F	T	F	T	T	F	T	F	T
F	F	T	F	F	F	T	T	T
F	F	F	T	T	F	T	T	T

 빨간색으로 표시된 부분은 전제가 모두 참(T)인 경우이다. 그러나 이에 해당하는 결론 중, ★로 표시한 결론은 거짓(F) 이므로, 전제가 참(T)인 경우에 대한 결론이 모두 참(T)은 아니다. 그러므로 이 추론은 부당하다.

∴ 허위 추론

 

논리적 추론 법칙

• 논리적 동치 법칙과 마찬가지로 추론해서 항상 성립하는 유효 추론을 논리적 추론 법칙이라고 한다.

법칙 이름	추론	항진 명제
논리곱 (Conjunction)	$p$ $q$ $∴ p \land q$	$(p \land q) → (p \land q)$
선언적 부가 (Disjunctive Addition)	$p$ $∴ p \lor q$	$p → (p \lor q)$
단순화 (Simplication)	$p \land q$ $∴ p$ (또는 `q`)	$(p \land q) → p$ (또는 `q`)
긍정 논법 (Modus Ponens)	$p$ $p → q$ $∴ q$	$\{ p \land (p → q) \} → q$
부정 논법 (Modus Tollens)	$\neg q$ $p → q$ $∴ \neg p$	$\{ \neg q \land (p → q) \} → \neg p$
선언적 삼단 논법 또는 소거 (Disjunctive Syllogism)	$p \lor q$ $\neg q$ $∴ p$	$\{ (p \lor q) \land \neg q \} → p$
가설적 삼단 논법 또는 추이 (Hypothetical Syllogism)	$p → q$ $q → r$ $∴ p → r$	$\{ (p→q) \land (q→r) \} → (p → r)$

• 유효 추론의 전제와 결론은 모두 진릿값이 참(T)이다. 그러므로 유효 추론의 전제에 해당하는 명제를 논리곱(AND)으로 연산한 결과는 항상 참(T)이다.
• 또한 조건 명제에서 조건인 명제가 참(T)이면 결론인 명제도 참(T) 이어야 조건 명제의 진릿값이 참(T)이다.
• 이 논리를 이용하여 추론의 전제와 결론을 논리곱(AND) 연산과 조건 명제로 표현한 것이 위의 항진 명제 항목이다.

 

예제 : 주어진 추론 법칙과 명제를 보고 빈칸에 알맞은 내용을 써라.

(a) 논리곱

희영이는 영어를 공부한다.

시진이는 야구를 한다.

∴ ______________________________________

 

(b) 긍정 논법

영수가 수학을 공부하면, 희영이는 영어를 공부한다.

_________________①____________________

∴ ________________②____________________

 

(c) 부정 논법

재성이가 국어를 공부하면, 시진이는 야구를 한다.

_________________ ① ____________________

∴ ________________②____________________

 

(d) 가설적 삼단 논법 / 추이

여준이가 축구를 하면, 승주는 수영을 한다.

_______________________________________

∴ 여준이가 축구를 하면, 시진이는 야구를 한다.

 

(e) 선언적 삼단 논법 / 소거

_______________________________________

영수는 수학을 공부하지 않는다.

∴ 재성이는 국어를 공부한다.

 

위 물음에서 사용한 명제를 정리하면 다음과 같다.

`p` : 영수는 수학을 공부한다.
`q` : 희영이는 영어를 공부한다.
`r` : 재성이는 국어를 공부한다.
`s` : 시진이는 야구를 한다.
`t` : 여준이는 축구를 한다.
`u` : 승주는 수영을 한다.

 

(a)

전제로 주어진 명제는 `p, s` 이다. 두 전제에 논리곱 추론 법칙을 적용하면 $p \land s$ 이다.

∴ 희영이는 영어를 공부하고, 시진이는 야구를 한다.

 

(b) 

전제로 주어진 명제는 `p → q` 이다. 이 전제에 긍정 논법을 적용하려면 전제 `p` 가 필요하고, 긍정 논법을 통해 얻는 결론은 `q` 이다.

∴ ① 영수가 수학을 공부한다.

   ② 희영이가 영어를 공부한다.

 

(c) 

전제로 주어진 명제는 `r → s` 이다. 이 전제에 부정 논법을 적용하려면 전제 $\neg s$ 가 필요하고 부정 논법을 통해 얻는 결론은 $\neg r$ 이다.

∴ ① 시진이는 야구를 하지 않는다.
   ② 재성이가 국어를 공부하지 않는다.

 

(d)

전제로 주어진 명제는 `t → u` 이고, 결론으로 주어진 명제는 `t → s` 이다. 이 전제와 결론에 적용된 추론 법칙은 가설적 삼단 논법(추이)이므로 `u → s` 가 전제로 필요하다.

∴ 승주가 수영을 하면 시진이는 야구를 한다.

 

(e)

전제로 주어진 명제는 $\neg p$ 이고, 결론으로 주어진 명제는 `r` 이다. 이 전제와 결론에 적용된 추론 법칙은 선언적 삼단 논법(소거)이므로 $p \lor r$ 이 전제로 필요하다.

∴ 영수가 수학을 공부하거나 재성이가 국어를 공부한다.

 

• 논리적 추론 법칙은 항상 유효 추론이므로, 주어진 추론이 유효 추론인지 허위 추론인지를 판별하거나 전제를 이용하여 결론을 유도하는 과정 등에 사용할 수 있다.
  • 단, 전제들에 추론 법칙을 적용하여 정당한지 부당한지를 판별하거나 결론을 유도할 때에는 주어진 전제 모두를 최소 한 번 이상 사용해야 한다.
• 하나 이상의 전제가 주어질 때, 그 전제들을 이용한 추론이 유효 추론인지 알아보려면 우선 주어진 전제에 추론 법칙이나 논리 법칙을 적용한다.
  • 그러면 새로운 참(T)인 명제가 만들어지며, 새롭게 만들어진 명제를 추론의 전제로 추가하여 이어서 추론 과정을 진행한다.
  • 이러한 과정은 모든 전제가 추론 과정에 사용될 때까지 반복한다.

 

예 : 전제와 결론을 이용하여 추론하기

전제 A : $(\neg p \lor \neg q) → \neg r$
전제 B : $\neg r → \neg s$
전제 C : `s`
결론 : `p`

 

• 주어진 전제와 결론을 이용한 추론 과정은 다음과 같다.

① 전제 A와 B에 가설적 삼단 논법 적용 : $(\neg p \lor \neg q) → \neg s$ (전제 D)
② 전제 D와 C에 부정 논법 적용 : $\neg (\neg p \lor \neg q)$
③ ②의 결과에 드 므로간의 법칙 적용 : $p \land q$ (전제 E)
④ 전제 E에 단순화 적용 : `p`

• 앞의 ①에서 전제 A와 B에 가설적 삼단 논법(추이)을 적용하면 명제 $(\neg p \lor \neg q) → \neg s$ 가 나오며, 이를 전제 D로 이 추론의 전제에 추가한다.
  • ① 이후에는 추론에 사용할 수 있는 전제가 A, B, C, D로 4개이다.
• ②에서 얻은 명제 $\neg (\neg p \lor \neg q)$ 는 논리 법칙(드 므로간의 법칙)으로 정리하면 명제 $p \land q$ 이고, 명제 $p \land q$ 는 또 다른 추론 법칙(단순화)을 적용하여 결론으로 유도할 수 있다.
  • 따라서 ②에서 얻은 명제 $\neg (\neg p \lor \neg q)$ 를 전제 E로 이 추론의 전제에 추가하는 대신, ③에서 드 므로간의 법칙을 적용한 결과로 얻은 명제 $p \land q$ 를 전제 E로 추가한다.
• ④에서 명제 `p` 까지 유도하고 추론을 마무리한 이유는 주어진 결론 `p` 와 같은 결론이 나와 유효 추론임을 확인해서이기도 하지만, ④의 직전 단계까지에서 주어진 전제 A, B, C, D, E를 추론 과정에 모두 사용하여 더 진행할 필요가 없기 때문이기도 하다.

 

예제 : 다음 추론이 유효 추론인지 허위 추론인지 판별하라.

(a) `p → q`

$p \land \neg q$

$∴ r$

 

(b) `p`
$r → (\neg q \land r)$

$\neg (q → p) \lor r$

$∴ \neg q$

 

(c) $q → \neg (p → r)$

$\neg p → q$

$q \lor (r → \neg p)$

$\neg p \lor r$

$∴ \neg p$

 

(a)

전제 A : `p → r`
전제 B : $p \land \neg q$

① 전제 A에 단순화 적용 : `p` (전제 C)
② 전제 B와 C에 긍정 논법 적용 : `r`

∴ 유효 추론

 

(b) 

전제 A : `p`
전제 B : $r → ( \neg q \land r)$
전제 C : $\neg (q → p) \lor r$

① 전제 A에 선언적 부가 적용 : $p \lor \neg q$
② ①의 결과에 논리 법칙 중 함축 법칙 적용 : $p \lor \neg q ≡ q → p$ (전제 D)
③ 전제 C와 D에 선언적 삼단 논법(소거) 적용 : `r` (전제 E)
④ 전제 B와 E에 긍정 논법 적용 : $\neg q \land r$ (전제 F)
⑤ 전제 E에 단순화 적용 : $\neg q$

∴ 유효 추론

 

(c) 

전제 A : $q → \neg (p → r)$
전제 B : $\neg p → q$
전제 C : $q \lor (r → \neg p)$
전제 D : $\neg p \lor r$

① 전제 D에 논리 법칙 중 함축 법칙 적용 : $\neg p \lor r ≡ p → r$
② 전제 A와 D에 부정 논법 적용 : $\neg q$ (전제 E)
③ 전제 C와 E에 선언적 삼단 논법(소거) 적용 : $r → \neg p$ (전제 F)
④ 전제 B와 F에 가설적 삼단 논법(추이) 적용 : $r → q$ (전제 G)
⑤ 전제 E에 G에 부정 논법 적용 : $\neg r$

∴ 허위 추론