[이산 수학] 명제 함수와 한정자

명제 함수와 한정자

• 명제의 정의에 따라 식 `x > 10` 은 `x` 값이 정해지지 않았으므로 진릿값을 판별할 수 없어 명제가 아니다. 그러나 `x` 의 값이나 범위가 주어진다면 진릿값을 판별할 수 있으므로 명제가 될 수 있다.
• 이와 같이 범위가 주어진 변수를 포함하는 명제를 명제 함수라 하고, 주어진 범위를 논의 영역이라고 한다.

 

명제 함수(Propositional Function : $P(x)$)

논의 영역이 주어진 변수 `x` 를 포함하여 진릿값을 판별할 수 있는 문장이나 수식

 

논의 영역(Domain of Discource : $D$)

명제 함수에 포함된 변수 `x` 의 범위나 값

 

• 명제 함수는 일반적으로 `P, Q, R, \codts` 과 같은 대문자와 명제 함수에 포함된 변수를 함께 표시한다.
  • 명제 함수의 예)
    • `P(x)` : 정수 `x` 에 대하여 $|x| ≤ 0$ 을 만족하는 정수가 적어도 한 개는 있다.
    • `Q(x, y)` : 실수 `x, y` 에 대하여 `x = 2y` 를 만족하는 `x, y` 는 하나도 없다.

 

한정자(Quantifier)

• 앞의 예제와 같이 논의 영역이 특정 값으로 주어질 수도 있으나, 다음과 같이 값이나 원소의 범위 형태로 주어질 수도 있다.
  • $D = \{ x \; | \; 0 ≤ x ≤ 100, \; x ∈ Z \}$
• 논의 영역이 범위 형태로 주어지는 경우, 주어진 범위에 포함되는 값들이 모두 명제 함수를 참(T)으로 만드는지, 아니면 일부 값만 명제 함수를 참(T)으로 만드는지, 혹은 범위 내의 어느 값도 명제 함수를 참(T)으로 만들지 않는지에 따라 명제 함수의 진릿값이 달라질 수 있다.
• 그러므로 범위 형태로 논의 영역이 주어지는 경우 명제 함수가 논의 영역의 전체 값(원소)에 대한 것인지, 혹은 일부에 대한 것인지를 표시해야 하는데, 이를 한정자(Quantifier)라고 한다.
• 정리하면, 논의 영역이 범위 형태로 주어지는 경우, 명제 함수에 포함되는 모든 변수가 한정자에 의해 제한된 구속 변수여야만 명제 함수의 정확한 진릿값을 판별할 수 있다.
• 한정자는 전체 한정자와 존재 한정자로 구분된다.

 

구속 변수와 자유 변수

명제 함수를 구성하는 변수는 다음과 같이 구분할 수 있다.

• 구속 변수(Binding Variable) : 한정자에 의해 범위가 제한되는 변수
• 자유 변수(Free Variable) : 한정자에 의해 범위가 제한되지 않는 변수

 

전체 한정자(Universal Quantifier : $\forall$ )

논의 영역에 포함되는 모든 값(원소)을 의미
논의 영역 `D` 에 포함되는 모든 `x` 에 대한 명제 $P(x) \; : \; \forall \; xP(x)$

• 전체 한정자로 논의 영역의 범위가 주어진 명제 함수 `P(x)` 는 $\forall \; xP(x)$ 로 표기하며, '모든 `x` 에 대하여 `P(x)` 이다' 라고 읽는다.
• $\forall \; xP(x)$ 는 명제 함수 `P(x)` 의 진릿값이 논의 영역에 포함된 모든 원소에 대하여 참(T)이면 명제 함수의 진릿값을 참(T)으로 판단한다.
• 그러나 논의 영역에 포함되는 원소 중 하나에 대해서라도 명제 함수가 거짓(F)이면 그 명제 함수는 거짓(F)으로 판단한다.

 

예 1 

• 논의 영역 `D` 가 정수 집합이고, 명제 함수 `P(x)` 가 '`x` 는 실수이다.' 이라고 하자.
• 그러면 $\forall \; xP(x)$ 는 '논의 영역 `D` 의 모든 `x` 는 실수이다.' 이고, 논의 영역 `D` 에 포함되는 정수는 모든 실수에 포함되므로 $\forall \; xP(x)$ 의 진릿값은 참(T)이라고 판단한다.

 

