离散数学 第三篇 数理逻辑01 命题逻辑

离散数学

---

命题连接词

注意：
合取与析取不要搞混了
善意推定：
$1 \rightarrow 1$,然而，如果前件为0

$$0 \rightarrow 1 (or) 0 \rightarrow 0$$ 均为真

优先级：在上图中，优先级顺序为

命题公式

永真公式

永假公式

可满足公式

即：
$\neg$永假$\leftrightarrow$可满足

等价关系$=$与等价连接词$\leftrightarrow$的区别

命题公式的基本等价关系

联结词的完备集

范式

文字：
命题变元或其否定

子句（析取式）：
有限个文字的析取

短语（合取式）：
有限个文字的合取

互补对
命题变元及其否定

析取范式

有限个短语的析取式

合取范式

有限个子句的合取式

极小项（$\wedge$）

短语（合取式）中命题变元及其否定有且只出现一次

极大项 ($\vee$)

主析取范式

主合取范式

主范式的简单例子

原公式：$(P \rightarrow Q)\rightarrow(Q \wedge R)$
主析取范式：

$$(P \wedge \neg Q \wedge R)\vee(P \wedge \neg Q \wedge \neg R)\vee(P \wedge Q \wedge R)\vee(\neg P \wedge Q \wedge R)$$

总结：一个括号里面每个命题变元或者其否定，必须要有一个（有且只有一个）

求主范式的方法

公式法

利用两个公式

易错点：
去掉括号外面的$\neg$时记得要变号（合取变析取，析取变合取）

真值表法：

真值表法求范式的例子：
求该公式的主析取范式、主合取范式：$(P \rightarrow Q)\Leftrightarrow R$

$P$	$Q$	$R$	$P \rightarrow Q$	$(P \rightarrow Q)\Leftrightarrow R$
0	0	0	0	0
1	0	0	0	1
0	1	0	1	0
0	0	1	1	1
1	1	0	1	0
1	0	1	0	0
0	1	1	1	1
1	1	1	1	1

极小项（合取）：

$$(P,-Q,-R),(-P,-Q,R),(-P,Q,R),(P,Q,R)$$
取析取即可得主析取范式

极大项（析取）：

$$(P,Q,R),(P,-Q,R),(-P,-Q,R),(-P,Q,-R)$$
取合取即可主合取范式

主析取范式$\rightarrow$主合取范式

主合取范式$\rightarrow$主析取范式

同理

范式的应用

判断永真or永假

（1） 永真
$G$为永真$\Leftrightarrow$ $G$的合取范式有：每个子句（括号里面的）同时包含至少一个变元及其否定

$G$为永真$\Leftrightarrow$ $G$的主析取范式有：所有的极小项$\Leftrightarrow$ 没有主合取范式

（2） 永假
$G$为永假$\Leftrightarrow$ $G$的析取范式有：每个短语（括号里面的）同时包含至少一个变元及其否定

$G$为永假$\Leftrightarrow$ $G$的主合取范式有：所有的极大项$\Leftrightarrow$ 没有主析取范式

（3）等价
$G$与$R$为等价$\Leftrightarrow$ $G$与$R$对应的主合取范式等价$\Leftrightarrow$$G$与$R$对应的主析取范式等价