逻辑语义 (Basic Semantics)

逻辑有效、逻辑等价、逻辑后承

定义

定义：逻辑有效、逻辑等价、逻辑后承

对于任意的公式 $\varphi$ 和 $\psi$ ，还有任意的公式集 $\Gamma$ ，

如果对于任意的 $\mathfrak{A}$ 和 $\alpha$ ，都有 $\underset{\mathfrak{A}}{|\!\!\!=}\ \varphi[\alpha]$ ，则称 $\varphi$ 为逻辑有效 (logically valid) 的，符号上记为 $\models \varphi$ .
如果对于任意的 $\mathfrak{A}$ 和 $\alpha$ ，都有 $\underset{\mathfrak{A}}{|\!\!\!=}\ \varphi[\alpha] \iff \underset{\mathfrak{A}}{|\!\!\!=}\ \psi[\alpha]$ ，那么此时称 $\psi$ 和 $\varphi$ 逻辑等价 (logically equivalent)，记为 $\varphi \models\hspace{-5pt}|~ \psi$ .
如果对于任意的 $\mathfrak{A}$ 和 $\alpha$ ，都有 $\underset{\mathfrak{A}}{|\!\!\!=}\ \varphi[\alpha] \Rightarrow \underset{\mathfrak{A}}{|\!\!\!=}\ \psi[\alpha]$ ，那么此时称 $\psi$ 和 $\varphi$ 逻辑后承 (logical consequence)，记为 $\varphi \models \psi$ .
给定语句 $\psi$ ，如果语句集 $\Gamma$ 当中的任意语句 $\varphi$ ，都有 $\psi$ 为 $\varphi$ 的逻辑后承，则称 $\psi$ 为 $\Gamma$ 的逻辑后承.
$\Gamma$ 相容当且仅当存在 $\mathfrak{A}$ 和 $\alpha$ ，对于任意的 $\varphi\in \Gamma$ 有 $\underset{\mathfrak{A}}{|\!\!\!=}\ \varphi[\alpha]$.

以下是简单推论：

$\varphi \models\hspace{-5pt}|~ \psi \iff \models \varphi\leftrightarrow \psi$ ；
$\varphi\models \psi\iff \models \varphi\to \psi$ ；
$\models \psi \iff \varnothing \models \psi$ ；
如果 $\Gamma \subseteq \Delta$ 且 $\Gamma \models \psi$ ，那么 $\Delta \models \psi$ ；
对于以下任意的 $\varphi_0,\varphi_1,\cdots,\varphi_{n-1}$ 且 $i<n$ ，以下等价：
$\Gamma\cup \left\lbrace \varphi_1,\cdots,\varphi_n \right\rbrace \models \psi$ ；
$\Gamma\cup \left\lbrace \bigwedge\limits_{k=0}^n \varphi_k \right\rbrace \models \psi$ ；
$\Gamma \cup \left\lbrace \varphi_0,\cdots,\varphi_{i-1} \right\rbrace \models \bigwedge\limits_{k=i}^n \varphi_k \to \psi$ .

相容的部分和命题逻辑的推论类似：

$\Gamma\models \psi\iff \Gamma\cup \left\lbrace \neg \psi \right\rbrace$ 是不相容的；
如果 $\Gamma$ 相容，则 $\Gamma\cup \left\lbrace \psi \right\rbrace$ 和 $\Gamma\cup \left\lbrace \neg \psi \right\rbrace$ 至少有一个是相容的.

重言式

本章我们不再使用“永真式”这样的说法，因为这样的说法具有一定的误导性，转而采用重言式来指代 tautlogy .

引入 $L$-真值指派：函数 $V:\mathrm{Fm}_L\to \left\lbrace \mathrm{T},\mathrm{F} \right\rbrace$ 将一个公式给定一个真值.

此时对于重言式，和命题逻辑类似，有如下定义：

定义：重言式、语义等价、语义后承

