离散数学及其应用第2章-谓词逻辑课件.ppt

1、谓词的概念与表示谓词的概念与表示(n命题逻辑的局限性命题逻辑的局限性：在命题逻辑中，命题是命题演算的基本在命题逻辑中，命题是命题演算的基本单位，不再对原子命题进行分解，因而无法单位，不再对原子命题进行分解，因而无法研究命题的内部结构、成分及命题之间的内研究命题的内部结构、成分及命题之间的内在联系，甚至无法处理一些简单而又常见的在联系，甚至无法处理一些简单而又常见的推理过程。推理过程。2022-8-5计算机科学与技术学院n例如，下列推理：例如，下列推理：所有的人都是要死的。所有的人都是要死的。苏格拉底是人。苏格拉底是人。苏格拉底是要死的。苏格拉底是要死的。众所周知众所周知,这是真命题。但在命题逻

2、辑中这是真命题。但在命题逻辑中,如如果用果用P,Q,R表示以上三个命题，则上述推理过表示以上三个命题，则上述推理过程为：（程为：（PQ）R。借助命题演算的推理理。借助命题演算的推理理论不能论不能证明其为重言式证明其为重言式。谓词的概念与表示谓词的概念与表示(2022-8-5计算机科学与技术学院谓词的概念与表示谓词的概念与表示(原因：原因：命题逻辑不能将命题之间的内在联系命题逻辑不能将命题之间的内在联系和数量关系反映出来。和数量关系反映出来。解决办法：解决办法：将命题进行分解。将命题进行分解。2022-8-5计算机科学与技术学院谓词的概念与表示谓词的概念与表示(2.1谓词的概念与表示谓词的概念与

3、表示(2.1.1 客体客体和和谓词谓词 在谓词逻辑中，可将在谓词逻辑中，可将原子命题原子命题划分为划分为客体客体和和谓词谓词两部分。两部分。客体客体：可以独立存在的具体事物的或抽象的概：可以独立存在的具体事物的或抽象的概念。念。例例如，电子计算机、李明、玫瑰花、黑如，电子计算机、李明、玫瑰花、黑板、实数、中国、思想、唯物主义等，客体也板、实数、中国、思想、唯物主义等，客体也可称之为主语。可称之为主语。2022-8-5计算机科学与技术学院谓词的概念与表示谓词的概念与表示(谓词：谓词：用来刻划客体的性质或客体之间的相互关系的词。用来刻划客体的性质或客体之间的相互关系的词。例如在下面命题中：例如在下

4、面命题中：（1）张明是个劳动模范。）张明是个劳动模范。（2）李华是个劳动模范。）李华是个劳动模范。刻划客体的性质刻划客体的性质 （3）王红王红是个大学生。是个大学生。（4）小李比小赵高小李比小赵高2cm。（5）点）点a在在b与与c之间。之间。刻划客体之间的相互关系刻划客体之间的相互关系 （6）阿杜与阿寺同岁。阿杜与阿寺同岁。“是个劳动模范是个劳动模范”、“是个大学生是个大学生”、“比比高高2cm”、“在在与与之间之间”都是都是谓词。谓词。2022-8-5计算机科学与技术学院谓词的概念与表示谓词的概念与表示(n刻划刻划一个客体性质一个客体性质的词称之为的词称之为一元谓词一元谓词,刻划刻划n个客体

5、个客体之间关系之间关系的词称之为的词称之为n元谓词元谓词.n一般我们用大写英文字母表示一般我们用大写英文字母表示谓词，谓词，用小写英文字母用小写英文字母表示客体名称，例如，表示客体名称，例如，将上述谓词分别记作大写字母将上述谓词分别记作大写字母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(a,b)a:阿杜。阿杜。b:阿寺。阿寺。其中其中(1)、(2)、(3)为一元谓词，为一元谓词，(4)、(6)为二元谓词，为二元谓词，(

6、5)为三元谓词。为三元谓词。2022-8-5计算机科学与技术学院谓词的概念与表示谓词的概念与表示(n注注:n(1)单独一个谓词并不是命题，在谓词字母单独一个谓词并不是命题，在谓词字母后填上客体所得到的式子称之为谓词填式。后填上客体所得到的式子称之为谓词填式。n(2)在谓词填式中，若客体确定，则在谓词填式中，若客体确定，则A(a1，a2.an)就变成了命题就变成了命题 n(3)在多元谓词表达式中，客体字母出现的在多元谓词表达式中，客体字母出现的先后次序与事先约定有关先后次序与事先约定有关,一般不可以随意交一般不可以随意交换位置换位置(如如,上例中上例中H(s,t)与与H(t,s)代表两个不代表两

7、个不同的命题同的命题)。2022-8-5计算机科学与技术学院谓词的概念与表示谓词的概念与表示(n 设谓词设谓词H表示表示“是劳动模范是劳动模范”,a表示客体名称表示客体名称张明张明,b表示客体名称表示客体名称李华李华,c表示客体名称这只老表示客体名称这只老虎，虎，那么那么H(a)、H(b)、H(c)表示三个不同的命表示三个不同的命题题,但它们有一个共同的形式但它们有一个共同的形式,即即H(x).一般地，一般地，H(x)表示客体表示客体x具有性质具有性质H。这里。这里x表示抽象的或表示抽象的或泛指的客体，称为泛指的客体，称为客体变元客体变元，常用小写英文字母，常用小写英文字母x,y,z,表示。相

8、应地，表示具体或特定的客体表示。相应地，表示具体或特定的客体的词称为的词称为客体常项客体常项，常用小写英文字母，常用小写英文字母a,b,c,表表 示。示。2022-8-5计算机科学与技术学院谓词的概念与表示谓词的概念与表示(同理，客体变元同理，客体变元x，y具有关系具有关系L，记作，记作L(x,y);客体变元客体变元x,y,z具有关系具有关系A，记作，记作A(x,y,z).nH(x)、L(x,y)、A(x,y,z)本身并不是一个命题本身并不是一个命题.只只有用特定的客体取代客体变元有用特定的客体取代客体变元x,y,z后，它们才成为后，它们才成为命题。我们称命题。我们称H(x)、L(x,y)、A

9、(x,y,z)为为命题函数。命题函数。一般地我们有一般地我们有2022-8-5计算机科学与技术学院谓词的概念与表示谓词的概念与表示(n定义定义2.1.1:由一个谓词由一个谓词H和和n个客体变元组成的表个客体变元组成的表达式达式H(x1,x2,xn)称为称为n元元简单命题函数简单命题函数.n由定义可知由定义可知,n元谓词就是有元谓词就是有n个客体变元的个客体变元的命题命题函数函数.当当n=0时时,称为称为0元谓词元谓词.因此因此,一般情况下一般情况下,命题命题函数不是命题函数不是命题;特殊情况特殊情况0元谓词就变成一个命题元谓词就变成一个命题.n复合命题函数复合命题函数:由一个或几个简单命题函数

10、以及由一个或几个简单命题函数以及逻辑联结词组合而成的表达式逻辑联结词组合而成的表达式.2022-8-5计算机科学与技术学院谓词的概念与表示谓词的概念与表示(例例1:若若x的学习好的学习好,则则x的工作好的工作好 设设S(x):x学习好；学习好；W(x):x工作好工作好 则有则有S(x)W(x)例例2:将下列命题用将下列命题用0元谓词符号化元谓词符号化.(1)2是素数且是偶数是素数且是偶数.(2)如果如果2大于大于3,则则2大于大于4.(3)如果如果张明比李民高张明比李民高,李民比赵亮高李民比赵亮高,则张明比赵亮则张明比赵亮高高.2022-8-5计算机科学与技术学院谓词的概念与表示谓词的概念与表

11、示(n解解:(1)设设F(x):x是素数是素数.G(x):x是偶数是偶数.则则命题符号化为：命题符号化为：F(2)G(2)(2)设设L(x,y)：x大于大于y.则则命题符号化为：命题符号化为：L(2,3)L(2,4)(3)设设 H(x,y):x比比y高高.a:张明张明 b:李民李民 c：赵亮：赵亮 则则命题符号化为：命题符号化为：H(a,b)H(b,c)H(a,c)注意注意:命题函数中命题函数中,客体变元在哪些范围内取特定的客体变元在哪些范围内取特定的值值,对命题的真值极有影响对命题的真值极有影响.2022-8-5计算机科学与技术学院谓词的概念与表示谓词的概念与表示(例如例如:H(x,y)H(

12、y,z)H(x,z)n若若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米米”,当当x,y,z为平面上的为平面上的点，则这个式子表示点，则这个式子表

13、示“若若x距距y10米且米且y距距z10米，则米，则x距距z10米米”。这个命题的真值将由。这个命题的真值将由x,y,z的具体位置的具体位置而定，它可能是而定，它可能是1，也可能是，也可能是0。2022-8-5计算机科学与技术学院谓词的概念与表示谓词的概念与表示(n在命题函数中，客体变元的取值范围称为在命题函数中，客体变元的取值范围称为个体个体域域，又称之为论域。个体域可以是有限事物的，又称之为论域。个体域可以是有限事物的集合，也可以是无限事物的集合。集合，也可以是无限事物的集合。n全总个体域：全总个体域：宇宙间一切事物组成的个体域称宇宙间一切事物组成的个体域称为为全总个体域。全总个体域。20

14、22-8-5计算机科学与技术学院谓词的概念与表示谓词的概念与表示(n2.1.2 量词量词(Quantifiers)n量词量词：分为全称量词：分为全称量词()和存在量词和存在量词()1.全称量词全称量词(The Universal Quantifiers)对日常语言中的对日常语言中的“一切一切”、“所有所有”、“凡凡”、“每一每一个个”、“任意任意”等词，等词，用符号用符号“”表示表示，表示表示对个体域里的所有个体，对个体域里的所有个体，()表示个体域表示个体域里的所有个体具有性质里的所有个体具有性质F.符号符号“”称为称为全称量词全称量词.2022-8-5计算机科学与技术学院谓词的概念与表示谓

15、词的概念与表示(例例3：在谓词逻辑中将下列命题符号化在谓词逻辑中将下列命题符号化.（1）凡是人都呼吸。）凡是人都呼吸。（2）每个学生都要参加考试。）每个学生都要参加考试。(3)任何整数或是正的或是负的。任何整数或是正的或是负的。解解:(1)当个体域为当个体域为人类集合人类集合时：时：令令F(x):x呼吸。则（呼吸。则（1）符号化为）符号化为 xF(xxF(x)当个体域为当个体域为全总个体域全总个体域时：时：令令M(x):x是人。则（是人。则（1）符号化为）符号化为 x(M(x)x(M(x)F(x).F(x).2022-8-5计算机科学与技术学院谓词的概念与表示谓词的概念与表示(2)当个体域为当

16、个体域为全体学生的集合全体学生的集合时：时：令令P(x):x要参加考试。则（要参加考试。则（2）符号化为）符号化为 xP(xxP(x)当个体域为当个体域为全总个体域全总个体域时：时：令令S(x):x是学生。则（是学生。则（2）符号化为）符号化为 x(S(x)x(S(x)P(x).P(x).2022-8-5计算机科学与技术学院谓词的概念与表示谓词的概念与表示(3)当个体域为当个体域为全体整数的集合全体整数的集合时：时：令令P(x):x是正的。是正的。N(x):x是负的。则（是负的。则（3）符）符号化为号化为 x(P(x)x(P(x)N(x)当个体域为当个体域为全总个体域全总个体域时：时：令令I(

17、x):x是是整数整数。则（。则（3）符号化为）符号化为 x(I(x)x(I(x)(P(x)(P(x)N(x).).2022-8-5计算机科学与技术学院谓词的概念与表示谓词的概念与表示(2.存在量词存在量词(The Existential Quantifiers)对日常语言中的对日常语言中的“有一个有一个”、“有的有的”、“存在存在着着”、“至少有一个至少有一个”、“存在一些存在一些”等等词，词，用符号用符号“”表示表示，表示存在个体域里的个体，表示存在个体域里的个体，()表示存在个体域里的个体具有性质表示存在个体域里的个体具有性质F.符号符号“”称为称为存在存在量词量词.例例4：在谓词逻辑中将

18、下列命题符号化在谓词逻辑中将下列命题符号化.（1）一些数是有理数。）一些数是有理数。（2）有些人活百岁以上。）有些人活百岁以上。2022-8-5计算机科学与技术学院谓词的概念与表示谓词的概念与表示(解解:(1)令令Q(x):x是有理数。则（是有理数。则（1）符号化为）符号化为 Q(x)（2）当个体域为）当个体域为人类集合人类集合时：时：令令G(x):x活百岁以上。则（活百岁以上。则（2）符号化为）符号化为 xG(x)当个体域为当个体域为全总个体域全总个体域时：时：令令M(x):x是人。则（是人。则（2）符号化为）符号化为 x(M(x)G(x)2022-8-5计算机科学与技术学院谓词的概念与表示

19、谓词的概念与表示(有时需要同时使用多个量词。有时需要同时使用多个量词。例例5.命题命题“对任意的对任意的x,存在存在y,使得使得x+y=5”,取取个个体域为实数体域为实数集合集合,则该命题则该命题符号化为符号化为:x y H(x,y).其中其中H(x,y):x+y=5.这是个真命题这是个真命题.2022-8-5计算机科学与技术学院谓词的概念与表示谓词的概念与表示(3.使用使用量词时应注意的问题量词时应注意的问题（1）在不同的个体域，同一命题的符号化形式）在不同的个体域，同一命题的符号化形式可能相同也可能不同。可能相同也可能不同。（2）在不同的个体域，同一命题的真值可能相）在不同的个体域，同一命

20、题的真值可能相同也可能不同。同也可能不同。(如如,R（x）表示）表示x为大学生。如为大学生。如果个体域为大学里的某个班级的学生，则果个体域为大学里的某个班级的学生，则 x R（x）为真；若个体域为中学里的某个班）为真；若个体域为中学里的某个班级的学生，则级的学生，则 x R（x）为假）为假.).2022-8-5计算机科学与技术学院谓词的概念与表示谓词的概念与表示(（3）约定以后如不指定个体域，默认为全总个体）约定以后如不指定个体域，默认为全总个体域。对每个客体变元的变化范围域。对每个客体变元的变化范围,用特性谓词加用特性谓词加以限制以限制.特性谓词特性谓词:限定客体变元变化范围的谓词限定客体变

21、元变化范围的谓词(如例如例3中中的的M（x）).一般而言，对全称量词，特性谓词常作蕴含的前一般而言，对全称量词，特性谓词常作蕴含的前件，如（件，如（x）(M(x)F(x)；对存在量词，特性；对存在量词，特性谓词常作合取项，如（谓词常作合取项，如（x）(M(x)G(x).2022-8-5计算机科学与技术学院谓词的概念与表示谓词的概念与表示(4)一般来说，当多个量词同时出现时，它们的顺一般来说，当多个量词同时出现时，它们的顺序不能随意调换。如：序不能随意调换。如：在实数域上用在实数域上用H(x,y)表示表示x+y=5,则命题则命题“对于任对于任意的意的x,都存在都存在y使得使得x+y=5”可符号化

22、为：可符号化为：x yH(x,y),其真值为其真值为1.若调换量词顺序后为：若调换量词顺序后为：y xH(x,y),其真值为其真值为0。(5)当个体域为有限集合时当个体域为有限集合时,如如D=a1,a2,an,对任对任意谓词意谓词A(x),有有2022-8-5计算机科学与技术学院谓词的概念与表示谓词的概念与表示(x)A(x)A(a1)A(a2)A(an)（x）A(x)A(a1)A(a2)A(an)例例6：在谓词逻辑中将下列命题符号化：在谓词逻辑中将下列命题符号化.（1）所有的人都长头发。）所有的人都长头发。（2）有的人吸烟。）有的人吸烟。（3）没有人登上过木星。）没有人登上过木星。（4）清华大

23、学的学生未必都是高素质的。）清华大学的学生未必都是高素质的。解：令解：令M(x):x是人。（特性谓词）是人。（特性谓词）（1）令令F(x):x长头发。则符号化为：长头发。则符号化为：（x）(M(x)F(x)2022-8-5计算机科学与技术学院谓词的概念与表示谓词的概念与表示(（2）令令S(x):x吸烟。则符号化为：吸烟。则符号化为：（x x）(M(x)(M(x)S(x)(x)（3）令令D(x):x登上过木星。则符号化为：登上过木星。则符号化为：(x)(M(x)D(xx)(M(x)D(x)（4）令）令Q(x):x是清华大学的学生。是清华大学的学生。H(x):x是高素是高素质的。则符号化为：质的。

24、则符号化为：(x)(Q(xx)(Q(x)H(x)(x)2022-8-5计算机科学与技术学院谓词的概念与表示谓词的概念与表示(小结小结:本节将原子命题进行分解本节将原子命题进行分解,分为客体和谓词分为客体和谓词两部分两部分.进而介绍了客体和谓词、一元谓词和进而介绍了客体和谓词、一元谓词和n元元谓词谓词、命题函数、全称量词和存在量词等概念。、命题函数、全称量词和存在量词等概念。重点掌握重点掌握一元谓词和一元谓词和n元谓词的概念、元谓词的概念、全称量词全称量词和存在量词及量化命题的符号化。和存在量词及量化命题的符号化。作业作业:1.预习第二章预习第二章2.2,2.3 2.习题习题2.12022-8-

25、5计算机科学与技术学院2.2 谓词公式与翻译谓词公式与翻译(Predicate formulaen2.2谓词公式与翻译谓词公式与翻译(Predicate formulae nn元元谓词谓词A(x1，x2.xn)称为谓词演算的称为谓词演算的原子公式。原子公式。定义定义2.2.1谓词演算的谓词演算的合式公式合式公式,可由下述各条组成可由下述各条组成:（1）原子公式是合式公式。）原子公式是合式公式。（2）若）若A 是合式公式，则是合式公式，则(A)也是合式公式。也是合式公式。（3）若）若A，B是合式公式，则是合式公式，则(A B)，(A B)，(A B)，(A B)也是合式公式。也是合式公式。（4）

26、若）若A是合式公式，是合式公式，x是是A中出现的任何变元中出现的任何变元,则则(x)x)A,(x)x)A，也是合式公式。，也是合式公式。(5)只有有限次应用只有有限次应用(1)(4)得到的公式是得到的公式是合式公式合式公式.2022-8-5计算机科学与技术学院2.2 谓词公式与翻译谓词公式与翻译(Predicate formulae例例1：在谓词逻辑中将下列命题符号化在谓词逻辑中将下列命题符号化.（1）凡正数都大于零。）凡正数都大于零。（2）存在小于）存在小于2的素数。的素数。（3）没有不能表示成分数的有理数。）没有不能表示成分数的有理数。（4）并不是所有参加考试的人都能取得好成绩。）并不是所

27、有参加考试的人都能取得好成绩。解：（解：（1）令令F(x):x是正数。是正数。M(x):x大于零。则大于零。则符号化为：（符号化为：（x）(F(x)M(x)2022-8-5计算机科学与技术学院2.2 谓词公式与翻译谓词公式与翻译(Predicate formulae（2）令令E(x):x小于小于2。S(x):x是素数。是素数。则符号化为：则符号化为：（x)(E(x)S(x)真值为真值为0。（3）令）令D(x):x是有理数。是有理数。F(x):x能表示成分数。能表示成分数。则符号化为：则符号化为：(x)(D(x)F(x)或或 (x)(D(x)F(x)真值为。真值为。（4）令）令M(x)：x是人是

28、人.Q(x):x参加考试。参加考试。H(x):x取得取得好成绩。则符号化为：好成绩。则符号化为：(x)(M(x)Q(x)H(x)或或 (x)(M(x)Q(x)H(x)2022-8-5计算机科学与技术学院2.2 谓词公式与翻译谓词公式与翻译(Predicate formulaen例例2：在谓词逻辑中将下列命题符号化在谓词逻辑中将下列命题符号化.（1）所有运动员都钦佩某些教练）所有运动员都钦佩某些教练.（2）有些运动员不钦佩教练）有些运动员不钦佩教练.设：设：L(x):x是运动员是运动员 J(y):y是教练是教练 A(x,y):x钦佩钦佩y(1)(1)(x)x)(L(x)L(x)（y)y)(J(y

29、)(y)A(x,y)(x,y)(2)(2)（x)x)(L(x)L(x)(y)y)(J(y)(y)A(x,y(x,y)2022-8-5计算机科学与技术学院2.2 谓词公式与翻译谓词公式与翻译(Predicate formulaen例例3：在谓词逻辑中将下列命题符号化在谓词逻辑中将下列命题符号化.（1）那位戴眼镜的用功的大学生在看这本大而厚的巨著）那位戴眼镜的用功的大学生在看这本大而厚的巨著.（2）P63(7)解解:(1)设：设：S(x):x是大学生是大学生.A(x):x戴眼镜戴眼镜.B(x):x用功用功.D(x):x是巨著是巨著.F(x,y):x看看y.E(y):y是大的是大的.G(y):y是厚

30、的是厚的.a:那位那位 b:这本这本(1)(1)符号化为符号化为:A(a)B(a)S(a)D(b)E(b)G(b)F(a,b)2022-8-5计算机科学与技术学院2.2 谓词公式与翻译谓词公式与翻译(Predicate formulae（2）设：）设：P(x,y):x在在y连续连续.Q(x,y):x大于大于y.(2)符号化为符号化为:P(f,a)()(Q(,0)()Q(,0)(x)(Q(,)Q(,)P(f,a)()()(x)(Q(,0)(Q(,0)(Q(,)Q(,).axax)()(afxf)()(afxf2022-8-5计算机科学与技术学院2.2 谓词公式与翻译谓词公式与翻译(Predica

31、te formulaen小结：小结：本节介绍了本节介绍了谓词合式谓词合式公式的概念，公式的概念，重点掌握重点掌握谓词公式的翻译谓词公式的翻译.作业作业:P41 1:P41 1，2 22022-8-5计算机科学与技术学院2.3 变元的约束变元的约束(Bound of variable2.3 变元的约束变元的约束(Bound of variable2.3.1 变元的约束变元的约束2.3.2 约束变元的约束变元的换名与换名与自由变元的自由变元的代入代入2022-8-5计算机科学与技术学院2.3 变元的约束变元的约束(Bound of variable2.3.1变元的约束变元的约束(Bound of

32、variable定义定义2.3.1:在在谓词谓词公式公式中中,形如形如(x)P(x)和和(x)P(x)的部分的部分,称为谓词称为谓词公式的公式的x约束部分约束部分.(x)P(x)或或(x)P(x)中的中的x叫做叫做量词的量词的指导变元指导变元或或作用变作用变元元，P(x)称为称为相应量词的相应量词的作用域作用域或或辖域辖域。2022-8-5计算机科学与技术学院2.3 变元的约束变元的约束(Bound of variable在在 x和和 x的辖域中，的辖域中，x的所有出现都称为的所有出现都称为约束出约束出现现，相应的，相应的x称为称为约束变元约束变元;P(x)中除约束变元以中除约束变元以外出现的

33、变元称为是外出现的变元称为是自由变元自由变元。例例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)2022-8-5计算机科学与技术学院2.3 变元的约束变元的约束(Bound of variablen说明说明:(1)n元谓词公式元谓词公式A(x1，x2.xn)中有中有n个自由变元个自由变元,若若对其中的对其中的k(kn)个进行约束个进行约束,则构成了则构成了n-k元谓词元谓词;如果一个公式中没有自由变元出现如果一个公式中没有自由变元出现,则该公式就则该公式就变成了一个命题变成了一个命题(2)一个公式的约束变元所使用的名称符号是无关一个公式

34、的约束变元所使用的名称符号是无关紧要的紧要的,如如(x)M(x)与与(y)M(y)意义相同意义相同.2022-8-5计算机科学与技术学院2.3 变元的约束变元的约束(Bound of variablen2.3.2 约束变元的约束变元的换名与换名与自由变元的自由变元的代入规则代入规则 在例在例1中中,一个变元在同一个公式中既是自由一个变元在同一个公式中既是自由出现又是约束出现出现又是约束出现,这样在理解上容易发生混淆这样在理解上容易发生混淆.为为了避免这种混乱了避免这种混乱,可对可对约束变元进行换名约束变元进行换名.换名规则换名规则:(对约束变元而言）对约束变元而言）对约束变元进行换名对约束变元

35、进行换名,使得一个变元在一个公式中使得一个变元在一个公式中只呈一种形式出现只呈一种形式出现.2022-8-5计算机科学与技术学院2.3 变元的约束变元的约束(Bound of variable(1)约束变元可以换名约束变元可以换名,其更改的变元名称范围是量其更改的变元名称范围是量词中的指导变元以及该量词作用域中所出现的词中的指导变元以及该量词作用域中所出现的该变元该变元,公式的其余部分不变公式的其余部分不变.(2)换名时一定要更改为作用域中没有出现的变元换名时一定要更改为作用域中没有出现的变元名称名称.2022-8-5计算机科学与技术学院2.3 变元的约束变元的约束(Bound of vari

36、ablen例例1:x(P(x)R(x,y)L(x,y)换名为换名为 t(P(t)R(t,y)L(x,y)n x(H(x,y)y(W(y)L(x,y,z)换名为换名为 x(H(x,y)s(W(s)L(x,s,z)2022-8-5计算机科学与技术学院2.3 变元的约束变元的约束(Bound of variablen代入规则代入规则（对自由变元而言）（对自由变元而言）对公式中自由变元的更改称为代入对公式中自由变元的更改称为代入(1)对于谓词公式中的自由变元可以作代入对于谓词公式中的自由变元可以作代入,代入时代入时需要对公式中出现该自由变元的需要对公式中出现该自由变元的每一处每一处进行进行;(2)用以

37、代入的变元与原公式中所有变元的名称不用以代入的变元与原公式中所有变元的名称不能相同能相同.例如对例例如对例1中的公式中的公式 x(P(x)R(x,y)L(x,y)自由变元自由变元y用用z来代入来代入,得得 x(P(x)R(x,z)L(x,z)2022-8-5计算机科学与技术学院2.3 变元的约束变元的约束(Bound of variablen小结：小结：本节介绍了本节介绍了约束变元、约束变元、自由变元自由变元的概念，的概念，重点掌握重点掌握约束变元的约束变元的换名与换名与自由变元的自由变元的代入代入.作业作业:P43:2，32022-8-5计算机科学与技术学院2.4 谓词演算的等价式与蕴含式谓

38、词演算的等价式与蕴含式2.4谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式(Equivalences&implications of predicate calculus)2.4.1谓词的等价和永真的概念谓词的等价和永真的概念2.4.2谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式2022-8-5计算机科学与技术学院2.4 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式2.4.1谓词的等价和永真的概念谓词的等价和永真的概念定义定义2.4.1:给定任意的谓词公式给定任意的谓词公式A,其个体域为其个体域为E,对于对于A的的所有赋值所有赋值,公式公式A都为真都为真,则称则称A在在E上是上是永真

39、的永真的(或有效或有效的的);若对于若对于A的所有赋值的所有赋值,公式公式A都为假都为假,则称则称A在在E上是上是永假的永假的(或不可满足的或不可满足的);若至少存在着一种赋值使得公若至少存在着一种赋值使得公式式A为真为真,则称则称A在在E上是上是可满足的可满足的.n定义定义2.4.2:给定任何两个谓词公式给定任何两个谓词公式A、B，设它们有共，设它们有共同的个体域同的个体域E，若对，若对A和和B的任一组变元进行赋值，所的任一组变元进行赋值，所得命题的真值相同，则称得命题的真值相同，则称谓词公式谓词公式A和和B在在E上等价上等价，并记为并记为A B2022-8-5计算机科学与技术学院2.4 谓

40、词演算的等价式与蕴含式谓词演算的等价式与蕴含式n1、命题公式的推广、命题公式的推广在命题公式中成立的式子，用谓词公式去代换其在命题公式中成立的式子，用谓词公式去代换其中相应的命题变元，得到的公式依然成立中相应的命题变元，得到的公式依然成立如：如：x x(P(x)P(x)Q(x)Q(x)x x(P(xP(x)Q(x)Q(x)P(x)P(x)Q(xQ(x)（P(x)P(x)Q(x)Q(x)）等等n2、量词与、量词与之间的关系之间的关系 (x)P(x)x)P(x)(x)x)P(xP(x)(x)P(x)x)P(x)(x)x)P(xP(x)2022-8-5计算机科学与技术学院2.4 谓词演算的等价式与蕴

41、含式谓词演算的等价式与蕴含式n3 3、量词辖域的扩张与收缩、量词辖域的扩张与收缩量词辖域中如果有合取或析取项，且其中有一个量词辖域中如果有合取或析取项，且其中有一个是命题，则可将该命题移至量词辖域之外。如：是命题，则可将该命题移至量词辖域之外。如：（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 2022-8-5计算机科学与技术学院2.4 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式n量词辖域的扩张量词辖域的扩张（xA(x)B）（x)(A(x)B）(（x)A(x)B)(x)(A(x)B）(B(x

42、)A(x)）（x)(B A(x)）(B(x)A(x)(x)(B A(x)另有多个公式见课本另有多个公式见课本70页页2022-8-5计算机科学与技术学院2.4 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式n4、量词分配等值式、量词分配等值式设设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)(3)x(A(x)B(x)x A(x)x B(x)(4)x(A(x)B(x)x A(x)x B(x)2022-8-5计算机科学与技术学院n5.谓词演算蕴含式谓词

43、演算蕴含式n xA(x)xA(x)xB(xxB(x)x(A(x)B(x)x(A(x)B(x)x(A(x)B(x)x(A(x)B(x)x A(x)x A(x)x B(x)x B(x)6.6.多个量词的使用多个量词的使用 多个量词同时出现时多个量词同时出现时,其顺序是至关重要的其顺序是至关重要的.2.4 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式2022-8-5计算机科学与技术学院2.4 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式n x y P(x,y)y x P(x,y)y x P(x,y)x y P(x,y)x y P(x,y)y x P(x,y)y x P(x,y)x y P(x

44、,y)2022-8-5计算机科学与技术学院2.4 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式n小结：本节介绍了谓词公式的概念及谓词演算小结：本节介绍了谓词公式的概念及谓词演算的的等价式与蕴涵式等价式与蕴涵式，重点掌握谓词演算的，重点掌握谓词演算的等价等价式与蕴涵式式与蕴涵式n作业作业:P50:1(1),(3)；2,3(1)；42022-8-5计算机科学与技术学院2.5 前束范式前束范式(Prenex Normal Form2.5 前束范式前束范式(Prenex normal form2.5.1 前束范式前束范式(Prenex normal form 2.5.2 前束析取范式和前束合取范式

45、前束析取范式和前束合取范式(Prenex disjunctive normal form&Prenex conjunctive normal form 2022-8-5计算机科学与技术学院2.5 前束范式前束范式(Prenex Normal Form2.5.1前束范式前束范式(Prenex normal form n定义定义2.5.1:任何一个谓词公式任何一个谓词公式A，如果具有如下形式：，如果具有如下形式：(x1)(x2)(xn)B其中其中可能是量词可能是量词 或量词或量词，xi（i=1，n）是客体变是客体变元，元，B是不含量词的是不含量词的谓词公式，则称谓词公式，则称A是前束范式。是前束范

46、式。n说明说明:前束范式前束范式的量词均在全式的开头的量词均在全式的开头,它们的作用域它们的作用域延伸到整个公式的末尾。延伸到整个公式的末尾。n例例1:x y（F(x)G(y)）H(x,y)）x y(F(x,y)G(y,z)x H(x,y,z)2022-8-5计算机科学与技术学院2.5 前束范式前束范式(Prenex Normal Formn定理定理2.5.1:任何一个谓词公式任何一个谓词公式,均和一个前束范均和一个前束范式等价。式等价。前束范式的求法：前束范式的求法：第一步：否定深入。即利用量词转化公式，把否定联结第一步：否定深入。即利用量词转化公式，把否定联结 词深入到命题变元和词深入到命

47、题变元和谓词填式的谓词填式的前面。前面。第二步：改名。即利用换名规则、代入规则更换一些变第二步：改名。即利用换名规则、代入规则更换一些变元的名称，以便消除混乱。元的名称，以便消除混乱。第三步：量词前移。即利用量词辖域的收缩与扩张把量第三步：量词前移。即利用量词辖域的收缩与扩张把量词移到前面。这样便可求出与公式等价的前束范式。词移到前面。这样便可求出与公式等价的前束范式。2022-8-5计算机科学与技术学院2.5 前束范式前束范式(Prenex Normal Form例例2:2:求下列公式的前束范式。求下列公式的前束范式。),(),()(),()(),()()6(),()()()(),()()5

48、()()()()()4()()()()()3()()()()()2()()()()()1(yxBxyAyyxByxyxAyxyxHxyGyyxFxxGxxFxxGxxFxxGxxFxxGxxFx2022-8-5计算机科学与技术学院2.5 前束范式前束范式(Prenex Normal Formn解解:)()()()()()()()()()()()1(量词分配量词转换律xGxFxxGxxFxxGxxFx)()()()()()()()()()()()()()()()()()()()()2(辖域扩张辖域扩张换名量词转换律yGxFyxyGyxFxyGyxFxxGxxFxxGxxFx2022-8-5计算机

49、科学与技术学院2.5 前束范式前束范式(Prenex Normal Form )(,()(),()()()()(,()()(),()()()(,()()(),()()()(,()()()(),()()(,()()()(),()(),()()()(),()(),()()()(),()(),()()()(),()(),()()()(),()()5(辖域扩张辖域扩张辖域扩张换名代入ztHyGzxFtyxztHtyGzxFyxztHtyGzxFyxztHtyGyzxFxzxHxyGyzxFxyxHxyGyyxFxyxHxyGyyxFxyxHxyGyyxFxyxHxyGyyxFx2022-8-5计算机科

50、学与技术学院2.5 前束范式前束范式(Prenex Normal Formn (6)()()(,)()()(,)()(,)(,)()()(,)()()(,)()(,)(,)()()(,)()()(,)()(,)(,)xy A x yxy B x yyA y xB x yxy A x yxy B x yyA y xB x yxy A x yxyB x yyA y xB x y 2022-8-5计算机科学与技术学院2.5 前束范式前束范式(Prenex Normal Form ),(),(),(),()()()()()(,(),()(),()(),()(),(),()(),()(),()()6(z