离散数学讲义第三章谓词逻辑.ppt

《离散数学讲义第三章谓词逻辑.ppt》由会员分享，可在线阅读，更多相关《离散数学讲义第三章谓词逻辑.ppt（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第三章第三章 谓词逻辑谓词逻辑 在命题逻辑中，命题被当作一个基本的在命题逻辑中，命题被当作一个基本的，不可分割的，不可分割的单位，只研究由原子命题和联结词所组成的复合命题；因单位，只研究由原子命题和联结词所组成的复合命题；因而无法研究命题的内部结构及命题之间内在的联系。本章而无法研究命题的内部结构及命题之间内在的联系。本章介绍的谓词逻辑，对原子命题的成份、结构和原子命题间介绍的谓词逻辑，对原子命题的成份、结构和原子命题间的共同特性等作了进一步分析。引入了个体词、谓词、量的共同特性等作了进一步分析。引入了个体词、谓词、量词、谓词公式等概念，在此基础上研究谓词公式间的等值词、谓词公式等概念，在此

2、基础上研究谓词公式间的等值关系和蕴含关系，并且对命题逻辑中的推理规则进行扩充关系和蕴含关系，并且对命题逻辑中的推理规则进行扩充和进行谓词演绎。和进行谓词演绎。主要内容如下：主要内容如下：3.1、3.2 谓词的概念与表示谓词的概念与表示;命题函数和量词命题函数和量词 3.3 3.5 谓词演算的合适公式谓词演算的合适公式;变元的约束变元的约束;谓词公式的解释谓词公式的解释 3.6 谓词演算的永真式谓词演算的永真式 3.7 谓词演算的推理理论谓词演算的推理理论23.13.1、3.2 3.2 谓词、命题函数和量词谓词、命题函数和量词 例例 判断下述论断的正确性判断下述论断的正确性 “苏格拉底三段论苏格

3、拉底三段论”：凡人都是要死的，凡人都是要死的，苏格拉底是人，苏格拉底是人，所以苏格拉底是要死的。所以苏格拉底是要死的。类似的例子类似的例子 还有许多。还有许多。例如：例如：所有的人都要呼吸所有的人都要呼吸,所有的正整数都大于所有的正整数都大于0,李莉是人李莉是人 ,3是正整数是正整数,所以李莉要呼吸。所以李莉要呼吸。所以所以3大于大于0。3一、谓词一、谓词 在谓词演算中，可将原子命题分解为谓词与个在谓词演算中，可将原子命题分解为谓词与个体词两部分。体词两部分。定义定义 个体个体是指可以独立存在的客体。是指可以独立存在的客体。注注个体可以是抽象的，也可是具体的。个体通常个体可以是抽象的，也可是具

4、体的。个体通常在一个命题里表示思维对象。在一个命题里表示思维对象。定义定义 用来刻划个体的性质或个体之间关系的用来刻划个体的性质或个体之间关系的词称为词称为谓词谓词，刻划一个个体性质的词称为，刻划一个个体性质的词称为一元谓词一元谓词；刻划刻划n个个体之间关系的词称为个个体之间关系的词称为n元谓词元谓词。例例1 （1）李明是学生；）李明是学生；（2）张亮比陈华高；）张亮比陈华高；（3）陈华坐在张亮与李明之间。）陈华坐在张亮与李明之间。在这三个命题中，李明、张亮、陈华都是个体；在这三个命题中，李明、张亮、陈华都是个体；“是学生是学生”是一元谓词，是一元谓词，“比比高高”是二元谓是二元谓词，词，“坐

5、坐与与之间之间”是三元谓词。是三元谓词。4 通常，我们用大写字母表示谓词，小写字母通常，我们用大写字母表示谓词，小写字母表示个体。表示个体。一般地，一个由一般地，一个由n个个体和个个体和n元谓词所组成的元谓词所组成的命题可表示为命题可表示为F（a1,a2,an）,其中其中F表示表示n元谓元谓词词,a1,a2,an 分别表示分别表示n个个体。个个体。上述命题可分别表示为上述命题可分别表示为 Q（a a）,P（b,c），），R（c,b,a）。）。注意注意：a1,a2,an的排列次序是重要的。的排列次序是重要的。5 二、个体变元和命题函数二、个体变元和命题函数 个体常元个体常元 表示具体或特定的个体

