younghwanjoo1608

ㅎㅇ

10 minute read


Propositional logic의 semantics에서 $\wedge$와 $\neg$는 각각 “and”, “negation”과 같은 역할을 한다고 해석했다. 비슷하게 양화사 $\forall$, $\exists$는 각각 “for all”, “there exists”로 보면 된다.

그렇지만 논리학의 semantics는 좀 더 자세히 정의할 필요가 있다. 본 Section의 목표는 first-order logic의 semantics를 형식적으로 정의하는 것.


일단 간단한 예시로 다음 sentence를 보자.

\[\forall y \exists x f(x) = y\]

이 sentence를 해석해보자면, 모든 $y$에 대해 $x$가 존재하여 $f(x)=y$를 만족한다는 것이다. 이 sentence가 참인지 아닌지를 판단하기 위해서는 context가 필요하다. 즉 variable이 무엇을 나타내는지, 함수 $f$가 무언지를 알아야 한다. 만일 variable들이 실수이고, $f$가 $f(x)=x^2$라는 규칙으로 정의된다면 위 sentence는 false가 된다. $f(x) = -1$을 만족하는 $x$는 존재하지 않기 때문.


자, 이번엔 다음 sentence다.

\[\forall x \forall y (R(x,y)\rightarrow \exists z (z \neq x \wedge z \neq y \wedge (R(x,z) \wedge R(z,y))))\]

이 sentence를 해석하면 임의의 $x$, $y$에 대해 만약 $R(x,y)$가 성립한다면, $x$, $y$와는 다른 어떤 $z$가 존재해서, $R(x,z)$와 $R(z,y)$가 모두 성립한다는 의미이다.

다시 variable들이 실수라고 가정하고, relation $R(x,y)$가 $x<y$를 의미한다고 해 보자. 그러면 위 sentence는 참이 된다. 임의의 두 실수 사이에는 항상 다른 실수가 존재하기 때문. 그러므로 실수는 dense하다. 그러나 만약 variable들이 정수라면 위 sentence는 거짓이 된다.


정리해 보자면, 어떤 sentence가 참이냐 거짓이냐를 결정하는 것은 variable들이 어떤 set인지, fuction을 어떻게 해석할 것인지다.


Structure는 기저에 깔린 set과 다양한 function, constant, relation의 해석을 모두 포함하는 단어이다. First-order logic에서 structure의 역할은 propositional logic에서 assignment가 하는 역할과 같다고 보면 된다.

임의의 sentence $\varphi$와 임의의 structure $M$가 주어졌을 때, $M$이 $\varphi$를 model한다는 것은 직관적으로 봤을 때 $\varphi$가 $M$에 관하여 참이라는 의미이다. Propositional logic에서는 이를 $M \models \varphi$로 표기하였다. First-order logic에서는 어떨까?


Definition 1.3.1

Vocabulary는 function, relation, constant symbol들의 set이다.


Definition 1.3.2

$\mathcal{V}$가 vocabulary라고 하자. $\mathcal{V}$-structure는 $\mathcal{V}$의 interpretation에 따른 nonempty underlying set $U$로 이루어진다.

$\mathcal{V}$의 interpretation에는 다음이 할당된다.:

  • $U$의 각 element로부터 $\mathcal{V}$의 각 constant로,
  • $U^n$에서 $U$로의 function으로부터 $\mathcal{V}$ 내의 각 $n$-ary fucntion으로,
  • $U^n$의 subset으로부터 $\mathcal{V}$ 내의 각 $n$-ary relation으로.


$M$이 어떤 vocabulary $\mathcal{V}$의 $\mathcal{V}$-structure이면, $M$을 structure라고 한다.

이제 stucture를 underlying set(universe)과 해석되는 function, relation, constant symbol들로 나타낼 수 있다.


Example 1.3.3

Vocabulary $\mathcal{V}=\{f, R, c\}$를 생각하자. 이때 $f$는 unary function, $R$은 binary relation, $c$는 constant라고 하자.

그러면 $M = (\mathbb{Z}\vert f, R, c)$는 $\mathcal{V}$-structure를 나타낸다. $M$의 universe는 정수 집합 $\mathbb{Z}$이다.

$M$에 대한 묘사가 완전해지려면 $f$, $R$, $c$가 어떻게 해석되는지까지 알아야 한다. 예를 들어, $M$이 $f(x)$를 $x^2$로, $R(x,y)$를 $x<y$로, constant $c$를 $3$으로 해석한다면 structure $M$은 완전히 묘사가 끝난 것이다.


