一阶逻辑

前置

• 命题逻辑演算

定义

一阶语言的量词只作用到变量上。
二阶语言的量词可作用到变量和谓词上。

• Symbols of first-order language $\mathcal{L}$(一阶语言的符号集):

  • Variables: $x_1,x_2,\cdots$
  • Individual constants: $a_1,a_2,\cdots$
  • Predicate letters: $A_1^1,A_2^1,\cdots ,A_1^2,A_2^2,\cdots$
  • Function letters: $f_1^1,f_2^1,\cdots ,f_1^2,f_2^2,\cdots$
  • Punctuation: $(,),,$
  • Connectives: $\neg$, $\to$
  • Quantifier: $\forall$

• Term in $\mathcal{L}$:

  1. Variables and individual constants are terms.
  2. If $f^n$ is an $n$-ary function letter in $\mathcal{L}$ and $t_1,\dots ,t_n$ are terms in $\mathcal{L}$, then $f^n(t_1,\dots ,t_n)$ is a term in $\mathcal{L}$.
  3. The set of all terms is generated as in (1) and (2).

• Atomic formula(原子公式):

  • If $A^k$ is a $k$-ary predicate letter in $\mathcal{L}$ and $t_1,\dots ,t_k$ are terms in $\mathcal{L}$, then $A^k(t_1,\dots ,t_k)$ is an atomic formula in $\mathcal{L}$.

• Well-formed formula(wfs)(良形公式):

  1. Each atomic formula is a wfs.
  2. If $\mathcal{A}$ and $\mathcal{B}$ are wfs in $\mathcal{L}$, then $(\neg \mathcal{A})$, $(\mathcal{A}\to \mathcal{B})$, $(\forall x_i)\mathcal{A}$ are wfs in $\mathcal{L}$, where $x_i$ is an arbitrary variable.
  3. All wfs are generated as in (1) and (2).

• In the wf. $(\forall x_i)\mathcal{A}$, we say that $\mathcal{A}$ is the scope of the quantifier. More generally, when $(\forall x_i)\mathcal{A}$ occurs as a subformula of a wf. $\mathcal{B}$, we say that the scope of this quantifier in $\mathcal{B}$ is $\mathcal{A}$.

• An occurrence of the variable $x_i$ in a wf. is said to be bound if it occurs within the scope of a $(\forall x_i)$ in the wf., or if it is the $x_i$ in a $(\forall x_i)$.

• If an occurrence of a variable is not bound it is said to be free.

• An interpretation $I$ of $\mathcal{L}$ is a non-empty set $D_I$ (the domain of $I$) together with

  • a collection of distinguished elements $({\bar{a}}_1,{\bar{a}}_2,\dots )$,
  • a collection of functions on $D_I$ $({\bar{f}}_i^n,i>0,n>0)$,
  • a collection of relations on $D_I$ $({\bar{A}}_i^n,i>0,n>0)$.

• A valuation in $I$ is a function $v:\{\text{terms of }\mathcal{L}\}\to D_I$
  with the properties:

  1. $v(a_i)={\bar{a}}_i$ for each individual constant $a_i$ of $\mathcal{L}$.
  2. $v(f^n(t_1,\dots ,t_n))={\bar{f}}^n(v(t_1),\dots ,v(t_n))$, where $f^n$ is any function letter in $\mathcal{L}$ and $t_1,\dots ,t_n$ are any terms of $\mathcal{L}$.

Interpretation只提供变量的变化范围，常量的取值，然后给出函数和关系的具体含义。
即Interpretation把一个合式公式限制成一阶的，只剩下变量可以在$D_{I}$中变化。
Valuation只给term赋值。即给变量赋值。

• Two valuations $v$ and $v^{\prime }$ are i-equivalent (i-等价, 记作$v\stackrel{i}{\sim }{v}^{\prime }$) if $v(x_j)=v^{\prime }(x_j)$ for every $j\ne i$.

• Let $\mathcal{A}$ be a wf. of $\mathcal{L}$ and let $I$ be an interpretation of $\mathcal{L}$. A valuation $v$ in $I$ is said to satisfy $\mathcal{A}$, if it can be shown inductively under the following four conditions:

  1. Atomic case
     $v$ satisfies $A^k(t_1,\dots ,t_k)$ iff the relation

     $${\bar{A}}^k(v(t_1),\dots ,v(t_k))$$

     holds (is true) in $D_{\mathcal{I}}$.

  2. Negation
     $v$ satisfies $(\neg \mathcal{A})$ iff $v$ does not satisfy $\mathcal{A}$.

  3. Implication
     $v$ satisfies $(\mathcal{A}\to \mathcal{B})$ iff either

     • $v$ satisfies $(\neg \mathcal{A})$, or
     • $v$ satisfies $\mathcal{B}$.

  4. Universal quantification
     $v$ satisfies $(\forall x_i)\mathcal{A}$ iff every valuation $v^{\prime }$ that is $i$-equivalent to $v$ satisfies $\mathcal{A}$.
     (Two valuations are $i$-equivalent when they agree on all variables except possibly $x_i$.)