6、的个体词称为个体常元。表示具体或特定的个体的个体词称为个体常元。个体变元个体变元 表示抽象的，或泛指的（或者说取值不确定的）表示抽象的，或泛指的（或者说取值不确定的）个体称为个体变元。个体称为个体变元。例例2 设设 H是表示谓词是表示谓词“能够到达山顶能够到达山顶”，若个体，若个体w:王王红；红；t：老虎；：老虎；s：汽车，则：汽车，则H（w），），H（t），），H（s）分别表）分别表示示“王红能够到王红能够到 达山顶。达山顶。”“老虎能够到达山顶。老虎能够到达山顶。”“汽车汽车能够到达山顶。能够到达山顶。”这里这里w、t、s均是个体常元。均是个体常元。H（x）：）：x能够到达山顶。这里的能够

7、到达山顶。这里的x是泛指的，不确定的，是泛指的，不确定的，x可在一定的范围内取值。故可在一定的范围内取值。故x是个体变元。是个体变元。例例3 L（x,y,z）表示）表示“x+y=z”,其中其中x,y,z为个体变元。为个体变元。L（3，2，5）表示真命题）表示真命题“3+2=5”，而而L（1，2，4）表示假命题）表示假命题“1+2=4”。6 定义定义 由一个谓词和若干个个体变元组成的命题形式称为由一个谓词和若干个个体变元组成的命题形式称为简单命题函数简单命题函数，表示为，表示为P（x1,x2,xn）。由一个或若干个简）。由一个或若干个简单命题函数以及逻辑联结词组成的命题形式称为单命题函数以及逻辑

8、联结词组成的命题形式称为复合命题函复合命题函数数。例如例如 H（x），），L（x,y,z）均是简单命题函数。）均是简单命题函数。在命题函数中，个体变元的取值范围称为在命题函数中，个体变元的取值范围称为个体域个体域。例例4 4 P（x,y）表示）表示“2 x+y=1”，若，若x,y的个体域为正整数集，的个体域为正整数集，则总是假；则总是假；若若x,y的个体域为有理数集，则的个体域为有理数集，则y=12x，对任意的有理数，对任意的有理数k，在，在x=k，y=12k时，时，P（k，12k）为真。）为真。（P(x,y)L(x,y,z)）P（y,x）是一复合命题函数）是一复合命题函数7三、量词和全总个体

9、域三、量词和全总个体域 量词量词 在命题里表示数量的词。在命题里表示数量的词。1.量词量词 使用前面介绍的概念，还不足以表达日常生活中使用前面介绍的概念，还不足以表达日常生活中的各种命题。的各种命题。例如例如：对于命题：对于命题“所有的正整数都是素数所有的正整数都是素数”和和 “有些正整数是素数有些正整数是素数”仅用个体词和谓词是很难表达的。仅用个体词和谓词是很难表达的。（1）全称量词全称量词“x”如如“所有人都是要死的。所有人都是要死的。”可表示为可表示为 x D（x），），x的个体域为全体人的集合。的个体域为全体人的集合。8（2）存在量词）存在量词“x”（3）存在唯一量词）存在唯一量词“!

