2강. 술어논리와 한정기호

명제논리는 “ $p$ 그리고 $q$ ”처럼 문장을 통째로 다룹니다. 그런데 “모든 자연수는 0 이상입니다”나 “제곱하면 2가 되는 유리수가 있습니다” 같은 문장은 안쪽 구조가 중요합니다. 이 강에서는 변수가 들어간 문장과, 그 변수를 묶는 두 기호를 다룹니다.

2.1 술어

정의 2.1 (술어). 변수를 포함하고, 변수에 값을 넣으면 명제가 되는 문장을 술어(predicate)라 합니다. 변수가 가질 수 있는 값의 모임을 영역(정의역)이라 합니다.

$P(x)$ 를 “ $x > 3$ ”이라 하고 영역을 정수라 합시다. $P(5)$ 는 참인 명제, $P(1)$ 은 거짓인 명제입니다. $P(x)$ 자체는 $x$ 가 정해지지 않았으므로 명제가 아닙니다.

변수가 둘인 술어도 있습니다. $Q(x, y)$ 를 “ $x + y = 0$ ”이라 하면 $Q(2, -2)$ 는 참이고 $Q(1, 1)$ 은 거짓입니다.

2.2 전칭과 존재

정의 2.2 (전칭 한정기호). $\forall x\, P(x)$ 는 “영역의 모든 $x$ 에 대해 $P(x)$ 가 참”이라는 명제입니다. “모든 $x$ 에 대해”라고 읽습니다.

정의 2.3 (존재 한정기호). $\exists x\, P(x)$ 는 “영역에 $P(x)$ 를 참으로 만드는 $x$ 가 적어도 하나 있다”는 명제입니다. “어떤 $x$ 가 있어”라고 읽습니다.

한정기호가 붙으면 변수는 더 이상 자유롭지 않고 문장 전체가 참 또는 거짓이 됩니다. 이렇게 한정기호에 묶인 변수를 묶인 변수(bound variable), 묶이지 않은 변수를 자유 변수(free variable)라 합니다.

진릿값은 영역에 따라 달라집니다.

명제	영역 = 자연수 $\{0, 1, 2, \dots\}$	영역 = 정수
$\forall x\, (x \ge 0)$	참	거짓 ( $x = -1$ )
$\exists x\, (x + 3 = 1)$	거짓	참 ( $x = -2$ )
$\forall x\, (x^2 \ge 0)$	참	참

영역이 유한하면 한정기호는 연결사로 풀어 쓸 수 있습니다. 영역이 $\{a_1, \dots, a_n\}$ 이면

\forall x\, P(x) \equiv P(a_1) \land \cdots \land P(a_n), \qquad \exists x\, P(x) \equiv P(a_1) \lor \cdots \lor P(a_n)

입니다. 그래서 $\forall$ 는 큰 “그리고”, $\exists$ 는 큰 “또는”으로 볼 수 있습니다.

예제 2.4. 영역이 $\{1, 2, 3, 4\}$ 이고 $P(x)$ 가 “ $x$ 는 짝수”일 때, $\forall x\, P(x)$ 는 $1$ 이 짝수가 아니므로 거짓입니다. $\exists x\, P(x)$ 는 $2$ 가 짝수이므로 참입니다.

2.3 한정기호의 부정

“모든 학생이 숙제를 냈다”의 부정은 “숙제를 내지 않은 학생이 있다”입니다. “모든 학생이 숙제를 내지 않았다”가 아닙니다.

정리 2.5 (한정기호의 드모르간 법칙).

\neg \forall x\, P(x) \equiv \exists x\, \neg P(x), \qquad \neg \exists x\, P(x) \equiv \forall x\, \neg P(x)

증명. 첫째 식: $\forall x\, P(x)$ 가 거짓이라는 것은 $P(x)$ 가 거짓인 $x$ 가 적어도 하나 있다는 뜻이고, 이는 $\exists x\, \neg P(x)$ 가 참이라는 뜻입니다. 둘째 식은 첫째 식에 $\neg P$ 를 넣고 양변을 부정하면 나옵니다. □

부정을 안으로 밀어 넣을 때마다 $\forall$ 와 $\exists$ 가 서로 바뀌고, 맨 안쪽의 술어가 부정됩니다.

예제 2.6. “모든 $\varepsilon > 0$ 에 대해 어떤 $N$ 이 있어, 모든 $n \ge N$ 에 대해 $|a_n| < \varepsilon$ ”(수열이 0으로 수렴한다)의 부정은

