离散数学：命题逻辑

发表于 2020-03-09 更新于 2023-10-11 分类于 math Waline：阅读次数：

命题逻辑

命题

数理逻辑研究的中心问题是推理，而推理的前提和结论都是命题，因而命题是推理的基本单位

Definition

具有确切真值的陈述句成为命题(proposition)。该命题可以取一个值，称为真值。真值只有“真”和“假”两种，分别用“T”（1）或者“F”（0）表示。

一切没有判断的句子，图命令句（祈使句）、感叹句、疑问句、二义性的陈述句等都不能作为命题

复合命题

Definition

原子命题（简单命题）：不能再分解为更为简单命题的命题。

符合命题：可以分解为更为简单命题的命题。这些命题之间通过如“或者”、“并且”、“不”、“如果……则……”、“当且仅当”等这样的关联词和标点符号复合而成。

$预定：通常用大写的带或不带小标的英文字母表示命题 (包括原子命题和符合命题) A, B, C, \dots, P, Q, R, \dots, P_{i}, Q_{i}, R_{i}, \dots$

命题连接词

否定联结词

Definition

设P是任意一个命题，复合命题“非P”（或“P的否定”）成为P的否定式(negation),记作 $\neg P$

$\neg$ 是否定连接词。P当且仅当 $P$ 为假。

P $\neg P$

0 1

1 0

$\neg$ 是自然语言中“非”、“不”、“没有”等的逻辑抽象

P	$\neg P$
0	1
1	0

合取联结词

Definition

设P、Q是任意两个命题，复合命题“P并且Q”（或“P和Q”）成为P与Q的合取式(conjunction),记作 $P \land Q$ , $" \land "$ 为合取联结词。 $P \land Q$ 为真当且仅当P、Q同为真。

P Q $P \land Q$

0 0 0

0 1 0

1 0 0

1 1 1

P	Q	$P \land Q$
0	0	0
0	1	0
1	0	0
1	1	1

析取联结词

Definition

设P、Q是任意两个命题，复合命题“P或Q”称为P与Q的析取式(disjunction),记作 $P \lor Q$ , $\lor$ 为析取联结词. $P \lor Q$ 为真当且仅当P，Q至少有一个为真。

P Q $P \lor Q$

0 0 0

0 1 1

1 0 1

1 1 1

P	Q	$P \lor Q$
0	0	0
0	1	1
1	0	1
1	1	1

蕴含联结词

Definition

设P、Q是任意两个命题，复合命题“如果P，则Q”成为P与Q的蕴含式(implication),记作 $P \to Q$ , $\to$ 为蕴含联结词。 $P \to Q$ 为假当且仅当P为真且Q为假。一般把蕴含式 $P \to Q$ 中的P称为该蕴含是的前件，Q称为蕴含式的后件。

P Q $P \to Q$

0 0 1

0 1 1

1 0 0

1 1 1

P	Q	$P \to Q$
0	0	1
0	1	1
1	0	0
1	1	1

等价联结词

Definition

设P、Q是任意两个命题，复合命题“P当且仅当Q”称为P与Q等价式(quivalence),记作 $P \leftrightarrow Q$ , $\leftrightarrow$ 为等价联结词(也称作双条件联结词)。 $P \leftrightarrow Q$ 为真当且仅当P、Q同为真假。

P Q $P \leftrightarrow Q$

0 0 1

0 1 0

1 0 0

1 1 1

P	Q	$P \leftrightarrow Q$
0	0	1
0	1	0
1	0	0
1	1	1

联结词总结

P	Q	$\neg P$	$P \land Q$	$P \lor Q$	$P \to Q$	$P \leftrightarrow Q$
0	0	1	0	0	1	1
0	1	1	0	1	1	0
1	0	0	0	1	0	0
1	1	0	1	1	1	1

联结词是两个命题真值之间的联结，而不是命题内容之间的联结，因此复合命题的真值只取决于构成他们的各简单命题的真值，而与它们的内容无关，与两者之间是否有联系无关。