10、“!x”如如“有些有理数是整数。有些有理数是整数。”令令(x）：）：x是整数；是整数；于是命题可表示为于是命题可表示为 x(x）其中其中x的个体域为有理数集合。的个体域为有理数集合。如如“方程方程x+1=0存在唯一的整数解。存在唯一的整数解。”令令P（x）：）：x是是x+1=0的整数解。的整数解。则命题可表示为则命题可表示为 !x P（x），），其中其中x的个体域为整数集。的个体域为整数集。9 2全总个体域全总个体域 含有量词的命题的表达式的形式，与个体含有量词的命题的表达式的形式，与个体域有关。域有关。含有量词的命题的真值与个体域也有关含有量词的命题的真值与个体域也有关。因此，为了方便，我们

11、引入全总个体域的概念。因此，为了方便，我们引入全总个体域的概念。宇宙间所有的个体聚集在一起所构成的集宇宙间所有的个体聚集在一起所构成的集合称为合称为全总个体域全总个体域。后面的讨论中，除特殊说明外，均使用全总后面的讨论中，除特殊说明外，均使用全总个体域。而对个体变化的真正取值范围，用特性个体域。而对个体变化的真正取值范围，用特性谓词加以限制。谓词加以限制。一般地，对全称量词，此特性谓词作蕴含的一般地，对全称量词，此特性谓词作蕴含的前件；对存在量词，此特性谓词常作合取项。前件；对存在量词，此特性谓词常作合取项。10 当取当取x的个体域为全总个体域时，必须引入一个特性谓的个体域为全总个体域时，必须

12、引入一个特性谓词将人从全宇宙的一切事物中分离出来。词将人从全宇宙的一切事物中分离出来。（1）对所有个体而言，如果它是人，则它是要死的。）对所有个体而言，如果它是人，则它是要死的。(2）存在着个体，它是人并且它活百岁以上。）存在着个体，它是人并且它活百岁以上。令令D（x）：）：x是要死的。则（是要死的。则（1）可表示为）可表示为 x D（x）。）。令令G（x）：）：x活百岁以上。则（活百岁以上。则（2）可表示为）可表示为 x G（x）。）。例例5 (1)“所有的人都是要死的。所有的人都是要死的。”(2)“有的人活百岁以上。有的人活百岁以上。”当当x的个体域的个体域E为全体人组成的集合时，符号化上

13、述命题。为全体人组成的集合时，符号化上述命题。于是令于是令M（x）：）：x是人。是人。（1）x（M（x）D（x）（2）x（M（x）G（x）11四命题符号化四命题符号化 例例6 将下列命题符号化将下列命题符号化(使用全总使用全总 个体域个体域)。(1)发光的不都是金子发光的不都是金子 解解 令令P（x）：）：x发光；发光；G（x）：）：x是金子。是金子。（2）所有运动员都钦佩某些教练。）所有运动员都钦佩某些教练。解解 令令P（x）：）：x是运动员；是运动员；T（x）：）：x是教练；是教练；Q（x，y）：）：x钦佩钦佩y。则可表示为则可表示为 或或 则该命题可表示为则该命题可表示为 12 （3）凡

14、是实数均能比较大小。）凡是实数均能比较大小。解解 令令R（x）：）：x是实数；是实数；G（x,y)：x与与y可比较大小可比较大小.例例7 将下列命题符号化将下列命题符号化 （1）会叫的狗未必咬人。会叫的狗未必咬人。解解 令令D（x）：）：x是狗；是狗；P（x）：）：x会叫；会叫；Q（x）：）：x咬人。咬人。则可表示为则可表示为 或表示为或表示为 则该命题可表示为则该命题可表示为 或者令或者令Q（x,y）:xy;13 （3）不是一切人都一样高。）不是一切人都一样高。（2）一切人不是一样高。）一切人不是一样高。解解 M(x)M(x)：x x是人；是人；G(x,y):xG(x,y):x与与y y一样

15、高一样高;H(x,y):xH(x,y):x与与y y是不同的人。是不同的人。可表示为可表示为 可表示为可表示为 或者表示为或者表示为143.3 3.3 谓词演算谓词演算的合适的合适公式公式一、谓词公式一、谓词公式 定义定义3.3.1（谓词公式的递归定义。）（谓词公式的递归定义。）(1）命题常元、命题变元和简单命题函数都是谓词公式。）命题常元、命题变元和简单命题函数都是谓词公式。（2）如果）如果A是谓词公式，则是谓词公式，则 A也是谓词公式。也是谓词公式。（3）如果）如果A和和B是谓词公式，则（是谓词公式，则（AB）,(AB）,(A B),(A B)也也 是谓词公式。是谓词公式。（4）如果）如果

16、A是谓词公式，是谓词公式，x是是A中的个体变元，则中的个体变元，则 和和 也是谓词公式。也是谓词公式。（5）只有由使用上述四条规则有限次而得到的才是谓词公式。）只有由使用上述四条规则有限次而得到的才是谓词公式。15 例例1 苏格拉底三段论可用谓词公式表示。苏格拉底三段论可用谓词公式表示。令令M（x）：）：x是人；是人；D（x）：）：x是要死的；是要死的；a：苏格拉底：苏格拉底 例例2 给出给出“x+y3”的谓词公式的表示形式。的谓词公式的表示形式。解解 令令P（x,y,z）：）：x+yz 则上述表达式可用谓词公式表示为则上述表达式可用谓词公式表示为P（x,y,3）。）。则三段论可表示为则三段论

17、可表示为 (x（M（x）D（x）M（a）)D（a）16例例1 令令 P（x,y）：）：“x 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是自由变元。是自由变元。20二、换名规则和代入规则二、换名规则和代入规则 1.换名规则换名规则

18、对约束变元进行换名，使得一个变元在一个对约束变元进行换名，使得一个变元在一个公式中只呈一种形式出现。公式中只呈一种形式出现。（1 1）约束变元换名时，该变元在量词及其辖域中）约束变元换名时，该变元在量词及其辖域中的所有出现均须同时更改，公式的其余部分不变；的所有出现均须同时更改，公式的其余部分不变；（2 2）换名时，一定要更改为该量词辖域中没有出）换名时，一定要更改为该量词辖域中没有出现过的符号，最好是公式中未出现过的符号。现过的符号，最好是公式中未出现过的符号。21解解需对需对x，y换名换名错误法：错误法：例例4 4对公式对公式 进进行换名，使各变元只呈一种形式出现。行换名，使各变元只呈一种

19、形式出现。22 2.代入规则代入规则 对于公式中自由变元的更改叫做对于公式中自由变元的更改叫做代入代入。的的x,y的自由出现分别用的自由出现分别用w,t代入得代入得 （1）对于谓词公式中的自由变元可以代入，代入时须对）对于谓词公式中的自由变元可以代入，代入时须对该自由变元的所有自由出现同时进行代入；该自由变元的所有自由出现同时进行代入；（2）代入时所选用的变元符号与原公式中所有变元的符）代入时所选用的变元符号与原公式中所有变元的符号不相同。号不相同。例如对例例如对例8中公式中公式 233.5 3.5 谓词公式的解释谓词公式的解释 对谓词公式对谓词公式A的的解释解释I包括以下几点包括以下几点：1

20、)指定一个论域指定一个论域D 2)对对A中出现的每一个中出现的每一个n元函数，指定一个元函数，指定一个D上的上的 n元个体元个体函数常量函数常量 3)对对A中出现的每一个中出现的每一个n元谓词，指定一个元谓词，指定一个D上的上的n元谓词元谓词常量常量 4)对对A中中出现的每一个个体常量及自由变元，指定出现的每一个个体常量及自由变元，指定D中的中的一个个体常量一个个体常量 5)对对A中出现的每一个命题变元中出现的每一个命题变元P，指派一个真值指派一个真值T或或F 由此得到一个命题由此得到一个命题AI，称称AI的真值为合适公的真值为合适公式式A在解释在解释I 下下的真值的真值24例例 取解释取解释

