离散数学第二章谓词逻辑.ppt

《离散数学第二章谓词逻辑.ppt》由会员分享，可在线阅读，更多相关《离散数学第二章谓词逻辑.ppt（96页珍藏版）》请在三一办公上搜索。

1、1,命题逻辑的局限性：在命题逻辑中，命题是命题演算的基本单位，不再对原子命题进行分解，因而无法研究命题的内部结构、成分及命题之间的内在联系，甚至无法处理一些简单而又常见的推理过程。,第二章 谓 词 逻 辑,2,例如，下列推理：所有的人都是要死的。苏格拉底是人。苏格拉底是要死的。众所周知，这是真命题。但在命题逻辑中,如果用P，Q，R表示以上三个命题，则上述推理过程为：（PQ）R。借助命题演算的推理理论不能证明其为重言式。,第二章 谓 词 逻 辑,3,原因：命题逻辑不能将命题之间的内在联系和数量关系反映出来。解决办法：将命题进行分解。,第二章 谓 词 逻 辑,4,2.1 谓词的概念与表示2.2 命

2、题函数与量词2.3 谓词公式与翻译2.4 变元的约束2.5 谓词演算的等价式与蕴含式2.6 前束范式2.7 谓词演算的推理理论,第二章 谓 词 逻 辑,5,2.1 谓词的概念与表示 在谓词逻辑中，可将原子命题划分为个体和谓词两部分。个体：可以独立存在的具体事物的或抽象的概念。例如，电子计算机、李明、玫瑰花、黑板、实数、中国、思想、唯物主义等，客体也可称之为 主语。谓词：用来刻划个体的性质或个体之间的相互关系 的词。,第二章 谓 词 逻 辑2.1 谓词的概念与表示,6,例如在下面命题中：（1）张明是个劳动模范。（2）李华是个劳动模范。刻划个体的性质（3）王红是个大学生。（4）小李比小赵高2cm。

3、（5）点a在b与c之间。刻划个体之间的相互关系（6）阿杜与阿寺同岁。“是个劳动模范”、“是个大学生”、“比高2cm”、“在与之间”“与同岁”都是谓词。,第二章 谓 词 逻 辑2.1 谓词的概念与表示,7,刻划一个个体性质的词称之为一元谓词，刻划n个个体之间关系的词称之为n元谓词。一般我们用大写英文字母表示谓词，用小写英文字母表示个体名称。,第二章 谓 词 逻 辑2.1 谓词的概念与表示,8,例如，将上述谓词分别记作大写字母F、G、H、R、S，则上述命题可表示为：(1)F(a)a：张明(2)F(b)b：李华(3)G(c)c：王红(4)H(s,t)s：小李 t：小赵(5)R(a,b,c)(6)S(

4、a,b)a:阿杜 b:阿寺其中，(1)、(2)、(3)为一元谓词，(4)、(6)为二元谓词，(5)为三元谓词。,第二章 谓 词 逻 辑2.1 谓词的概念与表示,9,注意:(1)单独一个谓词并不是命题，在谓词字母后填 上个体所得到的式子称之为谓词形式。(2)在谓词形式中，若个体确定，则A(a1，a2，.，an)就变成了命题。(3)在多元谓词表达式中，个体字母出现的先后 次序与事先约定有关，一般不可以随意交换 位置。,第二章 谓 词 逻 辑2.1 谓词的概念与表示,10,小结：本节将原子命题进行分解，分为个体和谓词两部分。进而介绍了个体和谓词、一元谓词和n元谓词的概念。重点掌握一元谓词和n元谓词的

5、概念。,第二章 谓 词 逻 辑2.1 谓词的概念与表示,11,2.2.1 命题函数2.2.2 量词,第二章 谓 词 逻 辑2.2 命题函数与量词,12,2.2.1 命题函数例如：设谓词H表示“是劳动模范”，a表示个体张明，b表示个体李华，c表示个体这只老虎，那么H(a)、H(b)、H(c)表示三个不同的命题，但它们有一个共同的形式，即H(x)。,第二章 谓 词 逻 辑2.2 命题函数与量词,13,一般地，H(x)表示个体x具有性质H。这里x表示抽象的或泛指的个体，称为个体变元，常用小写英文字母x,y,z,表示。相应地，表示具体或特定的个体的词称为个体常元，常用小写英文字母a,b,c,表示。同理

