离散数学谓词逻辑.pptx

离散数学谓词逻辑; 一、个体词与谓词 在谓词演算中,可将原子命题分解为谓词与个体词两部分。; 通常,我们用大写字母表示谓词,小写字母表示个体。 上述命题可分别表示为 Q(a), P(b,c),R(c,b,a)。 一般地,一个由n个个体与n元谓词所组成得命题可表示为F(a1,a2, … ,an),其中F表示n元谓词, a1,a2, … ,an 分别表示n个个体。 注意:a1,a2, … ,an得排列次序就是重要得。; 二、个体变元与命题函数 个体常元 表示具体或特定得个体得个体词称为个体常元。 个体变元 表示抽象得,或泛指得(或者说取值不确定得)个体称为个体变元。; 定义2-3 由一个谓词与若干个个体变元组成得命题形式称为简单命题函数,表示为P(x1,x2,…,xn)。由一个或若干个简单命题函数以及逻辑联结词组成得命题形式称为复合命题函数。; 三、量词与全总个体域 ;（2）存在量词 “　x ” ; 2、全总个体域 含有量词得命题得表达式得形式,与个体域有关。; 当取x得个体域为全总个体域时,必须引入一个特性谓词将人从全宇宙得一切事物中分离出来。 ; 四．命题符号化 ; (3)凡就是实数均能比较大小。 ;大家学习辛苦了,还就是要坚持; (3)不就是一切人都一样高。 ;谓词演算公式; 例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、 代入规则 对于公式中自由变元得更改叫做代入。 ;谓词公式得等值与蕴含; 例1 试说明下列各公式得类型(个体域取??全总个体域); 解 (1) 可满足公式。;　定义2-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);证明;谓词演算得推理理论 ; 与量词有关得推理规则; 使用此规则时应注意: (1)c 就是使A为真得特定个体常元; (2)如果A(x)中有其她自由变元出现,且x就是随其她自由变元变化得,那么不能使用此规则。 ;4、EG（存在一般化规则）;二、推理规则的应用 ;例2 证明;例3 证明;例4 证明; 证法二 （1） 附加前提; （2） （1）；I1 ; 例6 指出下面推理的错误. 设D(x,y)表示“x可被y 整除” ,个体域 为{ 5,7 ,10 ,11 }. 因为D(5，5)和D(10,5)为真，所以 xD(x,5)为真. 因为D(7，5)和D(11,5)为假，所以 xD(x,5)为假.;47; 习 题;(3)对于每一个实数x,存在一个更大得实数y