21、I如下：如下：1）D=1,2,2）定义定义D上的二元谓词上的二元谓词P真值为真值为 P(1,1):T；P(1,1):F；P(2,1):F；P(2,2):T 则则 和 在解释I下的真值分别为T 和F253.6 3.6 谓词演算的永真式谓词演算的永真式一、公式的类型一、公式的类型 定义定义 给定谓词公式给定谓词公式A，其个体域为，其个体域为E，如果，如果对于对于E上的任一组解释，公式上的任一组解释，公式A的值总是为真，则的值总是为真，则称称A在在E上是上是永真的永真的。如果对于公式。如果对于公式A的任一组解的任一组解释，公式释，公式A的值总是为假，则称的值总是为假，则称A在在E上是上是永假的永假的

22、。如果至少存在着一组指派，使公式如果至少存在着一组指派，使公式A的值为真，则的值为真，则称称A在在E上是上是可满足的可满足的。26 例例1 试说明下列各公式的类型（个体域取为全总个体域）试说明下列各公式的类型（个体域取为全总个体域）（1）（2）（3）F(x)（其中F(x):x+6=5）（4）解 (1)永真公式永真公式(2)可满足公可满足公式式(3)可满足公可满足公式式(4)永假公式永假公式27 解解 （1）可满足公式。可满足公式。（2）永假公式。永假公式。（3）永真公式。永真公式。（4）可满足公式。可满足公式。例例2 试说明下列各公式的类型。试说明下列各公式的类型。（1）（2）（3）（4）P（

