离散数学谓词逻辑分解

第二章谓词逻辑杨圣洪引言命题逻辑好像功能强大，但还是有些问题难以解决。如杨圣洪要喝水、刘翔要喝水、姚明要喝水、姚晨要喝水、刘德华要喝水、……，可归纳为“某某要喝水”，无法表示。所有的人都要呼吸、喝水、吃饭……，“所有”如何表示呢？有些人要升官、有些人要失恋……，“有些”又如何表示？所有男人都会多看几眼漂亮女人所有女人都会多喜欢漂亮的衣服又如有名三段论：所有人都是要变老的，杨圣洪是人，所以杨圣洪也会变老的，无法表示。为此需要我们学习新的逻辑工具-谓词逻辑或一阶逻辑2.1基本概念1、谓词“某某要喝水”、“喜欢漂亮衣服”、“喜欢帅哥”、“结婚生崽”都是所在句子的谓语部分。命题逻辑中用大写字母表示命题。谓词逻辑中用大写字母表示谓语部分，如用W表示“要喝水”，用L表示“喜欢漂亮衣服”，用H表示“喜欢帅哥”，用M表示“结婚生崽”。这些表示谓语部分的大写字母，称为“谓词”。2.1基本概念2、个体常元表示某种判断的语句一般都有主语。主语是表示某个、某些客体，也称为个体。如“刘翔”、“姚明”。为了描述方便，常用小写字母表示这些个体。如a表示“刘翔”，c表示“姚明”，这些表示具体个体的小写字母，称为“个体常元”或个体常量。其他学科中，也是用字母表中靠前的字母表示常量。2.1基本概念3、个体变元对于不针对特定个体的泛指，如“某某”、“男人”、“女人”，常用x,y,z,r,s,t等字母表中靠后的字母表示，其他学科中，也是这样表示，这些小字字母称为“个体变元”。因此“某某要喝水”表示为W(x),x泛指所有的人，“女人喜欢漂亮衣服”表示为L(x,y)，x泛指“女人”、y泛指“衣服”，“女人喜欢帅哥”表示为H(y,z)，其中y泛指女人、z泛指帅哥。“男人结婚生崽”表示为M(z)，z泛指男人。2.1基本概念4、全称量词为了表示“所有女人都喜欢漂亮的衣服”、“所有女人都喜欢帅哥”等中“所有”，引入符号“”，称为全称量词。可能是“ALL”的字母A倒写，表示所有、全部。当用x泛指“人”，“所有人”表示为“x”，“所有活人都要喝水”表示为xW(x)。当用x表示“女人”,y表示漂亮的衣服时，“所有女人”则表示为x、“所有漂亮的衣服”则表示为“y”，因此“所有女人都喜欢漂亮的衣服”表示为xyL(x,y)。当用x表示“女人”,y表示帅哥时，“所有女人都喜欢帅哥”表示为xyH(x,y)。2.1基本概念5、存在量词为了表示“有些男人结婚生崽”中“有些”，引入符号“”，表示“存在，有些、有部分”等的含义。称为存在量词。它是Exist的首字母，左旋180度，如用z表示“男人”，那么“有些男人”表示为“z”，“有些男人结婚生崽”表示为“zM(z)”。2.1基本概念6、谓词公式将表示全部的符号“”，表示为部分的“”称为量词，将单个谓词公式如W(x)，带量词的谓词如zM(z)，统称为“谓词公式”。谓词W(x),M(z)中只有1个个体变元,则称为1元谓词公式，常用来刻划对象的性质、属性。谓词L(x,y)、H(y,z)中有2个个体变元，称为2元谓词。常用来表示二个对象之间的关系，如喜欢，类似如果有n个个体变元则称为n元谓词公式。个体变元的取值范围称为“讨论域”，如果没有交待讨论域，表示对个体变元的取值范围，不做任何限制，泛指宇宙界的万物，称为“全总个体域”，常用大写字母U表示。利用量词、谓词将自然语言转换为谓词公式例1：(1)凡人都要呼吸(2)有的人用左手写字。解：当个体域为“人类”时xB(x),其中B(x)表示x人呼吸breath.xWL(x)，其中WL(x)表示x用左边写字。当个体域为全总个体域(宇宙万物组成)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时，谓词公式相同但真值不同！例3(1)兔子比乌龟跑得快(2)有的兔子比所有的乌龟跑得快(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)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)))因为对于实数x，y，(x2-2xy+y2)=(x-y)2，当xy时，有(x-y)20，故(x2-2xy+y2)0，故x2+y22xy，故H(x2+y2,2xy))为真故原话正确，故以上公式的真值为1。故谓词公式可出现个体变元,平方,乘、倍数、函数等。例5表示“所有人都要变老的，杨圣洪是人，所以杨圣洪也会变老的”。解：个体域为全总个体域，即对个体变元的取值不做任何限。H(x)表示对象x是人类，O(x)表示对象x变老，c表示个体常元“杨圣洪”，则H(c)表示个体常元杨圣洪是人类，O(c)表示个体常元杨圣洪要变老，原句表示(x(H(x)O(x))H(c))O(c)。该公式不仅有个体变元，还有个体常元例6表示“所有人都要死的，苏格拉底是人，所以苏格拉底也会死”。解：个体域为全总个体域，即对个体变元的取值不做任何限制。H(x)表示对象x是人类，O(x)表示对象x要死的，c表示个体常元“苏格拉底”，则H(c)表示个体常元苏格拉底是人类，O(c)表示个体常元苏格拉底要死，原句表示(x(H(x)O(x))H(c))O(c)。这两个例题，语句不同，但是最后的谓词公式相同。2.2、谓词公式及解释上节得到一些谓词公式，获得一些结论，也有存在一些疑惑？(1)谓词公式有个体常元、个体变元，还可以有个体变元的表达式，那么谓词公式究竟还有哪些形式，究竟什么的字符串是合法的谓词公式？(2)同一句话有二个不同的公式，那么这二个公式等值吗？(3)不同的话拥有同样的谓词公式，到底这二句话有何共性？(4)同一样公式在不同的论域下真值不同，究竟如何确定一个公式的真值呢？2.2、谓词公式及解释非逻辑符号:个体常元、函数符号、谓词符号逻辑符号:个体变元、量词符号、联结词、逗号、括号。项的定义：个体常元与变元及其函数式为项。(1)个体常元和个体变元是项。(2)若(x1,x2,…,xn)是n元函数,t1,t2,…tn是n个项，则(t1,t2,…,tn)是项。(3)有限次使用(2)得到的表达式是项。原子公式：设R(x1,x2,…,xn)是n元谓词，t1,t2,…,tn是项，则R(t1,t2,…,tn)是原子公式。2.2、谓词公式及解释项的定义：个体常元与变元及其函数式为项。原子公式：设R(x1,x2,…,xn)是n元谓词，t1,t2,…,tn是项，则R(t1,t2,…,tn)是原子公式。合式谓词公式：(1)原子公式是合式公式；(2)若A是合式公式，则(A)也是合式公式；(3)若A,B合式，则AB,AB,AB,AB合式(4)若A合式，则xA、xA合式(5)有限次使用(2)~(4)得到的式子是合式。2.2、谓词公式及解释(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条规则写出的表达式，就是合法谓词公式(也称为合式公式)。不再拘泥于某个具体的自然语句。直接研究含义不确定或泛指的谓词公式。从形式上研究合式公式的性质。2.2、谓词公式及解释-个体变元的身份量词指导变元：xA和xA中的x量词辖域：xA和xA中的A为量词/辖域变元的约束出现：指导变元的每次出现(称约束变元)。变元的自由出现：不是约束出现的变元(称自由变元)。例题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，各一次。2.2、谓词公式及解释-个体变元的身份量词指导变元：xA和xA中的x量词辖域：xA和xA中的A为量词/辖域变元的约束出现：指导变元的每次出现(称约束变元)。变元的自由出现：不是约束出现的变元(称自由变元)。例题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次。2.2、谓词公式及解释-个体变元的身份例题分析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不是一回事，只是恰巧二个名字相同而矣，好比有2个李勇，一个是正坐在家里看电视的“李勇”，一个是在马路上散步的“李勇”，为了避免这种“误会”出现，要对“约束变元”改名。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不是一回事，只是恰巧二个名字相同而矣，为避免这种“误会”出现要对“约束变元”改名。将量词x的指导变元x，x的每次约束出现换成公式中未出现的r。将量词y指导变元y、约束变元y的每次出现换成公式中未出现的s，则原式为r(F(r)G(y))s(H(x)L(x,s,z))，所有约束变元与自由变元均不重名，无误会。2.2、谓词公式及解释-个体变元的身份例题分析xy(P(x,y)Q(y,z))xP(x,y)作用域与变元约束情况解：x、y的作用域是(P(x,y)Q(y,z))，x的作用域是P(x,y)。将与自由变元同名约束变元yr，将与前一个同名约束变元xs，则原公式xr(P(x,r)Q(r,z))sP(s,y)2.2、谓词公式及解释-个体变元的身份例题x(P(x)xQ(x,z)yR(x,y))Q(x,y)解：x的辖域是P(x)xQ(x,z)yR(x,y)，。x的辖域是Q(x,z)y的辖域是R(x,y)s(P(s)rQ(r,z)tR(s,t))Q(x,y)改名规则：一般仅对约束变元改名后出现者约束变元也要改名。方法：将量词的指导变元，及辖域中约束变元每次约束出现，全部换成公式中未出现的字母。2.2、谓词公式及解释-个体变元的身