北京大学 离散数学 2009下学期期中考试试题及答案

2009下学期离散数学期中考试试题姓名 学号 计分总分(21)(22)(23)(24)(25)(26)一选择题(20%):【将选择的答案填入下而表格屮】(2)(3)(4)(5)(6)(7)(8)(9)(10)(1)在联结词八、V、¥、中，具有可结合性的有( )个⑷2 (B)3 (C)4 (D)5命题形式pVqAr的对偶式是pVqAr(B)pAqVr(C)pA(qVr)(D)-^pA^qV-^r)下而是有关推理的一些概念，不正确的是( )：—个小一致的推理一定是正确的：呆一个推理形式是AiVA2VA3=>B.A!、A2、A3就是推理的前提。然推理系统P中进行证明时，在证明的任何一步，都nJ*以引入任何的前提。任何证叫必须在一个推现系统中进行，而且耑逛应用相应的证明方法。R和S是集合A上的W个关系，下面命题真值为真的是：( )R和S是自反的，则R«S也是自反的;R和S是对称的，则R°S也是对称的;R和S是反对称的，则RoS也是反对称的：R和S是传递的，则R=S也是传递的。有关关系的逆关系的说法不正确的是：( )等价关系和相容关系的逆关系就是其木身：«序关系的逆关系仍然是偏序关系：伞序关系的逆关系仍然是个序关系：tl序关系的逆关系仍然S良序关系；下而是一些运算的分妃性表达式，不成立是( )An(B㊉C)=(Ar^B)㊉(AnC)(B) (B㊉C)=(AuB)㊉(AuC)(C)(A㊉B)XC=(AXC)㊉(BXC)(D)(A—B)XC=(AXC)—(BXC)下而( )不是命题：VxP(x)(B)3xP(x)(C)3x(P(x)VP(y))(D)3x3y(P⑻VP(y))下而说法不止确的是( )：公式A是可满足式，则A的任何柃换实例仍然是可满足式：公式层次S用米描述公式g杂性的一个11个命题变项构成的各种命题形式，小M的S.值表有限，只有个。从范式现论米看，pAq可能足简笮合取式、最小项，也可能S合取范式。SA是以空集为唯一元素的集介，|fljB=p(p(A)).则卜‘而不成立的是

