《离散数学》第2章谓词逻辑

第二章谓词逻辑,第一节谓词逻辑基本概念,内容：,个体词，谓词，量词，命题符号化。,重点：,1、掌握个体词，谓词，量词的有关概念，,2、掌握在一阶逻辑中的命题符号化。,一、谓词逻辑研究的内容。,例如：判断以下推理是否正确：,凡人都是要死的，,苏格拉底是人，,所以苏格拉底是要死的。,二、个体词，谓词，量词。,1、个体词，谓词。,例如：陈景润是数学家。,是无理数。,小王比小李高2厘米。,个体域(或称论域)个体变项取值的范围。,：小王，,：小明，,：小王比小明高。,一元谓词,个体常项,个体常项,：李华,：小明,分别表示李华，小明是大学生，,它们是0元谓词。,2、量词表示数量的词。,使用量词时，应注意以下6点：,三、命题符号化。,例1、在一阶逻辑中将下面命题符号化。,(1)所有的有理数均可表成分数。,解：,因无指定个体域，则以全总个体域为个体域。,(2)有的有理数是整数。,解：,例2、在一阶逻辑中将下列命题符号化。,(1)凡偶数均能被2整除。,(2)存在着偶素数。,(3)没有不犯错误的人。,原命题即：“每个人都犯错误”。,又可符号化为：,第一句为：,或,第二句为：,或,例3设个体域为实数集，令是整数是有理数试用日常语言叙述下列命题，并指出其真值,（1）（2）（3）（4）,（2）存在着实数，使得对于任意实数，都有该命题真值为0（3）存在着实数和,使得且该命题真值为1（4）对于任意实数，存在着实数，使得且，,解：（1）对于任意实数，存在着实数，使得该命题真值为1,该命题真值为0,内容：,重点：,(1)掌握合式公式的概念，,第二节一阶逻辑合式公式及解释,一般：,(1)换名规则，代替规则，,(2)解释的概念，,(3)代换实例。,了解：,(1)闭式的概念，,(2)判断合式公式的类型。,一、一阶逻辑中的合式公式。,1、字母表。,(1)个体常项：,(2)个体变项：,(3)函数符号：,(4)谓词符号：,(5)量词符号：,(6)联结词符：,(7)括号和逗号：(，)，。,2、元的递归定义。,(1)个体常项和变项是元。,(3)只有有限次地使用(1)、(2)生成的符号串才是元。,例如：,等都是元。,3、原子公式。,4、合式公式的递归定义。,(1)原子公式是合式公式；,5、约束出现，自由出现。,约束出现，自由出现,（1）,（2）,（3）,换名规则指导变项，约束变项换名,例如：,换成,代替规则自由变项代替,例如：,换成,二、合式公式的解释。,例2给定解释如下：,中特定元素；,(1);,(2),函数为；,(3),谓词为；,(4),为,为,；,在解释下，求下列各式的真值,（1）；（2）；（3）；（4）,解：设（1）、（2）、（3）、（4）中公式分别为在解释下，,有一些公式，可以利用命题公式的结论。,例如：,(1),(2),所以原公式是逻辑有效的。,(3),所以原公式是逻辑有效的。,(4),所以原公式是矛盾式。,内容：,一阶逻辑等值式，前束范式。,重点：,一般：,使用基本等值式进行等值演算。,了解：,前束范式的定义和求法。,第三节谓词逻辑等值式,一、一阶逻辑等值式。,定理21量词否定等值式。,(1),(2),定理22量词分配等值式。,(1),(2),定理23量词辖域收缩与扩张等值式。,(1),(2),(4),(3),(5),(6),(7),(8),定理24多个量词间的次序排列等值式。,(1),(2),二、前束范式。,前束范式：形式,例如：,任一合式公式都可表示为前束范式，其化归步骤如下：,（1）消去公式中出现的多余量词；（2）将合式公式中出现的联结词都化为（3）利用双重否定律，德摩根律及量词否定等值式将合式公式中的否定字符深入到谓词字母前；（4）利用代替规则和换名规则，使所有约束变元均不相同，并且使自由变元与约束变元不同（5）利用量词辖域收缩与扩张等值式，扩大量词的辖域至整个公式,例2、求下列公式的前束范式。,解：,(1),（定理21（2）,（换名规则）,（定理23（1）,（定理23（1）,(2),解：,（代替规则）,（换名规则）,（定理23（2）,（定理23（2）,（定理23（1）,（定理23（1）,第四节谓词逻辑中的推理,一、谓词逻辑推理的概念。,1、概念。,2、量词分配定律。,(1),(2),(3),(4),二、推理规则。,1、全称量词消去规则,2、全称量词引入规则,取任何值时,3、存在量词消去规则,4、存在量词引入规则,：苏格拉底。,前提：,结论：,例1证明苏格拉底三段论“凡人都是要死的苏格拉底是人所以苏格拉底是要死的”,证明：,前提引入,前提引入,假言推理,例2指出下面推理的错误,前提引入UIEIUGEG,解：,因中存在自由出现的个体变项，因而不能使用EI规则，所以错误,例3构造下面推理的证明,前提：结论：,证明：,前提引入前提引入UIUI假言易位假言三段论假言易位UG,一、谓词逻辑的基本概念。,1、基本概念。,2、应用。,在谓词逻辑中将命题符号化。,第二章小结与例题,二、谓词逻辑合式公式及解释。,1、基本概念。,2、应用。,(1)求某些公式在给定解释下的真值。,(2)判断某些简单公式的类型。,三、谓词逻辑等值式。,基本概念。,等值式，常用等值式；前束范式。,四、谓词逻辑推理理论。,2、应用。,用构造法证明某些简单的推理。,例1、在一阶逻辑中将下列命题符号化。,(1)至少有一个实数不是自然数,(2)任何金属均可溶解于某种液体中。,设是实数，是自然数，符号化为,解：,真值0。,真值0。,真值0。,真值1。,设解释I为：个体域为，谓词,例3,根据解释I，求下列各式的真值：,（1）；（2）；（3）,解：,（