离散数学(第2.1)陈瑜

1、陈瑜陈瑜Email：2022年年7月月6日星期三日星期三2022-7-62022-7-6计算机学院计算机学院2 2/70/70主要内容主要内容n 量词化逻辑量词化逻辑 1.1.谓词谓词 2.2.量词量词 3.3.全总个体域全总个体域 4.4.自由变元与约束变元自由变元与约束变元 5.5.两个量词量化谓词的真值两个量词量化谓词的真值2022-7-62022-7-6计算机学院计算机学院3 3/70/70n 命题逻辑是数理逻辑的基础，主要研究命题和命题演命题逻辑是数理逻辑的基础，主要研究命题和命题演算。原子命题是命题演算的基本单位，并把它算。原子命题是命题演算的基本单位，并把它看作是看作是不可再分解

2、不可再分解。这就带来了命题逻辑的。这就带来了命题逻辑的局限性局限性。命题逻命题逻辑研究的范围限制在辑研究的范围限制在命题及其外部关系上命题及其外部关系上，无法研究，无法研究命题内部的成份、结构，命题之间所具有的命题内部的成份、结构，命题之间所具有的逻辑特征逻辑特征（如，共同性和差异性）（如，共同性和差异性）n 例例1.1 1.1 设基本命题，设基本命题，P P：李明是大学生；：李明是大学生；Q Q：王芳是大：王芳是大学生学生 R R：松树是植物。：松树是植物。 很明显，很明显，P P与与Q Q在内部关系上，应该比在内部关系上，应该比R R密切得多。密切得多。然而，命题逻辑无法反映这种区别，也无

3、法反映然而，命题逻辑无法反映这种区别，也无法反映P P、Q Q间的共同性。间的共同性。第二章第二章: :一阶谓词逻辑一阶谓词逻辑2022-7-62022-7-6计算机学院计算机学院4 4/70/70n 命题逻辑是数理逻辑的基础，主要研究命题和命题演算。原子命题是命题演算的基本单位，并把它看作是不可再分解。这就带来了命题逻辑的局限性。命题逻辑研究的范围限制在命题及其外部关系上，无法研究命题内部的成份、结构，命题之间所具有的逻辑特征（共同性和差异性）n 例例1.11.1 设基本命题，设基本命题，P P：李明是大学生；：李明是大学生；Q Q：王芳是大：王芳是大学生学生 R R：松树是植物。：松树是植

4、物。 很明显，很明显，P P与与Q Q在内部关系上，应该比在内部关系上，应该比R R密切得多。密切得多。然而，命题逻辑无法反映这种区别，也无法反映然而，命题逻辑无法反映这种区别，也无法反映P P、Q Q间的共同性。间的共同性。第二章第二章: :一阶谓词逻辑一阶谓词逻辑2022-7-62022-7-6计算机学院计算机学院5 5/70/70解：假设：解：假设：n例例1.21.2 ( (著名的苏格拉底三段论著名的苏格拉底三段论) ) 设自然语言中的三个命题：设自然语言中的三个命题： 1 1）所有的人都是要死的；所有的人都是要死的； 2 2）苏格拉底是人；苏格拉底是人； 3 3）所以，苏格拉底是要死的

5、。所以，苏格拉底是要死的。 P P：所有的人都是要死的；：所有的人都是要死的； Q Q：苏格拉底是人。：苏格拉底是人。 R R：所以，苏格拉底是要死的。：所以，苏格拉底是要死的。 显然，无论用什么方法也无法推论出显然，无论用什么方法也无法推论出 P P，Q Q R R。 但是，这样简单的，凭直觉就知苏格拉底的论证是但是，这样简单的，凭直觉就知苏格拉底的论证是正确的推理，命题逻辑却无能为力。正确的推理，命题逻辑却无能为力。这是由命题逻辑的这是由命题逻辑的局限性造成的，因此，需要对命题的内部关系进行研究。局限性造成的，因此，需要对命题的内部关系进行研究。2022-7-62022-7-6计算机学院计

6、算机学院6 6/70/70解：假设解：假设：n例例1.21.2 (著名的苏格拉底三段论) 设自然语言中的三个命题： 1）所有的人都是要死的； 2）苏格拉底是人； 3）所以，苏格拉底是要死的。 P P：所有的人都是要死的；：所有的人都是要死的； Q Q：苏格拉底是人。：苏格拉底是人。 R R：所以，苏格拉底是要死的。：所以，苏格拉底是要死的。 显然显然，无论用什么方法也无法推论出，无论用什么方法也无法推论出 P P，Q Q R R。 但是，这样简单的，凭直觉就知苏格拉底的论证是但是，这样简单的，凭直觉就知苏格拉底的论证是正确的推理，命题逻辑却无能为力。正确的推理，命题逻辑却无能为力。这是由命题逻

7、辑的这是由命题逻辑的局限性造成的，因此，需要对命题的内部关系进行研究。局限性造成的，因此，需要对命题的内部关系进行研究。2022-7-62022-7-6计算机学院计算机学院7 7/70/70解：解：假设：n例例1.21.2 (著名的苏格拉底三段论) 设自然语言中的三个命题： 1）所有的人都是要死的； 2）苏格拉底是人； 3）所以，苏格拉底是要死的。 P：所有的人都是要死的； Q：苏格拉底是人。 R：所以，苏格拉底是要死的。 显然，无论用什么方法也无法推论出 P，Q R。 但是但是，这样简单的、凭直觉就知苏格拉底的论证是，这样简单的、凭直觉就知苏格拉底的论证是正确的推理，命题逻辑却无能为力。正确