重言式：$\mid\!\equiv \varphi$ 当且仅当每个 $L$-真值指派 $V$ 都有 $V(\varphi) = \mathrm{T}$ .
语义等价：$\varphi\mid\!\equiv\!\mid \psi$ 当且仅当 $V(\varphi) = V(\psi)$ .
语义后承：$\varphi\mid\!\equiv \psi$ 当且仅当 $V(\varphi)=\mathrm{T}$ 可以推出 $V(\psi)=\mathrm{T}$ .

这个地方有个非常容易陷入的误区，这也是为什么我们现在不把 tautlogy 称为永真式.

对于如下的公式：

\[ x=x \]

它是否是重言式？事实上它并不是，如果我们还用“永真式”这个翻译的话，就会出现非常令人迷惑的情况.

我们需要厘清这里面的逻辑链条：

首先，重言式这个概念继承自命题逻辑，它表示不管其中的语句符号 $\varphi$ 取值为什么都取值为真，例如 $\varphi\leftrightarrow \varphi$ 中尽管 $\varphi$ 是不确定的，但它是永真的.
随后，$L$-语言当中的语句符号在一阶语言当中到底代表哪个部分？事实上，一个语句符号表示的是原子公式，这是由于我们在命题逻辑当中只引入了二元逻辑连接词和 $\neg$ .
最后，我们就能解答刚才的问题了，因为 $x=x$ 为原子公式，利用 $L$-语言表达为 $\varphi$ ，单个语句符号自然不会是重言式. （即使我们知道，$x=x$ 是不可能为假的）

所以，综上 $V(x=x)=\mathrm{F}$ 是可以指定的.

教材上的命题 2.2.4 表明的是：语义（重言、等价、后承）可以推导出逻辑（有效、等价、后承）.

等词公理

等词公理的内容

等词公理

对于任意的项 $t,u,\cdots$ 和 $f\in \mathrm{Fs}_L$ ，$p\in \mathrm{Rs}_L$ ，

$\models t=t$ ；（自反）
$\models t=u \to u=t$ ；（交换）
$\models t=u \land u=v \to t=v$ ；（传递）
$\models (t_0=u_0)\land \cdots \land (t_{\nu_L(f)-1} = u_{\nu_L(f)-1})\to$ $ft_0\cdots t_{\nu_L(f)-1} = fu_0\cdots u_{\nu_L(f)-1}$ ；
$\models (t_0=u_0)\land \cdots \land (t_{\nu_L(p)-1} = u_{\nu_L(p)-1})\to$ $[pt_0\cdots t_{\nu_L(f)-1} \leftrightarrow pu_0\cdots u_{\nu_L(f)-1}]$ ；

这些都是从 $=$ 代表 $A$ 中的等值直接可以推出来的.

常见的逻辑有效和逻辑后承式

命题逻辑部分我们就曾讨论过这方面的内容，事实上，逻辑语句和命题逻辑的部分也比较类似，可以相互转化，例如：

\[ \forall x (\varphi\land \psi) \models\!\!\!| \forall x \varphi \land \forall x \psi \]

这个实际上和命题逻辑里面的

\[ \mid\!\equiv \theta \land \chi \iff \mid\!\equiv \theta \text{ and } \mid\!\equiv \chi \]

是一致的，这个地方的 translation 实际上是从重言式的定义当中来的：

\[ \begin{aligned} &\text{for all } V [V (\theta) = \mathrm{T}\text{ and } V(\chi) = \mathrm{T}] \\ &\iff\text{for all } V[V(\theta)=\mathrm{T}] \text{ and for all } V[V(\chi)=\mathrm{T}]. \end{aligned} \]

那么有如下的一些性质：

量词否定律 (quantifier negation laws)
$\neg \exists x \varphi \models \!\!\!| \forall x \neg \varphi$ .
分配律
$\forall$ 和 $\land$ 、$\exists$ 和 $\lor$ 是满足分配律的，例如：$\forall x (\varphi \land \psi)\models \forall x \varphi \land \forall x \psi$ .
$\forall$ 和 $\lor$ 、$\exists$ 和 $\land$ 满足部分分配律：$\forall x \varphi \lor \forall x \psi \models \forall x(\varphi\lor \psi)$ .
全域非空
$\varphi\models \exists x \varphi$ .
同种量词可换
$\forall x \forall y \varphi \models\!\!\! | \forall y\forall x \varphi$ .

