제 4 절 한정기호

제 4 절 한정기호

명제 “모든 사람은 죽는다”를 생각하여 보자. 모든 사람의 집합을 전체집합 U로 생각할 때, 이 명제는 다음과 같이 나타낼 수 있다.

U에 속한 모든 x에 대해 x는 죽는다.

이제 “U에 속한 모든 x에 대해서”라는 구절을 전칭기호(universal quanti- fier)를 사용하여 (∀x)로 나타낸다. 따라서 p(x)를 “x는 죽는다”라는 명제 함수라 하면,

(∀x)(p(x)) 또는 ∀x p(x) 와 같이 쓸 수 있다.

“x에 관계없이”,

“임의의 x에 대해”

등의 표현은 모두 전칭기호로 나타낼 수 있다.

전칭기호는 가끔 생략할 경우가 있다. 예를 들어 대수적 항등식

(a + b)(a− b) = a²− b²은 모든 실수(혹은 복소수)에 대해 성립하는데, 이 식은 전칭기호가 생략된 것이다.

다음으로 “어떤 사람은 죽는다”라는 명제를 생각해보자.

U에 속한 어떤 x에 대해 x는 죽는다.

“U에 속한 어떤 x에 대해”라는 구절을존재기호 (existential quantifier)를 사용하여 (∃x)로 나타낸다. 따라서 위 명제는

(∃x)(p(x)) 또는 ∃x p(x) 로 쓸 수 있다.

“적어도 한 개의 x에 대해”,

“...인 x가 있다”,

“...인 x가 존재한다”

등의 표현은 모두 존재기호로 나타낼 수 있다.

전칭기호와 존재기호를 통틀어 한정기호 (quantifier)라 한다.

참 고 1.43 명제함수를 명제로 만드는 방법에는 2가지가 있다. 먼저 명제 함수의 변수에 어떤 값을 대입하면 명제가 된다. 또 한가지 방법은 명제함수에 한정기호를 붙이는 방법이다. 예를 들어 p(x)를 “x는 양수이다”라는 명제함 수라 하면, p(x)는 참, 거짓을 정할 수 없지만,

∀x p(x) 는 거짓인 명제가 되어 진리값을 갖는다. 또한

∃x p(x)

도 참인 명제가 된다.

[[ 예 ]] 1.44 “모든 삼각형은 다각형이다”라는 명제는

“x가 삼각형이면, x는 다각형이다”로 나타낼 수 있다. 따라서

∀x(x가 삼각형이다 → x는 다각형이다)

와 같이 전칭기호를 이용하여 나타낼 수 있다.

‘이 세상에 있는 모든 뱀은 독이 있다’라는 사실의 부정을 생각하면 ‘어떤 뱀은 독이 없다’가 될 것이다. 이와 같이 일반적으로 모든 경우에 성립하는 명 제를 부정할 경우, 한가지만 성립하지 않아도 되므로 논리에서도 다음과 같이 정의한다.

정 의 1.45 [한정기호 부정법(rule of quantifier negation)]

p(x)가 명제함수라 할 때, 아래와 같이 한정기호 부정의 규칙을 정의한다.

∼ [(∀x)(p(x))] ≡ (∃x)(∼ p(x))

∼ [(∃x)(p(x))] ≡ (∀x)(∼ p(x))

참 고 1.46 전체집합 U가 유한집합 {a1, a2, . . . , an}일 경우를 생각하면, (∀x)(p(x)) ≡ p(a1) ∧ p(a2) ∧ . . . ∧ p(an)

(∃x)(p(x)) ≡ p(a1) ∨ p(a2) ∨ . . . ∨ p(an) 가 된다. 이 경우

∼ [(∀x)(p(x))]

≡∼ [p(a1) ∧ p(a2) ∧ . . . ∧ p(an)]

≡∼ p(a1)∨ ∼ p(a2) ∨ . . . ∨ ∼ p(an) (∵ De Morgan)

≡ (∃x)(∼ p(x))

따라서 한정기호 부정법은 De Morgan 법칙의 일반화가 된다.

참 고 1.47 전체 집합 U 중 일부분인 A에 대한 전칭기호가 있는 명제는 아래와 같이 변형된다.

(∀x ∈ A)(p(x)) ≡ (∀x ∈ U)(x ∈ A → p(x))

≡ (x ∈ A → p(x)) (∵ 전칭기호의 생략)

또한 존재기호가 들어있을 경우는 아래와 같이 변형된다.

(∃x ∈ A)(p(x)) ≡ (∃x ∈ U)(x ∈ A ∧ p(x))

