命题逻辑

命题逻辑的基本概念

命题与真值

• 命题：判断结果唯一的陈述句
• 命题的真值：判断的结果
• 真值的取值：真与假
• 真命题与假命题 注意： 感叹句、祈使句、疑问句都不是命题 陈述句中的悖论，判断结果不唯一确定的不是命题

命题分类

简单命题（也称原子命题,不能被分解成更简单的命题） 复合命题（由简单命题通过联结词联结而成的命题）

简单命题符号化

• 用小写英文字母 $p,q,r\cdots$ 或 $p_1,p_2,p_3\cdots$ 表示
• 用 $1$ 表示真（$T$），用 $0$ 表示假（$F$）

连接词

• 否定：$\mathrm{\neg }p$
• 合取：$p\wedge q$
• 析取：$p\vee q$
• 蕴含：$p\to q$
• 等价：$p\leftrightarrow q$

命题变项

• 命题常项：一个命题标识符表示确定的命题
• 命题变项：一个命题标识符表示不确定的命题

命题常项和变项均由字母表示

合式公式

1. 单个命题变项和命题常项是合式公式, 称作原子命题公式
2. 若A是合式公式，则 ($\mathrm{\neg }A$)也是
3. 若A, B是合式公式，则($A\wedge B$), ($A\vee B$), ($A\to B$), ($A\leftrightarrow B$)也是
4. 只有有限次地应用 1. — 3. 形成的符号串才是合式公式

合式公式的层次

1. 单个命题变项为 $0$ 层
2. 称 A 是 $n+1(n\ge 0)$ 层公式是指下面情况之一： (a) $A=\mathrm{\neg }B$, $B$ 是 $n$ 层公式； (b) $A=B\wedge C$, 其中 $B,C$ 分别为 $i$ 层和 $j$ 层公式， 且 $n=max(i,j)$； (c) $A=B\vee C$, 其中 $B,C$ 的层次及 $n$ 同 (b)； (d) $A=B\to C$, 其中 $B,C$ 的层次及 $n$ 同 (b)； (e) $A=B\leftrightarrow C$, 其中 $B,C$ 的层次及 $n$ 同 (b).
3. 若公式 $A$ 的层次为 $k$, 则称 $A$ 为 $k$ 层公式.

公式赋值

设 $p_1,p_2,\cdots ,p_n$ 是在 $A$ 中出现的所有命题变项，$A$ 是一个合式公式，$a_1,a_2,\cdots ,a_n$ 是 $p_1,p_2,\cdots ,p_n$ 的真值，则称 $a_1,a_2,\cdots ,a_n$ 是 $A$ 的一个赋值。

• 若使 $A$ 的值为真，则称 $a_1,a_2,\cdots ,a_n$ 是 $A$ 的一个真值赋值
• 若使 $A$ 的值为假，则称 $a_1,a_2,\cdots ,a_n$ 是 $A$ 的一个假值赋值

公式的类型

• 重言式 或 永真式：对任何赋值，公式的值都为真
• 矛盾式 或 永假式：对任何赋值，公式的值都为假

若一个公式不是矛盾式，则称它是可满足式。

真值表

将命题公式 $A$ 在所有赋值下取值的情况列成表, 称作 $A$ 的真值表.

等值式

若 $A\leftrightarrow B$ 是重言式，则称 $A$ 与 $B$ 等值，记作 $A\iff B$，并称 $A$ 与 $B$ 是等值式。

• 真值表法
• 等值演算法

基本等值式