0cB(B)0eB(C){0，{{0}}}cBD{0,{{0}}}eBf:A-B是可逆的，充耍条件是(A)A=B (B)A和B具有相冋的基数(C)f是满射的(D)f是双射的二填空题(20%):【将相应的答案填入卜而表格屮】(11)(12)(13)(14)(15)(16)(17)(18)(19)(20)推理理论中的证叨方法有CP规则，有时也称为 定理。A上存在二元关系，冋时具有H反性和非H反性的，A是 “W为可满足穴的任何替换实例是可满足式，所以承言式的、矛质式的任何替换实例相应一定是重言式、矛盾式”，该命题的真值是 命题逻辑的范式理论的u的在r构建命题形式的标准形式，而具有唯一性的标准形式是 。个体域{1，2}，谓词公式Vy3x(x+y=4)的真位是 A={1，2,3,4,5}，A上的二元关系中有 个等价关系。偏序集＜A，哈斯阁如阁所示，B是A的子集，B={3,6}B的上确界是 每个人的外泔付都是他付亲的付亲。设:个体域:人;P(x，y):x是y的外祖母，Q(x.y):x是y的母亲，则逻辑符号化为: 一个n个元素的集合A上的偏序关系，元素最多有 个。谓同逻辑的合式公式屮不#在『1巾变元，该公式被称为 的。 三根据要求解答:【(21)〜(24)必做，(25)〜(26)任选一题，写在答题纸上】(12%)某三元哀值函数f(p，q.r)为:f(0,0,0)=0,f(0,0,1)=1,f(0,1，0)=0,f(0,1,1)=1,f(l,0,0)=1,f(L0,1)=1,f(l,1,0)=0.f(l,1，1)=1,试用仅介联结词o的命题形式來表示f。(15%)每个旅客成少头等舱成二等舱，毎个旅客当且仅当他富裕时才少头等舱，有些旅客富裕但并非所有旅客富裕，所以有些旅客坐二等舱。(15%)己知&和1^2都是A上等价关系，且RjoR2=R2。Ri，证明Ri，Rz也是A上的等价关系。(9%)用特征函数证明下式成立的充要条件：A㊉B=0。(9%)己知A上的二元关系R满足Rn=R,则R，R2，R3，."，Rn中的哪个可确定具有nJ*传递性。(9%)'4出{a，b,c}I•.的所有满足Pf=IA的函数。2009下学期离散数学期中考试试题答案姓名 学号 计分—总分(21)(22)(23)(24)(25)(26)一选择题(20%):【将选择的答案填入下而表格屮】(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)CCBADBCADD(1)在联结词八、V、¥、中，具有可结合性的有( )个⑷2 (B)3 (C)4 (D)5命题形式pVqAr的对偶式是(A)pVqAr(B)pAqVr(C)pA(qVr)(D)-^pA(->qV-<r)下而是有关推理的一些概念，不正确的是( )：—个小一致的推理一定是正确的：呆一个推理形式是AiVA2VA3=>B,A!、A2、A3就是推理的前提。(c)在H然推理系统p中进行证明时，在证明的任M—步，都II]*以引入任何的前提。(D)任何证叫必须在一个推理系统中进行，而且耑逛应用相应的证明方法。R和S是集合A上的W个关系，下曲命题K值为真的是：( )R和S是自反的，则R，S也是自反的;R和S是对称的，则RoS也是对称的;R和S足反对称的，则RoS也是反对称的：R和S是传递的，则R=S也是传递的。有关关系的逆关系的说法不正确的是：( )等价关系和相容关系的逆关系就是其本身：偏序关系的逆关系仍然是偏序关系：伞序关系的逆关系仍然是仝序关系：tl序关系的逆关系仍然S良庁关系；下而是一些运算的分K性表达式，不成立是( )(A)An(B㊉C)=(Ar^B)㊉(AnC)(B) (B㊉C)=(AuB)㊉(AuC)(A㊉B)XC=(AXC)㊉(BXC)(D)(A—B)XC=(AXC)—(BXC)下而( )不是命题：(A)VxP(x) (B)3xP⑻(C)3x(P(x)VP(y)) (D)3x3y(P⑻VP(y))下而说法不正确的是( )：公式A是可满足式，则A的任何柃换实例仍然是可满足式：公式层次S用米描述公式g杂性的一个11个命题变项构成的各种命题形式，小M的ft值表有限，只有^个。从范式现论來看，pAq可能足简単合取式、最小项，也可能S合取范式。SA是以空集为唯一元素的集介，|fljB=p(p(A)).则卜‘而不成立的是

