[Discrete Mathematics] 한정기호(quantifiers) 및 다중 한정기호

---

명제함수 (Propositional Function) 혹은 술어 (Predicate)

 

명제는 참이나 거짓이 결정되어 있어야 한다. 예를 들어 " $ P $ : $ n $ 은 짝수이다" 같은 형태는 $ n $ 에 따라 $ P $ 가 True 혹은 False 로 결정되기 때문에 명제라 할 수 없다.

이러한 문장 " $ P $ : $ n $ 은 짝수이다"를 바꾸어서 $ P(x) $ 와 같이 형태로 표현할 수 있다. 이 $ P(x) $ 와 집합 $ D $ 가 주어졌을 때, 각 $ x \in D $ 에 대해 $ P(x) $ 가 명제이면 $ P $ 를 ($ D $ 에 대한) 명제함수, 혹은 술어라 한다. 또한 $ D $ 를 $ P $ 의 논의영역(the domain of discourse)이라 한다.

 

---

전칭한정 (Universal Quantifier) 및 존재한정 (Existential Quantifier)

 

전칭한정은 논의영역에 속하는 모든 객체에 대해 어떤 명제함수 $ P(x) $ 가 항상 성립함을 나타낸다. 수학적 기호로는 모든 것을 뜻하는 기호 $ \forall $ 을 사용하여 $ \forall x P(x) $ 라 표기한다.

전칭한정된 문장은 논의영역의 모든 $ x $ 에 대해 $ P(x) $ 가 참일 때 참이고, 하나라도 $ P(x) $ 를 거짓으로 만드는 $ x $ 가 있다면 거짓이다. 이때 전칭한정된 문장을 거짓으로 만드는 특정한 값 $ x $ 를 반례(counterexample)라 한다.

명제함수 $ P(x) $ 에서 변수 $ x $ 를 자유변수(free variable)이라 하고, 전칭 한정된 문장 $ \forall x P(x) $ 에서 변수 $ x $ 를 구속변수(bound variable)이라 한다. 이는 $ x $ 가 한정기호 $ \forall $ 에 구속된다는 의미이다. 자유변수가 포함된 명제는 $ x $ 가 논의영역에서 자유롭게 선택될 수 있기 때문에 명제가 아니며, 자유변수가 없는, 즉 모든 변수가 한정된 문장은 명제이다.

전칭한정된 문장은 다음과 같이 증명될 수 있다. 예를 들어 "모든 실수 $ x $ 에 대해 만약 $ x > 1 $ 이면 $ x + 1 > 1 $ 이다." 라는 전칭한정된 조건 명제를 증명해보자. $ x $ 를 임의의 실수로 생각하고 케이스를 나누어 증명할 수 있다. $ x $ 는 임의의 실수이므로 $ x > 1 $ 혹은 $ x \leq 1 $ 중 하나가 참이다. 만약 $ x \leq 1 $ 이 참이라면 조건 명제의 전제인 $ x > 1 $ 이 거짓이므로 조건 명제의 진리값은 참이된다. 만약 $ x > 1 $ 이 참이라면 $ x $ 값에 상관없이 $ x + 1 > x $ 이고, $ x > 1 $ 이므로 $ x + 1 > 1 $ 이 되고 조건 명제의 전제와 결과 모두 참이되기 때문에 해당 조건 명제의 진리값은 참이다. 모든 실수 $ x $ 에 대해 이 명제가 참임을 보였기 때문에 이 전칭 한정된 문장은 참이다.

존재한정은 논의영역에 속하는 어떤 객체에 대해 명제함수 $ P(x) $ 가 성립함을 나타낸다. 수학적 기호로는 존재한다는 것을 뜻하는 기호 $ \exists $ 를 사용하여 $ \exists x P(x) $ 라 표기한다.

존재한정된 문장은 논의영역 $ D $ 를 가진 명제함수 $ P(x) $ 에서 논의영역에 속하는 적어도 하나의 어떤 $ x $ 가 $ P(x) $ 를 참으로 만든다면 이 존재한정된 문장은 참이고, 논의영역 $ D $ 에 속하는 모든 $ x $ 에 대해 $ P(x) $ 가 거짓이면 거짓이다.

존재한정된 문장은 특정 $ x $ 를 찾기만 하면 참임을 증명할 수 있다. 반대로 존재한정된 문장이 거짓임을 증명하는 것은 전칭한정된 문장을 증명하는 것과 같다.

 

이러한 한정된 명제에 대한 의사코드를 다음과 같이 표현할 수 있다.

$ P $ 가 논의영역이 집합 $ \{ d_1, d_2, \dots , d_n \} $ 인 명제함수라 하자. 다음의 의사코드는 $ \forall x P(x) $ 가 참인지 거짓인지 결정한다.

for i = 1 to n
    if (not P(d_i))
        return false
return true

다음의 의사코드는 $ \exists x P(x) $ 가 참인지 거짓인지 결정한다.