$$\begin{array}{rlrl}\mathrm{双}\mathrm{重}\mathrm{否}\mathrm{定}\mathrm{律}& & \mathrm{\neg }(\mathrm{\neg }A)& \iff A\\ \\ \mathrm{幂}\mathrm{等}\mathrm{律}& & A\wedge A& \iff A\\ & & A\vee A& \iff A\\ \\ \mathrm{交}\mathrm{换}\mathrm{律}& & A\wedge B& \iff B\wedge A\\ & & A\vee B& \iff B\vee A\\ \\ \mathrm{结}\mathrm{合}\mathrm{律}& & A\wedge (B\wedge C)& \iff (A\wedge B)\wedge C\\ & & A\vee (B\vee C)& \iff (A\vee B)\vee C\\ \\ \mathrm{分}\mathrm{配}\mathrm{律}& & 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)\\ \\ \mathrm{吸}\mathrm{收}\mathrm{律}& & A\wedge (A\vee B)& \iff A\\ & & A\vee (A\wedge B)& \iff A\\ \\ \mathrm{零}\mathrm{律}& & A\wedge 0& \iff 0\\ & & A\vee 1& \iff 1\\ \\ \mathrm{同}\mathrm{一}\mathrm{律}& & A\wedge 1& \iff A\\ & & A\vee 0& \iff A\\ \\ \mathrm{排}\mathrm{中}\mathrm{律}& & A\vee \mathrm{\neg }A& \iff 1\\ & & A\wedge \mathrm{\neg }A& \iff 0\\ \\ \mathrm{矛}\mathrm{盾}\mathrm{律}& & A\wedge \mathrm{\neg }A& \iff 0\\ & & A\vee \mathrm{\neg }A& \iff 1\\ \\ \mathrm{蕴}\mathrm{含}\mathrm{等}\mathrm{值}\mathrm{式}& & A\to B& \iff \mathrm{\neg }A\vee B\\ & & \mathrm{\neg }(A\to B)& \iff A\wedge \mathrm{\neg }B\\ \\ \mathrm{德}\mathrm{摩}\mathrm{根}\mathrm{律}& & \mathrm{\neg }(A\wedge B)& \iff \mathrm{\neg }A\vee \mathrm{\neg }B\\ & & \mathrm{\neg }(A\vee B)& \iff \mathrm{\neg }A\wedge \mathrm{\neg }B\\ \\ \mathrm{等}\mathrm{价}\mathrm{等}\mathrm{值}\mathrm{式}& & A\leftrightarrow B& \iff (A\to B)\wedge (B\to A)\\ \mathrm{假}\mathrm{言}\mathrm{易}\mathrm{位}& & A\to B& \iff \mathrm{\neg }B\to \mathrm{\neg }A\\ & & \mathrm{\neg }(A\to B)& \iff A\wedge \mathrm{\neg }B\\ \\ \mathrm{等}\mathrm{价}\mathrm{否}\mathrm{定}& & A\leftrightarrow B& \iff \mathrm{\neg }A\leftrightarrow \mathrm{\neg }B\\ \mathrm{归}\mathrm{谬}\mathrm{论}& & A\to B& \iff \mathrm{\neg }B\to \mathrm{\neg }A\end{array}$$

析取范式与合取范式

简单析取式与简单合取式

• 文字：命题变项或其否定
• 简单析取式：有限个文字的析取$$p,\mathrm{\neg }q,p\vee q,\mathrm{\neg }p\vee q,\mathrm{\neg }p\vee \mathrm{\neg }q$$
• 简单合取式：有限个文字的合取$$p,\mathrm{\neg }q,p\wedge q,\mathrm{\neg }p\wedge q,\mathrm{\neg }p\wedge \mathrm{\neg }q$$

单个文字既是析取式又是合取式

一个简单析取式是重言式当且仅当它包含一个命题变项和它的否定 一个简单合取式是矛盾式当且仅当它包含一个命题变项和它的否定

析取范式与合取范式

析取范式：$$A_1 \lor A_2 \lor \cdots \lor A_n$$ 其中 $A_i$ 是简单合取式

合取范式：$$A_1 \land A_2 \land \cdots \land A_m$$ 其中 $A_i$ 是简单析取式

一个析取范式是矛盾式当且仅当它的每一个合取式都是矛盾式 一个合取范式是重言式当且仅当它的每一个析取式都是重言式

任意一个命题公式都可以化为析取范式和合取范式

主析取范式与主合取范式

主析取范式与极小项

主析取范式：$$m_0 \lor m_1 \lor \cdots \lor m_{2^n-1}$$ 其中 $m_i$ 被称作极小项，是 $n$ 个文字的析取 $m_i$ 的第 $j$ 个文字是 $p_j$ 或 $\mathrm{\neg }{p}_j$ 若 $i$ 的二进制表示为 $b_1{b}_2\cdots b_n$，则 $m_i$ 为

$$p_1^{b_1}\wedge p_2^{b_2}\wedge \cdots \wedge p_n^{b_n}$$

