《计算机数学基础—离散数学》谓词逻辑.docVIP

第2章 谓词逻辑 ? 一、教学要求 ? 1. 理解谓词、量词、个体词、个体域、原子公式、谓词公式和变元等概念。会将不太复杂的命题符号化。 2. 掌握在有限个体域下求公式的真值和某些公式在给定解释下真值的方法，判别公式类型(永真式、永假式和可满足式)的方法。 3. 掌握谓词演算的等值式和重言蕴含式 (六种情况：(1)命题公式的推广；(2)量词否定式的等值式；(3)量词辖域扩张和收缩的等值式；(4)量词与联结词(，(，(的等值式；(5)量词与联结词的重言蕴含式；(6)两个量词公式间的等值式与重言蕴含式)。会进行谓词公式的等值演算。 4. 了解前束范式的概念，会求公式的前束范式。 5. 了解谓词逻辑推理的规则：全量词消去规则(US规则)；全量词附加规则(UG规则)；存在量词消去规则(ES规则)；存在量词附加规则(EG规则) ? 本章重点：谓词与量词，公式与解释，前束范式，谓词逻辑推理证明。 ? 二、学习辅导 ? 在命题逻辑中，我们把原子命题作为基本研究单位，对原子命题不再进行分解，只有复合命题才可以分解，揭示了一些有效的推理过程. 但是进一步研究发现，仅有命题逻辑是无法把一些常见的推理形式包括进去. 例如 “凡人要死，张三是人，张三要死” 显然是正确推理. 用命题逻辑解释三段式. 设 P：人要死；Q张三是人；R：张三要死。 表示成复合命题有 P(Q(R 这不是重言式，即R不是前提P，Q的有效结论. 这反映了命题逻辑的局限性，其原因是把本来有内在联系的命题P，Q，R，视为独立的命题。要反映这种内在联系，就要对命题逻辑进行分析，分析出其中的个体词、谓词和量词，再研究它们之间的逻辑关系，总结出正确的推理形式和规则，这就是谓词逻辑的研究内容。 ? 1. 谓词与量词 学习这一部分要反复理解谓词和量词引入的意义，概念的含义。 在谓词逻辑中，原子命题分解成个体词和谓词。个体词是可以独立存在的客体，它可以是具体事物或抽象的概念，如小张，房子，南京，大米，思想，实数2等等。谓词是用来刻划个体词的性质或事物之间的关系的词。例如 (1)??? ln5是无理数； (2)??? 高可比李木相高4cm； (3) 郑州位于北京和广州之间。 这时三个简单命题，其中ln5，高可，李木相，郑州，北京，广州等都是个体词，而“是无理数”，“……比……高4cm”，“……位于……和……之间”等都是谓词。 个体词分个体常项(用a,b,c,d,…表示)和个体变项(用x,y,z,…表示)；谓词分谓词常项(表示具体性质和关系的词)和谓词变项(表示抽象的或泛指的谓词)，用F,G,P,…表示。 个体常项a和个体变项都具有性质F，记作F(a)或F(x);个体常项a,与b或个体变项x与y具有关系L,记作L(a,b)或L(x,y)。一般地，用F(a)表示a是无理数，其中a表示ln5，F表示的是“…是无理数”。当F的含义不变时，则F(x)表示x是无理数，x是个体变项，F谓词常项，F(x)不是命题，而是命题变项，F(a)是命题。用M(x,y,z)表示“z=x×y”，M(x,y,z)不是命题。a表示3，b表示5，c表示15，M(a,b,c)表示“15＝3×5”。M(a,b,c)是命题，真值为1，若c=12，那么M(a,b,c)是命题，真值为0。 注意，单独的个体词和谓词不能构成命题，将个体词和谓词分开不是命题。 例2.1 将下列命题符号化： (1) 丘华和李兵都是学生； (2) 2既是偶数又是素数； (3) 如果张华比黎明高，黎明比王宏高，则张华比王宏高。 解 (1) 设个体域是人的集合。 P(x)：:x是学生。 a：丘华 b：黎兵 该命题符号化为P(a)(P(b) (2) 设个体域为正整数集合N＋。 F(x)：x是偶数， Q(x)：x是素数 a：2 该命题符号化为F(a)(Q(a) (3)??? 设个体域是人的集合。 G(x,y)：x比y高。 a：张华 b：黎明 c：王宏 该命题符号化为G(a,b)(G(b,c)(G(a,c) ? 量词是在命题中表示数量的词，量词有两类：全称量词(，表示“所有的”或“每一个”；存在量词(，表示“存在某个”或“至少有一个”。 ? 例2.2 将下列命题符号化 (1)??? 每个母亲都爱自己的孩子； (2) 所有的人都呼吸； (3) 有某些实数是有理数。 解 (1) 设个体域是所有母亲的集合。 M(x)：x表示爱自己的孩子； 该命题符号化为(xM(x)。 (2) 设个体域为人的集合。 H(x)：x表示要呼吸。 该命题符号化为(xH(x) 或设个体域为生物集合， M(x)：x是人。 H(x)：x表示要呼吸。 该命题符号化为(x(M(x)(H(x)) (3) 设个体域