离散数学课件(第2章).ppt

离散数学离散数学教案教案计算机科学与技术学院计算机科学与技术学院课程学时：课程学时：64主主 讲：宋讲：宋 成成河南理工大学河南理工大学电子教案电子教案第二章：谓词逻辑第二章：谓词逻辑2.1谓词的概念与表示谓词的概念与表示2.2命题函数与量词命题函数与量词2.3谓词公式与翻译谓词公式与翻译2.4变元的约束变元的约束2.5谓词演算的等价式和蕴含式谓词演算的等价式和蕴含式2.6前束范式前束范式2.7谓词演算的推理理论谓词演算的推理理论教学目的及要求：教学目的及要求：深刻理解和掌握谓词逻辑的基本概念和基本推理方深刻理解和掌握谓词逻辑的基本概念和基本推理方法法教学类容：教学类容：谓词的概念与表示、命题函数与量词、谓词公式与谓词的概念与表示、命题函数与量词、谓词公式与翻译、变量的约束、谓词演算的等价式与蕴含式、翻译、变量的约束、谓词演算的等价式与蕴含式、前束范式、谓词演算的推理理论。前束范式、谓词演算的推理理论。教学重点：教学重点：谓词逻辑中基本概念和基本推理方法。谓词逻辑中基本概念和基本推理方法。教学难点：教学难点：谓词演算的推理理论。谓词演算的推理理论。第二章：谓词逻辑第二章：谓词逻辑2.1 谓词的概念与表示谓词的概念与表示 在研究命题逻辑中，原子命题是命题演算中的最基在研究命题逻辑中，原子命题是命题演算中的最基小单位，不在对原子命题进行分解，这样会产生两小单位，不在对原子命题进行分解，这样会产生两大缺点大缺点1.不能研究命题的结构、成分和内部的逻辑特征；不能研究命题的结构、成分和内部的逻辑特征；2.也不能表达两个原子命题所具有的共同特征，甚至在命也不能表达两个原子命题所具有的共同特征，甚至在命题逻辑中无法处理一些简单又常见的过程。题逻辑中无法处理一些简单又常见的过程。例：苏格拉底论证是正确的，但是不能用命题逻辑的例：苏格拉底论证是正确的，但是不能用命题逻辑的推理规则推导出来。推理规则推导出来。“所有的人都是要死的所有的人都是要死的”A “苏格拉底是人苏格拉底是人”B “所以苏格拉底是要死的所以苏格拉底是要死的”C第二章：谓词逻辑第二章：谓词逻辑1、客体（个体）、客体（个体）考察下面的三个原子命题：考察下面的三个原子命题：李玲是优秀共产党员。李玲是优秀共产党员。张华比李红高。张华比李红高。小高坐在小王和小刘的中间。小高坐在小王和小刘的中间。上述命题中的李玲、张华、李红、小高、小王、上述命题中的李玲、张华、李红、小高、小王、小刘等就是客体。所以可以这样说，客体是指所小刘等就是客体。所以可以这样说，客体是指所研究对象中可以独立存在的具体的或抽象的个体。研究对象中可以独立存在的具体的或抽象的个体。它可以是独立存在的人或物体，也可以是抽象的它可以是独立存在的人或物体，也可以是抽象的概念，如概念，如“马列主义马列主义”，“资本主义资本主义”等。客体等。客体常用小写英文字母或小写英文字母带下标表示，常用小写英文字母或小写英文字母带下标表示，叫做客体标识符。叫做客体标识符。第二章：谓词逻辑第二章：谓词逻辑 表示具体或特定客体的标识符称作客体常元，一般用小写英表示具体或特定客体的标识符称作客体常元，一般用小写英文字母文字母a、b、c、或这些英文字母带下标表示。例如：李或这些英文字母带下标表示。例如：李玲、张华、李红、小高、小王、小刘可如下表示：玲、张华、李红、小高、小王、小刘可如下表示：a：李玲：李玲 b：张华：张华 c：李红：李红 d：小高：小高 e：小王：小王 f：小刘：小刘 a,b,c,d,e,f都是客体常元。都是客体常元。将表示任意客体或泛指某类客体的标识符称为客体变元，将表示任意客体或泛指某类客体的标识符称为客体变元，常表示为常表示为x、y、z、等或这些英文字母带下标。等或这些英文字母带下标。客体变元的变化范围称为客体域或论域。客体域可以是有穷客体变元的变化范围称为客体域或论域。客体域可以是有穷集合，也可以是无穷集合，包含任意客体的客体域称为全总集合，也可以是无穷集合，包含任意客体的客体域称为全总客体域，它是由宇宙间一切对象组成的集合。客体域，它是由宇宙间一切对象组成的集合。第二章：谓词逻辑第二章：谓词逻辑2、谓词、谓词 在上面的三个原子命题中，在上面的三个原子命题中，可以分解成为客体可以分解成为客体“李玲李玲”和和“是优秀共产党员是优秀共产党员”两部分。两部分。“是优秀共产党员是优秀共产党员”是用来描述个体是用来描述个体“李玲李玲”的性质的；的性质的；可以分解成为客体可以分解成为客体“张华张华”、“李红李红”和和“比比高高”两部分。两部分。“比比高高”是用来描述客体是用来描述客体“张华张华”和和“李红李红”的身高关系的；的身高关系的；可以分解成为客体可以分解成为客体“小高小高”、“小王小王”、“小刘小刘”和和“坐在坐在和和的中间的中间”两部分。两部分。“坐在坐在和和的中间的中间”是是用来描述客体用来描述客体“小高小高”、“小王小王”、“小刘小刘”的位置关系的位置关系的。的。【定义定义】用以刻划客体性质或关系的即是谓词。谓词常用大用以刻划客体性质或关系的即是谓词。谓词常用大写英文字母表示，叫做谓词标识符。写英文字母表示，叫做谓词标识符。例如可以用例如可以用F，G，H表示上面三个命题中谓词：表示上面三个命题中谓词：F：是优秀共产党员。是优秀共产党员。G：比比高。高。H：坐在坐在和和的中间。的中间。第二章：谓词逻辑第二章：谓词逻辑 把与一个客体相关联的谓词叫做一元谓词。把与一个客体相关联的谓词叫做一元谓词。F是一元谓词；把与是一元谓词；把与两个客体相关联的谓词叫做二元谓词。两个客体相关联的谓词叫做二元谓词。G是二元谓词；把与三是二元谓词；把与三个客体相关联的谓词叫做三元谓词。个客体相关联的谓词叫做三元谓词。H是三元谓词；是三元谓词；。一般。一般的，把与的，把与n个客体相关联的谓词叫做个客体相关联的谓词叫做n元谓词。元谓词。设设F是一元谓词，是一元谓词，a是客体常元，用是客体常元，用F(a)表示客体常元表示客体常元a具有具有性质性质F；设；设G是二元谓词，是二元谓词，a,b是客体常元，用是客体常元，用G(a,b)表示客体表示客体常元常元a和和b具有关系具有关系G；于是上面三个命题就表示为：于是上面三个命题就表示为：F(a)：李玲是优秀共产党员。：李玲是优秀共产党员。G(b,c)：张华比李红高。：张华比李红高。H(d,e,f)：小高坐在小王和小刘的中间。：小高坐在小王和小刘的中间。将谓词字母后面填上相关联的客体常元所得的式子叫做谓词填将谓词字母后面填上相关联的客体常元所得的式子叫做谓词填式。式。F(a)，G(b,c)，H(d,e,f)都是谓词填式。谓词填式表示的都是谓词填式。谓词填式表示的是命题。是命题。第二章：谓词逻辑第二章：谓词逻辑2.2谓词函数与量词谓词函数与量词1、命题函数、命题函数 客体在谓词表达式中可以是任意名词。客体在谓词表达式中可以是任意名词。【例例】C：总是要死的。：总是要死的。j:张三；张三；t：老虎；：老虎；e:桌子桌子 则则C(j)，C(t)，C(e)均表达了命题。均表达了命题。在上面的例子中，在上面的例子中，C：表示总是要死的，：表示总是要死的，x：表示：表示变元（客体变元），则变元（客体变元），则C(x)：表示：表示x总是要死的，总是要死的，则称则称C(x)为命题函数为命题函数第二章：谓词逻辑第二章：谓词逻辑 类似的，用类似的，用F(x)表示个体变元表示个体变元x具有性质具有性质F；用用G(x,y)表示个体变元表示个体变元x和和y具有关系具有关系G；，用，用P(x1,x2,xn)(n1)表示个体变元表示个体变元x1,x2,xn具有关系具有关系P。如果谓词后面有。如果谓词后面有n个个个个体变元，则称为体变元，则称为n元命题函数。例如元命题函数。例如F(x)、G(x，y)、P(x1,x2,xn)分别叫做一元命题分别叫做一元命题函数、二元命题函数、函数、二元命题函数、n元命题函数元命题函数(n1)。因为命题函数中包含个体变元，因此命题函因为命题函数中包含个体变元，因此命题函数没有确定的真值，它不是命题。只要用个数没有确定的真值，它不是命题。只要用个体常元取代所有的个体变元，就得到了命题。体常元取代所有的个体变元，就得到了命题。第二章：谓词逻辑第二章：谓词逻辑 例如，用例如，用H(x,y)：x+y0，显然此命题函数不是，显然此命题函数不是命题，因为它无法判断真假。令命题，因为它无法判断真假。令 a：5,b：7 用用a,b分别取代分别取代x,y，就得到，就得到H(a,b)，它表示，它表示5+(7)0，这是个假命题，它的真值为假。，这是个假命题，它的真值为假。其实，用个体常元取代命题函数的所有个体变元所得其实，用个体常元取代命题函数的所有个体变元所得到的表达式就是前面所说的谓词填式。因为它由个体到的表达式就是前面所说的谓词填式。因为它由个体常元取代命题函数中所有的个体变元而得到，所以也常元取代命题函数中所有的个体变元而得到，所以也把谓词填式叫做把谓词填式叫做0元命题函数。元命题函数。F(a)，G(b,c)，H(d,e,f)都是都是0元命题函数，它们都是命题。于是命元命题函数，它们都是命题。于是命题逻辑中的命题均可以表示为谓词逻辑中的题逻辑中的命题均可以表示为谓词逻辑中的0元命题元命题函数函数(谓词填式谓词填式)，命题成为命题函数的特例。，命题成为命题函数的特例。第二章：谓词逻辑第二章：谓词逻辑【定义定义】由一个谓词字母和一个非空的客体变由一个谓词字母和一个非空的客体变元组成的表达式，称为简单命题函数。元组成的表达式，称为简单命题函数。定义讨论定义讨论a.当简单命题变元只有一个客体变元时，称为一当简单命题变元只有一个客体变元时，称为一元简单命题函数元简单命题函数b.若用任何客体取代客体变元之后，则命题函数若用任何客体取代客体变元之后，则命题函数就变为命题就变为命题c.命题函数中的客体变元的取值范围称为个体域命题函数中的客体变元的取值范围称为个体域（论述域）（论述域）例如例如P(x)表示表示x是质数。这是一个命题函数，是质数。这是一个命题函数，真值取决于个体域。真值取决于个体域。第二章：谓词逻辑第二章：谓词逻辑【例例】将下列命题符号化，并讨论它们的真值。将下列命题符号化，并讨论它们的真值。2与与3都是偶数。都是偶数。如果如果5大于大于3，则，则2大于大于6。解：解：设设F(x)：x是偶数。是偶数。a：2，b：3 该命题符号化为：该命题符号化为：F(a)F(b)F(b)表示表示3是偶数，它是个假命题。所以是偶数，它是个假命题。所以F(a)F(b)为假。为假。设设G(x,y)：x大于大于y a：5，b：3，c：2，d：6 该命题符号化为：该命题符号化为：G(a,b)G(c,d)G(a,b)表示表示5大于大于3，它是真命题。，它是真命题。G(c,d)表示表示2大于大于6，这是个假命题。所以这是个假命题。所以G(a,b)G(c,d)为假。为假。第二章：谓词逻辑第二章：谓词逻辑2、量词、量词量词分两种。量词分两种。全称量词全称量词 日常生活和数学中常用的日常生活和数学中常用的“一切的一切的”，“所有的所有的”，“每每一个一个”，“任意的任意的”，“凡凡”，“都都”等词统称为全称量词，等词统称为全称量词，将它们符号化为将它们符号化为“”。并用。并用(x)，(y)等表示个体域里等表示个体域里的所有个体，而用的所有个体，而用(x)F(x)和和(y)G(y)等分别表示个体域等分别表示个体域中的所有个体都有性质中的所有个体都有性质F和都有性质和都有性质G。存在量词存在量词 “存在存在”，“有一个有一个”，“有些有些”，“至少有一个至少有一个”等词统等词统称为存在量词，将它们符号化为称为存在量词，将它们符号化为“”。并用。并用(x)，(y)等表示个体域里有些个体，而用等表示个体域里有些个体，而用(x)F(x)和和(y)G(y)等分别表示在个体域中存在个体具有性质等分别表示在个体域中存在个体具有性质F和存在和存在个体具有性质个体具有性质G。全称量词与存在量词统称为量词。全称量词与存在量词统称为量词。第二章：谓词逻辑第二章：谓词逻辑【例例】（1）存在人；（）存在人；（2）某些人很聪明；（）某些人很聪明；（3）有些实数）有些实数是有理数是有理数 将（将（1）（）（2）（）（3）写成命题。）写成命题。解：令解：令M(x)：x是人；是人；C(x)：x很聪明；很聪明；R1(x)：x是实数；是实数；R2(x)：x是有理数是有理数 则：则：(1)(x)M(x)；(2)(x)(M(x)C(x)；(3)(x)(R1(x)R2(x)在命题函数前加上量词在命题函数前加上量词(x)和和(x)分别叫做个体分别叫做个体变元变元x被全称量化和存在量化。一般地说，命题函数不是被全称量化和存在量化。一般地说，命题函数不是命题，如果对命题函数中所有命题变元进行全称量化或存命题，如果对命题函数中所有命题变元进行全称量化或存在量化，该函数就变成了命题。这一结论在上例中得到验在量化，该函数就变成了命题。这一结论在上例中得到验证。证。虽然对命题函数中所有命题变元进行量化后，该命题虽然对命题函数中所有命题变元进行量化后，该命题函数就变成了命题，但所得命题的真值与个体域的选定有函数就变成了命题，但所得命题的真值与个体域的选定有关。请看下列例题：关。请看下列例题：第二章：谓词逻辑第二章：谓词逻辑【例】对下列命题符号化，并在对下列命题符号化，并在，三个个体域中考察命题三个个体域中考察命题的真值。的真值。命题：命题：所有数小于所有数小于5；至少有一个数小于至少有一个数小于5。个体域：个体域：-1，0，1，2，4 3，-2，7，8 15，20，24 解：设解：设L(x)：x小于小于5。“所有数小于所有数小于5。”符号化为：符号化为：(x)L(x)在个体域在个体域，中，它们的真值分别为：真，假，假。中，它们的真值分别为：真，假，假。“至少有一个数小于至少有一个数小于5。”符号化为：符号化为：(x)L(x)在个体域在个体域，中，它们的真值分别为：真，真，假。中，它们的真值分别为：真，真，假。命题函数中的个体变元被量化以后变成命题，其真值又与个体域命题函数中的个体变元被量化以后变成命题，其真值又与个体域的选定有关，这对命题函数的研究带来了一定的困难，为了统一，的选定有关，这对命题函数的研究带来了一定的困难，为了统一，我们今后使用全总个体域。而将其它个体域用一个谓词来我们今后使用全总个体域。而将其它个体域用一个谓词来第二章：谓词逻辑第二章：谓词逻辑 表示，叫做特性谓词。特性谓词加入的方法为：表示，叫做特性谓词。特性谓词加入的方法为：对全称量词，特性谓词作为条件命题的前件加入。对全称量词，特性谓词作为条件命题的前件加入。对存在量词，特性谓词作为合取项加入。对存在量词，特性谓词作为合取项加入。【例例】对下列命题在对下列命题在，两个个体域中符号化。两个个体域中符号化。命题：命题：所有老虎是要吃人。所有老虎是要吃人。存在一个老虎要吃人。存在一个老虎要吃人。个体域：个体域：所有老虎组成的集合。所有老虎组成的集合。全总个体域。全总个体域。解：设解：设A(x)：x是要吃人的。个体域为所有老虎的集合。是要吃人的。个体域为所有老虎的集合。符号化为符号化为(x)A(x)符号化为符号化为(x)A(x)个体域为全总个体域。设特性谓词个体域为全总个体域。设特性谓词T(x)：x是老虎。是老虎。符号化为符号化为(x)(T(x)A(x)符号化为符号化为(x)(T(x)A(x)第二章：谓词逻辑第二章：谓词逻辑2.3谓词公式与翻译谓词公式与翻译1、谓词公式、谓词公式 我们把命题、命题变元、谓词填式和命题函数叫做我们把命题、命题变元、谓词填式和命题函数叫做谓词演算的原子谓词公式。谓词演算的原子谓词公式。【定义定义】按下列规则构成的表达式称为谓词演算的合按下列规则构成的表达式称为谓词演算的合式公式，简称谓词公式。式公式，简称谓词公式。谓词演算的原子公式是合式公式。谓词演算的原子公式是合式公式。若若A是合式公式，则是合式公式，则A是合式公式。是合式公式。若若A和和B是合式公式，则是合式公式，则(AB)，(AB)，(AB)和和(A B)是合式公式。是合式公式。如果如果A是合式公式，是合式公式，x是是A中出现的任意个体变中出现的任意个体变元，则元，则(x)A，(x)A是合式公式。是合式公式。第二章：谓词逻辑第二章：谓词逻辑 只有有限次地应用只有有限次地应用、所得的所得的公式是合式公式。公式是合式公式。谓词公式也有以下约定：谓词公式也有以下约定：最外层的括号可以省略。最外层的括号可以省略。如果按如果按、在运算中在运算中的优先级别，省略括号后不改变原来的运的优先级别，省略括号后不改变原来的运算次序，可以省略括号，但量词后面括号算次序，可以省略括号，但量词后面括号不能省略。不能省略。第二章：谓词逻辑第二章：谓词逻辑下面举例说明如何用谓词公式表达自然语言中的命题。下面举例说明如何用谓词公式表达自然语言中的命题。【例例】并非每个实数都是有理数。并非每个实数都是有理数。解：设解：设R(x)：x是实数是实数 Q(x)：x是有理数是有理数 该命题符号化为：该命题符号化为：(x)(R(x)Q(x)【例例】没有不犯错误的人。没有不犯错误的人。解：设解：设M(x)：x是人是人 F(x)：x犯错误犯错误 此命题可以理解为：存在一些人不犯错误，这句话是不对此命题可以理解为：存在一些人不犯错误，这句话是不对的。此时，符号化为：的。此时，符号化为：(x)(M(x)F(x)也可以理解为：任何人都是要犯错误的。此时，符号化为：也可以理解为：任何人都是要犯错误的。此时，符号化为：(x)(M(x)F(x)第二章：谓词逻辑第二章：谓词逻辑【例例】并不是所有的兔子都比所有的乌龟跑得快。并不是所有的兔子都比所有的乌龟跑得快。解：设解：设F(x)：x是兔子。是兔子。G(x)：x是乌龟。是乌龟。H(x,y)：x比比y跑得快。跑得快。该命题符号化为：该命题符号化为：(x)(y)(F(x)G(y)H(x,y)【例例】将苏格拉底论证符号化将苏格拉底论证符号化“所有的人都是要死的。因为苏格拉底是人，所有的人都是要死的。因为苏格拉底是人，所以苏格拉底是要死的。所以苏格拉底是要死的。”解：设解：设M(x)：x是人是人 D(x)：x是要死的是要死的 M(s)：苏格拉底苏格拉底是人是人 D(s)：苏格拉底是要死的苏格拉底是要死的该命题的符号化为：该命题的符号化为：(x)(M(x)D(x)，M(s)D(s).2、由于对个体描述性质的刻画深度不同，可翻译成不、由于对个体描述性质的刻画深度不同，可翻译成不 同形式的谓词公式（如同形式的谓词公式（如P61，例，例4）第二章：谓词逻辑第二章：谓词逻辑2.4变元的约束变元的约束1、自由变元与约束变元、自由变元与约束变元【定义定义】如果如果A是谓词公式是谓词公式B的一部分且是谓词公式，的一部分且是谓词公式，则称则称A是是B的子公式。的子公式。【定义定义】紧接量词以后的最小子公式叫做该量词的辖紧接量词以后的最小子公式叫做该量词的辖域或作用域。域或作用域。【定义定义】量词量词(x)和和(x)中的中的x叫做该量词的指导叫做该量词的指导变元或作用变元。变元或作用变元。【定义定义】量词量词(x)和和(x)的辖域内的辖域内x的一切出现叫的一切出现叫约束出现，约束出现，x叫做约束变元；约束变元以外的其它变叫做约束变元；约束变元以外的其它变元的出现叫自由出现，自由出现的变元叫自由变元。元的出现叫自由出现，自由出现的变元叫自由变元。第二章：谓词逻辑第二章：谓词逻辑【例例】说明下列各式量词的辖域，找出约束变元和自由变元。说明下列各式量词的辖域，找出约束变元和自由变元。(x)P(x)Q(y)(x)(P(x)(y)Q(x,y)(x)P(x)(y)Q(x,y)(x)(y)(P(x,y)Q(y,z)(x)R(x,y)(x)P(x)R(x,y)解：解：(x)的辖域为的辖域为P(x)，x是约束变元，是约束变元，y是自由变元。是自由变元。(x)的辖域为的辖域为P(x)(y)Q(x,y)，(y)的辖域为的辖域为Q(x,y)，x和和y都是约束变元，无自由变元。都是约束变元，无自由变元。(x)的辖域为的辖域为P(x)，(y)的辖域为的辖域为Q(x,y)，P(x)中的中的x和和Q(x,y)中的中的y是约束变元，是约束变元，Q(x,y)中的中的x是自由变元。是自由变元。(x)的辖域为的辖域为(y)(P(x,y)Q(y,z)，(y)的辖域为的辖域为P(x,y)Q(y,z)，(x)的辖域为的辖域为R(x,y)，x是约束变元，是约束变元，z是自是自由变元，由变元，(P(x,y)Q(y,z)中的中的y是约束变元，是约束变元，R(x,y)中的中的y是自是自由变元。由变元。第二章：谓词逻辑第二章：谓词逻辑 (x)的辖域为的辖域为P(x)，y是自由变元，是自由变元，P(x)中中x是约束变元，是约束变元，R(x,y)中中x是自由变元。是自由变元。2、约束变元的改名规则、约束变元的改名规则 由上例可以看出，在一个公式中，同一个变元既可以是由上例可以看出，在一个公式中，同一个变元既可以是约束的，又可以是自由的，容易混淆。因为约束的，又可以是自由的，容易混淆。因为(x)P(x)与与(y)P(y)，(x)P(x)与与(y)P(y)都具有相同意都具有相同意义，所以约束变元与表示该变元的符号无关。根据这个义，所以约束变元与表示该变元的符号无关。根据这个特点，可以对约束变元换名。为了使换名后的公式中出特点，可以对约束变元换名。为了使换名后的公式中出现的变元要么是约束的，要么是自由的，我们提出如下现的变元要么是约束的，要么是自由的，我们提出如下的换名规则：的换名规则：对约束变元可以换名，其更改变元名称的范围是量对约束变元可以换名，其更改变元名称的范围是量词的指导变元，以及该量词辖域中的所有该变元，公式词的指导变元，以及该量词辖域中的所有该变元，公式的其余部分不变。的其余部分不变。换名时一定要更改成辖域中没有出现的变元名，最好换名时一定要更改成辖域中没有出现的变元名，最好是公式中没有的变量名。是公式中没有的变量名。第二章：谓词逻辑第二章：谓词逻辑【例例】对对(x)(y)(P(x,y)Q(y,z)(x)R(x,y)中的约束中的约束变元变元y换名。换名。解：用解：用u置换约束变元置换约束变元y。换名后为：。换名后为：(x)(u)(P(x,u)Q(u,z)(x)R(x,y)不能换成：不能换成：(x)(u)(P(x,u)Q(y,z)(x)R(x,y)也不能换成：也不能换成：(x)(z)(P(x,z)Q(z,z)(x)R(x,y)3、自由变元的代入规则、自由变元的代入规则 对公式中的自由变元也可以进行更改，用来解决公式中约束对公式中的自由变元也可以进行更改，用来解决公式中约束变元与自由变元的同名问题。这种更改叫做代入，代入规则变元与自由变元的同名问题。这种更改叫做代入，代入规则是：是：对于谓词公式中的自由变元可以代入，代入时需对公式中对于谓词公式中的自由变元可以代入，代入时需对公式中该变元自由出现的每处进行。该变元自由出现的每处进行。代入的变元与原公式中其他变元的名称不能相同。代入的变元与原公式中其他变元的名称不能相同。第二章：谓词逻辑第二章：谓词逻辑【例例】对对(x)(P(y)R(x,y)(y)Q(y)中的自由变元中的自由变元y进进行代入。行代入。解：用解：用z代换代换y，代入后为：，代入后为：(x)(P(z)R(x,z)(y)Q(y)不能换成：不能换成：(x)(P(x)R(x,x)(y)Q(y)或或 (x)(P(z)R(x,y)(y)Q(y)4、区别是命题还是命题函数的方法、区别是命题还是命题函数的方法a)若在谓词公式中出现自由变元，则该公式为命题函数若在谓词公式中出现自由变元，则该公式为命题函数b)若在谓词公式中的变元均为约束出现，在该公式为命题若在谓词公式中的变元均为约束出现，在该公式为命题【例例】(x)R(x,y,z)是二元谓词函数是二元谓词函数 (y)(x)R(x,y,z)是一元谓词函数是一元谓词函数 而谓词公式中如果没有自由变元出现，则该公式是一个命题而谓词公式中如果没有自由变元出现，则该公式是一个命题第二章：谓词逻辑第二章：谓词逻辑注：注：对于同一个体域，用不同的量词时，特对于同一个体域，用不同的量词时，特性谓词加入的方法不一样。性谓词加入的方法不一样。对于全称量词，特征谓词通常以前件的形式加入对于全称量词，特征谓词通常以前件的形式加入对于存在量词，特征谓词通常以与的形式加入对于存在量词，特征谓词通常以与的形式加入 当论域中的元素为有限时客体变元中的所有可当论域中的元素为有限时客体变元中的所有可能的取代是可以枚举的能的取代是可以枚举的对于全称量词，同常用对于全称量词，同常用“与与”联接词联接词对于存在量词，通常用对于存在量词，通常用“或或”联接词联接词 量词对变元的约束，往往与量词的次序有关量词对变元的约束，往往与量词的次序有关【例例】(y)(x)(x y-2)表示任何表示任何y均有均有x，使得，使得x y-2第二章：谓词逻辑第二章：谓词逻辑2.5谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式【定义定义2.5.1】设设A是谓词公式，个体域为是谓词公式，个体域为E，如果对如果对A的任何赋值，的任何赋值，A都为真，则称都为真，则称A是有效的或永真的。是有效的或永真的。【定义定义2.5.2】设设A是谓词公式，个体域为是谓词公式，个体域为E，如果对如果对A的任何赋值，的任何赋值，A都为假，则称都为假，则称A是不可满足的或永假的。是不可满足的或永假的。【定义定义2.5.3】设设A是谓词公式，如果个体域中至少有一组赋值使是谓词公式，如果个体域中至少有一组赋值使A为真，则称为真，则称A是可满足的。是可满足的。根据定义根据定义2.5.1和定义和定义2.5.3，如果一个谓词公式是有效的，它，如果一个谓词公式是有效的，它一定是可满足的。一定是可满足的。【定义定义2.5.4】设设A、B是任意两个谓词公式，且有共同的个体域是任意两个谓词公式，且有共同的个体域E，对，对A、B的任何赋值，若其真值相同，则称的任何赋值，若其真值相同，则称A与与B是在是在E上是等上是等价的，记作价的，记作AB；若；若AB是有效的，则称是有效的，则称A蕴含蕴含B，记作，记作AB。设设A、B是任意两个谓词公式。当是任意两个谓词公式。当AB时，由定义时，由定义2.5.1和定义和定义2.5.4知知A B是永真式。反之，当是永真式。反之，当A B是永真式时，是永真式时，AB。所以，。所以，也可以用也可以用A B是永真式描述是永真式描述AB。第二章：谓词逻辑第二章：谓词逻辑1、命题逻辑中的等价式的推广、命题逻辑中的等价式的推广 命题演算中的所有等价式都是谓词演算中的命题演算中的所有等价式都是谓词演算中的等价式。等价式。从谓词公式的定义可以看出，命题演算的合式公从谓词公式的定义可以看出，命题演算的合式公式都是谓词演算的合式公式。再根据定义式都是谓词演算的合式公式。再根据定义2.5.4，命题演算中的所有等价式都是谓词演算中的等价式。命题演算中的所有等价式都是谓词演算中的等价式。命题逻辑中的等价式的推广命题逻辑中的等价式的推广 在命题逻辑中，重言式的同一分量出现的每一处在命题逻辑中，重言式的同一分量出现的每一处都用同一合式公式置换，其结果仍是重言式。在谓都用同一合式公式置换，其结果仍是重言式。在谓词逻辑中可以推广为：在永真的谓词公式中，命题词逻辑中可以推广为：在永真的谓词公式中，命题变元出现的每一处都用同一谓词公式置换，其结果变元出现的每一处都用同一谓词公式置换，其结果仍是永真式。例如：仍是永真式。例如：第二章：谓词逻辑第二章：谓词逻辑 因为因为(pq)pq，故，故(pq)(pq)为永真式，为永真式，用用(x)P(x)代替代替p，(y)R(y)代替代替q，得到永真式：，得到永真式：(x)P(x)(y)R(y)(x)P(x)(y)R(y)所以所以(x)P(x)(y)R(y)(x)P(x)(y)R(y)2、消去量词等价式、消去量词等价式 设个体域为有限集设个体域为有限集 a1，a2，an，A(x)是含自由变元是含自由变元x的的任意谓词公式，有下列等价式成立：任意谓词公式，有下列等价式成立：(x)A(x)A(a1)A(a2)A(an)(x)A(x)A(a1)A(a2)A(an)3量词否定等价式量词否定等价式 设设A(x)是含自由变元是含自由变元x的任意谓词公式。则的任意谓词公式。则 (x)A(x)(x)A(x)(x)A(x)(x)A(x)约定，量词之前的否定联结词，不是否定该量词，而是否定约定，量词之前的否定联结词，不是否定该量词，而是否定该量词及其辖域。该量词及其辖域。第二章：谓词逻辑第二章：谓词逻辑这两个等价式可在有限个体域上证明，设个体域为这两个等价式可在有限个体域上证明，设个体域为 a1，a2，an (x)A(x)(A(a1)A(a2)A(an)A(a1)A(a2)A(an)(x)A(x)(x)A(x)(A(a1)A(a2)A(an)A(a1)A(a2)A(an)(x)A(x)当个体域为无限集时，等价式也是成立的。但因为情况复当个体域为无限集时，等价式也是成立的。但因为情况复杂，仅作以下说明：对等价式杂，仅作以下说明：对等价式(x)A(x)(x)A(x)，(x)A(x)表示：并不是所有的表示：并不是所有的x都有性质都有性质A。(x)A(x)表示：存在表示：存在x没有性质没有性质A。显然。显然“并不是所有的并不是所有的x都有性质都有性质A”和和“存在存在x没有性质没有性质A”是相同的，所以是相同的，所以(x)A(x)(x)A(x)。对等价式。对等价式(x)A(x)(x)A(x)来说，来说，“不存在某个不存在某个x有性质有性质A”和和“所有的所有的x都没有性质都没有性质A”是相同的。是相同的。第二章：谓词逻辑第二章：谓词逻辑4、量词作用域的扩展与收缩等价式、量词作用域的扩展与收缩等价式 设设A(x)是含自由变元是含自由变元x的任意谓词公式。的任意谓词公式。B是不含变元是不含变元x的谓的谓词公式，则词公式，则 (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 利用上述四式可以得到以下四式：利用上述四式可以得到以下四式：(x)(A(x)B)(x)A(x)B (x)(A(x)B)(x)A(x)B (x)(BA(x)B(x)A(x)(x)(BA(x)B(x)A(x)【例例】证明证明(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第二章：谓词逻辑第二章：谓词逻辑5、量词分配等价式、量词分配等价式 设设A(x)和和B(x)是含自由变元是含自由变元x的任意谓词公式，则的任意谓词公式，则 (x)(A(x)B(x)(x)A(x)(x)B(x)(x)(A(x)B(x)(x)A(x)(x)B(x)前者可以理解为：前者可以理解为：“所有的所有的x有性质有性质A和性质和性质B”和和“所有的所有的x有有性质性质A且所有的且所有的x有性质有性质B”是等同的。后者可以利用前者来证明。是等同的。后者可以利用前者来证明。【例例】证明证明(x)(A(x)B(x)(x)A(x)(x)B(x)解：解：因为因为(x)(A(x)B(x)(x)A(x)(x)B(x)而而 (x)(A(x)B(x)(x)(A(x)B(x)(x)(A(x)B(x)(x)A(x)(x)B(x)(x)A(x)(x)B(x)(x)A(x)(x)B(x)所以所以 (x)(A(x)B(x)(x)A(x)(x)B(x)于是于是 (x)(A(x)B(x)(x)A(x)(x)B(x)第二章：谓词逻辑第二章：谓词逻辑6、量词与联结词的蕴含式、量词与联结词的蕴含式 设设A(x)和和B(x)是含自由变元是含自由变元x的任意谓词公式。的任意谓词公式。(x)A(x)(x)B(x)(x)(A(x)B(x)(x)(A(x)B(x)(x)A(x)(x)B(x)(x)(A(x)B(x)(x)A(x)(x)B(x)(x)(A(x)B(x)(x)A(x)(x)B(x)对第一式作如下说明：令对第一式作如下说明：令A(x)表示表示x有一支钢笔，有一支钢笔，B(x)表示表示x有一支铅笔，个体域是有一支铅笔，个体域是2000级计算机级计算机1班全体同学。全班每个同学都有一支钢笔或每个同班全体同学。全班每个同学都有一支钢笔或每个同学都有一支铅笔，当然可以推出全班每个同学有一学都有一支铅笔，当然可以推出全班每个同学有一支钢笔或有一支铅笔。但反过来是不对的。支钢笔或有一支铅笔。但反过来是不对的。第二式可用第一式推出。第二式可用第一式推出。第二章：谓词逻辑第二章：谓词逻辑【例例】证明证明(x)(A(x)B(x)(x)A(x)(x)B(x)解：解：由第一式可得：由第一式可得：(x)A(x)(x)B(x)(x)(A(x)B(x)而而 (x)A(x)(x)B(x)(x)A(x)(x)B(x)(x)A(x)(x)B(x)(x)(A(x)B(x)(x)(A(x)B(x)(x)(A(x)B(x)故有故有 (x)A(x)(x)B(x)(x)(A(x)B(x)由双条件否定等价式有由双条件否定等价式有 (x)(A(x)B(x)(x)A(x)(x)B(x)第三、四式可以类似推出。第三、四式可以类似推出。第二章：谓词逻辑第二章：谓词逻辑7、多个量词的使用、多个量词的使用 约定：约定：(x)(y)A(x,y)表示表示(x)(y)A(x,y)一般地说，多个量词相连时，同名量词是无序的，即改一般地说，多个量词相连时，同名量词是无序的，即改变它们的次序，命题真值不变。异名量词是有序的，即改变变它们的次序，命题真值不变。异名量词是有序的，即改变它们的次序，命题真值发生变化。对后者作如下的说明：它们的次序，命题真值发生变化。对后者作如下的说明：令令A(x,y)表示表示x+y=10，个体域为整数集合，个体域为整数集合I。(x)(y)A(x,y)表示对任一整数表示对任一整数x，存在整数，存在整数y，使，使x+y=10。这是一个真命题。这是一个真命题。(y)(x)A(x,y)表示存在整数表示存在整数y，对任一整数，对任一整数x，有，有x+y=10。这是一个假命题。这是一个假命题。第二章：谓词逻辑第二章：谓词逻辑 因为同名量词是无序的，所以有：因为同名量词是无序的，所以有：(x)(y)A(x,y)(y)(x)A(x,y)(x)(y)A(x,y)(y)(x)A(x,y)异名量词有下列的蕴含关系：异名量词有下列的蕴含关系：(y)(x)A(x,y)(x)(y)A(x,y)(x)(y)A(x,y)(y)(x)A(x,y)具有两个量词的谓词公式还有下列的蕴含式：具有两个量词的谓词公式还有下列的蕴含式：(x)(y)A(x,y)(y)(x)A(x,y)(y)(x)A(x,y)(x)(y)A(x,y)(x)(y)A(x,y)(y)(x)A(x,y)(y)(x)A(x,y)(x)(y)A(x,y)第二章：谓词逻辑第二章：谓词逻辑2.6前束范式前束范式【定义定义】一个公式，如果量词均在全式的开头，它们的作用域一个公式，如果量词均在全式的开头，它们的作用域延伸到整个公式的末尾，则称为前束范式。延伸到整个公式的末尾，则称为前束范式。根据这个定义前束范式可表示成如下形式：根据这个定义前束范式可表示成如下形式：(v1)(v2)(vn)A 其中：其中：是是 或或 vi是个体变元，是个体变元，i=1,n A是不含量词的谓词公式是不含量词的谓词公式【例例】(x)(y)(F(x)G(y)L(x,y)(y)(x)(z)(H(x,y)F(x)L(x,z)都是前束范式。而都是前束范式。而 (x)F(x)(y)(G(y)L(x,y)(y)(x)(H(x,y)F(x)(z)L(x,z)都不是前束范式。都不是前束范式。第二章：谓词逻辑第二章：