$p_j^{b_j}$ 表示 $p_j$ 若 $b_j=1$ 则取 $p_j$，否则取 $\mathrm{\neg }{p}_j$

主合取范式与极大项

主合取范式：$$M_0 \land M_1 \land \cdots \land M_{2^n-1}$$ 其中 $M_i$ 被称作极大项，是 $n$ 个文字的合取 $M_i$ 的第 $j$ 个文字是 $p_j$ 或 $\mathrm{\neg }{p}_j$ 若 $i$ 的二进制表示为 $b_1{b}_2\cdots b_n$，则 $M_i$ 为

$$p_1^{b_1}\vee p_2^{b_2}\vee \cdots \vee p_n^{b_n}$$

$p_j^{b_j}$ 表示 $p_j$ 若 $b_j=1$ 则取 $p_j$，否则取 $\mathrm{\neg }{p}_j$

任意一个命题公式都可以化为唯一的主析取范式和主合取范式

连接词完备集

• 不可兼析取：$\bar{\vee }$ 即异或
  • $A\bar{\vee }B\iff (A\vee B)\wedge \mathrm{\neg }(A\wedge B)\iff (A\wedge \mathrm{\neg }B)\vee (\mathrm{\neg }A\wedge B)$
• 或非：$\downarrow$
  • $A\downarrow B\iff \mathrm{\neg }(A\vee B)\iff \mathrm{\neg }A\wedge \mathrm{\neg }B$
• 与非：$\uparrow$
  • $A\uparrow B\iff \mathrm{\neg }(A\wedge B)\iff \mathrm{\neg }A\vee \mathrm{\neg }B$

若任意 $n$ 元真值函数都可以由仅含 $S$ 中的连接词构成的公式表示，则称 $S$ 为连接词完备集

部分完备集举例

$$S=\{\mathrm{\neg },\wedge ,\vee \}$$

证明：任意一个 $n$ 元函数都可与唯一的一个主析取范式和主合取范式对应

$$S=\{\mathrm{\neg },\wedge \}$$

证明：$A\vee B\iff \mathrm{\neg }(\mathrm{\neg }A\wedge \mathrm{\neg }B)$

$$S=\{\mathrm{\neg },\vee \}$$

证明：$A\wedge B\iff \mathrm{\neg }(\mathrm{\neg }A\vee \mathrm{\neg }B)$

$$S=\{\mathrm{\neg },\to \}$$

证明：$A\wedge B\iff \mathrm{\neg }A\to B$

$$S=\{\vee ,\wedge ,\to ,\leftrightarrow \}\$\$\mathrm{不}\mathrm{是}\mathrm{完}\mathrm{备}\mathrm{集}，\mathrm{恒}\mathrm{取}\$0\$\mathrm{的}\mathrm{函}\mathrm{数}\mathrm{无}\mathrm{法}\mathrm{表}\mathrm{示}\$\$S=\{\uparrow \}$$

证明：$$\begin{aligned} \neg A &\Leftrightarrow A \uparrow A\ A \land B &\Leftrightarrow \neg (A \uparrow B)\ A \lor B &\Leftrightarrow \neg (\neg A \uparrow \neg B)\ \end{aligned}$$

最小连接词完备集

若 $S$ 是连接词完备集，从 $S$ 中去掉任意一个连接词后 $S$ 不再是完备集，则称 $S$ 为最小连接词完备集

消解算法与可满足性问题

$$C_1\wedge C_2\approx Res(C_1,C_2)=C_1^{\prime }\vee C_2^{\prime }$$

1. 若 $C_1\wedge C_2\leftrightarrow (l\vee C_1^{\prime })\wedge (\mathrm{\neg }l\vee C_2^{\prime })$ 是可满足的，则称 $C_1^{\prime }\vee C_2^{\prime }$ 也是可满足的
2. 若 $C_1^{\prime }\vee C_2^{\prime }$ 是可满足的，则称 $C_1\wedge C_2$ 也是可满足的 故可将 $C_1\wedge C_2$ 化为 $C_1^{\prime }\vee C_2^{\prime }$，称作消解

推理