自由变量、受囿变量

在有了公式之后，我们其实就会去思考一个问题：一个公式的取值是否和所有的变量都有关系？例如对于以下的公式：

\[ \exists x(x\dot{+}y=z) \]

在这个公式里面，它是否成立和 $x$ 的取值没有什么关系，它属于一种占位符，就好像定积分

\[ \int_0^2 f(x)\mathrm{d}x \]

当中的 $x$ 一样. 这种理解带来的效果就是它可以换元，就好像 $\displaystyle\int_0^1 f(x)\mathrm{d}x = \int_0^1 f(u)\mathrm{d}u$ 一样，我们换元也能得到：

\[ \exists x(x\dot{+}y=z) = \exists u(u\dot{+}y=z) \]

但是我们实际上还是要比较严谨地说明这件事情，这就引出了自由变量这个概念.

定义：自由变量

对于任意的公式 $\varphi$ ，它的自由变量集合 $\mathrm{Fv}(\varphi)$ 由如下递归定义生成：

如果 $\varphi$ 是原子公式，$\mathrm{Fv}(\varphi) = \left\lbrace x:x \text{ 在 } \varphi \text{ 中出现} \right\rbrace$.
$\mathrm{Fv}(\varphi)=\mathrm{Fv}(\neg \varphi)$ ；
$\mathrm{Fv}(\varphi\lor \psi) = \mathrm{Fv}(\varphi)\cup \mathrm{Fv}(\psi)$ ；
$\mathrm{Fv}(\exists x \varphi)=\mathrm{Fv}(\varphi)\sim \left\lbrace x \right\rbrace$.

当 $x\in \mathrm{Fv}(\varphi)$ 时，称 $x$ 为 $\varphi$ 的自由变量，也称 $x$ 在 $\varphi$ 中自由出现 (occurs free). 自由变量之外的变量统称为受囿变量 (Bounded variables) ，记为 $\mathrm{Bv}(\varphi)$ .

例题

设
$$ \varphi = (\exists x(x=y+z))\lor (\exists y (y=u+x)) $$
试求 $\mathrm{Fv}(\varphi)$ .

这里面出现的变量只有 $x,y,z,u$ ，可以用定义证明

\[ \mathrm{Fv}(\varphi) = \left\lbrace x,y,z,u \right\rbrace \]

$\square$

$L$-语句

定义：$L$-语句

一个 $L$ 公式 $\varphi$ 是一个 $L$ 语句当且仅当 $\mathrm{Fv}(\varphi) = \varnothing$ .

这里可以再次讨论一下 $x=x$ 的问题，它是原子公式，$x$ 为自由变量，它自然就不是语句. 但是 $\exists x(x=x)$ 它就是一个 $L$ 语句.

命题

对于任意的 $L$-结构 $\mathfrak{A}$ 和任意的 $\mathfrak{A}$-指派 $\alpha$ 和 $\beta$ .

对于任意的项 $t$ ，如果对于所有在 $t$ 中的变元 $x$ ，都有 $\alpha(x)=\beta(x)$ ，那么 $$ t^\mathfrak{A} [\alpha] = t^\mathfrak{A}[\beta] $$
对于任意的公式 $\varphi$ ，对 $\varphi$ 中所有的自由变量 $x\in \mathrm{Fv}(\varphi)$ ，如果 $\alpha(x) = \beta(x)$ ，那么 $$ \underset{\mathfrak{A}}{|\!\!\!=} \varphi[\alpha]\iff \underset{\mathfrak{A}}{|\!\!\!=} \varphi[\beta] $$

利用项的归纳和公式的归纳即可证明. $\square$

$\underset{\mathfrak{A}}{\models}\ \varphi$ 的基本性质

