特性谓词

第二章谓词逻辑第二讲1.谓词及其表示定义1可以独立存在的人、物、事称为个体或客体。定义2在谓词逻辑中，刻划个体性质和关系的谓语称为谓词。回顾2.常元与变元在谓词逻辑中，表示特定个体的词称为个体常元。在谓词逻辑中，用来表示未知或泛指的个体的词称为个体变元。其标识符常用小写字母x，y，z．．．表示。3.命题函数定义3由一个谓词和一些个体变元组成的表达式称为原子命题函数。用逻辑联结词把一个或多个原子命题函数连接而成的表达式称为复合命题函数。4.个体域定义4个体变元的论述范围称为个体域（或论域）。各种个体域综合在一起作为论述范围称为全总个体域。5.量化a.全称量词∀xA(x)表示“所有的”、“任意的”、“每一个”等b.存在量词∃xA(x)表示“存在着”、“有的”、“至少有一个”、“有一些”等【说明】∀xP(x)和∃xP(x)与P(x)有着本质的区别。P(x)是不能确定真值的命题函数，其中的x是个体变元；而∀xP(x)和∃xP(x)都是可以确定真值的命题，其中的x再不起变元的作用，已经受到量词∀x、∃x的限制。个体变元受到量词限制的过程称之为量化。在存在量化中，特性谓词常作为合取项。6.特性谓词定义5在全总个体域中,表示具体个体域的谓词称为特性谓词。在全称量化中，特性谓词常作为条件命题的前件。7.量化与代换实例当个体域为有限集{a1,a2,a3,…an}时，由量词的定义可以知道，对于任意谓词都有：这就是量词的消去规则，它可以将带量词的谓词公式转化成谓词公式的代换实例。)()()()(21naPaPaPxxP)()()()(21naPaPaPxxP定义2-7原子谓词公式定义如下：(1)一个命题是原子谓词公式。(2)一个命题变元是原子谓词公式。(3)由n个个体变元及n元谓词所组成的命题函数也是一个原子谓词公式。原子谓词公式简称为原子公式。nxxxx,...,,321定义2-8谓词公式定义如下：(1)一个原子公式是一个谓词公式。(2)若A是谓词公式，则┐A也是谓词公式。(3)若A、B是谓词公式，则(A∧B)、(A∨B)、(A→B)、(A↔B)也是谓词公式。(4)若A是谓词公式，x是A中的个体变元，则∀xA(x)、∃xA(x)也是谓词公式。只有有限次地运用规则(1)、(2)、(3)、(4)所得到的符号串才是谓词公式。注意:谓词公式中的某些圆括号也可以省略,其规定与命题公式相同，但量词后的圆括号不能省略，因为它关系到量词的作用范围。2．3．2谓词公式的翻译与命题公式的翻译类似，谓词公式的翻译同样有两个方面，一是将自然语言描述的命题符号化，也称形式化；二是将形式化的谓词公式翻译成自然语言描述的命题。在公式翻译过程中，除注意联结词的选择外，还必须注意量词的选择。一、将自然语言描述的谓词公式形式化例2-4每个人都会犯错误解：该命题可以说成“对于所有的x，如果x是人，则x会犯错误”。设H(x)：x是人。M(x)：x会犯错误。则命题可表示为：))()((xMxHx例2-5并非所有实数都是有理数解：该命题可以说成“所有实数都是有理数是不对的”。设R(x)：x是实数。Q(x)：x是有理数。则命题可表示为：例2-6尽管有的人聪明，但不是所有的人都聪明解：该命题是由两个并列的句子组成，即由两个合取项组成。第一个合取项为“存在聪明的人”，第二个合取项是“不是所有的人都是聪明人”。设H(x)：x是人。C(x)：x聪明。则命题可表示为：))()((xQxRx))()(())()((xCxHxxCxHx例2-7李涛无书不读。解：该命题即是说“李涛所有的书都读”。设P(x)：x是书。Q(y,x)：y读x。a:李涛。则命题可表示为：例2-8有人无书不读。解：该命题可解释为存在这样的人，这种人所有书都读。H(y)：y是人。P(x)：x是书。Q(y,x)：y读x。则命题可表示为：)),()((xaQxPx))),()(()((xyQxPxyHy例2-9设个体域为全总个体域，令C(x):x是火车；G(y):y是汽车；Q(x,y):x比y跑得快;S(x,y):x和y相同。符号化下列命题：(1)有的火车比所有的汽车跑得快。(2)并不是所有的火车比汽车跑得快。(3)不存在两辆完全相同的汽车。))),()(()((yxQyGyxCx)),()()((yxSyGxGyx))),()(()((yxQyGyxCx符号化谓词公式的步骤：（1）分解原子谓词，包括谓词、个体和量词。（2）选择正确的量词。（3）选择正确的联接词。)),()()((yxQyGxCyx•例：在谓词逻辑中将下列命题符号化.（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)))摔倒。今天有雨雪，有些人会所有的乌龟跑得快。并不是所有的兔子都比不是一切人都一样高。会叫的狗未必会咬人。将下列命题符号化：例)4()3()2()1(咬人。：会叫。：是狗。设：会叫的狗未必会咬人。xxCxxBxxD)()(:)()1())()()((xCxBxDx则不是一切人都一样高。)2(一样高。和：是人。设：yxyxBxxH),(:)()),()()((yxAyHxHyx则)),()()((yxAyHxHyx或者所有的乌龟跑得快。并不是所有的兔子都比)3(跑得快。比：是乌龟。：是兔子。设：yxyxAxxDxxR),()(:)()),()()((yxAyDxRyx则摔倒。今天有雨雪，有些人会)4(会摔倒。是人。：：今天有雪。今天有雨。设：xxDxxHSR:)()(:))()((xDxHxSR则练习在谓词逻辑中将下列命题符号化。（1）不存在最大的数。（2）计算机系的学生都要学离散数学。解取个体域为全总个体域。（1）令F（x）：x是数，L（x，y）：x大于y；则命题（1）符号化为﹁x（F（x）∧y（F（y）→L（x，y）））（2）令C（x）：x是计算机系的学生，G（x）：x要学离散数学;则命题（2）可符号化为：x（C（x）→G（x））(1)不存在大于所有数的数二、将形式化谓词公式翻译成自然语言描述的命题将形式化谓词公式翻译成自然语言描述的命题比较复杂，除要注意联结词的选择外，还要注意量词的选择。例2-10令P(x)表示x是素数；E(x)表示x是偶数；O(x)表示x是奇数；D(x,y)表示x整除y。（1）解：若x为任意偶数，能被x整除的每一个数y必定是偶数。（能被任意偶数整除的每个数都是偶数）（2）解：对于任一个素数x，必定存在一些偶数y能被x整除。（3）解：如果x是任意奇数，则x无法整除所有的素数。)))(),(()((yEyxDyxEx))),()(()((yxDyEyxPx))),()(()((yxDyPyxOx把形式化的谓词公式翻译成自然语言描述的命题时，特别要注意语言的表达。如果语言描述得好，读起来语句显得通顺，容易理解。如果表达得不好，读起来晦涩难懂。练习1:将下列命题符号化：[1]每一个有理数都是实数[2]某些实数是有理数[3]不是每一个实数都是有理数[4]存在偶素数[5]有些液体能溶解任何金属[6]任何金属均可溶解于某种液体中2．3变元的约束一个谓词公式中的所有个体变元被量化以后便成为命题。分析一个谓词公式，看它是否成为命题，必须看它被量化的情况。2．3．1定义定义2-9在谓词公式中，被量化的个体变元称为约束变元。定义2-10在谓词公式中，量词的作用范围称为辖域。在量词辖域中，约束变元的一切出现称为约束出现。定义2-11在谓词公式中，未被约束的变元称为自由变元。自由变元的一切出现称为自由出现。在谓词公式中存在自由变元有两种情况：（1）该变元在量词的辖域中，但与量词的指导变元不同名。（2）该变元与量词指导变元同名，但不在量词的辖域中。例2-11指出下列各式中量词的辖域、约束变元和自由变元。（1）（2）（3）))()((xQxPx)),()((yxyQxPx)),()),(),(((yxxPzyQyxPyx解：（1）全称量词的辖域是，个体变元x为约束变元，x在辖域中的所有出现为约束出现。（2）全称量词的辖域是，个体变元x是约束变元，x在辖域中的所有出现为约束出现（包括出现在的命题公式中的x）。存在量词的辖域是,y为约束变元。x))()((xQxPx)),()((yxyQxP),(yxyQy),(yxQ))()((xQxPx)),()((yxyQxPx（3）存在量词的辖域是，其中的个体变元x受到存在量词的约束，个体变元y受到全称量词的约束，个体变元z未受约束，是自由变元；命题公式中的x除受存在量词的约束外，又受全称量词的约束，以最内层的全称量词的约束为准，其中的y未受约束，是自由变元。x)),()),(),(((yxxPzyQyxPy)),(),((zyQyxPyxy),(yxxPxxx)),()),(),(((yxxPzyQyxPyx【说明】（1）如果一个个体变元受到多重约束，则最内层辖域的约束变元以最后一次约束为准。（2）如果一个谓词公式中没有自由变元，则该公式为命题。（3）若至少有一个个体变元未被约束，则该谓词公式为命题函数。2．3．2约束变元的换名在谓词公式中，一个个体变元可能处在不同量词辖域内，或者一个个体变元受到多重约束。例如在公式的前件中，y分别受到∀y与∃y的两重约束，x、z为自由变元；在公式的后件中x、y均为自由变元。由于同一个体变元在同一命题公式中受到不同量词的约束，容易引起混乱。我们知道，一个公式中的个体变元与所使用的个体变元的符号无关。例如∀xP(x)与∀yP(y)的含义相同，都表示论域中个体具有P属性。即谓词公式中个体的名称用任何字母表示都一样，因此，我们可以更改公式中约束变元的名称符号，这个过程称为约束变元的换名。)),(),(()),,()((yxRyxSzyxyQyPy约束变元的换名规则：①只能对量词指导变元所指示的变元换名。②若某一量词指导变元一旦被换名，则辖域中该变元都应换成相同名称。即换名一致性。③换名时一定要换成公式中未出现的名称。例2-12对下列谓词公式的约束变元进行换名（1）（2）（3）（4）·解（1）：公式中的变元x分别受到量词约束，z为自由变元。可将受全称量词约束的变元x换名为y，得题公式：),()(zxxQxxP))()((xxQxPx)),(),(()),,()((yxRyxSzyxyQyPy)),(),(()),()((yxRyxSyxyxQxPxxx和),()(zyyQxxP•解:公式中全称量词的辖域为(P(x)→∃xQ(x))，辖域中的x受到全称量词的约束，又受到存在量词的约束。可将受存在量词约束的变元换名为y，得公式：•解：公式前件的变元y受到两重约束，P(y)受到全称量的约束，Q(x,y,z)中的y受到存在量词的约束，后件的变x,y都是自由变元。可将受全称量词约束的变元y换为u，受存在量词约束的变元y换为v。得公式：))()((yyQxPx)),(),(()),,()((yxRyxSzvxvQuPu))()(()2(xxQxPx)),(),(()),,()(()3(yxRyxSzyxyQyPy解：全称量词的辖域中的个体变元为x，不变。存在量词辖域中的个体变元x换为v，全称量词辖域中的个体变元y换为m，得谓词公式：)),(),(()),()((mvRmvSmvyxQxPx)),(),(()),()(()4(yxRyxSyxyxQxPx2．3．3自由变元的代入由于谓词公式中的同一个个体变元可以是约束变元，也可以是自由变元，容易引起概念上的混