for i = 1 to n
    if (P(d_i))
        return true
return false

 

만약 $ P $ 가 논의영역 $ D $ 를 가진 명제함수라면 일반화된 드모르간의 법칙(generalized de morgan’s laws for logic)에 의해 다음이 성립한다.

$$ \lnot \text{ } (\forall x P(x)) \equiv \exists x \lnot \text{ } P(x) $$

$$ \lnot \text{ } (\exists x P(x)) \equiv \forall x \lnot \text{ } P(x) $$

 

---

한정된 문장의 부정

 

한정된 문장을 부정하여 사용할 수도 있다. 예를 들어 "어떤 새들은 날 수 있다"는 문장이 있다고 가정하자. 이 문장을 수식으로 표현하면 $ \exists x P(x) $, $ P(x) $: "$ x $ 는 날 수 있다.", $ D $: "새" 로 표현할 수 있다. 이 문장을 부정하면 "어떤 새들은 날 수 없다"가 되어 $ \exists x \lnot \text{ } P(x) $ 로 표현된다.

위 문장을 다시 부정해보자. $ \lnot (\exists x \lnot \text{ } P(x)) $ 로 표기한다. 이는 드모르간의 법칙을 적용하면 $ \forall x \lnot \lnot \text{ } P(x) $ 로 나타낼 수 있으며, 다시 이는 $ \forall x P(x) $ 로 나타낼 수 있다. 이는 문장으로 풀어쓰면 "모든 새는 날 수 있다"가 된다.

 

---

한정된 문장에 대한 추론 규칙

 

• 전칭 예시화 (Universal Instantiation)

$$ \begin{align*} & \forall x P(x) \\ \hline & \therefore P(d) \text{ if } d \in D \end{align*} $$

• 전칭 일반화 (Univarsal Generalization)

$$ \begin{align*} & P(x) \text{ for every } d \in D \\ \hline & \therefore \forall x P(x) \end{align*} $$

• 존재 예시화 (Existential Instantiation)

$$ \begin{align*} & \exists x P(x) \\ \hline & \therefore P(d) \text{ for some } d \in D \end{align*} $$

• 존재 일반화 (Existential Generalization)

$$ \begin{align*} & P(d) \text{ for some } d \in D \\ \hline & \therefore \exists x P(x) \end{align*} $$

 

---

다중 한정기호

 

두 개 이상의 한정기호를 사용하여 복잡한 명제나 논리적 관계를 표현 할 수 있다. 두 개 이상의 한정기호를 사용하기 때문에 전칭한정이 여러 개 사용될 수도, 전칭한정과 존재한정이 같이 사용될 수도, 존재한정이 여러 개 사용될 수도 있다.

• $ \forall x \forall y P(x, y) $

모든 $ x \in X $ 와 모든 $ y \in Y $ 에 대해 $ P(x, y) $ 가 참이면 참이다. 즉 적어도 하나의 $ x \in X $ 와 적어도 하나의 $ y \in Y $ 에 대하여 $ P(x, y) $ 가 거짓이면 거짓이다.

• $ \forall x \exists y P(x, y) $

모든 $ x \in X $ 에 대해 적어도 하나의 $ y \in Y $  가 존재하여 $ P(x, y) $ 가 참이면 참이다. 즉 모든 $ y \in Y $ 에 대해 $ P(x, y ) $ 가 거짓이 되는 $ x \in X $ 가 존재한다면 거짓이다.

• $ \exists x \exists y P(x, y) $

적어도 하나의 $ x \in X $ 와 적어도 $ y \in Y $ 가 존재하여 $ P(x, y) $ 가 참이면 참이다. 즉 모든 $ x \in X $ 와 모든 $ y \in Y $ 에 대해 $ P(x, y) $ 가 거짓이면 거짓이다.

 

이러한 다중 한정된 명제에 대해 다음과 같이 의사 코드로 나타낼 수도 있다.

$ P $ 가 논의영역이 $ \{ d_1, d_2, \dots, d_n \} \times \{ d_1, d_2, \dots, d_n \} $ 인 명제함수라 하자. 다음의 의사코드는 $ \forall x \forall y P(x, y) $ 가 참인지 거짓인지 결정한다.

for i = 1 to n
    for j = 1 to n
        if (not P(d_i, d_j))
            return false
return true

다음의 의사코드는 $ \forall x \exists y P(x, y) $ 가 참인지 거짓인지 결정한다.

exists_dj(i) {
    for j = 1 to n
        if (P(d_i, d_j))
            return true
    return false
}

for i = 1 to n
    if (not exists_dj(d_i))
        return false
return true

 

한정된 문장에서 적용할 수 있었던 드모르간의 법칙은 다중 한정된 문장에서 다음과 같이 적용할 수 있다.

$$ \lnot \text{ } (\forall x \exists y P(x, y)) \equiv \exists x \lnot \text{ } (\exists y P(x, y)) \equiv \exists x \forall y \lnot \text{ } P(x, y) $$