离散数学笔记（2）——命题逻辑（2）

wzf2000
2019年9月17日

离散数学笔记（2）——命题逻辑（2）

命题逻辑

重言蕴涵式

重要的重言蕴涵式

$P \land Q \Rightarrow P,P \land Q \Rightarrow Q$

$P,Q \Rightarrow P \land Q$

$\lnot P \land (P \lor Q) \Rightarrow Q$

$P \land (P \rightarrow Q) \Rightarrow Q$

$\lnot Q \land (P \rightarrow Q) \Rightarrow \lnot P$

$(P \rightarrow Q) \land (Q \rightarrow R) \Rightarrow P \rightarrow R$

性质

自反性、传递性、反对称性等

其他联结词

与非：$P \uparrow Q = \lnot (P \land Q)$

或非：$P \downarrow Q = \lnot(P \lor Q)$

条件否定：$P \mathop{\rightarrow}\limits^c Q = \lnot(P \rightarrow Q)$

等价公式的对偶性

对偶式

在一个只含联结词 $\lnot,\lor,\land$ 的公式 $A$ 中（之后两条默认成立），将 $\lor,\land$ 互换，$T,F$ 互换，其他不变，得到 $A^ *$，称 $A$ 和 $A^ *$ 互为对偶式。

用对偶式求公式的否定

$\lnot A(P_1,\cdots,P_n) = A^*(\lnot P_1,\cdots,\lnot P_n)$

对偶原理

如果 $A(P_1,\cdots,P_n) = B(P_1,\cdots,P_n)$，则 $A^*(P_1,\cdots,P_n) = B^*(P_1,\cdots,P_n)$

推论：若 $A$ 是重言式，则 $A$ 必为矛盾式。

范式

只含有 $\lnot,\lor,\land$。

合取式与析取式

合取式：用 $\land$ 联结命题变元或变元的否定构成的式子。

析取式：用 $\lor$ 联结命题变元或变元的否定构成的式子。

$P,\lnot P$ 两者均可看成。

析取范式与合取范式

析取范式：公式 $A$ 如果写为如下形式：$A_1 \lor A_2 \lor \cdots \lor A_n(n \ge 1)$ 其中每个 $A_i$ 是合取式，称之为 $A$ 的析取范式。

合取范式：公式 $A$ 如果写为如下形式：$A_1 \land A_2 \land \cdots \land A_n(n \ge 1)$ 其中每个 $A_i$ 是析取式，称之为 $A$ 的合取范式。

$P \lor Q \lor R$ 两者均可看成。

析取范式与合取范式的求法

范式定理：任一命题公式都存在与之等值的析取范式和合取范式。

求法：

1. 先用相应公式去掉 $\rightarrow$ 和 $\leftrightarrow$
2. 用德-摩根定律将 $\lnot$ 后移到命题变元之前
3. 用分配律、结合律、幂等律等公式进行整理，使之成为所要求的形式。

主析取范式

小项：在一个有 $n$ 个命题变元的合取式中，每个变元或该变元的否定必出现且仅出现一次，称这个合取式为小项。

每一组指派有且只有一个小项为 $T$。

析取范式 $A_1 \lor A_2 \lor \cdots \lor A_n$ 其中每个 $A_i$ 均为小项，称之为主析取范式。

主合取范式

大项：在一个有 $n$ 个命题变元的析取式中，每个变元或该变元的否定必出现且仅出现一次，称这个析取式为大项。

每一组指派有且只有一个大项为 $F$。

合取范式 $A_1 \land A_2 \land \cdots \land A_n$ 其中每个 $A_i$ 均为大项，称之为主合取范式。

求法

1. 列真值表
   1. 定理：在真值表中，一个公式的真值为 $T$ 的指派所对应的小项的析取，即为此公式的主析取范式。
   2. 定理：在真值表中，一个公式的真值为 $F$ 的指派所对应的大项的合取，即为此公式的主合取范式。
2. 公式的等价变换
   1. 先写出对应的析（合）取范式
   2. 补全缺少的变元，用永真（假）式联结
   3. 用分配律等公式加以整理

命题逻辑推理

推理

根据一个或几个已知的判断得出一个新的判断的思维过程。称已知的判断为前提。得到的新的判断为前提的有效结论。

令 $H_1,H_2,\cdots,H_n$ 是已知的命题公式，若有 $H_1 \land H_2 \land \cdots \land H_n \Rightarrow C$，则称 $C$ 是 $H_1,H_2,\cdots,H_n$ 的有效结论，简称结论。

规则

规则 P（引入前提规则）

在推理过程中，可以随时引入前提。

规则 T（引入结论规则）

在推理过程中，如果前面有一个或几个公式永真蕴涵公式 $S$，则可将 $S$ 纳入推理过程中。

规则 CP

如果 $H_1 \land H_2 \land \cdots \land H_n \land R \Rightarrow S$，则 $H_1 \land H_2 \land \cdots \land H_n \Rightarrow R \rightarrow S$

三种推理方法

直接推理、条件论证及反证法

直接推理

格式中包含步骤号，给定前提或得出的结论，推理时所用规则，此结论是从哪几步得到的以及所用公式。

（$I$：蕴涵式，$E$：等价式）

条件论证

反证法

主要思想：假设结论不成立，可以推出矛盾的结论(矛盾式)。

定义：设 $H_1,H_2,\cdots,H_n$ 为命题公式，$P_1,P_2,\cdots,P_m$ 是公式中的命题变元，如果对所有命题变元至少有一种指派，使得 $H_1 \land H_2 \land \cdots \land H_n$ 的真值为 $T$，则称公式集合 ${H_1,H_2,\cdots,H_n}$ 是相容的（也称是一致的）；如果对所有命题变元每一种指派，都使得 $H_1 \land H_2 \land \cdots \land H_n$ 的真值为 $F$，则称公式集合 ${H_1,H_2,\cdots,H_n}$ 是不相容的（也称是不一致的）。

定理：若要证明相容的公式集合 ${H_1,H_2,\cdots,H_n}$ 可以推出公式 $C$，只要证明 $H_1 \land H_2 \land \cdots \land H_n \land \lnot C$ 是个矛盾式即可。

证明推理不正确：取合适真值使得条件为真，结论为假。

 离散数学 笔记