数理逻辑基础

第一章 命题演算

命题演算是最简单、最基本的形式系统，主要用来表示较为简单的逻辑推理的一种数学模型. 其简单性表现为：当它把复合命题分解成简单命题后，就把简单命题视为最小考察对象，不再继续对简单命题进行分解.

1.1 命题与命题联结词

1.1.1 命题

定义1.1 命题

具有确切真值的陈述句（或断言）称为命题（proposition）.

命题的取值称为真值. 真值只有“真”和“假”两种，分别用 $\mathrm{T}$$\mathrm{T}$（$1$$1$）和 $\mathrm{F}$$\mathrm{F}$（$0$$0$）表示.

命题的真值非真即假，只有两种取值，这样的系统称为二值逻辑系统.

注意：

• 命题一定是通过陈述句来表达；反之，并非一切的陈述句都是命题.

• 命题的真值有时可明确给出，有时还需要依靠环境条件、实际情况、时间等才能确定其真值，但其真值一定是唯一确定的.

命题的类型：

• 若一个命题已不能分解成更简单的命题，则该命题叫原子命题或本原命题或简单命题（simple proposition）；

• 若一个命题可以分解为简单命题，而且这些简单命题之间是通过关联词和标点符号复合而构成的，则该命题叫复合命题（compound proposition）.

命题通常用大写英文字母（可带下标）来表示.

1.1.2 命题联结词

命题通常可以通过一些联结词复合而构成新的命题，这些联结词被称为逻辑联结词. 在命题演算中，这些联结词可以看作运算符，因此也叫作逻辑运算符.

定义1.2 否定联结词

设 $P$$P$ 是任一命题，复合命题”非 $P$$P$ “（或”$P$$P$ 的否定“）称为 $P$$P$ 的否定式（negation），记作 $\mathrm{\neg }P$$\lnot P$，”$\mathrm{\neg }$$\lnot$“ 称为否定联结词.

$\mathrm{\neg }P$$\lnot P$ 为真当且仅当 $P$$P$ 为假.

定义1.3 合取联结词

设 $P$$P$、$Q$$Q$ 是任意两个命题，复合命题 ”$P$$P$ 并且 $Q$$Q$ “（或“ $P$$P$ 与 $Q$$Q$ ”）称为 $P$$P$ 与 $Q$$Q$ 的合取式（conjunction），记作 $P\wedge Q$$P\land Q$，“$\wedge$$\land$” 称为合取联结词.

$P\wedge Q$$P\land Q$ 为真当且仅当 $P$$P$，$Q$$Q$ 同为真；$P\wedge Q$$P\land Q$ 为假当且仅当 $P$$P$ 与 $Q$$Q$ 二者至少有一为假.

定义1.4 析取联结词

设 $P$$P$、$Q$$Q$ 是任意两个命题，复合命题“ $P$$P$ 或 $Q$$Q$ ” 称为 $P$$P$ 与 $Q$$Q$ 的析取式（disjunction），记作 $P\vee Q$$P\lor Q$，“$\vee$$\lor$” 称为析取联结词.

$P\vee Q$$P\lor Q$ 为真当且仅当 $P$$P$，$Q$$Q$ 至少一个为真.

 

这里的“或”是“相容或”（“可兼或”）.

定义1.5 蕴涵联结词

设 $P$$P$、$Q$$Q$ 是任意两个命题，复合命题“如果 $P$$P$ 那么 $Q$$Q$ ” 称为 $P$$P$ 与 $Q$$Q$ 的蕴涵式（implication），记作 $P\to Q$$P\to Q$，“$\to$$\to$” 称为蕴涵联结词，$P$$P$ 称为蕴涵式的前提、假设或前件，$Q$$Q$ 称为结论或后件.

$P\to Q$$P\to Q$ 为真当且仅当 $P$$P$ 为真 $Q$$Q$ 为假.

 

蕴涵式 $P\to Q$$P\to Q$ 可以用多种方式陈述：

• “若 $P$$P$，则 $Q$$Q$ ”；

• “ $P$$P$ 是 $Q$$Q$ 的充分条件”；

• “ $Q$$Q$ 是 $P$$P$ 的必要条件”；

• “ $Q$$Q$ 每当 $P$$P$ ”；

• “ $P$$P$ 仅当 $Q$$Q$ ”.

给定命题 $P\to Q$$P\to Q$，

• $Q\to P$$Q\to P$ 是其逆命题；

• $\mathrm{\neg }P\to \mathrm{\neg }Q$$\lnot P\to\lnot Q$ 是其反命题；

• $\mathrm{\neg }Q\to \mathrm{\neg }P$$\lnot Q\to\lnot P$ 是其逆反命题.

定义1.6 等价联结词

设 $P$$P$、$Q$$Q$ 是任意两个命题，复合命题“ $P$$P$ 当且仅当 $Q$$Q$ ” 称为 $P$$P$ 与 $Q$$Q$ 的等价式（equivalence），记作 $P\leftrightarrow Q$$P\leftrightarrow Q$，“$\leftrightarrow$$\leftrightarrow$” 称为等价联结词.

$P\leftrightarrow Q$$P\leftrightarrow Q$ 为真当且仅当 $P$$P$、$Q$$Q$ 同为真假.

一般约定：

• 运算符（联结词）结合力强弱顺序为

  $$\mathrm{\neg },\wedge ,\vee ,\to ,\leftrightarrow ,$$

  凡符合此顺序的，括号可省略；

• 相同的运算符，从左到右次序计算时，括号可省去；

• 最外层括号可省.

1.2 公式的解释与真值表

1.2.1 命题公式

定义1.7

一个特定的命题是一个常值命题（constant proposition），它不是具有值“ $\mathrm{T}$$\mathrm T$ ”（“$0$$0$”）就是具有值“ $\mathrm{F}$$\mathrm F$ ”（“$0$$0$”）；

一个任意的没有赋予具体内容的原子命题是一个变量命题，常称它为命题变量（命题变元、命题变项）（proposition variable），命题变量无具体的真值，它的值域是集合 $\{\mathrm{T},\mathrm{F}\}$$\{\mathrm T,\mathrm F\}$ （或 $\{1,0\}$$\{1,\ 0\}$）.

原子命题在不指派真值时称为命题变元，而复合命题由原子命题和联结词构成，可以看作是命题变元的函数，且该函数的值仍为“真”或“假”，可以称为真值函数（true value function）或命题公式（propositional formula）.

不是原子命题和联结词的任意组合都可以为命题公式. 我们用递归的方法来定义命题公式.

定义1.8 命题公式（合式公式、形式命题）

1. 命题变元本身是一个公式；

2. 如果 $P$$P$ 是公式，则 $\mathrm{\neg }P$$\lnot P$ 也是公式；

3. 如果 $P$$P$、$Q$$Q$ 是公式，则 $P\wedge Q$$P\land Q$、$P\vee Q$$P\lor Q$、$P\to Q$$P\to Q$、$P\leftrightarrow Q$$P\leftrightarrow Q$ 也是公式；

4. 命题公式是仅由有限步使用规则 1 ~ 3 后产生的结果，公式常用符号 $G$、$H$$H$ 等表示.

注意：

• 如果 $G$ 是含有 $n$$n$ 个命题变元 $P_1,P_2,\cdots ,P_n$$P_1,\ P_2,\cdots,\ P_n$ 的公式，则 $G$ 通常记为 $G(P_1,P_2,\cdots ,P_n)$$G(P_1,\ P_2,\cdots,\ P_n)$ 或简记为 $G$.