联结词的优先级

优先顺序:否定，合取，析取，蕴含，等价
同济联结词，按其先后顺序
若运算要求和优先次序不一致时，可使用括号；同级联结词相邻时，也可使用括号。括号中运算为最高优先级。

命题公式和真值表

命题变元

Definition

一个特定的命题是一个常值命题，它不是具有值“T”（“1”），就是具有值“F”（“0”）。

Definition

一个任意没有赋予具体内容的原子命题是一个变量命题，常称它为命题变量（或命题变元）(propositional variable)，该命题变量无具体的真值，它的变域是集合｛T，F｝。

复合命题是由原子命题与联结词构成的命题。所以，当其中的原子命题是命题变元时，此复合命题也即为命题变元的函数，且该函数的值仍为“真”或“假”值，这样的函数可形象地成为“真值函数”或者“命题公式”，此命题公式没有确切的真值。

例如： $G = P \land Q \to \neg R$

命题公式

Definition

命题验算的合式公式(well formed formula,wff),又称为命题公式(简称公式)，按以下规则生成：

命题变元本身是一个公式；（如：P，Q，R，……）

如G是公式，则 $(\neg G)$ 也是公式；（如： $\neg P, \neg Q, \neg R, \dots$ ）

如果G、H是公式，则 $(G \land H) 、 (G \lor H) 、 (G \to H) 、 (G \leftrightarrow H)$ 也是公式；(如： $P \land Q, (\neg Q) \to R, \dots$ )

仅由有限步使用规则（1）、（2）、（3）后所得到的包含命题变元、联结词和括号的符号串才是命题公式.(如： $\neg (P \land Q) \leftrightarrow R, (\neg Q \lor (P \land \neg R)) \to R, \dots$ )

如果G是含有n个命题变元 $P_{1} 、 P_{2} 、 \dots 、 P_{n}$ 的公式，可记为： $G (P_{1}, P_{2}, \dots, P_{n})$ 或简写为G。

原子命题变元时最简单的合式公式，成为原子合式公式，简称原子公式；

命题公式没有真值，只有对其命题变元进行真值指派后，方可确定命题公式的真值；

整个公式的最外层括号可以省略；公式内不影响运算顺序的括号也可以省略。

在实际应用中，为了便于储存和运算，命题公式常用二元树的方式来表达。

公式的解释

Definition

设 $P_{1} 、 P_{2} 、 P_{3} 、 \dots 、 P_{n}$ 是出现在公式G中的所有命题变元，指定 $P_{1} 、 P_{2} 、 P_{3} 、 \dots 、 P_{n}$ 一组真值，则这组真值称为G的一个解释，常记为I。

如果公式G在解释I下是真的，则称I满足G，此时I是G的成真赋值；

如果公式G在解释I下是假的，则称I弄假于G，此时I是G的成假赋值。

真值表

Definition

由公式G在其所有可能的即使下所取真值构成的表，成为G的真值表(truth table).

命题公式的分类和等价

命题公式的分类

公式G称为永真公式(重言式，tautology),如果在它的所有解释之下其真值都为真。

公式G称为永假公式(矛盾式，contradiction)，如果在它的所有解释下其真值都为“假”。有时也称为不可满足公式。

公式G称为可满足公式(satisfiable),如果它不是永假的。

关系

G是永真的当且仅当 $\neg G$ 是永假的；

G是可满足的当且仅当至少有一个解释I，使G在I下为真。

若G是永真式，则G一定是可满足式，但反之可满足时不一定是永真式；

公式的逻辑等价

Definition

设 G，H 是两个命题公式, $P_{1}, P_{2}, P_{3}, \dots, P_{n}$ 是出现在 G,H 中所有的命题变元,如果对于 $P_{1}, P_{2}, P_{3}, \dots, P_{n}$ 的 2n 个解释,G 与 H 的真值结果都相同，则称公式 G 与 H 是等价的,记作G=H。(或 $G \Leftrightarrow H$ )