\exists \varepsilon > 0\; \forall N\; \exists n \ge N\; (|a_n| \ge \varepsilon)

입니다. “아무리 멀리 가도 $\varepsilon$ 이상 떨어진 항이 또 나온다”는 뜻입니다.

2.4 한정기호의 순서

한정기호가 여럿이면 순서가 뜻을 바꿉니다. 영역을 정수라 하고 $Q(x, y)$ 를 “ $x + y = 0$ ”이라 합시다.

$\forall x\, \exists y\, Q(x, y)$ : 모든 $x$ 마다 (그 $x$ 에 맞춘) $y$ 가 있습니다. $y = -x$ 로 잡으면 되므로 참입니다.
$\exists y\, \forall x\, Q(x, y)$ : 어떤 하나의 $y$ 가 모든 $x$ 와 더해 0이 됩니다. 그런 $y$ 는 없으므로 거짓입니다.

정리 2.7. $\exists y\, \forall x\, Q(x, y)$ 이면 $\forall x\, \exists y\, Q(x, y)$ 입니다. 거꾸로는 일반적으로 성립하지 않습니다.

증명. 모든 $x$ 에 통하는 $y_0$ 가 있으면, 각 $x$ 에 대해 바로 그 $y_0$ 를 고르면 됩니다. 거꾸로가 틀린 예는 위의 $x + y = 0$ 입니다. □

같은 종류의 한정기호끼리는 순서를 바꿔도 됩니다: $\forall x\, \forall y \equiv \forall y\, \forall x$ , $\exists x\, \exists y \equiv \exists y\, \exists x$ .

2.5 문장을 기호로 옮기기

문장	기호
모든 정수의 제곱은 0 이상입니다	$\forall x \in \mathbb{Z}\, (x^2 \ge 0)$
짝수인 소수가 있습니다	$\exists x\, (\text{짝수}(x) \land \text{소수}(x))$
모든 소수는 홀수입니다 (거짓)	$\forall x\, (\text{소수}(x) \to \text{홀수}(x))$
가장 큰 정수는 없습니다	$\forall x \in \mathbb{Z}\, \exists y \in \mathbb{Z}\, (y > x)$

“모든 A는 B다”는 $\forall x\, (A(x) \to B(x))$ 로, “B인 A가 있다”는 $\exists x\, (A(x) \land B(x))$ 로 씁니다. 짝을 바꿔 $\forall$ 와 $\land$ , $\exists$ 와 $\to$ 를 쓰면 뜻이 달라집니다. 예를 들어 $\exists x\, (A(x) \to B(x))$ 는 A가 아닌 $x$ 하나만 있어도 참이 되어 버립니다.

쓰이는 곳. 논문의 정의와 정리는 '모든 $\varepsilon > 0$ 에 대해 어떤 $\delta > 0$ 이 있어'처럼 한정기호가 겹친 문장으로 쓰입니다. 한정기호의 순서를 바꾸면 뜻이 달라진다는 것을 알아야 수렴, 연속, 일반화 오차의 정의를 정확히 읽을 수 있습니다.

2.6 이 장의 요약

술어는 값을 넣으면 명제가 되는 문장이고, 한정기호는 변수를 묶어 문장 전체를 명제로 만듭니다.
$\neg\forall \equiv \exists\neg$ , $\neg\exists \equiv \forall\neg$ .
$\exists y\,\forall x$ 는 $\forall x\,\exists y$ 보다 강합니다.

문제

2.1 [개념] · 확인 문제

영역이 정수일 때 참인 명제는?

$\forall x\, (x^2 > 0)$
$\exists x\, (x^2 = 2)$
$\forall x\, \exists y\, (y = x + 1)$
$\exists y\, \forall x\, (y > x)$

힌트 1

반례 하나로 $\forall$ 문장을 깨고, 예 하나로 $\exists$ 문장을 세웁니다.

정답

풀이

1번은 $x = 0$ 이 반례입니다. 2번은 $\sqrt{2}$ 가 정수가 아니므로 거짓입니다. 3번은 각 $x$ 마다 $y = x + 1$ 을 고르면 되므로 참입니다. 4번은 모든 정수보다 큰 정수 $y$ 가 있다는 뜻이고, $x = y$ 를 넣으면 깨지므로 거짓입니다.

