한정규칙(Quantification Rules)

전칭기호(universal quantifier)

전체집합(universal set) : 어떤 집합이 주어젔을때 그 집합의 모든대상을 포함하는 집합.

가령 명제

"모든 사람은 죽는다."

위 명제의 전체집합은 "인류" 이다. 전체집합을 이용하여 위 명제를 아래처럼 나타낼 수 있다.

"전체집합의 모든 $x$에 대하여 $x$는 죽기 마련이다."

여기서 하나의 구 "전체집합의 모든 $x$에 대하여" 를 전칭기호(universal quantifier)라 하고 이것을 $all$의 $A$를 뒤집어 만든 $\forall x$로 나타낸다.

즉, $\forall x$는 "모든 $x$에 대하여" 혹은 "각 $x$에 대하여" 의 뜻을 지닌다.

이 경우 "$x$는 죽기 마련이다"라는 주장은 $x$에 대한 한가지 조건을 제시하고 있다. 이러한 주장을 기호 $p(x)$로 정의할 경우 명제 "모든 사람은 죽는다." 를 $\forall x \; p(x)$와 같이 간단히 나타낼 수 있다.

가령 전체집합이 유한개의 원소 $a_1, a_2, \cdots , a_n$으로 이루어졌을 경우를 생각하면

$\forall x ~ p(x)$는 모든 $a_1, a_2, \cdots, a_n$에 대하여 $p(x)$가 참임을 주장하므로

$$p(a_1), p(a_2),\cdots , p(a_n)$$

의 논리곱이 참이면, 그리고 그때에만, 참이다.

따라서 $\forall x ~ p(x)$ 는

$$p(a_1) \wedge p(a_2) \wedge \cdots \wedge p(a_n)$$

를 뜻한다.

 

존재기호(existential quantifier)

한편 또다른 명제

"어느 사람은 죽기 마련이다"

를 생각할 때 전체집합은 역시 "인류"이다. 이런 전체집합을 염두에 두고 명제를 다음중 한가지로 생각 나타낼 수 있다.

a) 죽기 마련인 사람이 적어도 한명 존재한다.

b) 적어도 하나의 $x$가 존재함으로써 $x$는 죽는다.

c) 적어도 하나의 $x$가 존재함으로써 $p(x)$

이 경우 "적어도 하나의 $x$가 존재함으로써" 를 존재기호(existential quantifier)라 하고 $Exist$의 $E$를 뒤집어 만든 $\exists x$로 나타낸다. 그리하여 명제를 $\exists \; x p(x)$와 같이 나타낼 수 있다.

그리고 $\exists x ~ p(x)$는 다음을 뜻한다.

$$p(a_1) \vee p(a_2) \vee \cdots \vee p(a_n)$$

 

전체집합 $U$의 임의의 원소 $x$에 관한 명제 이른바 명제함수(propositional function) $p(x)$를 생각할때

$\forall x p(x)$는 $U$에 속하는 모든 $x$에 대하여 $p(x)$가 참인 것을 주장하는 명제이다. 

즉, $\exists x$는 "적당한 $x$에 대하여" 혹은 "$x$가 존재함으로써" 의 뜻을 지닌다.

$\exists x p(x)$는 $U$에 속하는 $x$가 적어도 하나 존재함으로써 $p(x)$가 참인것을, 다시 말해 $p(x)$가 참인 $x$가 $U$에 적어도 하나 존재한다는것을 주장하는 명제이다.

가령

$\forall x \; f(x) = 0$ 은 "모든 $x$에 대하여 $f(x)=0$"을 뜻하며

$\exists x \; f(x) = 0$ 은 "적어도 하나의 $x$에 대하여 $f(x) = 0$" 을 뜻한다.

 

전칭기호와 존재기호를 모두 한정기호(quantifier)라고 한다.

 

 

한정기호의 부정규칙(Rule of Quantifier Negation; Q.N.)
전체집합 $U$의 임의의 원소 $x$에 관한 명제함수 $p(x)$에 대하여 다음이 성립한다.
$$\sim \forall x~p(x) \equiv \exists x~\sim p(x),~~~~~~~ \sim \exists x ~ p(x) \equiv \forall x ~ \sim p(x)$$

명제

"($U$에 속하는) 모든 $x$에 대하여 $p(x)$"

의 부정 즉, $\sim \forall x ~ p(x)$는

"($U$에 속하는) 적어도 하나의 $x$에 대하여 $\sim p(x)$"

이는 곧 $\exists x ~ \sim p(x)$를 나타내는 명제이다.

 

마찬가지로 $\sim \exists x ~ p(x)$는

"($U$에 속하는) 적당한 $x$에 대하여 $p(x)$는 아니다."

또는

"($U$에 속하는) 모든 $x$에 대하여 $p(x)$는 아니다."

이는 곧 $\forall ~ \sim p(x)$를 나타내는 명제이다.

 

한정기호의 부정규칙은 드 모르간의 법칙을 일반화 한것임을 알 수 있다.