充分必要条件，定理

对于任意两个公式G和H，G=H的充分必要条件是公式 $G \leftrightarrow H$ 是永真公式。

命题公式的可判定性

能否给出一个可行方法，完成对任意公式的判定类问题。(类型或等价判定)

命题公式是可判定的。

基本等价关系及其应用

基本等价关系

定理：

设G，H，S为任意的命题公式。

定理名称

$E_{1} : G \lor G = G$
$E_{2} : G \land G = G$ 幂等率

$E_{3} : G \lor H = H \lor G$ ;
$E_{4} : G \land H = H \land G$ 交换律

$E_{5} : G \lor (H \lor S) = (G \lor H) \lor S$ ;
$E_{6} : G \land (H \land S) = (G \land H) \land S$ 结合律

$E_{7} : G \lor 0 = G$ ;
$E_{8} : G \land 1 = G$ 同一律

$E_{9} : G \lor 1 = 1$ ;
$E_{10} : G \land 0 = 0$ 零率

$E_{11} : G \lor (H \land S) = (G \lor H) \land (G \lor S)$ ;
$E_{12} : G \land (H \lor S) = (G \land H) \lor (G \land S)$ 分配率

$E_{13} : G \lor (G \land H) = G$ :
$E_{14} : G \land (G \lor H) = G$ 吸收率

$E_{15} : \neg G \land G = 0$ 矛盾律

$E_{16} : \neg G \lor G = 1$ 排中律

$E_{17} : \neg (\neg G) = G$ 双重否定率

$E_{18} : \neg (G \lor H) = \neg G \land \neg H$ ;
$E_{19} : \neg (G \land H) = \neg G \lor \neg H$ 德摩根律

$E_{20} : G \to H = \neg G \lor H$ 蕴含式

$E_{21} : G \to H = \neg H \to \neg G$ 假言易位

$E_{22} : G \leftrightarrow H = (G \to H) \land (H \to G) = (\neg G \lor H) \land (\neg H \lor G)$ 等价式

$E_{23} : G \leftrightarrow H = \neg G \leftrightarrow \neg H$ 等价否定等式

$E_{24} : (G \to H) \land (G \to \neg H) = \neg G$ 归谬论

定理	名称
$E_{1} : G \lor G = G$ $E_{2} : G \land G = G$	幂等率
$E_{3} : G \lor H = H \lor G$ ; $E_{4} : G \land H = H \land G$	交换律
$E_{5} : G \lor (H \lor S) = (G \lor H) \lor S$ ; $E_{6} : G \land (H \land S) = (G \land H) \land S$	结合律
$E_{7} : G \lor 0 = G$ ; $E_{8} : G \land 1 = G$	同一律
$E_{9} : G \lor 1 = 1$ ; $E_{10} : G \land 0 = 0$	零率
$E_{11} : G \lor (H \land S) = (G \lor H) \land (G \lor S)$ ; $E_{12} : G \land (H \lor S) = (G \land H) \lor (G \land S)$	分配率
$E_{13} : G \lor (G \land H) = G$ : $E_{14} : G \land (G \lor H) = G$	吸收率
$E_{15} : \neg G \land G = 0$	矛盾律
$E_{16} : \neg G \lor G = 1$	排中律
$E_{17} : \neg (\neg G) = G$	双重否定率
$E_{18} : \neg (G \lor H) = \neg G \land \neg H$ ; $E_{19} : \neg (G \land H) = \neg G \lor \neg H$	德摩根律
$E_{20} : G \to H = \neg G \lor H$	蕴含式
$E_{21} : G \to H = \neg H \to \neg G$	假言易位
$E_{22} : G \leftrightarrow H = (G \to H) \land (H \to G) = (\neg G \lor H) \land (\neg H \lor G)$	等价式
$E_{23} : G \leftrightarrow H = \neg G \leftrightarrow \neg H$	等价否定等式
$E_{24} : (G \to H) \land (G \to \neg H) = \neg G$	归谬论