예 2 

• 논의 영역 `D` 가 정수 집합이고, 명제 함수 `P(x)` 가 '`x` 는 자연수이다.' 이라고 하자.
• 그러면 $\forall \; xP(x)$ 는 '논의 영역 `D` 의 모든 `x` 는 자연수이다.' 이고, 논의 영역 `D` 에 포함되는 정수 중 일부인 0과 음수는 자연수가 아니므로, 논의 영역 `D` 의 모든 값이 자연수인 것은 아니므로 $\forall \; xP(x)$ 의 진릿값은 거짓(F)이라고 판단한다.

 

존재 한정자(Existential Quantifier : $\exists$ )

논의 영역에 포함되는 모든 값(원소) 중 일부를 의미
논의 영역 `D` 에 포함되는 모든 `x` 에 대한 명제 $P(x) \; : \; \exists\; xP(x)$

• 존재 한정자로 논의 영역의 범위가 주어진 명제 함수 `P(x)` 는 $\exists\; xP(x)$ 로 표기하며, '어떤 `x` 에 대하여 `P(x)` 이다' 라고 읽는다.
• $\exists \; xP(x)$ 는 명제 함수 `P(x)` 의 진릿값이 논의 영역에 포함된 일부(하나 이상) 원소에 대하여 참(T)이면 명제 함수의 진릿값을 참(T)으로 판단한다.
• 그러나 논의 영역의 모든 원소에 대하여 명제 함수가 거짓(F)이면 그 명제 함수는 거짓(F)으로 판단한다.

 

예 1 

• 논의 영역 `D` 가 정수 집합이고, 명제 함수 `P(x)` 가 '`x` 는 자연수이다.' 이라고 하자.
• 그러면 $\exists\; xP(x)$ 는 '논의 영역 `D` 의 어떤 `x` 는 자연수이다.' 이고, 논의 영역 `D` 에 포함되는 정수 중 일부인 양수는 곧 자연수이므로 $\exists \; xP(x)$ 의 진릿값은 참(T)이라고 판단한다.

 

예 2 

• 논의 영역 `D` 가 정수 집합이고, 명제 함수 `P(x)` 가 '`x` 는 허수이다.' 이라고 하자.
• 그러면 $\exists\; xP(x)$ 는 '논의 영역 `D` 의 어떤 `x` 는 허수이다.' 이고, 논의 영역 `D` 에 포함되는 정수 모두가 허수가 아니므로, $\exists \; xP(x)$ 의 진릿값은 거짓(F)이라고 판단한다.

 

한정된 명제 함수

• 논의 영역이 범위 형태로 주어진 명제 함수의 진릿값을 판별하기 위해서는 명제 함수를 구성하는 변수들이 구속 변수여야 한다.
• 그러므로 명제 함수에 포함되는 변수가 2개 이상인 경우에는 모든 변수에 대하여 한정자를 표시해야 한다.
• 예를 들어, 변수 `x, y` 를 갖는 명제 함수 `P(x, y)` 에 대해서는 8가지($2^{2}×2$)의 한정된 명제 함수 표현이 존재하며, 각 표현에 대한 문장 표현은 다음과 같다.

한정된 명제 함수	문장 표현
$\forall x \; \forall y \; P(x, y)$	모든 `x` 와 모든 `y` 에 대하여, `P(x, y)` 가 성립한다.
$\forall x \; \exists y \; P(x, y)$	모든 `x` 에 대하여, `P(x, y)` 를 만족하는 `y` 가 적어도 하나 존재한다.
$\exists x \; \forall y \; P(x, y)$	어떤 `x` 가 존재하여 모든 `y` 에 대해, `P(x, y)` 가 성립한다.
$\exists x \; \exists y \; P(x, y)$	어떤 `x` 에 대하여, `P(x, y)` 를 만족하는 `y` 가 적어도 하나 존재한다.
$\forall y \; \forall x \; P(x, y)$	모든 `y` 와 모든 `x` 에 대하여, `P(x, y)` 가 성립한다.
$\forall y \; \exists x \; P(x, y)$	모든 `y` 에 대하여, `P(x, y)` 를 만족하는 `x` 가 적어도 하나 존재한다.
$\exists y \; \forall x \; P(x, y)$	어떤 `y` 가 존재하여 모든 `x` 에 대해, `P(x, y)` 가 성립한다.
$\exists y \; \exists x \; P(x, y)$	어떤 `y` 에 대하여, `P(x, y)` 를 만족하는 `x` 가 적어도 하나 존재한다.

 