• 原子命题变元是最简单的公式，也叫原子公式；

• 合式公式没有真值，只有对其变元进行指派后才有真值；

• 合式公式无限多.

1.2.2 公式的解释与真值表

公式本身没有真值，只有在对其所有命题变元指定真值后才变成一个具有真值的命题.

定义1.9 公式的解释

设 $P_1,P_2,\cdots ,P_n$$P_1,\ P_2,\cdots,\ P_n$ 是出现在公式 $G$ 中的所有命题变元，指定 $P_1,P_2,\cdots ,P_n$$P_1,\ P_2,\cdots,\ P_n$ 一组真值，则这组真值称为 $G$ 的一个解释（explanation）或真值指派，记作 $I$$I$.

一般来说，若有 $n$$n$ 个命题变元，则应有 $2^n$$2^n$ 个不同的解释.

定义1.10 公式的真值表

公式 $G$ 在其所有可能的解释下所取真值的表，称作 $G$ 的真值表（truth）.

1.2.3 一些特殊的公式

1. 重言式

定义1.11

• 公式 $G$ 称为永真公式（重言式），如果在它的所有解释下都为“真”，记作 $\models G$$\vDash G$；

• 公式 $G$ 称为可满足的，如果它不是永假的；

• 公式 $G$ 称为永假公式（矛盾式），如果在它的所有解释下都为“假”，有时也称为不可满足公式.

注意：

• 重言式的否定是矛盾式，矛盾式的否定是重言式，因此只需研究其中一种情形；

• 重言式的合取、析取、蕴涵、等价等都是重言式；

• 重言式中有许多非常有用的恒等式和永真蕴涵式；

• 命题的永真（永假）性是可判定的，其判定方法有真值表法和公式推演法.

2. 恒等式

定义1.12

公式 $G$、$H$$H$，如果在其任意解释下，其真值相同，则称 $G$ 是 $H$$H$ 的等价式（equivalent）或称 $G$ 恒等于 $H$$H$，记作 $G\iff H$$G\Leftrightarrow H$ 或 $\models G\leftrightarrow H$$\vDash G\leftrightarrow H$.

定理1.1

对于公式 $G$、$H$$H$，$G\iff H$$G\Leftrightarrow H$ 的充分必要条件是公式 $G\leftrightarrow H$$G\leftrightarrow H$ 是重言式.

常用逻辑恒等式：

• E1 双重否定律：

  $$\mathrm{\neg }\mathrm{\neg }P\iff P；$$

• E2 $\vee$$\lor$ 的幂等律：

  $$P\vee P\iff P;$$

• E3 $\wedge$$\land$ 的幂等律：

  $$P\wedge P\iff P;$$

• E4 $\vee$$\lor$ 的交换律：

  $$P\vee Q\iff Q\vee P;$$

• E5 $\wedge$$\land$ 的交换律：

  $$P\wedge Q\iff Q\wedge P;$$

• E6 $\vee$$\lor$ 的结合律：

  $$(P\vee Q)\vee R\iff P\vee (Q\vee R);$$

• E7 $\wedge$$\land$ 的结合律：

  $$(P\wedge Q)\wedge R\iff P\wedge (Q\wedge R);$$

• E8 $\wedge$$\land$ 在 $\vee$$\lor$ 上的分配律：

  $$P\wedge (Q\vee R)\iff (P\wedge Q)\vee (P\wedge R);$$

• E9 $\vee$$\lor$ 在 $\wedge$$\land$ 上的分配律：

  $$P\vee (Q\wedge R)\iff (P\vee Q)\wedge (P\vee R);$$

• E10、E11 德·摩根定律（De Morgan's Law）:

  $$\begin{array}{rl}\mathrm{\neg }(P\vee Q)& \iff \mathrm{\neg }P\wedge \mathrm{\neg }Q,\\ \\ \mathrm{\neg }(P\wedge Q)& \iff \mathrm{\neg }P\vee \mathrm{\neg }Q;\end{array}$$

• E12、E13 吸收律：

  $$\begin{array}{rl}P\vee (P\wedge Q)& \iff P,\\ \\ P\wedge (P\vee Q)& \iff P;\end{array}$$

• E14 蕴涵等值式：

  $$(P\to Q)\iff \mathrm{\neg }P\vee Q;$$

• E15 等价等值式：

  $$(P\leftrightarrow Q)\iff (P\to Q)\wedge (Q\to P);$$

• E16、E17 零律：

  $$\begin{array}{rl}P\vee \mathrm{T}& \iff \mathrm{T},\\ \\ P\wedge \mathrm{F}& \iff \mathrm{F};\end{array}$$

• E18、E19 幺律：

  $$\begin{array}{rl}P\vee \mathrm{F}& \iff P,\\ \\ P\wedge \mathrm{T}& \iff P;\end{array}$$

• E20 排中律：

  $$P\vee \mathrm{\neg }P\iff \mathrm{T};$$

• E21 矛盾律：

  $$P\wedge \mathrm{\neg }P\iff \mathrm{F};$$

• E22 等价否定等值式：

  $$(P\leftrightarrow Q)\iff (\mathrm{\neg }P\leftrightarrow \mathrm{\neg }Q);$$

• E23 归谬律：

  $$((P\to Q)\wedge (P\to \mathrm{\neg }Q))\iff \mathrm{\neg }P;$$

• E24 逆反律（假言异位）：

  $$(P\to Q)\iff \mathrm{\neg }Q\to \mathrm{\neg }P.$$

3. 永真蕴涵式

定义1.13

若 $A\to B$$A\to B$ 是一永真式，那么称其为永真蕴涵式，记为 $A\Rightarrow B$$A\Rightarrow B$，读作“$A$$A$ 永真蕴涵 $B$$B$”.

常用永真蕴涵式：

• I1 同一律

  $$P\Rightarrow P;$$

• I2

  $$P\Rightarrow P\vee Q;$$

• I3

  $$P\wedge Q\Rightarrow P;$$

• I4

  $$P\wedge (P\to Q)\Rightarrow Q;$$

• I5

  $$(P\to Q)\wedge \mathrm{\neg }Q\Rightarrow \mathrm{\neg }P;$$

• I6

  $$\mathrm{\neg }P\wedge (P\vee Q)\Rightarrow Q;$$

• I7

  $$(P\to Q)\wedge (Q\to R)\Rightarrow (P\to R);$$

• I8

  $$(P\to Q)\Rightarrow ((Q\to R)\to (P\to R));$$

• I9

  $$((P\to Q)\wedge (R\to S))\Rightarrow (P\wedge R\to Q\wedge S).$$

4. 恒等式和永真蕴涵式的两个性质

• 逻辑恒等（“$\iff$$\Leftrightarrow$”）和永真蕴涵（“$\Rightarrow$$\Rightarrow$”）都是可传递的；

• 若 $A\Rightarrow B$$A\Rightarrow B$，$B\Rightarrow C$$B\Rightarrow C$，则 $A\Rightarrow B\wedge C$$A\Rightarrow B\land C$.

1.2.4 代入规则和替换规则

定理1.2 代入定理