23、x，y）其中其中x，y的个体域为的个体域为R；谓词；谓词P（x，y）：）：x=y；Q是命题变元是命题变元.28定义定义3.6.2设设A、B是两个公式，它们有共同的是两个公式，它们有共同的个体域个体域E，若对于，若对于A和和B的任意一组指派，两公式的任意一组指派，两公式都具有相同的真值，则称公式都具有相同的真值，则称公式A和和B在在E上等价上等价，记作记作A B。定义定义3.6.3对于公式对于公式A和和B，若，若A B 1，则，则称公式称公式A蕴含公式蕴含公式B，记作，记作A B。二、二、谓词演算中的等价式和蕴涵式谓词演算中的等价式和蕴涵式29 定理定理3.6.1(代入定理代入定理）设设A是命题

24、逻辑中的是命题逻辑中的永真式，则用谓词逻辑的合适公式代替永真式，则用谓词逻辑的合适公式代替A中的某中的某些命题变元得到的代换实例也是永真式；如果些命题变元得到的代换实例也是永真式；如果A是永假式，则上述代换实例也是永假式是永假式，则上述代换实例也是永假式。例如例如 例如例如又例如又例如 1.命题演算的推广命题演算的推广302.全称量词和存在量词间转化的等价式全称量词和存在量词间转化的等价式（其中（其中A(x)是任意的公式）是任意的公式）对个体域是有限时对个体域是有限时，给出其证明。给出其证明。证明证明 设个体域设个体域 ,则则31 3.量词辖域扩展与收缩的等价式量词辖域扩展与收缩的等价式 1.

25、证明证明 设个体域设个体域 ,则则32（2）证明证明33 证明证明（1 1）“个体域中每一个体个体域中每一个体x x，使得，使得A(x)A(x)与与B(x)B(x)均均为真为真”与与“个体域中每一个体个体域中每一个体x x，使得，使得A(x)A(x)为为真且每一个体真且每一个体x x使得使得B(x)B(x)为真为真”具有相同的含具有相同的含义义.4.4.量词分配等价式与蕴涵式量词分配等价式与蕴涵式（1）34（1）证明证明 由由得得35 证明证明 （2 2）由（由（2 2）得得（2）即即 即即 故故36证明证明（1）5.5.量词与联结词的关系量词与联结词的关系37证明证明因此在个体域中必存因此在

26、个体域中必存 在某个体在某个体a使使B(a)为假，但为假，但A(a)为真。为真。证明证明 设设 为假，为假，则则 为真，为真，为假。为假。于是于是 为假，因此为假，因此 为假。为假。故故由此由此 永真。永真。386.6.多个量词的量化次序多个量词的量化次序393.7 3.7 谓词演算的推理理论谓词演算的推理理论 一、推理规则一、推理规则 命题演算中的推理规则，可在谓词推理理命题演算中的推理规则，可在谓词推理理论中应用。论中应用。在谓词演算中，推理的形式结构仍为在谓词演算中，推理的形式结构仍为 若若 是永真式，是永真式，则称由前提则称由前提 逻辑的推出结论逻辑的推出结论C，在此在此 ,C均为谓词

27、公式。均为谓词公式。402、与量词有关的推理规则、与量词有关的推理规则1.US(全称特定化规则全称特定化规则)使用此规则时要使用此规则时要注意注意：（1）y为任意不在为任意不在A(x)中约束出现的个体变元；中约束出现的个体变元；（2）c为任意的个体常元为任意的个体常元。例如例如：设：设A(x,y):xy 考查考查 x yA(x,y):xy 可得到结论可得到结论 yA(z,y)但不能得出结论但不能得出结论 yA(y,y)41 使用此规则时应使用此规则时应注意注意：（1）c 是使是使A为真的特定个体常元；为真的特定个体常元；（2）c不在不在A（x)中出现中出现 （3）如果）如果A(x)中有其他自由

