硕士研究生08级高等数理逻辑考试题0811

1、成绩 西安交通大学研究生考试题 课 程：高 等 数 理 逻 辑 系 别：计算机科学与技术 考试时间： 2008年12月29日 专业班级：硕士829,830,831,832等班 姓 名： 学号： 期中 期末题号一(10%)二(10%)三(10%)四(10%)五(10%)六(10%)七(10%)合计(70%)得分一.经典逻辑(10%)1º. 在J×ukasiewicz的PC公理系统J-系统中证明： 16*. J(p®(q®r)®(p®q)®(p®r)。2º. 试在Tarski-语义下论证如下的群公理集(tG:

2、=c, f, P)通是独立的： j(封闭性公理) "x"y(PxÙPy®Pfxy) ；k(结合性公理) "x"y"z(PxÙPyÙPz®ffxyz = fxfyz) ；l(有幺性公理) "x(PcÙPx®fcx = xÙ fxc= x) ；m(有逆性公理) "x$y(PxÙPy®fxy = cÙ fyx = c) ；提示：通过给出(构造出)四个有限Tarski-语义反驳(反模型

3、)来论证，使得每个反模型只满足其中的某三个公理而不满足剩下的那个公理。二 模态逻辑(10%)1º.试证明：对每个使得Gi*Gj的极大一致集GjÎG，都有aÎGj ÛaÎGi。2º.在模态逻辑Kripke-可能世界形式语义下，通过构造反(F+T)=-模型，试证明一阶模态公式("x)(aÚb)®("x)aÚ("x)b不是(F+T)=-有效的，即·K,(F+T)= ("x)(aÚb)®("x)aÚ("x)b。三.

4、时态逻辑框架(10%)1º.在Manna-Pnueli(1981)的时态逻辑演算框架TL=_系统中，试给出DR14.TL=w1®w2Uw3 ,TL=w3®w2Uw4 Þ TL=w1®w2Uw4的形式推导。2º.在Manna-Pnueli(1981)的一阶时态逻辑形式语义下，通过构造反&P-模型，试证明TL38的逆不是&P-有效的，即·M&P "u×(w1Uw2) ®"u×w1U"u×w2。四.l演算及组合逻辑(10%)1º

5、.j如何将一阶(多元)f(x1, x2,xn)函数转换为高阶(一元)函数fx1x2xn?k如何将高阶(一元)函数fx1x2xn转换为一阶(多元)f(x1, x2,xn)函数?2º.j试构造组合子(P,Q,R)（设其Z）(Godel算子)，(Z)0（取首算子），(Z)1（取中算子），(Z)2（取尾算子），使得对一切C-项P,Q,R,都有(Z)0(P,Q,R)0=P、(Z)1(P,Q,R)1=Q、(Z)2(P,Q,R)2=R及(Z)0,(Z)1,(Z)2)=Z；提示：利用K，I算子。k利用Y算子，求解不动点方程：(P,Q,R)=F(P,Q,R) 并分别给出C-项P,Q,R的解表达式。 提

6、示：利用(P,Q,R)=(P,Q),R)及j的结果。五.二阶逻辑(10%)首先，在二阶逻辑S-系统中引入下列 ·定义： Def£ (X£X¢)=Def"x(Xx®X¢x)Def= (X=X¢)=Def"x(Xx«X¢x) ·公理： DC. S "X($xXxÙ$xØXxÙ"x"y(XxÙy<x®Xy)构成一实用的新的二阶逻辑S¢-系统。然后，在新二阶逻辑S¢-系统中试证明

