命题与形式化表示

在谈命题之前我们首先简单介绍形式化表示，所谓形式化表示简单来说就是由一些给定集合里的符号拼接相连而成的，他们本身没有任何意义类似于一个占位符直至我们对其进行具体的解释说明，关于这个形式化表示的具体内容我们在后面会逐渐补充讲解，其实它早已经渗透我们过去的数学学习，例如我们用 $f(x,y)$ 形式化表示 $(x,y)$ 经由 $f$ 映射得到的结果，当我们不对 $(x,y)$ 赋值解释它本身是没有意义的，如果我们不解释 $f$ 当然也没有意义，它就只是一堆符号而已。

接下来回归主题，所谓命题就是能够判断真假的陈述句，一般用小写字母符号 $p,q,r$ 形式化表示，它的判断结果我们称为该命题的真值，要么是真要么是假，我们分别用数字符号 1 和 0 来形式化表示，并用 $v(p)$ 来形式化表示 $p$ 的真值，上述符号 p 我们一般叫做变量符号，1 叫做常量符号，v 叫做函数符号

命题与命题之间也可以做运算得到一个新的命题，这就要用到命题联结词：否定、析取、合取、蕴含和等价，若记全体命题集合为 $W$，则命题联结词本质上为一个从 $W^n$ 到 $W$ 的映射 (n=1或2)，我们分别用 $\neg,\lor,\land,\to,\leftrightarrow$ 来形式化表示这五种映射。例如，合取映射的结果我们可以形式化表示为 $p\land q$，当我们对 $p,q$ 赋值后它就是一个新的命题。

若一个命题由有限个命题通过命题联结词有限多次复合运算而成，则称其为复合命题，否则称为简单命题。

命题变元与命题公式

现实中很多时候我们关心的是命题的真值情况而非具体内容，我们可以发现复合命题的真值是由其子命题的真值唯一确定而与具体内容无关，所以自然就会去想这个命题联结词对于命题真值的间接映射规则是什么，此时我们就需要抽离命题的具体内容来分析其真值对应情况，这就体现了形式化表示的好处，天然的遮蔽了命题的具体内容。

我们先通过枚举自变量命题的真值取值，来来看单个命题联结词作用于命题后得到的新命题和旧命题真值之间的关系：

$p$	$q$	$\neg p$	$p \land q$	$p \lor q$	$p \to q$	$p \leftrightarrow q$
$1$	$1$	$0$	$1$	$1$	$1$	$1$
$1$	$0$	$0$	$0$	$1$	$0$	$0$
$0$	$1$	$1$	$0$	$1$	$1$	$0$
$0$	$0$	$1$	$0$	$0$	$1$	$1$

也就是说命题联结词自然就继承或说被赋予了另一种形式的映射：$v(W)^n\to v(W)$，即 $\{0,1\}^n \to \{0,1\}$，其中 $n=1,2$，映射规则如上表，并且我们称取值为全体命题真值集合 $\{0,1\}$ 的变量为命题变元，也用小写字母 $p,q,r$ 形式化表示。

前面定义的命题联结词的复合运算结果构建了复合命题，现在命题联结词赋予了另一种映射，自然也可以进行复合运算从而构建了命题公式的概念：关于命题公式，我们定义为由有限个命题变元符号通过有限次命题联结词的复合运算拼接得到的形式化结果，类似于占位符，它不是一个映射，它作为多次联结复合运算的形式化表示我们记为 $f(p_1,\cdots,p_n)$，当我们对其赋值解释才有意义，如果某个赋值使得映射值为 1，则称为成真赋值，如果为 0，则为成假赋值，而我们称某公式值为 1 是指该公式在进行赋值后的值为 1。

对于形如 $f(p,q,r)=(p\to q)\land r$ 的形式化表示，如果给 $p,q,r$ 赋值为命题，则 $f(p,q,r)$ 就是一个复合命题，其中映射 $f:W^3\to W$，而如果给 $p,q,r$ 赋值为命题真值，那么此时 $f(p,q,r)$ 为命题真值，其中映射 $f:\{0,1\}^3\to \{0,1\}$。我们可以不加区分这两个概念，依据上下文需要而定，并且我们有 $v(f(p_1,\cdots,p_n))=f(v(p_1),\cdots,v(p_n))$。