设 $G(P_1,\cdots ,P_n)$$G(P_1,\cdots,P_n)$ 是一个命题公式，其中 $P_1,\cdots ,P_n$$P_1,\cdots,P_n$ 是命题变元，$G_1(P_1,\cdots ,P_n)$$G_1(P_1,\cdots,P_n)$，$\cdots$$\cdots$，$G_n(P_1,\cdots ,P_n)$$G_n(P_1,\cdots,P_n)$ 为任意的命题公式，此时若 $G$ 是永真公式或永假公式，则用 $G_1$$G_1$ 取代 $P_1$$P_1$，$G_n$$G_n$ 取代 $P_n$$P_n$ 后得到的新命题公式

$$G(G_1,\cdots ,G_n)\iff G^{\prime }(P_1,\cdots ,P_n)$$

也是一个永真公式或永假公式.

定理1.3 替换定理

设 $G_1$$G_1$ 是 $G$ 的子公式，$H_1$$H_1$ 是任意的命题公式，在 $G$ 中凡出现 $G_1$$G_1$ 处都以 $H_1$$H_1$ 替换后得到新的命题公式 $H$$H$. 若 $G_1\iff H_1$$G_1\Leftrightarrow H_1$，则 $G\iff H$$G\Leftrightarrow H$.

1.2.5 对偶原理

定义1.4 对偶公式

设公式 $A$$A$ 中仅有联结词 $\wedge$$\land$，$\vee$$\lor$，$\mathrm{\neg }$$\lnot$. 在 $A$$A$ 中将 $\wedge$$\land$，$\vee$$\lor$，$\mathrm{T}$$\mathrm{T}$，$\mathrm{F}$$\mathrm{F}$ 分别换以 $\vee$$\lor$，$\wedge$$\land$，$\mathrm{F}$$\mathrm{F}$，$\mathrm{T}$$\mathrm{T}$ 得到公式 $A^{\ast }$$A^*$，则 $A^{\ast }$$A^*$ 称为 $A$$A$ 的对偶公式，$A$$A$ 与 $A^{\ast }$$A^*$ 互为对偶.

定理1.4

设 $A$$A$ 和 $A^{\ast }$$A^*$ 是对偶式，$P_1,P_2,\cdots ,P_n$$P_1,P_2,\cdots,P_n$ 是出现于 $A$$A$ 和 $A^{\ast }$$A^*$ 中所有命题变元，于是

$$\begin{array}{}\text{(1)}& \mathrm{\neg }A(P_1,P_2,\cdots ,P_n)=A^{\ast }(\mathrm{\neg }{P}_1,\mathrm{\neg }{P}_2,\cdots ,\mathrm{\neg }{P}_n).\end{array}$$

定理1.5 对偶原理

若 $A\iff B$$A\Leftrightarrow B$，且 $A$$A$，$B$$B$ 为命题变元 $P_1,P_2,\cdots ,P_n$$P_1,P_2,\cdots,P_n$ 及联结词 $\wedge ,\vee ,\mathrm{\neg }$$\land,\lor,\lnot$ 构成的公式，则 $A^{\ast }\iff B^{\ast }$$A^*\Leftrightarrow B^*$.

定理1.6

若 $A\Rightarrow B$$A\Rightarrow B$，且 $A$$A$，$B$$B$ 为命题变元 $P_1,P_2,\cdots ,P_n$$P_1,P_2,\cdots,P_n$ 及联结词 $\wedge ,\vee ,\mathrm{\neg }$$\land,\lor,\lnot$ 构成的公式，则 $B^{\ast }\iff A^{\ast }$$B^*\Leftrightarrow A^*$.

1.3 联结词的完备集

1.3.1 联结词的扩充

首先考虑一元运算.

最多只能定义 4 种运算，但除了否定之外，永假、永真、恒等作为运算意义不大，所以一般不再定义其它一元运算.

考虑两变元在一个二元运算作用下可能的真值表.

为了叙述方便，引进下面四个联结词.

这九个联结词（否定、合取、析取、蕴涵、等价、异或、蕴含否定、与非、或非）构成命题演算中的所有联结词.

1.3.2 与非、或非、异或的性质

与非的性质：

• $P\uparrow Q\iff Q\uparrow P$$P\uparrow Q\Leftrightarrow Q\uparrow P$；

• $P\uparrow P\iff \mathrm{\neg }P$$P\uparrow P\Leftrightarrow\lnot P$；

• $(P\uparrow Q)\uparrow (P\uparrow Q)\iff P\wedge Q$$(P\uparrow Q)\uparrow(P\uparrow Q)\Leftrightarrow P\land Q$；

• $(P\uparrow P)\uparrow (Q\uparrow Q)\iff P\vee Q$$(P\uparrow P)\uparrow(Q\uparrow Q)\Leftrightarrow P\lor Q$.

或非的性质：

• $P\downarrow Q\iff Q\downarrow P$$P\downarrow Q\Leftrightarrow Q\downarrow P$；

• $P\downarrow P\iff \mathrm{\neg }P$$P\downarrow P\Leftrightarrow\lnot P$；

• $(P\downarrow Q)\downarrow (P\downarrow Q)\iff P\vee Q$$(P\downarrow Q)\downarrow(P\downarrow Q)\Leftrightarrow P\lor Q$；

• $(P\downarrow P)\downarrow (Q\downarrow Q)\iff P\wedge Q$$(P\downarrow P)\downarrow(Q\downarrow Q)\Leftrightarrow P\land Q$.

异或的性质：

• $P\bar{\vee }Q\iff Q\bar{\vee }P$$P\overline{\lor}Q\Leftrightarrow Q\overline{\lor} P$；

• $P\bar{\vee }(Q\bar{\vee }R)\iff (P\bar{\vee }Q)\bar{\vee }R$$P\overline{\lor}(Q\overline{\lor}R)\Leftrightarrow(P\overline{\lor}Q)\overline{\lor}R$；

• $P\bar{\vee }P\iff \mathrm{F}$$P\overline{\lor}P\Leftrightarrow\mathrm{F}$；

• $\mathrm{F}\bar{\vee }P\iff P$$\mathrm{F}\overline{\lor}P\Leftrightarrow P$；

• $\mathrm{T}\bar{\vee }P\iff \mathrm{\neg }P$$\mathrm{T}\overline{\lor}P\Leftrightarrow \lnot P$.

1.3.3 全功能联结词

定义1.15

设 $S$$S$ 的联结词的集合.

1. 用 $S$$S$ 中的联结词表示的公式可以等价地表示任何命题公式，则称 $S$$S$ 是一个联结词完备集（或全功能集合）（adequate set of connectives）；

2. $S$$S$ 是一个联结词的完备集，且 $S$$S$ 中无冗余的联结词（即集合中不存在可以被其中的其它联结词所定义的联结词），则称 $S$$S$ 为极小联结词完备集.

• $\{\mathrm{\neg },\wedge \}$$\{\lnot,\land\}$、$\{\mathrm{\neg },\vee \}$$\{\lnot,\lor\}$、$\{\mathrm{\neg },\to \}$$\{\lnot,\to\}$、$\{\mathrm{\neg },\nrightarrow \}$$\{\lnot,\nrightarrow\}$、$\{\uparrow \}$$\{\uparrow\}$、$\{\downarrow \}$$\{\downarrow\}$ 都是极小完备集；

• $\{\wedge ,\vee ,\to ,\leftrightarrow \}$$\{\land,\lor,\to,\leftrightarrow\}$ 及其子集不是完备集；