• A wf. $\mathcal{A}$ is true in an interpretation $I$ if every valuation in $I$ satisfies $\mathcal{A}$.

• A wf. $\mathcal{A}$ is false in an interpretation $I$ if there is no valuation in $I$ which satisfies $\mathcal{A}$.

• We write $I\models \mathcal{A}$ if $\mathcal{A}$ is true in $I$. This is read as ”$I$ satisfies $\mathcal{A}$“.

• Thus if we take a wf. ${\mathcal{A}}_0$ of ${\mathcal{L}}_0$ and replace each statement letter occurring by a wf. of $\mathcal{L}$ (replacing the same letter by the same wf. throughout), we shall obtain a wf. $\mathcal{B}$ of $\mathcal{L}$. $\mathcal{B}$ is called a substitution instance in $\mathcal{L}$ of ${\mathcal{A}}_0$.

• A wf. $\mathcal{A}$ of $\mathcal{L}$ is a tautology if it is a substitution instance in $\mathcal{L}$ of a tautology in ${\mathcal{L}}_0$.

• A wf. $\mathcal{A}$ of $\mathcal{L}$ is said to be closed if no variable occurs free in $\mathcal{A}$.

• A wf. $\mathcal{A}$ of $\mathcal{L}$ is logically valid if $\mathcal{A}$ is true in every interpretation of $\mathcal{L}$.

• A wf. $\mathcal{A}$ of $\mathcal{L}$ is contradictory if $\mathcal{A}$ is false in every interpretation of $\mathcal{L}$.

性质

1. Substitution Lemma (Valuation Version) Let $\mathcal{A}(x_i)$ be a well-formed formula in which the variable $x_i$ occurs free, $t$ be a term free for $x_i$ in $\mathcal{A}(x_i)$, $v$ be any valuation in the given interpretation $I$, $v^{\prime }$ be the valuation that is $i$-equivalent to $v$ and satisfies$v^{\prime }(x_i)=v(t).$
   Then $v$ satisfies $\mathcal{A}(t)$ iff $v^{\prime }$ satisfies $\mathcal{A}(x_i).$
2. If, in a particular interpretation $I$, the wfs. $\mathcal{A}$ and $\mathcal{A}\to \mathcal{B}$ is true, then $\mathcal{B}$ is true in $I$.
3. Let $\mathcal{A}$ be a wf. of $\mathcal{L}$, and let $I$ be an interpretation of $\mathcal{L}$. Then $I\models \mathcal{A}$ if and only if $I\models (\forall x_i)\mathcal{A}$, where $x_i$ is any variable.
4. Let $y_1,y_2,\cdots ,y_n$, be variables in $\mathcal{L}$, let $\mathcal{A}$ be a wfs. of $\mathcal{L}$, and let $I$ be aninterpretation. Then $I\models A$ if and only if $I\models \forall y_1\forall y_2\cdots \forall y_n\mathcal{A}$ .
5. In an interpretation $I$, a valuation $v$ satisfies the formula $\exists x_i\mathcal{A}$ if and only if there is at least one valuation $v^{\prime }$ which is i-equivalent to $v$ and which satisfies $\mathcal{A}$ .
6. A wf. $\mathcal{A}$ of $\mathcal{L}$ which is a tautology is true in any interpretation of $\mathcal{L}$
7. Let $I$ be an interpretation of $\mathcal{L}$ and let $\mathcal{A}$ be a wfs. of $\mathcal{L}$. If $v$ and $w$ are valuations such that $v(x_i)=w(x_i)$ for every free variable $x_i$ of $\mathcal{A}$, then $v$ satisfies $\mathcal{A}$ if and only if $w$ satisfies $\mathcal{A}$.
8. If $\mathcal{A}$ is a closed wf. of $\mathcal{L}$ and $I$ is an interpretation of $\mathcal{L}$, then either $I\models \mathcal{A}$ or $I\models (\neg \mathcal{A})$.