离散数学课程报告
命题公式的类型定义
永真式（重言式）：命题公式A在各种赋值下真值永远为1 可满足式：
命题公式A在各种赋值下有 0或1
永假式（矛盾式）：命题公式A在各种赋值下真值永远为0
判断命题公式类型的方法
p 1 1 0 0
真值表法 例：p?(p?q)?p q 1 0 1 0 公式法
(p?q) p?(p?q) 1 0 0 0 1 1 0 0
例：(p?r)?(q?r)?(p?q)?r
(p?r)?(q?r)??p?r??q?r??(p?q)?r?(p?q)?r
主析取范式
定义
如果含n个命题变元的命题公式的析取范式的每个合取式全是极小项，则称该析取范式为主析取范式。
步骤
给出命题A 求A的析取范式A’
若A’的某合取式B不是极小项，则补入没有出现的变元。 消去重复出现的命题变项、矛盾式及重复出现的极小项
主合取范式
定义
如果含n个命题变元的命题公式的析取范式的每个合取式全是极大项，则称该析取范式为主合取范式。
步骤
给出命题A 求A的合取范式A’
若A’的某析取式B不是极大项，则补入没有出现的变元。 消去重复出现的命题变项、矛盾式及重复出现的极大项
例：求命题公式??q?r??(p?q) 的主析取范式和主合取范式
主析取范式：
??q?r??(p?q)?(p?r)?(p?q)?(q?p)?(p?r)?(?p?q)?(?q?p)
?p?(?p?q)?(?q?p)?r?(?p?q)?(?q?p)、
?(p??p??q)?(p??p?q)?(p?q??q)?(p?q?p)?(r??p??q)?(r??p?p)?(r?q??q)?(r?q?p)
?(p?q??r)?(?p??q?r)??(p?q?r)
主合取范式：
??q?r??(p?q)?(p?r)?(p?q)?(q?p)?(p?r)?(?p?q)?(?q?p) ?(p?r)??q??q??(?p?q)??r??r??(?q?p)??r??r?
?(p?q?r)?(?p?q?r)?(p??q?r)?(p??q?r)?(?p?q??r)?(p??q??r)
命题演算的常用推理证明方法
推理定律
1．??∧?????
p?q?q （化简）
2. q?p?q p?p?q
（附加） （假言推理） （拒取式） 析取三段论 合取
3. p,p?q?q 4. ?q,p?q??p 5. ?p,p?q?q 6. p,q?p?q
7. p?q,q?r?p?r 假言三段论 8. p?q,q?r?p?r 等价三段论 9. p?q,r?s,p?r?q?s 构造性二难
归结式
10. p?q,?p?r?q?r 推理证明方法
1. 真值表法
证明前提p,q,可以推出结论p?q。 p q p?q p?q?p?q 0 0 1 1 2. 等价演算法
1 0 1 0 0 0 1 0 1 1 1 1 由真值表可知，p?q?p?q 是重言式，所以前提p,q可以推出p?q
证明?p是?q和p?q的结论
?q?(p?q)??p??(?q?(?p?q))?q?q??(?p?q)??p ?q?(p??q)??p?(q?p??p)?(q??q??p)?1?1?1
3. 演绎法(从前提（假设）出发，一句公认的推理规则和推理定理，推导出结论)
命题演算的推理系统：推理规则?推理定理?基本等价公式 推理规则
1） 前提引入规则 2） 结论引入规则
3） 置换规则：子公式可以用等值的公式置换。
4） CP规则（附加前提规则）：如果推出的结论形为P?Q，则
可以把P放到前提中去，设法推出Q即可。
例： 证明p?r,q?s,p?q?r?s。
1) p?q 2) p 3) q 4) p?r 5) r 6) q?s 7) s
8) r?s
4. 附加前提证明法
（p?(q?r))?(q?(r?s))?p?(q?s)成立。 例：证明，
1) p
cp规则 附加 化简
2) p?q 3) q
4) p?(q?r) 5) q?r
前提引入规则
1），4）假言推理 前提引入 3），6）假言推理 5），7）假言三段论
6) q?(r?s) 7) r?s 8) q?s
证明方法）
5. 间接推理法（归谬法）（把推出的结论否定后与原来的前提一起使用推出矛盾结论的
1) ?s
2) r?s 3) ?r 4) ?q?r 5) ?q
否定结论
前提引入 1），2）拒取式 前提引入
3），4）析取三段论 前提引入 化简
6) ?p?q 7) q 8) 0
5），6）合取
证明：?p?q,?q?r,r?s,p?s
6. 归结证明法（前提和结论必须被表示为子句（子句是变元或其否定的析取）对于非子句，
可以用一个或多个等价的子句的语句替换它）
例：证明p?r,q?s,p?q?r?s。
离散数学期中课程报告
