1.1 The Language of First-order Logic
First-order logic(일차논리)는 propositional logic의 symbol들 $\wedge$, $\vee$, $\neg$, $\rightarrow$, $\leftrightarrow$(거기에 괄호까지)에 더해 다음 두 기호가 추가된다.
그리고 수많은 symbol들이 있다. 이 symbol들은 다음 다섯 가지 부류로 나눌 수 있다.
-
Variables : 알파벳 뒷부분을 소문자로($\dots x, y, z$) 써서 variable(변항)을 나타낸다. Variable은 set의 임의의 element를 나타낸다. 사실은 first-order가 바로 그런 뜻이다. 예를 들어, second-order는 element들의 set을 나타내는 표현이다.
-
Constants : 알파벳 앞부분을 소문자로($a, b, c, \dots$) 써서 constant(상항)을 나타낸다. Constant는 set의 특정 element를 나타낸다.
-
Functions : 소문자 $f$, $g$, $h$를 function을 나타낼 때 사용한다. 괄호로 리스트된 형태의 function symbol $f(x_1, x_2, \dots, x_n)$로 쓰이기도 한다. First-order logic의 function들은 몇 개의 variable들을 symbol로써 포함한다. Function $f$가 variable을 1개, 2개, 3개 가질 때 각각 unary, binary, ternary라고 한다. 일반적으로 $n$-개의 variable을 가지면 $n$-ary라고 하며 이떄 $n$을 해당 function의 arity라고 한다.
-
Relations : 대문자 $P$, $Q$, $R$, $S$를 relation을 나타낼 때 쓴다. Function과 마찬가지로, 각 relation들은 관련된 arity를 가진다.
-
Fixed Symbols : Fixed symbol이란 $\wedge$, $\vee$, $\neg$, $\rightarrow$, $\leftrightarrow$, $($, $)$, $\exists$, $\forall$을 말한다. Fixed symbol이란 언제나 같은 의미로 사용된다는 의미이다.
Fixed symbol $\exists$, $\forall$을 quantifier(양화사)라고 한다. 각각 existential, universal quantifier라고 하며 이들의 뒤에는 variable이 뒤따른다.
Example 1.1.1
First-order logic의 sentence의 예시로 다음을 보자.
\[\forall y \exists x R(f(x), y)\]위 sentence는 [모든 $y$에 대해 $x$가 존재하여 relation $R$이 ordered pair $(f(x), y)$를 만족한다.]라는 의미이다.\
여기서 알 수 있는 것은 $f$가 unary function이고, $R$이 binary relation이라는 것이다. 이 문장이 참인지 아닌지는 문맥에 따라 달려 있다.
당연하다는 듯이, 우리는 fixed symbol의 목록에 $=$를 ‘equality’의 의미로 추가한다. 등호의 존재는 quantifier가 실제로 quantify를 행하도록 만든다.
예를 들어 다음 문장
\[\exists x_1 \exists x_2 \exists x_3(\neg (x_1=x_2) \wedge \neg (x_1=x_3) \wedge \neg (x_2=x_3))\]은 서로 다른 적어도 세 element들이 존재함을 말해 준다. 비슷하게 우리는 100만 개의 서로 다른 element들이 존재한다는 문장을 만들 수 있다.
자, 다음은 syntax와 semantics다.