6、，个体变元x,y具有关系L，记作L(x,y)；个体变元x,y,z具有关系A，记作A(x,y,z)。H(x)、L(x,y)、A(x,y,z)本身并不是一个命题。只有用特定的个体取代个体变元x,y,z后，它们才成为命题。我们称H(x)、L(x,y)、A(x,y,z)为命题函数。,第二章 谓 词 逻 辑2.2 命题函数与量词,14,定义:由一个谓词H和n个个体变元组成的表达式 H(x1,x2,xn)称为n元简单命题函数。由定义可知，n元谓词就是有n个个体变元的命题函数。当n=0时，称为0元谓词。因此，一般情况下，命题函数不是命题；特殊情况0元谓词就变成一个命题。,第二章 谓 词 逻 辑2.2 命题函

7、数与量词,15,复合命题函数：由一个或几个简单命题函数以及逻辑联结词组合而成的表达式。例1：若x的学习好，则x的工作好。设S(x):x学习好；W(x):x工作好 则有S(x)W(x),第二章 谓 词 逻 辑2.2 命题函数与量词,16,例2：将下列命题用0元谓词符号化。(1)2是素数且是偶数。(2)如果2大于3，则2大于4。(3)如果张明比李民高，李民比赵亮高，则张明比赵亮高。,第二章 谓 词 逻 辑2.2 命题函数与量词,17,解：(1)设F(x):x是素数.G(x):x是偶数.则命题符号化为：F(2)G(2)(2)设L(x,y)：x大于y.则命题符号化为：L(2,3)L(2,4)(3)设

8、H(x,y):x比y高.a:张明 b:李民 c：赵亮 则命题符号化为：H(a,b)H(b,c)H(a,c)注意：命题函数中，个体变元在哪些范围内取特定 的值，对命题的真值极有影响。,第二章 谓 词 逻 辑2.2 命题函数与量词,18,例如：H(x,y)H(y,z)H(x,z)若H(x,y)解释为:x大于y，当x,y,z都在实数中取值时，则这个式子表示“若x大于y 且y 大于z，则x大于z”。这是一个永真式。如果H(x,y)解释为:“x是y的儿子”，当x,y,z都指人时，则这个式子表示“若x为y的儿子 且y 是z的儿子，则x是z的儿子”。这是一个永假式。如果H(x,y)解释为:“x距y10米”，

9、当x,y,z为平面上的点，则这个式子表示“若x距y10米且y距z10米，则x距z10米”。这个命题的真值将由x,y,z的具体位置而定，它可能是1，也可能是0。,第二章 谓 词 逻 辑2.2 命题函数与量词,19,在命题函数中，个体变元的取值范围称为个体域，又称之为论域。个体域可以是有限事物的集合，也可以是无限事物的集合。全总个体域：宇宙间一切事物组成的个体域称为全总个体域。,第二章 谓 词 逻 辑2.2 命题函数与量词,20,2.2.2 量词量词：全称量词()和存在量词()1.全称量词 对日常语言中的“一切”、“所有”、“凡是”、“每一个”、“任意”等词，用符号“”表示，表示对个体域里的所有个

