命题逻辑

命题逻辑的基本概念

命题与真值

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

命题分类

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

简单命题符号化

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

连接词

否定：$\neg p$
合取：$p \land q$
析取：$p \lor q$
蕴含：$p \to q$
等价：$p \leftrightarrow q$

命题变项

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

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

合式公式

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

合式公式的层次

单个命题变项为 $0$ 层
称 A 是 $n+1(n \geq 0)$ 层公式是指下面情况之一： (a) $A=\neg B$, $B$ 是 $n$ 层公式； (b) $A=B \land C$, 其中 $B,C$ 分别为 $i$ 层和 $j$ 层公式，且 $n=\max(i,j)$； (c) $A=B \lor C$, 其中 $B,C$ 的层次及 $n$ 同 (b)； (d) $A=B \to C$, 其中 $B,C$ 的层次及 $n$ 同 (b)； (e) $A=B \leftrightarrow C$, 其中 $B,C$ 的层次及 $n$ 同 (b).
若公式 $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 \Leftrightarrow B$，并称 $A$ 与 $B$ 是等值式。

真值表法
等值演算法

基本等值式

$$\begin{aligned} 双重否定律 & & \neg(\neg A) & \Leftrightarrow A \newline \newline 幂等律 & & A \land A & \Leftrightarrow A \newline & & A \lor A & \Leftrightarrow A \newline \newline 交换律 & & A \land B & \Leftrightarrow B \land A \newline & & A \lor B & \Leftrightarrow B \lor A \newline \newline 结合律 & & A \land (B \land C) & \Leftrightarrow (A \land B) \land C \newline & & A \lor (B \lor C) & \Leftrightarrow (A \lor B) \lor C \newline \newline 分配律 & & A \land (B \lor C) & \Leftrightarrow (A \land B) \lor (A \land C) \newline & & A \lor (B \land C) & \Leftrightarrow (A \lor B) \land (A \lor C) \newline \newline 吸收律 & & A \land (A \lor B) & \Leftrightarrow A \newline & & A \lor (A \land B) & \Leftrightarrow A \newline \newline 零律 & & A \land 0 & \Leftrightarrow 0 \newline & & A \lor 1 & \Leftrightarrow 1 \newline \newline 同一律 & & A \land 1 & \Leftrightarrow A \newline & & A \lor 0 & \Leftrightarrow A \newline \newline 排中律 & & A \lor \neg A & \Leftrightarrow 1 \newline & & A \land \neg A & \Leftrightarrow 0 \newline \newline 矛盾律 & & A \land \neg A & \Leftrightarrow 0 \newline & & A \lor \neg A & \Leftrightarrow 1 \newline \newline 蕴含等值式 & & A \to B & \Leftrightarrow \neg A \lor B \newline & & \neg(A \to B) & \Leftrightarrow A \land \neg B \newline \newline 德摩根律 & & \neg(A \land B) & \Leftrightarrow \neg A \lor \neg B \newline & & \neg(A \lor B) & \Leftrightarrow \neg A \land \neg B \newline \newline 等价等值式 & & A \leftrightarrow B & \Leftrightarrow (A \to B) \land (B \to A) \newline 假言易位 & & A \to B & \Leftrightarrow \neg B \to \neg A \newline & & \neg(A \to B) & \Leftrightarrow A \land \neg B \newline \newline 等价否定 & & A \leftrightarrow B & \Leftrightarrow \neg A \leftrightarrow \neg B \newline 归谬论 & & A \to B & \Leftrightarrow \neg B \to \neg A \newline \end{aligned}$$

析取范式与合取范式

简单析取式与简单合取式

文字：命题变项或其否定
简单析取式：有限个文字的析取 $$p, \neg q, p \lor q, \neg p \lor q, \neg p \lor \neg q$$
简单合取式：有限个文字的合取 $$p, \neg q, p \land q, \neg p \land q, \neg p \land \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$ 或 $\neg p_j$ 若 $i$ 的二进制表示为 $b_1b_2\cdots b_n$，则 $m_i$ 为 $$p_1^{b_1} \land p_2^{b_2} \land \cdots \land p_n^{b_n}$$ $p_j^{b_j}$ 表示 $p_j$ 若 $b_j=1$ 则取 $p_j$，否则取 $\neg p_j$

主合取范式与极大项

主合取范式：$$M_0 \land M_1 \land \cdots \land M_{2^n-1}$$ 其中 $M_i$ 被称作极大项，是 $n$ 个文字的合取 $M_i$ 的第 $j$ 个文字是 $p_j$ 或 $\neg p_j$ 若 $i$ 的二进制表示为 $b_1b_2\cdots b_n$，则 $M_i$ 为 $$p_1^{b_1} \lor p_2^{b_2} \lor \cdots \lor p_n^{b_n}$$ $p_j^{b_j}$ 表示 $p_j$ 若 $b_j=1$ 则取 $p_j$，否则取 $\neg p_j$

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

连接词完备集

