1、引言引言 命题逻辑命题逻辑好像功能强大，但还是有些问题难以解决。好像功能强大，但还是有些问题难以解决。 如杨圣洪要喝水、刘翔要喝水、姚明要喝水、姚晨要喝如杨圣洪要喝水、刘翔要喝水、姚明要喝水、姚晨要喝水、刘德华要喝水、水、刘德华要喝水、，可归纳为，可归纳为“某某要喝水某某要喝水”，无，无法表示。法表示。 所有的人都要呼吸、喝水、吃饭所有的人都要呼吸、喝水、吃饭，“所有所有”如何表如何表示呢？示呢？ 有些人要升官、有些人要失恋有些人要升官、有些人要失恋，“有些有些”又如何表又如何表示？示？ 所有所有男人都会多男人都会多看看几眼漂亮几眼漂亮女人女人 所有所有女人都会多女人都会多喜欢喜欢漂亮的漂亮的
2、衣服衣服 又如有名又如有名三段论三段论：所有人都是要变老的，杨圣洪是人，：所有人都是要变老的，杨圣洪是人，所以杨圣洪也会变老的，无法表示所以杨圣洪也会变老的，无法表示。 为此为此需要我们学习新的逻辑工具需要我们学习新的逻辑工具-谓词逻辑谓词逻辑或一阶逻辑或一阶逻辑谓词逻辑基本概念谓词逻辑基本概念个体词和谓词个体词和谓词定义：定义： 个体词个体词是指可以独立存在的客体，可以是一个具体是指可以独立存在的客体，可以是一个具体的事物或抽象的概念，是原子命题所描述的对象。的事物或抽象的概念，是原子命题所描述的对象。谓词谓词是用来说明个体的性质或个体间的关系。是用来说明个体的性质或个体间的关系。例如例如
3、小王是个大学生小王是个大学生 3大于大于2谓词个体词个体词个体词谓词基本概念基本概念1、谓词、谓词 “某某要喝水某某要喝水”、“喜欢漂亮衣服喜欢漂亮衣服”、“喜欢帅哥喜欢帅哥”、“结婚生崽结婚生崽”都是所在句子的都是所在句子的谓语部分谓语部分。 命题逻辑命题逻辑中中用小写字母用小写字母表示命题。表示命题。 谓词逻辑谓词逻辑中用大写字母表示中用大写字母表示谓语部分谓语部分，如，如 用用W表示表示“要喝水要喝水”， 用用L表示表示“喜欢漂亮衣服喜欢漂亮衣服”， 用用H表示表示“喜欢帅哥喜欢帅哥”， 用用M表示表示“结婚生崽结婚生崽”。 基本概念基本概念2、个体常元、个体常元 表示某种表示某种判断判
4、断的语句一般都有的语句一般都有主语主语。 如如“刘翔刘翔”、“姚明姚明”。 为了描述方便，常用为了描述方便，常用小写字母小写字母表示这些个体。表示这些个体。 如如a表示表示“刘翔刘翔”， c表示表示“姚明姚明”， 这些表示具体个体的小写字母，称为这些表示具体个体的小写字母，称为“个体常元个体常元”或个或个体常量。体常量。 其他学科中，也是用字母表中靠前的字母表示常量。其他学科中，也是用字母表中靠前的字母表示常量。基本概念基本概念3、个体变元、个体变元 如如“某某某某”、“男人男人”、“女人女人”， 常用常用x,y,z,r,s,t等字母表中靠后的字母表示，等字母表中靠后的字母表示， 其他学科中，
5、也是这样表示，其他学科中，也是这样表示， 因此因此“某某要喝水某某要喝水”表示为表示为W(x), ,x泛指所有的人，泛指所有的人， “女人喜欢漂亮衣服女人喜欢漂亮衣服”表示为表示为L(x,y)，x泛指泛指“女人女人”、y泛指泛指“衣服衣服”， “女人喜欢帅哥女人喜欢帅哥”表示为表示为H(y,z)，其中其中y泛指女人、泛指女人、z泛指泛指帅哥。帅哥。 “男人结婚生崽男人结婚生崽”表示为表示为M(z)，z泛指男人。泛指男人。 谓词谓词 形如形如“b是是A”类型的命题可表达为类型的命题可表达为A(b)；表示多个个体间关系的命题，可表达为表示多个个体间关系的命题，可表达为B(a，b)，或或P(a，b，
6、c)定义定义:和一个个体相联系的谓词称为和一个个体相联系的谓词称为一元谓词一元谓词，和二个，和二个个体相联系的谓词称为个体相联系的谓词称为二元谓词二元谓词，和，和n个个体相联系的个个体相联系的谓词称为谓词称为n元谓词元谓词。个体常元个体常元 表示具体的或特定的个体，表示具体的或特定的个体，如如a，b，c，等；等；个体变元个体变元 表示抽象的或泛指的个体，表示抽象的或泛指的个体，如如x，y，z，等。等。谓词常项谓词常项 表示具体性质或关系的谓词，表示具体性质或关系的谓词， R(a)表示表示a是是人；人；谓词变项谓词变项 表示抽象或泛指的谓词表示抽象或泛指的谓词 ，如：如：P(a)表示表示a具具有
7、有P 性质性质。谓词表达式和命题函数谓词表达式和命题函数定义定义:一个原子命题可以用一个谓词常项一个原子命题可以用一个谓词常项P和几个个体常和几个个体常元，如元，如a，b，c，表示成，表示成P(a，b，c，)的形的形式。称式。称P(a，b，c，)为原子命题或命题的为原子命题或命题的谓词表达谓词表达式式。一个谓词常项一个谓词常项P和几个个体变元如和几个个体变元如x，y，z，表示表示成成P(x，y，z，)的形式，称为的形式，称为命题函数命题函数，其中的个，其中的个体变元可以代表任意一个个体。体变元可以代表任意一个个体。注意：注意：命题的谓词表达式是有真值的，命题函数的真值命题的谓词表达式是有真值的
8、，命题函数的真值是不确定的是不确定的。例题例题写出下列命题写出下列命题的谓词表达式的谓词表达式。 1. 小王和小李是大学生。小王和小李是大学生。解：解：设设A(x)：x是大学生。是大学生。a：小王，：小王，b：小李。：小李。 A(a) A(b)2. 北京是中国的首都。北京是中国的首都。解：解：设设F(x，y)：x是是y的首都。的首都。a：北京，：北京，b：中国。：中国。 F(a，b)3. 如果你来，他就走。如果你来，他就走。解：解：设设P(x)：x来。来。Q(x)：x走。走。a：你，：你，b：他。：他。 P(a) Q(b)例题（续）例题（续）4. 如果如果3 2，2 1，则，则3 1。解：解：
9、设设B(x，y)：x y。a：3，b：2，c：1。则。则 ： B(a，b) B(b，c) B(a，c) 5. 武汉位于北京和广州之间。武汉位于北京和广州之间。解：解：设设Q(x，y，z)：y位于位于x和和z之间。之间。a：北京，：北京，b：广州，：广州，c：武汉。：武汉。 Q(a，c，b)个体域个体域定义定义:命题函数中，个体变元的取值范围称为命题函数中，个体变元的取值范围称为个体域个体域或或论述域论述域。 个体域可以是有限的，也可以是无限的。把宇宙中一个体域可以是有限的，也可以是无限的。把宇宙中一切事物作为对象的的集合称为切事物作为对象的的集合称为全总个体域全总个体域。通常，没有特别说明时，
10、个体变元的论述域是指全总个通常，没有特别说明时，个体变元的论述域是指全总个体域。体域。如：如：A(x)表示：表示：x是大学生。是大学生。个体域：计科个体域：计科1班班学生，则学生，则A(x)是永真式。是永真式。个体域：希望小学个体域：希望小学1班班学生，则学生，则A(x)是永假式。是永假式。个体域：个体域：xx公司公司员工，其中有些是大学生，有些不是员工，其中有些是大学生，有些不是大学生，则对有些人，大学生，则对有些人，A(x)为真，对有些人，为真，对有些人，A(x)为假。为假。例题例题给出执行语句给出执行语句“If P(x) then x：=1”以后以后x的值，其中的值，其中P(x)为语句为
11、语句“x 1”，且执行到该语句时，且执行到该语句时x的值如下：的值如下：1) x=0 2) x=1 3) x=2解解 1) 若若x=0，P(x)为语句为语句“0 1”，真值为，真值为0，不执行赋，不执行赋值语句值语句“x：=1”，所以，所以x=0。2) 若若x=1，P(x)为语句为语句“1 1”，真值为，真值为0，不执行赋值语，不执行赋值语句句“x：=1”，所以，所以x=1。3) 若若x=2，P(x)为语句为语句“2 1”，真值为，真值为1，执行赋值语句，执行赋值语句“x：=1”，所以，所以x=1。量词量词定义：定义：表示个体常元或个体变元之间数量关系的词称为表示个体常元或个体变元之间数量关系
12、的词称为量词量词。量词有两种：量词有两种： 全称量词全称量词 符号符号： x表示对个体域“所有的x”，“每一个x”，“一切x”等。 存在量词存在量词 符号符号： x表示个体域中“存在这样的x”，“某个x”，“至少有一个x”或“有一些x”等。 xF(x)表示个体域中所有个体都有性质表示个体域中所有个体都有性质F xF(x)表示个体域中存在个体有性质表示个体域中存在个体有性质F基本概念基本概念4、全称量词、全称量词 为了表示为了表示“所有女人都喜欢漂亮的衣服所有女人都喜欢漂亮的衣服”、 “所有女人都喜欢帅哥所有女人都喜欢帅哥”等中等中 可能是可能是“ALL”的字母的字母A倒写，表示倒写，表示所有、
13、全部所有、全部。 当用当用x泛指泛指“人人”，“所有人所有人”表示为表示为“ x”， “所有活人都要喝水所有活人都要喝水”表示为表示为 xW(x)。 当用当用x表示表示“女人女人”, ,y表示表示漂亮的衣服漂亮的衣服时，时， “所有女人所有女人”则表示为则表示为 x x、 “所有漂亮的衣服所有漂亮的衣服”则表示为则表示为“ y”，因此，因此 “所有女人都喜欢漂亮的衣服所有女人都喜欢漂亮的衣服”表示为表示为 x yL(x,y)。 当用当用x表示表示“女人女人”, ,y表示帅哥时，表示帅哥时， “所有女人都喜欢帅哥所有女人都喜欢帅哥”表示为表示为 x yH(x,y)。 基本概念基本概念5、存在量词
14、、存在量词 为了表示为了表示“有些男人结婚生崽有些男人结婚生崽”中中“有些有些”， 引入符号引入符号“ ”， 。 称为称为存在量词存在量词。 它是它是Exist的首字母，左旋的首字母，左旋180180度，度， 如用如用z表示表示“男人男人”，那么，那么 “有些男人有些男人”表示为表示为“ z”， “有些男人结婚生崽有些男人结婚生崽”表示为表示为“ zM(z)”。例题例题假设假设F(x)表示表示x选修离散数学，选修离散数学，x的个体域是这个班的同的个体域是这个班的同学，将学，将下下面的两个命题符号化。面的两个命题符号化。1. 这个班的所有学生都选修离散数学这个班的所有学生都选修离散数学2. 这个
15、班有些学生选修离散数学这个班有些学生选修离散数学解解 当个体域当个体域是这个班的同学是这个班的同学时：时：1. xF(x)2. xF(x)若个体域是全总个体域时，要若个体域是全总个体域时，要引入一个新的谓词表示个引入一个新的谓词表示个体的取值范围。称这个表示个体范围的谓词为体的取值范围。称这个表示个体范围的谓词为特性谓词。特性谓词。例题例题假设假设F(x)表示表示x选修离散数学，将选修离散数学，将下下面的两个命题符号化。面的两个命题符号化。1. 这个班的所有学生都选修离散数学这个班的所有学生都选修离散数学2. 这个班有些学生选修离散数学这个班有些学生选修离散数学解解 （没有特别说明时个体域是全
16、总个体域）（没有特别说明时个体域是全总个体域）设特性谓词设特性谓词S(x)：表示：表示x是这个班的同学，是这个班的同学，1. x(S(x) F(x)2. x(S(x) F(x)注意注意：在使用全称量词时，在使用全称量词时， 特性谓词和表示个体性质的谓词特性谓词和表示个体性质的谓词构成构成条件关系式条件关系式； 在使用存在量词时，特性谓词和表示个体在使用存在量词时，特性谓词和表示个体性质的谓词构成性质的谓词构成合取关系式合取关系式。例题例题在个体域分别为在个体域分别为：(a):(a):自然数集合，自然数集合，(b):(b):实数集合时，实数集合时，将下列命题符号化，并给出它们的真值。将下列命题符
17、号化，并给出它们的真值。对于任意的对于任意的x，均有，均有x23x+2=(x1)(x2);存在存在x，使得，使得x+5=2。解解 假设假设F(x)：x23x+2=(x1)(x2)，G(x)：x+5=2。 (a) 个体域为自然数集合。个体域为自然数集合。符号化为：符号化为： xF(x)，真值为，真值为1。符号化为：符号化为： xG(x)，真值为，真值为0。(b) 个体域为实数集合。个体域为实数集合。符号化为：符号化为： xF(x)，真值为，真值为1。符号化为：符号化为： xG(x)，真值为，真值为1。量词量词当论述域中的元素个数有限时，例如，论述域为当论述域中的元素个数有限时，例如，论述域为n个
18、元个元素的集合素的集合a1，a2，a3，an时，有时，有 x A(x) A(a1) A(a2) A(a3) A(an) x A(x) A(a1) A(a2) A(a3) A(an)例题例题若若P(x)是语句是语句“x210”，论述域为不超过，论述域为不超过4的正整数，的正整数， xP(x)和和 x P(x)的真值是什么？的真值是什么？ 解解 由于论述域为由于论述域为1，2，3，4，命题，命题 xP(x)为为 x x P P( (x x) ) P P(1)(1) P P(2)(2) P P(3)(3) P P(4)(4)而而P(1)即即“1210”为假，所以为假，所以 x P(x)为假。为假。命
19、题命题 xP(x)为为 x x P P( (x x) ) P P(1)(1) P P(2)(2) P P(3)(3) P P(4)(4)而而P(4)即即“4210”为真，所以为真，所以 x P(x)为真。为真。例题例题设设P(x，y)表示表示“x+y10”，论述域为实数，论述域为实数， x yP(x，y)和和 y xP(x，y)的真值是什么？的真值是什么？ 解解： x x yP(xyP(x，y)y)表示命题：表示命题：“对每一个实数对每一个实数x x，都存在实数，都存在实数y y，使得，使得x+y10 x+y10成立成立”，这是个真命题，真值为，这是个真命题，真值为1 1。 y y xP(xx
20、P(x，y)y)表示命题：表示命题：“存在实数存在实数y y，对每一个实数，对每一个实数x x，都有，都有x+y10 x+y10成立成立”，这是个假命题，真值为，这是个假命题，真值为0 0。注意：注意：除非所有量词都是全称量词或存在量词，否则，除非所有量词都是全称量词或存在量词，否则，多个量词同时出现时，不能随意颠倒量词的顺序，颠倒多个量词同时出现时，不能随意颠倒量词的顺序，颠倒后会改变原命题的含义。后会改变原命题的含义。基本概念基本概念6、谓词公式、谓词公式 将表示将表示全部全部的符号的符号“ ”，表示为，表示为部分部分的的“ ”称为称为量词量词， 将将单个谓词单个谓词公式如公式如W(x)，
21、带，带量词量词的谓词如的谓词如 zM(z)， 统称为统称为“谓词公式谓词公式”。 谓词谓词W(x),M(z)中只有中只有1 1个个体变元个个体变元, , 则称为则称为1 1元元谓词公式，谓词公式， 常用来刻划对象的常用来刻划对象的性质、属性性质、属性。 谓词谓词L(x,y)、H(y,z)中有中有2 2个个体变元，称为个个体变元，称为2 2元元谓词。谓词。 常用来表示常用来表示二个对象之间二个对象之间的关系，的关系， 如喜欢，如喜欢， 类似如果有类似如果有n n个个体变个个体变元则称为元则称为n n元元谓词公式。谓词公式。 个体变元的个体变元的取值取值范围称为范围称为“讨论域讨论域”， 如果如果
22、没有交待没有交待讨论域，表示对个体变元的讨论域，表示对个体变元的取值范围取值范围，不，不做做任何任何限制，泛指限制，泛指宇宙界宇宙界的万物，称为的万物，称为“全总个体域全总个体域”，常用大写常用大写字母字母U表示。表示。 基本概念基本概念利用量词、谓词将自然语言转换为谓词公式利用量词、谓词将自然语言转换为谓词公式 例例1：(1)凡人都要呼吸凡人都要呼吸 (2)有的人用左手写字。有的人用左手写字。 解解：当个体域为：当个体域为“人类人类”时时 xB(x),其中其中B(x)表示表示x人呼吸人呼吸breath. xWL(x)，其中，其中WL(x)表示表示x用左边写字。用左边写字。 当当个体域个体域为
23、全总为全总个体域个体域(宇宙万物组成宇宙万物组成) x(H(x)B(x) H(x)表示个体表示个体x是人类是人类 x(H(x) WL(x)，WL(x)表示表示x用左边写字。用左边写字。 个体域不同，谓词公式不同。个体域不同，谓词公式不同。例例2 (1)任意任意x,x2-2x+1=(x-1)2. 有有x,使得使得x*5=3解：当解：当x的取值范围即个体域为自然数的取值范围即个体域为自然数N时时 xE(x) E(x)表示表示x2-2x+1=(x-1)2 xF(x) F(x)表示表示x*5=3 当当x的个体域为实数的个体域为实数R时，时，谓词公式相同但真值不同谓词公式相同但真值不同！例题例题用谓词逻
24、辑将下列命题符号化。用谓词逻辑将下列命题符号化。1.所有的偶数均能被所有的偶数均能被2整除。整除。解解 设设 A(x)：x是偶数，是偶数，B(x)：x能被能被2整除。整除。 x(A(x) B(x)2.这个班有些学生有电脑。这个班有些学生有电脑。解解 设设 A(x)：x是这个班的学生，是这个班的学生，B(x)：x有电脑。有电脑。 x(A(x) B(x)。3.没有不犯错误的人。没有不犯错误的人。解解 设设 A(x)：x是人，是人，B(x)：x犯错误。犯错误。 x(A(x) B(x)。例题（续）例题（续）4.尽管有人聪明，但未必一切人都聪明。尽管有人聪明，但未必一切人都聪明。解解 设设 A(x)：x
25、是人，是人，B(x)：x聪明。聪明。 x(A(x) B(x)x(A(x) B(x)5.有些有些人喜欢某些体育运动。人喜欢某些体育运动。解解 设设 A(x)：x是人，是人，B(y)：y是体育运动，是体育运动， C(x，y)：x喜欢喜欢y。 x(A(x)y(B(y) C(x，y)。6.并非并非所有的工作都可以由所有的工作都可以由一些一些机器人来完成。机器人来完成。解解 设设 A(x)：x是工作，是工作，B(x，y)：x可以由可以由y来完成，来完成， R(x)：x是机器人。是机器人。 x(A(x)y(R(y) B(x，y)。基本概念基本概念例例3 (1)兔子比乌龟跑得快兔子比乌龟跑得快 (2)有的兔
26、子比所有的乌龟跑得快有的兔子比所有的乌龟跑得快 (3)并不是所有的兔子都比乌龟跑得快并不是所有的兔子都比乌龟跑得快 (4)不存在跑得同样快的两只兔子不存在跑得同样快的两只兔子. 解：解：H(x,y)表示表示x比比y跑得快跑得快. L(x,y)表示表示x与与y一样快一样快 R(x)表示表示x是兔子是兔子 T(x)表示表示x是乌龟是乌龟 (1) x y(R(x) T(y)H(x,y) (2) x y(R(x) T(y) H(x,y) (3) x y(R(x) T(y)H(x,y) x y(R(x) T(y)H(x,y) (4) x y(R(x) R(y) L(x,y) x y(R(x) R(y)
27、L(x,y)基本概念基本概念例例4任意两个不相等实数，其平方和大于积的二倍。任意两个不相等实数，其平方和大于积的二倍。 解解：个体域为：个体域为全总个体域全总个体域即不对个体变元的取值做任何即不对个体变元的取值做任何限制。限制。 F(x)表示表示x是实数，是实数， G(x,y)表示表示x y， H(x,y)表示表示xy，则原话表示为，则原话表示为 x y (F(x) F(y) G(x,y)H(x2+y2,2xy)。 若用若用f(x,y)表示表示x2+y2，g(x,y)表示表示2xy，则原话表示为，则原话表示为 (F(x) F(y) G(x,y)H(f(x,y),g(x,y) 因为对于实数因为对
28、于实数x，y，(x2-2xy+y2)=(x-y)2， 当当x y时，有时，有(x-y)20， 故故(x2-2xy+y2)0， 故故x2+y22xy， 故故H(x2+y2,2xy) 为真为真 故原话正确，故以上公式的真值为故原话正确，故以上公式的真值为1 1。 故谓词公式可出现个体变元故谓词公式可出现个体变元,平方平方,乘、倍数、函数等。乘、倍数、函数等。基本概念基本概念例例5表示表示“所有人都要变老的，杨圣洪是人，所以杨圣洪也所有人都要变老的，杨圣洪是人，所以杨圣洪也会变老的会变老的”。 解解：个体域为全总个体域，即对个体变元的取值不做任：个体域为全总个体域，即对个体变元的取值不做任何限。何限
29、。 H(x)表示对象表示对象x是人类，是人类， O(x)表示对象表示对象x变老，变老， c表示个体常元表示个体常元“杨圣洪杨圣洪”，则，则 H(c)表示个体常元杨圣洪是人类，表示个体常元杨圣洪是人类， O(c)表示个体常元杨圣洪要变老，原句表示表示个体常元杨圣洪要变老，原句表示 ( x(H(x)O(x) H(c)O(c)。 该公式不仅有个体变元，还有个体常元该公式不仅有个体变元，还有个体常元 基本概念基本概念例例6表示表示“所有人都要死的，苏格拉底是人，所以苏格拉底所有人都要死的，苏格拉底是人，所以苏格拉底也会死也会死”。 解解：个体域为全总个体域，即对个体变元的取值不做任：个体域为全总个体域
30、，即对个体变元的取值不做任何限制。何限制。 H(x)表示对象表示对象x是人类，是人类， O(x)表示对象表示对象x要死的，要死的， c表示个体常元表示个体常元“苏格拉底苏格拉底”，则，则 H(c)表示个体常元苏格拉底是人类，表示个体常元苏格拉底是人类， O(c)表示个体常元苏格拉底要死，原句表示表示个体常元苏格拉底要死，原句表示 ( x(H(x)O(x) H(c)O(c)。 这两个例题，语句不同，但是最后的谓词公式相同。这两个例题，语句不同，但是最后的谓词公式相同。谓词公式及解释谓词公式及解释上节上节得到一些谓词公式，得到一些谓词公式，获得一些结论，也有存在一些获得一些结论，也有存在一些疑疑惑
31、惑？ (1)谓词公式有个体谓词公式有个体常元常元、个体、个体变元变元，还可以有个体变元的，还可以有个体变元的表达式表达式，那么谓词公式究竟，那么谓词公式究竟还有还有哪些形式，究竟什么的字哪些形式，究竟什么的字符串是符串是合法的合法的谓词公式？谓词公式？ (2)同一句话有同一句话有二个不同二个不同的公式，那么这二个公式的公式，那么这二个公式等值等值吗？吗？ (3)不同的话拥有不同的话拥有同样同样的的谓词公式谓词公式，到底这二句话，到底这二句话有何共性有何共性？ (4)同一样公式在同一样公式在不同的论域不同的论域下真值不同，究竟如何确定一下真值不同，究竟如何确定一个公式的真值呢？个公式的真值呢？
32、谓词公式及解释谓词公式及解释 1.合法的谓词公式合法的谓词公式非逻辑符号非逻辑符号:个体常元、函数符号、谓词符号个体常元、函数符号、谓词符号逻辑符号逻辑符号:个体变元、量词符号、联结词、逗号、括号。个体变元、量词符号、联结词、逗号、括号。项的定义项的定义：个体常元与变元及其函数式为项。：个体常元与变元及其函数式为项。(1)个体常元和个体变元是项。个体常元和个体变元是项。(2)若若 (x1,x2, xn)是是n元函数元函数,t1,t2,tn是是n个项，则个项，则 (t1,t2, tn)是项。是项。(3)有限次使用有限次使用(2)得到的表达式是项。得到的表达式是项。原子公式原子公式： 设设R(x1
33、,x2,xn)是是n元谓词，元谓词，t1,t2,tn是项，则是项，则R(t1,t2, tn)是原子公式。是原子公式。谓词公式及解释谓词公式及解释 项的定义项的定义：个体常元与变元及其函数式为项。：个体常元与变元及其函数式为项。原子公式原子公式： 设设R(x1,x2,xn)是是n元谓词元谓词，t1,t2,tn是项，则是项，则R(t1,t2, tn)是原子公式。是原子公式。合式谓词公式合式谓词公式： (1)原子公式是合式公式；原子公式是合式公式； (2)若若A是合式公式，则是合式公式，则( A)也是合式公式；也是合式公式； (3)若若A,B合式，则合式，则A B, A B, AB , AB 合式合
34、式 (4)若若A合式，则合式，则 xA、 xA合式合式 (5)有限次使用有限次使用(2)(4)得到的式子是合式。得到的式子是合式。谓词公式及解释谓词公式及解释 (F(x) F(y) G(x,y)H(f(x,y),g(x,y)、 x y(R(x) T(y)H(x,y)、 x y(R(x) T(y)H(x,y)、 x(H(x) WL(x)、( x(H(x)O(x) H(c) )O(c)， 因此以上公式均是合法的公式，而因此以上公式均是合法的公式，而 F(x) F(y) G(x,y)、F(y)G(x,y)不是合法不是合法的公式。的公式。 凡按照以上凡按照以上5 5条规则写出的表达式，就是合法谓词公式
35、条规则写出的表达式，就是合法谓词公式( (也称为也称为合式公式合式公式) )。 不再拘泥不再拘泥于某个具体的于某个具体的自然自然语句。语句。 直接研究含义直接研究含义不确定不确定或或泛指泛指的的谓词谓词公式。公式。 从从形式上形式上研究研究合式公式合式公式的性质。的性质。谓词公式及解释谓词公式及解释 个体变元的身份个体变元的身份量词指导变元量词指导变元： xA和和 xA中的中的x量词辖域量词辖域： xA和和 xA中的中的A为量词为量词 / 辖域辖域变元的约束出现变元的约束出现：指导变元的每次出现：指导变元的每次出现(称约束变元称约束变元)。变元的自由出现变元的自由出现：不是约束出现的变元：不是
36、约束出现的变元(称自由变元称自由变元) 。例题例题 x(F(x,y)G(x,z)解解： x是量词是量词 的指导变元。的指导变元。 (F(x,y)G(x,z)是量词是量词 的辖域的辖域 在在 (F(x,y)G(x,z)中中x是约束出现，出现是约束出现，出现2次。次。 在在(F(x,y)G(x,z)自由出现的变元自由出现的变元y/z，各一次。，各一次。 谓词公式及解释谓词公式及解释 个体变元的身份个体变元的身份量词指导变元量词指导变元： xA和和 xA中的中的x量词辖域量词辖域： xA和和 xA中的中的A为量词为量词 / 辖域辖域变元的约束出现变元的约束出现：指导变元的每次出现：指导变元的每次出现
37、(称约束变元称约束变元)。变元的自由出现变元的自由出现：不是约束出现的变元：不是约束出现的变元(称自由变元称自由变元) 。 例题例题 x(F(x,y)G(x,z)例题例题 x(F(x)G(y)y(H(x) L(x,y,z)解：解： 量词量词 的指导变元的指导变元x, (F(x)G(y)是量词是量词 的辖域，其中的辖域，其中x是约束出现，是约束出现，y是自是自由出现。由出现。 量词量词 的指导变元的指导变元y, H(x) L(x,y,z)是量词是量词 的辖域，其中的辖域，其中x是自由是自由2次，次，y是约束是约束出现。整个公式中是约束出现。整个公式中是约束1自由自由2次。次。谓词公式及解释谓词公
38、式及解释 个体变元的身份个体变元的身份 例题例题 分析分析 x(F(x)G(y)y(H(x) L(x,y,z)变元身份变元身份解解： x的辖域是：的辖域是：(F(x)G(y)，约束变元是，约束变元是x，x有有1次约束出次约束出现，现，y是自由变元，有是自由变元，有1次自由出现。次自由出现。 y的辖域是：的辖域是：H(x) L(x,y,z)，约束变元是，约束变元是y，y有有1次约束出次约束出现，现，x与与z是自由变元，各有是自由变元，各有1次自由出现。次自由出现。 尽管尽管x在公式在公式 x(F(x)G(y)出现，又在出现，又在 y(H(x) L(x,y,z)出现，但两个出现，但两个x不是一回事
39、，不是一回事， 只是恰巧二个名字相同而矣，只是恰巧二个名字相同而矣， 好比有好比有2 2个个李勇，一个是正坐在家里看电视的李勇，一个是正坐在家里看电视的“李勇李勇”，一个是在马路上散步的一个是在马路上散步的“李勇李勇”， 为了避免这种为了避免这种“误会误会”出现，要对出现，要对“约束变元约束变元”改名。改名。谓词公式及解释谓词公式及解释 个体变元的身份个体变元的身份 例题例题 分析分析 x(F(x)G(y)y(H(x) L(x,y,z)变元身份变元身份解解：尽管：尽管x在公式在公式 x(F(x)G(y)出现，又在出现，又在 y(H(x) L(x,y,z)出现，但两个出现，但两个x不是一回事，不
40、是一回事， 只是恰巧二个名字相同而矣，只是恰巧二个名字相同而矣， 为避免这种为避免这种“误会误会”出现要对出现要对“约束变元约束变元”改名。改名。 将量词将量词 x的指导变元的指导变元x，x的每次约束出现换成公式中未的每次约束出现换成公式中未出现的出现的r。 将量词将量词 y指导变元指导变元y、约束变元、约束变元y的每次出现换成公式中未的每次出现换成公式中未出现的出现的s，则原式为，则原式为 r(F(r)G(y)s(H(x) L(x,s,z)， 所有约束变元与自由变元均不重名，无误会。所有约束变元与自由变元均不重名，无误会。 谓词公式及解释谓词公式及解释 个体变元的身份个体变元的身份 例题例题
41、 分析分析 x y(P(x,y) Q(y,z)xP(x,y)作用域与变元约作用域与变元约束情况束情况 解解： x、 y的的作用域作用域是是(P(x,y) Q(y,z)， x的的作用域作用域是是P(x,y)。 将与将与自由变元自由变元同名同名约束变元约束变元yr， 将与将与前一个前一个同名同名约束变元约束变元x xs，则原公式，则原公式 x r(P(x,r) Q(r,z)sP(s,y) 谓词公式及解释谓词公式及解释 个体变元的身份个体变元的身份 例题例题 x(P(x)xQ(x,z)yR(x,y) Q(x,y) 解解： x的辖域是的辖域是P(x)xQ(x,z)yR(x,y)，。，。 x的辖域是的辖
42、域是Q(x,z) y的辖域是的辖域是R(x,y) s(P(s)rQ(r,z)tR(s,t) Q(x,y) 改名规则：改名规则：一般仅对约束变元改名一般仅对约束变元改名 后出现者约束变元也要改名。后出现者约束变元也要改名。 方法方法：将量词的指导变元，及辖域中约束变元每次约束：将量词的指导变元，及辖域中约束变元每次约束出现，全部换成公式中未出现的字母。出现，全部换成公式中未出现的字母。谓词公式及解释谓词公式及解释 个体变元的身份个体变元的身份 闭公式闭公式：不含自由变元的谓词公式：不含自由变元的谓词公式 。 x(F(x,y)G(x,z)因因y,z是自由变元，故不是是自由变元，故不是。 r(F(r
43、)G(y)s(H(x) L(x,s,z) 因为因为y,x,z自由故不是自由故不是 x r(P(x,r) Q(r,z)sP(s,y) 因因z与与y自由自由，故不是，故不是。 s(P(s)rQ(r,z)tR(s,t) 因因z自由故不是自由故不是(F(x) F(y) G(x,y)H(f(x,y),g(x,y) 因因x/y自由故不是自由故不是以下公式均没有自由变元，均为闭公式：以下公式均没有自由变元，均为闭公式： x y(R(x) T(y)H(x,y)、 x y(R(x) T(y)H(x,y)、x y(R(x) T(y)H(x,y)、 x y(R(x) T(y) H(x,y)、x y(R(x) R(y
44、) L(x,y)、 x y(R(x) R(y) L(x,y)、 x(H(x)B(x)、 x(H(x) WL(x)、( x(H(x)O(x) H(c)O(c)谓词公式及解释谓词公式及解释 谓词公式的真值谓词公式的真值 前面我们学习前面我们学习“合式公式合式公式”时，说过不再拘泥于某个具时，说过不再拘泥于某个具体的自然语句，从形式上研究合式公式的性质。体的自然语句，从形式上研究合式公式的性质。 但谓词公式是逻辑公式，它总得有一个真假呀？但谓词公式是逻辑公式，它总得有一个真假呀？ 如何确定其真假呢？如何确定其真假呢？ 神马不能总是浮云？神马不能总是浮云？ 总得落地。总得落地。 确定真值的方法：确定真
45、值的方法： (1)(1)确定个体域，即个体的取值范围，确定个体域，即个体的取值范围，哪个范围哪个范围？ (2)(2)将个体常元指定为个体域的具体值。将个体常元指定为个体域的具体值。哪个对象哪个对象？ (3)(3)函数常元表示指定个体域中个体变元的项。函数常元表示指定个体域中个体变元的项。 (4)(4)用指定个体域中的对象来解释各个原子公式。用指定个体域中的对象来解释各个原子公式。 (5)(5)用原子公式的解释来描述整个公式的含义。用原子公式的解释来描述整个公式的含义。原义？原义？ 根据个体域中知识，判断整个公式的含义是否正确，若根据个体域中知识，判断整个公式的含义是否正确，若对则公式的真值为对
46、则公式的真值为1 1，否则为，否则为0 0谓词公式及解释谓词公式及解释 谓词公式的真值谓词公式的真值例题例题： x(F(x)G(x) 其中其中x的的取值范围取值范围是什么？是什么？ F(x)的的含义含义是什么？是什么？G(x)的的含义含义是什么？是什么？ 将这些问题确定后，表达式将这些问题确定后，表达式 x(F(x)G(x)的真值就确定的真值就确定了，这就是公式的了，这就是公式的解释解释。 dom(x)=D1=全总个体域全总个体域 F(x)表示表示x是人，是人，G(x)表示表示x是是黄种黄种人。人。 x(F(x)G(x)：所有的人都是：所有的人都是黄种黄种人，人，值为值为F. dom(x)=D
47、2=实数集实数集R F(x)表示表示x是自然数，是自然数，G(x)表示表示x是是整数整数。 x(F(x)G(x)：所有的自然数都是：所有的自然数都是整数整数，值为值为T.谓词公式及解释谓词公式及解释 例例： x y (F(x) F(y) G(x,y)H(f(x,y),g(x,y) f(x,y),g(x,y)是函数变元，一元谓词公式是函数变元，一元谓词公式F(x),二元谓词二元谓词G与与H。 x与与y的的个体域个体域：全总个体域全总个体域。 F(x):x是是实数实数 G(x,y):x y H(x,y):xy f(x,y)=x2+y2 g(x,y)=2xy 这时整个这时整个公式的含义公式的含义：
48、对于任意的对于任意的x和和y，若，若x与与y是实数且是实数且x y，那么，那么x2+y2 2xy ，其真值为其真值为1. 如果如果H(x,y): xy f(x,y)=x2+y2 g(x,y)=2xy 这时整个公式的含义：这时整个公式的含义： 对于任意的对于任意的x和和y，若，若x与与y是实数且是实数且x y，那么，那么x2+y2 2xy ，其真值为其真值为1. 总结总结： 个体常元的值个体常元的值、个体变元个体变元的值域、的值域、确定函数确定函数、谓词公式谓词公式的的含义。含义。谓词公式及解释谓词公式及解释 个体常元的值个体常元的值、个体变元个体变元的值域、的值域、确定函数确定函数、谓词公式谓
49、词公式的的含义。含义。例例4：个体变元的值域：个体变元的值域D=N, 常元的常元的a=0,函数函数f(x,y)=x+y ,g(x,y)=x*y 谓词谓词F(x,y):x=y解释下列各公式的含义解释下列各公式的含义： (1) F(f(x,y),g(x,y)原式原式=F(x+y,x*y)，x+y=x*y，对于自然数，对于自然数x/y，此式真假不，此式真假不确定，确定，故不是命题故不是命题。 (2) F(f(x,a),y)F(g(x,y),z)代入各式代入各式= F(x+0,y)F(x*y,z)=F(x,y)F(x*y,z)确定确定F后后: x=yx*y=z,真假难定真假难定,不是命题不是命题.谓词
50、公式及解释谓词公式及解释 个体常元的值个体常元的值、个体变元个体变元的值域、的值域、确定函数确定函数、谓词公式谓词公式的的含义。含义。例例：个体变元的值域：个体变元的值域D=N, 常元的常元的a=0,函数函数f(x,y)=x+y ,g(x,y)=x*y 谓词谓词F(x,y):x=y解释下列各公式的含义解释下列各公式的含义： (3) F(g(x,y),g(y,z)将函数确定后将函数确定后: F(x*y,y*z)将谓词确定后将谓词确定后: x*y=y*z, 是否成立要看是否成立要看x,y,z的值的值,非命题非命题! (4) xF(g(x,y),z)确定函数后确定函数后: xF(x*y,z) 确定谓