Example 1.3.4

Vocabulary $\{+, \cdot, 0, 1\}$의 structure $\mathbf{R}=(\mathbb{R}\vert +, \cdot, 0, 1)$을 생각하자. 여기서 $+$, $\cdot$은 binary function이고 $0$, $1$은 constant이다. $\mathbf{R}$의 universe는 실수 집합 $\mathbb{R}$이다.

이제 $+$, $\cdot$를 우리가 아는 평범한 “plus”, “times”로 해석하고, $0$, $1$을 우리가 아는 실수 $0$, $1$로 해석하기로 한다면, structure $\mathbf{R}$는 완전히 묘사되는 것이다.


Definition 1.3.5

$\mathcal{V}$를 vocabulary라고 하자. $\mathcal{V}$-formula는 모든 function, relation, constant가 $\mathcal{V}$ 안에 들어 있는 formula를 말한다. $\mathcal{V}$-sentence는 sentence인 $\mathcal{V}$-formula이다.


만약 $M$이 $\mathcal{V}$-structure라면 각 $\mathcal{V}$-sentence $\varphi$는 $M$에서 참이거나 거짓이다. 만약 $\varphi$가 $M$에서 참이면, 우리는 $M$이 $\varphi$를 model한다고 말하며 $M \models \varphi$로 쓴다.

아까 말했던 것처럼, structure의 역할은 propositional logic에서 assignment가 하는 역할과 같다. Propositional logic에서는 sentence에서 오로지 유한히 많은 assignment가 존재했다. First-order logic에서는 다르다. 주어진 sentence를 model하는 structure의 수에는 제한이 없다!

$M \models \varphi$의 개념을 조금 더 정밀하게 정의하자. 일단 예시 하나 더.


Example 1.3.6

다시 Example 1.3.4의 structure $\mathbf{R}=(\mathbb{R}\vert +, \cdot, 0, 1)$를 떠올리자. 이 structure에 대한 vocabulary $\{+, \cdot, 0, 1\}$를 $\mathcal{V}_{ar}$로 나타내자.1

$\mathcal{V}$-sentence $\forall x \exists y (1 + x \cdot x = y)$를 생각하자. 이 sentence는 임의의 $x$에 대해 어떤 $y$가 존재하여 그 값이 $x^2 + 1$과 같다는 뜻이다. 이 sentence는 $\mathbf{R}$에서 참이다. 임의의 실수를 가져다가 제곱하고 1을 더하면 그 결과는 다른 실수이기 때문.

따라서, $\mathbf{R} \models \forall x \exists y (1 + x \cdot x = y)$가 된다.


이번에는 $\mathcal{V}$-sentence $\forall y \exists x (1 + x \cdot x = y)$를 생각하자. 이 sentence는 임의의 $y$에 대해 어떤 $x$가 존재하여 $x^2 + 1 = y$를 만족한다는 뜻이다. 이 sentence는 $\mathbf{R}$에서 거짓이다. $y=-2$를 택하면 $x^2 + 1 = y$를 만족하는 $x$는 존재하지 않기 때문이다.

따라서, $\mathbf{R}$는 $\forall y \exists x (1 + x \cdot x = y)$를 model하지 않는다.


$M$이 $\mathcal{V}$-structure, $\varphi$이 $\mathcal{V}$-sentence라고 하자. 이제 $M$이 $\varphi$를 model한다는 것이 어떤 것인지 형식적으로 정의할 것이다. 먼저 $\varphi$가 $\vee$, $\rightarrow$, $\leftrightarrow$, $\forall$를 포함하지 않는 경우에 대해 정의하자. 우리는 $M \models \varphi$를 symbol $\wedge$, $\neg$, $\exists$가 등장하는 숫자에 대한 induction을 통해 증명하고자 한다. 물론 이런 symbol들이 등장하지 않을 때는, $\varphi$는 atomic이다.


  • $\varphi$가 atomic이면, definition에 의해 $\varphi$는 form $t_1=t_2$ 또는 $R(t_1, \cdots, t_m)$이다. 물론 여기서 $R$은 $n$-ary relation이며, $t_1, \cdots, t_m$은 term.

    $\varphi$가 sentence이므로 $\varphi$는 variable을 포함하지 않는다. 따라서 각 $t_i$는 $M$의 universe $U$에 속하는 어떤 element $a_i$로 해석된다. 이제,

    $M \models t_1 = t_2 \Leftrightarrow$ $a_1$과 $a_2$는 $U$의 같은 element.

    $M \models R(t_1, \cdots, t_m) \Leftrightarrow$ tuple $(a_1, \cdots, a_m)$은 $m$-ary relation $R$로 assign된 $U^m$의 subset.


