일반화 (논리학)

1. 개요

일반화는 논리학에서 특정 진술로부터 더 일반적인 진술을 도출하는 추론 규칙을 의미한다. 전칭 일반화 규칙은 가설을 허용하는 경우 몇 가지 제한을 받는데, 이는 건전성을 확보하기 위함이다. 이러한 제한 조건은 특정 변수가 가설에 언급되지 않아야 하며, 일반화하려는 공식에 나타나지 않아야 함을 의미한다. 일반화 규칙을 이용한 증명 예시가 제시되며, 추론 정리 적용 가능 조건이 설명된다.

2. 가설을 사용한 일반화

턴스타일 왼쪽에 가설을 포함하는 전칭 일반화 규칙은 건전성을 보장하기 위해 몇 가지 제한 조건이 따른다. $\backslash Gamma$를 공식 집합, $\backslash varphi$를 공식이라고 가정하고 $\backslash Gamma\; \backslash vdash\; \backslash varphi(y)$가 유도되었다고 가정할 때, 일반화 규칙은 다음 조건 하에 $\backslash Gamma\; \backslash vdash\; \backslash forall\; x\; \backslash ,\; \backslash varphi(x)$를 유도할 수 있다고 명시한다.

* $y$는 $\backslash Gamma$에 언급되지 않아야 한다.
* $x$는 $\backslash varphi$에 나타나지 않아야 한다.

이러한 제한이 없다면 가설에서 옳지 않거나 모순된 결론을 도출할 수 있다.

2.1. 제한 조건

$\backslash Gamma\; \backslash vdash\; \backslash varphi(y)$가 유도되었다고 가정할 때, $\backslash Gamma$는 논리식 집합이고, $\backslash varphi$는 논리식이다. 일반화 규칙이 적용되려면 다음 두 가지 제한 조건이 필요하다.

* $y$는 $\backslash Gamma$에서 언급되지 않아야 한다.
* $x$는 $\backslash varphi$에 나타나지 않아야 한다.

이러한 제한 조건은 추론의 건전성을 보장하기 위해 필요하다. 첫 번째 제한 조건이 없다면, 가설 $P(y)$에서 $\backslash forall\; x\; P(x)$를 결론 내릴 수 있게 된다. 예를 들어, "y는 사람이다"라는 가설에서 "모든 x는 사람이다"를 결론 내릴 수 있게 되는데, 이는 옳지 않다.

두 번째 제한 조건이 없다면 다음과 같은 잘못된 추론이 가능해진다.

1. $\backslash exists\; z\; \backslash ,\; \backslash exists\; w\; \backslash ,\; (\; z\; \backslash not\; =\; w)$ (가설)
2. $\backslash exists\; w\; \backslash ,\; (y\; \backslash not\; =\; w)$ (존재 예시화)
3. $y\; \backslash not\; =\; x$ (존재 예시화)
4. $\backslash forall\; x\; \backslash ,\; (x\; \backslash not\; =\; x)$ (잘못된 보편적 일반화)

이는 $\backslash exists\; z\; \backslash ,\; \backslash exists\; w\; \backslash ,\; (\; z\; \backslash not\; =\; w)\; \backslash vdash\; \backslash forall\; x\; \backslash ,\; (x\; \backslash not\; =\; x)$를 보여주는 것으로, "서로 다른 z와 w가 존재한다"는 가설에서 "모든 x는 자기 자신과 같지 않다"는 모순된 결론을 도출하는 잘못된 추론이다.

2.2. 제한 조건의 필요성

이러한 제한은 건전성을 위해 필요하다. 첫 번째 제한이 없으면 가설 $P(y)$에서 $\backslash forall\; x\; P(x)$를 결론지을 수 있다. 두 번째 제한이 없으면 다음과 같은 추론을 할 수 있다.

# $\backslash exists\; z\; \backslash ,\; \backslash exists\; w\; \backslash ,\; (\; z\; \backslash not\; =\; w)$ (가설)
# $\backslash exists\; w\; \backslash ,\; (y\; \backslash not\; =\; w)$ (존재 예시화)
# $y\; \backslash not\; =\; x$ (존재 예시화)
# $\backslash forall\; x\; \backslash ,\; (x\; \backslash not\; =\; x)$ (잘못된 보편적 일반화)

이것은 $\backslash exists\; z\; \backslash ,\; \backslash exists\; w\; \backslash ,\; (\; z\; \backslash not\; =\; w)\; \backslash vdash\; \backslash forall\; x\; \backslash ,\; (x\; \backslash not\; =\; x)$를 보여주는 것으로, 이는 건전하지 않은 추론이다. $y$가 $\backslash Gamma$에 언급되지 않으면 $\backslash Gamma\; \backslash vdash\; \backslash forall\; y\; \backslash ,\; \backslash varphi(y)$가 허용된다는 점에 유의해야 한다 (두 번째 제한은 $\backslash varphi(y)$의 의미 구조가 변수의 대체에 의해 변경되지 않으므로 적용될 필요가 없다).

3. 증명의 예시

전칭 일반화를 사용하여 $\backslash forall\; x\; \backslash ,\; (P(x)\; \backslash rightarrow\; Q(x))\; \backslash rightarrow\; (\backslash forall\; x\; \backslash ,\; P(x)\; \backslash rightarrow\; \backslash forall\; x\; \backslash ,\; Q(x))$를 증명하는 예시는 다음과 같다. 이 증명은 $\backslash forall\; x\; \backslash ,\; (P(x)\; \backslash rightarrow\; Q(x))$와 $\backslash forall\; x\; \backslash ,\; P(x)$로부터 유도될 수 있다. 증명 과정은 "증명 과정" 하위 섹션에 상세히 기술되어 있다.

3.1. 증명 과정

$\backslash forall\; x\; \backslash ,\; (P(x)\; \backslash rightarrow\; Q(x))\; \backslash rightarrow\; (\backslash forall\; x\; \backslash ,\; P(x)\; \backslash rightarrow\; \backslash forall\; x\; \backslash ,\; Q(x))$는 $\backslash forall\; x\; \backslash ,\; (P(x)\; \backslash rightarrow\; Q(x))$와 $\backslash forall\; x\; \backslash ,\; P(x)$로부터 유도될 수 있다. 증명 과정은 다음과 같다.