(A)0cB(B)0eB(C){0，{{0}}}cBD{0，{{0}}}eBf:A-B是可逆的，充®条件是(A)A=B (B)A和B具有相同的基数(C)f是满射的(D)f是双射的二填空题(20%):【将相应的答案填入卜而表格中】(")演绎(12)0(13)T(14)主合取范式、主析取范式(15)F(16)67(即划分数)(17)6(18)VxVy(P(x.y)^3z(Q(x,z)AQ(z，y))(19)n(n+l)/2(20)封闭推理理论中的证明方法有CP规则，有时也称为 定理。A上存在二元关系，冋时具有H反性和非H反性的，A是 “W为可满足忒的任何替换实例是可满足式，所以承言式的、矛盾式的任何替换实例相应一定是重言式、矛盾式”，该命题的真值是 命题逻辑的范式理论的u的/i:r构建命题形忒的标准形式，而具有唯一性的标准形式是 个体域{1,2}，谓词公式Vy3x(x+y=4)的真位是 A={1，2,3,4,5}，A上的二元关系中有 个等价关系。偏序集＜A，＜＞哈斯W如W所示，B是A的子集，B={3,6}，B的上确界每个人的外祖付都是他付亲的母亲。设:个体域：人;P(x，y):x是y的外祖母，Q(x，y):x是y的母亲，则逻辑符号化为: 一个n个元累的集合A上的偏序关系，元素最多有 个。诮同逻辑的合式公式屮不#在flltl变元，该公式被称为 的。 三根据要求解答:【(21)〜(24)必做，(25)〜(26)任选一题，写在答题纸上】(12%)某三元哀值函数f(p，q.r)为：f(0.0,0)=0,f(0,0,1)=1,f(0,1，0)=0,f(0,1,1)=1,f(l,0,0)=1,f(L0,1)=1,f(l,1,0)=0.f(l,1，1)=1,试用仅介联结词o的命题形式來表示f。(15%)每个旅客成少头等舱成二等舱，毎个旅客当且仅当他富裕时才少头等舱，有些旅客宫裕但并非所有旅客富裕，所以有些旅客坐二等舱。(15%)己知&和R2都是A上等价关系，且卽R2=R2°Ru证明Ri。R2也是A上的等价关系。(9%)用特征函数证明下式成立的充要条件：A㊉B=0。(9%)己知A上的二元关系R满足Rn=R,则R,R2，R3，."，Rn中的哪个可确定具有nJ*传递性。(9%)写出{a，b，c}I•.的所有满足f°f=IA的函数。(21)解：因为成真赋值较多，较为简便的是采川主合取范式，得到一种形式fo(pVqVr)A(pV-^qVr)A(-.pV-^qVr)O(pVqVr)A(-iqVi.)<=>((pVq)A->q)VrO(pA^q)Vr (可以用卡诺图直接得到)<=>-n(-,pVq)Vr(22)解：符号化P(x):x坐头等舱，Q⑻:x坐二等舱，R(x):x富裕；个体域：所有旅客。前提：Vx(P⑻vQ⑻)，Vx(P(x>~>R(x))，彐xR(x)a-iVxR(x)：结论：3xQ(x)证明：TOC\o"1-5"\h\z彐xR(x)a-iVxR(x) P-.VxR(x) T(1)I3x-,R(x) T(2)E-.R(a) T(3)£ZVx(P(x)<->R(x)) PP(a)^>R(a) T(5)67(P(a) R(a))a(R(a) Q(a))T(6)EP(a)R(a) T(7)I-P(a) T(4)(8)IVx(P(x)vQ(x)) PP(a)vQ(a) T⑽W⑽ P(a)vQ(a) T(H)IQ(a) T(9)(12)I3xQ(x) T⑽沉(23)证明等价关系，就是证明JC具有H反、对称、传递性质。久和^是等价关系，所以都具有H反、对称、传递性。(A)自反性：对于任何的xEA.因为R:和R:都是H反的，<x,x>ER:，<x，x>eR:，所以〈X，x>eR1R;,具有A反性。B对称性：对丁•任何的x，yEA，<x，y>eR.°R;3<x,y>£RlcR2=R:°R:=>3t(<X,t>^R±A<t,y>FR:)(如果不清楚用还是O,则尽可能用=>3t«t,x>eR：a<y,t>eR:)(R1和R2是对称的)<y,x〉ER，R2R，R:具有对称性。C可传递性：对于任何的x，y,zEA.如果<x,y>eRx0R:,<y,z>^R2则<x,z>GR^R2oR.cR2=RioRjoR,-^Cl:直接应用关系式Ri^RiCR：因为R,,R:是可传递的，所以R”R2-R2cr2<x,z〉E么。!^。^。!^彐t(<x,t>GR：°R1a<t,z>GR;oR;)=>3t«x,t>eRta<t,z>eR2)(因为RrR:R”R2^R2CR:)=><x,z>eRxcR,C2:也可按照步骤一步一步的证明：<x,z〉EHR，R:=>彐t(<x,t>GRx°Ria<t，z>ER:°R：)=>3t(3ti«x,ti>^RiA<ti,t>GRi)A彐t：(<t,t:>GR;A<t：,Z>GR;))=>3t«x,t>GR;A<t,z>eR,)(因为RpR2是可传递的)=><x,z>^Ri°R2)R：°R：具有可传迎性。所以匕见是等价关系。XAeB=0XAuB-A^B=0Xa+Xb-XaXb—(Xa+Zb—XaZb)XaXb=0Xa+Xb-XaXb-XaXaXb+XbXaXb~XAXbXaXb=0Xa+Xb一XaZb一XaXb+XaZb一XaZb=0XaZa+Xb/b-XaXb-Xa/b=0(Xa-Xb)2=0Xa=XbA=B没 可传递性，则RX«RX^Rxx是1，2