10、体，F()表示个体域里的所有个体具有性质F。符号“”称为全称量词。,第二章 谓 词 逻 辑2.2 命题函数与量词,21,例3：在谓词逻辑中将下列命题符号化。（1）凡是人都呼吸。（2）每个学生都要参加考试。（3）任何整数或是正的或是负的。,第二章 谓 词 逻 辑2.2 命题函数与量词,22,解:(1)当个体域为人类集合时：令F(x):x呼吸。则（1）符号化为xF(x).当个体域为全总个体域时：令M(x):x是人。则（1）符号化为 x(M(x)F(x).,第二章 谓 词 逻 辑2.2 命题函数与量词,23,(2)当个体域为全体学生的集合时：令P(x):x要参加考试。则（2）符号化为 xP(x).当

11、个体域为全总个体域时：令S(x):x是学生。则（2）符号化为 x(S(x)P(x).,第二章 谓 词 逻 辑2.2 命题函数与量词,24,(3)当个体域为全体整数的集合时：令P(x):x是正的。N(x):x是负的。则（3）符号化为 x(P(x)N(x).当个体域为全总个体域时：令I(x):x是整数。则（3）符号化为 x(I(x)(P(x)N(x).,第二章 谓 词 逻 辑2.2 命题函数与量词,25,2.存在量词 对日常语言中的“有一个”、“有的”、“存在着”、“至少有一个”、“存在一些”等词，用符号“”表示，表示存在个体域里的个体，F()表示存在个体域里的个体具有性质F。符号“”称为存在量词

12、。,第二章 谓 词 逻 辑2.2 命题函数与量词,26,例4：在谓词逻辑中将下列命题符号化.（1）一些数是有理数。（2）有些人活百岁以上。,第二章 谓 词 逻 辑2.2 命题函数与量词,27,解:(1)令Q(x):x是有理数。则（1）符号化为Q(x)。（2）当个体域为人类集合时：令G(x):x活百岁以上。则（2）符号化为xG(x)。当个体域为全总个体域时：令M(x):x是人。则（2）符号化为 x(M(x)G(x),第二章 谓 词 逻 辑2.2 命题函数与量词,28,有时需要同时使用多个量词。例5：命题“对任意的x,存在y,使得x+y=5”,取个体域为实数集合，则该命题符号化为 x y H(x,

13、y).其中H(x,y):x+y=5.这是个真命题.,第二章 谓 词 逻 辑2.2 命题函数与量词,29,3.使用量词时应注意的问题（1）在不同的个体域，同一命题的符号化形式可 能相同也可能不同。（2）在不同的个体域，同一命题的真值可能相同 也可能不同。(如，R（x）表示x为大学生。如 果个体域为大学里的某个班级的学生，则x R（x）为真；若个体域为中学里的某个班级 的学生，则x R（x）为假。),第二章 谓 词 逻 辑2.2 命题函数与量词,30,（3）约定以后如不指定个体域，默认为全总 个体域。对每个个体变元的变化范围,用 特性谓词加以限制。,第二章 谓 词 逻 辑2.2 命题函数与量词,3

14、1,特性谓词：限定个体变元变化范围的谓词。一般而言，对全称量词，特性谓词常作蕴含的前件，如x(M(x)F(x)；对存在量词，特性谓词常作合取项，如x(M(x)G(x)。,第二章 谓 词 逻 辑2.2 命题函数与量词,32,(4)一般来说，当多个量词同时出现时，它们的顺序不能随意调换。例如：在实数域上用H(x,y)表示x+y=5，则命题“对于任意的x，都存在y使得x+y=5”可符号化为：xyH(x,y)，其真值为1。若调换量词顺序后为：yxH(x,y),其真值为0。,第二章 谓 词 逻 辑2.2 命题函数与量词,33,(5)当个体域为有限集合时，如D=a1,a2,an，对任意谓词A(x)，有 x

15、A(x)A(a1)A(a2)A(an)xA(x)A(a1)A(a2)A(an),第二章 谓 词 逻 辑2.2 命题函数与量词,34,例6：在谓词逻辑中将下列命题符号化。（1）所有的人都长头发。（2）有的人吸烟。（3）没有人登上过木星。（4）清华大学的学生未必都是高素质的。解：令M(x):x是人。（特性谓词）（1）令F(x):x长头发。则符号化为：（x）(M(x)F(x),第二章 谓 词 逻 辑2.2 命题函数与量词,35,（2）令S(x):x吸烟。则符号化为：（x）(M(x)S(x)（3）令D(x):x登上过木星。则符号化为：（x）(M(x)D(x)（4）令Q(x):x是清华大学的学生。H(x

16、):x是高 素质的。则符号化为：（x）(Q(x)H(x),第二章 谓 词 逻 辑2.2 命题函数与量词,36,小结:本节介绍了n元谓词、命题函数、全称量词和存在量词等概念。重点掌握全称量词和存在量词及量化命题的符号化。,第二章 谓 词 逻 辑2.2 命题函数与量词,37,2.3谓词公式与翻译n元谓词A(x1，x2.xn)称为谓词演算的原子公式。定义：谓词演算的合式公式，可由下述各条组成:（1）原子公式是合式公式。（2）若A 是合式公式，则(A)也是合式公式。（3）若A，B是合式公式，则(A B)，(A B)，(A B)，(A B)也是合式公式。（4）若A是合式公式，x是A中出现的任何变元,则(

17、x)A,(x)A，也是合式公式。（5）只有有限次应用(1)(4)得到的公式是合式公式。,第二章 谓 词 逻 辑2.3 谓词公式与翻译,38,例1：在谓词逻辑中将下列命题符号化.（1）凡正数都大于零。（2）存在小于2的素数。（3）没有不能表示成分数的有理数。（4）并不是所有参加考试的人都能取得好成绩。解：（1）令F(x):x是正数。M(x):x大于零。则符号化为：（x）(F(x)M(x),第二章 谓 词 逻 辑2.3 谓词公式与翻译,39,（2）令E(x):x小于2。S(x):x是素数。则符号化为：x(E(x)S(x)（真值为0）（3）令D(x):x是有理数。F(x):x能表示成分数。则符号化为

18、：x(D(x)F(x)或 x(D(x)F(x)（真值为）（4）令M(x)：x是人。Q(x):x参加考试。H(x):x取得好成绩。则符号化为：x(M(x)Q(x)H(x)或 x(M(x)Q(x)H(x),第二章 谓 词 逻 辑2.3 谓词公式与翻译,40,例2：在谓词逻辑中将下列命题符号化.（1）所有运动员都钦佩某些教练.（2）有些运动员不钦佩教练.设：L(x):x是运动员 J(y):y是教练 A(x,y):x钦佩y(1)(x)(L(x)（y)(J(y)A(x,y)(2)（x)(L(x)(y)(J(y)A(x,y),第二章 谓 词 逻 辑2.3 谓词公式与翻译,41,小结：本节介绍了谓词合式公式

19、的概念，重点掌握谓词公式的翻译。,第二章 谓 词 逻 辑2.3 谓词公式与翻译,42,变元的约束定义:在谓词公式中，形如(x)P(x)和(x)P(x)的部 分，称为谓词公式的x约束部分。(x)P(x)或(x)P(x)中的x叫做量词的指导变元 或作用变元，P(x)称为相应量词的作用域或辖域。在x和x的辖域中，x的所有出现都称为约束出 现，相应的x称为约束变元;P(x)中除约束变元 以外出现的变元称为是自由变元。,第二章 谓 词 逻 辑2.4 变元的约束,43,例1：1、x(H(x,y)y(W(y)L(x,y,z)2、x(H(x)W(y)y(F(x)L(x,y,z),第二章 谓 词 逻 辑2.4

20、变元的约束,44,说明:(1)n元谓词公式A(x1，x2.xn)中有n个自由变元，若对其中的k(kn)个进行约束，则构成了n-k元谓词；如果一个公式中没有自由变元出现，则该公式就变成了一个命题。(2)一个公式的约束变元所使用的名称符号是无关紧要的，如(x)M(x)与(y)M(y)意义相同。,第二章 谓 词 逻 辑2.4 变元的约束,45,2.4.2 约束变元的换名与自由变元的代入 一个变元在同一个公式中既是自由出现又是约束出现，这样在理解上容易发生混淆。为了避免这种混乱，可对约束变元进行换名。,第二章 谓 词 逻 辑2.4 变元的约束,46,换名规则:(对约束变元而言）对约束变元进行换名，使得

21、一个变元在一个公式中只呈一种形式出现(1)约束变元可以换名，其更改的变元名称范围是量词中的指导变元以及该量词作用域中所出现的该变元，公式的其余部分不变。(2)换名时一定要更改为作用域中没有出现的变元名称。,第二章 谓 词 逻 辑2.4 变元的约束,47,例1:x(P(x)R(x,y)L(x,y)换名为t(P(t)R(t,y)L(x,y)2：x(H(x,y)y(W(y)L(x,y,z)换名为x(H(x,y)s(W(s)L(x,s,z),第二章 谓 词 逻 辑2.4 变元的约束,48,代入规则（对自由变元而言）对公式中自由变元的更改称为代入(1)对于谓词公式中的自由变元可以作代入，代入时需要对公式

22、中出现该自由变元的每一处进行；(2)用以代入的变元与原公式中所有变元的名称不能相同。例：x(P(x)R(x,y)L(x,y)对自由变元y用z来代入，得x(P(x)R(x,z)L(x,z),第二章 谓 词 逻 辑2.4 变元的约束,49,小结：本节介绍了约束变元、自由变元的 概念，重点掌握约束变元的换名与自由变元的代入。,第二章 谓 词 逻 辑2.4 变元的约束,50,谓词公式的等价和永真的概念定义：一个解释I由下面4部分组成：1.非空个体域DI；2.DI中部分特定元素a、b，.；3.DI上的特定一些函数f、g，.；4.DI上特定谓词P、Q，.。见书P40例。,第二章 谓 词 逻 辑2.5 谓词

23、演算的等价式与蕴涵式,51,定义：给定任意的谓词公式A，其个体域为E，（1）对于A的所有解释，公式A都为真，则称A在E上是永真的(或有效的)。（2）若对于A的所有解释，公式A都为假，则称A在E上是永假的(或不可满足的)。（3）若至少存在着一种解释使得公式A为真，则称A在E上是可满足的。,第二章 谓 词 逻 辑2.5 谓词演算的等价式与蕴涵式,52,定义：给定任何两个谓词公式A、B，设它们有共同的个体域E，若对A和B的任一组变元进行解释，所得命题的真值相同，则称谓词公式A和B在E上等价，并记为A B。定义：给定任何两个谓词公式A、B，当且仅当A B是永真式时，称“A蕴涵B”，记作A B。,第二章

24、 谓 词 逻 辑2.5 谓词演算的等价式与蕴涵式,53,2.5.2 谓词演算的等价式和蕴涵式1、命题公式的推广在命题公式中成立的等价公式，用谓词公式去代换其中相应的命题变元，得到的公式依然成立如：x(P(x)Q(x)x(P(x)Q(x)P(x)Q(x)（P(x)Q(x)）,第二章 谓 词 逻 辑2.5 谓词演算的等价式与蕴涵式,54,2、量词与之间的关系（x）P(x)（x）P(x)（x）P(x)（x）P(x)证明：对个体域 a1，a2，an，xP(x)(P(a1)P(a2)P(an)P(a1)P(a2)P(an)x P(x),第二章 谓 词 逻 辑2.5 谓词演算的等价式与蕴涵式,55,3、量

25、词作用域的扩张与收缩量词作用域中如果有合取或析取项，且其中有一个是命题，则可将该命题移至量词作用域之外。如：（x）（A(x)B）（x）A(x)B（x）（A(x)B）（x）A(x)B（x）（A(x)B）（x）A(x)B（x）（A(x)B）（x）A(x)B,第二章 谓 词 逻 辑2.5 谓词演算的等价式与蕴涵式,56,证明：当个体域为a1，a2，an，xA(x)P(P(a1)P(a2)P(an)P)(P(a1)P)(P(a2)P)(P(an)P)x(A(x)P),第二章 谓 词 逻 辑2.5 谓词演算的等价式与蕴涵式,57,量词作用域的扩张和收缩(xA(x)B）（x)(A(x)B）(（x)A(x)

26、B)(x)(A(x)B）(B(x)A(x)）（x)(B A(x)）(B(x)A(x)（x）(B A(x),第二章 谓 词 逻 辑2.5 谓词演算的等价式与蕴涵式,58,例1：xA(x，y)P(y)x(A(x，y)P(y)例2：xy(P(x)Q(y)(x P(x)yQ(y),第二章 谓 词 逻 辑2.5 谓词演算的等价式与蕴涵式,59,例1：xA(x，y)P(y)x(A(x，y)P(y)例2：xy(P(x)Q(y)(x P(x)yQ(y)证明：xy(P(x)Q(y)xy(P(x)Q(y)x(P(x)y Q(y)xP(x)yQ(y)x P(x)y Q(y)x P(x)yQ(y),第二章 谓 词 逻

27、 辑2.5 谓词演算的等价式与蕴涵式,60,4、量词的分配设A(x)、B(x)是任意的含自由出现个体变元x的公式，则(1)x(A(x)B(x)x A(x)x B(x)(2)x(A(x)B(x)x A(x)x B(x),第二章 谓 词 逻 辑2.5 谓词演算的等价式与蕴涵式,61,证明：对个体域a1，a2，an x(A(x)B(x)(A(a1)B(a1)(A(an)B(an)(A(a1)A(a2)A(an)(B(a1)B(a2)B(an)xA(x)xB(x),第二章 谓 词 逻 辑2.5 谓词演算的等价式与蕴涵式,62,(3)x(A(x)B(x)x A(x)x B(x)(4)x(A(x)B(x)

28、x A(x)x B(x),第二章 谓 词 逻 辑2.5 谓词演算的等价式与蕴涵式,63,注意：逆方向不成立。如（4）式，xA(x)x B(x)x(A(x)B(x)不成立。举反例：设个体域是整数集合 A(x)：x为奇数，B(x)：x为偶数，则xA(x)xB(x)为真，但x(A(x)B(x)为假。,第二章 谓 词 逻 辑2.5 谓词演算的等价式与蕴涵式,64,(5)x(A(x)B(x)xA(x)xB(x)(6)x A(x)xB(x)x(A(x)B(x),第二章 谓 词 逻 辑2.5 谓词演算的等价式与蕴涵式,65,5、多个量词的使用(1)xyP(x，y)y xP(x，y)(二者同义)(2)xyP(

29、x，y)y xP(x，y)xyP(x，y)x yP(x，y)(3)yxP(x，y)xyP(x，y)(4)xyP（x，y）xyP(x，y)yxP（x，y）yxP(x，y)(5)yxP（x，y）yxP(x，y),第二章 谓 词 逻 辑2.5 谓词演算的等价式与蕴涵式,66,注意:上述蕴涵式逆方向均不成立。例：如（3）中，设个体域为有理数集合，P(x,y)：x+y=0，则xy P(x,y)为真。但是，y xP(x,y)为假。,第二章 谓 词 逻 辑2.5 谓词演算的等价式与蕴涵式,67,小结：本节介绍了谓词演算的基本等价式和蕴涵式。重点掌握谓词公式之间的等价演算。,第二章 谓 词 逻 辑2.5 谓词

30、演算的等价式与蕴涵式,68,定义:任何一个谓词公式A，如果具有如下形式：(x1)(x2)(xn)B，其中可能是量词或量词，xi（i=1，n）是个体变元，B是不含量词的谓词公式，则称 A是前束范式。说明：前束范式的量词均在全式的开头,它们的作用 域延伸到整个公式的末尾。,第二章 谓 词 逻 辑2.6 前束范式,69,例:xy(F(x)G(y)H(x,y)xy(F(x,y)G(y,z)x H(x,y,z)定理：任何一个谓词公式，均和一个前束范 式等价。,第二章 谓 词 逻 辑2.6 前束范式,70,前束范式的求法：第一步：否定深入。即利用量词转化公式，把否定联结词深入到命题变元和谓词填式的前面。第

31、二步：改名。即利用换名规则、代入规则更换一些变元的名称，以便消除混乱。第三步：量词前移。即利用量词辖域的收缩与扩张把量词移到前面。这样便可求出与公式等价的前束范式。,第二章 谓 词 逻 辑2.6 前束范式,71,例:求下列公式的前束范式。,第二章 谓 词 逻 辑2.6 前束范式,72,解:,第二章 谓 词 逻 辑2.6 前束范式,73,第二章 谓 词 逻 辑2.6 前束范式,74,第二章 谓 词 逻 辑2.6 前束范式,75,第二章 谓 词 逻 辑2.6 前束范式,76,说明：1.等价演算的顺序不同，使得前束范式不唯一。2.一个谓词公式的前束范式的各指导变元应是各不相同的，原来在谓词公式中自由

32、出现的个体变元在前束范式中还应是自由出现。小结：本节介绍了谓词公式前束范式的概念和求法。,第二章 谓 词 逻 辑2.6 前束范式,77,推理规则在谓词演算中，推理的形式结构仍为 H1H2H3.HnC。若 H1H2H3.HnC是永真式，则称由前提H1,H2,H3,Hn逻辑的推出结论C，但在谓词逻辑中,H1,H2,H3,.,Hn,C均为谓词公式。（命题演算中的推理规则，可在谓词推理理论中应用。）,第二章 谓 词 逻 辑2.7 谓词演算的推理理论,78,与量词有关的四条重要推理规则：1、全称量词消去规则（US规则）2、全称量词产生规则（UG规则）3、存在量词消去规则（ES规则）4、存在量词产生规则（

33、EG规则）注意：只能对前束范式适用上述规则。,第二章 谓 词 逻 辑2.7 谓词演算的推理理论,79,1.全称指定规则（US）：x A(x)A(c)x A(x)A(y)使用此规则时要注意：（1）x是A(x)中的自由变元；（2）c是个体域中任意个体常元；（3）y为任意不在A(x)中约束出现的个体变元。,第二章 谓 词 逻 辑2.7 谓词演算的推理理论,80,例：设F(x，y)：xy，x、y的个体域为实数集合，令A(x)y F(x，y)，则x A(x)x y F(x，y),该式真值为1。若应用US得y F(y，y)，则是错误的，正确的做法是换成y F(z，y),第二章 谓 词 逻 辑2.7 谓词演

34、算的推理理论,81,2.全称推广规则（UG）：A(y)x A(x)使用此规则时注意:(1)y在A(y)中自由出现，且y取任何值时A均为真；(2)取代y的x不在A(y)中约束出现。,第二章 谓 词 逻 辑2.7 谓词演算的推理理论,82,例：设F(x，y)：xy，x、y的个体域为实数集合，令A(y)x F(x，y)，该式真值为1，若应用UG规则取x代替y得x x F(x，x)，则是错误的，正确的做法是换成z x F(x，z)。,第二章 谓 词 逻 辑2.7 谓词演算的推理理论,83,3.存在指定规则(ES):x A(x)A(c)注意：c是个体域中的某些个体，c并不具有任意性。使用此规则时应注意：

35、（1）c是使A为真的特定的个体常元，且未在A(x)中 出现过；（2）如果A(x)中有其他自由变元出现，且x是随其 他自由变元变化的，那么不能使用此规则。,第二章 谓 词 逻 辑2.7 谓词演算的推理理论,84,(4)存在推广规则(EG):A(c)x A(x)使用此规则时注意:(1)c是个体域中某个确定的个体常元；(2)取代c的x不能已在A(c)中出现。,第二章 谓 词 逻 辑2.7 谓词演算的推理理论,85,证明举例,第二章 谓 词 逻 辑2.7 谓词演算的推理理论,86,例1证明苏格拉底三段论:凡是人都是要死的。苏格拉底是人。苏格拉底是要死的。设：M(x):x是人。D(x):x 是要死的。a

36、:苏格拉底前提：x(M(x)D(x)，M(a）。结论：D(a)。证明：x(M(x)D(x)P M(a)D(a)US M(a)P D(a)T I(直接证法),第二章 谓 词 逻 辑2.7 谓词演算的推理理论,87,例2:前提：x(F(x)G(x)，x G(x).结论：x F(x).,第二章 谓 词 逻 辑2.7 谓词演算的推理理论,88,例2:前提：x(F(x)G(x)，x G(x).结论：x F(x).证明：x G(x)P x G(x)TE G(a)US x(F(x)G(x)P F(a)G(a)US F(a)T I x F(x)EG,第二章 谓 词 逻 辑2.7 谓词演算的推理理论,89,例3

37、：前提：x(A(x)B(x)，x A(x)结论：x B(x),第二章 谓 词 逻 辑2.7 谓词演算的推理理论,90,例3：前提：x(A(x)B(x)，x A(x)结论：x B(x)证明：x A(x)P A(c)ES x(A(x)B(x)P A(c)B(c)US B(c)T I x B(x)EG 注意：引入的顺序不可更改！,第二章 谓 词 逻 辑2.7 谓词演算的推理理论,91,例4：前提：x(F(x)G(x)，x(R(x)G(x)，x R(x).结论：x F(x).(归谬法),第二章 谓 词 逻 辑2.7 谓词演算的推理理论,92,例4：前提：x(F(x)G(x)，x(R(x)G(x)，x

38、R(x).结论：x F(x).(归谬法)证明：x F(x)P结论否定引入 x F(x)TE F(a)ES x(F(x)G(x)P F(a)G(a)US G(a)TI,第二章 谓 词 逻 辑2.7 谓词演算的推理理论,93,x(R(x)G(x)P R(a)G(a)US R(a)T x R(x)P(11)R(a)US(12)R(a)R(a)矛盾式,第二章 谓 词 逻 辑2.7 谓词演算的推理理论,94,例5:前提:x(P(x)Q(x)结论：(x)P(x)(x)Q(x)(附加前提法),第二章 谓 词 逻 辑2.7 谓词演算的推理理论,95,证明：(1)(x)P(x)P(附加前提)(2)(x)P(x)T(1)(3)P(c)ES(2)(4)x(P(x)Q(x)P(5)P(c)Q(c)US(4)(6)Q(c)T(3)(5)(7)(x)Q(x)EG(6)(8)(x)P(x)(x)Q(x)CP,第二章 谓 词 逻 辑2.7 谓词演算的推理理论,96,小结：本节介绍了谓词演算的推理规则，并举例说明了它们的应用。重点：深刻理解四个推理规则，会应用它们推理证明。,第二章 谓 词 逻 辑2.7 谓词演算的推理理论,