2.2 [계산] · 확인 문제

$\neg\, \forall x\, \exists y\, (x < y)$ 와 동치인 것은?

$\exists x\, \forall y\, (x \ge y)$
$\forall x\, \exists y\, (x \ge y)$
$\exists x\, \exists y\, (x \ge y)$
$\forall x\, \forall y\, (x \ge y)$

힌트 1

부정을 한정기호 하나씩 안으로 옮기며 $\forall$ 와 $\exists$ 를 바꿉니다.

정답

풀이

$\neg\forall x\, \exists y\, (x < y) \equiv \exists x\, \neg\exists y\, (x < y) \equiv \exists x\, \forall y\, \neg(x < y) \equiv \exists x\, \forall y\, (x \ge y)$ 입니다.

2.3 [계산] · 확인 문제

영역이 $\{1, 2, 3, 4, 5, 6\}$ 일 때 각 명제의 진릿값을 T 또는 F로 씁니다.

명제	진릿값
$\forall x\, (x < 7)$	[?]
$\exists x\, (x^2 = 10)$	[?]
$\forall x\, \exists y\, (x + y = 7)$	[?]
$\exists x\, \forall y\, (x \le y)$	[?]
$\forall x\, \exists y\, (y = 2x)$	[?]

힌트 1

영역이 유한하므로 $x$ 를 하나씩 넣어 확인할 수 있습니다. 넷째 줄은 가장 작은 원소가 있는지 묻습니다.

정답

T
F
T
T
F

풀이

모든 원소가 7보다 작으므로 T.
제곱이 10인 원소가 없으므로 F.
각 $x$ 에 $y = 7 - x$ 를 고르면 $y$ 도 1부터 6 사이이므로 T.
$x = 1$ 이 모든 $y$ 이하이므로 T.
$x = 4$ 이면 $y = 8$ 이 영역에 없으므로 F.

2.4 [계산]

영역이 $\{1, 2, \dots, 10\}$ 일 때, $\exists y\, (x = 2y)$ 를 참으로 만드는 $x$ 는 몇 개일까요?

정답

풀이

$x = 2y$ 이고 $y$ 가 1부터 10 사이이므로 $x$ 는 영역 안의 짝수 $2, 4, 6, 8, 10$ 입니다. 5개입니다.

2.5 [개념]

“어떤 학생도 모든 문제를 풀지는 못했다”를 기호로 옮긴 것은? ( $S(x, y)$ : 학생 $x$ 가 문제 $y$ 를 풀었다)

$\forall x\, \exists y\, \neg S(x, y)$
$\exists x\, \forall y\, S(x, y)$
$\forall x\, \forall y\, \neg S(x, y)$
$\exists y\, \forall x\, \neg S(x, y)$

정답

풀이

“모든 문제를 푼 학생이 있다”는 $\exists x\, \forall y\, S(x, y)$ 이고, 문장은 그 부정입니다. $\neg\exists x\, \forall y\, S \equiv \forall x\, \exists y\, \neg S$ 이므로 1번입니다. “모든 학생마다 못 푼 문제가 하나는 있다”는 뜻입니다.

2.6 [증명]

$\forall x\, (P(x) \land Q(x)) \equiv \forall x\, P(x) \land \forall x\, Q(x)$ 임을 보입니다. 그리고 $\forall x\, (P(x) \lor Q(x))$ 와 $\forall x\, P(x) \lor \forall x\, Q(x)$ 는 동치가 아님을 반례로 보입니다.

풀이

왼쪽이 참이면 모든 $x$ 에서 $P(x)$ 와 $Q(x)$ 가 둘 다 참이므로 $\forall x\, P(x)$ 와 $\forall x\, Q(x)$ 가 모두 참입니다. 거꾸로 오른쪽이 참이면 임의의 $x$ 에서 $P(x)$ 도 $Q(x)$ 도 참이므로 $P(x) \land Q(x)$ 가 참입니다.

반례: 영역을 정수, $P(x)$ 를 “ $x$ 는 짝수”, $Q(x)$ 를 “ $x$ 는 홀수”라 합시다. 모든 정수는 짝수이거나 홀수이므로 $\forall x\, (P(x) \lor Q(x))$ 는 참입니다. 그러나 모든 정수가 짝수인 것도, 모든 정수가 홀수인 것도 아니므로 $\forall x\, P(x) \lor \forall x\, Q(x)$ 는 거짓입니다.