≡ (∃x)(x ∈ A ∧ p(x))

참 고 1.48 논리합이나 논리곱으로 이루어진 경우 한정기호의 영향을 받지 않는 명제는 한정기호의 영향 범위 안이나 밖으로 이동이 가능하다. 예를 들어 논리합으로 이루어진 명제에 대해 아래 사실이 성립한다.

(1) (∀x p(x)) ∨ q ≡ ∀x (p(x) ∨ q).

(2) p∨ (∀x q(x)) ≡ ∀x (p ∨ q(x)).

(3) (∃x p(x)) ∨ q ≡ ∃x (p(x) ∨ q).

(4) p∨ (∃x q(x)) ≡ ∃x (p ∨ q(x)).

논리곱에 대해서도 마찬가지 사실이 성립한다.

(1^′) (∀x p(x)) ∧ q ≡ ∀x (p(x) ∧ q).

(2^′) p ∧ (∀x q(x)) ≡ ∀x (p ∧ q(x)).

(3^′) (∃x p(x)) ∧ q ≡ ∃x (p(x) ∧ q).

(4^′) p ∧ (∃x q(x)) ≡ ∃x (p ∧ q(x)).

그러나 조건문의 전건부에 한정기호가 있을 경우에는 아래 정리에서 보는 것처럼 한정기호가 바뀐다.

정 리 1.49 한정기호가 있는 명제함수에 대해 아래 사실이 성립한다.

(1) (∀x p(x)) → q ≡ (∃x )(p(x) → q).

(2) (∃x p(x)) → q ≡ (∀x )(p(x) → q).

(3) p→ (∀x q(x)) ≡ (∀x )(p → q(x)).

(4) p→ (∃x q(x)) ≡ (∃x )(p → q(x)).

증명. 조건문을 논리합으로 변형한 후 계산하면 간단히 보일 수 있으므로 한 가지만 보이기로 하자.

(∀x p(x)) → q ≡ [∼ (∀x p(x))] ∨ q (∵ 정리 1.15)

≡ [∃x (∼ p(x))] ∨ q (∵ 한정기호 부정법)

≡ [∃x (∼ p(x) ∨ q)] (∵ 참고 1.48)

≡ [∃x (p(x) → q)] (∵ 정리 1.15)



참 고 1.50 위 정리의 사용 예는 예제 ??에서 알아볼 것이다.

[[ 예 ]] 1.51 아래 명제의 부정을 구하고 진리값을 구하여라.

모든 실수 x에 대해 x²+ 2x + 1 ≥ 0이다

풀이. ∼ [∀x (x²+ 2x + 1 ≥ 0)]

≡ ∃x ( ∼ (x²+ 2x + 1 ≥ 0))

≡ ∃x ( x²+ 2x + 1 < 0)

따라서 부정명제는 “어떤 실수 x에 대해 x² + 2x + 1 < 0”가 되며 거짓이 다.

[[ 예 ]] 1.52 아래 명제의 부정을 구하고 진리값을 구하여라.

모든 실수 x에 대해 x² < 1이면 x < 1이다

풀이.

∼ [∀x (x² < 1 → x < 1)]

≡ ∃x [∼ (x² < 1 → x < 1)] (∵ 한정기호 부정법)

≡ ∃x [∼ [∼ (x² < 1) ∨ (x < 1)]] (∵ 정리 1.15)

≡ ∃x [(x² < 1)∧ ∼ (x < 1)] (∵ De Morgan)

≡ ∃x [(x² < 1) ∧ (x ≥ 1)]

따라서 부정명제는 거짓이다.

[[ 예 ]] 1.53 아래 명제는 “x = a에서 연속”이라는 정의이다. 이 명제의 부 정을 구하여라.

∀ϵ ∃δ [( |x − a| < δ → |f(x) − f(a)| < ϵ)]

풀이. 한정기호 부정법을 사용하여 부정명제를 구하면

∼ [∀ϵ ∃δ (|x − a| < δ → |f(x) − f(a)| < ϵ)]

≡ ∃ϵ ∀δ [∼ (|x − a| < δ → |f(x) − f(a)| < ϵ)] (∵ 한정기호 부정법)

≡ ∃ϵ ∀δ [∼ [∼ (|x − a| < δ) ∨ (|f(x) − f(a)| < ϵ)]] (∵ 정리 1.15)

≡ ∃ϵ ∀δ [(|x − a| < δ) ∧ ∼ (|f(x) − f(a)| < ϵ)] (∵ De Morgan)

≡ ∃ϵ ∀δ [(|x − a| < δ) ∧ (|f(x) − f(a)| ≥ ϵ)]