命题逻辑的基础概念 #
命题、联结词、命题形式与真值表 #
- 命题：取值为0或1的符号
- 联结词：否定、合取
- 复合命题 = 命题 + 联结词
- 命题形式的BNF (Bacus Normal Form): $$ \alpha ::= p \mid \neg \alpha \mid (\alpha \lor \beta) \mid (\alpha \land \beta) \mid (\alpha \to \beta) \mid (\alpha \leftrightarrow \beta) $$ 每个命题形式都是有限的符号串
- 指派：命题形式的所有变元的一组值
- 真值表：命题形式在所有指派下的值
- 重言式、矛盾式、可满足式
- 与哑元的无关性
联结词的完全集 #
联结词确定了复合命题的构造方式，复合命题建立了真假值的对应方式；这个对应方式形成了一个真值函数，那么就意味着联结词确定了一个真值函数；反过来，每一个真值函数也能确定一个真值表，对于每一个指派都有一个在{0,1}内的值，也确定了一个联结词。
联结词能确定一个真值函数，由联结词和变元构成的命题形式，也能确定一个真值函数。设命题形式$\alpha$所含的命题变元都在$p1, p2, ..., pn$中。如下定义的n元真值函数称为$\alpha$确定的真值函数，记为$f_{\alpha}$:
$$ f_{\alpha}(t1, t2 , … , tn) = \alpha \text{ 关于 } p1, p2 , … , pn \text{ 在 } \text{指派 } t1, t2 , … , tn \text{ 下的值 }。 $$完全集：设A一个联结词集合，称A为联结词的一个完全集，如果任一个真值函数f都可用A中联结词来表示，即：对任真值函数 f，都存在仅含A中联结词的命题$\alpha$使得：
$$ \alpha \text{ 在任意指派 }例如：$\{ \neg, \land, \lor, \to \}$是联结词的一个完全集，$\{\neg, \land\}$也是联结词的一个完全集。
推理形式与有效性 #
上面是命题的形式（命题、联结词、命题形式、联结词的完全集），接下来介绍推理的形式。推理是逻辑的研究对象。
- 推理形式：一组前提和一个结论，前提和结论都是命题形式。
- 有效的推理形式：对于任意一个指派，若前提都为真，则结论也为真。
- 无效的推理形式：存在一个指派，使得前提都为真，但结论为假。 若$\Gamma 推出 \beta$是有效的，则记作$\Gamma \vDash \beta$。
形式系统的基本组成 #
由四个集合构成：
- 符号库/字母表：非空集合A(I)
- 公式集：由A(I)中的有限序列构成集合E(I)
- 公理集: 公式集上的一个子集
- 推理规则集：公式集上的部分运算构成的集合 前两者为I的形式语言，后两者为I的形式推理。
命题演算的自然推理形式系统 N #
形式语言与公理 #
建立N：
- 符号库A(N): （1）可数个命题符号p1,p2,… （2）5个联结词符号 $\neg, \land, \lor, \to, \leftrightarrow$ （3）三个辅助符号 $), ($
- 公式集F(N): （1）命题符号都是公式；（2）若 $\alpha$ 是公式，则$(\neg \alpha)$也是公式。（3）若$\alpha$是公式，则$(\alpha \land \beta),(\alpha \lor \beta),(\alpha \to \beta),(\alpha \leftrightarrow \beta)$也是公式。（4）N的每个公式都是有限次应用（1）（2）（3）得到的。
- 公理集是空集。
基本推理规则 #
- 推理规则集：
1. 前提规则 #
$$ \Gamma \cup \{\alpha\} \vdash_N \alpha $$2. 合取引入律 #
$$ \frac{ \Gamma \vdash_N \alpha \qquad \Gamma \vdash_N \beta }{ \Gamma \vdash_N \alpha \land \beta } \;(\land+) $$3. 合取消去律 #
$$ \frac{ \Gamma \vdash_N \alpha \land \beta }{ \Gamma \vdash_N \alpha } \;(\land-) \qquad \frac{ \Gamma \vdash_N \alpha \land \beta }{ \Gamma \vdash_N \beta } \;(\land-) $$4. 析取引入律 #
$$ \frac{ \Gamma \vdash_N \alpha }{ \Gamma \vdash_N \alpha \lor \beta } \;(\lor+) \qquad \frac{ \Gamma \vdash_N \beta }{ \Gamma \vdash_N \alpha \lor \beta } \;(\lor+) $$5. 析取消去律 #
$$ \frac{ \Gamma \cup \{\alpha\} \vdash_N \gamma \qquad \Gamma \cup \{\beta\} \vdash_N \gamma }{ \Gamma \cup \{\alpha \lor \beta\} \vdash_N \gamma } \;(\lor-) $$6. 蕴含引入律 #
$$ \frac{ \Gamma \cup \{\alpha\} \vdash_N \beta }{ \Gamma \vdash_N \alpha \to \beta } \;(\to+) $$7. 蕴含消去律（分离规则） #
$$ \frac{ \Gamma \vdash_N \alpha \to \beta \qquad \Gamma \vdash_N \alpha }{ \Gamma \vdash_N \beta } \;(\to-) $$8. 否定引入律 #
$$ \frac{ \Gamma \cup \{\alpha\} \vdash_N \beta \qquad \Gamma \cup \{\alpha\} \vdash_N \neg\beta }{ \Gamma \vdash_N \neg\alpha } \;(\neg+) $$9. 否定消去律（经典反证法） #
$$ \frac{ \Gamma \cup \{\neg\alpha\} \vdash_N \beta \qquad \Gamma \cup \{\neg\alpha\} \vdash_N \neg\beta }{ \Gamma \vdash_N \alpha } \;(\neg-) $$10. 等价引入律 #
$$ \frac{ \Gamma \vdash_N \alpha \to \beta \qquad \Gamma \vdash_N \beta \to \alpha }{ \Gamma \vdash_N \alpha \leftrightarrow \beta } \;(\leftrightarrow+) $$11. 等价消去律 #
$$ \frac{ \Gamma \vdash_N \alpha \leftrightarrow \beta \qquad \Gamma \vdash_N \alpha }{ \Gamma \vdash_N \beta } \;(\leftrightarrow-) $$$$ \frac{ \Gamma \vdash_N \alpha \leftrightarrow \beta \qquad \Gamma \vdash_N \beta }{ \Gamma \vdash_N \alpha } \;(\leftrightarrow-) $$形式证明的定义 #
- 形式证明：若有限序列
满足：
-
$\Gamma_1,\Gamma_2,\ldots,\Gamma_n$ 为 $N$ 中有限公式集，$\alpha_1,\alpha_2,\ldots,\alpha_n$ 为 $N$ 中公式。
-
每个 $\Gamma_i\vdash\alpha_i$（$1\le i\le n$）都是对 $(*)$ 中它之前的若干个 $\Gamma_j\vdash\alpha_j$（$j
则称 $(*)$ 为 $\Gamma_n\vdash\alpha_n$ 在 $N$ 中的一个形式证明，$n$ 称为这个形式证明的长度。此时也称 $\alpha_n$ 在 $N$ 中可由 $\Gamma_n$ 形式证明或形式推出，记为 $\Gamma_n\vdash_N\alpha_n$ 或 $\Gamma_n\vdash\alpha_n$。
利用形式证明的定义，和已有的推理规则，可以继续延伸：
12. 增加前提律 #
$$ \frac{ \Gamma \vdash_N \alpha }{ \Gamma, \beta \vdash_N \alpha } \;(+) $$
元定理 #
两个元定理：
- 传递律(Tr)：若$\Gamma \vdash \alpha_1, \alpha_2, ..., \alpha_n, $且$\alpha_1, \alpha_2, ..., \alpha_n \vdash \alpha$，则 $\Gamma \vdash \alpha$。
推论：若$\Gamma_1 \vdash \Gamma_2, \Gamma_2 \vdash \Gamma_3, ... \Gamma_{n-1} \vdash \Gamma_n $，则 $\Gamma_1 \vdash \Gamma_n$。
- 设 $\alpha_1,\alpha_2,\alpha_3,\alpha_4$ 都是 $N$ 中公式。若
且 $\alpha_1\vdash\alpha_2$，则 $\alpha_3\vdash\alpha_4$。
有前提的形式推演与内定理 #
对于任意公式 $\alpha,\alpha_1,\alpha_2,\ldots,\alpha_n$，
$$ \begin{aligned} (1)\quad &\alpha_1,\alpha_2,\ldots,\alpha_n \vdash \alpha \quad \text{当且仅当} \quad \varnothing \vdash \alpha_1 \to \bigl(\alpha_2 \to \cdots \to (\alpha_{n-1} \to (\alpha_n \to \alpha))\cdots\bigr); \\[6pt] (2)\quad &\alpha_1,\alpha_2,\ldots,\alpha_n \vdash \alpha \quad \text{当且仅当} \quad \varnothing \vdash (\alpha_1 \land \alpha_2 \land \cdots \land \alpha_n) \to \alpha. \end{aligned} $$这个定理的意义是：
若 $\varnothing \vdash_N \alpha$，则称 $\alpha$ 为 $N$ 的一个可证公式或内定理，记为 $\vdash_N \alpha$，在不引起混淆情况下，也简记为 $\vdash \alpha$。
任何一个有前提的形式推演关系 都可转化为 与之等价的 没有前提的形式推演关系。即：任何一个形式推演关系都可化为一个与之等价的可证式。
命题演算形式系统 P #
形式语言、公理与推理规则 #
建立P：
- 符号库A(N): （1）可数个命题符号p1,p2,… （2）2个联结词符号 $\neg, \to$ （3）三个辅助符号 $), ($
- 公式集F(N): （1）命题符号都是公式；（2）若 $\alpha$ 是公式，则$(\neg \alpha)$也是公式。（3）若$\alpha$是公式，则$(\alpha \to \beta)$也是公式。（4）N的每个公式都是有限次应用（1）（2）（3）得到的。
- 公理集有三类： $$ \begin{aligned} \text{(A1)}\quad &(\alpha \to (\beta \to \alpha));\\[6pt] \text{(A2)}\quad &((\alpha \to (\beta \to \gamma)) \to ((\alpha \to \beta) \to (\alpha \to \gamma)));\\[6pt] \text{(A3)}\quad &(((\neg \alpha) \to (\neg \beta)) \to (\beta \to \alpha)). \end{aligned} $$
- 推理规则集： 分离规则：由 $\alpha, (\alpha \to \beta)$ 可得到 $\beta$，记为 $(\mathrm{M})$。
无前提的形式推理与内定理 #
对于任意的 $\mathrm{P}$ 中公式序列：
$$ \alpha_1,\ \alpha_2,\ \cdots,\ \alpha_n, \tag{*} $$若对每个 $i\ (1 \le i \le n)$，下列两条件之一成立：
(1) $\alpha_i$ 是公理；
(2) $\alpha_i$ 是由序列 $(*)$ 中 $\alpha_i$ 之前的某两个公式 $\alpha_j,\alpha_k$（$1 \le j,k < i$）应用分离规则 $(\mathrm{M})$ 得到的。
则 $\alpha_n$ 称为 $\mathrm{P}$ 的一个内定理，记作 $\vdash_{\mathrm{P}} \alpha_n$ 或 $\vdash \alpha_n$，称 $(*)$ 为 $\alpha_n$ 的一个证明序列。
有前提的推演 #
定义：设 $\Sigma$ 是 $P$ 中的一个公式集，称 $P$ 中公式序列
$$ \alpha_1,\ \alpha_2,\ \cdots,\ \alpha_n \tag{*} $$为在前提 $\Sigma$ 下推出 $\alpha_n$ 的一个证明，如果对每一个 $\alpha_i\ (1 \le i \le n)$，下列三个条件之一成立：
(1) $\alpha_i$ 是 $P$ 中一个公理；
(2) $\alpha_i \in \Sigma$；
(3) $\alpha_i$ 是由序列 $(*)$ 中它前面的两个公式应用分离规则 $(\mathrm{M})$ 得到的。
此时，记为 $\Sigma \vdash_P \alpha$ 或 $\Sigma \vdash \alpha$。
演绎定理 #
建立了 “内定理” & “有前提的推理” 之间的联系，也使得许多内定理证明得以简化
设 $\Gamma$ 是 $P$ 中的一个公式集，$\alpha,\beta$ 是 $P$ 的两个公式，若 $\Gamma \cup \{\alpha\} \vdash \beta$，则 $\Gamma \vdash \alpha \to \beta$。
由演绎定理可知：
$$ 若\{ \alpha_1, \alpha_2, ..., \alpha_n \} \vdash \beta，则 \vdash (\alpha_1 \to (\alpha_2 \to \cdots \to (\alpha_n \to \beta) \cdots ) $$演绎定理的逆命题 #
设 $\Gamma$ 是 $P$ 中的一个公式集，$\alpha,\beta$ 是 $P$ 的两个公式，若 $\Gamma \vdash \alpha \to \beta$，则 $\Gamma \cup \{\alpha\} \vdash \beta$。
常用内定理 #
| 名称或用途 | 内定理 |
|---|---|
| 自反式 | \(A\to A\) |
| 矛盾推出任意公式 | \(\neg A\to(A\to B)\) |
| 双重否定消去 | \(\neg\neg A\to A\) |
| 双重否定引入 | \(A\to\neg\neg A\) |
| 逆否式(A3) | \((A\to B)\to(\neg B\to\neg A)\) |
| 蕴含传递 | \((A\to B)\to((B\to C)\to(A\to C))\) |
| 归谬式 | \((\neg A\to A)\to A\) |
| 否定蕴含，得到前件 | \(\neg(A\to B)\to A\) |
| 否定蕴含，得到后件的否定 | \(\neg(A\to B)\to\neg B\) |
| 分类讨论 | \((A\to B)\to((\neg A\to B)\to B)\) |
推导的传递性 #
设 $\Sigma$ 是 $P$ 中公式集，$\alpha_1,\alpha_2,\ldots,\alpha_n$ 为 $P$ 中公式。若 $\Sigma \vdash \alpha_1,\ \Sigma \vdash \alpha_2,\ \ldots,\ \Sigma \vdash \alpha_n$，且 $\alpha_1,\alpha_2,\ldots,\alpha_n \vdash \alpha$，则 $\Sigma \vdash \alpha$。
公理的使用与证明模板 #
对于A1，用途一般是对一个已证公式添加一个前置公式，就是这种公式：
$$ \vdash 某个前置公式 \to 显然的已证公式
$$
其中“显然的已证公式”比如A1、A2、A3等。那么证明序列就是利用A1来引进这个“某个前置公式”：
$$ \begin{aligned} 1.\quad & \text{显然的已证公式} && \text{（已知）} \\[6pt] 2.\quad & \text{显然的已证公式} \to (\text{某个前置公式} \to \text{显然的已证公式}) && \text{（A1）} \\[6pt] 3.\quad & \text{某个前置公式} \to \text{显然的已证公式} && \text{（M：1，2）} \end{aligned} $$这样就完成了添加前置公式，有点类似于N中的引入前提。
对于A2，在形式上有点像分配律。
对于A3，可以用来引入否定。
此外，在P中的证明序列，如果不能用Tr的话，也是可用A1、A2、A3等公理来模版化证明的。比如要求下面在P中的证明序列：
$$ A \to B, B \to C \vdash_P A \to C
$$
证明序列：
$$ \begin{aligned} 1.\quad & A \to B && \text{（已知）} \\[6pt] 2.\quad & B \to C && \text{（已知）} \\[6pt] \quad & （tip-接下来想要在2中引入A作为前件） \\[6pt] 3.\quad & (B \to C) \to (A \to (B \to C)) && \text{（A1）} \\[6pt] 4.\quad & A \to (B \to C) && \text{（M：2, 3）} \\[6pt] \quad & （tip-分配律） \\[6pt] 5.\quad & (A \to (B \to C)) \to ((A \to B) \to (A \to C)) && \text{（A2）} \\[6pt] 6.\quad & (A \to B) \to (A \to C) && \text{（M：4, 5）} \\[6pt] 7.\quad & A \to C && \text{（M：1, 6）} \end{aligned} $$常用内定理的证明 #
矛盾推出任意公式 #
证明：
$$ \vdash_P\neg A\to(A\to B). $$利用A1和A3，发现只需要一次Tr即可。套用上面的证明模板。
$$ \begin{array}{rll} \text{①}& \neg A\to(\neg B\to\neg A) &(\mathrm{A1})\\[6pt] \text{②}& (\neg B\to\neg A)\to(A\to B) &(\mathrm{A3})\\[6pt] \text{③}& \bigl((\neg B\to\neg A)\to(A\to B)\bigr) \to \bigl(\neg A\to((\neg B\to\neg A)\to(A\to B))\bigr) &(\mathrm{A1})\\[6pt] \text{④}& \neg A\to((\neg B\to\neg A)\to(A\to B)) &(\mathrm M)\text{②③}\\[6pt] \text{⑤}& \bigl(\neg A\to((\neg B\to\neg A)\to(A\to B))\bigr) \to \bigl((\neg A\to(\neg B\to\neg A)) \to(\neg A\to(A\to B))\bigr) &(\mathrm{A2})\\[6pt] \text{⑥}& (\neg A\to(\neg B\to\neg A)) \to(\neg A\to(A\to B)) &(\mathrm M)\text{④⑤}\\[6pt] \text{⑦}& \neg A\to(A\to B) &(\mathrm M)\text{①⑥} \end{array} $$其中，第②行在 A3 中取 $\varphi=B,\ \psi=A$。
整个证明没有使用任何前提，因此：
$$ \boxed{\vdash_P\neg A\to(A\to B).} $$归谬式 #
证明：
$$ \vdash_P(\neg A\to A)\to A. $$记：
$$ T=(A\to A),\qquad H=(\neg A\to A). $$其中，$T$ 是已证的自反式。先以 $H$ 为临时前提证明 $A$：
$$ \begin{array}{rll} \text{①}& T &\text{（已证自反式）}\\[6pt] \text{②}& \neg A\to(A\to\neg T) &\text{（由第1个内定理，取 }B=\neg T\text{）}\\[6pt] \text{③}& \bigl(\neg A\to(A\to\neg T)\bigr) \to \bigl((\neg A\to A)\to(\neg A\to\neg T)\bigr) &(\mathrm{A2})\\[6pt] \text{④}& H\to(\neg A\to\neg T) &(\mathrm M)\text{②③}\\[6pt] \text{⑤}& H &\text{（临时前提）}\\[6pt] \text{⑥}& \neg A\to\neg T &(\mathrm M)\text{④⑤}\\[6pt] \text{⑦}& (\neg A\to\neg T)\to(T\to A) &(\mathrm{A3})\\[6pt] \text{⑧}& T\to A &(\mathrm M)\text{⑥⑦}\\[6pt] \text{⑨}& A &(\mathrm M)\text{①⑧} \end{array} $$其中，第⑦行在 A3 中取 $\varphi=A,\ \psi=T$。
于是：
$$ \neg A\to A\vdash_P A. $$由演绎定理，撤销临时前提 $H=\neg A\to A$，得到：
$$ \boxed{\vdash_P(\neg A\to A)\to A.} $$临时假设与演绎定理 #
- 可以引入假设前提，再利用演绎定理撤销
例题：17（3） #
证明：
$$ (\alpha\to\beta)\to\gamma \vdash_P (\gamma\to\alpha)\to(\alpha'\to\alpha). $$- 证明思路
目标有两层蕴含，先临时加入前提 $\gamma\to\alpha$ 和 $\alpha'$，把目标变为证明 $\alpha$。
为证明 $\alpha$，再临时假设 $\neg\alpha$。利用“矛盾推出任意公式”的内定理，可以启动以下推理：
$$ \neg\alpha \Longrightarrow \alpha\to\beta \Longrightarrow \gamma \Longrightarrow \alpha. $$随后用演绎定理撤销 $\neg\alpha$，得到 $\neg\alpha\to\alpha$；再由归谬式得到 $\alpha$。最后依次撤销前提 $\alpha'$ 和 $\gamma\to\alpha$。
- 证明序列
记：
$$ H=((\alpha\to\beta)\to\gamma),\qquad K=(\gamma\to\alpha). $$先在前提 $H,K,\alpha',\neg\alpha$ 下证明 $\alpha$：
$$ \begin{array}{rll} \text{①}& H &\text{（原前提）}\\[6pt] \text{②}& K &\text{（临时前提）}\\[6pt] \text{③}& \alpha' &\text{（临时前提）}\\[6pt] \text{④}& \neg\alpha &\text{（临时前提）}\\[6pt] \text{⑤}& \neg\alpha\to(\alpha\to\beta) &\text{（已证内定理）}\\[6pt] \text{⑥}& \alpha\to\beta &(\mathrm M)\text{④⑤}\\[6pt] \text{⑦}& \gamma &(\mathrm M)\text{⑥①}\\[6pt] \text{⑧}& \alpha &(\mathrm M)\text{⑦②} \end{array} $$因此：
$$ H,K,\alpha',\neg\alpha\vdash_P\alpha. $$由演绎定理，撤销临时前提 $\neg\alpha$，得到：
$$ H,K,\alpha'\vdash_P\neg\alpha\to\alpha. $$仍在前提 $H,K,\alpha'$ 下，继续证明：
$$ \begin{array}{rll} \text{①}& \neg\alpha\to\alpha &\text{（由前段及演绎定理）}\\[6pt] \text{②}& (\neg\alpha\to\alpha)\to\alpha &\text{（已证归谬式）}\\[6pt] \text{③}& \alpha &(\mathrm M)\text{①②} \end{array} $$于是：
$$ H,K,\alpha'\vdash_P\alpha. $$由演绎定理，撤销临时前提 $\alpha'$：
$$ H,K\vdash_P\alpha'\to\alpha. $$再由演绎定理，撤销临时前提 $K=\gamma\to\alpha$：
$$ H\vdash_P(\gamma\to\alpha)\to(\alpha'\to\alpha). $$即：
$$ \boxed{ (\alpha\to\beta)\to\gamma \vdash_P (\gamma\to\alpha)\to(\alpha'\to\alpha). } $$注意：临时前提 $\alpha'$ 在推导 $\alpha$ 时没有被使用，这是允许的。演绎定理仍然可以撤销它，得到 $\alpha'\to\alpha$。
N 与 P 的等价性 #
可证性的有限性 #
设 $\Sigma,\alpha$ 分别为 $P$ 中公式集与公式，若 $\Sigma \vdash_P \alpha$，则存在 $\Sigma$ 的有限子集 $\Sigma_0 \subseteq \Sigma$，使得 $\Sigma_0 \vdash_P \alpha$。
P 的公理在 N 中可证 #
若 $\alpha$ 是 $P$ 中公理，则对 $P$ 中任何有限公式集 $\Sigma$ 都有 $\Sigma \vdash_N \alpha$。
由 P 到 N 的可证性 #
设 $\Sigma,\alpha$ 分别为 $P$ 中有限公式集和公式，若 $\Sigma \vdash_P \alpha$，则 $\Sigma \vdash_N \alpha$。
由 N 到 P 的可证性 #
设 $\Sigma,\alpha$ 分别为 $N$ 中有限公式集和公式，若 $\Sigma \vdash_N \alpha$，则 $\Sigma \vdash_P \alpha$。
N 与 P 的内定理相同 #
对 $P$ 或 $N$ 中的公式 $\alpha$，$\vdash_P \alpha$ 当且仅当 $\vdash_N \alpha$。
赋值 #
形式推理只检查公式是否为公理、推理是否符合规则；赋值则给公式赋予真假值，用来讨论公式是否永真。
指派与公式的赋值 #
- 指派：给每个命题符号指定一个值 $0$ 或 $1$，其中 $0$ 表示假，$1$ 表示真。
- 赋值：根据指派和联结词，递归计算每个公式的值。公式 $\alpha$ 在指派 $\sigma$ 下的值记为 $\alpha^\sigma$。
因此，蕴含只有在前件真、后件假时才为假。其他联结词在 $P$ 中是简写，其值也与原来的真值表一致：
$$ \begin{aligned} \alpha\lor\beta&:=\neg\alpha\to\beta, & (\alpha\lor\beta)^\sigma&=\max\{\alpha^\sigma,\beta^\sigma\},\\ \alpha\land\beta&:=\neg(\alpha\to\neg\beta), & (\alpha\land\beta)^\sigma&=\min\{\alpha^\sigma,\beta^\sigma\},\\ \alpha\leftrightarrow\beta&:=(\alpha\to\beta)\land(\beta\to\alpha). \end{aligned} $$其中，$(\alpha\leftrightarrow\beta)^\sigma=1$ 当且仅当 $\alpha^\sigma=\beta^\sigma$。
- 例：若 $\sigma(p_1)=0,\sigma(p_2)=1,\sigma(p_3)=0$，则 $((p_1\lor p_2)\to p_3)^\sigma=0$。
- 哑元无关性：公式的值只取决于其中实际出现的命题符号。两个指派只要在这些符号上相同，公式的值就相同。
永真式、矛盾式、可满足式 #
- 永真式（重言式）：对任意指派 $\sigma$，都有 $\alpha^\sigma=1$。
- 矛盾式（永假式）：对任意指派 $\sigma$，都有 $\alpha^\sigma=0$。
- 可满足式：存在指派 $\sigma$，使得 $\alpha^\sigma=1$。永真式也是可满足式；不可满足的公式就是矛盾式。
公理的永真性与分离规则的保真性 #
$P$ 的公理都是永真式，分离规则保持永真性：若 $\alpha$ 和 $\alpha\to\beta$ 都是永真式，则 $\beta$ 也是永真式。因此，$P$ 中的内定理都是永真式。
重言式的替换定理 #
若 $\alpha$ 是重言式，把其中命题变元 $q_1,\ldots,q_n$ 同时分别替换为任意公式 $\beta_1,\ldots,\beta_n$，所得公式仍为重言式。
- 同一个命题变元的所有出现必须统一替换。例如，$p\to p$ 是重言式，只替换其中一个 $p$ 得到 $q\to p$，就不一定永真。
- 这里替换的是命题变元，不能任意替换整个子公式。例如，把 $p\to(q\to p)$ 中的子公式 $q\to p$ 任意换成 $q$，得到的 $p\to q$ 不再是重言式。
公式的等值与逻辑蕴含 #
等值与逻辑蕴含的定义 #
- 等值：若 $\alpha\leftrightarrow\beta$ 是重言式，称 $\alpha$ 与 $\beta$ 逻辑等价，记为 $\alpha\Leftrightarrow\beta$。
- 逻辑蕴含：若 $\alpha\to\beta$ 是重言式，称 $\alpha$ 逻辑蕴含 $\beta$，记为 $\alpha\Rightarrow\beta$。
注意：$\to,\leftrightarrow$ 是公式内部的联结词；$\Rightarrow,\Leftrightarrow$ 是在公式外部描述逻辑蕴含、等值关系的记号。$\vdash_P\alpha$ 则表示形式可证性。
等值关系具有自反性、对称性和传递性，因此可以连续进行等值变形。
基本等值公式 #
交换律、结合律 #
$$ \begin{aligned} \alpha\lor\beta&\Leftrightarrow\beta\lor\alpha,\\ \alpha\land\beta&\Leftrightarrow\beta\land\alpha,\\ \alpha\leftrightarrow\beta&\Leftrightarrow\beta\leftrightarrow\alpha,\\ (\alpha\lor\beta)\lor\gamma&\Leftrightarrow\alpha\lor(\beta\lor\gamma),\\ (\alpha\land\beta)\land\gamma&\Leftrightarrow\alpha\land(\beta\land\gamma),\\ (\alpha\leftrightarrow\beta)\leftrightarrow\gamma &\Leftrightarrow\alpha\leftrightarrow(\beta\leftrightarrow\gamma). \end{aligned} $$分配律 #
$$ \begin{aligned} \alpha\land(\beta\lor\gamma) &\Leftrightarrow(\alpha\land\beta)\lor(\alpha\land\gamma),\\ \alpha\lor(\beta\land\gamma) &\Leftrightarrow(\alpha\lor\beta)\land(\alpha\lor\gamma),\\ \alpha\to(\beta\to\gamma) &\Leftrightarrow(\alpha\to\beta)\to(\alpha\to\gamma). \end{aligned} $$双重否定律、德摩根律 #
$$ \begin{aligned} \neg\neg\alpha&\Leftrightarrow\alpha,\\ \neg(\alpha\lor\beta)&\Leftrightarrow\neg\alpha\land\neg\beta,\\ \neg(\alpha\land\beta)&\Leftrightarrow\neg\alpha\lor\neg\beta. \end{aligned} $$幂等律、吸收律 #
$$ \begin{aligned} \alpha\lor\alpha&\Leftrightarrow\alpha, &\alpha\land\alpha&\Leftrightarrow\alpha,\\ \alpha\lor(\alpha\land\beta)&\Leftrightarrow\alpha, &\alpha\land(\alpha\lor\beta)&\Leftrightarrow\alpha. \end{aligned} $$蕴含、逆否、归谬及等价的等值式 #
$$ \begin{aligned} \alpha\to\beta&\Leftrightarrow\neg\alpha\lor\beta,\\ \alpha\to\beta&\Leftrightarrow\neg\beta\to\neg\alpha,\\ (\alpha\to\beta)\land(\alpha\to\neg\beta)&\Leftrightarrow\neg\alpha,\\ \alpha\leftrightarrow\beta &\Leftrightarrow(\alpha\to\beta)\land(\beta\to\alpha),\\ \alpha\leftrightarrow\beta&\Leftrightarrow(\neg\alpha\leftrightarrow\neg\beta). \end{aligned} $$零律、同一律、排中律、矛盾律 #
$$ \begin{aligned} \alpha\lor1&\Leftrightarrow1, &\alpha\land0&\Leftrightarrow0,\\ \alpha\lor0&\Leftrightarrow\alpha, &\alpha\land1&\Leftrightarrow\alpha,\\ \alpha\lor\neg\alpha&\Leftrightarrow1, &\alpha\land\neg\alpha&\Leftrightarrow0. \end{aligned} $$这里的 $0,1$ 是矛盾式、重言式的代称，不是 $P$ 新增加的公式符号。
替换定理与等值演算 #
第一替换定理：统一替换命题变元 #
- 第一替换定理：若 $\alpha\Leftrightarrow\beta$，对两边的命题变元同时进行相同的统一替换，所得 $\alpha',\beta'$ 仍满足 $\alpha'\Leftrightarrow\beta'$。它保证可以把等值公式当作模板使用。
例如，在吸收律 $p\land(p\lor q)\Leftrightarrow p$ 中，统一取 $p=(\alpha\to\beta),q=\neg\gamma$，得到：
$$ (\alpha\to\beta)\land((\alpha\to\beta)\lor\neg\gamma) \Leftrightarrow\alpha\to\beta. $$第二替换定理：替换等值子公式 #
- 第二替换定理：若 $\alpha\Leftrightarrow\beta$，将公式 $\gamma$ 中某些作为子公式出现的 $\alpha$ 替换为 $\beta$，所得 $\delta$ 与 $\gamma$ 等值。它保证可以在大公式内部替换等值的局部公式。
例如，由 $\alpha\land(\alpha\lor\beta)\Leftrightarrow\alpha$，可得：
$$ \neg(\alpha\land(\alpha\lor\beta))\Leftrightarrow\neg\alpha. $$两种替换定理的区别 #
区别：第一替换定理是对等值式两边的命题变元统一替换；第二替换定理是在已知局部公式等值的条件下，替换大公式中的子公式，可以只替换其中部分出现。
等值演算 #
- 等值演算：利用基本等值式和替换定理逐步变形，再由等值关系的传递性得到结论。平时直接套公式、替换局部表达式，依据的就是这两个替换定理。
例题：蕴含与合取的转换 #
例：证明 $p\to(q\to r)\Leftrightarrow(p\land q)\to r$。
$$ \begin{aligned} p\to(q\to r) &\Leftrightarrow\neg p\lor(q\to r) &&\text{（蕴含等值式、第一替换定理）}\\ &\Leftrightarrow\neg p\lor(\neg q\lor r) &&\text{（蕴含等值式、第二替换定理）}\\ &\Leftrightarrow(\neg p\lor\neg q)\lor r &&\text{（结合律）}\\ &\Leftrightarrow\neg(p\land q)\lor r &&\text{（德摩根律、第二替换定理）}\\ &\Leftrightarrow(p\land q)\to r &&\text{（蕴含等值式、第一替换定理）}. \end{aligned} $$析取范式与合取范式 #
范式是公式在等值意义下的一种标准形式，用来把公式整理成统一的结构。
文字与简单析（合）取式 #
- 文字：命题变元或命题变元的否定，例如 $p,\neg q$。
- 简单合取式：由 $\land$ 联结文字形成的公式，例如 $p\land\neg q\land r$。
- 简单析取式：由 $\lor$ 联结文字形成的公式，例如 $p\lor\neg q\lor r$。
- 单个文字同时属于简单合取式、简单析取式。$\neg\neg p$、$\neg(p\land q)$ 都不属于这两种形式，虽然可以进一步等值化简。
析取范式与合取范式的定义 #
- 析取范式（DNF）：若干简单合取式的析取，即“先合取，再析取”。
- 合取范式（CNF）：若干简单析取式的合取，即“先析取，再合取”。
其中，$\ell_{ij}$ 都是文字。允许某一层只有一项，所以单个简单合取式或简单析取式，都既是析取范式，也是合取范式。
例如，$(p\land\neg q)\lor r$ 是析取范式；$(p\lor r)\land(\neg q\lor r)$ 是合取范式。
简单析（合）取式的性质 #
- 简单析取式是重言式，当且仅当它同时包含某个命题变元及其否定，例如 $p\lor\neg p\lor q$。
- 简单合取式是矛盾式，当且仅当它同时包含某个命题变元及其否定，例如 $p\land\neg p\land q$。
- 对固定的变元序列 $q_1,\ldots,q_n$，若每个变元都出现，则非矛盾的简单合取式有唯一的成真指派，非永真的简单析取式有唯一的成假指派。若某个变元没有出现，它的值就不受限制，不能保证唯一。
例如，关于 $(q_1,q_2,q_3)$：
$$ \begin{aligned} \neg q_1\land q_2\land q_3 &\quad\text{唯一成真指派为 }(0,1,1),\\ \neg q_1\lor q_2\lor q_3 &\quad\text{唯一成假指派为 }(1,0,0). \end{aligned} $$合取要求各部分同时真，析取只要求某一部分真。因此：
| 公式结构 | 成真指派集 | 成假指派集 |
|---|---|---|
| $\alpha_1\land\cdots\land\alpha_n$ | 各部分成真指派集的交集 | 各部分成假指派集的并集 |
| $\alpha_1\lor\cdots\lor\alpha_n$ | 各部分成真指派集的并集 | 各部分成假指派集的交集 |
范式的存在性 #
每个命题公式都等值于一个析取范式，也等值于一个合取范式。
证明思路：为每个成真指派构造一个只在该指派下为真的简单合取式，再把它们析取起来，便能得到与原公式相同的成真指派集。合取范式则可以从成假指派出发构造，也可以先求否定公式的析取范式，再用德摩根律转换。
范式的求法 #
真值表法 #
先固定变元序列，列出公式的真值表。
- 求析取范式：选取所有成真行，每行写一个简单合取式；值为 $1$ 的变元直接写，值为 $0$ 的变元加否定；最后把各项用 $\lor$ 联结。
- 求合取范式：选取所有成假行，每行写一个简单析取式；值为 $0$ 的变元直接写，值为 $1$ 的变元加否定；最后把各项用 $\land$ 联结。
例如，对于指派 $(q_1,q_2,q_3)=(1,0,1)$：
$$ \begin{aligned} \text{对应的简单合取式：}&\quad q_1\land\neg q_2\land q_3,\\ \text{对应的简单析取式：}&\quad\neg q_1\lor q_2\lor\neg q_3. \end{aligned} $$前者只在该行取真，后者只在该行取假。记忆：析取范式找真行，合取范式找假行。
若没有成真行，公式为矛盾式，可用 $p\land\neg p$ 表示其析取范式；若没有成假行，公式为重言式，可用 $p\lor\neg p$ 表示其合取范式。
等值演算法 #
- 消去 $\to$、$\leftrightarrow$，只保留 $\neg,\land,\lor$。
- 用德摩根律将否定内移，并消去双重否定，使否定只作用于命题变元。
- 用分配律整理结构：求析取范式时，把 $\land$ 对 $\lor$ 分配；求合取范式时，把 $\lor$ 对 $\land$ 分配。
- 用幂等律、吸收律等适当化简。
例题：求两种范式 #
求 $\alpha=((\neg p_1)\lor p_2)\to p_3$ 的析取范式与合取范式。
$$ \begin{aligned} \alpha &\Leftrightarrow\neg(\neg p_1\lor p_2)\lor p_3 &&\text{（蕴含等值式）}\\ &\Leftrightarrow(\neg\neg p_1\land\neg p_2)\lor p_3 &&\text{（德摩根律）}\\ &\Leftrightarrow(p_1\land\neg p_2)\lor p_3 &&\text{（双重否定律，已是析取范式）}\\ &\Leftrightarrow(p_1\lor p_3)\land(\neg p_2\lor p_3) &&\text{（分配律，已是合取范式）}. \end{aligned} $$普通范式与主范式 #
- 普通范式不唯一。同一个公式可以有不同的析取范式或合取范式，通常希望找到较简洁的形式。
- 固定变元集合后，要求每个简单合取项或简单析取项都包含全部变元，每个变元恰出现一次，并删除重复项，就得到主析取范式或主合取范式。它们在忽略项的顺序、括号等书写差异后唯一。
- 真值表法逐行构造的，就是对应的主范式：每个成真行对应一个极小项（简单合取项），每个成假行对应一个极大项（简单析取项）。
- 对于矛盾式的主析取范式、重言式的主合取范式，通常约定空析取为 $0$、空合取为 $1$。
利用范式证明联结词完全集 #
只含 $\neg,\land,\lor$ 的公式称为限制性公式。
任意 $n$ 元真值函数（$n\ge1$）都能由这种公式表示：
- 若函数恒为 $0$，用 $p_1\land\neg p_1$ 即可表示。
- 否则，列出函数值为 $1$ 的所有指派，为每行构造一个简单合取式，再把它们析取起来。
因此：
$$ \boxed{\{\neg,\land,\lor\}\text{ 是联结词的完全集。}} $$这个证明与真值表法求析取范式的构造过程相同。
可靠性、和谐性与完备性 #
语法与语义的联系 #
- 语法：研究公式、公理、推理规则和形式证明，核心问题是 $\vdash_P\alpha$ 是否成立。
- 语义：通过指派解释公式的真假，核心问题是公式是否永真，记为 $\vDash\alpha$。
可靠性与完备性讨论的是这两者能否对应；和谐性讨论的是形式系统本身是否会证明出矛盾。
| 性质 | 表述 | 理解 |
|---|---|---|
| 可靠性 | $\vdash_P\alpha\ \Longrightarrow\ \vDash\alpha$ | 形式上能证明的，语义上一定永真 |
| 完备性（完全性） | $\vDash\alpha\ \Longrightarrow\ \vdash_P\alpha$ | 语义上永真的，形式上一定能证明 |
| 和谐性（一致性） | 不存在 $\alpha$，使 $\vdash_P\alpha$ 与 $\vdash_P\neg\alpha$ 同时成立 | 系统不会同时证明一个公式和它的否定 |
这些是关于形式系统的元定理，不是 $P$ 内部的公式或推理规则。
可靠性 #
定理：$P$ 的内定理都是重言式。
$$ \boxed{\vdash_P\alpha\ \Longrightarrow\ \vDash\alpha.} $$证明思路：对证明序列的长度归纳。
- 公理都是重言式。
- 分离规则保持永真性：若 $\alpha$ 与 $\alpha\to\beta$ 都永真，则 $\beta$ 也永真。
- 因此，任何无前提证明序列中的每一行都永真，最后的结论也永真。
可靠性也给出了判断不可证的一种方法：只要找出使 $\alpha$ 为假的指派，就能断定 $\nvdash_P\alpha$。
和谐性 #
定理：$P$ 中不存在公式 $\alpha$，使 $\alpha$ 和 $\neg\alpha$ 都是内定理。
证明思路：若两者都可证，由可靠性知两者都永真。但对任意指派 $\sigma$，有：
$$ (\neg\alpha)^\sigma=1-\alpha^\sigma, $$因此两者不可能同时为真，矛盾。所以 $P$ 的可靠性蕴含其和谐性。
- 推论：$P$ 中至少有一个公式不是内定理。
- 和谐性不要求 $\alpha$ 与 $\neg\alpha$ 中必有一个可证。例如，$p$ 和 $\neg p$ 都不是重言式，由可靠性可知两者都不是内定理。
完备性 #
定理：$P$ 中的每个重言式都是内定理。
$$ \boxed{\vDash\alpha\ \Longrightarrow\ \vdash_P\alpha.} $$关键引理：把一个指派写成前提 #
设公式 $\beta$ 中的命题变元都在 $v_1,\ldots,v_n$ 中。对于一个指派 $\sigma$，取：
$$ \ell_i= \begin{cases} v_i,&\sigma(v_i)=1,\\ \neg v_i,&\sigma(v_i)=0. \end{cases} $$记 $\Delta_\sigma=\{\ell_1,\ldots,\ell_n\}$，即把这个指派规定的真假情况转成文字前提，则：
$$ \begin{aligned} \beta^\sigma=1&\quad\Longrightarrow\quad\Delta_\sigma\vdash_P\beta,\\ \beta^\sigma=0&\quad\Longrightarrow\quad\Delta_\sigma\vdash_P\neg\beta. \end{aligned} $$例如，指派 $\sigma(p)=1,\sigma(q)=0$ 对应前提 $\{p,\neg q\}$。因为 $(p\to q)^\sigma=0$，引理保证 $p,\neg q\vdash_P\neg(p\to q)$。
引理可对公式结构归纳证明。核心是：在给定指派所对应的前提下，形式推理能重现真值计算的结果。
完备性证明的主线 #
若 $\beta$ 是重言式，则对所有指派 $\sigma$，都有 $\Delta_\sigma\vdash_P\beta$。接着把这些指派前提逐个消去。
消去一个变元 $v$ 时，固定其余文字前提 $\Gamma$，两个分支都能证明 $\beta$：
$$ \Gamma,v\vdash_P\beta, \qquad \Gamma,\neg v\vdash_P\beta. $$由演绎定理得到：
$$ \Gamma\vdash_P v\to\beta, \qquad \Gamma\vdash_P\neg v\to\beta. $$再使用已证的分类讨论内定理：
$$ \vdash_P(v\to\beta)\to((\neg v\to\beta)\to\beta), $$连续两次分离便得到 $\Gamma\vdash_P\beta$。这样就消去了关于 $v$ 的假设。对所有变元重复这一过程，最终得到 $\vdash_P\beta$。
整个证明是在做穷尽的分类讨论：每种指派下都能证明，再合并分支，最终不依赖任何指派前提。
结论与可判定性 #
结合可靠性与完备性：
$$ \boxed{\vdash_P\alpha\quad\Longleftrightarrow\quad\vDash\alpha.} $$由于 $N$ 与 $P$ 的可证性等价，$N$ 的内定理也恰好是重言式。
- 命题演算的内定理问题是可判定的：一个公式只有有限个命题变元，列出全部 $2^n$ 个指派，检查是否永真，就能在有限步内判断它是否可证。
- “完备”不表示每个公式或其否定总有一个可证；它表示所有重言式都可证。比如 $p$ 和 $\neg p$ 都不是永真的。
- 证明搜索中暂时没有找到证明，不等于已经证明不可证；反例指派则可以通过可靠性说明不可证。
有限前提的情形 #
对于有限前提集 $\Gamma=\{\gamma_1,\ldots,\gamma_n\}$，可靠性与完备性也给出：
$$ \boxed{\Gamma\vdash_P\alpha\quad\Longleftrightarrow\quad\Gamma\vDash\alpha.} $$其中，$\Gamma\vDash\alpha$ 表示：任意使 $\Gamma$ 中所有前提都为真的指派，也使 $\alpha$ 为真。
这一结论可以通过演绎定理，将前提逐个移入公式，再对蕴含链使用无前提的可靠性与完备性得到。因此，有限前提的推理有效，当且仅当它在 $P$ 中可证。