不依赖 $\mathfrak{A}$ 指派

命题：语句的真值不依赖变量指派

对于任意的语句 $\varphi$ 和任意的结构 $\mathfrak{A}$ 以及 $\mathfrak{A}$ 指派 $\alpha,\beta$ ，有
$$ \underset{\mathfrak{A}}{|\!\!\!=}\ \varphi[\alpha]\iff \underset{\mathfrak{A}}{|\!\!\!=}\ \varphi[\beta] $$
因此，只要对于一些 $\alpha$ 满足 $\underset{\mathfrak{A}}{|\!\!\!=}\ \varphi[\alpha]$ ，对于全部的指派均满足 $\underset{\mathfrak{A}}{|\!\!\!=}\ \varphi[\alpha]$.

$L$ 语句的真假

定义：$L$ 语句的真假

对于任意的公式 $\varphi$ ，如果 $\mathrm{Fv}(\varphi)\subseteq \left\lbrace x_0,\cdots,x_{k-1} \right\rbrace$ ，那么我们可以写
$$ \underset{\mathfrak{A}}{|\!\!\!=} \varphi_{x_0,\cdots,x_{k-1}}[a_0,\cdots,a_{k-1}] $$
或者简单的 $\underset{\mathfrak{A}}{|\!\!\!=}\ \varphi[a_0,\cdots,a_{k-1}]$ 来表示一些（当然，也就是任意）满足 $i<k$ ，$\alpha(x_i)=a_i$ 的指派 $\alpha$ 有 $\underset{\mathfrak{A}}{|\!\!\!=}\ \varphi[\alpha]$ .特别的，如果 $\varphi$ 还是个语句，可以直接写 $\underset{\mathfrak{A}}{|\!\!\!=}\ \varphi$ 来表明 $\varphi$ 在 $\mathfrak{A}$ 中为真，如果 $\underset{\mathfrak{A}}{|\!\!\!\neq}\varphi$ ，则 $\varphi$ 为假.

之后的命题 2.2.11 是命题逻辑连接词的延续，不必多言.

为什么需要是一个语句才能证明是否为真？在确定了 $\mathfrak{A}$ 后，只有语句才能明确是是否为真，例如在 $(\mathbb{R},<,+,1)$ 当中，对于下面的三个语句：

$\exists x(x=x)$ ；
$\exists x(x=1)$ ；
$\exists x(x=y)$ .

无论是直觉还是理论上，前两个都能判断为真，而第三个是无法判断的，它存在自由变量 $y$ ，没有明确 $y$ 的情况下，就不可能说明它的真假性.

真假公式的例子

下面的例子都比较重要，建议都记忆.

(1) 逻辑有效的语句在所有结构当中都为真，反之，逻辑错误 (logically false) 的语句在所有结构中都为假.

(2) 对于 $n \geqslant 2$ ，用如下的句子来定义 $\exists^{\geqslant n}$ ：

\[ \exists x_0 \cdots \exists x_{n-1} [\neg (x_0 = x_1)\land \neg (x_0=x_2) \land \cdots \land \neg (x_{n-2}=x_{n-1})] \]

也就是存在 $n$ 个元素两两互不相等. 也可简洁地记为如下的形式：

\[ \exists x_0\cdots \exists x_{n-1} \bigwedge_{i<j<n} \neg (x_i=x_j) \]

如果 $n=1$ ，语句写为：$\exists^{\geqslant 1} = \exists x[x=x]$ .

不难验证

\[ \underset{\mathfrak{A}}{|\!\!\!=}\ \exists^{\geqslant n} \iff |A|\geqslant n \]

(3) 严格线序的几个条件也可以用语句表达，例如非自反性：

\[ \theta_{\mathrm{irrefl}} = \forall x (\neg x < x) \]

此时也就是说 $\mathfrak{A}$ 具有非自反性. 同样的还有传递性、全序性 (connected) 以及稠密性 $\theta_{\mathrm{trans}},\theta_{\mathrm{conn}},\theta_{\mathrm{dense}}$ .