7、下列定理:REF. S¢ "X(X£X)ANT. S¢ "X"Y(X£YÙY£X®X=Y)TRA. S¢ "X"Y"Y(X£YÙY£ Z®X£Z)COM. S¢ "X"Y(X£YÚY£X)。六.直觉主义逻辑(10%)1º. 在一阶谓词演算的直觉主义系统I中试证:I (a®b)®Øg)®(a®

8、;ØØb)®Øg)。2º.构造适当的克里普克语义结构Â=W，D，s，使：(a®$xb)®$x(a®b) (条件: xÏfree(a)在此语义结构中是假的。七.小论文(10%)结合实际，请给出我们所讲过的课程中的非经典逻辑在计算机科学与技术中某一领域的一个精彩而简小的应用。(完)2008.12.25 注意：交卷地点：709交卷时间：2009年1月9日下午3:006:00 (过时不收!)考卷：打印稿，电子稿各一份；作业：电子稿一份；格式：考卷与作业的电子稿放在一个文件之中，文件名格式为 班级_姓名_

9、学号 。考卷打印稿要在班级上打勾。一.经典逻辑(10%)1º. 在J×ukasiewicz的PC公理系统J-系统中证明： 16*. J(p®(q®r)®(p®q)®(p®r)。 证明：JA1(1)(p®q)®(q®r)®(p®r)(2)假设 (p®r) (1)(2)TR1 (3)(p®q)®(q®(p®r)®(p®(p®r)(4) 假设 (q®r) (3)(4)TR1 (5)

10、(p®(q®r)®(q®r)®(p®r)®(p®(p®r) Def® (6) (p®(q®r)®(q®r)®(p®r)®(ØpÚØpÚr) (7) (p®(q®r)®(q®r)®(p®r)®(ØpÚr) Def® (8) (p®(q®r)®(q®r)

11、®(p®r)®(p®r) (1) (9) (p®(q®r)®(p®q)®(p®r) 得证2º. 试在Tarski-语义下论证如下的群公理集(tG:=c, f, P)通是独立的： j(封闭性公理) "x"y(PxÙPy®Pfxy) ；k(结合性公理) "x"y"z(PxÙPyÙPz®ffxyz = fxfyz) ；l(有幺性公理) "x(PcÙPx&

12、#174;fcx = xÙ fxc= x) ；m(有逆性公理) "x$y(PxÙPy®fxy = cÙ fyx = c) ；提示：通过给出(构造出)四个有限Tarski-语义反驳(反模型)来论证，使得每个反模型只满足其中的某三个公理而不满足剩下的那个公理。证明：假设有一个塔斯基语义反模型满足klm而不满足j，既有：Á= (U,x)UT Ø"x"y(PxÙPy®Pfxy) xUT "x"y"z(PxÙPyÙP

13、z®ffxyz = fxfyz) xUT "x(PcÙPx®fcx = xÙ fxc= x) xUT "x$y(PxÙPy®fxy = cÙ fyx = c) x由群的定义得知，不满足封闭性公理的公理集不是一个群，这与题意矛盾。同理，单独不满足k、l、m的其他三个塔斯基语义反模型一样与公理集的群性质有矛盾。由此可得该群公理集的四个公理是相互独立的。二 模态逻辑(10%)1º.试证明：对每个使得Gi*Gj的极大一致集GjÎG，都有aÎGj Ûa&#

14、206;Gi。证明：我们构造一个Kripke-可能世界模型如下：令|是与极大一致集对应的那个可能世界（对每个）|且且Gi*Gj 且和分别与和对应因此，R显然是自反的（因为Gi*Gj），所以M是一个T-模型。是一个赋值，使得对任一命题变项，对每个可能世界，（这里且与对应）对每个使得的可能世界，都有对每个使得Gi*Gj的极大一致集，都有2º.在模态逻辑Kripke-可能世界形式语义下，通过构造反(F+T)=-模型，试证明一阶模态公式("x)(aÚb)®("x)aÚ("x)b不是(F+T)=-有效的，即·K,(F+T)=

15、 ("x)(aÚb)®("x)aÚ("x)b。证明： 我们只要构造一个反-模型即可。(1)构造：令：，其中 ； ；显然，R是自反的，因此M是一个-模型；明显的，R不是对称的（因，但），因此M不是一个对称模型。，其中，因此满足（对应于）；，使得，；，使得任意。(2)分析：由于，所以K，（F+T）=，K，（F+T）=；因而K，（F+T）=(这是因为)；注意到，因此得到（K，（F+T）=）；进而得到K，（F+T）=。 但是，由于，因此K，（F+T）=；注意到，因而并非（K，（F+T）=）；于是K，（F+T）=；又注意到，我们就得到K，（F+

16、T）=；由于，因此K，（F+T）=；注意到，因而并非（K，（F+T）=）；于是K，（F+T）=；又注意到，我们就得到K，（F+T）=；于是得到K，（F+T）=； 因此K，（F+T）=； 进而K，（F+T）=； 所以K，（F+T）=。 证明完毕。三.时态逻辑框架(10%)1º.在Manna-Pnueli(1981)的时态逻辑演算框架TL=_系统中，试给出DR14.TL=w1®w2Uw3 ,TL=w3®w2Uw4 Þ TL=w1®w2Uw4的形式推导。证明： condition1： （1）TL=w1®w2Uw3说明当w1 成立时，存在k使

17、得w3=ture，那很自然w3 也是成立的 ，condition2： w3®w2Uw4，由根据Syll公式可以得出w1®w2Uw4。2º.在Manna-Pnueli(1981)的一阶时态逻辑形式语义下，通过构造反&P-模型，试证明TL38的逆不是&P-有效的，即·M&P "u×(w1Uw2) ®"u×w1U"u×w2。(a)构造:构造反模型M=(I,a,s),其中:s=s0,s1,s2, ,sn, D=,假定当k=1时，w2=true，且w2=true。 当k=

18、0时，w1=true，且w1=true。 且当w2和w1不能同时为true。(b)分析:显然有当k=1时，有w2=true，此时w1=true，同理w2=true，w1=true，因此"u×(w1Uw2)成立，但当k=1时，对u用,赋值，w2=true，且w2=true，可是有w2和w1不能同时为true，在这种情况下，w1不能等于true。四.l演算及组合逻辑(10%)1º.j如何将一阶(多元)f(x1, x2,xn)函数转换为高阶(一元)函数fx1x2xn?k如何将高阶(一元)函数fx1x2xn转换为一阶(多元)f(x1, x2,xn)函数?解：j通过柯里法可

19、以将一阶多元函数转化为高阶一元函数，此时f(x1, x2,xn)记作 lx1x2xnf ; k通过非柯里法可以将高阶一元函数转为为一阶多元函数，此时fx1x2xn记作l(x1, x2, , xn)f .2º.j试构造组合子(P,Q,R)（设其Z）(Godel算子)，(Z)0（取首算子），(Z)1（取中算子），(Z)2（取尾算子），使得对一切C-项P,Q,R,都有(Z)0(P,Q,R)0=P、(Z)1(P,Q,R)1=Q、(Z)2(P,Q,R)2=R及(Z)0,(Z)1,(Z)2)=Z；提示：利用K，I算子。k利用Y算子，求解不动点方程：(P,Q,R)=F(P,Q,R) 并分别给出C-

20、项P,Q,R的解表达式。 提示：利用(P,Q,R)=(P,Q),R)及j的结果。解：j利用已有的求常算子Kºlxyx，此外定义Fºlxyy。构造组合子Zº(P,Q,R) ºlxxPQR，定义(Z)0ºlxyKx(yKZ)(Z)1ºlxyFx(yKZ)(Z)2ºlxxFZ它们满足：(Z)0ºlxyKx(yKZ)=lxKx(lxxPQR(K)=lxKx (KPQR)=lxKx(PQ)=KPQ=P(Z)1ºlxyFx(yKZ)=lxFx(lxxPQR(K)=lxFx (KPQR)=lxFx(PQ)=FPQ=Q(

21、Z)2ºlxxFZ=lxxPQR(F)=FPQR=R(Z)0,(Z)1,(Z)2)=Z kY算子定义如下：Y=lf(lxf(xx) (lxf(xx) 因此，YF=lf(lxf(xx) (lxf(xx)F=lxF(xx)(lxF(xx)=F(lxF(xx)(lxF(xx)=F(YF) 因此，YF是F的不动点，令(P,Q,R)=(P,Q),R)=YF，则根据题j可得： P=(YF)0 ,Q=(YF)1 ,R=(YF)2五.二阶逻辑(10%)REFIden(1)a®a(1)´UGSP(2)"X(X x®Xx)(2)´UG(3)"x

22、"X(X x®Xx)(3), Def£(4) "X(X£X)ANTPremise(1)X£YÙY£X(1) ´PC15(2)X£Y(2), Def£(3)"x(Xx®Yx)(4), "1(4) Xx®Yx(1) ´PC16(5) Y£X(5), Def£(6)"x(Yx®Xx)(6), "1(7) Yx®Xx(4),(7), Def«(8) Xx«Yx(8)

23、 ´UG(9)"x(Xx«Yx)(9), Def=(10) X=Y(1), (10) ´ Syll(11) X£YÙY£X®X=Y(11) ´UGSP(12) "Y (X£YÙY£X®X=Y)(12) ´UGSP(13) "X"Y (X£YÙY£X®X=Y)TRAPremise(1)X£YÙY£Z(1) ´PC15(2)X£Y(2), D

24、ef£(3)"x(Xx®Yx)(4), "1(4) Xx®Yx(1) ´PC16(5) Y£Z(5), Def£(6)"x(Yx®Zx)(6), "1(7) Yx®Zx(4),(7) ´ Syll(8) Xx®Zx(8) ´UG(9)"x(Xx®Zx)(9), Def£(10) X£Z(1), (10) ´ Syll(11) X£YÙY£ Z®X£

25、Z(11) ´UGSP(12) "Y (X£YÙY£ Z®X£Z)(12) ´UGSP(13) "X"Y (X£YÙY£ Z®X£Z)COMPC35(1) aÚØa(1), A2, Syll(2) (aÚØa)Ú(bÚØb)(2), PC4, PC6(3) (ØaÚb)Ú(ØbÚa)(3), def(4)(a®b)&#

26、218;(b®a)(4) ´UGSP(5)"X(X x®b)Ú(b® X x)(5) ´UGSP(6)"X"Y (X x®Yx)Ú(Yx® Xx)(6), "1(7)" x"X"Y (X x®Yx)Ú(Yx® Xx) (7), Def£(8)"X"Y(X£YÚY£X)六.直觉主义逻辑(10%)1º. 在一阶谓词演算的直觉主义系统I中试证:

27、I (a®b)®Øg)®(a®ØØb)®Øg)。证明：I26: (1) ØØ(a®b)«(ØØa®ØØb) I26: (2)ØØ(a®ØØb)«(ØØa®ØØØØb) I6: (3) ØØØb«Øb (2),(3) ´EQ: (4

28、) ØØ(a®ØØb)«(ØØa®ØØb) I6,(4),I9, ´EQ: (5) ØØ(a®ØØb)«(Øb®Øa) (1),I9, ´EQ: (6) ØØ(a®b)«(Øb®Øa) (5),(6) ´EQ: (7) ØØ(a®ØØb)«

29、ØØ(a®b) (7) ´A10: (8) ØØ(a®ØØb)®ØØ(a®b) (7) ´A11: (9) ØØ(a®b)®ØØ(a®ØØb) (8),I9,I6: (10) Ø(a®b)®Ø(a®ØØb) (9),I9,I6: (11) Ø(a®ØØb)&#

30、174;Ø(a®b) (10),(11) ´A12: (12) Ø(a®b)«Ø(a®ØØb) I9: (13)( g®Ø (a®b)« (a®b)®Øg) I9: (14) ( g®Ø(a®ØØb)«(a®ØØb)®Øg) (12),(13),(14) ´EQ: (15) (a®b)®&

31、#216;g)«(a®ØØb)®Øg) (14) ´A10: (16) (a®b)®Øg)®(a®ØØb)®Øg)2º.构造适当的克里普克语义结构Â=W，D，s，使：(a®$xb)®$x(a®b) (条件: xÏfree(a)在此语义结构中是假的。absk1d0k0a解：构造克里普克语义结构Âa，其中:W =k0，k1，=d0 。其哈斯图如右图所示，仅有b ，且a，a

32、。根据定义3.7(5)可易证a®$x b。另一方面，由于a，故由定义3.7(6)及定义3.7(4)可知$x（a® b）于是由定义3.7(5)有（a®$x b）®$x（a® b）。解：构造克里普克语义结构Âa，其中:W =k0，k1，=d0，=d0，d1。其哈斯图如下图所示，有a ，b，a ，b，a ，b。在阶段，由于a 和b，有$xb，加之的论域中只有d0，所以有a®$xb。但是在阶段上有a ，b，所以有a®b，再加上阶段的论域中只有d0，所以有$x(a®b)，即有(a®$xb)®$x

33、(a®b)，结论得证。 k1d0d1k0d0.七.小论文(10%)结合实际，请给出我们所讲过的课程中的非经典逻辑在计算机科学与技术中某一领域的一个精彩而简小的应用。答：非经典逻辑包括模态逻辑，高阶（二阶）逻辑，时态逻辑，时间逻辑，直觉主义（构造性）逻辑及认知（认识）逻辑，多值逻辑，无穷逻辑及模糊逻辑，元逻辑，量子逻辑，道义逻辑，优先逻辑，祈使逻辑，自然逻辑，问题逻辑，信念（相信）逻辑，断定逻辑，内涵逻辑，相干（干涉）逻辑，现代归纳逻辑，语用逻辑，粗值逻辑，程序逻辑及规范逻辑，行为逻辑及意图逻辑。这里举一个非经典逻辑中模态逻辑的应用，即模态逻辑在强Agent社会智能系统中的应用。首先对Agent做一个解释，可以把Agent看成是能够完成被建立起来的一个任务或一系列任务的实体。这些实体具有信念、