이제 $\varphi$에 $\wedge$, $\neg$, $\exists$가 $m+1$번 등장한다고 가정하자. $M \models \varphi$가 많아야 $m$개의 $\wedge$, $\neg$, $\exists$를 갖는 임의의 sentence $\psi$에 대해 정의된다고 가정하자. First-order formula들은 atomic formula들로부터 rule $(R1)$, $(R2)$, $(R3)$을 적용하여 만들어지므로, $\varphi$에 대해 세 가지 가능성이 존재한다.


  • $\varphi$가 form $\neg \psi$이면, $M \models \varphi \Leftrightarrow$ $M$이 $\psi$를 modle하지 않음.

  • $\varphi$가 form $\psi \wedge \theta$이면, $M \models \varphi \Leftrightarrow$ $M \models \psi$이고 $M \models \theta$.

  • $\varphi$가 form $\exists x \psi$이면, $x$가 $\psi$의 free variable이 아닌 경우 $M \models \varphi \Leftrightarrow M \models \psi$이고…


Free variable이 아니면? 일단 $\psi(x)$를 $x$를 free variable로 갖는 formula라고 하자. 이 경우에 $M \models \varphi$를 정의하기 위해선 다음 개념이 필요하다.


Definition 1.3.7

$\mathcal{V}$가 vocabulary라고 하자. $\mathcal{V}$의 expansion은 $\mathcal{V}$를 subset으로써 포함하는 vocabulary이다.


Definition 1.3.8

$M$이 $\mathcal{V}$-structure라고 하자. Structure $M’$이 $M$과 같은 universe를 가지고 $\mathcal{V}$의 symbol들 역시 $M$과 똑같이 해석할 때, $M’$을 $M$의 expansion이라고 한다.


만약 $M’$이 $M$의 expansion이라면, 역으로 $M$을 $M’$의 reduct라고 한다.


만약 $M’$이 $M$의 expansion이라면, $M’$의 vocabulary는 필연적으로 $M$의 vocabulary의 extension이 된다.


Example 1.3.9

Structure $M’ = (\mathbb{R} \vert +, -, <, \cdot, 0, 1)$은 $M’ = (\mathbb{R} \vert +, \cdot, <, 0)$의 expansion이다.


Example 1.3.10

임의의 structure는 자명하게 자기 자신의 expansion.


이제 우리가 관심을 가져야 할 부분은 $M$의 universe $U_M$의 각 element마다 새로운 constant를 추가해서 만든 expansion이다.

$\mathcal{V}$-structure $M$에 대해, $\mathcal{V}(M)$을 vocabulary $\mathcal{V} \cup \{c_m \vert m \in U_M\}$이라고 쓰자. 여기서 $c_m$은 constant를 말한다.

이제 각 $c_m$을 element $m$으로 해석하는 $\mathcal{V}(M)$-structure로써의 $M$의 유일한 expansion을 $M_C$로 쓸 것이다. 이제 세 번째 가능성에 대한 내용이 정리된다.

  • $\varphi$가 form $\exists x \psi$이면, $M \models \varphi \Leftrightarrow M_C \models \psi(c)$ for some constant $c$ of $\mathcal{V}(M)$.


이제 $\vee$, $\rightarrow$, $\leftrightarrow$, $\forall$를 포함하지 않는 임의의 sentence $\varphi$에 대해 $M \models \varphi$가 정의되었다. 이 symbol들은 $\neg$, $\wedge$, $\exists$의 term으로써 나타낼 수 있으므로 이들에 대한 sentence들 역시 $M \models \varphi$를 자연스럽게 정의할 수 있다. 위 symbol이 등장할 때마다 단순히 $\neg$, $\wedge$, $\exists$를 사용한 식으로 대체해 주면 끝!


지금까지 $\mathcal{V}$-structure $M$이 $\mathcal{V}$-sentence $\varphi$를 model한다는 것의 의미를 정의했다. 이를 $\mathcal{V}(M)$-structure으로 확장한다면?