对于 $n$ 元命题公式 $f(p_1,\cdots,p_n)$，我们容易知道映射 $f$ 只有 $2^n$ 个，但是这样的命题公式的形式是无穷多个的，这说明存在不同形式的命题公式其对应映射是一样的。我们考虑两类特殊的映射，一种是全部映射到 $1$，我们称对应这样映射的命题公式为重言式，另一种是全部映射到 $0$，我们则称为矛盾式。如果任给两个公式 $\alpha,\beta$ 有公式 $\alpha\leftrightarrow \beta$ 为重言式，则称这两个公式是等价的，记为 $\alpha\equiv \beta$，容易知道对应相同映射的 $n$ 元公式一定是等价的。

注意，等价的两个公式，不一定对应的映射相同，这是因为二者可能并不一定是同元的，比如 $p\lor q\equiv p\lor q \lor r\lor (\neg r)$

有时候命题公式的形式太复杂我们往往没法很好的得到其对应的真值映射，比如一个重言式可能会有很复杂的形式，但它对应的映射却很简单，而所有 n 元公式可以根据上述定义的等价关系划分为 $2^n$ 类，所以我们自然会想在每个类中寻找一个较为简单看出其对应映射的公式形式，且类中的每个元都有唯一的这样形式的公式对应，从而有助于现实中我们对于一个复杂命题真题的判断。

主析取范式

我们不妨采用执果索因，先分析哪种代表元容易看出其对应映射，对于一个 $n$ 元公式 $f$，我们不妨考虑它的成真赋值，更特殊的如果它只有一个成真赋值 $(\delta_1,\cdots,\delta_n)$，那么必然有如下等式成立：

$$f\equiv m(p_1,\cdots,p_n)=p_1'\land\cdots\land p_n',\quad p_k'=\begin{cases}p_k,\,\delta_k=1\\\neg p_k,\,\delta_k=0\end{cases}$$

而 $m$ 这种形式的公式我们是非常容易看出其成真赋值的，有了成真赋值自然就知道对应的映射了，而对于具有 $k$ 个成真赋值的 n 元公式 $f$，我们也可以等价于上述形式的合取 $m_1\lor m_2\cdots\lor m_k$，这里的 $m_k$ 分别对应每个成真赋值，等价关系是容易看出的，并且在不考虑 $m_i$ 的次序的情况下是由 $f$ 唯一确定的，也就是说这类代表元就是我们想要寻找的。

我们称上述的 $m_i$ 为 n 元极小项，称 $m_1\lor m_2\cdots\lor m_k$ 为 $f$ 的主析取范式。

现在的问题就是我们该如何快速的或者说系统的对任意一个公式将它变形为我们想要的主析取范式的形式，观察主析取范式的形式：

• 首先它不含蕴含和等价
• 其次它的否定是位于变元前面
• 再者它是一些形如变元或其否定的合取，再析取而成的
• 每个合取要出现且仅出现每个变元或其否定

根据这个思路，我们可以采取如下策略对其等价变形： Let $\alpha, \beta, \gamma$ be formulas

• $\alpha \leftrightarrow \beta \equiv (\alpha \land \beta) \lor (\neg \alpha \land \neg \beta)$, $\alpha \to \beta \equiv \neg \alpha \lor \beta$.
• $\neg \neg \alpha \equiv \alpha$ , $\neg (\alpha \land \beta) \equiv \neg \alpha \lor \neg \beta$ , $\neg (\alpha \lor \beta) \equiv \neg \alpha \land \neg \beta$.
• $\alpha \lor (\beta \land \gamma) \equiv (\alpha \lor \beta) \land (\alpha \lor \gamma)$ , $\alpha \land (\beta \lor \gamma) \equiv (\alpha \land \beta) \lor (\alpha \land \gamma)$.
• $\alpha \land \beta \equiv \alpha \land \beta \land (\gamma \lor \neg \gamma) \equiv (\alpha \land \beta \land \gamma) \lor (\alpha \land \beta \land \neg \gamma)$. $\alpha \lor \alpha \lor \beta \equiv \alpha \lor \beta$.

从而就可以系统化的得到每个公式的主析取范式，从而快速得到其映射规则。

注：我们也可以根据成假赋值构造极大项与主合取范式，思路一样，不加赘述。

逻辑推理与公理系统

根据主析取范式，我们可以很容易根据变元的赋值得到映射的值，也就是当我们知道几个命题的真值后，可以很容易得到这几个命题的复合命题的真值，这其实就属于逻辑推理：根据几个前提命题的真值，得到目标命题的真值，即形式化表述为在已知公式 $f_1(p_1,\cdots,p_n),\cdots,f_n(p_1,\cdots,p_n)$ 值为 1，如何求得公式 $g(p_1,\cdots,p_n)$ 的值。

