离散数学-谓词逻辑.ppt

第八章 谓词逻辑 在命题逻辑中，命题被当作一个基本的，不可分割的单位，只研究由原子命题和联接词所组成的复合命题；因而无法研究命题的内部结构及命题之间内在的联系。本章介绍的谓词逻辑，对原子命题的成份、结构和原子命题间的共同特性等作了进一步分析。引入了个体词、谓词、量词、谓词公式等概念，在此基础上研究谓词公式间的等值关系和蕴含关系，并且对命题逻辑中的推理规则进行扩充和进行谓词演绎。;8.1 谓词、个体词和量词 ; 一、个体词和谓词 在谓词演算中，可将原子命题分解为谓词与个体词两部分。; 通常，我们用大写字母表示谓词，小写字母表示个体。 上述命题可分别表示为 Q（a）, P（b,c），R（c,b,a）。 一般地，一个由n个个体和n元谓词所组成的命题可表示为F（a1,a2, … ,an）,其中F表示n元谓词, a1,a2, … ,an 分别表示n个个体。 注意：a1,a2, … ,an的排列次序是重要的。; 二、个体变元和命题函数 个体常元 表示具体或特定的个体的个体词称为个体常元。 个体变元 表示抽象的，或泛指的（或者说取值不确定的）个体称为个体变元。; 定义8-3 由一个谓词和若干个个体变元组成的命题形式称为简单命题函数，表示为P（x1,x2,…,xn）。由一个或若干个简单命题函数以及逻辑联结词组成的命题形式称为复合命题函数。; 三、量词和全总个体域 ;（2）存在量词 “　x ” ; 2．全总个体域 含有量词的命题的表达式的形式，与个体域有关。; 当取x的个体域为全总个体域时，必须引入一个特性谓词将人从全宇宙的一切事物中分离出来。 ; 四．命题符号化 ; （3）凡是实数均能比较大小。 ; （3）不是一切人都一样高。 ;8.2 谓词演算公式; 例1 苏格拉底三段论可用谓词公式表示。 ;二、约束变元和自由变元 ;　　例6 　　“某些人对某些药物过敏”; x,y,z在公式中的所有出现均是约束出现，故它们均是约束变元。 ; 解 P（x，y）－ yQ（x，y，z）是 x的辖域，在这一部分中，x是约束出现 ，故x是约束变元，在P（x，y）中的y是自由出现，故y为自由变元。但Q（x， y ，z）是 y的辖域，因而在Q（x， y ，z）中y却是约束出现，故此时y是约束变元，z是自由变元。在S（x，z）中x，z是自由变元。; 三、换名规则和代入规则 1.换名规则 对约束变元进行换名，使得一个变元在一个公式中只呈一种形式出现。;　解　需对x，y换名 ; 2. 代入规则 对于公式中自由变元的更改叫做代入。 ;8.3 谓词公式的等值和蕴含; 例1 试说明下列各公式的类型（个体域取为全总个体域）; 解 （1） 可满足公式。;　定义8-8　设A、B是两个公式，它们有共同的个体域E，若对于A和B的任意一组指派，两公式都具有相同的真值，则称公式A和B在E上等值，记作A B。; 将此情况推广到谓词公式中，用谓词公式去取代命题演算中等值式或蕴涵式的命题变元时，便得到谓词演算的等值式或蕴涵式。;2. 全称量词和存在量词间转化的等值式; 3.量词辖域扩展与收缩的等值式 1.;（2）① ② ③ ④; 证明 （1） ① “个体域中每一个体x，使得A(x)与B(x)均为真”与 “个体域中每一个体x，使得A(x)为真且每一个体x使得B(x)为真”具有相同的含义.;（1）② ; 证明 （2） ② ??（2） ① 得;证明 （1）;证明;8.4 谓词演算的推理理论 ; 与量词有关的推理规则; 使用此规则时应注意： （1）c 是使A为真的特定个体常元； （2）如果A(x)中有其他自由变元出现，且x是随其他自由变元变化的，那么不能使用此规则。 ;4、EG（存在一般化规则）;二、推理规则的应用 ;例2 证明;例3 证明;例4 证明; 证法二 （1） 附加前提; 证明（1）