范式

Definition

命题变元或命题变元的否定称为文字。 $P, \neg P, Q, \neg Q, \dots$

有限个文字的析取成为简单析取式（或子句）。 $P \lor Q \lor R, \dots$

有限个文字的合取成为简单合取式（或短语）。 $\neg P \land Q \land R$

P与 $\neg P$ 称为互补对。

Definition

有限个简单合取式（短语）的析取式成为析取范式(disjunctive normal form);

如 $(P \land Q) \lor (\neg P \land Q)$

有限个简单析取式（子句）的合取式成为合取范式(conjunctive normal form)。

如： $(P \lor Q) \land (\neg P \lor Q)$

范式存在定理

对于任何命题公式，都存在与其等价的析取范式和合取范式。

主范式

极小项和极大项

Definition

在含有n个命题变元 $P_{1}, P_{2}, P_{3}, \dots, P_{n}$ 的短语或子句中，若每个命题变元与其否定不同时存在，但二者之一恰好出现一次且仅一次，并且出现次序与 $P_{1}, P_{2}, P_{3}, \dots, P_{n}$ 一致，则称此短语或子句为关于 $P_{1}, P_{2}, P_{3}, \dots, P_{n}$ 的一个极小项或极大项。

一般来说，若有n个命题变元，则有 $2^{n}$ 个不同的极小项和 $2^{n}$ 个不同的极大项。

极小项

没有两个不同的极小项是等价的。

每个极小项只有一组成真赋值，因此可用于给极小项编码。编码规律：命题变元与1对应，命题变元的否定与0对应。

极大项

没有两个不同的极大项是等价的。

每个极大项只有一组成假赋值，因此可用于给极大项编码。编码规律为：命题变元与0对应，命题变元的否定与1对应

性质(小写字母极小项，大写字母极大项)

$m_{i} \land m_{j} = 0$

$M_{i} \lor M_{j} = 1$ ( $i \neq j$ )

$m_{i} = \neg M_{i}$

$M_{i} = \neg m_{i}$

$⋁_{i = 0}^{2^{n} - 1} m_{i} = 1 ⋀_{i = 0}^{2^{n} - 1} M_{i} = 0$

主析取范式和主合取范式

Definition

在给定的析取范式中，若每个短语都是极小项，且按照编码从小到大的排序排列，则称该范式为主析取范式(priincipal disjunctive normal form)。

在给定的合取范式中，若每一个最大子句都是极大项，且按照编码从小到大的顺序排列，则称该范式为主合取范式(principal conjunctive normal form)。

Theorem

任何一个公式都有与之等价的主析取范式和主合取范式。

主范式求解定理

Proof

求出该公式所对应的的析取范式和合取范式

消去重复的命题变元，矛盾式和重言式；

幂等率、矛盾律、同一律、排中律、零率

主范式可用于了解公式的真值情况，进行公式类型的判定以及等价关系的判定。

如果主析取范式包含所有的极小项，该公式为永真公式

如果主合取范式包含所有的极大项，该公式为永假公式

若两个公式具有相同的主析取范式或主合取范式，则两公式等价

基本推理形式和蕴含关系

推理的基本形式

所谓推理，是指从一组前提合乎逻辑的退出结论的思维过程。在这里，我们使用命题公式来表达前提和结论。

Definition $设 G_{1}, G_{2}, \dots, G_{n}, H 是公式，称 H 是 G_{1}, G_{2}, \dots, G_{n} 的逻辑结果当且仅当对任意解释 I 如果 I 使得 G_{1} \land G_{2} \land G_{3} \land \dots \land G_{n} 为真，则 I 也会使 H 为真。记为 G_{1}, G_{2}, \dots, G_{n} \Rightarrow H . " \Rightarrow " 成为蕴含关系。此时称 G_{1}, G_{2}, \dots, G_{n} \Rightarrow H 为有效的，否则成为无效的。 G_{1}, G_{2}, \dots, G_{n} 成为一组前提，有时用集合 Γ 来表示，记作 Γ = {G_{1}, G_{2}, \dots, G_{n}}, H 成为结论。此时也成 H 是前提集合 Γ 的逻辑结果。记为 Γ \Rightarrow H 。$ Theorem

