离散数学王元元习题解答3.doc

第二章 谓词演算与其形式系统2.1 个体、谓词和量词内容提要 谓词演算中把一切讨论对象都称为个体，它们可以是客观世界中的具体客体，也可以是抽象的客体，诸如数字、符号等。确定的个体常用a，b，c等到小写字母或字母串表示。a，b，c等称为常元constants。不确定的个体常用字母x，y，z，u，v，w等来表示。它们被称为变元variables。 谓词演算中把讨论对象个体的全体称为个体域domain of individuals，常用字母D表示，并约定任何D都至少含有一个成员。当讨论对象遍与一切客体时，个体域特称为全总域universe，用字母U表示。例如，当初中学生说“所有数的平方非负时，实数集是个体域；而达尔文在写物种起源时，如此以全体生物为个体域；也许哲学家更偏爱全总域。讨论常常会涉与多种类型个体,这时使用全总域也是比拟方便的。当给定个体域时，常元表示该域中的一个确定的成员，而变元如此可以取该域中的任何一个成员为其值。表示D上个体间运算的运算符与常元、变元组成所谓个体项terms。例如，x+y，x2等。我们把语句中表示个体性质和关系的语言成分通常是谓语称为谓词predicate。谓词携有可以放置个体的空位，当空位上填入个体后便产生一个关于这些个体的语句，它断言个体具有谓词所表示的性质和关系。通常把谓词所携空位的数目称为谓词的元数。 谓词演算中的量词quantifiers指数量词“所有和“有，分别用符号"(All的第一个字母A的倒写)和$(Exist的第一个字母E的反写)来表示。为了用量词"和$分别表示个体域中所有个体和有些个体满足一元谓词P，需引入一个变元，同时用作量词的指导变元放在量词后和谓词P的命名式变元："xP(x) 读作“所有任意,每一个x满足P(x)。 表示个体域中所有的个体满足谓词P(x)。$x P(x) 读作“有存在,至少有一个x满足P(x)。 表示个体域中至少有一个体满足P(x)。当量词用于一谓词或复合的谓词表达式式，该谓词或复合的谓词表达式称为量词的辖域domainsof quantifiers。因此，量词的辖域或者是紧邻其右侧的那个谓词;或者是其右侧第一对括号的表达式。当然，量词辖域与该量词指导变元同一的变元都是约束变元。例如"x(A(x)B(x)C(x)中"x的辖域是A(x)B(x)，其中的x是约束变元；但C(x)不在辖域，其中的x如此是自由变元；$x A(x)B(x)中$x的辖域是A(x)，其中x是约束变元，而B(x)中x为自由变元。定义2.1 以下条款规定的符号串称为谓词公式 predicate forrmula，简称公式。 1谓词填式是公式，命题常元是公式看作零元谓词。 2如果A，B是公式，x为任一变元，那么(A)，(AB)，("xA)，($x A)当使用五个联结词时还有(AB)，(AB)，(A«B)都是公式。 3只有有限步使用1，2条款所形成的符号串是公式。括号省略原如此同前，并约定，("xA)，($x A)中最外层括号也可省略。习题解答练习 1、指出如下谓词公式中的量词与其辖域，指出各自由变元和约束变元，并回答它们是否是命题：1"x(P(x)Q(x)RR为命题常元 2"x(P(x)Q(x)$xS(x)T(x) 3"x(P(x)$y(B(x,y)Q(y)T(y)4P(x)("y$x(P(x)B(x,y)P(x)解1全称量词"，辖域 P(x)Q(x)，其中x为约束变元，"x(P(x)Q(x)R是命题。2全称量词"，辖域 P(x)Q(x)，其中 x为约束变元。存在量词$，辖域 S(x) ，其中 x为约束变元。T(x)中x为自由变元。"x(P(x)Q(x)$xS(x)T(x)不是命题。3全称量词"，辖域 P(x)$y(B(x,y)Q(y)T(y)，其中 x为约束变元，T(y)中y为自由变元。存在量词$，辖域B(x,y)Q(y)，其中y为约束变元。"x(P(x)$y(B(x,y)Q(y)T(y)是命题。4全称量词"，辖域$x(P(x)B(x,y)，其中 y为约束变元。存在量词$，辖域P(x)B(x,y)，其中 x为约束变元。不在量词辖域中的P(x)中的x为自由变元。P(x)("y$x(P(x)B(x,y)P(x)不是命题。 2、对个体域0，1判定如下公式的真值, E(x)表示“x是偶数： 1"x(E(x)x=1) 2"x(E(x)x=1) 3$x(E(x)x=1) 4$x(E(x)x=1)再将它们的量词消去,表示成合取或析取命题公式，鉴别你所确定的真值是否正确。解1"x(E(x)x=1) 真"x(E(x)x=1) 可表示成命题公式E(0)0=1E(1)1=1其中E(0)0=1真，E(1)1=1也真，故E(0)0=1E(1)1=1真。 2"x(E(x)x=1) 假"x(E(x)x=1) 可表示成命题公式E(0)0=1E(1)1=1其中E(0)0=1真，但E(1)1=1假，故E(0)0=1E(1)1=1假。3$x(E(x)x=1) 假$x(E(x)x=1) 可表示成命题公式 (E(0)0=1) (E(1)1=1)其中E(0)0=1假，E(1)1=1也假，故 (E(0)0=1) (E(1)1=1)假。4$x(E(x)x=1) 真$x(E(x)x=1) 可表示成命题公式 (E(0)0=1) (E(1)1=1)其中E(0)0=1假，但E(1)1=1真，故 (E(0)0=1) (E(1)1=1)真。 3、设整数集为个体域，判定如下公式的真值(*表示数乘运算)： 1"x$y(x*y=x) 2"x$y(x*y=1) 3"x$y(x+y=1) 4$y"x (x*y=x)5$y"x (x+y=0)6"x$y(x+y=0) 解1"x$y(x*y=x) 真 2"x$y(x*y=1) 假 3"x$y(x+y=1) 真 4$y"x (x*y=x) 真 5$y"x (x+y=0) 假6"x$y(x+y=0) 真4、量词$!表示“有且仅有，$!xP(x)表示有且仅有一个个体满足谓词P(x)。试用量词，", $,等号“=与谓词P(x),表示$! P(x)，即写出一个通常的谓词公式使之与$!xP(x)具有一样的意义。解 $!xP(x)可用以下具有一样的意义的谓词公式表示$xP(x)"yP(y)y=x 5、设个体域为整数集，试确定两个谓词P(x,y)，分别使得如下两个蕴涵式假： 1"x$!yP(x,y)$!y"x P(x,y)2$!y"x P(x,y)"x$!yP(x,y)解1当P(x,y)表示x+y=0时"x$!yP(x,y)$!y"x P(x,y)为假。2当P(x,y)表示x*y=0时$!y"x P(x,y)"x$!yP(x,y) 为假(*表示数乘运算)。因为只有数0对一切整数x，有x*0=0，从而前件真；但对数0，可有众多y，使0*y=0，从而后件假。 6、指定整数集的一个尽可能大的子集如果存在为个体域，使得如下公式为真： 1"x(x>0) 2"x(x=5x=6) 3"x$y(x+y=3)4$y"x (x+y<0)解1对正整数集个体域，"x(x>0)为真 2对5，6 ，"x(x=5x=6) 为真 3对整数集，"x$y(x+y=3) 为真4使得$y"x (x+y<0) 为真的整数集的尽可能大的子集不存在。 7、以实数集为个体域, 用谓词公式将如下语句形式化： 1如果两实数的平方和为零，那么这两个实数均为零。2f(x)为一实函数当且仅当对每一实数x都有且只有一个实数y满足y = f(x)不得使用量词 $!。“f(x)为实函数可译为RF(f)。解1"x"y(x2+y2=0x=0y=0) 。2RF(f )«"x $y(y = f(x)$z(zyz= f(x) 8、用谓词公式将如下语句形式化： 1高斯是数学家，但不是文学家。 2没有一个奇数是偶数。 3一个数既是偶数又是质数，当且仅当该数为2。 4有的猫不捉耗子，会捉耗子的猫便是好猫。 5发亮的东西不都是金子。 6不是所有的男人都至少比一个女人高，但至少有一个男人比所有的女人高。 7一个人如果不相信所有其他人，那么他也就不可能得到其他人的信任。 8如果别的星球上有人，天文学家是不会感到惊讶的。 9党指向哪里，我们就奔向那里。10谁要是游戏人生，他就一事无成；谁不能主宰自己，他就是一个奴隶。歌德解1M(x) 表示“x是数学家，A(x) 表示“x是天文学家，g表示“高斯,原句可表示为 M(g) A(g)2O(x) 表示“x是奇数，E(x) 表示“x是偶数 ,原句可表示为$x(O(x)E(x)3O(x) 表示“x是奇数，E(x) 表示“x是偶数 ,原句可表示为"x(O(x)E(x)«x=2)4C(x) 表示“x是猫，M(x)表示“x是老鼠，G(x) 表示“x是好的，K(x,y)表示“x会捉y ,原句可表示为$x(C (x)"y(M (y)K(x,y)"x(C (x)"y(M (y)K(x,y)G(x)5G(x) 表示“x是金子，L(x) 表示“x是发亮的 ,原句可表示为"x(L (x)G(x)6M(x) 表示“x是男人， F(x) 表示“x是女人，H(x,y) 表示“x比y高,原句可表示为"x(M (x)$y(F(y)H(x,y)$x(M (x)"y(F(y)H(x,y)7M(x) 表示“x是人，B(x,y)表示“x相信y, 原句可表示为"x(M (x)$y(M(y)xyB(x,y)$y(M(y)xyB(y,x)8C(x) 表示“x是星球，M(x) 表示“x是人，A(x) 表示“x是天文学家，e表示“地球，H(x,y) 表示“x有y，S(x) 表示“x惊讶，原句可表示为$x(C (x)xe$y(M(y)H(x,y)"x(A (x)S(x)9Q(x,y) 表示“x指向y，J(x,y) 表示“x奔向y，party表示“党 ，we表示“我们,原句可表示为"x(Q(party，x)J(we, x) 10M(x) 表示“x是人，K(x) 表示“x游戏人生，L(x) 表示“x一事无成， H(x,y) 表示“x主宰y，N(x) 表示“x是奴隶，原句可表示为"x(M(x)K(x)L(x)"x(H(x,x)N(x) 谓词演算永真式 容提要定义 给定个体域D与公式A中各谓词符号的解释I，如果A中个体变元x1 ,xn分别取值u1 ,un时A真，如此称A在u1 ,un处真；当x1 ,xn无论取D中怎样的个体u1 ,un, A在u1 ,un处均真，如此称A在解释I下真。定义 给定个体域D，假如公式A在每一解释I下均真，那么称A在D上永真。假如公式A对任何个体域D均有D上永真，如此称A为永真式，或称A永真valid。A永真仍记为A。 沿用命题演算中引入的一些符号和称呼： AB表示“AB永真，称A逻辑蕴涵B。AB当且仅当对任意个体域和解释，一切使A真的变元取值状况均使B亦真。GA同前，可作类似的定义。 AB表示“A«B永真，称A逻辑等价B。AB当且仅当对一切域、解释和变元取值状况，A与B都具有一样的真值。定义 公式A称为可满足的，如果对某一个体域、某一解释和变元的某一取值状况，A在此处取值真。公式A不可满足时也称A为永假式。谓词演算永真式 1所有重言式。首先，由于谓词演算中允许使用命题常元，因而谓词公式中仍包含命题公式，其中的重言式显然在谓词演算中仍然是永真式。2当A不含自由变元x时，"xAA , $xAA 3"xA(x) A(x)A(x)$xA(x)"xA(x)$xA(x) 4$xA(x)"xA(x)"xA(x)$xA(x)$x A(x)"xA(x)"xA(x)$xA(x) 5当公式B中不含自由变元x时，"xA(x)B"x(A(x)B)"xA(x)B"x(A(x)B)$xA(x)B$x(A(x)B)$xA(x)B$x(A(x)B)6上一组永真式中的公式B假如含自由变元x，情况就要复杂一些。"x(A(x)B(x)"xA(x)"xB(x)"xA(x)"xB(x)"x(A(x)B(x)$x(A(x)B(x)$xA(x)$x B(x)$x(A(x)B(x)$xA(x)$x B(x) 7"x"yA(x,y)"y"xA(x,y)"x"yA(x,y)$y"xA(x,y)$y"xA(x,y)"x$yA(x,y)"x$yA(x,y)$y$xA(x,y)$x$yA(x,y)$y$xA(x,y)8当C中无自由变元x时，"x(CA(x)C"xA(x)$x(CA(x)C$xA(x)"x(A(x)B(x)"xA(x)"xB(x)定义 设谓词公式A中含自由变元x，设t为一个体项，且t中无自由变元为A中的约束变元，那么称t是在A中对x可代入的，其代入实例记为A(t/x)代入的意义同前。定理代入原理假如A是永真式，那么对A中变元可代入的代入实例都是永真式。 由于A永真，因此它的取值与A中变元的取值无关，故其代入实例仍为永真式。定理替换原理设A，D为谓词公式，C为A的子公式，且CD。假如B为将A中子公式C的某些出现未必全部替换为D后所得的公式，那么AB。定义 设A为仅含联结词，的谓词公式，A*为将A中符号，t，f，" , $分别换为，f，t,$，"后所得的公式，那么称A*为A的对偶式。 注意，第一章中关于对偶式的一切讨论，现在对于谓词演算都仍然成立。 定理 改名原理假如公式A中无自由变元y，那么，"xA(x)"yA(y) , $xA(x)$yA(y)习题解答练习1、 利用量词意义或利用已经证明了的永真式与几个根本原理，证明节第28组永真式未证明的各式。解 证3之b A(x)$xA(x) 设U,I,s分别是使A(x)真的个体域、解释和指派，s(x)=dÎU，那么A(d)真,因此对个体域U、解释I,$xA(x) 也真。证3之c "xA(x)$xA(x)由"xA(x)A(x) 和 "xA(x)$xA(x) 立即可得。证4之b "xA(x)$xA(x) 设U,I是使"xA(x)真的个体域和解释，那么并非U中的所有个体都使得解释I下的谓词A(x)假，因此U中有个体使得解释I下的谓词A(x)真，故个体域U和解释I下$xA(x)真。上述证明是可逆的，所以"xA(x)$xA(x)得证。证4之c "xA(x)$xA(x)在4之a中取A(x)为A(x) 即可得本式。证4之d "xA(x)$xA(x)在4之b中取A(x)为A(x) 即可得本式。证5之a "xA(x)B"x(A(x)B)设U,I是使"xA(x)B真的个体域和解释，那么1U,I使B真。于是U,I使A(x)B对一切x均真，因此U,I使"x(A(x)B)。2U,I使"xA(x)真。于是U,I使A(x)对一切x均真，从而对一切x ，A(x)B真，因此U,I使"x(A(x)B)。故 "xA(x)B"x(A(x)B) 。上述证明是可逆的，所以"xA(x)B"x(A(x)B)得证。证5之b "xA(x)B"x(A(x)B)仿5之a可证。证5之d $xA(x)B$x(A(x)B)$xA(x)B($xA(x)B)($xA(x)B)("xA(x)B) (据4之c )"x(A(x)B)(据5之a )$x(A(x)B) (据4之d )$x(A(x)B)证6之a "x(A(x)B(x)"xA(x)"x B(x)设U,I是使"x(A(x)B(x)真的个体域和解释，那么对任意dÎU，A(d)B(d)真。因此，对任意dÎU，A(d)真，对任意dÎU，B(d)真。故U,I是使"xA(x)"x B(x)真。"x(A(x)B(x)"xA(x)"x B(x)得证。上述证明是可逆的，所以"x(A(x)B(x)"xA(x)"x B(x)得证。证6之b $x(A(x)B(x)$xA(x)$x B(x)$x(A(x)B(x)($x(A(x)B(x)("x(A(x)B(x) (据4之c )("xA(x)"xB(x) (据6之a )($xA(x)$xB(x) (据4之d )$xA(x)$xB(x)证7之a "x"yA(x,y)"y"xA(x,y)个体域和解释U,I使"x"yA(x,y)真的意义，与个体域和解释U,I使"y"xA(x,y)真的意义一样，因此"x"yA(x,y)"y"xA(x,y) 。证7之b "x"yA(x,y)$y"xA(x,y)由"x"yA(x,y)"y"xA(x,y) 和 "y"xA(x,y)$y"xA(x,y) 立即可得。证7之c $y"xA(x,y)"x$yA(x,y)设U,I是使$y"xA(x,y)真的个体域和解释，那么有cÎU，使得对任意dÎU，A(c,d) 真。因此，对任以dÎU，总可取cÎU，使得A(c,d) 真。故U,I也使"x$yA(x,y)真。$y"xA(x,y)"x$yA(x,y)得证。证7之d "x$yA(x,y)$y$xA(x,y)由"x$yA(x,y)$x$yA(x,y) 和 $x$yA(x,y)$y$xA(x,y) (7之e,下面给出证明) 立即可得。证7之e $x$yA(x,y)$y$xA(x,y)$x$yA(x,y)($x$yA(x,y)("x"yA(x,y) (据4之c )("y"xA(x,y) (据7之a )$y$xA(x,y) (据4之b )证之a "x(CA(x)C"x A(x) (C中无自由变元x )设U,I是使"x(CA(x)真的个体域和解释，那么对任意dÎU，CA(d) 真。此时C假，如此C"x A(x)真。C真，那么对任意dÎU，A(d) 真，即"x A(x)真，因此C"x A(x)真。故个体域和解释U,I使C"x A(x)真，"x(CA(x)C"x A(x)得证。上述证明是可逆的，所以"x(CA(x)C"x A(x)得证。证之b $x(CA(x)C$x A(x) (C中无自由变元x )仿之a 可证。2、证明如下逻辑蕴涵式与逻辑等价式方法不限：1$xP(x)"x Q(x)"x(P(x)Q(x)证 $xP(x)"x Q(x)$xP(x)"x Q(x)"xP(x)"x Q(x)"xP(x)Q(x)"x(P(x)Q(x)2P(x)"x Q(x)$x(P(x)Q(x)证 P(x)"x Q(x)P(x)Q(x)$x(P(x)Q(x)3"x"y(P(x)Q(y)"x P(x)"y Q(y)证"x"y(P(x)Q(y)"x (P(x)"y Q(y)"x P(x)"y Q(y)4$x$y(P(x)Q(y)$x P(x)$y Q(y)证$x$y(P(x)Q(y)$x (P(x)$y Q(y)$x P(x)$y Q(y)5$x$y(P(x)Q(y)"x P(x)$y Q(y)证$x$y(P(x)Q(y)$x$y(P(x)Q(y)$x (P(x)$y Q(y)$xP(x)$y Q(y)"x P(x)$y Q(y)"x P(x)$y Q(y)6"x"y(P(x)Q(y)$x P(x)"y Q(y)证"x"y(P(x)Q(y)"x"y(P(x)Q(y)"x (P(x)"y Q(y)"x P(x)"y Q(y)$x P(x)"y Q(y)$x P(x)"y Q(y)3、试举出一个个体域与两种解释，分别证明第2题之12的逆不能成立。解 第2题之1。取个体域为自然数集合，P(x)表示：x为不等于2的质数，Q(x)表示：x为奇数，那么"x(P(x)Q(x)真，$xP(x)"x Q(x)假$xP(x)假，而"x Q(x)真。故"x(P(x)Q(x)$xP(x)"x Q(x)不能成立。第2题之2取个体域为自然数集合，P(x)表示：x 等于2，Q(x)表示：x为偶数，指派P(x)中自由变元x=3, 那么$x(P(x)Q(x)真，P(x)"x Q(x)假。$x(P(x)Q(x)P(x)"x Q(x) 不能成立。 4、设个体域D=d1,dn，试用消去量词的方法证明如下根本逻辑等价式：1"xA(x)$xA(x)解"xA(x)Ad1AdnAd1Adn$xA(x)2"xA(x)P"x(A(x)P) P为命题常元解"xA(x)PAd1AdnPAd1P(AdnP)"x(A(x)P)3"xA(x)"x B(x)"x(A(x)B(x)解 "xA(x)"x B(x)Ad1AdnBd1BdnAd1Bd1AdnBdn"x(A(x)B(x)4$xA(x)$x B(x)$x(A(x)B(x)解 $xA(x)$x B(x)Ad1AdnBd1BdnAd1Bd1AdnBdn$x(A(x)B(x) 5、利用对偶原理“假如AB如此A*B*与“假如AB，如此B*A*，作出与节第7中各永真式相应的永真式。"xA(x)A(x)与 A(x)$xA(x)对偶"xA(x)$xA(x)与自身对偶$xA(x)"xA(x)与"xA(x)$xA(x)对偶"xA(x)$xA(x) 与"xA(x)$xA(x)对偶"xA(x)B"x(A(x)B) 与$xA(x)B$x(A(x)B)对偶"xA(x)B"x(A(x)B) 与$xA(x)B$x(A(x)B) 对偶"x(A(x)B(x)"xA(x)"xB(x)与$xA(x)$x B(x)$x(A(x)B(x) 对偶"x"yA(x,y)"y"xA(x,y)与$x$yA(x,y)$y$xA(x,y) 对偶"x"yA(x,y)$y"xA(x,y) 与"y$xA(x,y)$x$y A(x,y) 对偶$y"xA(x,y)"x$yA(x,y) 与$x"yA(x,y)"y$xA(x,y) 对偶"x$yA(x,y)$y$xA(x,y) 与"y"xA(x,y)$x"y A(x,y) 对偶6、用谓词公式写出的定义，并据此写出的意义用自然语言表示。解定义如下个体域为实数集"ee>0$>0"x| x c |<|f(x) k |<e等价于"ee>0$>0"x| x c |<|f(x) k |<e$ee>0">0$x| x c |<|f(x) k |e可用自然语言表述为：存在正数e，对无论怎样的正数，均有x使得| x c |<但|f(x) k |e。 7、判别如下公式是否是可满足的，并说明理由： 1"xP(x)$yP(y) 2"xP(x)$yP(y) 3(P(a)«$xP(x)4(P(a)$xP(x)（5） P(a)$xP(x) 6"xP(x)P(a)解 1"xP(x)$yP(y) 是可满足的，因为可使"xP(x)和$yP(y)之一为真。2"xP(x)$yP(y) 是不可满足的，因为不可能使"xP(x)和$yP(y)同时为真。3(P(a)«$xP(x) 是可满足的，因为只要使$xP(x)真，P(a)假，P(a)«$xP(x)便为假，从而(P(a)«$xP(x)真。4(P(a)$xP(x) 是可满足的，因为只要使$xP(x)假，或P(a)假，P(a)$xP(x)便为假，从而(P(a)$xP(x)真。5P(a)$xP(x) 是可满足的，因为只要使P(a)假，P(a)$xP(x)便为真。6"xP(x)P(a) 是可满足的，因为只要使"xP(x)假，"xP(x)P(a)便为真。 谓词公式的前束式 容提要定义 公式A称为公式A的前束式prenex normal forms，如果AA，且A形如 Q1x1QnxnB其中Q1，Qn为量词"或$，B称为母式，B中无量词。当B为合取析取式时，A称为A的前束合取析取式。定理 前束式定理 对任意谓词公式均可作出其前束式，进而作出其前束合取式或前束析取式。 对任何谓词公式均可作出其前束式，因为我们总可以利用各组逻辑等价式将量词逐个移至公式的前部，其步骤是: 首先将公式中联结词,«消除。 其次将否认词深入到各原子公式之前。最后，利用节的第5组和第6组永真式将量词逐个移至公式前部。习题解答练习 1、设个体域D=d1, d2,d3，试用消去量词的方式证明：当A(x)中无自由变元y, B(y) 中无自由变元x时，"x$y (A(x)B(y)$y"x(A(x)B(y)解 "x$y (A(x)B(y)"xA(x)B(d1)A(x)B(d2)A(x)B(d3)A(d1)B(d1)A(d1)B(d2)A(d1)B(d3)A(d2)B(d1)A(d2)B(d2)A(d2)B(d3)A(d3)B(d1)A(d3)B(d2)A(d3)B(d3)A(d1)B(d1)B(d2)B(d3)A(d2)B(d1)B(d2)B(d3)A(d3)B(d1)B(d2)B(d3)A(d1)A(d2)A(d3)B(d1)B(d2)B(d3)$y"x(A(x)B(y)$y(A(d1)B(y)(A(d2)B(y)(A(d3)B(y)(A(d1)B(d1)(A(d2)B(d1)(A(d3)B(d1)(A(d1)B(d2)(A(d2)B(d2)(A(d3)B(d2)(A(d1)B(d3)(A(d2)B(d3)(A(d3)B(d3)A(d1)A(d2)A(d3)B(d1)A(d1)A(d2)A(d3)B(d2)A(d1)A(d2)A(d3)B(d3)A(d1)A(d2)A(d3)B(d1)B(d2)B(d3)故"x$y (A(x)B(y)$y"x(A(x)B(y) 2、求如下各式的前束合取式： 1"x(A(x)$y B(y) 2"x(A(x)$y B(x,y) 3"x"y ($zA(x,y,z)«$z B(x,y,z) 4$x($y A(x,y)($z B(z)C(x)5"x($yA(x,y)$x"y( B(x,y)"y(A(y,x)B(x,y)解 1"x(A(x)$y B(y)$xA(x)"yB(y)$x"yA(x)B(y)2"x(A(x)$y B(x,y)"x(A(x)$y B(x,y)"x$y (A(x)B(x,y)3"x"y ($zA(x,y,z)«$z B(x,y,z)"x"y($zA(x,y,z)$z B(x,y,z)($z B (x,y,z)$z A(x,y,z)"x"y($zA(x,y,z)$zB(x,y,z)($z B (x,y,z)$z A(x,y,z)"x"y("zA(x,y,z)$zB(x,y,z)("zB (x,y,z)$z A(x,y,z)"x"y("zA(x,y,z)$uB(x,y,u)("vB (x,y,v)$w A(x,y,w)"x"y"z$u"v$w(A(x,y,z)B(x,y,u)(B (x,y,v)A(x,y,w)4$x($y A(x,y)($z B(z)C(x)$x($y A(x,y)($z B(z)C(x)$x($y A(x,y)("zB(z)C(x)$x($y A(x,y)"z (B(z)C(x)$x$y "z (A(x,y)B(z)C(x)5"x($yA(x,y)$x"y( B(x,y)"y(A(y,x)B(x,y)$ x($yA(x,y)$x"y( B(x,y)"u (A(u,x)B(x, u)$ x($yA(x,y)$x"y"u( B(x,y)(A(u,x)B(x, u)$ x($yA(x,y)$v"w"u( B(v, w)(A(u, v)B(v, u)$ x$y$v"w"u (A(x,y)B(v, w)(A(u, v)B(v, u) 一阶谓词演算形式系统 容提要 一阶谓词演算形式系统FPC的语言成分要复杂得多，它包括： 个体变元 x ,y ,z ,u ,v ,w , 个体常元 a ,b ,c ,d ,e, 个体间运算符号函数符 f (n) , g (n) , h (n) ,其中n为任一正整数，表示函数的元数。 谓词符号P(n)，Q(n)，R(n)，S(n)，其中n为非负整数，表示谓词的元数。当 n =0时谓词符退化为一个命题常元。 真值联结词 , 量词" , $ 括号，注意，FPC不使用联结词 , ，«和量词$，但把它们看作可定义的记号，或缩写记号。例如，$xA(x)可看作是"x A(x)的缩写。当需要引入量词$时，只要在系统中添加定义$的公理：$xA(x)"x A(x) , "x A(x)$xA(x) FPC的更高一级的语言成分有“个体项和“公式。 FPC的个体项(terms)下简称项由以下条款规定： 1个体变元和个体常元是项。 2对任意正整数n，如果f (n)为一n元函数符，t1, ,tn为项，那么f (n)(t1,tn)也是项。 3除有限次使用1，2条款所确定的符号串外，没有别的东西是个体项。 FPC的公式(formula)由以下条款规定： 1对任意非负整数n，如果P(n)为一n元谓词符，t1, ,tn为项，那么P(0)命题常元和P(n