• 实际应用中经常采取的联结词集合为 $\{\mathrm{\neg },\wedge ,\vee \}$$\{\lnot,\land,\lor\}$.

1.4 范式

1.4.1 范式

同一个命题有不同的表达形式，这样给命题演算带来了一定的困难. 为了使命题公式规范化，引入范式的概念.

定义1.16

• 命题变元或命题变元的否定称为文字；

• 有限个文字的析取式称为简单析取式（基本和），有限个文字的合取式称为简单合取式（基本积）；

• 由有限个简单合取式构成的析取式称为析取范式（disjunctive normal form），由有限个简单析取式构成的合取式称为合取范式（conjunctive normal form）.

性质：

• 一个文字既是一个析取范式又是一个合取范式；

• 一个析取范式为矛盾式当且仅当它的每个简单合取式是矛盾式；

• 一个合取范式为重言式当且仅当它的每个简单析取式是重言式.

定理1.7

任一命题公式都存在着与之等值的析取范式和合取范式.

---

证明：对于任一公式，可用下面的方法构造出与之等值的范式：

1. 利用等价公式

   $$A\leftrightarrow B\iff (A\to B)\wedge (B\to A),A\to B\iff \mathrm{\neg }A\vee B$$

   使公式中仅含联结词 $\mathrm{\neg }$$\lnot$、$\wedge$$\land$、$\vee$$\lor$；

2. 利用德·摩根定律

   $$\mathrm{\neg }(A\vee B)\iff \mathrm{\neg }A\wedge \mathrm{\neg }B,\mathrm{\neg }(A\wedge B)\iff \mathrm{\neg }A\vee \mathrm{\neg }B$$

   和双重否定律

   $$\mathrm{\neg }\mathrm{\neg }A=A$$

   将否定符 $\mathrm{\neg }$$\lnot$ 移到命题变元前，并去掉多余的否定符；

3. 利用分配律

   $$A\wedge (B\vee C)\iff (A\wedge B)\vee (A\wedge C),A\vee (B\wedge C)\iff (A\vee B)\wedge (A\vee C)$$

   将公式化成析取范式或合取范式，所得即与原公式等价.

1.4.2 主析取范式和主合取范式

范式虽然为命题公式提供了一种统一的表达形式，但这种表达形式却不是唯一的，这种不唯一的表达形式给研究问题带来了不便，因此有必要引进更为标准的范式.

定义1.17

• 包含 $A$$A$ 中所有命题变元或其否定一次仅一次的简单合取式称为极小项；

• 包含 $A$$A$ 中所有命题变元或其否定一次仅一次的简单析取式称为极大项；

• 由有限个极小项组成的析取范式称为主析取范式；

• 由有限个极大项组成的合取范式称为主合取范式.

1. 极小项和极大项的性质

一般来说，对于 $n$$n$ 个命题变元，应有 $2^n$$2^n$ 个不同的极小项和 $2^n$$2^n$ 个不同的极大项.

性质：

• 没有两个不同的极小项是等价的，且每个极小项只有一组真值指派使得该极小项的真值为真，因此可给极小项编码，使极小项为 $\mathrm{T}$$\mathrm{T}$ 的那组真值指派为对应的极小项编码；

• 没有两个不同的极大项是等价的，且每个极大项只有一组真值指派使得该极大项的真值为假，因此可给极小项编码，使极小项为 $\mathrm{F}$$\mathrm{F}$ 的那组真值指派为对应的极大项编码.

  $P$$P$	$Q$$Q$	$R$$R$	极小项	极大项
  0	0	0	$m_0=\mathrm{\neg }P\wedge \mathrm{\neg }Q\wedge \mathrm{\neg }R$$m_0=\lnot P\land\lnot Q\land\lnot R$	$M_0=P\vee Q\vee R$$M_0=P\lor Q\lor R$
  0	0	1	$m_1=\mathrm{\neg }P\wedge \mathrm{\neg }Q\wedge R$$m_1=\lnot P\land\lnot Q\land R$	$M_1=P\vee Q\vee \mathrm{\neg }R$$M_1=P\lor Q\lor\lnot R$
  0	1	0	$m_2=\mathrm{\neg }P\wedge Q\wedge \mathrm{\neg }R$$m_2=\lnot P\land Q\land\lnot R$	$M_2=P\vee \mathrm{\neg }Q\vee R$$M_2=P\lor\lnot Q\lor R$
  0	1	1	$m_3=\mathrm{\neg }P\wedge Q\wedge R$$m_3=\lnot P\land Q\land R$	$M_3=P\vee \mathrm{\neg }Q\vee \mathrm{\neg }R$$M_3=P\lor\lnot Q\lor\lnot R$
  1	0	0	$m_4=P\wedge \mathrm{\neg }Q\wedge \mathrm{\neg }R$$m_4=P\land\lnot Q\land\lnot R$	$M_4=\mathrm{\neg }P\vee Q\vee R$$M_4=\lnot P\lor Q\lor R$
  1	0	1	$m_5=P\wedge \mathrm{\neg }Q\wedge R$$m_5=P\land\lnot Q\land R$	$M_5=\mathrm{\neg }P\vee Q\vee \mathrm{\neg }R$$M_5=\lnot P\lor Q\lor\lnot R$
  1	1	0	$m_6=P\wedge Q\wedge \mathrm{\neg }R$$m_6=P\land Q\land\lnot R$	$M_6=\mathrm{\neg }P\vee \mathrm{\neg }Q\vee R$$M_6=\lnot P\lor\lnot Q\lor R$
  1	1	1	$m_7=P\wedge Q\wedge R$$m_7=P\land Q\land R$	$M_7=\mathrm{\neg }P\vee \mathrm{\neg }Q\vee \mathrm{\neg }R$$M_7=\lnot P\lor\lnot Q\lor\lnot R$

• 任意两极小项的合取必假，任意两极大项的析取必真，

  $$m_i\wedge m_j\iff \mathrm{F},M_i\vee M_j\iff \mathrm{T}(i,j\in [0,2^n-1],i\ne j);$$

  极大项的否定是极小项，极小项的否定是极大项，

  $$m_i\iff \mathrm{\neg }{M}_i,M_i\iff \mathrm{\neg }{m}_i.$$

• 所有极小项的析取为永真公式，所有极大项的合取为永假公式，即

  $$\underset{i=0}{\overset{2^n-1}{\bigvee }}{m}_i=\mathrm{T},\underset{i=0}{\overset{2^n-1}{\bigwedge }}{M}_i=\mathrm{F}.$$

2. 主析取范式和主合取范式的存在性和唯一性

定理1.8

任何命题公式的主析取范式和主合取范式存在且唯一，即任何命题公式有且仅有一个与之等价的主析取范式和主合取范式.

---

求主析取范式和主合取范式的方法：

• 真值表技术：

  

• 公式转换法：

  

  在公式中的命题变元较少时，利用真值表技术更为简单；当命题变元较多时，一般采用公式转换法.

3. 主析取范式和主合取范式之间的转换

(1) 已知公式 $G$ 的主析取范式，求公式 $G$ 的主合取范式：

• 求 $\mathrm{\neg }G$$\lnot G$ 的主析取范式，即 $G$ 的主析取范式中没有出现过的极小项的析取；

• $G\iff \mathrm{\neg }(\mathrm{\neg }G)$$G\Leftrightarrow\lnot(\lnot G)$ 即是 $G$ 的主合取范式.

