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

命题连接词

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

均为真

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

命题公式

永真公式

永假公式

可满足公式

**即：
¬$\mathrm{\neg }$永假↔$\leftrightarrow$可满足**

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

命题公式的基本等价关系

联结词的完备集

范式

文字：
命题变元或其否定

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

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

互补对
命题变元及其否定

析取范式

有限个短语的析取式

合取范式

有限个子句的合取式

极小项（∧$\wedge$）

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

极大项 (∨$\vee$)

主析取范式

主合取范式

主范式的简单例子

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

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

求主范式的方法

公式法

利用两个公式

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

真值表法：

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

P$P$	Q$Q$	R$R$	P→Q$P\to Q$	(P→Q)⇔R$(P\to Q)\iff 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

极小项（合取）：

取析取即可得主析取范式

极大项（析取）：

取合取即可主合取范式

主析取范式→$\to$主合取范式

主合取范式→$\to$主析取范式

同理

范式的应用

判断永真or永假

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

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

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

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

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

总结：

搬运自我的markdown笔记：
https://www.zybuluo.com/Arbalest-Laevatain/note/1172732
点击上面这个链接，可以留下批注方便交流