28、变元出现，且中有其他自由变元出现，且x是随其是随其他自由变元变化的，那么不能使用此规则他自由变元变化的，那么不能使用此规则。2.ES（存在特定化规则）（存在特定化规则）yA(z,y)例如例如：设：设A(x,y):xy，考查如下推理过程是否正确考查如下推理过程是否正确 x yA(x,y)A(z,c)423.UG（全称一般化规则）（全称一般化规则）使用此规则时注意使用此规则时注意:(1)y在在A(y)中自由出现，且中自由出现，且y取任何值时取任何值时A均为真。均为真。(2)x不在不在A(y)中约束出现中约束出现 例如例如：设：设A(x,y):xy，考查下面的推理过程考查下面的推理过程:(1)xA(

29、x,y)(2)x xA(x,x)是错误的是错误的!434、EG（存在一般化规则）（存在一般化规则）使用此规则时注意使用此规则时注意:(1)C是个体域中某个确定的个体。是个体域中某个确定的个体。(2)代替代替C的的x不能已在不能已在A(c)中出现。中出现。例如例如：设：设A(x,y):xy，考查下面的推理过程考查下面的推理过程:(1)A(x,c)(2)xA(x,x)是错误的是错误的!44二、推理规则的应用二、推理规则的应用 例例1 1 证明苏格拉底的三段论。证明苏格拉底的三段论。解解 令令M(x):x是人是人;D(x):x是要死的是要死的;c:苏格拉底。苏格拉底。于是苏格拉底三段论可表示为：于是

30、苏格拉底三段论可表示为：证明证明（1）M(c)P（2）P（3）T（1）;US（4）D(c)T(1),(3);I 45例例2 证明证明 （3）C(a)Q(a)T（2）;ES 证明证明 （1）P （2）P （4）T（1）;US （5）C(a)T（3）；）；I （6）W(a)R(a)T（4）,（5）；）；I （7）Q(a)T（3）；）；I （8）R(a)T（6）；）；I （9）Q(a)R(a)T（7）,（8）；）；I （10）T（9）;EG46例例3 证明证明证明证明 （1）附加前提附加前提 （2）T（1）；）；E （6）Q(c)T（3）,（5）；）；I （7）T（6）;EG （3）T（2）;ES

31、（4）P (5)T（4）;US47例例4 证明证明 （1）附加前提附加前提 （2）T（1）；）；E证证法一法一:(间接证明法间接证明法)（3）T（2）；）；I （4）T（2）；）；I （5）T（4）；）；I （6）T（3）；）；E （7）T（6）;ES （8）T（5）;US （9）T（7）（）（8）；）；I （10）T（9）；）；E （11）P （12）T（11）;US （13）T（10）（）（12）;I48 证证法二法二 （1）附加前提附加前提 （2）T（1）；）；E （3）P （4）T（2）;ES （5）T（3）;US （6）T（4）（）（5）；）；I （7）T（6）;EG （8）T（1）