即，若

为 $G$ 的主析取范式，则

为 $\mathrm{\neg }G$$\lnot G$ 的主析取范式，其中 $m_{j_i^{\prime }}、(i=1,2,\cdots ,2^n-k)$$m_{j_i'}、 (i=1,2,\cdots,2^n-k)$ 是 $m_i(i=0,1,\cdots ,2^n-1)$$m_i\ (i=0,1,\cdots,2^n-1)$ 中去掉 $m_{j_i}(i=1,\cdots ,k)$$m_{j_i}\ (i=1,\cdots,k)$ 后剩下的极小项，则

(2) 已知公式 $G$ 的主合取范式，求公式 $G$ 的主析取范式：

• 求 $\mathrm{\neg }G$$\lnot G$ 的主合取范式，即 $G$ 的主合取范式中没有出现过的极大项的合取；

• $G\iff \mathrm{\neg }(\mathrm{\neg }G)$$G\Leftrightarrow\lnot(\lnot G)$ 即是 $G$ 的主析取范式.

即，若

为 $G$ 的主合取范式，则

为 $\mathrm{\neg }G$$\lnot G$ 的主合取范式，其中 $M_{j_i^{\prime }}、(i=1,2,\cdots ,2^n-k)$$M_{j_i'}、 (i=1,2,\cdots,2^n-k)$ 是 $M_i(i=0,1,\cdots ,2^n-1)$$M_i\ (i=0,1,\cdots,2^n-1)$ 中去掉 $M_{j_i}(i=1,\cdots ,k)$$M_{j_i}\ (i=1,\cdots,k)$ 后剩下的极大项，则

4. 主析取范式和主合取范式的性质

性质：

• 命题公式是永真公式 $⟺$$\iff$ 它的主析取范式包含所有极小项.

  此时主合取范式不含有任何极大项，为空，记 $1$$1$ 或 $\mathrm{T}$$\mathrm{T}$；

• 命题公式是永假公式 $⟺$$\iff$ 它的主合取范式包含所有极小项.

  此时主析取范式不含有任何极小项，为空，记 $0$$0$ 或 $\mathrm{F}$$\mathrm F$；

• 两个命题公式 $A$$A$、$B$$B$，则

  $$A\iff B⟺A\text{与}B\text{有}\text{相}\text{同}\text{的}\text{真}\text{值}\text{表}⟺A\text{与}B\text{有}\text{相}\text{同}\text{的}\text{主}\text{析}\text{取}\text{范}\text{式}(\text{主}\text{合}\text{取}\text{范}\text{式}).$$

  换句话说，真值表和主范式是描述命题公式标准形式的两种不同的等价形式.

5. 主范式的应用

1. 求公式的成真或成假赋值.

2. 判定问题：根据主范式的定义和性质，判定含 $n$$n$ 个命题变元的公式，其关键是先求出给定公式的主范式 $A$$A$，其次按下列条件判定之：

   • 若 $A\iff \mathrm{T}$$A \lrArr \mathrm T$，或 $A$$A$ 可化为与其等价的含 $2^n$$2^n$ 个极小项的主析取范式，则 $A$$A$ 为永真式；

   • 若 $A\iff \mathrm{F}$$A \lrArr \mathrm F$，或 $A$$A$ 可化为与其等价的含 $2^n$$2^n$ 个极大项的主合取范式，则 $A$$A$ 为永假式；

   • 若 $A$$A$ 不与 $\mathrm{T}$$\mathrm T$ 或 $\mathrm{F}$$\mathrm F$ 等价，且又不含 $2^n$$2^n$ 个极小项或极大项，则 $A$$A$ 为可满足的.

3. 证明等价性：由于任何一公式的主范式是唯一的，所以求给定两公式的主范式，若主范式相同，则给定两公式是等价的.

4. 解决实际问题.

1.5 命题演算的推理理论

1.5.1 推理的基本概念和推理形式

推理也称论证，它是指从前提出发推出结论的思维过程：前提是已知命题公式集合，结论是从前提出发应用推理规则推出的命题形式.

定义1.18

设 $G_1,G_2,\cdots ,G_n,H$$G_1,G_2,\cdots,G_n,H$ 是命题公式，若对于 $G_1,G_2\cdots ,G_n,H$$G_1,G_2\cdots,G_n,H$ 中出现的命题变元的任意一组赋值，或者 $G_1\wedge G_2\wedge \cdots \wedge G_n$$G_1\land G_2\land\cdots\land G_n$ 为假，或者当 $G_1\wedge G_2\wedge \cdots \wedge G_n$$G_1\land G_2\land\cdots\land G_n$ 为真时 $H$$H$ 也为真，则称 $H$$H$ 是 $G_1,G_2,\cdots ,G_n$$G_1,G_2,\cdots,G_n$ 的有效结论（efficacious conclusion）或逻辑结果（logic conclusion），$G_1,G_2,\cdots ,G_n$$G_1,G_2,\cdots,G_n$ 为一组前提（premise）. 记 $\{G_1,\cdots ,G_n\}$$\{G_1,\cdots,G_n\}$ 推理 $H$$H$ 为 $\{G_1,\cdots ,G_n\}⊢H$$\{G_1,\cdots,G_n\}\vdash H$，若推理有效或正确，则记为 $\{G_1,\cdots ,G_n\}\models H$$\{G_1,\cdots,G_n\}\vDash H$.

定理1.19

命题公式 $G_1,G_2,\cdots ,G_n$$G_1,G_2,\cdots,G_n$ 推出结论 $H$$H$ 的推理正确或公式 $H$$H$ 是前提条件 $\{G_1,G_2,\cdots ,G_n\}$$\{G_1,G_2,\cdots,G_n\}$ 的逻辑结果，当且仅当 $(G_1\wedge G_2\wedge \cdots \wedge G_n)\to H$$(G_1\land G_2\land\cdots\land G_n)\to H$ 为重言式.

由 $\{G_1,G_2,\cdots ,G_n\}$$\{G_1,G_2,\cdots,G_n\}$ 推理 $H$$H$ 用蕴涵式表示为 $(G_1\wedge G_2\wedge \cdots \wedge G_n)\to H$$(G_1\land G_2\land\cdots\land G_n)\to H$；

由 $\{G_1,G_2,\cdots ,G_n\}$$\{G_1,G_2,\cdots,G_n\}$ 正确推理出 $H$$H$ 用蕴涵式表示为 $G_1\wedge G_2\wedge \cdots \wedge G_n\Rightarrow H$$G_1\land G_2\land\cdots\land G_n\Rightarrow H$.

推理的有效性判断，即判断推理是否正确，也就是判断 $(G_1\wedge G_2\wedge \cdots \wedge G_n)\to H$$(G_1\land G_2\land\cdots\land G_n)\to H$ 是否为重言式.

1.5.2 判断结论有效的方法

1. 真值表法

2. 等值演算法

直接用等值演算来判断推理的形式结构是否是重言式.

3.主析取范式法

将推理的形式结构转化为主析取范式，但仍判断其是否为重言式.

以上方法，当形式结构比较复杂，特别是所含的命题变元较多时，一般很不方便.

1.5.3 构造证明法

构造证明法是依据一些公认的推理规则，从前提出发，推导结论. 它可以看作是公式的序列，其中每个公式都是按照事先规定的规则得到的，且可将所用的规则在公式后写明，该系列最后一个公式是所要证明的结论.

1. 推理规则

• ① 前提引入规则：在推理的任何步骤上都可以引入前提；

• ② 结论引入规则：在推理的任何步骤上所得到的的结论都可以作为后续证明的前提；

• ③ 置换规则：在推理的任何步骤上，命题公式的子公式都可以用与之等价的公式置换，得到公式序列中又一个公式.

2. 推理定理

一些重要的永真蕴涵式：

1. （附加律）$A\Rightarrow (A\vee B)$$A\Rightarrow (A\lor B)$；

2. （化简律）$A\wedge B\Rightarrow A$$A\land B\Rightarrow A$；

3. （假言推理）$(A\to B)\wedge A\Rightarrow B$$(A\to B)\land A\Rightarrow B$；

4. （拒取式）$(A\to B)\wedge \mathrm{\neg }B\Rightarrow \mathrm{\neg }A$$(A\to B)\land \lnot B\Rightarrow \lnot A$；

5. （析取三段论）$(A\vee B)\wedge \mathrm{\neg }B\Rightarrow A$$(A\lor B)\land\lnot B\Rightarrow A$；

6. （假言三段论）$(A\to B)\wedge (B\to C)\Rightarrow A\to C$$(A\to B)\land(B\to C)\Rightarrow A\to C$；

7. （等价三段论）$(A\leftrightarrow B)\wedge (B\leftrightarrow C)\Rightarrow A\leftrightarrow C$$(A\harr B)\land(B\harr C)\Rightarrow A\harr C$；

8. （构造性二难）$(A\to B)\wedge (C\to D)\wedge (A\vee C)\Rightarrow (B\vee D)$$(A\to B)\land(C\to D)\land(A\lor C)\Rightarrow(B\lor D)$，

   （构造性二难，特殊形式）$(A\to B)\wedge (\mathrm{\neg }A\to B)\wedge (A\vee \mathrm{\neg }A)\Rightarrow B$$(A\to B)\land(\lnot A\to B)\land(A\lor\lnot A)\Rightarrow B$；

9. （破坏性二难）$(A\to B)\wedge (C\to D)\wedge (\mathrm{\neg }B\vee \mathrm{\neg }D)\Rightarrow (\mathrm{\neg }A\vee \mathrm{\neg }C)$$(A\to B)\land(C\to D)\land(\lnot B\lor\lnot D)\Rightarrow(\lnot A\lor\lnot C)$.

由这 9 个定律中的 8 个可以得到 8 个推理规则：

• ④ 附加规则：$A\models (A\vee B)$$A\vDash(A\lor B)$；

• ⑤ 化简规则：$(A\wedge B)\models A$$(A\land B)\vDash A$；

• ⑥ 假言推理规则：$(A\to B),A\models B$$(A\to B),A\vDash B$；

• ⑦ 拒取式规则：$(A\to B),\mathrm{\neg }B\models \mathrm{\neg }A$$(A\to B),\lnot B\vDash\lnot A$；

• ⑧ 假言三段论规则：$(A\to B),(B\to C)\models (A\to C)$$(A\to B),(B\to C)\vDash(A\to C)$；

• ⑨ 析取三段论规则：$(A\vee B),\mathrm{\neg }B\models A$$(A\lor B),\lnot B\vDash A$；

• ⑩ 构造性二难规则：$(A\to B),(C\to D),(A\vee C)\models (B\vee D)$$(A\to B),(C\to D),(A\lor C)\vDash(B\lor D)$；

• ⑪ 破坏性二难规则：$(A\to B),(C\to D),(\mathrm{\neg }B\vee \mathrm{\neg }D)\models (\mathrm{\neg }A\vee \mathrm{\neg }C)$$(A\to B),(C\to D),(\lnot B\lor \lnot D)\vDash(\lnot A\lor\lnot C)$；

• ⑫ 合取引入规则：$A,B\models (A\wedge B)$$A,B\vDash(A\land B)$.

3. 附加前提证明法（CP 规则）

$P_1\wedge P_2\wedge \cdots \wedge P_n\to (P\to Q)$$P_1\land P_2\land\cdots\land P_n\to(P\to Q)$ 形式命题的证明：

若 $\{P_1,P_2,\cdots ,P_n,P\}\models Q$$\{P_1,P_2,\cdots,P_n,P\}\vDash Q$，则 $\{P_1,P_2,\cdots ,P_n\}\models P\to Q$$\{P_1,P_2,\cdots,P_n\}\vDash P\to Q$.

意义：当推理的结论是蕴涵式时，可以将其前件作为附加前提引用，只要能推理出其后件，则原推理成立.

4. 反证法（归谬法）

定义1.19

设 $G_1,G_2,\cdots ,G_n$$G_1,G_2,\cdots,G_n$ 是一组命题公式，$P_1,P_2,\cdots ,P_n$$P_1,P_2,\cdots,P_n$ 是出现在 $G_1,G_2,\cdots ,G_n$$G_1,G_2,\cdots,G_n$ 中的一切命题变元， $I$$I$ 是它的任意解释.

• 若有解释 $I$$I$ 使 $G_1\wedge G_2\wedge \cdots \wedge G_n$$G_1\land G_2\land\cdots\land G_n$ 取值为真，则称公式 $G_1,G_2,\cdots ,G_n$$G_1,G_2,\cdots,G_n$ 是一致的（consistency）；

• 如对任意的解释 $I$$I$，都有 $G_1\wedge G_2\wedge \cdots \wedge G_n$$G_1\land G_2\land\cdots\land G_n$ 取值为假，则称公式 $G_1,G_2,\cdots ,G_n$$G_1,G_2,\cdots,G_n$ 是不一致的（inconsistency），或者说 $G_1\wedge G_2\wedge \cdots \wedge G_n$$G_1\land G_2\land\cdots\land G_n$ 是一个矛盾式.

定理1.10

设命题公式集合 $\{G_1,G_2,\cdots ,G_n\}$$\{G_1,G_2,\cdots,G_n\}$ 是一致的，于是从前提集合 $\{G_1,G_2,\cdots ,G_n\}$$\{G_1,G_2,\cdots,G_n\}$ 出发可以逻辑地推出公式 $H$$H$ 的充要条件是从前提集合 $G_1,G_2,\cdots ,G_n,\mathrm{\neg }H$$G_1,G_2,\cdots,G_n,\lnot H$ 出发，可以逻辑推出一个矛盾式来.

由上述定理得归谬法：

将结论的否定作为附加前提引入，公式序列的最后一行得到一矛盾式，则原结论成立.

1.6 命题演算的形式系统

1.6.1 形式系统的基本概念

形式系统一般由以下几个部分组成

1. 字母表：由不加定义而采用的符号组成，字母表指此形式系统可以使用的符号；

2. 字母表上符号串的一个子集是公式集（form）：公式集中的元素称为公式，公式集指此形式系统可以使用的符号串；

3. 公式集的一个子集是公理集（axiom）：公理集中的元素称为公理，公理集指此形式系统一开始便接受而不加证明的定理；

4. 推理规则系证明（rule），证明中的元素称为推理规则，证明规定了公式间的转换关系.

对于一个形式系统，公理集和证明均可以为空. 当两者皆为空时，系统仅仅为一个语句生成系统. 在数理逻辑中，如果公理集非空，则称为公理系统；若公理集为空，则称为自然推理系统.

对于一个具体的实际系统，用形式系统来描述，有两个具体的问题必须解决，即语法推论和语义推论的一致性问题：

• 可靠性问题：形式系统中正确推理出来的公式，定理在所讨论的具体实际系统中是否为永真；

• 完备性问题：具体实际系统中的永真的语句是否均为形式系统内的定理.

1.6.2 命题演算公式集

1. 字母表：

   1. 两个运算符：$\mathrm{\neg },\to$$\lnot,\to$（括号可省）；

   2. 命题变元的可数序列：

      $$x_1,x_2,\cdots ,x_n,\cdots .$$

2. 公式集（形成规则）：

   1. 命题变元 $x_1,x_2,\cdots ,x_n,\cdots$$x_1,x_2,\cdots,x_n,\cdots$ 中的每一个都是公式；

   2. 若 $p,q$$p,q$ 是公式，则 $\mathrm{\neg }p,p\to q$$\lnot p, p\to q$ 是公式；

   3. 任一公式皆由规则 1, 2 的有限次使用形成.

   记 $X=\{x_1,x_2,\cdots ,x_n,\cdots \}$$X=\{x_1,x_2,\cdots,x_n,\cdots\}$，则用 $L(X)$$L(X)$ 表示由 1 - 3 形成的所有公式所构成的公式集.

1.6.3 命题演算公式的唯一读法及命题演算公式集的代数结构

命题演算公式的唯一读法

• 省括号：中缀表达式→前缀表达式，如 $p\to q$$p\to q$ 写成 $\to pq$$\to pq$；

• 定义权重：

  $$\begin{array}{c}w(\mathrm{\neg })=0,w(\to )=-1,w(x_i)=1,i\in \mathbb{N},\\ w(u_1\cdots u_n)=w(u_1)+\cdots +w(u_n),\\ w(\varnothing )=0.\end{array}$$

命题1

若一字母串是公式，则该串的权重必是 $1$$1$，而该串的任一真前段的权重都小于 $1$$1$.

命题2

若一字母串是由两个公式并接而成，则并接的方式是唯一的.

确定任一给定字母串是否是公式的算法：

• 计算权重，权重不为 $1$$1$ 时排除；

• 权重为 $1$$1$ 时，若该串是单字母串，那只能是 $x_i$$x_i$；

• 权重为 $1$$1$ 且长度大于 $1$$1$ 时，三种可能：

  • 该串以 $x_i$$x_i$ 开头，则肯定不是公式；

  • 该串以 $\mathrm{\neg }$$\lnot$ 开头，则去掉 $\mathrm{\neg }$$\lnot$ 后对剩下的较短字母串进行检查，决定于较短字母串是否是公式；

  • 该串以 $\to$$\to$ 开头，则去掉权重为 $-1$$-1$ 的 $\to$$\to$ 后，检查剩下较短的字母串（权重为 2）是否是两个公式的并接. 若是，则并接方式是唯一的.

命题演算公式集的代数结构

1.6.4 命题演算 $L$$L$

定义1（命题演算 $L$$L$）

命题变元集 $X=\{x_1,x_2,\cdots \}$$X=\{x_1,x_2,\cdots\}$ 上的命题演算 $L$$L$ 是指带有下面规定的公理和证明的命题代数 $L(X)$$L(X)$：

1. 公理——取 $L(X)$$L(X)$ 的具有以下形状的公式作为公理：

   • （L1）$p\to (q\to p)$$p\to(q\to p)$ 肯定前件律；

   • （L2）$(p\to (q\to r))\to ((p\to q)\to (p\to r))$$(p\to(q\to r))\to((p\to q)\to(p\to r))$ 蕴含词分配律；

   • （L3）$(\mathrm{\neg }p\to \mathrm{\neg }q)\to (q\to p)$$(\lnot p\to\lnot q)\to(q\to p)$ 换位律，

   其中 $p,q,r\in L(X)$$p,q,r\in L(X)$.

2. 证明——设 $\mathrm{\Gamma }\subseteq L(X),p\in L(X)$$\Gamma\sube L(X),p\in L(X)$，若存在 $L(X)$$L(X)$ 的公式有限序列 $p_1,\cdots ,p_n$$p_1,\cdots,p_n$，其中 $p_n=p$$p_n=p$，且每个 $p_k(k=1,\cdots ,n)$$p_k(k=1,\cdots,n)$ 满足

   a) $p_k\in \mathrm{\Gamma }$$p_k\in\Gamma$，b) $p_k$$p_k$ 是公理，或 c) 存在 $i,j<k$$i,j<k$ 使 $p_j=p_i\to p_k$$p_j=p_i\to p_k$，

   则称公式 $p$$p$ 是从公式集 $\mathrm{\Gamma }$$\Gamma$ 可证的，$p_1,p_2,\cdots ,p_n$$p_1,p_2,\cdots,p_n$ 叫做 $p$$p$ 从 $\mathrm{\Gamma }$$\Gamma$ 的证明.