예 : 논의 영역 `D` 인 $\{d \; | \; 0 < d < ≤ 3, \; d ∈ N \}$ 에서 변수 `x, y` 를 갖는 명제 함수 `P(x, y)` 가 `xy > 5` 인 경우

• 논의 영역의 각 값을 명제 함수 `P(x, y)` 에 입력한 결과는 다음과 같다.

$x = 1, \; y = 1$ 일 때, `1 · 1 < 5` ∴ 거짓(F)
$x = 1, \; y = 2$ 일 때, `1 · 2 < 5` ∴ 거짓(F)
$x = 1, \; y = 3$ 일 때, `1 · 1 < 5` ∴ 거짓(F)
$x = 2, \; y = 1$ 일 때, `2 · 1 < 5` ∴ 거짓(F)
$x = 2, \; y = 2$ 일 때, `2 · 2 < 5` ∴ 거짓(F)
$x = 2, \; y = 3$ 일 때, `2 · 3 > 5` ∴ 참(T)
$x = 3, \; y = 1$ 일 때, `3 · 1 < 5` ∴ 거짓(F)
$x = 3, \; y = 2$ 일 때, `3 · 2 > 5` ∴ 참(T)
$x = 3, \; y = 3$ 일 때, `3 · 3 > 5` ∴ 참(T)

(1) $\forall x \; \forall y \; P(x, y) ≡ \forall y \; \forall x \; P(x, y)$ 
모든 `x` (또는 `y`) 의 각 값이 모든 `y` (또는 `x`) 값에 대하여 참(T)인 경우에만 참(T)으로 판별할 수 있는데, 이에 해당하는 경우가 없으므로 거짓(F)이다.

(2) $\forall x \; \exists y \; P(x, y) ≡ \exists y \; \forall x \; P(x, y)$
`x = 1` (또는 `y = 1`)인 경우에는 모든 `y` (또는 `x`)에 대하여 거짓(F)이다.

(3) $\exists x \; \forall y \; P(x, y) ≡ \forall y \; \exists x \; P(x, y)$
어떤 `x` 값(또는 `y` 값) 도 모든 `y` (또는 모든 `x`) 에 대하여 참(T)인 경우가 없으므로 거짓(F)이다.

(4) $\exists x \; \exists y \; P(x, y) ≡ \exists y \; \exists x \; P(x, y)$
`x = 2, \; y = 3` 인 경우, `x = 3 \; y = 2` 인 경우, `x = 3, \; y = 3` 인 경우에 참(T)이다.

 

728x90

 

한정자와 논리합(OR) / 논리곱(AND)

• 명제 함수도 명제이므로 논리 연산이 가능하다. 그러므로 논리 연산이 한정자에 미치는 영향도 이해해야 한다.
• 한정자로 제한된 명제 함수의 논리합(OR)과 논리곱(AND) 연산은 다음과 같다.

$\forall x \; (P(x) \land Q(x)) ≡ \forall x \; P(x) \land \forall x \; Q(x)$
$\exists x \; (P(x) \lor Q(x)) ≡ \exists x \; P(x) \lor \exists x \; Q(x)$

 

증명 : $\forall x \; (P(x) \land Q(x)) ≡ \forall x \; P(x) \land \forall x \; Q(x)$

• 이 식이 성립함을 증명하려면 다음의 쌍방 조건 명제가 성립해야 한다.

$\{ \forall x \; (P(x) \land Q(x)) ≡$ T  $ \} ↔ \{ \forall x \; P(x) \land \forall x \; Q(x) ≡$ T  $\}$

 

• 이 쌍방 조건 명제는 다음과 같이 2개의 조건 명제를 논리곱으로 연산하는 논리식과 동치이다.

$\{\; \forall x \; (P(x) \land Q(x)) ≡$ T  $ \} → \{ \forall x \; P(x) \land \forall x \; Q(x) ≡$ T  $\}$	$\land$	$\{\; \forall x \; P(x) \land \forall x \; Q(x) ≡$ T  $\}$ → $\{ \forall x \; (P(x) \land Q(x)) ≡$ T  $ \}$
(1)		(2)

 

