1 谓词逻辑初步
谓词逻辑初步 1
回顾 2 问题1：什么是命题逻辑？ -与命题真假有关的判断 问题2：如何判断命题表达式的真假？ 。真值表与逻辑等价 问题3：如何判定命题可满足？ -NPC完全问题；范式与主范式
回顾 2 问题1：什么是命题逻辑？ - 与命题真假有关的判断 问题2：如何判断命题表达式的真假？ - 真值表与逻辑等价 问题3：如何判定命题可满足？ - NPC完全问题；范式与主范式
本节提要 问题1：如何基于命题逻辑进行推理？ 问题2：什么是（一阶）谓词逻辑？ 问题3：如何基于谓词逻辑进行推理？
本节提要 问题1：如何基于命题逻辑进行推理？ 问题2：什么是(一阶)谓词逻辑？ 问题3：如何基于谓词逻辑进行推理？
引例 如果税收下降，收入一定上升。 现在我的收入 上升了，所以，一定是税收下降了！ 口定义命题P:税收下降；命题Q:收入上升 口前提： 口P→Q；Q 口结论： 推理过程的不正确， 口P 不能保证任何结果的正确性 口推理过程：
引例 如果税收下降，收入一定上升。现在我的收入 上升了，所以，一定是税收下降了！ 定义命题P：税收下降；命题Q：收入上升 前提： P → Q；Q 结论： P 推理过程: ? 推理过程的不正确， 不能保证任何结果的正确性
推理规则 口前提：一组命题公式A1uA2,Ak 口结论：一个命题公式B ▣ 推理正确”当且仅当： (A,个A2N·人A)→B是永真式 口说明： 口B称为一个有效结论 对诸A和B中出现的命题变元的任一指派，若前 提的合取式为真，则结论必为真 若前提的合取式为假，推理总是正确，或者说， 推理正确并不保证结论正确
推理规则 前提：一组命题公式A1 , A2 , …, Ak 结论：一个命题公式B “推理正确”当且仅当： （A1 A2 … Ak )→B是永真式 说明： B称为一个有效结论 对诸Ai和B中出现的命题变元的任一指派，若前 提的合取式为真，则结论必为真 若前提的合取式为假，推理总是正确，或者说， 推理正确并不保证结论正确
例 6 口小王不管上不上学都不睡觉，小王今天睡觉了。 所以小王即上学又不上学。 口P:小王上学，Q:小王睡觉 口前提： 口(PVP)→Q;Q 口结论： 推理正确，结论有效； 口PAP 前提不一致导致结论不正确
例 小王不管上不上学都不睡觉，小王今天睡觉了。 所以小王即上学又不上学。 P: 小王上学，Q：小王睡觉 前提： (P∨P) → Q；Q 结论： P∧P 6 推理正确，结论有效； 前提不一致导致结论不正确
例 消解 AVB,AVC→BVC
例
常用的蕴涵永真式 8 1.A->(AvB) 蕴含永真式在逻辑推理 2.(AΛB)→A 3.(A→B)ΛA)>B 中相当重要 4.(A>B)∧B)>A 5.(AVB)ΛB)>A 6.(A→B)Λ(B→C)→(A→C) 7.(A←>B)(B←→C)→(A←→C) 8.(A>B)Λ(C>D)Λ(AVC)>(BVD) (A→B)Λ(A→B)>B 9.(A→B)A(C>D)Λ(BVD)>(AVC)
常用的蕴涵永真式 8 9.(( ) ( ) ( )) ( ) (( ) ( )) 8.(( ) ( ) ( )) ( ) 7.(( ) ( )) ( ) 6.(( ) ( )) ( ) 5.(( ) ) 4.(( ) ) 3.(( ) ) 2.( ) 1. ( ) A B C D B D A C A B A B B A B C D A C B D A B B C A C A B B C A C A B B A A B B A A B A B A B A A A B → → → → → → → → → → → → → → → → → → → → → → 蕴含永真式在逻辑推理 中相当重要
蕴涵永真式与导出的推理规则 9 附加律 1.A→(AVB) 化简律 2.(AΛB)→A 假言推理 3.(A→B)ΛA→B 取拒式 4.(A→B)ΛB)→A 析取三段论5.(AVB)∧一B)→A 假言三段论 6.(A→B)A(B→C)→(A→C) 等价三段论7.(A←→B)Λ(B←→C)→(A←>C) 构造性二难8.(A→B)A(C→D)A(AVC)→(BVD) (A→B)Λ(A→B)→B 破坏性二难9.(A→B)∧(C→D)∧（一BVD)→（一AVC)
蕴涵永真式与导出的推理规则 9 9.(( ) ( ) ( )) ( ) (( ) ( )) 8.(( ) ( ) ( )) ( ) 7.(( ) ( )) ( ) 6.(( ) ( )) ( ) 5.(( ) ) 4.(( ) ) 3.(( ) ) 2.( ) 1. ( ) A B C D B D A C A B A B B A B C D A C B D A B B C A C A B B C A C A B B A A B B A A B A B A B A A A B → → → → → → → → → → → → 附加律 化简律 假言推理 取拒式 析取三段论 假言三段论 等价三段论 构造性二难 破坏性二难
论证 10 An argument in propositional logic is a sequence of propositions.All but the final proposition in the argument are called premises and the final proposition is called the conclusion.An argument is valid if the truth of all its premises implies that the conclusion is true. “如果我是马云，那么我给各位每人发一辆法拉利。 “我是马云。” 我给各位每人发一辆法拉利
论证 An argument in propositional logic is a sequence of propositions. All but the final proposition in the argument are called premises and the final proposition is called the conclusion. An argument is valid if the truth of all its premises implies that the conclusion is true. 10 “如果我是教师，那么我要上课。” “我是教师。” ∴“我要上课。” “如果我是马云，那么我给各位每人发一辆法拉利。” “我是马云。” ∴“我给各位每人发一辆法拉利