定义2（语法推论）

建立命题演算 $L$$L$ 后，进一步规定：

1. 如果公式 $p$$p$ 从公式集 $\mathrm{\Gamma }$$\Gamma$ 可证，则记作 $\mathrm{\Gamma }⊢p$$\Gamma\vdash p$ 或 $\mathrm{\Gamma }{⊢}_{L}p$$\Gamma\vdash_L p$. 这时 $\mathrm{\Gamma }$$\Gamma$ 中的公式叫做假定，$p$$p$ 叫做假定集 $\mathrm{\Gamma }$$\Gamma$ 的语法推论.

2. 若 $\varnothing ⊢p$$\varnothing\vdash p$，则称 $p$$p$ 是 $L$$L$ 的定理，记作 $⊢p$$\vdash p$. $p$$p$ 在 $L$$L$ 中从 $\varnothing$$\varnothing$ 的证明 $p_1,\cdots ,p_n$$p_1,\cdots,p_n$ 简称为 $p$$p$ 在 $L$$L$ 中的证明.

3. 在一个证明中，当 $p_j=p_i\to p_k(i,j<k)$$p_j=p_i\to p_k(i,j<k)$ 时，就说 $p_k$$p_k$ 由 $p_i,p_i\to p_k$$p_i,p_i\to p_k$ 使用假言推理（modus ponens）这条推理规则而得，即使用 MP 而得.