$\mathcal{V}(M)$ 정의를 다시 떠올려 보면, $\mathcal{V}(M)$ $\mathcal{V}$의 extension으로, $M$의 universe에 존재하는 각 element마다 새로운 constant를 추가해서 만들어진다. $\mathcal{V}(M)$-structure로의 $M$의 natural expansion $M_C$가 존재한다.

임의의 $\mathcal{V}(M)$-sentence $\varphi$에 대해, 우리는 $M \models \varphi$를 $M_C \models \varphi$를 의미하는 것으로 정의한다.

임의의 $\mathcal{V}$-structure $M$에 대해, $\mathcal{V}$에는 존재하지 않는 $\mathcal{V}(M)$의 constant를 우리는 parameter라고 한다.


Example 1.3.11

$\mathcal{V}_{<}$를 하나의 binary relation $<$을 갖는 vocabulary라고 하자.

$\mathbf{R}_<$를 $\mathbb{R}$을 underlying set으로 가지며 binary relation $<$을 일반적으로 해석하는 $\mathcal{V}_{<}$-structure라고 하자. 그러면 $\mathbf{R}_<$은 아래 sentence들을 model한다.

\[\forall x \exists y \exists z ((y < x) \land (x < z))\] \[\forall x \forall y ((x < y) \rightarrow \exists z ((x < z) \land (z < y)))\] \[(3 < 5) \land (-2 < 0)\] \[\lnot \exists x ((x < -2) \land (5 < x))\]


첫 두 sentence는 $\mathcal{V}_{<}$-sentence이다. 그러나 아래 두 $\mathcal{V}_{<}(\mathbf{R}_<)$-sentence들은 $\mathcal{V}_{<}$-sentence는 아니다. 여기에는 paremeter $-2$, $0$, $3$, $5$가 들어가 있다.


지금까지 sentence에 대한 “model”의 개념이었다. 그러면 formula는?

sentence는 free variable이 없는 formula였다. 우리는 아직까지 일반적인 formula에 대한 “model”의 개념을 정의하지 않았다.

관습적으로 우리는 structure $M$이 formula $\varphi(x_1, \cdots, x_n)$를 model한다는 것을 $M$이 sentence $\forall x_1 \cdots \forall x_n \varphi(x_1, \cdots, x_n)$를 model함을 의미하는 것으로 정의한다. 물론 $\varphi(x_1, \cdots, x_n)$는 $x_1, \cdots, x_n$의 값에 따라 참인지 거짓인지 갈릴 수 있다. 이 formula가 성립하는 $n$-tuple들의 집합을 $\varphi$에 의해 정의된 set이라고 말한다.


Definition 1.3.12

$\varphi(x_1, \cdots, x_n)$를 $\mathcal{V}$-formula라고 하자. $M$을 underlying set $U_M$을 갖는 $\mathcal{V}$-structure라고 하자.

$M \models \varphi (b_1, \cdots, b_n)$인 모든 $n$-tuple $(b_1, \cdots, b_n) \in (U_M)^n$의 set을 $\varphi (M)$라고 쓴다. 이 set $\varphi (M)$을 $M$의 $\mathcal{V}$-definable subset이라고 한다.


일반적으로 structure의 universe의 subset 대부분은 definable하지 않다. 이 내용은 Sec. 1.5로.

Definable subset의 진가는 Model theory에서 드러난다. $\mathcal{V}$-definable subset들은 vocabulary $\mathcal{V}$가 서술할 수 있는 subset이라고 볼 수 있다.


Example 1.3.13

Example 1.3.11의 $\mathcal{V}_{<}$와 $\mathbf{R}_<$를 다시 가져오자. 다음 $\mathcal{V}_{<}(\mathbf{R}_<)$-formula들을 생각하자.

\[(x < y) \lor (x > y) \lor (x = y)\] \[(\lnot (x < 3) \land \lnot (x = 3) \land (5 < x)) \lor (x = 5) \lor (x < -2)\]

첫 번째 formula를 $\varphi(x,y)$로, 두 번째 formula를 $\psi(x)$로 쓰기로 하자. 그러면 $\mathbf{R}_< \models \varphi(x,y)$이다. $\mathbf{R}_<$이 sentence $\forall x \forall y \varphi(x,y)$를 model하기 때문이다. $\varphi(x,y)$로부터 정의된 set이 $\mathbb{R}^2$ 전체라는 것으로부터 나온다.

