离散数学左孝凌-课件

第二章第二章 谓词逻辑谓词逻辑（Predicate Logic）2-1谓词的概念与表示谓词的概念与表示2-2 命题函数与量词命题函数与量词2-3谓词公式与翻译谓词公式与翻译2-4变元的约束变元的约束2-5谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式2-7前束范式前束范式2-7谓词演算的推理理论谓词演算的推理理论计算机学院计算机学院第二章 谓词逻辑（Predicate Logic）2-1第二章第二章 谓词逻辑谓词逻辑（Predicate Logic）2-1 2-1 谓词的概念与表示谓词的概念与表示(Predicate and Its Expression)Predicate and Its Expression)n命题逻辑的局限性命题逻辑的局限性：在命题逻辑中，命题是命题演算的基本在命题逻辑中，命题是命题演算的基本单位，不再对原子命题进行分解，因而无法单位，不再对原子命题进行分解，因而无法研究命题的内部结构、成分及命题之间的内研究命题的内部结构、成分及命题之间的内在联系，甚至无法处理一些简单而又常见的在联系，甚至无法处理一些简单而又常见的推理过程。推理过程。计算机学院计算机学院第二章 谓词逻辑（Predicate Logic）2n例如，下列推理：例如，下列推理：所有的人都是要死的。所有的人都是要死的。苏格拉底是人。苏格拉底是人。苏格拉底是要死的。苏格拉底是要死的。众所周知众所周知,这是真命题。但在命题逻辑中这是真命题。但在命题逻辑中,如如果用果用P,Q,R表示以上三个命题，则上述推理过表示以上三个命题，则上述推理过程为：（程为：（PQ）R。借助命题演算的推理理。借助命题演算的推理理论不能论不能证明其为重言式证明其为重言式。第二章第二章 谓词逻辑谓词逻辑（Predicate Logic）2-1 2-1 谓词的概念与表示谓词的概念与表示(Predicate and Its Expression)Predicate and Its Expression)计算机学院计算机学院例如，下列推理：第二章 谓词逻辑（Predicat第二章第二章 谓词逻辑谓词逻辑（Predicate Logic）2-1 2-1 谓词的概念与表示谓词的概念与表示(Predicate and Its Expression)Predicate and Its Expression)原因：原因：命题逻辑不能将命题之间的内在联系命题逻辑不能将命题之间的内在联系和数量关系反映出来。和数量关系反映出来。解决办法：解决办法：将命题进行分解。将命题进行分解。计算机学院计算机学院第二章 谓词逻辑（Predicate Logic）2第二章第二章 谓词逻辑谓词逻辑（Predicate Logic）2.1 2.1 谓词的概念与表示谓词的概念与表示(Predicate and Its Expression)Predicate and Its Expression)2-1谓谓 词词 的的 概概 念念 与与 表表 示示(Predicate and its expression)2-1.1 客体客体和和谓词谓词 在谓词逻辑中，可将在谓词逻辑中，可将原子命题原子命题划分为划分为客体客体和和谓词谓词两部分。两部分。客体客体：可以独立存在的具体事物的或抽象的概：可以独立存在的具体事物的或抽象的概念。念。例例如，电子计算机、李明、玫瑰花、黑如，电子计算机、李明、玫瑰花、黑板、实数、中国、思想、唯物主义等，客体也板、实数、中国、思想、唯物主义等，客体也可称之为可称之为主语主语。计算机学院计算机学院第二章 谓词逻辑（Predicate Logic）2第二章第二章 谓词逻辑谓词逻辑（Predicate Logic）2-1 2-1 谓词的概念与表示谓词的概念与表示(Predicate and Its Expression)Predicate and Its Expression)谓词：谓词：用来刻划客体的性质或客体之间的相互关系的词。用来刻划客体的性质或客体之间的相互关系的词。例如在下面命题中：例如在下面命题中：（1）张明是个劳动模范。）张明是个劳动模范。（2）李华是个劳动模范。）李华是个劳动模范。刻划客体的性质刻划客体的性质 （3）王红王红是个大学生。是个大学生。（4）小李比小赵高小李比小赵高2cm。（5）点）点a在在b与与c之间。之间。刻划客体之间的相互关系刻划客体之间的相互关系 （6）阿杜与阿寺同岁。阿杜与阿寺同岁。“是是个个劳劳动动模模范范”、“是是个个大大学学生生”、“比比高高2cm”、“在在与与之间之间”都是都是谓词。谓词。计算机学院计算机学院第二章 谓词逻辑（Predicate Logic）2第二章第二章 谓词逻辑谓词逻辑（Predicate Logic）2-1 2-1 谓词的概念与表示谓词的概念与表示(Predicate and Its Expression)Predicate and Its Expression)n刻刻划划一一个个客客体体性性质质的的词词称称之之为为一一元元谓谓词词,刻刻划划n个个客客体体之之间关系间关系的词称之为的词称之为n元谓词元谓词.n一般我们用大写英文字母表示一般我们用大写英文字母表示谓词，谓词，用小写英文字母用小写英文字母表示客体名称，例如，表示客体名称，例如，将上述谓词分别记作大写字母将上述谓词分别记作大写字母F、G、H、R，S则上述命题可表示为：则上述命题可表示为：(1)F(a)a：张明张明 (2)F(b)b：李华李华 (3)G(c)c：王红王红 (4)H(s,t)s：小李小李 t：小赵：小赵 (5)R(a,b,c)(6)S(a,b)a:阿杜。阿杜。b:阿寺。阿寺。其中其中(1)、(2)、(3)为一元谓词，为一元谓词，(4)、(6)为二元谓词，为二元谓词，(5)为三元谓词。为三元谓词。计算机学院计算机学院第二章 谓词逻辑（Predicate Logic）2第二章第二章 谓词逻辑谓词逻辑（Predicate Logic）2-1 2-1 谓词的概念与表示谓词的概念与表示(Predicate and Its Expression)Predicate and Its Expression)n注注:n(1)单独一个谓词并不是命题，在谓词字母单独一个谓词并不是命题，在谓词字母后填上客体所得到的式子称之为谓词填式。后填上客体所得到的式子称之为谓词填式。n(2)在谓词填式中，若客体确定，则在谓词填式中，若客体确定，则A(a1，a2.an)就变成了命题就变成了命题 n(3)在多元谓词表达式中，客体字母出现的在多元谓词表达式中，客体字母出现的先后次序与事先约定有关先后次序与事先约定有关,一般不可以随意交一般不可以随意交换位置换位置(如如,上例中上例中H(s,t)与与H(t,s)代表两个不代表两个不同的命题同的命题)。计算机学院计算机学院第二章 谓词逻辑（Predicate Logic）2第二章第二章 谓词逻辑谓词逻辑（Predicate Logic）2-1 2-1 谓词的概念与表示谓词的概念与表示(Predicate and Its Expression)Predicate and Its Expression)n设设谓谓词词H表表示示“是是劳劳动动模模范范”,a表表示示客客体体名名称称张张明明,b表表示示客客体体名名称称李李华华,c表表示示客客体体名名称称这这只只老老虎虎，那那么么H(a)、H(b)、H(c)表表示示三三个个不不同同的的命命题题,但但它它们们有有一一个个共共同同的的形形式式,即即H(x).一一般般地地，H(x)表表示示客客体体x具具有有性性质质H。这这里里x表表示示抽抽象象的的或或泛泛指指的的客客体体，称称为为客客体体变变元元，常常用用小小写写英英文文字字母母x,y,z,表表示示。相相应应地地，表表示示具具体体或或特特定定的的客客体体的的词词称称为为客体常项客体常项，常用小写英文字母，常用小写英文字母a,b,c,表示。表示。计算机学院计算机学院第二章 谓词逻辑（Predicate Logic）2-1-1 谓词的概念与表示谓词的概念与表示(Predicate and Its Expression)Predicate and Its Expression)同理，客体变元同理，客体变元x，y具有关系具有关系L，记作，记作L(x,y);客体变元客体变元x,y,z具有关系具有关系A，记作，记作A(x,y,z).nH(x)、L(x,y)、A(x,y,z)本身并不是一个命题本身并不是一个命题.只只有用特定的客体取代客体变元有用特定的客体取代客体变元x,y,z后，它们才成为后，它们才成为命题。命题。计算机学院计算机学院2-1 谓词的概念与表示(Predicate and I2-2 命题函数与量词2-2.1 命题函数命题函数一一般般来来说说，当当谓谓词词P给给定定，x1,x2,xn是是客客体体变变元元，P(x1,x2,xn)不不是是一一个个命命题题，因因为为他他的的真真值值无无法法确确定定，要要想想使使它它成成为为命命题题，要要用用n个个客客体体常常项项代代替替n个个客客体体变元。变元。P(x1,x2,xn)就是就是命题函数命题函数。比比如如L(x,y)表表示示“x小小于于y”，那那么么L(2,3)表表示示了了一一个个真真命命题题“2小小于于3”。而而 L(5,1)表表示示了了一一个个假假命命题题“5小于小于1”计算机学院计算机学院2-2 命题函数与量词2-2.1 命题函数计算机学院2-2.1 命题函数定义定义2-2.1：简单命题函数简单命题函数(simple propositional function)：由由一一个个谓谓词词，一一些些客客体体变变元元组组成成的的表表达达式式称称为为简单命题函数简单命题函数。比如：比如：A(x)，B(x,y)，L(x,y,z)简简单单命命题题函函数数不不是是命命题题，只只有有当当变变元元x,y,z等等取取特定的客体才确定了一个命题。特定的客体才确定了一个命题。对对于于n元元谓谓词词，当当n=0时时，称称为为0元元谓谓词词，它它本本身身就就是是一一个个命命题题，故故命命题题是是n元元谓谓词词的的一一个个特特殊殊情况。情况。计算机学院计算机学院2-2.1 命题函数定义2-2.1：简单命题函数(simpl2-2.1 命题函数比比如如：L(x,y)表表示示“x小小于于y”是是二二元元谓谓词词，L(x,3)表表示示“x小小于于3”是是一一元元谓谓词词，L(2,3)表表示示“2小于小于3”是是0元谓词。元谓词。因因此此可可以以将将命命题题看看成成n元元谓谓词词的的一一个个特特殊殊情情况。况。0元元谓谓词词都都是是命命题题，命命题题逻逻辑辑中中的的简简单单命命题题都可以用都可以用0元谓词表示。元谓词表示。计算机学院计算机学院2-2.1 命题函数比如：L(x,y)表示“x小于y”是二2-2.1 命题函数定定义义2-2.2：复复合合命命题题函函数数（compound propositional function）：）：由由一一个个或或n个个简简单单命命题题函函数数以以及及逻逻辑辑联联结结词组合而成的表达式。词组合而成的表达式。命命题题逻逻辑辑中中的的联联结结词词在在谓谓词词逻逻辑辑中中含含义义完完全相同。全相同。举例说明：举例说明：P56例，例例，例计算机学院计算机学院2-2.1 命题函数定义2-2.2：复合命题函数（comp2-2.1 命题函数定义定义2-2.3：谓词填式谓词填式单单独独一一个个谓谓词词不不是是完完整整的的命命题题，把把谓谓词词字字母以客体填后所得的式子称为谓词填式。母以客体填后所得的式子称为谓词填式。例例如如：P(x)表表示示x3，则则P(1)、P(2)、P(5)分分别别表表示示1大大于于3，2大大于于3，5大大于于3，P(1)、P(2)、P(5)即是谓词填式。即是谓词填式。计算机学院计算机学院2-2.1 命题函数定义2-2.3：谓词填式计算机学院2-2.1 命题函数定义定义2-2.4：谓词表达式谓词表达式简单命题函数与逻辑联结词组合而成。简单命题函数与逻辑联结词组合而成。示例分析示例分析 P59(1)a),b),c)a)设设W(x):x是是工工人人，z:小小张张，则则原原命命题题表表示示为为：W(z)b)设设S(x):x是是田田径径运运动动员员，B(x):x是是球球类类运运动动员员，h:他，则原命题表示为：他，则原命题表示为：S(h)B(h)c)设设C(x):x是是聪聪明明的的，B(x):x是是美美丽丽的的，a:小小莉莉，则则原原命题表示为：命题表示为：C(a)B(a)计算机学院计算机学院2-2.1 命题函数定义2-2.4：谓词表达式计算机学院注注意意：命命题题函函数数不不是是一一个个命命题题，只只有有客客体体变变元元取取特特定定客客体体时时，才才能能成成为为一一个个命命题题。但但是是客客体体变变元元在在哪哪些些范范围围取取特特定定的的值值，对对命命题题函函数数以以下下两两方面有极大影响：方面有极大影响：(1)命题函数是否能成为一个命题；命题函数是否能成为一个命题；(2)命题的真值是真还是假。命题的真值是真还是假。2-2.1 命题函数计算机学院计算机学院注意：命题函数不是一个命题，只有客体变元取特定客体时，2-2.1 命题函数个体域个体域(universe of discourse)：在在命命题题函函数数中中，命命题题变变元元的的论论述述范范围围称称为为个个体域体域。全总个体域：全总个体域：个个体体域域可可以以是是有有限限的的，也也可可以以是是无无限限的的，把把各各种种个个体体域域综综合合在在一一起起，作作为为论论述述范范围围的的域域，称为称为全总个体域全总个体域。计算机学院计算机学院2-2.1 命题函数个体域(universe of dis2-2.2 量词例题：例题：符号化以下命题符号化以下命题(1)所有人都要死去。所有人都要死去。(2)有的人的年龄超过百岁。有的人的年龄超过百岁。以以上上给给出出的的命命题题，除除了了有有个个体体词词和和谓谓词词以以外外，还还有有表表示示数数量量的的词词，称称表表示示数数量量的的词词为为量量词词。量量词有两种：词有两种：全称量词全称量词(universal quantifier)存在量词存在量词(existential quantifier)计算机学院计算机学院2-2.2 量词例题：符号化以下命题计算机学院2-2.2 量词定义定义2-2.5全称量词全称量词(universal quantifier)用用符符号号“”表表示示，“x”表表示示对对个个体体域域里里的的所所有有个个体体。(x)P(x)表表示示对对个个体体域域里里的的所所有有个个体体都都有有属属性性P。表表达达“对对所所有有的的”，“每每一一个个”，“对对任任一一个个”，“凡凡”，“一切一切”等词。等词。定定 义义 2-2-7 存存 在在 量量 词词(existential quantifier)用用符符号号“”表表示示。x表表示示存存在在个个体体域域里里的的个个体体。(x)P(x)表表示示存存在在个个体体域域里里的的个个体体具具有有性性质质P。符符号号“”称称为为存存在在量量词词，用用以以表表达达“某某个个”，“存存在在一一些些”，“至至少少有有一一个个”，“对对于于一一些些”等词。等词。计算机学院计算机学院2-2.2 量词定义2-2.5全称量词(universal2-2.2 量词现现在在对对以以上上两两个个命命题题进进行行符符号号化化，在在进进行行符符号号化化之前必须确定个体域。之前必须确定个体域。第一种情况第一种情况个体域个体域D为人类集合。为人类集合。设：设：F(x)：x是要死的。是要死的。G(x)：x活百岁以上。活百岁以上。则有则有(x)F(x)和和 (x)G(x)这两个命题都是真命题这两个命题都是真命题计算机学院计算机学院2-2.2 量词现在对以上两个命题进行符号化，在进行符号化之2-2.2 量词 第二种情况第二种情况个体域个体域D为全总个体域。为全总个体域。不不能能符符号号化化为为(x)F(x)和和(x)G(x)，因为因为:(x)F(x)表表示示宇宇宙宙间间一一切切事事物物都都要要死死的的，这与原命题不符。这与原命题不符。(x)G(x)表表示示宇宇宙宙间间一一切切事事物物中中存存在在百百岁以上，这与原命题不符。岁以上，这与原命题不符。计算机学院计算机学院2-2.2 量词 第二种情况个体域D为全总个体域。计算机学2-2.2 量词因因此此必必须须引引入入一一个个新新的的谓谓词词，将将人人分分离离出出来来。在全总个体域的情况下，以上两个命题叙述如下：在全总个体域的情况下，以上两个命题叙述如下：(1)对对于于所所有有个个体体而而言言，如如果果它它是是人人，则则它它要死去。要死去。(2)存在着个体，它是人并且活过百岁以上。存在着个体，它是人并且活过百岁以上。于于是是，再再符符号号化化时时必必须须引引入入一一个个新新的的谓谓词词 M(x)：x是人。是人。称这个谓词为称这个谓词为特性谓词特性谓词。计算机学院计算机学院2-2.2 量词因此必须引入一个新的谓词，将人分离出来。在全2-2.2 量词定义：特性谓词定义：特性谓词在在讨讨论论带带有有量量词词的的命命题题函函数数时时，必必须须确确定定其其个个体体域域，为为了了方方便便，可可使使用用全全总总个个体体域域。限限定定客客体变元变化范围的谓词，称作特性谓词。体变元变化范围的谓词，称作特性谓词。利用特性谓词，对以上两个命题进行符号化利用特性谓词，对以上两个命题进行符号化(1)(x)(M(x)F(x)(2)(x)(M(x)G(x)计算机学院计算机学院2-2.2 量词定义：特性谓词计算机学院使用量词时应注意的问题：使用量词时应注意的问题：(1)在在讨讨论论有有量量词词的的命命题题函函数数时时如如果果事事先先没没有有给给出出个体域，那么都应以全总个体域为个体域。个体域，那么都应以全总个体域为个体域。(2)对对全全称称量量词词，特特性性谓谓词词常常做做蕴蕴含含的的前前件件。对对存存在量词，特性谓词常做合取项。在量词，特性谓词常做合取项。2-2.2 量词计算机学院计算机学院使用量词时应注意的问题：在讨论有量词的命题函数时如果事先没有举例说明：举例说明：例例1“有些人是要死的有些人是要死的”.解解1：采用全体人作为个体域采用全体人作为个体域.设设:G(x):x是要死的是要死的.原命题符号化成原命题符号化成:(x)G(x)解解2：采用全总个体域采用全总个体域.设设:M(x):x是人是人;G(x):x是要死的是要死的.原命题符号化成原命题符号化成:(x)(M(x)G(x)2-2.2 量词计算机学院计算机学院举例说明：例1“有些人是要死的”.2-2.2 量词计算机学例例2“凡人都是要死的凡人都是要死的”.解解1:采用全体人作为个体域采用全体人作为个体域.设设:G(x):x是要死的是要死的.原命题符号化成原命题符号化成:(x)G(x)解解2:采用全总个体域采用全总个体域.设设:M(x):x是人是人;G(x):x是要死的是要死的.原命题符号化成原命题符号化成:(x)(M(x)G(x)2-2.2 量词计算机学院计算机学院例2“凡人都是要死的”.2-2.2 量词计算机学院例例3:“存在最小的自然数存在最小的自然数”。解解1:采用全体自然数作为个体域采用全体自然数作为个体域.设设:G(x,y):xy;原命题符号化成原命题符号化成:(x)(y)G(x,y)注意量词顺序注意量词顺序:(y)(x)G(x,y):“没有最小的自然数没有最小的自然数”.解解2:设设:F(x):x是自然数是自然数;G(x,y):x(x)P(x)(x)Q(x)(附加前提法附加前提法)n证明：证明：(1)(x)P(x)P(附加前提附加前提)(2)(x)P(x)T(1)(3)P(c)ES(2)(4)x(P(x)Q(x)P (5)P(c)Q(c)US(4)计算机学院计算机学院第二章 谓词逻辑（Predicate Logic）2-第二章第二章 谓词逻辑谓词逻辑（Predicate Logic）2-7 谓词演算的推理理论谓词演算的推理理论n(6)Q(c)T(3)(5)n(7)(x)Q(x)EG(6)n(8)(x)P(x)(x)Q(x)CP小结：小结：本节介绍了谓词演算的推理规则本节介绍了谓词演算的推理规则,并举例说明了它并举例说明了它们的应用们的应用.重点重点:深刻理解四个推理规则深刻理解四个推理规则,会应用它们推会应用它们推理证明理证明.作业作业:P79(1)a)c)(2)a)(3)计算机学院计算机学院第二章 谓词逻辑（Predicate Logic）2-