• 그러므로 쌍방 조건 명제  $\{ \forall x \; (P(x) \land Q(x)) ≡$ T  $ \} ↔ \{ \forall x \; P(x) \land \forall x \; Q(x) ≡$ T  $\}$ 가 성립함을 증명하기 위해서는 조건 명제 (1), (2)가 모두 참(T)임을 증명하면 된다.
• 이 때, 명제 함수 `P(x)` 와 `Q(x)` 의 논의 영역은 다음과 같다.

 

(1) $\{\; \forall x \; (P(x) \land Q(x)) ≡$ T $ \}$ $→ \{\; \forall x \; P(x) \land \forall x \; Q(x) ≡$ T $\}$ 가 참(T)임을 증명

• $\forall x \; (P(x) \land Q(x)) ≡$ T  라고 가정하면, 논의 영역에 속하는 모든 `x` 에 대하여 $P(x) \land Q(x)$ 가 참(T)임을 의미하고, 이는 논의 영역에 속하는 모든 `x` 에 대하여 `P(x)` 도 참(T)이고 `Q(x)` 도 참(T)이므로 성립한다.
• 즉, $\forall x \; P(x)$ 도 참(T), $\forall x \; Q(x)$ 도 참(T)이므로 $\forall x \; P(x) \land \forall x \; Q(x) ≡$ T  가 성립한다.

 

(2) $\{\; \forall x \; P(x) \land \forall x \; Q(x)) ≡$ T  $\}$ → $\{ \forall x \; (P(x) \land Q(x)) ≡$ T  $ \}$ 가 참(T)임을 증명

• $\forall x \; P(x) \land \forall x \; Q(x)) ≡$ T  라고 가정하면, 논의 영역에 속하는 모든 `x` 에 대하여 $P(x)$ 도 참(T)이고, $Q(x)$ 도 참(T)이다. 그러면 논의 영역에 속하는 모든 `x` 에 대하여 $P(x) \land Q(x)$ 가 참(T)이므로 $\forall x \; (P(x) \land Q(x)) ≡$ T  가 성립한다.

 

• 결론적으로 조건 명제 (1)과 (2)가 모두 참(T)이므로 쌍방 조건 명제 $\{ \forall x \; (P(x) \land Q(x)) ≡$ T  $ \} ↔ \{ \forall x \; P(x) \land \forall x \; Q(x) ≡$ T  $\}$ 가 참(T)이다.
• 따라서 전체 한정자($\forall$ )에 대한 논리곱(AND) 연산 $\forall x \; (P(x) \land Q(x)) ≡ \forall x \; P(x) \land \forall x \; Q(x)$ 가 성립한다고 정리할 수 있다.
  • 존재 한정자($\exists$ )에 대한 논리합(OR) 연산 또한 같은 방법으로 증명할 수 있다.

 

• 한편, 전체 한정자($\forall$ )의 경우에는 논리합(OR)에 대하여, 존재 한정자($\exists$ )의 경우에는 논리곱(AND)에 대하여 논리식이 언급되지 않음을 알 수 있다. 그 이유는 서로 간에 동치 관계가 성립되지 않기 때문이다.
  • $\forall x \; (P(x) \lor Q(x))$ 와 $\forall x \; P(x) \lor \forall x \; Q(x)$
  • $\exists x \; (P(x) \land Q(x))$ 와 $\exists x \; P(x) \land \exists x \; Q(x)$

 

$\exists x \; (P(x) \land Q(x))$ 와 $\exists x \; P(x) \land \exists x \; Q(x)$ 사이에 동치 관계가 성립하지 않는 이유?

• 논의 영역이 $D = \{ x | x \in \mathbb{R} \}$ 이고, 명제 함수 `P(x)` 와 `Q(x)` 가 다음과 같다고 하자.

$$P(x) : x > 0, \quad Q(x) : x < 0$$