几点结论：

1. 若 $p$$p$ 是 $L$$L$ 的公理，则 $\mathrm{\Gamma }⊢p$$\Gamma\vdash p$ 对任一公式集 $\mathrm{\Gamma }$$\Gamma$ 都成立；

2. 若 $⊢p$$\vdash p$（即 $p$$p$ 是 $L$$L$ 的定理），则 $\mathrm{\Gamma }⊢p$$\Gamma\vdash p$ 对任一公式集 $\mathrm{\Gamma }$$\Gamma$ 都成立；

3. 若 $p\in \mathrm{\Gamma }$$p\in \Gamma$，则 $\mathrm{\Gamma }⊢p$$\Gamma\vdash p$；

4. $\{p,p\to q\}⊢q$$\{p,p\to q\}\vdash q$；

5. 若 $\mathrm{\Gamma }⊢p_n$$\Gamma\vdash p_n$，且已知 $p_1,p_2,\cdots ,p_n$$p_1,p_2,\cdots,p_n$ 是 $p_n$$p_n$ 从 $\mathrm{\Gamma }$$\Gamma$ 的证明，则当 $1⩽k⩽n$$1\leqslant k\leqslant n$ 时，有 $\mathrm{\Gamma }⊢p_k$$\Gamma\vdash p_k$，且 $p_1,\cdots ,p_k$$p_1,\cdots,p_k$ 是 $p_k$$p_k$ 从 $\mathrm{\Gamma }$$\Gamma$ 的证明.