8、的推理，命题逻辑却无能为力。这是由命题逻辑的这是由命题逻辑的局限性造成的，因此，局限性造成的，因此，需要对命题的内部关系进行研究。需要对命题的内部关系进行研究。2022-7-62022-7-6计算机学院计算机学院8 8/70/702.1 2.1 量词化逻辑量词化逻辑谓词和量词谓词和量词n 一、谓词一、谓词 PredicatePredicate 在对命题的在对命题的内部逻辑关系内部逻辑关系进行研究时，把基本进行研究时，把基本命题分成命题分成客体客体( (个体）个体）和和谓词谓词。n 客体客体命题中所描述的对象。（命题中的主命题中所描述的对象。（命题中的主语，客观实体，可以独立存在的物体）。语，客

9、观实体，可以独立存在的物体）。n 谓词谓词命题中描述的个体性质（特征）或关命题中描述的个体性质（特征）或关系的部分。系的部分。n 谓词一般用大写字母（串）表示谓词一般用大写字母（串）表示; ;n 个体用小写字母表示。个体用小写字母表示。2022-7-62022-7-6计算机学院计算机学院9 9/70/702.1 2.1 量词化逻辑量词化逻辑谓词和量词谓词和量词n 一、谓词一、谓词 PredicatePredicate 在对命题的内部逻辑关系进行研究时，把基本命题分成客体(个体）和谓词。n 客体客体命题中所描述的对象。（命题中的主命题中所描述的对象。（命题中的主语，客观实体，可以独立存在的物体）

10、。语，客观实体，可以独立存在的物体）。n 谓词谓词命题中描述的个体性质（特征）或关命题中描述的个体性质（特征）或关系的部分。系的部分。n 谓词一般用大写字母（串）表示谓词一般用大写字母（串）表示; ;n 个体用小写字母表示。个体用小写字母表示。2022-7-62022-7-6计算机学院计算机学院1010/70/702.1 2.1 量词化逻辑量词化逻辑谓词和量词谓词和量词n 一、谓词一、谓词 PredicatePredicate 在对命题的内部逻辑关系进行研究时，把基本命题分成客体(个体）和谓词。n 客体命题中所描述的对象。（命题中的主语，客观实体，可以独立存在的物体）。n 谓词命题中描述的个体

11、性质（特征）或关系的部分。n 谓词一般用大写字母（串）表示谓词一般用大写字母（串）表示; ;n 个体用小写字母表示。个体用小写字母表示。2022-7-62022-7-6计算机学院计算机学院1111/70/70n 例例1.31.3如有句子：如有句子：张红张红是一个四川大学的学生是一个四川大学的学生；王南王南是一个四川大学的学生是一个四川大学的学生；李华李华是一个四川大学的学生是一个四川大学的学生。 则在命题中必须要用三个命题则在命题中必须要用三个命题P P，Q Q，R R来表示。来表示。但是，它们都具有一个共同的特征：但是，它们都具有一个共同的特征： “ “是一个是一个四川大学的四川大学的学生学

12、生”因此，若将句子分解成：因此，若将句子分解成：“主语谓语主语谓语”用用P P表示表示“是一个是一个四川大学的四川大学的学生学生”，P P后紧跟后紧跟“某某某某人人”。则上述句子可写为：。则上述句子可写为：P(P(张红张红) )；P(P(王南王南) )；P(P(李华李华) )。一般地，一般地，P(xP(x) )：x x是一个是一个四川大学的四川大学的学生。学生。2022-7-62022-7-6计算机学院计算机学院1212/70/70n 例例1.31.3如有句子：张红是一个四川大学的学生；王南是一个四川大学的学生；李华是一个四川大学的学生。 则在命题中必须要用三个命题P，Q，R来表示。但是，它们

13、都具有一个共同的特征：但是，它们都具有一个共同的特征： “是一个是一个四川大学的四川大学的学生学生”因此，若将句子分解成：因此，若将句子分解成：“主语谓语主语谓语”用用P P表示表示“是一个是一个四川大学的四川大学的学生学生”，P P后紧跟后紧跟“某某某某人人”。则上述句子可写为：。则上述句子可写为：P(P(张红张红) )；P(P(王南王南) )；P(P(李华李华) )。一般地，一般地，P(xP(x) )：x x是一个是一个四川大学的四川大学的学生。学生。2022-7-62022-7-6计算机学院计算机学院1313/70/70n 例例1.31.3如有句子：张红是一个四川大学的学生；王南是一个四

14、川大学的学生；李华是一个四川大学的学生。 则在命题中必须要用三个命题P，Q，R来表示。但是，它们都具有一个共同的特征： “是一个四川大学的学生”因此，若将句子分解成：“主语谓语”用P表示“是一个四川大学的学生”，P后紧跟“某某人”。则上述句子可写为：P(张红)；P(王南)；P(李华)。一般地一般地，P(xP(x) )：x x是一个是一个四川大学的四川大学的学生。学生。P P：谓词：谓词x x：客体词：客体词P(x)P(x)：命题函数：命题函数2022-7-62022-7-6计算机学院计算机学院1414/70/70n 与谓词相联系的个体的数目，就是与谓词相联系的个体的数目，就是谓词的元数谓词的元

15、数。 描述描述一个个体的性质的谓词一个个体的性质的谓词叫叫“一元谓词一元谓词”。 描述描述两个个体间的关系的谓词两个个体间的关系的谓词叫叫“二元谓词二元谓词”。 如如A A：比比大大 命题命题4 4比比3 3大表示成大表示成A A（4 4，3 3） 描述描述三个个体间的关系三个个体间的关系的谓词叫的谓词叫“三元谓词三元谓词”。 如如B B：在在和和之间之间 B B（n,c,zn,c,z）：内江在成都与重庆之间。）：内江在成都与重庆之间。n 定义定义2.12.1：设：设D D是由客体构成的称为个体域的非空集合，是由客体构成的称为个体域的非空集合，以以D D中元素为值的变元称为客体变元。由形如中元

16、素为值的变元称为客体变元。由形如 谓词标识符（客体变元谓词标识符（客体变元1 1，客体变元，客体变元2 2，客体变元，客体变元n n） 构成的、其值为构成的、其值为“真真”或或“假假”的表达式，称为的表达式，称为n n元谓词。元谓词。 即即n n元谓词是描述元谓词是描述n n个个体间的关系个个体间的关系。2022-7-62022-7-6计算机学院计算机学院1515/70/70n 与谓词相联系的个体的数目，就是谓词的元数。 描述一个个体的性质的谓词叫“一元谓词”。 描述两个个体间的关系的谓词叫“二元谓词”。 如A：比大 命题4比3大表示成A（4，3） 描述三个个体间的关系的谓词叫“三元谓词”。

17、如B：在和之间 B（n,c,z）：内江在成都与重庆之间。n 定义定义2.12.1：设设D D是由客体构成的称为是由客体构成的称为个体域个体域的非空集合，的非空集合，以以D D中元素为值的变元称为客体变元。由形如中元素为值的变元称为客体变元。由形如 谓词标识符（客体变元谓词标识符（客体变元1 1，客体变元，客体变元2 2，客体变元，客体变元n n） 构成的、其值为构成的、其值为“真真”或或“假假”的的表达式表达式，称为，称为n n元谓词元谓词。 即即n n元谓词是描述元谓词是描述n n个个体间的关系个个体间的关系。2022-7-62022-7-6计算机学院计算机学院1616/70/70n定义定义

18、2.12.1：设设D D为非空的个体域，定义在为非空的个体域，定义在D Dn n( (表示表示n n个个客体都在个体域客体都在个体域D D上取值上取值) )上取值于上取值于0,10,1上的上的n n元元函 数 ， 称 为函 数 ， 称 为 n n 元 命 题 函 数 或元 命 题 函 数 或 n n 元 谓 词元 谓 词 , , 记 为记 为P(xP(x1 1,x,x2 2, ,x,xn n) )。此时，。此时，客体变元客体变元x x1 1,x,x2 2, ,x,xn n的定义的定义域都为域都为D D， P(xP(x1 1,x,x2 2, ,x,xn n) )的值域为的值域为00，1 1。n注

19、意：注意：n n元谓词中的客体或客体变元是有一定次序的。元谓词中的客体或客体变元是有一定次序的。 如如A A（4 4，3 3）为）为T T，A A（3 3，4 4）为）为F F。 如果谓词中为客体变元如果谓词中为客体变元, ,我们称为谓词填式我们称为谓词填式( (谓词命谓词命名式名式,n,n元命题函数元命题函数) )。 如如S(x),A(x,yS(x),A(x,y) )，不能判断真和假。，不能判断真和假。 只有将具体的客体代替客体变元，才能判断真和假。只有将具体的客体代替客体变元，才能判断真和假。 2022-7-62022-7-6计算机学院计算机学院1717/70/70n定义2.1：设D为非空

20、的个体域，定义在Dn(表示n个客体都在个体域D上取值)上取值于0,1上的n元函数，称为n元命题函数或n元谓词,记为P(x1,x2,xn)。此时，客体变元x1,x2,xn的定义域都为D， P(x1,x2,xn)的值域为0，1。n注意：注意：n n元谓词中的客体或客体变元是有一定次序的。元谓词中的客体或客体变元是有一定次序的。 如如A A（4 4，3 3）为）为T T，A A（3 3，4 4）为）为F F。 如果谓词中为客体变元如果谓词中为客体变元, ,我们称为我们称为谓词填式谓词填式( (谓词命谓词命名式名式,n,n元命题函数元命题函数) )。 如如S(x),A(x,yS(x),A(x,y) )

21、，不能判断真和假。，不能判断真和假。 只有将具体的客体代替客体变元，才能判断真和假。只有将具体的客体代替客体变元，才能判断真和假。 2022-7-62022-7-6计算机学院计算机学院1818/70/70n 客体取值的范围叫客体取值的范围叫个体域个体域( (论域论域) )。 谓词通常用于高级程序语言的控制语句中，谓词通常用于高级程序语言的控制语句中， 如如 if x3 then y:=5if x3 then y:=5 x3 x3是谓词，是谓词，x3x3的值由的值由x x的现行值确定。的现行值确定。n n n元谓词和命题的关系：元谓词和命题的关系： P(x,y,z):x+yP(x,y,z):x+

22、y=z 3=z 3元谓词元谓词 x=3,P(3,y,z):3+y=z 2x=3,P(3,y,z):3+y=z 2元谓词元谓词 x=3,y=4,P(3,4,z):3+4=z 1x=3,y=4,P(3,4,z):3+4=z 1元谓词元谓词 x=3,y=4,z=5,P(3,4,5):3+4=5 0 x=3,y=4,z=5,P(3,4,5):3+4=5 0元谓词元谓词( (命题命题)F)Fn 可见，可见， 0 0元谓词就是命题；命题是谓词的特殊情况，谓词是命题元谓词就是命题；命题是谓词的特殊情况，谓词是命题的扩充。的扩充。2022-7-62022-7-6计算机学院计算机学院1919/70/70n 客体

23、取值的范围叫个体域(论域)。 谓词通常用于高级程序语言的控制语句中， 如 if x3 then y:=5 x3是谓词，x3的值由x的现行值确定。n n n元谓词和命题的关系：元谓词和命题的关系： P(x,y,z):x+yP(x,y,z):x+y=z 3=z 3元谓词元谓词 x=3,P(3,y,z):3+y=z 2x=3,P(3,y,z):3+y=z 2元谓词元谓词 x=3,y=4,P(3,4,z):3+4=z 1x=3,y=4,P(3,4,z):3+4=z 1元谓词元谓词 x=3,y=4,z=5,P(3,4,5):3+4=5 0 x=3,y=4,z=5,P(3,4,5):3+4=5 0元谓词元

24、谓词( (命题命题)F)Fn 可见，可见， 0 0元谓词就是命题；命题是谓词的特殊情况，谓词是命题元谓词就是命题；命题是谓词的特殊情况，谓词是命题的扩充。的扩充。2022-7-62022-7-6计算机学院计算机学院2020/70/70n 客体取值的范围叫个体域(论域)。 谓词通常用于高级程序语言的控制语句中， 如 if x3 then y:=5 x3是谓词，x3的值由x的现行值确定。n n元谓词和命题的关系： P(x,y,z):x+y=z 3元谓词 x=3,P(3,y,z):3+y=z 2元谓词 x=3,y=4,P(3,4,z):3+4=z 1元谓词 x=3,y=4,z=5,P(3,4,5):

25、3+4=5 0元谓词(命题)Fn 可见，可见， 0 0元谓词就是命题；命题是谓词的特殊情况，谓词是命题元谓词就是命题；命题是谓词的特殊情况，谓词是命题的扩充。的扩充。2022-7-62022-7-6计算机学院计算机学院2121/70/70n 个体域对命题的真值有个体域对命题的真值有直接的影响直接的影响。 如如P(xP(x) :x) :x是科学家。是科学家。 x x在科学家范围内，则在科学家范围内，则P(xP(x) )为为T T，x x不在科学家不在科学家范围内，则范围内，则P(xP(x) )为为F F。 x x只在科学家范围内，则只在科学家范围内，则P(xP(x) )为永真。为永真。n 每个谓

26、词一般都有各自的个体域，把各种个体每个谓词一般都有各自的个体域，把各种个体域综合在一起作为论述范围的域叫全总个体域域综合在一起作为论述范围的域叫全总个体域（全论域）用（全论域）用E E表示。表示。2022-7-62022-7-6计算机学院计算机学院2222/70/70n 个体域对命题的真值有直接的影响。 如P(x) :x是科学家。 x在科学家范围内，则P(x)为T，x不在科学家范围内，则P(x)为F。 x只在科学家范围内，则P(x)为永真。n 每个谓词一般都有各自的个体域，把各种个体每个谓词一般都有各自的个体域，把各种个体域综合在一起作为论述范围的域叫域综合在一起作为论述范围的域叫全总个体域全

27、总个体域（全论域）（全论域）用用E E表示。表示。2022-7-62022-7-6计算机学院计算机学院2323/70/70几个结论几个结论1 1）谓词中个体词的顺序是十分重要的，不能随意变更。谓词中个体词的顺序是十分重要的，不能随意变更。2 2）一元谓词用以描述某一个客体的某种特性或性质，而）一元谓词用以描述某一个客体的某种特性或性质，而n n元谓词（二个以上）则用以描述元谓词（二个以上）则用以描述n n个客体之间的关系。个客体之间的关系。3 3）0 0元谓词元谓词( (不含客体词的不含客体词的) )实际上就是一般的命题。实际上就是一般的命题。4 4）具体命题的谓词表示形式和）具体命题的谓词表

28、示形式和n n元命题函数元命题函数(n(n元谓词元谓词) )是是不同的，前者是有真值的，而后者不是命题，它的真不同的，前者是有真值的，而后者不是命题，它的真值是不确定的。值是不确定的。5 5）一个）一个n n元谓词不是一个命题，但将元谓词不是一个命题，但将n n元谓词中的客体变元谓词中的客体变元都用个体域中具体的客体取代后，就成为一个命题。元都用个体域中具体的客体取代后，就成为一个命题。而且，客体变元在不同的个体域中取不同的值对是否而且，客体变元在不同的个体域中取不同的值对是否成为命题及命题的真值有很大的影响。成为命题及命题的真值有很大的影响。2022-7-62022-7-6计算机学院计算机学

29、院2424/70/70几个结论几个结论1 1）谓词中个体词的顺序是十分重要的，不能随意变更。2 2）一元谓词用以描述某一个客体的某种特性或性质，而）一元谓词用以描述某一个客体的某种特性或性质，而n n元谓词（二个以上）则用以描述元谓词（二个以上）则用以描述n n个客体之间的关系个客体之间的关系。3 3）0 0元谓词元谓词( (不含客体词的不含客体词的) )实际上就是一般的命题。实际上就是一般的命题。4 4）具体命题的谓词表示形式和）具体命题的谓词表示形式和n n元命题函数元命题函数(n(n元谓词元谓词) )是是不同的，前者是有真值的，而后者不是命题，它的真不同的，前者是有真值的，而后者不是命题

30、，它的真值是不确定的。值是不确定的。5 5）一个）一个n n元谓词不是一个命题，但将元谓词不是一个命题，但将n n元谓词中的客体变元谓词中的客体变元都用个体域中具体的客体取代后，就成为一个命题。元都用个体域中具体的客体取代后，就成为一个命题。而且，客体变元在不同的个体域中取不同的值对是否而且，客体变元在不同的个体域中取不同的值对是否成为命题及命题的真值有很大的影响。成为命题及命题的真值有很大的影响。2022-7-62022-7-6计算机学院计算机学院2525/70/70几个结论几个结论1 1）谓词中个体词的顺序是十分重要的，不能随意变更。2 2）一元谓词用以描述某一个客体的某种特性或性质，而n

31、元谓词（二个以上）则用以描述n个客体之间的关系。3 3）0 0元谓词元谓词( (不含客体词的不含客体词的) )实际上就是一般的命题。实际上就是一般的命题。4 4）具体命题的谓词表示形式和）具体命题的谓词表示形式和n n元命题函数元命题函数(n(n元谓词元谓词) )是是不同的，前者是有真值的，而后者不是命题，它的真不同的，前者是有真值的，而后者不是命题，它的真值是不确定的。值是不确定的。5 5）一个）一个n n元谓词不是一个命题，但将元谓词不是一个命题，但将n n元谓词中的客体变元谓词中的客体变元都用个体域中具体的客体取代后，就成为一个命题。元都用个体域中具体的客体取代后，就成为一个命题。而且，

32、客体变元在不同的个体域中取不同的值对是否而且，客体变元在不同的个体域中取不同的值对是否成为命题及命题的真值有很大的影响。成为命题及命题的真值有很大的影响。2022-7-62022-7-6计算机学院计算机学院2626/70/70几个结论几个结论1 1）谓词中个体词的顺序是十分重要的，不能随意变更。2 2）一元谓词用以描述某一个客体的某种特性或性质，而n元谓词（二个以上）则用以描述n个客体之间的关系。3 3）0元谓词(不含客体词的)实际上就是一般的命题。4 4）具体命题的谓词表示形式和具体命题的谓词表示形式和n n元命题函数元命题函数(n(n元谓词元谓词) )是是不不同的，前者是有真值的，而后者不

33、是命题，它的真同的，前者是有真值的，而后者不是命题，它的真值是不确定的。值是不确定的。5 5）一个）一个n n元谓词不是一个命题，但将元谓词不是一个命题，但将n n元谓词中的客体变元谓词中的客体变元都用个体域中具体的客体取代后，就成为一个命题。元都用个体域中具体的客体取代后，就成为一个命题。而且，客体变元在不同的个体域中取不同的值对是否而且，客体变元在不同的个体域中取不同的值对是否成为命题及命题的真值有很大的影响。成为命题及命题的真值有很大的影响。2022-7-62022-7-6计算机学院计算机学院2727/70/70几个结论几个结论1 1）谓词中个体词的顺序是十分重要的，不能随意变更。2 2

34、）一元谓词用以描述某一个客体的某种特性或性质，而n元谓词（二个以上）则用以描述n个客体之间的关系。3 3）0元谓词(不含客体词的)实际上就是一般的命题。4 4）具体命题的谓词表示形式和n元命题函数(n元谓词)是不同的，前者是有真值的，而后者不是命题，它的真值是不确定的。5 5）一个）一个n n元谓词不是一个命题，但将元谓词不是一个命题，但将n n元谓词中的客体变元谓词中的客体变元都用个体域中具体的客体取代后，就成为一个命题。元都用个体域中具体的客体取代后，就成为一个命题。而且，客体变元在不同的个体域中取不同的值对是否而且，客体变元在不同的个体域中取不同的值对是否成为命题及命题的真值有很大的影响

35、。成为命题及命题的真值有很大的影响。2022-7-62022-7-6计算机学院计算机学院2828/70/70二、量词二、量词 QuantifierQuantifiern 在在苏格拉底苏格拉底三段论的例子中，如要对句子：三段论的例子中，如要对句子： P P：H(xH(x)D(xD(x) )（）求否定求否定，则，则有：有：(H(x(H(x)D(xD(x)H H( ()( () )H H( ()( () ) 上述式子说明：上述式子说明：“命题命题P”P”的否定是：的否定是：“所有的人都不死所有的人都不死”。 但这与人们在日常生活中对命但这与人们在日常生活中对命题：题：“所有人都是要死的所有人都是要死

36、的”的否定为：的否定为：“并非一切的人并非一切的人都是要死的都是要死的”。显然相差甚远。显然相差甚远。 其原因在于：其原因在于： 命题命题P P的确切含义是：的确切含义是：“对任意的对任意的x x，如果，如果x x是人，则是人，则x x是是要死的要死的”。但。但H(x)D(xH(x)D(x) )并没有确切地表示出并没有确切地表示出“对任意对任意x”x”这个意思，亦即这个意思，亦即H(x)D(xH(x)D(x) )不是一个命题不是一个命题2022-7-62022-7-6计算机学院计算机学院2929/70/70二、量词二、量词 QuantifierQuantifiern 在苏格拉底三段论的例子中，

37、如要对句子： P：H(x)D(x)（所有的人都是要死的）求否定，则有：(H(x)D(x)H()() 上述式子说明：上述式子说明：“命题命题P”P”的否定是：的否定是：“所有的人都不死所有的人都不死”。但这与人们在日常生活中对命题：。但这与人们在日常生活中对命题：“所有人都是要死的所有人都是要死的”的否定为：的否定为：“并非一切的人都是并非一切的人都是要死的要死的”。显然相差甚远。显然相差甚远。 其原因在于：其原因在于： 命题命题P P的确切含义是：的确切含义是：“对任意的对任意的x x，如果，如果x x是人，则是人，则x x是是要死的要死的”。但。但H(x)D(xH(x)D(x) )并没有确切

38、地表示出并没有确切地表示出“对任意对任意x”x”这个意思，亦即这个意思，亦即H(x)D(xH(x)D(x) )不是一个命题不是一个命题2022-7-62022-7-6计算机学院计算机学院3030/70/70二、量词二、量词 QuantifierQuantifiern 在苏格拉底三段论的例子中，如要对句子： P P：H(xH(x)D(xD(x) )（所有的人都是要死的）所有的人都是要死的）求否定，则有：(H(x)D(x)H()()H()()上述式子说明：“命题P”的否定是：“所有的人都不死”。但这与人们在日常生活中对命题：“所有人都是要死的”的否定为：“并非一切的人都是要死的”。显然相差甚远。

39、其原因在于：其原因在于： 命题命题P P的确切含义是：的确切含义是：“对任意的对任意的x x，如果，如果x x是人，则是人，则x x是是要死的要死的”。但。但H(x)D(xH(x)D(x) )并没有确切地表示出并没有确切地表示出“对任意对任意x x”这个意思，亦即这个意思，亦即H(x)D(xH(x)D(x) )不是一个命题不是一个命题2022-7-62022-7-6计算机学院计算机学院3131/70/70例例1.41.4：n 符号化下述命题：符号化下述命题： 1 1）所有的老虎所有的老虎都要吃人；都要吃人； 2 2）每一个人每一个人都会犯错误；都会犯错误； 3 3）有一些人有一些人会摔跤；会摔

40、跤； 4 4）有一些人有一些人是大学生；是大学生； 5 5）每一个带伞的人每一个带伞的人都不怕雨；都不怕雨； 6 6）有一些自然数有一些自然数是素数。是素数。 上述每一个描述量词的语句下划有上述每一个描述量词的语句下划有“下划线下划线”。2022-7-62022-7-6计算机学院计算机学院3232/70/70例例1.41.4（续（续1）n 解：解：设立如下谓词：设立如下谓词： R(x)R(x)：x x会吃人；会吃人；P(xP(x) )：x x会犯错误；会犯错误； N(xN(x) )：x x会摔跤；会摔跤；Q(xQ(x) )：x x是大学生；是大学生； C(xC(x) )：x x不怕雨；不怕雨；

41、S(xS(x) )：x x是素数。是素数。 则有：则有： 1 1）所有的）所有的x x，R(x) xR(x) x 老虎；老虎； 2 2）每一个）每一个x x，P(xP(x) x) x 人人 ； 3 3）有一些）有一些x x，N(xN(x) x) x 人人 ； 4 4）有一些）有一些x x，Q(xQ(x) x) x 人人 ； 5 5）每一个）每一个x x，C(xC(x) x) x 带伞的人带伞的人 ； 6 6）有一些）有一些x x，S(xS(x) x ) x 自然数自然数 。 2022-7-62022-7-6计算机学院计算机学院3333/70/70量词的定义：量词的定义：n 上述一系列例子，都仅

42、仅只符号化了一部分内容，而对上述一系列例子，都仅仅只符号化了一部分内容，而对句子中的句子中的“对每一个对每一个”，“对任意的对任意的”，“有一些有一些”等等等等无法用谓词来表示无法用谓词来表示，这些都是与客体词的，这些都是与客体词的数量有关数量有关的的语句。语句。n 为了把它们符号化，引进如下两个符号：为了把它们符号化，引进如下两个符号： ( ( x x ) ) : : 所 有 的所 有 的 x x ； ( ( x )x ) : : 有 些有 些 x x ； 任意的任意的x x； 至少有一个至少有一个x x； 一 切 的一 切 的 x x ； 存 在存 在 x x ； 每一个每一个x x；等等

43、。等等。 等等。等等。n 定义定义2.1.2:(2.1.2:( x x) )称为全称量词称为全称量词。( ( x)x)为存在量为存在量词词, ,其中其中的的x x称为作用变量称为作用变量。一般将量词加在谓词之前，记为一般将量词加在谓词之前，记为( ( x x) )F(x), (F(x), ( x)x)F(x)F(x)。2022-7-62022-7-6计算机学院计算机学院3434/70/70量词的定义：量词的定义：n 上述一系列例子，都仅仅只符号化了一部分内容，而对句子中的“对每一个”，“对任意的”，“有一些”等等无法用谓词来表示，这些都是与客体词的数量有关的语句。n 为了把它们符号化，引进如下

44、两个符号：为了把它们符号化，引进如下两个符号： ( ( x x ) ) : : 所 有 的所 有 的 x x ； ( ( x )x ) : : 有 些有 些 x x ； 任意的任意的x x； 至少有一个至少有一个x x； 一 切 的一 切 的 x x ； 存 在存 在 x x ； 每一个每一个x x；等等。等等。 等等。等等。n 定义定义2.2:(2.2:( x x) )称为全称量词称为全称量词。( ( x)x)为存在量为存在量词词, ,其中的其中的x x称为作用变量称为作用变量。一般将量词加在谓词之前，记为一般将量词加在谓词之前，记为( ( x x) )F(x), (F(x), ( x)x)

45、F(x)F(x)。2022-7-62022-7-6计算机学院计算机学院3535/70/70量词的定义：量词的定义：n 上述一系列例子，都仅仅只符号化了一部分内容，而对句子中的“对每一个”，“对任意的”，“有一些”等等无法用谓词来表示，这些都是与客体词的数量有关的语句。n 为了把它们符号化，引进如下两个符号： ( x ) : 所 有 的 x ； ( x ) : 有 些 x ； 任意的x； 至少有一个x； 一 切 的 x ； 存 在 x ； 每一个x；等等。 等等。n 定义定义2.2:2.2:( ( x x) )称为称为全称量词全称量词。( ( x)x)为为存在量存在量词词, ,其中的其中的x x

46、称为称为作用变量作用变量。一般将量词加在谓词之前，记为一般将量词加在谓词之前，记为( ( x x) )F(x)F(x), , ( ( x)x)F(x)F(x)。全称量化命题全称量化命题存在量化命题存在量化命题2022-7-62022-7-6计算机学院计算机学院3636/70/70例例1.4 (1.4 (续续2)2)n 在例在例1.41.4中，利用量词则有：中，利用量词则有： ( ( x)R(xx)R(x) )(x(x 老虎老虎) ( ( x)P(xx)P(x) ) (x (x 人人) ( ( x)N(xx)N(x) )(x(x 人人) ( ( x)Q(xx)Q(x) )(x(x 人人) ( (

47、 x)C(xx)C(x) )(x(x 带伞的人带伞的人) ( ( x)S(xx)S(x) )(x(x 自然数自然数)n 前面苏格拉底三段论中的前面苏格拉底三段论中的P P也可表示为：也可表示为：( ( x)(H(x)D(xx)(H(x)D(x)。2022-7-62022-7-6计算机学院计算机学院3737/70/70例例1.4 (1.4 (续续2)2)n 在例1.4中，利用量词则有： (x)R(x)(x老虎) (x)P(x) (x人) (x)N(x)(x人) (x)Q(x)(x人) (x)C(x)(x带伞的人) (x)S(x)(x自然数)n 前面苏格拉底三段论中的前面苏格拉底三段论中的P P也

48、可表示为：也可表示为：( ( x)(H(x)D(xx)(H(x)D(x)。2022-7-62022-7-6计算机学院计算机学院3838/70/70不便之处不便之处n 1)1)从书写上十分不便，总要特别注明个体域。从书写上十分不便，总要特别注明个体域。 2)2)在同一个比较复杂的句子中，对于不同命题函数中在同一个比较复杂的句子中，对于不同命题函数中的个体可能属于不同的个体域，此时无法清晰表达。的个体可能属于不同的个体域，此时无法清晰表达。 3)3)有时，由于个体域的注明不清楚，造成无法确定其有时，由于个体域的注明不清楚，造成无法确定其真值。对于同一个公式，不同的个体域有可能带来不真值。对于同一个

49、公式，不同的个体域有可能带来不同的真值。同的真值。n 如如( ( x)x)(x(x6 65):5):1 1）在实数范围内时，确有）在实数范围内时，确有x x-1-1使得使得x x6 65 5， 因此，因此，( ( x)x)(x(x6 65)5)为为“真真”。2 2）在正整数范围内时，则找不到任何）在正整数范围内时，则找不到任何x x，使得，使得 x x6 65 5为为“真真”，所以，所以，( ( x)x)(x(x6 65)5)为为“假假”。2022-7-62022-7-6计算机学院计算机学院3939/70/70不便之处不便之处n 1)1)从书写上十分不便，总要特别注明个体域。 2)2)在同一个

50、比较复杂的句子中，对于不同命题函数中的个体可能属于不同的个体域，此时无法清晰表达。 3)3)有时，由于个体域的注明不清楚，造成无法确定其真值。对于同一个公式，不同的个体域有可能带来不同的真值。n 如如( ( x)x)(x(x6 65):5):1 1）在实数范围内时，确有在实数范围内时，确有x x-1-1使得使得x x6 65 5， 因此，因此，( ( x)x)(x(x6 65)5)为为“真真”。2 2）在正整数范围内时，则找不到任何在正整数范围内时，则找不到任何x x，使得，使得 x x6 65 5为为“真真”，所以，所以，( ( x)x)(x(x6 65)5)为为“假假”。2022-7-62

51、022-7-6计算机学院计算机学院4040/70/70三、全总个体域三、全总个体域n 基于上述情况，有必要对个体域进行统一，全部使用基于上述情况，有必要对个体域进行统一，全部使用全总个体域，此时，对每一个句子中客体变量的变化全总个体域，此时，对每一个句子中客体变量的变化范围用一定的范围用一定的特性谓词特性谓词刻划之。而统一成刻划之。而统一成全总个体域全总个体域后，此全总个体域在谓词公式中就不必特别说明，常后，此全总个体域在谓词公式中就不必特别说明，常常省略不记。常省略不记。n 同时，这种特性谓词在加入到命题函数中时必定遵循同时，这种特性谓词在加入到命题函数中时必定遵循如下原则：如下原则： 1

52、1）对于全称量词，刻划其对应个体域的特性谓词作为）对于全称量词，刻划其对应个体域的特性谓词作为蕴涵的前件加入。蕴涵的前件加入。 2 2）对于存在量词，刻划其对应个体域的特性谓词作为）对于存在量词，刻划其对应个体域的特性谓词作为合取式之合取项加入。合取式之合取项加入。2022-7-62022-7-6计算机学院计算机学院4141/70/70三、全总个体域三、全总个体域n 基于上述情况，有必要对个体域进行统一，全部使用全总个体域，此时，对每一个句子中客体变量的变化范围用一定的特性谓词刻划之。而统一成全总个体域后，此全总个体域在谓词公式中就不必特别说明，常常省略不记。n 同时，这种特性谓词在加入到命题

53、函数中时必定遵循同时，这种特性谓词在加入到命题函数中时必定遵循如下如下原则原则： 1 1）对于全称量词，刻划其对应个体域的特性谓词作为对于全称量词，刻划其对应个体域的特性谓词作为蕴涵的前件加入蕴涵的前件加入。(P29)(P29) 2 2）对于存在量词，刻划其对应个体域的特性谓词作为对于存在量词，刻划其对应个体域的特性谓词作为合取式之合取项加入合取式之合取项加入。(P29)(P29)2022-7-62022-7-6计算机学院计算机学院4242/70/70例例1.4 (1.4 (续续3)3)n 对于例对于例1 14 4 中的例子运用特性谓词描述。中的例子运用特性谓词描述。解：解：1)1) U(x)

54、U(x)：x x是老虎；是老虎；( ( x x) )( (U(x)R(x)U(x)R(x)2)2) H(x)H(x)：x x是人；是人； ( ( x x) )(H(x)P(x)(H(x)P(x) )3)3) H(x)H(x)：x x是人；是人； ( ( x)x)( (H(x)H(x)N(x)N(x)4)4) H(x)H(x)：x x是人；是人；( ( x)x)( (H(x)H(x)Q(x)Q(x)5)5) M(x)M(x)：x x是带伞的人；是带伞的人； ( ( x x) )( (M(x)C(xM(x)C(x)6)6) T(x)T(x)：x x是自然数；是自然数；( ( x)(x)(T(x)T

55、(x)S(x)S(x)n苏格拉底三段论可完整翻译为：苏格拉底三段论可完整翻译为： ( ( x x) )(H(x(H(x)D(xD(x)，H(S)H(S)D(S)D(S) ( ( x x) )(H(x(H(x)D(xD(x)( ( x)x)( (H H( ()D(D()2022-7-62022-7-6计算机学院计算机学院4343/70/70例例1.4 (1.4 (续续3)3)n 对于例14 中的例子运用特性谓词描述。解：1) U(x)：x是老虎；(x)(U(x)R(x)2) H(x)：x是人； (x)(H(x)P(x)3) H(x)：x是人； (x)(H(x)N(x)4) H(x)：x是人；(x

56、)(H(x)Q(x)5) M(x)：x是带伞的人； (x)(M(x)C(x)6) T(x)：x是自然数；(x)(T(x)S(x)n苏格拉底苏格拉底三段论可完整翻译为：三段论可完整翻译为： ( ( x x) )(H(x(H(x)D(xD(x)，H(S)H(S)D(S)D(S) ( ( x x) )( (H(xH(x)D(xD(x) ) )( ( x)x)( (H H( ()D(D() ) )2022-7-62022-7-6计算机学院计算机学院4444/70/70例例1.5:1.5:n 符号化下述语句符号化下述语句：1)1) 天下乌鸦一般黑；天下乌鸦一般黑；2)2) 那位身体强健的、用功的、肯于思

57、考的大学那位身体强健的、用功的、肯于思考的大学生，解决了一个数学难题；生，解决了一个数学难题；3)3) 张强和李平都是足球运动员；张强和李平都是足球运动员；4)4) 每个实数都存在比它大的另外的实数。每个实数都存在比它大的另外的实数。5)5) 并非所有的动物都是脊椎动物；并非所有的动物都是脊椎动物；6)6) 尽管有人很聪明，但未必一切人都聪明；尽管有人很聪明，但未必一切人都聪明；7)7) 对于任意给定的对于任意给定的 00，必存在着，必存在着 00，使得对，使得对任意的任意的x x，只要，只要|x-a|x-a| ，就有：，就有： |f(x)-f(a)|f(x)-f(a)|0)(0)()()(

58、0)0) (|x-a| (|x-a| )(|f(x)-f(a)(|f(x)-f(a)|)|0)(0)() )( ( ( 0)0) ( (|x-a|(|x-a| )(|f(x)-f(a)(|f(x)-f(a)|)| ) ) ) ) )2022-7-62022-7-6计算机学院计算机学院5252/70/70四、自由变元与约束变元四、自由变元与约束变元n 定义定义2.32.3：在表达式在表达式 xA(xxA(x) )或或 xA(xxA(x) )中，中，x x称为称为指导指导（作用）变元（作用）变元，A(xA(x) )称为相应量词的称为相应量词的辖域（作用域）辖域（作用域）。在辖域中在辖域中x x的所

59、有出现称为的所有出现称为x x在公式在公式A A中的约束出现，中的约束出现， 此时的变元此时的变元x x称为称为约束变元约束变元。 A A中不是约束出现的其它中不是约束出现的其它变元称为变元称为自由变元自由变元。n 例例1.61.6： a a） x(P(x)Q(x):x(P(x)Q(x): x x的辖域为的辖域为P P（x x）Q(x),xQ(x),x为约为约 束变元。束变元。 b b） xP(x)Q(x):xP(x)Q(x): x x的辖域为的辖域为P(x),xP(x),x为约束出现，为约束出现， Q(xQ(x) )中的中的x x为自由出现。为自由出现。2022-7-62022-7-6计算机

60、学院计算机学院5353/70/70四、自由变元与约束变元四、自由变元与约束变元n 定义2.3：在表达式xA(x)或xA(x)中，x称为指导（作用）变元，A(x)称为相应量词的辖域（作用域）。在辖域中x的所有出现称为x在公式A中的约束出现， 此时的变元x称为约束变元。 A中不是约束出现的其它变元称为自由变元。n 例例1.61.6： a a） x x( (P(x)Q(x)P(x)Q(x) ): : x x的辖域为的辖域为P P（x x）Q(x),xQ(x),x为约为约 束变元。束变元。 b b） xP(x)Q(x):xP(x)Q(x): x x的辖域为的辖域为P(x),xP(x),x为约束出现，为