离散数学试卷及答案

考试课程考试日期课程号教师号任课教师姓名考生姓名年级专业请将答案填写在答卷纸上。1.命题公式A是可满足式当且仅当A的标准合取范式至少包含一个最大项。3.公式Vxp(gx,y,z+a)在个体域为实数集合，个体常元a=1，二元函数fx,y=x*y,二元谓词1.下列属于命题的是。A外面下雨，请带伞。B2020年无人驾驶汽车将大行其道。C我在说假话。Dx>y2.命题p:北极熊生活在北极。q:企鹅生活在南极。r:企鹅生活在北极。下列命题为真的是。ApΛq→rBpVq→rCp→q→r3.下列式子不成立的是。Cp→q,p→r→q→rDp→q,p艹r→p→r4.设个体域是整数集合，用自然语言表达下列各式后，真值为0的是。5.令个体域为全总个体域，p(x):x是人工智能，Q(x):x是人类，R(x,y)：x下围棋比y厉害。则“有些的人工智能下围棋比所有人类都厉害”可以符号化为。6.下列关于谓词公式判定说法正确的是。A仅(1)为永真式B均为永真式C仅(4)为可满足式D上述没有永假式7.下列命题不成立的是。8.A,B,C,D是任意集合，下列成立的是。9.下列关于二元关系性质的描述，错误的是()A一个关系可以既不是自反关系又不是反自反关系。B一个关系可以既是对称的又是反对称的。C一个关系可以既不是对称的又不是反对称的。D全域关系是自反的，是对称的，不是反对称的。10.下列不属于等价关系的是()B平面上直线集合L上的平行关系。CR1，其中R是集合A上的等价关系。D在整数集合上定义的模m同余关系。2.（11分）赵泽是一名大三的学生，暑期想申请一份学校实验室的工作。(I)如果赵泽具备一定的Java开发能力而且不考研，就可以获得这份实验室的工作。(II)赵泽具备一定的Java开发能力。(III)如果赵泽考研，他会去上考研培训班。(IV)他没有上考研培训班。P:赵泽具备一定的Java开发能力，q：赵泽考研，r：赵泽获得这份实验室的工作，s:赵泽上考研培训班3.（9分）请判断下列谓词公式是永真式、永假式还是可满足式，并说明理由。5.（10分）请用谓词逻辑的演绎推理证明：6.（每个2分，共12分）设集合A={a,b,c,d}，R和S是A上的二元关系：(1)R是否满足反对称，传递。(2)求包含S的最小关系，使得它是自反和传递的。明R是一个等价关系。A卷答案pqr000000001001010111011111100100101101110000111001III(I)如果赵泽具备一定的Java开发能力而且不考研，就可以获得这份实验室的工作。r：赵泽获得这份实验室的工作，s:赵泽上考研(2)赵泽能够获得这份实验室的工作(3)求关系矩阵MR-S(5)求关系矩阵Ms(R)(6)求关系矩阵Mt(R-1)MR-S=l丨MMt=l丨R证明2分）要证R是一个等价关系，需证明R满足自反、对称、传递的性质。因此<<u,v><x,y>>∈R，R对称有xv=yu,且un=vm,得n=vm/u则xn===ym因此<<x,y><m,n>>∈R，R传递考试课程考试日期课程号教师号任课教师姓名考生姓名年级专业请将答案填写在答卷纸上。1.命题A含有4个命题变元，A的标准析取范式由10个最大项组成，则A有10个成真赋值。4.令个体域为全总个体域，p(X):x是计算机专业毕业生，Q(X):x是非计算机专业毕业生，R(X,y)：x的起薪比y高。则“并不是所有的计算机专业毕业生起薪都比非计算机专业毕业生高”可以符号化为5.全域关系是自反的，不是反自反的，是对称的，不是反对称的，是传递的。1.下列属于命题的是。A你喜欢计算机专业吗？B如果外星人存在，那么地球文明终会灭亡。2.当p：0，q：1，r:1时，下列命题为假的是。Cp艹r→qDp→qVr3.如果小赵去旅游，那么小钱、小孙和小李将一起去。如果上述是真的，那以下哪项也是真的？A如果小赵没去旅游，那么小钱、小孙、小李三人中至少有一人没去。B如果小赵没去旅游，那么小钱、小孙、小李三人都没去。C如果小钱、小孙、小李都去旅游，那么小赵也去。D如果小孙没去旅游，那么小赵和小李不会都去。4.下列谓词公式是永假式。5.下列不正确的是()7.下列关于谓词公式演绎推理说法正确的是。A仅(5)错了B上述推理正确AR-1是传递的BR是自反的CR是对称的9.R是从集合A到B的关系，S1S2是从集合B到C的关系，T是从集合C到D的关系是错误的。10.R和S是集合A上的关系，下列说法错误的是()AR和S是传递的，则R∩S和RUS也是传递的。BR和S是自反的，则R∩S和RUS也是自反的。CR和S是对称的，则R-S，R-1和S-1也是自反的。DR和S是反自反的，则R∩S和RUS也是反自反的。4.（10分）请用谓词逻辑的演绎推理证明：5.（每个2分，共10分）设集合A={1,2,3,4}，R和S是A上的二元关系：(1)R的等价闭包y*（即包含R的最小的等价关系6分）(3)画出y*的关系图（3分）7.（10分）N是自然数集合，在N上定义二元关系R，(1)证明R是一个等价关系。一判断题（每小题2分，共10分）BCDBBCDDBApqr000001001011010001011011100100101111110011111011标准析取范式=Ⅲ000ΛⅢ00IΛⅢ0I0ΛⅢ0IIΛⅢI0IΛⅢII0ΛⅢIIIR={<1,2>,<2,3>,<3,4>,<4,2>}s={<1,3>,<2,3>,<4,1>,<4,4>}(1)求关系矩阵MR⊕S(2)求关系矩阵MR∪S-1(4)求关系矩阵Ms(R—S)(5)求关系矩阵Mr(Rc)(1)R⊕S={<1,2>,<1,3>,<3,4>,<4,1>,<4,2>,<4,4>}(2)R∪S—1={<1,2>,<1,4>,<2,3>,<3,1>,<3,2><3,4>,<4,2>,<4,4>}<4,1>,<4,3>,<4,4>}MR⊕S=l丨MR∪S-1=l丨Ms=l丨Mr=l丨证明2分）要证R是一个等价关系，需证明R满足自反、对称、传递的性质。3.∀x(A(x)∨B(x))⟹∀xA(x)∨∀xB(x)二选择题（每小题2分，共20分）A、pΛqVrC、p艹r→qB、A⊕B=A⊕C⇒B=CD、A∪C=B∪C⇒A=B14.设R是集合A上的关系，下列说法错误的是()A15.设R和S是集合A上的关系，下列说法错误的是()三综合题（共70分）(1)求关系矩阵MR-S(7)求传递闭包的关系矩阵Mt(R)1×2×3×4√5√二选择题（每小题2分，共20分）6A7C8C9DBAADAC（1）用等价演算法根据如下步骤给分=(¬r→(¬p∨(¬q∧r))∧((¬p∨(¬q∧r))→¬r)=(r∨¬p∨(¬q∧r))∧(¬(¬p∨(¬q∧r))∨¬r)=(r∨¬p∨(¬q∧r))∧((p∧(q∨¬r))∨¬r)=((r∨(¬q∧r))∨¬p)∧((p∧(q∨¬r))∨¬r)=(r∨¬p)∧((p∧(q∨¬r))∨¬r)中间过程（2分）=(r∨¬p)∧(p∨¬r)∧(q∨¬r)合取范式（1分）=(p∨q∨¬r)∧(p∨¬q∨¬r)∧(¬p∨q∨r）∧(¬p∨q∨¬r)∧(¬p∨¬q∨r）=(r∧p∧q)∨(¬p∧¬r)析取范式（1分）=(¬p∧¬q∧¬r）∨(¬p∧q∧¬r）∨（p∧q∧r）=m000∨m010∨m111标准析取范式（2分，错一个扣一分）（2）用真值表法，列对真值表给4分，求出标准析取范式2分，求出标准17.（10分）请用谓词逻辑的演绎推理证明：6.¬R(a)T(4)9.Q(a)T(5)(8)10.Q(a)∧¬R(a)T(6)(9)评分标准：错一步扣一分，扣完为止。（1）p∨q,p→¬r,s→¬t,¬s→r,t（2分）（3）推理过程（8分，每错一步扣一分，扣完为止）3）¬sT(1)(2)4）¬s→rP5）rT(3)(4)8）pVqP9）qT(7)(8)设p:A去，q:B去,r:C去，s:D去则命题符号化为选派方案有：答案中每错1个地方扣一分，扣完为止。因为R是自反的，对称的，传递的，所以R是等价关系。（1分）6.A∪C=B∪C⇒A=B五选择题（每小题2分，共20分）A、pΛqVrD、p→q,p艹r→p→rA、R是传递的B、(A⊕B)⊕C=A⊕（B⊕C）E、A=B⇒A∪C=B∪C14.设R是非空集合A上的等价关系，下列说法错误的是()A、R和S是自反的，则R-S也是自反的B、R和S是对称的，则R。S也是对称的C、R和S是传递的，则R∪S也是传递的D、R和S是反自反的，则R-S也是反自反的六综合题（共70分）(10)求关系矩阵MR-S(16)求传递闭包关系矩阵Mt(R)评分标准：（1）用等价演算法求时，中间过程2分，求出析取范式1分，求出标准析取范式（2分，错一个扣一分求出合取范式1分，求出标准合取范式（2（2）用真值表法求时，列对真值表给4分，求出标准析取范式2分（错一个扣2.Vx¬Q(x)E(1)3.¬Q(y)US(2)评分标准：错一步扣一分，扣完为止。1√2√3×4×5√二选择题（每小题2分，共20分）6B7A8B9CCCAACDpqr000010001111010010011010100010101111110001111010标准析取范式为：=m001∨m101∨m110标准合取范式为：=M000∧M010∧M011∧M100∧M111（1）(p∧¬q)→r,p,q→s,¬s(2分，错一个扣一个，扣完为止)（2）王平犯了谋杀罪（2分）（3）推理过程（8分，每错一步扣一分，扣完为止）6）(p∧¬q)→rP7）rT(5)(6)1910分）.=(A1∧¬B2∧C2∧¬D4∧A2∧¬D4)∨(A1∧¬B2∧C2∧¬D4∧¬A2∧D4)∨(¬A1∧B2∧¬C20.（每个2分，共20分）答案中每错1个地方扣一分，扣完为止。Yx,y∈A,xRy⇔x≤y或y≤x（2）对Yx,y∈A,若xRy⇒x≤y或y≤x⇒y≤x或x≤y⇒yRx,（3）Yx,y，z∈A,若xRy且yRz⇒x≤y或y≤x且y≤z或z≤y但是，若x≤y且z≤y时，却无法推出x和z之间的包含关系。也就是说，若xRy且yRz时，不一定有xRz因为R是自反的，对称的，但不是传递的，所以R不是等价关系。（1分）A0501520(6)令p：我在听课，q：我在看小说，则命题“我不能一边听课，一边看小说。”的符号化为()，（）}）；1×2√3×4√5×6D7C8D9DAACCBBpqr00000010010001010000101111001000100101010011001001111111P(1)Huffman算法的基本步骤3分）(2)最优二叉树4分）(2)总权值1分）A0501520(C)A∧(B∨C)=(A∧B)∨(A∧C)(D)┒(A∧B)，（则R是G上的等价关系。(3)¬(¬P(a)∨R(a))ES规则：(2)(4)P(a)∧¬R(a)(8)P(a)→Q(a)1×2×3√4×5√6D7D8A9ABBBCCDpqrp→¬p¬q¬r¬q∧¬r(¬q∧¬r)0000111111100101110000010011010000111110000010000011111101000100111100000101111111000011S*G。2)(正确得2分)枝(5，8)所对应的基本割集{（4,95,75,85,96,1）}(1)Huffman算法的基本步骤3分）(2)最优二叉树4分）(2)总权值1分）成绩A、张华明年9月要么去读研究生，要么去工作。三、综合题(共70分)12345678912345×√×√√6789ABCAAABDCCDC2.rP规则2=a2*b2101211011100），成绩符号化为：¬q→p。三、综合题(共70分)12345678912345对对错对对6789CACCCDDDp↔¬q标准合取范式：M00⋀M11（2）¬rP（3）¬qT(1)(2)（4）pPCPUG(5)-1=7a5b\4d6\4d22/c7 2/八477565242考试课程离散数学考试日期2022年月日成绩课程号A0501520教师号任课教师姓名余日泰、袁友伟、周丽、吴向阳、陈溪源、李玉、方启明、程世超考生姓名年级专业计算机类请将答案填写在答卷纸上。一、判断题（每小题2分，共10分）(2)┒∀xP(x)→(∀xP(x)→┒∃xQ(x))是永真式。()二、选择题（每小题2分，共20分）(6)下列语句中是命题。(D)我在撒谎。(A)所有志愿者都要整日穿戴防护服。(B)所有在校学生都是志愿者。(C)某些志愿者不用穿防护服。(D)某些在校同学不是志愿者。后得到生成树。三、综合题(共70分)(16)(8分)计算命题公式p∨q∧r→p∧q∨r的标准析取范式与标准合取范式。(17)(10分)请用谓3)(R-S)的传递闭包的关系(20)(10分)在城市互帮建设中，为更好组织城市互帮进程，n个城市的代表共同参加一场研讨会主办方可以为这n位代表安排安排一次圆桌会议以满足每个人都认识两旁的人。考试课程离散数学考试日期2022年月日成绩课程号A0501520教师号任课教师姓名余日泰、袁友伟、周丽、吴向阳、陈溪源、李玉、方启明、程世超考生姓名年级专业计算机类12345678920（共10分）21（共10分）22（共8分）考试课程离散数学考试日期2022年月成绩课程号A0501520教师号任课教师姓名袁友伟、周丽、陈溪源、李玉、方启明考生姓名年级专业计算机类1√2√3√4×5×6B7C8C9ACABACD1)命题公式p∨q∧r→p∧q∨r的真值表计算如下pqrq∧rp∧qp∨(q∧r)00000001001000010100000101110111100001001010011111001111111111112)标准析取范式为m000∨m001∨m010∨m011∨m101∨m110∨m111分。设n位代表的集合为图G的顶点集合，若两人相识，则其间连一条边。这样得到的图G是人的相识图。显然是一个简单图，图中顶点的度恰好表示该人认识的其他人的个数。利用图G，原题就抽象为下面的图论问题：在具有n个顶点简单图G种，若vu,vev，l士v，其余的n-2顶点都与u或v相邻，则G中存在哈密尔顿路或哈密尔顿回路。（1）若u与v认识，则d(u)+d(v)之2+(n-2)=n，（2）若u与v不认识，则对任意的顶点w，当w*u且w*v时，u与v都认识w。否则若u不认识w，即v和w都不认识u，从而v和w合起来至多认识其余的n-3个人，矛盾。于是u与v都认识w，由W的任意性可知d(u)+d(v)二2(n-2)当n≥4时，2(n-2)之n，于是无论认识与否都有d(u)+d(v)之n根据定理知G中存在哈密尔顿回路，所以这n位代表能排成一个圆圈，使得每个人都认识两旁的人。考试课程离散数学考试日期2022年月日成绩课程号A0501520教师号任课教师姓名余日泰、袁友伟、周丽、吴向阳、陈溪源、李玉、方启明、程世超考生姓名年级专业计算机类请将答案填写在答卷纸上。一、判断