4-第一章命题逻辑.ppt

第一章 命题逻辑
命题及其表示法
联结词 命题公式与翻译 真值表与等价公式
重言式与蕴含式

Propositional Logic
第17页
对偶与范式（复习）
二、范式
定义1- 一个命题公式称为合取范式，当且仅当
它具有型式：
其中 都是由命题变元或其否定所组成
的析取式。
合取范式的特点：
（1）不出现 和 （2）否定符号出现在变元前
（3）总体看是合取式 （4）每个合取项是析取式
（5）每个合取项中只包含命题变元或其否定。
3
第18页
对偶与范式（复习）
二、范式
定义1- 一个命题公式称为析取范式，当且仅当
它具有型式：
其中 都是由命题变元或其否定所组成
的合取式。
析取范式的特点：
（1）不出现 和 （2）否定符号出现在变元前
（3）总体看是析取式 （4）每个析取项是合取式
（5）每个析取项中只包含命题变元或其否定。
4
第20页
对偶与范式（复习）
二、范式
例3:求 合取范式。
例4:求 析取范式。
合取范式和析取范式的化归步骤：见书上31页
5
第20页
对偶与范式 （复习）
三、主范式
例5:试求 和 的主析取范式。
例6:试求 主析取范式。
主析取范式的化归步骤：见书上36页
(1)主析取范式
每个析取项中所有变元都要出现
每个变元只出现一次（命题变元或其否定）
6
第20页
对偶与范式 （复习）
三、主范式
定义1- n个变元的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时存在，但
两者必须出现且仅出现一次。
定义1- 对于给定的命题公式，如果有一个等价
公式，它仅由小项的析取所组成，则该等价式称为原式的主析取范式。
定理1- 在真值表中，一个公式的真值为T的指派所对应的小项的析取，即为此公式的主析取范式。
(1)主析取范式
7
第20页
对偶与范式 （复习）
三、主范式
(1)主析取范式
用两种方法求下面命题公式的主析取范式。
8
第20页
对偶与范式
三、主范式
例7:试求 的主合取范式。
例8:试求 主合取范式。
主合取范式的化归步骤：见书上38页
(2)主合取范式
每个合取项中所有变元都要出现
每个变元只出现一次（命题变元或其否定）
9
第20页
对偶与范式
三、主范式
定义1- n个变元的析取式，称作布尔析取或大项，其中每个变元与它的否定不能同时存在，但
两者必须出现且仅出现一次。
定义1- 对于给定的命题公式，如果有一个等价
公式，它仅由大项的合取所组成，则该等价式称为原式的主合取范式。
定理1- 在真值表中，一个公式的真值为F的指派所对应的大项的合取，即为此公式的主合取范式。
10