반면 formula $\psi(x)$는 $\mathbb{R}$의 임의의 $x$에 대해 성립하지 않는다. 따라서 $\mathbf{R}_<$가 $\psi(x)$를 model하지 못한다.

$\psi(x)$에 의해 정의된 set $\psi(\mathbf{R}_<)$는 $(- \inf, -2) \cup (3, 5]$이다. $\mathbf{R}_<$는 formula $\neg \psi(x)$ 역시 model하지 못하는데, $\neg \psi(\mathbf{R}_<)$는 $[2, 3] \cup (5, \inf)$이며, 이는 $\mathbb{R}$에서 $\psi(\mathbf{R}_<)$의 complement이기 때문이다.


$M$이 $\varphi$를 model한다면, 반대로 $\varphi$가 $M$에서 성립(hold)한다고 말한다.

하나의 sentence는 어떤 structure에서는 참일 수 있고, 다른 어떤 structure에서는 거짓일 수 있다. $\mathcal{V}$-sentence $\varphi$가 모든 $\mathcal{V}$-structure에서 참이라면 $\varphi$가 valid 또는 tautology라고 한다. $\varphi$가 어떤 $\mathcal{V}$-structure에서 참이라면 $\varphi$가 satisfiable이라고 한다. 반면 어떤 structure에서도 $\varphi$가 참이 아니라면, $\varphi$는 unsatisfiable 또는 contradiction이라고 한다.


이와 관련된 내용은 propositional logic과 똑같은 용어로 진행된다.

$\mathcal{V}$-sentence $\theta$와 $\varphi$에 대해, $\theta$가 $\varphi$의 consequence(귀결)이라는 것은 모든 $\mathcal{V}$-structure $M$에 대해, $M \models \varphi \Rightarrow M \models \theta$라는 의미.

$\mathcal{V}$-sentence $\theta$와 $\varphi$에 대해, $\theta$가 $\varphi$와 equivalent(동치)라는 것은 $\theta$와 $\varphi$가 서로 consequence라는 의미.


다음 notation도 마찬가지.


Notation 1.3.14

$\models \varphi$는 $\varphi$가 tautology라는 의미이다.

$\varphi \models \psi$는 $\psi$가 $\varphi$의 consequence라는 의미이다.

$\varphi \equiv \psi$는 $\varphi$와 $\psi$가 equivalent라는 의미이다.


Satisfiability의 개념을 sentence에서 formula로 확장해 보자.

Formula $\varphi(x_1, \cdots, x_n)$가 satisfiable $\Leftrightarrow$ sentence $\forall x_1 \cdots \forall x_n \varphi(x_1, \cdots, x_n)$가 satisfiable.

이에 따라 unsatisfiability, tautology, consequence의 개념도 formula에 대해 확장할 수 있다.

Propositional logic에서처럼, 우리의 목적은 다음 decision problem을 해결하는 것이다.

  • Validity problem : 주어진 formula $\varphi$에 대해, $\varphi$는 valid한가?

  • Satisfiability의 problem : 주어진 formula $\varphi$에 대해, $\varphi$는 satisfiable한가?

  • Consequence problem : 주어진 formula $\varphi$, $\psi$에 대해, $\psi$는 $\varphi$의 consequence인가?

  • Equivalence problem : 주어진 formula $\varphi$, $\psi$에 대해, $\varphi$와 $\psi$는 equivalent한가?


어떻게 보면 위 문제들은 다 하나의 문제로 귀결된다. Satisfiability problem만 해결할 수 있으면 나머지는 문제가 없다. Validity problem은 $\neg \varphi$가 unsatisfiable인지, consequence problem은 $\varphi \wedge \neg \psi$가 unsatisfiable인지, equivalence problem은 서로가 consequence인지 확인할 수만 있으면 해결된다.


주어진 formula가 satisfiable한지는 syntax에 달려 있다. 예를 들어 formula $(y+1) < y$를 생각하자. 만약 우리가 vocabulary $\{+, <, 1\}$을 일반적으로 해석한다면 이 formula는 satisfiable하지 않다. 그러나 다른 해석에서는 이는 satisfiable할 수 있다. 만일 $<$를 not equal로 해석하기로 한다면?

같은 이유로, $2+2=4$라는 formula 역시 tautology라고 할 수 없다.


