1.2 The Syntax of First-order Logic
First-order logic에서 말하는 formula의 의미는 propositional logic에서와 다르지 않다. 먼저 atomic formula를 정의하고 복잡한 formula를 만들어 낼 규칙을 정리한다.
Propositional logic에서는 formula들을 대문자 $F$, $G$, $H$ 등으로 나타냈다. First-order logic에서는 formula를 그리스 문자 $\varphi$, $\psi$, $\theta$ 등으로 쓴다.
Formula가 무엇인지 정의하기 전에, 용어 term을 정의해야 한다.1 Term의 정의는 다음 두 규칙으로부터 만들어진다.
$(T2)$ If $f$ is an $m$-ary function and $t_1, \dots, t_m$ are terms, then $f(t_1, \dots, t_m)$ is also a term.
Definition 1.2.1
Atomic formula란 $t_1=t_2$ 또는 $R(t_1, \dots, t_n)$ 형태를 갖는 formula를 말한다. 여기서 $R$은 $n$-ary relation이고 $t_1, \dots, t_n$은 term이다.
Propositional logic 때처럼, 몇 가지 기호는 primitive로 지정해야 할 필요가 있다. 여기서 우리는 $\neg$, $\wedge$, $\exists$를 primitive로 정할 것이다. 모든 first-order logic의 formula는 다음 세 rule로부터 만들어진다.
$(R2)$ If $\varphi$ and $\psi$ are fomulas then so is $\varphi \wedge \psi$.
$(R3)$ If $\varphi$ is a fomula, then so is $\exists x \varphi$ for any variable $x$.
$(R1)$, $(R2)$는 propositional logic에도 있었다. 새로 추가된 건 $(R3)$.
Definition 1.2.2
Symbol들의 stringd이 first-order logic의 formula라는 것은 atomic formula에 규칙 $(R1)$, $(R2)$, $(R3)$을 반복해서 적용해서 만들어졌다는 것이다.
$\vee$, $\rightarrow$, $\leftrightarrow$의 정의는 propositional logic과 같으니 생략. 우리는 $\forall x \varphi$를 $\neg \exists x \neg \varphi$로 정의한다. 임의의 formula $\varphi$에 대해 두 formula $\forall x \varphi$와 $\neg \exists x \neg \varphi$는 자유롭게 바꿔 쓸 수 있다. 따라서 $(R1)$과 $(R3)$에 따르면,
Example 1.2.3
$\forall y P(x,y) \vee \exists y Q(x,y)$ 는 formula지만, $x(Q \forall P) y \exists )( \vee$는 formula가 아니다.
Semantics에 대해서는 나중에 이야기하자. 기호의 순서에 대해서 말하자면, 괄호가 없을 때는 다음 규칙을 따른다.
Example 1.2.4
$\exists x P(x,y) \vee Q(x,y)$는 $(\exists x P(x,y)) \vee (Q(x,y))$를 의미하고, $\forall y P(x,y) \rightarrow Q(x,y)$는 $(\forall y P(x,y)) \rightarrow (Q(x,y))$를 의미한다.
다음 convention을 도입하기로 한다. 마찬가지로 Propositional logic에서 쓰던 것.
$(C2)$ For any formulas $F$, $G$, and $H$, we view $F \wedge G \wedge H$ as the same formula as $(F \wedge G) \wedge H$ and $F \vee G \vee H$ as the same formula as $(F \vee G) \vee H$.
이제 필요없는 괄호를 떨궈버릴 수 있다.
Example 1.2.5
$\neg (\exists x (\forall y (\exists z (R(x, y, z)))))$ 대신 $\neg \exists x \forall y \exists z R(x, y, z)$로 쓸 수 있다.
다음은 subformula다.
Definition 1.2.6
$\varphi$가 first-order logic의 formula라고 하자. $\theta$가 $\varphi$의 subformula라는 의미는 다음과 같이 inductive하게 정의된다.
만약 $\varphi$가 atomic이면, $\theta$가 $\varphi$의 subformula $\Leftrightarrow$ $\theta = \varphi$.
만약 $\varphi$가 $\neg \psi$이면, $\theta$가 $\varphi$의 subformula $\Leftrightarrow$ $\theta = \varphi$ 또는 $\theta$가 $\psi$의 subformula.
만약 $\varphi$가 $\psi_1 \wedge \psi_2$이면, $\theta$가 $\varphi$의 subformula $\Leftrightarrow$ $\theta = \varphi$ 또는 $\theta$가 $\psi_1$의 subformula 또는 $\theta$가 $\psi_2$의 subformula.
만약 $\varphi$가 $\exists x \psi$이면, $\theta$가 $\varphi$의 subformula $\Leftrightarrow$ $\theta = \varphi$ 또는 $\theta$가 $\psi$의 subformula.
Example 1.2.7
$\varphi$가 $\exists x \forall y P(x,y) \vee \forall x \exists y Q(x,y)$라고 하자.
$\varphi$의 subrofmula를 전부 쓰면 $\exists x \forall y P(x,y)$, $\forall y P(x,y)$, $P(x,y)$, $\forall x \exists y Q(x,y)$, $\exists y Q(x,y)$, $Q(x,y)$, 마지막으로 $\varphi$ 자기 자신.
Formula $\varphi$의 free variable은 $\varphi$에 등장하면서 양화되지 않은 것을 의미한다.
예를 들어, formula $\forall y R(x, y)$에서 $x$는 free variable이나 $y$는 그렇지 않다. $\forall$에 의해 양화되었기 때문.
임의의 first-order formula $\varphi$에 대해 $free(\varphi)$는 $\varphi$의 free variable들의 집합을 말한다. $free(\varphi)$는 다음과 같이 inductive하게 정의된다.:
$\varphi$가 atomic이면, $free(\varphi)$는 $\varphi$에 등장하는 모든 variable들의 set.
$\varphi$가 $\neg \psi$이면, $free(\varphi) = free(\psi)$.
$\varphi$가 $\psi_1 \wedge \psi_2$이면, $free(\varphi) = free(\psi) \cup free(\theta)$.
$\varphi$가 $\exists x \psi$이면, $free(\varphi) = free(\psi) - \{x\}$.
Definition 1.2.8
First-order logic의 sentence란, free variable이 없는 formula를 말한다.
Example 1.2.9
$\exists x \forall y P(x,y) \vee \forall x \exists y Q(x,y)$은 sentence이다. 반면 $\exists x P(x,y) \vee \forall x Q(x,y)$는 sentence가 아닌데 $y$가 free variable이기 때문.
Example 1.2.10
$\varphi$가 formula $\forall y \exists x f(x) = y$라고 하자. 그러면 $\varphi$는 sentence이다.
Formula $f(x)=y$, $\exists x f(x) = y$는 모두 $\varphi$의 subformula이지만, 둘 다 sentence는 아니다.
Free variable과 반대로, $\varphi$의 bound variable은 quantifier를 가지는 variable을 말한다. $bnd(\varphi)$로 표기하며, 정의는 마찬가지로 다음을 따른다.:
$\varphi$가 atomic이면, $bnd(\varphi) = \emptyset$.
$\varphi$가 $\neg \psi$이면, $bnd(\varphi) = bnd(\psi)$.
$\varphi$가 $\psi_1 \wedge \psi_2$이면, $bnd(\varphi) = bnd(\psi) \cup bnd(\theta)$.
$\varphi$가 $\exists x \psi$이면, $bnd(\varphi) = bnd(\psi) \cup \{x\}$.
$\varphi$의 모든 variable은 $free(\varphi)$ 또는 $bnd(\varphi)$ 중 하나에 속한다.
그런데 사실, 두 set은 disjoint할 필요는 없다!
Example 1.2.11
Formula $\exists x (R(x,y) \wedge \exists y R(y, x))$를 생각해 보자. Variable $y$는 $R(x,y)$ 안에서는 free이고 $\exists y R(y, x)$ 안에서는 bound이다. 반면 variable $x$는 bound variable로만 나타난다.
따라서, 위 formula를 $\psi$라고 하면, $free(\psi) = \{y\}$이며, $bnd(\psi) = \{x, y\}$이다.
Notation 1.2.12
$x_1, x_2, \cdots, x_n$을 free variable로 갖는 formula를 $\varphi(x_1, x_2, \cdots, x_n)$로 쓴다. $\varphi$ 내에서 $x_i$의 각 free occurence를 term $t_i$로 대체해서 얻은 formula는 $\varphi(t_1, t_2, \cdots, t_n)$로 쓴다.
이 notation을 사용할 때, 각 $t_i$는 $bnd(\varphi)$의 어떤 variable에도 포함되어 있지 않다는 가정이 필요하다.
예를 들어, $\varphi(x)$가 $\exists y \neg (x=y)$이면, $\varphi(y)$로의 대체는 불가능하다.
Free variable의 존재는 formula와 sentence를 구분하는 중요한 요소. 이는 propositional logic에서는 없었던 내용이다.
참(Truth)의 개념은 오로지 sentence에서만 가능하다. Formula $y=x+1$이 참인지 아닌지를 묻는 건 말이 안 된다. 그러나 sentence $\forall y \exists x (y=x+1)$가 참인지 아닌지 묻는 건 가능하다.
-
그런데 term은 용어라는 뜻이다. 참... ↩