公式H是前提集合 $Γ = {G_{1}, G_{2}, \dots, G_{n}}$ 的逻辑结果当且仅当（ $G_{1} \land G_{2} \land \dots \land G_{n} \to H$ ）为永真公式。

推理定律-基本蕴含关系

Theorem

设G，H，I为任意的命题公式。

规则表示

1.简化规则 $I_{1} : G \land H \Rightarrow G$
$I_{2} : G \land H \Rightarrow H$

2.添加规则 $I_{3} : G \Rightarrow G \lor H$
$I_{4} : H \Rightarrow G \lor H$

3.合取引入规则 $I_{5} : G, H \Rightarrow G \land H$

4.选言三段论 $I_{6}; G \lor H, \neg G \Rightarrow H$
$I_{7} : G \lor H, \neg H \Rightarrow G$

5.假言推定原则 $I_{8} : G \to H, G \Rightarrow H$

6.否定后件式 $I_{9} : G \to H, \neg H \Rightarrow \neg G$

7.假言三段论 $I_{10} : G \to H, H \to I \Rightarrow G \to I$

8.二难推论 $I_{11} : G \lor H, G \to I, H \to I \Rightarrow I$

规则	表示
1.简化规则	$I_{1} : G \land H \Rightarrow G$ $I_{2} : G \land H \Rightarrow H$
2.添加规则	$I_{3} : G \Rightarrow G \lor H$ $I_{4} : H \Rightarrow G \lor H$
3.合取引入规则	$I_{5} : G, H \Rightarrow G \land H$
4.选言三段论	$I_{6}; G \lor H, \neg G \Rightarrow H$ $I_{7} : G \lor H, \neg H \Rightarrow G$
5.假言推定原则	$I_{8} : G \to H, G \Rightarrow H$
6.否定后件式	$I_{9} : G \to H, \neg H \Rightarrow \neg G$
7.假言三段论	$I_{10} : G \to H, H \to I \Rightarrow G \to I$
8.二难推论	$I_{11} : G \lor H, G \to I, H \to I \Rightarrow I$

自然演绎法推理

推理规则

Theorem

规则P（称为前提引用规则）：在推导过程中，可随时引入前提集合中的任意前提；

规则T（称为逻辑结果引用规则）：在推导过程中，可以随时引入公式S，该公式S是由其前的一个或多个公式推导出来的逻辑结果。

规则CP（称为附加前提规则）：如果能从给定的前提集合 $Γ$ 与公式P推导出S，则能从此前提集合 $Γ$ 推导出 $P \to S$

自然演绎法

Definition

从前提集合 $Γ$ 推出结论H的一个演绎是构造命题公式的一个有线序列： $H_{1}, H_{2}, H_{3}, \dots, H_{n - 1}, H_{n}$ 其中， $H_{i}$ 或者是 $Γ$ 中的某个前提，或者前面某些 $H_{j} (j < i)$ 的有效结论，并且 $H_{n}$ 就是H，则称该公式H是该演绎的有效结论，或者称从前提 $Γ$ 能够演绎出来结论H来。

命题逻辑

命题

复合命题

命题连接词

否定联结词

合取联结词

析取联结词

蕴含联结词

等价联结词

联结词总结

联结词的优先级

命题公式和真值表

命题变元

命题公式

公式的解释

真值表

命题公式的分类和等价

命题公式的分类

公式的逻辑等价

基本等价关系及其应用

基本等价关系

范式

范式存在定理

主范式

极小项和极大项

主析取范式和主合取范式

主范式求解定理

基本推理形式和蕴含关系

推理的基本形式

推理定律-基本蕴含关系

自然演绎法推理

推理规则

自然演绎法

预览: