总结-数理逻辑

1、命题逻辑q 数理逻辑研究的数理逻辑研究的中心问题中心问题是是推理推理。q 推理的推理的前提前提和和结论结论都是都是表达判断表达判断的的陈述句陈述句。q 命题：命题：能能判断真假判断真假而而不是可真可假不是可真可假的的陈述句陈述句。v 真值、真命题、假命题、原子命题、复合命题真值、真命题、假命题、原子命题、复合命题v 感叹句、疑问句、祈使句都不能称为命题。感叹句、疑问句、祈使句都不能称为命题。v 判断结果不唯一确定的陈述句不是命题。判断结果不唯一确定的陈述句不是命题。v 陈述句中的悖论不是命题。陈述句中的悖论不是命题。q ,pq ppqpqpqpq001001101101101000100110

2、1111命题逻辑q 命题的概念和判断，熟练地将复合命题符号化。命题的概念和判断，熟练地将复合命题符号化。q 深刻理解各联结词的逻辑含义，要特别注意蕴涵联结的应用，要弄清深刻理解各联结词的逻辑含义，要特别注意蕴涵联结的应用，要弄清三个问题：三个问题： v pq 的逻辑关系的逻辑关系 v pq 的真值的真值 v pq 的灵活的叙述方法的灵活的叙述方法q 合式公式合式公式q 公式的类型：重言式、矛盾式、可满足式公式的类型：重言式、矛盾式、可满足式q 会写真值表，求公式的成真赋值和成假赋值。会写真值表，求公式的成真赋值和成假赋值。数理逻辑命题逻辑q 等值式与等值演算。等值式与等值演算。q 基本的等值式

3、，其中含：双重否定律、幂等律、交换律、结合律、分基本的等值式，其中含：双重否定律、幂等律、交换律、结合律、分配律、德配律、德摩根律、吸收律、零律、同一律、排中律、矛盾律、蕴含等摩根律、吸收律、零律、同一律、排中律、矛盾律、蕴含等值式、等价等值式、假言易位、等价否定等值式、归谬论。值式、等价等值式、假言易位、等价否定等值式、归谬论。q 与主析取范式及主合取范式有关的概念：简单合取式、简单析取式、与主析取范式及主合取范式有关的概念：简单合取式、简单析取式、析取范式、合取范式、极小项、极大项、主析取范式、主合取范式。析取范式、合取范式、极小项、极大项、主析取范式、主合取范式。 求给定公式范式的步骤求

4、给定公式范式的步骤(1)消去联结词消去联结词、(若存在若存在)。AB ABAB (AB)(AB)(2)否定号的消去否定号的消去(利用双重否定律利用双重否定律)或内移或内移(利用德摩根律利用德摩根律)。A A(AB) AB(AB) AB(3)利用分配律：利用利用分配律：利用对对的分配律求析取范式，的分配律求析取范式， 对对的分配律求合取范式。的分配律求合取范式。A(BC) (AB)(AC)A(BC) (AB)(AC)求公式A的主析取范式的方法与步骤方法一、等值演算法方法一、等值演算法(1)化归为析取范式。化归为析取范式。 (2)除去析取范式中所有永假的析取项。除去析取范式中所有永假的析取项。(3

5、)将析取式中重复出现的合取项和相同的变元合并。将析取式中重复出现的合取项和相同的变元合并。(4)对合取项补入没有出现的命题变元，即添加如对合取项补入没有出现的命题变元，即添加如(pp)式，然后应用式，然后应用分配律展开公式。分配律展开公式。方法二、真值表法方法二、真值表法(1)写出写出 A 的真值表。的真值表。(2)找出找出 A 的成真赋值。的成真赋值。(3)求出每个成真赋值对应的极小项（用名称表示），按角标从小到大求出每个成真赋值对应的极小项（用名称表示），按角标从小到大顺序析取。顺序析取。求公式A的主合取范式的方法与步骤方法一、等值演算法方法一、等值演算法(1)化归为合取范式。化归为合取范

6、式。 (2)除去合取范式中所有永真的合取项。除去合取范式中所有永真的合取项。(3)将合取式中重复出现的析取项和相同的变元合并。将合取式中重复出现的析取项和相同的变元合并。(4)对析取项补入没有出现的命题变元，即添加如对析取项补入没有出现的命题变元，即添加如(pp)式，然后应用式，然后应用分配律展开公式。分配律展开公式。方法二、真值表法方法二、真值表法(1)写出写出 A 的真值表。的真值表。(2)找出找出 A 的成假赋值。的成假赋值。(3)求出每个成假赋值对应的极大项（用名称表示），按角标从小到大求出每个成假赋值对应的极大项（用名称表示），按角标从小到大顺序析取。顺序析取。推理定律-重言蕴含式(

7、1) A AB 附加律附加律(2) AB A 化简律化简律(3) (AB)A B 假言推理假言推理(4) (AB)B A 拒取式拒取式(5) (AB)B A 析取三段论析取三段论 (6) (AB) (BC) (AC) 假言三段论假言三段论(7) (AB) (BC) (A C) 等价三段论等价三段论(8) (AB)(CD)(AC) (BD) 构造性二难构造性二难 (AB)(AB)(AA) B 构造性二难构造性二难 (特殊形式特殊形式)(9)(AB)(CD)(BD) (AC) 破坏性二难破坏性二难 自然推理系统的推理规则(1) 前提引入规则前提引入规则(2) 结论引入规则结论引入规则(3) 置换规

8、则置换规则(4)假言推理规则假言推理规则 AB A B(5)附加规则附加规则 A A B(6)化简规则化简规则 A B A(7)拒取式规则拒取式规则 AB B A(8) 假言三段论规假言三段论规则则 AB BC AC(9)析取三段论规则析取三段论规则 A B B A(10)构造性二难推理规则构造性二难推理规则 AB CD A C B D (11)破坏性二难推理规则破坏性二难推理规则 AB CD BD AC(12) 合取引入规则合取引入规则 A B A B命题逻辑的推理q 推理的形式结构推理的形式结构推理的前提推理的前提推理的结论推理的结论推理正确推理正确q 判断推理是否正确的方法判断推理是否正

9、确的方法真值表法真值表法等值演算法等值演算法主析取范式法主析取范式法 q 对于正确的推理，在自然推理系统对于正确的推理，在自然推理系统P中构造证明中构造证明 自然推理系统自然推理系统P的定义的定义自然推理系统自然推理系统P的推理规则的推理规则附加前提证明法附加前提证明法归谬法归谬法谓词逻辑q 三个基本要素：三个基本要素：个体词个体词、谓词谓词和和量词量词。q 要求准确地将给出的命题符号化：要求准确地将给出的命题符号化：当给定个体域时，在给定个体域内将命题符号化。当给定个体域时，在给定个体域内将命题符号化。当没给定个体域时，应在全总个体域内符号化。当没给定个体域时，应在全总个体域内符号化。在符号

10、化时，当引入特性时，注意全称量词与蕴含联结词的搭配，在符号化时，当引入特性时，注意全称量词与蕴含联结词的搭配，存在量词与合取联结词的搭配。存在量词与合取联结词的搭配。 q 公式类型：逻辑有效式、矛盾式、可满足式。公式类型：逻辑有效式、矛盾式、可满足式。 q 闭式的性质：在任何解释下均为命题。闭式的性质：在任何解释下均为命题。 q 对给定的解释，会判别公式的真值或不能确定真值。对给定的解释，会判别公式的真值或不能确定真值。一阶逻辑中的重要等值式q 消去量词等值式消去量词等值式设个体域为有限集设个体域为有限集 D= a1, a2, an , 则有则有(1) x A(x) A(a1) A(a2) A