如果说目标命题或公式可以写成已知命题或公式的复合，那么我们可以根据上述的主析取范式得到其真值，但往往很多时候我们都无法写成复合形式，此时我们一般有如下的三种策略：

• 把符合前提的赋值 $(p_1,\cdots,p_n)$ 求出来，再代入 $g(p_1,\cdots,p_n)$
  • 可以利用主析取范式直接得到每一个 $f_i$ 的成真赋值，再取交集
  • 也可以先利用主析取范式得到 $f_1$ 的成真赋值，再代入 $f_2$ 看起是否使其成真，如果不成真则换一个 $f_1$ 的成真赋值再代入，否则一直往下一个公式代入
• 利用主析取范式证明重言蕴含式
  • $(f_1 \land \cdots \land f_n) \to g$ 为重言式 $\Leftrightarrow g$ 值为 $1$
  • $(f_1 \land \cdots \land f_n) \to \neg g$ 为重言式 $\Leftrightarrow g$ 值为 $0$
  • 其他情况，implies $g$ 值不定
• 参考一些简单的已知的重言蕴含式，形如 $A_1\land\cdots\land A_n\to B$，（这里的 $A_i,B$ 为公式），记为 $A_1,\cdots,A_n \vdash B$，称之为推理规则，即在已知前提公式形如 $A_1,\cdots,A_n$ 为真时，可推出形如 $B$ 的公式为真，利用重言式进行变量替换仍为重言式，我们有如下例子：
  • 根据分离规则 $\alpha \land (\alpha \to \beta) \to \beta$，则若已知 $p$ 和 $p \to (q \lor r)$ 为真，有 $q \lor r$ 为真
  • 根据假言三段式规则 $(\alpha \to \beta) \land (\beta \to \gamma) \to (\alpha \to \gamma)$，则若已知 $p \to q$ 和 $q \to \neg r$ 为真，有 $p \to \neg r$ 为真
  • 一些常用的推理规则可以帮助我们迅速根据一些命题得到一些结论，而不需要进行演算

根据上面说的推理规则，我们可以构建一个公理系统，由以下三部分组成：

• 一些给定的重言式，称为公理
• 一些给定的推理规则，如分离规则
• 由给定的重言式根据推理规则得到的重言式，称为定理

注意在公理系统中，我们不能根据真值表或等价演算来推出定理，必须根据给定的规则，把前提都摆出来，才能得到结论。

一阶逻辑

前面我们一直在研究命题的真值而忽略其具体内容，但是现实中往往还要研究命题的其他特性，例如命题中的对象、属性以及对象之间的关系等，于是我们引入一阶逻辑，也叫谓词逻辑，可以理解为就是剖析了一个命题句子中的谓语动词和主语宾语这些概念，下面我们来系统性介绍。

我们称命题中的对象为个体，用小写字母 $a,b,c$ 形式化表示取值为个体的个体变元或者个体常量；并用谓词来体现命题中对象的属性，用 $p$ 表示，其是一个从个体到命题的映射，记为 $p:A^n\to W,\, (a_1,\cdots,a_n)\to p(a_1,\cdots,a_n)$，其中 $A$ 是指我们当前所讨论的全体个体构成的非空集合，称为论域或个体域；再用函词来对个体进行运算体现个体间的关系，用 $f$ 表示，其是一个从个体到个体的映射，记为 $f:A^n\to A，\,(a_1,\cdots,a_n)\to f(a_1,\cdots,a_n)$，注意 $f$ 必须将一个或多个个体映射回论域 $A$。

有了这个概念，我们就可以将命题进行拆解，例如对于命题 q: he loves your sister，可形式化写为 $q=p(a,f(b))$，我们进行如下解释： 变量 a 赋值 he ，变量 b 赋值 you，f(x) 表示 the sister of x，p(x,y) 表示 x love y，并且对于复合命题形式只需要用联结词联结就好，也就是说命题可以作为一个自变量为个体的的映射的值域。

值得注意的是，函词符号通常有三种形式化表示方法：

• 前置法，如 $\sin (3x),\ln(x)$
• 中置法，如 $x+y,x\cdot y$
• 后置法，如 $n!$

通常来说中置法需要引入括号顺序才不会乱，而前置和后置则不需要，例如：

• $5\div((x+2)\times 3-y)$
• $\div 5-\times +x23y$

下面我们再给出几个形式化定义：

• 项：个体变元符号 a 为项；个体常量符号 a 也为项；f 为 n 元函词符号，且 $t_1,\cdots,t_n$ 为项时，符号表示 $f(t_1,\cdots,t_n)$ 也为项；项仅有上法得
• 原子公式：$t_1,\cdots,t_n$ 为项，p 为 n 元函词符号，则称符号表示 $p(a_1,\cdots,a_n)$ 为原子公式