• 이 때, $P(x) \land Q(x)$ 가 성립하는 `x` 값이 존재하지 않으므로, $\exists x \; (P(x) \land Q(x))$ 는 거짓(F)이다.
• 반면, 논의 영역 `D` 에 속하는 값 중, 양의 실수 `x` 에 대해서는 `P(x)` 가 참(T)이므로 $\exists x \; P(x)$ 는 참(T)이고, 논의 영역 `D` 에 속하는 값 중 음의 실수 `x` 에 대해서는 `Q(x)` 가 참(T)이므로 $\exists x \; Q(x)$ 도 참(T)이다.
  • 그러므로 $\exists x \; P(x) \land \exists x \; Q(x)$ 는 참(T)이다.
• 결과적으로 $\exists x \; (P(x) \land Q(x))$ 의 진릿값과 $\exists x \; P(x) \land \exists x \; Q(x)$ 의 진릿값이 서로 다르므로, $\exists x \; (P(x) \land Q(x)) \not≡ \exists x \; P(x) \land \exists x \; Q(x)$ 이다.
  • 마찬가지로 $\forall x \; (P(x) \lor Q(x)) \not≡ \forall x \; P(x) \lor \forall x \; Q(x)$ 가 성립한다.

 

한정자와 부정(NOT)

• 한정자로 제한된 명제 함수의 부정(NOT) 연산은 다음과 같다.

$\neg \forall x \; P(x) ≡ \exists x \; (\neg P(x))$
$\neg \exists x \; P(x) ≡ \forall x \; (\neg P(x))$

 

• 예를 들어, 논의 영역이 $D = \{ d | d ∈ \text{과일} \}$ 이고, 명제 함수 `P(x)` 가 '이 상자에 있는 `x` 는 사과이다' 라고 하면, '이 상자에 있는 모든 과일은 사과이다' 라는 명제는 다음과 같이 기호로 표현할 수 있다.

'이 상자에 있는 모든 과일은 사과이다' : $\forall x \; P(x)$

• 명제 $\forall x \; P(x)$ 의 부정(NOT)은 기호로 $\neg \forall x \; P(x)$ 로 표현할 수 있다.
  • 그렇다면, $\neg \forall x \; P(x)$ 를 문장으로 표현하면 '이 상자에 있는 모든 과일은 사과가 아니다' 일까?
  • 그렇지 않다. $\neg \forall x \; P(x)$ 의 정확한 표현은 '이 상자에 있는 어떤 과일은 사과가 아니다' 이다.
    • 왜냐하면 '이 상자에 있는 모든 과일은 사과이다' 라는 명제는 상자 안에 사과 외의 다른 과일이 하나라도 있다면 거짓(T)이기 때문이다.
• '이 상자에 있는 어떤 과일은 사과가 아니다' 에 대한 기호 표현은 다음과 같다.

'이 상자에 있는 어떤 과일은 사과가 아니다' : $\exists x \; (\neg P(x))$

• 그러므로 $\forall x \; P(x)$ 의 부정(NOT)인 $\neg \forall x \; P(x)$ 는 $\exists x \; (\neg P(x))$ 와 동치이다.

 

• 둘 이상의 변수를 구속 변수로 한정한 명제 함수에 대해서는 부정(NOT) 연산자를 적용한 한정자부터 순차적으로 오른쪽으로 부정(NOT) 연산을 적용한다고 생각하면 쉽다.

$$\neg \forall x \; \forall y \; P(x, y) ≡ \exists x \; \neg \forall y \; P(x, y) ≡ \exists x \; \exists y \; \neg P(x, y)$$

$$\exists x \; \neg \forall y \; \exists z \; P(x, y, z) ≡ \exists x \; \exists y \; \neg \exists z \; P(x, y, z) ≡ \exists x \; \exists y \; \forall z \; \neg P(x, y, z)$$

 

• 만약 명제 함수의 논리합(OR) 또는 논리곱(AND)이 적용되어 있을 경우, 필요하다면 드므로간의 법칙을 적용한다.

$\neg( \forall x \; \exists y \; P(x, y) \land \exists y \; \forall z \; Q(x, y))$
$≡ \neg \forall x \; \exists y \; P(x, y) \lor \neg \exists y \; \forall z \; Q(y, z)$
$≡ \exists x \; \neg \exists y \; P(x, y) \lor \forall y \; \neg \forall z \; Q(y, z)$
$≡ \exists x \; \forall y \; \neg P(x, y) \lor \forall y \; \exists z \; \neg Q(y, z)$