32、（）（7）；）；CP （9）T（8）；）；E 原题可转化为证明原题可转化为证明49 证明证明（1）P （2）T（1）；）；I例例5 指出下面推理的错误指出下面推理的错误.（3）T（1）；）；I （4）T（2）;ES （5）T（3）;ES （6）T（4）（）（5）；）；I （7）T（6）;EG 因此因此 50 例例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

33、,5)为假为假.但有下面的推理过程：但有下面的推理过程：(1)xD(x,5)P (2)D(z,5)T(1);ES (3)xD(x,5)T(2);UG 因此，因此，xD(x,5)xD(x,5).51 例例7 7 对多个量词的使用情况，观察下列对多个量词的使用情况，观察下列推理过程推理过程.证明证明（1）前提前提 （2）US（1）（3）ES（2）（4）UG（3）（5）EG（4）推出错误结论：推出错误结论：与与 可交换可交换.52 习习 题题1 1 将下列命题符号化将下列命题符号化.（1 1）在上海高校学习的学生，未必都是上海籍的学生。）在上海高校学习的学生，未必都是上海籍的学生。解解 令令 H(x

34、)：x是在上海高校学习的学生是在上海高校学习的学生 S(y)：y是上海籍的学生是上海籍的学生 或者或者（2 2）没有一位女同志既是国家选手又是家庭妇女。）没有一位女同志既是国家选手又是家庭妇女。解解 令令W(x):x是一位女同志；是一位女同志；C(x):x是国家选手；是国家选手；H(x):x是家庭妇女是家庭妇女 x(W(x(W(x)C(x)H(x)53（3 3）对于每一个实数对于每一个实数x x，存在一个更大的实数存在一个更大的实数y y。解解 令令R(x)：x是实数；是实数；G(x,y):x比比y大。大。x(R(x)y(R(y)Gy(R(y)G(y,x)（4 4）某些汽车比所有的火车都慢，但

35、至少有一列火车比每）某些汽车比所有的火车都慢，但至少有一列火车比每辆汽车快。辆汽车快。解解 令令C(x)：x是汔车；是汔车；H(x)：x是火车；是火车；S(x,y):x比比y慢。慢。542 2 对下列谓词公式中的约束变元进行改名对下列谓词公式中的约束变元进行改名.(x(P(x)(R(x)Q(x)xR(x)zS(x,z)(R(x)Q(x)xR(x)zS(x,z)解解 对对 x(P(x)(R(x)Q(x)中的中的x换为换为y.xR(x)xR(x)中的中的x x换名为换名为t t得得 3.3.将下面谓词公式中的自由变元进行代换将下面谓词公式中的自由变元进行代换.解解 对对 y(P(x,y)y(P(x

36、,y)中的自由变元中的自由变元x x和和 Q(x,z)Q(x,z)中的自由变中的自由变元元x x代换为代换为t,t,对对 x(R(x,y)x(R(x,y)中的自由变元中的自由变元y y代换为代换为s s得得 55 4.用构造推理过程的方法证明用构造推理过程的方法证明证明证明56证明证明T(1);UST(2);UST(3),(4);IT(5);E前提前提前提前提57证明证明T(3):IT(4):IT(1),(5):IT(4):IT(2),(7):IT(8):EST(6):UST(9),(10):IT(11):EGT(3),(12):CP585.符号化下述命题,并推证其结论。“所有有理数是实数，某些有理数是整数，所有有理数是实数，某些有理数是整数，因此某些实数是整数因此某些实数是整数。”解解 先将命题符号化先将命题符号化 令令Q(x):x是有理数；是有理数；R(x):x是实数是实数;I(x);x是整是整数数.证明证明T(1);EST(2);UST(3);IT(4),(5);IT(3);IT(6),(7);IT(8);EG