不可兼析取：$\overline{\lor}$ 即异或
- $A \overline{\lor} B \Leftrightarrow (A \lor B) \land \neg (A \land B) \Leftrightarrow (A \land \neg B) \lor (\neg A \land B)$
或非：$\downarrow$
- $A \downarrow B \Leftrightarrow \neg (A \lor B) \Leftrightarrow \neg A \land \neg B$
与非：$\uparrow$
- $A \uparrow B \Leftrightarrow \neg (A \land B) \Leftrightarrow \neg A \lor \neg B$

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

部分完备集举例

$$S = \lbrace \neg, \land, \lor \rbrace$$ 证明：任意一个 $n$ 元函数都可与唯一的一个主析取范式和主合取范式对应

$$S = \lbrace \neg, \land \rbrace$$ 证明：$A \lor B \Leftrightarrow \neg (\neg A \land \neg B)$

$$S = \lbrace \neg, \lor \rbrace$$ 证明：$A \land B \Leftrightarrow \neg (\neg A \lor \neg B)$

$$S = \lbrace \neg, \to \rbrace$$ 证明：$A \land B \Leftrightarrow \neg A \to B$

$$S = \lbrace \lor, \land, \to, \leftrightarrow \rbrace$$ 不是完备集，恒取 $0$ 的函数无法表示

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

最小连接词完备集

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

消解算法与可满足性问题

$$C_1 \land C_2 \approx Res(C_1, C_2) = C_1’ \lor C_2’$$

若 $C_1 \land C_2 \leftrightarrow (l \lor C_1’) \land (\neg l \lor C_2’)$ 是可满足的，则称 $C_1’ \lor C_2’$ 也是可满足的
若 $C_1’ \lor C_2’$ 是可满足的，则称 $C_1 \land C_2$ 也是可满足的故可将 $C_1 \land C_2$ 化为 $C_1’ \lor C_2’$，称作消解

推理

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

推理的形式结构

$\lbrace A_1, A_2, \cdots, A_n \rbrace \vdash B$
- 若推理正确，记为 $\lbrace A_1, A_2, \cdots, A_n \rbrace \vDash B$
- 若推理不正确，记为 $\lbrace A_1, A_2, \cdots, A_n \rbrace \nvDash B$
$A_1 \land A_2 \land \cdots \land A_n \to B$
- 若推理正确，记为 $A_1 \land A_2 \land \cdots \Rightarrow B$
前提：$A_1, A_2, \cdots, A_n$，结论：$B$

推理定律

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

形式系统

自然推理系统

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

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

构造证明

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

附加前提证明法

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

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

归谬法

欲证
- 前提：$A_1, A_2, \ldots, A_k$
- 结论：$B$
等价地证明
- 前提：$A_1, A_2, \ldots, A_k, \neg B$
- 结论：$0$

一阶谓词逻辑

一阶逻辑命题符号化

客体

客体：客观存在的实体，如人、物、事物等。
个体词：所研究对象中独立存在的客体。
- 个体常项：具体的事物，用 $a$ 、 $b$ 、 $c$ 等表示。
- 个体变项：抽象的事物，用 $x$ 、 $y$ 、 $z$ 等表示。
个体域：个体变项的取值范围。
- 有限个体域：如 $\lbrace a,b,c \rbrace$，$\lbrace 1, 2 \rbrace$ 等。
- 无限个体域：如全体自然数 $\mathbb{N}$，全体实数 $\mathbb{R}$ 等。
- 全总个体域：由宇宙间一切事物组成的个体域。

谓词

谓词：对客体的性质、特征、关系等进行描述的符号。常用大写字母表示，如 $P$ 、 $Q$ 、 $R$ 等。例如 $A(x)$ 表示 $x$ 满足性质 $A$。
- 谓词常项：如，$F(a):a$ 是男性。
- 谓词变项：如，$F(x):x$ 是男性。
- $n$ 元谓词：含有 $n$ 个变项的谓词。
  - 一元谓词：表示一个客体的性质。
  - 多元谓词：表示多个客体之间的关系。
  - 零元谓词：不含个体变项的谓词，即命题常项或命题变项。

量词

$\forall$ 和 $\exists$ 称为量词。

全称量词：$\forall$，表示“对任意”、“对一切”。
存在量词：$\exists$，表示“存在”、“至少有一个”。如 $\forall x P(x)$ 表示“对任意 $x$，$x$ 满足性质 $P$”。

对于 $\forall$ 用 $\to$ 而不是 $\land$ 对于 $\exists$ 用 $\land$ 而不是 $\to$

变元的约束

在公式 $\forall x A$ 和 $\exists x A$ 中，$x$ 称为指导变元，$A$ 为对应量词的辖域。在辖域内，$x$ 称为约束出现，$A$ 中不是约束出现的其他变项称为自由出现。若 $A$ 中没有自由出现的变项，则称 $A$ 为闭式。

公式的解释

若公式在任何解释和该解释下的任何赋值下都为真，则称该公式为永真式。若公式在任何解释和该解释下的任何赋值下都为假，则称该公式为永假式。若公式在某个解释和该解释下的某个赋值下为真，则称该公式为可满足式。