当 $A_1\wedge A_2\wedge \cdots \wedge A_n\to B$ 是重言式时，称 $B$ 由 $A_1,A_2,\cdots ,A_n$ 推出，记作 $\{A_1,A_2,\cdots ,A_n\}⊢B$$A_1,A_2,\cdots ,A_n$ 称作前提，$B$ 称作结论 称前提推出结论是有效的或正确的，并称 $B$ 是有效结论。

推理的形式结构

1. $\{A_1,A_2,\cdots ,A_n\}⊢B$
   • 若推理正确，记为 $\{A_1,A_2,\cdots ,A_n\}\models B$
   • 若推理不正确，记为 $\{A_1,A_2,\cdots ,A_n\}⊭B$
2. $A_1\wedge A_2\wedge \cdots \wedge A_n\to B$
   • 若推理正确，记为 $A_1\wedge A_2\wedge \cdots \Rightarrow B$
3. 前提：$A_1,A_2,\cdots ,A_n$，结论：$B$

推理定律

$$\begin{array}{rlrl}\mathrm{附}\mathrm{加}\mathrm{律}& & A& \Rightarrow A\wedge B\\ \mathrm{化}\mathrm{简}\mathrm{律}& & A\wedge B& \Rightarrow A\\ \mathrm{假}\mathrm{言}\mathrm{推}\mathrm{理}& & A\wedge (A\to B)& \Rightarrow B\\ \mathrm{拒}\mathrm{取}\mathrm{式}& & \mathrm{\neg }A\wedge \mathrm{\neg }B& \Rightarrow \mathrm{\neg }(A\wedge B)\\ \mathrm{析}\mathrm{取}\mathrm{三}\mathrm{段}\mathrm{论}& & A\vee B,\mathrm{\neg }A& \Rightarrow B\\ \mathrm{假}\mathrm{言}\mathrm{三}\mathrm{段}\mathrm{论}& & A\to B,B\to C& \Rightarrow A\to C\\ \mathrm{等}\mathrm{价}\mathrm{三}\mathrm{段}\mathrm{论}& & A\leftrightarrow B,B\leftrightarrow C& \Rightarrow A\leftrightarrow C\\ \mathrm{构}\mathrm{造}\mathrm{性}\mathrm{二}\mathrm{难}& & A\to B,C\to D,A\vee C& \Rightarrow B\vee D\\ & & A\to B,\mathrm{\neg }A\to B& \Rightarrow B\\ \mathrm{破}\mathrm{坏}\mathrm{性}\mathrm{二}\mathrm{难}& & A\to B,C\to D,\mathrm{\neg }B\vee \mathrm{\neg }D& \Rightarrow \mathrm{\neg }A\vee \mathrm{\neg }C\\ & & A\to B,\mathrm{\neg }B\to A& \Rightarrow A\leftrightarrow B\end{array}$$

形式系统

自然推理系统

定义3.3 自然推理系统 $P$ 定义如下:

1. 字母表
   1. 命题变项符号：$p,q,r,\dots ,p_i,q_i,r_i,\dots$
   2. 联结词符号：$\mathrm{\neg },\wedge ,\vee ,\to ,\leftrightarrow$
   3. 括号与逗号：$(,),,$
2. 合式公式（同定义1.6）
3. 推理规则
   1. 前提引入规则
   2. 结论引入规则
   3. 置换规则

构造证明

设前提 $A_1,A_2,\dots ,A_k$，结论 $B$ 及公式序列 $C_1,C_2,\dots ,C_l$， 如果每一个 $C_i(1\le i\le l)$ 是某个 $A_j(1\le j\le k)$， 或者可由序列中前面的公式应用推理规则得到， 并且 $C_l=B$， 则称这个公式序列是由 $A_1,A_2,\dots ,A_k$ 推出 $B$ 的证明。

附加前提证明法

附加前提证明法适用于结论为蕴涵式

• 欲证
  • 前提：$A_1,A_2,\dots ,A_k$
  • 结论：$C\to B$
• 等价地证明
  • 前提：$A_1,A_2,\dots ,A_k,C$
  • 结论：$B$

归谬法

• 欲证
  • 前提：$A_1,A_2,\dots ,A_k$
  • 结论：$B$
• 等价地证明
  • 前提：$A_1,A_2,\dots ,A_k,\mathrm{\neg }B$
  • 结论：$0$