接着我们给出量词与公式的概念：

• 存在量词，用符号 $\exists$ 表示，作用于个体变元与公式，映射到一个新公式，映射规则为广义析取，表示为 $\exists\,x(\varphi(x))=\lor_{x}\varphi(x)$
• 全称量词，用符号 $\forall$ 表示，作用于个体变元与公式，映射到一个新公式，映射规则为广义合取，表示为 $\forall\,x(\varphi(x))=\land_x\varphi(x)$
• 原子公式是最简单的公式
• $\varphi$ 是公式时，$\exists\,x(\varphi(x)),\forall\,x(\varphi(x)),\neg \varphi$ 也是公式
• $\varphi,\phi$ 是公式时，$\varphi\lor\phi,\varphi\land \phi,\varphi\to\phi,\varphi\leftrightarrow\phi$ 也是映射
• 公式仅有上法所得

上述无论是项、原子公式还是公式，都是一堆符号表示，在未被解释说明的时候都没有意义。

并且我们称由量词作用的个体变元为约束变元，其他变元为自由变元，容易知道约束变元不需要进行赋值即有意义，因为量词会遍历所有取值，自由变元则可以自由赋值。

关于公式我们有如下简写约定：

• $\exists!x \ \varphi(x)$ 相当于 $\exists x(\varphi(x) \land \forall y(\varphi(y) \rightarrow y = x))$
• $\exists x \in X \ \varphi(x)$ 相当于 $\exists x(x \in X \land \varphi(x))$
• $\forall x \in X \ \varphi(x)$ 相当于 $\forall x(x \in X \rightarrow \varphi(x))$

上述一阶逻辑的公式称为一阶公式。

解释与模型

前面我们一直在模糊的谈对一堆符号的解释说明使得其有意义，下面我们系统性的对这个行为进行定义。事实上前面我们已经给出了一部分概念，对于一个一阶公式，它的符号有自由变元、约束变元、常量符号、函词符号、谓词符号，我们都要对其赋予意义，它才有真正含义。

首先考虑一个没有自由变元的一阶公式，我们称为闭公式或者断定。

对于闭公式 $\varphi$，取定某非空集合 $D$ 作为个体域，解释 $I$ 定义如下：

• 把 $\varphi$ 中常量符号解释为 $D$ 中具体个体 $C$，记为 $C^{\mathcal{U}}$
• 把 $\varphi$ 中 n 元函词符号 f 解释为 $D^n\to D$ 的具体映射，记为 $f^{\mathcal{U}}$
• 把 $\varphi$ 中 n 元谓词符号 p 解释为具体的 n 元谓词映射，记为 $p^{\mathcal{U}}$

从而 $I:\varphi\to \varphi^{\mathcal{U}}$，容易知道闭公式经过解释后就是一个命题，从而有真值，若经过解释为真，则称 $\mathcal{U}=\{D,I\}$ 为该闭公式 $\varphi$ 的一个模型，如果该模型为一个闭公式集中每一个闭公式的模型，则称该模型为该闭公式集的模型。

而对于有自由变元的一阶公式，我们同样可以像上述一样定义个体域 $D$ 与解释 $I$，称 $\mathcal{M}=\{D,I\}$ 为该公式的一个结构，此时我们定义一个赋值映射：$s:var\to D$，把所有的自由变元映射到个体域中，如果一阶公式 $\varphi$ 在结构 $\mathcal{M}$ 和任意赋值映射下均得到的命题均为真，则称结构 $\mathcal{M}$ 是 $\varphi$ 的一个模型。而若公式在结构 $\mathcal{M}$ 和某个赋值映射 $s$ 下为真，则称为在结构 $\mathcal{M}$ 和赋值 $s$ 下，公式 $\varphi$ 被满足，记为 $\mathcal{M}, s \models \varphi$。

对于一阶闭公式 $\varphi$，如果任何 $\mathcal{U}=\{D,I\}$ 均为他的模型，则称 $\varphi$ 为永真式，有了永真我们可以如命题公式一般去定义闭公式之间的等价，这里不赘述。

注：对于函数 $f(x)$ 我们已经知道这也是形式化表示，只有在某种结构下并给予一个赋值映射才能变成一个函数值，而这个形式化表示在被赋值后是完全对应上 $f$ 的映射规则的，这也是为什么用这个形式化表示该映射。

和命题逻辑类似，我们同样可以选取一些永真多一阶公式，采用一些推理规则，推导出一些永真式，从而构建一个公理系统。