那么此时表达严格线序 (strict linear ordering) 的语句为

\[ \theta_{\mathrm{SLO}} = \theta_{\mathrm{irrefl}}\land \theta_{\mathrm{trans}}\land \theta_{\mathrm{conn}} \]

稠密严格线序 (dense linear ordering)：

\[ \theta_{\mathrm{DLO}} = \theta_{\mathrm{SLO}}\land \exists^{\geqslant 2} \land \theta_{\mathrm{dense}} \]

数学结构模型

模型的定义

定义：数学结构模型

对于任意的结构 $\mathfrak{A}$，

$\mathfrak{A}$ 为 $L$-语句 $\varphi$ 的模型当且仅当 $\varphi$ 在 $\mathfrak{A}$ 中为真.
$\mathfrak{A}$ 为语句集 $\Gamma$ 的模型当且仅当对于其中的每个语句 $\varphi$ 在 $\mathfrak{A}$ 中为真.

一个语句对不对其实还是要看它所在的模型，这也就像我们讨论一个命题的正确与否必须要给定一个背景是一样的. 例如，我们不会说在全域为 $\mathbb{R}^2$ 中的一个元素为 $1$ 这个命题是对的.

模型的例子

我们这次折返回来讨论群论的基本对象：群结构 $\mathfrak{G} = (G,*,^{-1},e)$ . 在我们定义群的时候，实际上我们就是在定义 $\mathfrak{G}$ 为如下语句集的模型：

\[ \Gamma_{\mathrm{Gp}} := \left\lbrace \theta_{\mathrm{assoc}},\theta_{\mathrm{ident}},\theta_{\mathrm{inverse}} \right\rbrace \]

这三个语句就是结合律、存在幺元、任意元素存在逆元，这里由于教材有相应内容不多赘述.

如果我们拿掉其中的逆元运算符：$\mathfrak{G} = (G,*,e)$ ，那么相应的语句也会有所变化：

\[ \theta'_{\mathrm{inverse}} = \forall x \exists y [x*y = e \land y*x=e] \]

命题：逻辑后承的等价条件

对于任意的语句集 $\Gamma$ 和语句 $\psi$ ，
$$ \Gamma \models \psi \iff \text{每个 } \Gamma \text{ 的模型都是 } \psi \text{ 的模型}.$$

结合上面的命题，也就有

\[ \Gamma_{\mathrm{Gp}}\models \varphi \]

等价于 $\varphi$ 在所有群当中为真. 翻译过来就是说，如果对于所有满足群定义的三个条件结构 $\varphi$ 都为真，则 $\varphi$ 在所有的群当中为真. 每个这样的 $\varphi$ 也称为群论的定理.

代换的概念

现在我们终于要进行代换的讨论了，这里我们只要说的还是用项去代换变元的情形.

定义：代换

对于任意的项 $u$ 和变元 $x$ ，

对于任意的变元 $y$ ，$$ y_x(u) := \begin{cases}u ,&\text{如果 } y\text{ 是 }x, \ y, & \text{其他情况}. \end{cases} $$
对于常量 $c$ ，$c_x(u)$ 就是 $c$ .
对于任意的函数 $f$ 和任意的项 $t_0,\cdots,t_{\nu_L(f)-1}$，

\[ (ft_0\cdots t_{\nu_{L}(f)-1})(u) := f(t_0)_x(u)\cdots(t_{\nu_L(f)-1})_x(u) \]

逻辑语义 (Basic Semantics)

逻辑有效、逻辑等价、逻辑后承

定义

重言式

等词公理

等词公理的内容

常见的逻辑有效和逻辑后承式

自由变量、受囿变量

\(L\)-语句

\(\underset{\mathfrak{A}}{\models}\ \varphi\) 的基本性质

不依赖 \(\mathfrak{A}\) 指派

\(L\) 语句的真假

真假公式的例子

数学结构模型

模型的定义

模型的例子

代换的概念

评论