11、(an) (2) x A(x) A(a1) A(a2) A(an) q 量词否定等值式量词否定等值式设设 A(x) 是任意的含自由出现个体变项是任意的含自由出现个体变项 x 的公式，则的公式，则(1) xA(x) x A(x)(2) xA(x) x A(x)q 量词分配等值式量词分配等值式设设 A(x), B(x) 是任意的含自由出现个体变项是任意的含自由出现个体变项 x 的公式，则的公式，则(1) x(A(x)B(x) xA(x) xB(x)(2) x(A(x)B(x) xA(x) xB(x)一阶逻辑中的重要等值式q 量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式设设 A(x) 是任意的含

12、自由出现个体变项是任意的含自由出现个体变项 x 的公式，的公式，B 中不含中不含 x 的出现的出现，则，则 (1) x (A(x)B ) xA(x)B x (A(x)B) xA(x)B x (A(x)B) xA(x)B x (BA(x) B xA(x) (2) x (A(x)B) xA(x)B x (A(x)B) xA(x)B x(A(x)B) xA(x)B x(BA(x) B xA(x)一阶逻辑q 置换规则置换规则q 换名规则：约束变项换名规则：约束变项q 代替规则：自由出现的个体变项代替规则：自由出现的个体变项q 前束范式（形式可以不唯一）前束范式（形式可以不唯一）Q1x1 Q2 x2 Q

13、k xk B其中其中Qi ( 1 i k )为为 或或 ，B为不含量词的公式为不含量词的公式。q 求前束范式的过程，就是求前束范式的过程，就是制造量词辖域可以扩大的条件制造量词辖域可以扩大的条件，进行量词辖域进行量词辖域扩大扩大。消去量词和引入量词的规则q 全称量词消去规则全称量词消去规则(UI、 -)q 全称量词引入规则全称量词引入规则 (UG、 + )q 存在量词引入规则存在量词引入规则 (EG、 + )q 存在量词消去规则存在量词消去规则 (EI、 - )A(c)xA(x)A(y)xA(x)或xA(x)A(y)xA(x)A(c)A(c)xA(x)v 一定对前束范式才能使用一定对前束范式才

14、能使用UI、UG、EI、EG规则，对不是前束范式的规则，对不是前束范式的公式要使用它们，一定先求出公式的前束范式。公式要使用它们，一定先求出公式的前束范式。v 在同一推理的证明中，如果既要使用在同一推理的证明中，如果既要使用 UI 规则，又要使用规则，又要使用 EI 规则，规则，一一定要先使用定要先使用EI规则，后使用规则，后使用 UI 规则，而且规则，而且 UI 规则使用的个体常项一规则使用的个体常项一定是定是EI规则中使用过的。规则中使用过的。例题q 求主合取范式和主析取范式（略）求主合取范式和主析取范式（略）q 在自然推理系统在自然推理系统 P 中证明推理中证明推理前提：前提：p(qr)

15、, pq结论：结论： rsq 在自然推理系统在自然推理系统 P 中，构造用自然语言描述的推理中，构造用自然语言描述的推理v 若张超与李志都是计算机系学生，则王红是中文系学生。若王红是若张超与李志都是计算机系学生，则王红是中文系学生。若王红是中文系学生，则她爱看小说，可是，王红不爱看小说，张超是计算中文系学生，则她爱看小说，可是，王红不爱看小说，张超是计算机学生。所以，李志不是计算机学生。机学生。所以，李志不是计算机学生。v 若若 n 是偶数并且大于是偶数并且大于5，则，则 m 是奇数。只有是奇数。只有 n 是偶数，是偶数，m 才大于才大于6。n大于大于5。所以，若。所以，若 m 大于大于6，则，则 m 是奇数。是奇数。q 将下列命题符号化将下列命题符号化v 任意的偶数任意的偶数 x 与与 y 都有大于都有大于1的公约数的公约数v 存在奇数存在奇数 x 与与 y 没有大于没有大于1的公约数的公约数例题q 在自然推理系统在自然推理系统 N 中构造用自然语言描述的推理的证明中构造用自然语言描述