谓词逻辑(PredicateLogic).ppt

第二章 谓词逻辑Predicate Logic前言苏格拉底三段论(Socrates syllogism)：所有人都是要死的。所有人都是要死的。苏格拉底是人。苏格拉底是人。所以苏格拉底是要死的。所以苏格拉底是要死的。（Socrates,古古希希腊腊哲哲学学家家,公公元元前前470前前399）(孔子孔子,中国伟大哲学家中国伟大哲学家,公元前公元前551前前479)前言在命题逻辑中，如果设：P：凡人都是要死的；Q：苏格拉底是人；R：苏格拉底是要死的。前提：P,Q，结论：R。则(PQ)R表示上述推理，这个命题公式不是重言式。前言在谓词逻辑中，如果在谓词逻辑中，如果设：设：H(x)：x是人。是人。M(x)：x是要死的。是要死的。a：苏格拉底。苏格拉底。前提：前提：(x)(H(x)M(x)，H(a)结论：结论：M(a)(x)(H(x)M(x)H(a)M(a)前言 主语主语 谓语谓语 客（个）体客（个）体 谓词谓词客体客体可以独立存在，它可以是具体的，也可可以独立存在，它可以是具体的，也可以是抽象的。以是抽象的。而用来描述客体的性质或关系的即是而用来描述客体的性质或关系的即是谓词谓词。为了刻画命题内部的逻辑结构，就需要研究为了刻画命题内部的逻辑结构，就需要研究谓词逻辑（谓词逻辑（Predicate Logic）。）。前言比如：比如：P：张三是大学生：张三是大学生Q：李四是大学生：李四是大学生以以上上这这些些命命题题都都具具备备有有一一个个共共同同的的特特征征就就是是：x是大学生。是大学生。P(x)就可以代表这一类的命题。就可以代表这一类的命题。P(x)：x是大学生，是大学生，a：张三，：张三，b：李四，：李四，P(a)：张三是大学生：张三是大学生P(b)：李四是大学生：李四是大学生2-1 谓词的概念与表示2-1.1 谓词的概念谓词的概念定义定义1：谓词（：谓词（predicate）在在命命题题中中，用用以以刻刻画画客客体体词词的的性性质质或或客客体体词词之之间间关关系系的词即是谓词，谓词相当于命题中的谓语部分。的词即是谓词，谓词相当于命题中的谓语部分。例如：例如：(1)他是三好学生他是三好学生(2)“他他”是是个个体体，“是是三三好好学学生生”是是表表示示个个体体性性质质的谓词的谓词(2)5大于大于3(3)“5”和和“3”是是个个体体，“大大于于”是是表表示示个个体体之之间间关关系的谓词系的谓词2-1.2 谓词的表示：用用大大写写英英文文字字母母 A,B,C,D,表表示示谓谓词词，用小写字母表示客体。用小写字母表示客体。前面的例子可表示为：前面的例子可表示为：(1)A(x):x是三好学生，是三好学生，h:他，他，A(h):他是三好学生他是三好学生(2)G(x,y):x大于大于y，G(5,3):5大于大于32-1.3如何利用谓词表达命题：用用谓谓词词表表达达命命题题必必须须包包括括谓谓词词字字母母和和客客体体两个部分。比如：两个部分。比如：A(x)可可以以表表示示“x是是A”类类型型的的命命题题，表表达达了了客体的性质，称为一元谓词客体的性质，称为一元谓词。B(x,y)可可以以表表示示“x小小于于y”类类型型的的命命题题，表表达了客体之间的关系，称为二元谓词，达了客体之间的关系，称为二元谓词，。L(x,y,z)可可以以表表示示“点点x在在y与与z之之间间”类类型型的的命命题题，表表达达了了客客体体之之间间的的关关系系，称称为为三三元元谓谓词。词。用用P(x1,x2,xn)表表示示n元元谓谓词词，在在这这里里n个客体变元的顺序不能随意改动。个客体变元的顺序不能随意改动。2-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.1 命题函数定义定义1：简单命题函数：简单命题函数(simple propositional function)：由由一一个个谓谓词词，一一些些客客体体变变元元组组成成的的表表达达式式称称为为简简单单命命题题函函数数。比比如如：A(x)，B(x,y)，L(x,y,z)简简单单命命题题函函数数不不是是命命题题，只只有有当当变变元元x,y,z等等取特定的客体才确定了一个命题。取特定的客体才确定了一个命题。对对于于n元元谓谓词词，当当n=0时时，称称为为0元元谓谓词词，它它本本身身就就是是一一个个命命题题，故故命命题题是是n元元谓谓词词的的一一个特殊情况。个特殊情况。2-2.1 命题函数比比如如：L(x,y)表表示示“x小小于于y”是是二二元元谓谓词词，L(x,3)表表示示“x小小于于3”是是一一元元谓谓词词，L(2,3)表表示示“2小于小于3”是是0元谓词。元谓词。因因此此可可以以将将命命题题看看成成n元元谓谓词词的的一一个个特特殊殊情况。情况。0元元谓谓词词都都是是命命题题，命命题题逻逻辑辑中中的的简简单单命题都可以用命题都可以用0元谓词表示。元谓词表示。2-2.1 命题函数定定义义2：复复合合命命题题函函数数（compound propositional function）：）：由由一一个个或或n个个简简单单命命题题函函数数以以及及逻逻辑辑联联结词组合而成的表达式。结词组合而成的表达式。命命题题逻逻辑辑中中的的联联结结词词在在谓谓词词逻逻辑辑中中含含义完全相同。义完全相同。举例说明：举例说明：P56例，例例，例2-2.1 命题函数定义定义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 命题函数定义定义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)注注意意：命命题题函函数数不不是是一一个个命命题题，只只有有客客体体变变元元取取特特定定客客体体时时，才才能能成成为为一一个个命命题题。但但是是客客体体变变元元在在哪哪些些范范围围取取特特定定的的值值，对对命命题函数以下两方面有极大影响：题函数以下两方面有极大影响：(1)命题函数是否能成为一个命题；命题函数是否能成为一个命题；(2)命题的真值是真还是假。命题的真值是真还是假。2-2.1 命题函数个体域个体域(universe of discourse)：在在命命题题函函数数中中，命命题题变变元元的的论论述述范范围围称称为个体域。为个体域。全总个体域：全总个体域：个个体体域域可可以以是是有有限限的的，也也可可以以是是无无限限的的，把把各各种种个个体体域域综综合合在在一一起起，作作为为论论述述范范围围的的域，称为全总个体域。域，称为全总个体域。2-2.2 量词例题：例题：符号化以下命题符号化以下命题(1)所有人都要死去。所有人都要死去。(2)有的人的年龄超过百岁。有的人的年龄超过百岁。以以上上给给出出的的命命题题，除除了了有有个个体体词词和和谓谓词词以以外外，还还有有表表示示数数量量的的词词，称称表表示示数数量量的的词词为量词。量词有两种：为量词。量词有两种：全称量词全称量词(universal quantifier)存在量词存在量词(existential quantifier)2-2.2 量词定义定义1全称量词全称量词(universal quantifier)用用符符号号“”表表示示，“x”表表示示对对个个体体域域里里的的所所有有个体。个体。(x)P(x)表示对个体域里的所有个体都有属性表示对个体域里的所有个体都有属性P。表表达达“对对所所有有的的”，“每每一一个个”，“对对任任一一个个”，“凡凡”，“一切一切”等词。等词。The universal quantifier ,an upside-down A,is used to build compound propositions of the form(x)P(x),which we read as“for all x,P(x).”Other translations of are“for each,”“for every,”“for any.”The compound proposition(x)P(x)is assigned truth value as follows:(x)P(x)is true if P(x)is true for every x in U;otherwise(x)P(x)is false.2-2.2 量词定义2存在量词(existential quantifier)用符号“”表示。x表示存在个体域里的个体。(x)P(x)表示存在个体域里的个体具有性质P。符号“”称为存在量词，用以表达“某个”，“存在一些”，“至少有一个”，“对于一些”等词。The existential quantifier,a backward E is used to form propositions like（x）P(x),which we read as“there exists an x such that P(x),”“there is an x such that P(x),”or“for some x,P(x).”The compound proposition（x）P(x)has these truth values:（x）P(x)is true if P(x)is true for at least one x in U;（x）P(x)is false if P(x)is false for every x in U.2-2.2 量词唯一存在量词（唯一存在量词（unique quantifier）：）：“恰好存在一个恰好存在一个”，用符号，用符号“!”表示。表示。2-2.2 量词现现在在对对以以上上两两个个命命题题进进行行符符号号化化，在在进进行行符符号化之前必须确定个体域。号化之前必须确定个体域。第一种情况第一种情况个体域个体域D为人类集合。为人类集合。设：设：F(x)：x是要死的。是要死的。G(x)：x活百岁以上。活百岁以上。则有则有(x)F(x)和和 (x)G(x)这两个命题都是真命题这两个命题都是真命题2-2.2 量词 第二种情况第二种情况个体域个体域D为全总个体域。为全总个体域。不不能能符符号号化化为为(x)F(x)和和(x)G(x)，因为，因为:(x)F(x)表表示示宇宇宙宙间间一一切切事事物物都都要要死死的，这与原命题不符。的，这与原命题不符。(x)G(x)表表示示宇宇宙宙间间一一切切事事物物中中存存在在百岁以上，这与原命题不符。百岁以上，这与原命题不符。2-2.2 量词因因此此必必须须引引入入一一个个新新的的谓谓词词，将将人人分分离离出出来来。在在全全总总个个体体域域的的情情况况下下，以以上上两两个个命命题叙述如下：题叙述如下：(1)对对于于所所有有个个体体而而言言，如如果果它它是是人人，则则它要死去。它要死去。(2)存存在在着着个个体体，它它是是人人并并且且活活过过百百岁岁以以上。上。于于是是，再再符符号号化化时时必必须须引引入入一一个个新新的的谓谓词词 M(x)：x是人。是人。称这个谓词为称这个谓词为特性谓词特性谓词。2-2.2 量词定义：特性谓词定义：特性谓词在在讨讨论论带带有有量量词词的的命命题题函函数数时时，必必须须确确定定其其个个体体域域，为为了了方方便便，可可使使用用全全总总个个体体域域。限限定定客客体体变变元元变变化化范范围围的的谓谓词词，称称作作特特性性谓谓词。词。利利用用特特性性谓谓词词，对对以以上上两两个个命命题题进进行行符符号化号化(1)(x)(M(x)F(x)(2)(x)(M(x)G(x)使用量词时应注意的问题：(1)在在讨讨论论有有量量词词的的命命题题函函数数时时如如果果事事先先没没有有给给出出个个体体域域，那那么么都都应应以以全全总总个个体体域域为为个个体域。体域。(2)对对全全称称量量词词，特特性性谓谓词词常常做做蕴蕴含含的的前前件件。对存在量词，特性谓词常做合取项。对存在量词，特性谓词常做合取项。举例说明：举例说明：例例1“有些人是要死的有些人是要死的”.解解1：采用全体人作为个体域采用全体人作为个体域.设设:G(x):x是要死的是要死的.原命题符号化成原命题符号化成:(x)G(x)解解2：采用全总个体域采用全总个体域.设设:M(x):x是人是人;G(x):x是要死的是要死的.原命题符号化成原命题符号化成:(x)(M(x)G(x)例2“凡人都是要死的”.解1:采用全体人作为个体域.设:G(x):x是要死的.原命题符号化成:(x)G(x)解2:采用全总个体域.设:M(x):x是人;G(x):x是要死的.原命题符号化成:(x)(M(x)G(x)例例3:“存在最小的自然数存在最小的自然数”。解解1:采用全体自然数作为个体域采用全体自然数作为个体域.设设:G(x,y):xy;原命题符号化成原命题符号化成:(x)(y)G(x,y)注意量词顺序注意量词顺序:(y)(x)G(x,y):“没有最小的自然数没有最小的自然数”.解解2:设设:F(x):x是自然数是自然数;G(x,y):xy;原命题符号化成原命题符号化成:(x)(F(x)(y)(F(y)G(x,y)例例4:“不存在最大的自然数不存在最大的自然数”。解解:设设:F(x):x是自然数是自然数;G(x,y):xy;原命题符号化成原命题符号化成:(x)(F(x)(y)(F(y)G(x,y)或或:(x)(F(x)(y)(F(y)G(x,y)例例5:“火车比汽车快火车比汽车快”。解解:设设:F(x):x是火车是火车;G(x):x是汽车是汽车;H(x,y):x比比y快快原命题符号化成原命题符号化成:(x)(F(x)(y)(G(y)H(x,y)或或:(x)(y)(F(x)G(y)H(x,y)例例6:“有的汽车比火车快有的汽车比火车快”。解解:设设:F(x):x是汽车是汽车;G(x):x是火车是火车;H(x,y):x比比y快快原命题符号化成原命题符号化成:(x)(F(x)(y)(G(y)H(x,y)或或:(x)(y)(F(x)G(y)H(x,y)例例7:“有些病人相信所有的医生有些病人相信所有的医生”。解解:设设:F(x):x是病人是病人;G(x):x是医生是医生;H(x,y):x相信相信y原命题符号化成原命题符号化成:(x)(F(x)(y)(G(y)H(x,y)例例8:“存在唯一的对象满足性质存在唯一的对象满足性质P”。解解:设设:P(x):x满足性质满足性质P原命题符号化成原命题符号化成:(!x)P(x)或或:设设:P(x):x满足性质满足性质P;E(x,y):x和和y是同一个个体是同一个个体原命题符号化成原命题符号化成:(x)(P(x)(y)(P(y)E(x,y)2-3 谓词公式与翻译书上已经给出谓词，命题函数，谓词表达式。在数理逻辑中需要对能够进行谓词演算的公式进行准确的定义。这样以后我们不再说谓词，命题函数，谓词表达式等,而只研究谓词公式。2-3.1 谓词逻辑字母表：个体常项:a,b,c,a1,b1,c1,个体变项:x,y,z,x1,y1,z1,函数符号:f,g,h,f1,g1,h1,谓词符号:F,G,H,F1,G1,H1,量词符号:,!联结词符号:,括号与逗号:(,),，2-3.2 谓词公式定定义义：谓谓词词公公式式（谓谓词词演演算算的的合合式式公公式式）用用wff表示（表示（well form formulation)（1）A(x1,x2,xn)称称为为原原子子谓谓词词公公式式，原原子子谓词公式是谓词公式。谓词公式是谓词公式。（2）若）若A是谓词公式，则是谓词公式，则(A)是一个谓词公式。是一个谓词公式。（3）若若A和和B都都是是谓谓词词公公式式，则则(AB)，(AB)，(AB)，(AB)和都是谓词公式。和都是谓词公式。（4）如如果果A是是谓谓词词公公式式，x是是A中中出出现现的的任任何何变变元，则元，则(x)A，(x)A，和，和(!x)A都是谓词公式。都是谓词公式。（5）只只有有经经过过有有限限次次的的应应用用规规则则(1)，(2)，(3)，(4)所得到的公式是谓词公式。所得到的公式是谓词公式。2-3.2 谓词公式举例说明：举例说明：以下都是谓词公式以下都是谓词公式 x(F(x)y(G(y)H(x,y)F(f(a,a),b)2-3.3 翻译见P61 例1作业(2-1,2-2,2-3)P60(2)a),c),e)P62(3)b),c)