6. 若 $\mathrm{\Gamma }$$\Gamma$ 是无限集，且 $\mathrm{\Gamma }⊢p$$\Gamma\vdash p$，则存在 $\mathrm{\Gamma }$$\Gamma$ 的有限子集 $\mathrm{\Delta }$$\Delta$ 使 $\mathrm{\Delta }⊢p$$\Delta\vdash p$.

命题1 （同一律）

$$⊢p\to p.$$

命题2 （否定前件律）

$$⊢\mathrm{\neg }q\to (q\to p).$$

定义3（无矛盾公式集）

如果对任意公式 $q$$q$，$\mathrm{\Gamma }⊢q$$\Gamma\vdash q$ 和 $\mathrm{\Gamma }⊢\mathrm{\neg }q$$\Gamma\vdash\lnot q$ 二者都不同时成立，就称公式集 $\mathrm{\Gamma }$$\Gamma$ 是无矛盾公式集，否则称 $\mathrm{\Gamma }$$\Gamma$ 为有矛盾公式集.

命题3

若 $\mathrm{\Gamma }$$\Gamma$ 是有矛盾公式集，则对 $L$$L$ 的任一公式 $p$$p$，都有 $\mathrm{\Gamma }⊢p$$\Gamma\vdash p$.

1.6.5 演绎定理、反证律与归谬律

演绎定理

定理（演绎定理）

$$\mathrm{\Gamma }\cup \{p\}⊢q⟺\mathrm{\Gamma }⊢p\to q.$$

推论（假设三段论）

$$\{p\to q,q\to r\}⊢p\to r.$$

假设三段论（hypothetical syllogism）简记作 HS.

命题1（否定肯定律）

$$⊢(\mathrm{\neg }p\to p)\to p.$$

反证律与归谬律

定理1（反证律）

$$\mathrm{\Gamma }\cup \{\mathrm{\neg }p\}⊢q\text{且}\mathrm{\Gamma }\cup \{\mathrm{\neg }p\}⊢\mathrm{\neg }q⟹\mathrm{\Gamma }⊢p.$$

反证律虽然没有直接使用 (L3)，但通过使用否定前件律和否定肯定律而间接使用了 (L3).

推论（双重否定律）

$$1)\{\mathrm{\neg }\mathrm{\neg }p\}⊢p\text{或}2)⊢\mathrm{\neg }\mathrm{\neg }p\to p.$$

定理2（归谬律）

$$\mathrm{\Gamma }\cup \{p\}⊢q\text{且}\mathrm{\Gamma }\cup \{p\}⊢\mathrm{\neg }q⟹\mathrm{\Gamma }⊢\mathrm{\neg }p.$$

推论（第二双重否定律）

$$1)\{p\}⊢\mathrm{\neg }\mathrm{\neg }p\text{或}2)⊢p\to \mathrm{\neg }\mathrm{\neg }p.$$

总结：可直接引用的定律

1. $⊢p\to p$$\vdash p\to p$ （同一律）；

2. $⊢\mathrm{\neg }q\to (q\to p)$$\vdash \lnot q\to(q\to p)$ （否定前件律）；

3. $⊢(\mathrm{\neg }p\to p)\to p$$\vdash(\lnot p\to p)\to p$ （否定肯定律）；

4. $⊢(p\to q)\to ((q\to r)\to (p\to r))$$\vdash (p\to q)\to((q\to r)\to(p\to r))$ （HS，即假设三段论）；

5. $⊢\mathrm{\neg }\mathrm{\neg }p\to p$$\vdash\lnot\lnot p\to p$ （双重否定律）；

6. $⊢p\to \mathrm{\neg }\mathrm{\neg }p$$\vdash p\to\lnot\lnot p$ （第二双重否定律）；

7. $⊢(p\to q)\to (\mathrm{\neg }q\to \mathrm{\neg }p)$$\vdash(p\to q)\to(\lnot q\to\lnot p)$ （换位律）.

1.6.6 命题演算的语义、赋值与语义推论

命题演算的语义

定义1（真值函数）

令 $Z_2=\{0,1\}$$Z_2=\{0,1\}$，$Z_2$$Z_2$ 上的 $n$$n$ 元运算，即函数 $f:Z_2^n\to Z_2$$f:Z_2^n\to Z_2$ 叫做 $n$$n$ 元真值函数.

$n$$n$ 元真值函数的定义域有 $2^n$$2^n$ 个元素，不同的 $n$$n$ 元真值函数有 $2^{2^n}$$2^{2^n}$ 个.

• 公式1：$\mathrm{\neg }\mathrm{\neg }v=v$$\lnot\lnot v=v$；

• 公式2：$1\to v=v$$1\to v=v$；

• 公式3：$v\to 1=1$$v\to 1=1$；

• 公式4：$v\to 0=\mathrm{\neg }v$$v\to 0=\lnot v$；

• 公式5：$0\to v=1$$0\to v=1$.

命题1 任一真值函数都可用一元运算 $\mathrm{\neg }$$\lnot$ 和二元运算 $\to$$\to$ 表示出来.

赋值与语义推论

定义1（赋值）

具有“保运算性”的映射 $v:L(X)\to Z_2$$v:L(X)\to Z_2$ 叫做 $L(X)$$L(X)$ 的赋值. 映射 $v$$v$ 具有保运算性，是指对任意 $p,q\in L(X)$$p,q\in L(X)$，$v$$v$ 满足

1. $v(\mathrm{\neg }p)=\mathrm{\neg }v(p)$$v(\lnot p)=\lnot v(p)$；

2. $v(p\to q)=v(p)\to v(q)$$v(p\to q)=v(p)\to v(q)$.

对任意公式 $p\in L(X)$$p\in L(X)$，$v(p)$$v(p)$ 叫做 $p$$p$ 的真值. 同样，具有保运算性的映射 $v:L(X_n)\to Z_2$$v:L(X_n)\to Z_2$ 叫做 $L(X_n)$$L(X_n)$ 的赋值（$X_n=\{x_1,\cdots ,x_n\}$$X_n=\{x_1,\cdots,x_n\}$）.

定义2（真值指派）

映射 $v_0:X\to Z_2$$v_0:X\to Z_2$ 叫做命题变元的真值指派. 若把其中 $X$$X$ 换成 $X_n=\{x_1,\cdots ,x_n\}$$X_n=\{x_1,\cdots,x_n\}$，则 $v_0$$v_0$ 叫做 $x_1,\cdots ,x_n$$x_1,\cdots,x_n$ 的真值指派.

定理1

命题变元 $X=\{x_1,\cdots ,x_n,\cdots \}$$X=\{x_1,\cdots,x_n,\cdots\}$ 的任一真值指派，必可唯一地扩张成 $L(X)$$L(X)$ 的赋值；$X_n=\{x_1,\cdots ,x_n\}$$X_n=\{x_1,\cdots,x_n\}$ 的任一真值指派，必可唯一地扩张成 $L(X_n)$$L(X_n)$ 的赋值.