一阶逻辑公式是不可判定的，即无法判断一个公式是否永真、永假或可满足。

代换实例

设 $A_0$ 是含命题变项 $p_1, p_2, \ldots, p_n$ 的命题公式，$A_1, A_2, \ldots, A_n$ 是 $n$ 个谓词公式，用 $A_i$ ($1 \leq i \leq n$) 处处代替 $A_0$ 中的 $p_i$，所得公式 $A$ 称为 $A_0$ 的代换实例。

例如，$F(x) \to G(x)$，$\forall x F(x) \to \exists y G(y)$ 等都是 $p \to q$ 的代换实例。

重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式。

一阶逻辑的等值演算与推理

基本等值式

命题逻辑的基本等值式

基本等值式在一阶逻辑中仍然成立，如双重否定律、德摩根律等。需要代换实例。

量词的等值式

消去量词等值式

设 $D = \lbrace a_1, a_2, \ldots, a_n \rbrace$

$\forall x A(x) \Leftrightarrow A(a_1) \land A(a_2) \land \cdots \land A(a_n)$
$\exists x A(x) \Leftrightarrow A(a_1) \lor A(a_2) \lor \cdots \lor A(a_n)$

量词否定等值式

$\neg \forall x A(x) \Leftrightarrow \exists x \neg A(x)$
$\neg \exists x A(x) \Leftrightarrow \forall x \neg A(x)$

量词辖域收缩与扩张等值式

$A(x)$ 是含 $x$ 的自由出现的公式，$B$ 中不含 $x$ 的自由出现的公式。

关于全称量词的：
- $\forall x (A(x) \land B) \Leftrightarrow \forall x A(x) \land B$
- $\forall x (A(x) \lor B) \Leftrightarrow \forall x A(x) \lor B$
- $\textcolor{orange}{\forall x} (A(x) \to B) \Leftrightarrow \textcolor{orange}{\exists x} A(x) \to B$
- $\forall x (B \to A(x)) \Leftrightarrow B \to \forall x A(x)$
关于存在量词的：
- $\exists x (A(x) \land B) \Leftrightarrow \exists x A(x) \land B$
- $\exists x (A(x) \lor B) \Leftrightarrow \exists x A(x) \lor B$
- $\textcolor{orange}{\exists x} (A(x) \to B) \Leftrightarrow \textcolor{orange}{\forall x} A(x) \to B$
- $\exists x (B \to A(x)) \Leftrightarrow B \to \exists x A(x)$

量词分配等值式

$\forall x (A(x) \land B(x)) \Leftrightarrow \forall x A(x) \land \forall x B(x)$
$\exists x (A(x) \lor B(x)) \Leftrightarrow \exists x A(x) \lor \exists x B(x)$
$\exists x (A(x) \to B(x)) \Leftrightarrow \forall x A(x) \to \exists x B(x)$

形式类似的重演蕴含式

$\forall x (A(x) \lor B(x)) \Leftarrow \forall x A(x) \lor \forall x B(x)$
$\exists x (A(x) \land B(x)) \Rightarrow \exists x A(x) \land \exists x B(x)$
$$\begin{aligned}\exists x A(x) \to \forall x B(x) &\Rightarrow \forall x (A(x) \to B(x)) \newline \Rightarrow \forall x A(x) \to \forall x B(x) &\Rightarrow \exists x A(x) \to \exists x B(x)\end{aligned}$$

置换规则、换名规则、代替规则

置换规则

若 $A \Leftrightarrow B$ 则 $F(A) \Leftrightarrow F(B)$

换名规则

将公式 $A$ 中某量词辖域内的所有约束变元替换为该辖域中未出现的个体变项符号，得到的公式 $A’$ 与 $A$ 等值。

代替规则

设 $A$ 为一公式，将 $A$ 中的某个自由出现的变项用未曾出现在 $A$ 中的个体常项符号代替，得到的公式 $A’$ 与 $A$ 等值。

一阶逻辑前束范式

设 $A$ 为一阶逻辑公式，若 $A$ 的量词部分出现在公式的最前面，则称 $A$ 为前束范式。即 $A$ 可以表示为： $$Q_1 x_1 Q_2 x_2 \cdots Q_n x_n B$$ 其中 $Q_i$ 为量词，$x_i$ 为变项，$B$ 为不含量词的公式。

一阶逻辑中的任何公式都存在与之等值的前束范式

一阶逻辑的推理理论

量词规则

US：全称引入规则（Universal Specification） $$\forall x A(x) \Rightarrow A(c)$$
UG：全称推广规则（Universal Generalization） $$A(c) \Rightarrow \forall x A(x)$$
ES：存在引入规则（Existential Specification） $$A(c) \Rightarrow \exists x A(x)$$
EG：存在推广规则（Existential Generalization） $$\exists x A(x) \Rightarrow A(c)$$

自然推理系统

定义5.3 自然推理系统 $N_\mathcal{L}$ 定义如下：

字母表：同一阶语言 $\mathcal{L}$ 的字母表。
合式公式：同 $\mathcal{L}$ 的合式公式。
推理规则：基本等值式、量词规则。