이게 문제다. Propositional logic에서는 satisfiability problem을 해결하기 위해서는 truth table만 확인하면 됐다. First-order logic에서는 모든 structure에 대해서 이를 다 확인해야 한다. 이건 불가능하다. First-order formula가 unsatisfiable인지 증명할 방법은 지금은 없다!

그렇지만 어떤 formula가 satisfiable인지 보이는 건 간단하다. 그게 참이 되는 structure 하나만 찾으면 되니까.


Example 1.3.15

$\varphi$를 sentence $\forall x \exists y R(x,y) \wedge \exists y \forall x \neg R(x,y)$라고 하자. $\varphi$가 satisfiable인지 보이기 위해서는 $\varphi$를 model하는 structure $M$을 찾아야 한다.

$M=(\mathbb{N} \vert R)$로 두자. 여기서 $\mathbb{N}$은 자연수, binary relation $R$은 successor relation으로 두자. 즉 $R(x, y)$이 성립하는 것과 $y = x+1$은 동치이다.

위 해석 아래애서, $\varphi$는 모든 element가 successor를 가지며, 어떤 element는 predecessor를 가지지 않는다는 의미이다. 이는 $M$에서 참인데, 모든 자연수는 successor를 가지나, $0$은 predecessor를 갖지 않기 때문이다.

따라서, $M \models \varphi$이며 $\varphi$는 satisfiable이다.


$\varphi$가 tautology가 아님을 보이는 것도 간단한데, $\neg \varphi$를 model하는 structure를 하나만 찾으면 된다. 예를 들자면 $N=(\mathbb{Z} \vert R)$가 있겠다.


Example 1.3.16

$\mathcal{V}_E$를 하나의 binary relation $\{E\}$를 갖는 vocabulary라고 하자. $M$을 $\mathcal{V}_E$-structure라고 하자. relation $E$가 $M$ 위의 equivalence relation이라는 것과 $M$이 다음 세 sentence를 model한다는 것은 동치이다.:

\[\forall x E(x, x)\] \[\forall x \forall y (E(x, y) \leftarrow E(y, x))\] \[\forall x \forall y \forall z (E(x, y) \wedge E(y, z) \leftarrow E(x, z))\]


첫 번째 sentence $\varphi_1$은 $E$가 reflexive라는 의미이다. 두 번째 sentence $\varphi_2$은 $E$가 symmetric, 세 번째 sentence $\varphi_3$은 $E$가 transitive라는 의미이다.


실제로 propositional logic의 모든 formula들의 set $U$를 underlying set으로 갖는 $\mathcal{V}_E$-structure $(U \vert E)$가 각 $\varphi_i$를 model함을 보일 수 있다. 물론 $E$를 일반적인 equivalence relation $\equiv$로 해석했을 때.


위 세 sentence가 redundant하지 않음을 보일 수 있다. 다시 말해 위 세 sentence만 있으면 우리는 equivalence relation의 개념을 정의할 수 있다.

이를 보이기 위해서는 어떤 sentence가 다른 두 sentence들의 consequence가 아님을 보이면 된다. $\varphi_1$가 $\varphi_2$, $\varphi_3$의 sentence가 아님을 보이려면 $\varphi_2 \wedge \varphi_3 \wedge \neg \varphi_1$를 model하는 structure를 찾으면 된다. 이는 곧 $E$가 symmetric이고 transitive이나 reflexive가 아닌 해석을 갖는 $\mathcal{V}_E$-structure $(\mathbb{R} \vert E)$를 찾으면 된다는 말이다. $E$를 일반적인 $\neq$로 둔다면 OK. 나머지도 적당히 찾아볼 수 있겠다.


이와 같은 방법으로 어떤 formula가 satisfiable인지 보여줄 수 있다. 같은 방법으로 우리는 어떤 formula가 tautology가 아니라든가, 한 formula가 다른 formula의 consequence가 아니라든가, 두 formula가 서로 equivalence가 아님을 보일 수 있다.

그러나, 아직 우리는 어떤 formula가 unsatisfiable인지, 어떤 formula가 tautology인지, 한 formula가 다른 formula의 consequence인지, 두 formula가 서로 equivalent한지 보일 방법이 없다. 여기에는 formal proof와 resolution이 필요하며, Chapter 2에서 알아보도록 하자.


  1. vocabulary of arithmetic이라는 뜻. ↩

You may also enjoy