离散数学2010年7月自学考试真题及答案

注：1、教师命题时题目之间不留空白；2、考生不得在试题纸上答题，教师只批阅答题册正面部分，若考生须在试题图上作解答，请另附该试题图。3、请在试卷类型、考试方式后打勾注明。（第1页）一、单项选择题（本大题共15小题，每小题1分，共15分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1．下列句子不是．．命题的是（）A．中华人民共和国的首都是北京B．张三是学生C．雪是黑色的D．太好了！2．下列式子不是．．谓词合式公式的是（）A．（x）P(x)→R(y)B．(x)┐P（x）(x)(P(x)→Q(x))C．(x)(y)(P(x)∧Q(y))→(x)R(x)D．(x)(P(x,y)→Q(x,z))∨(z)R(x,z)3．下列式子为重言式的是（）A．(┐P∧R)→QB．P∨Q∧R→┐RC．P∨(P∧Q)D．(┐P∨Q)(P→Q)4．在指定的解释下，下列公式为真的是（）A．(x)(P(x)∨Q(x)),P(x):x=1,Q(x):x=2,论域:{1,2}B．(x)(P(x)∧Q(x)),P(x):x=1,Q(x):x=2,论域:{1,2}C．(x)(P(x)→Q(x)),P(x):x2,Q(x):x=0,论域:{3,4}D．(x)(P(x)→Q(x)),P(x):x2,Q(x):x=0,论域:{3,4}5．对于公式(x)(y)(P(x)∧Q(y))→(x)R(x,y)，下列说法正确的是（）A．y是自由变元B．y是约束变元C．(x)的辖域是R(x,y)D．(x)的辖域是(y)(P(x)∧Q(y))→(x)R(x,y)6．设论域为{1,2}，与公式(x)A(x)等价的是（）A．A(1)∨A(2)B．A(1)→A(2)C．A(1)∧A(2)D．A(2)→A(1)7．设Z+是正整数集，R是实数集，f:Z+→R,f(n)=log2n,则f（）A．仅是入射B．仅是满射C．是双射D．不是函数8．下列关系矩阵所对应的关系具有反对称性的是（）A．001110101B．101110001注：1、教师命题时题目之间不留空白；2、考生不得在试题纸上答题，教师只批阅答题册正面部分，若考生须在试题图上作解答，请另附该试题图。3、请在试卷类型、考试方式后打勾注明。（第2页）C．001100100D．0010101019．设R1和R2是集合A上的相容关系，下列关于复合关系R1R2的说法正确的是（）A．一定是等价关系B．一定是相容关系C．一定不是相容关系D．可能是也可能不是相容关系10．下列运算不满足．．．交换律的是（）A．a*b=a+2bB．a*b=min(a,b)C．a*b=|a-b|D．a*b=2ab11．设A是偶数集合，下列说法正确的是（）A．A,+是群B．A,×是群C．A,÷是群D．A,+,A,×,A,÷都不是群12．设*是集合A上的二元运算，下列说法正确的是（）A．若在A中有关于运算*的左幺元，则一定有右幺元B．若在A中有关于运算*的左右幺元，则一定有幺元C．若在A中有关于运算*的左右幺元，则它们不一定相同D．若在A中有关于运算*的幺元，则不一定有左右幺元13．题13图的最大出度是（）A．0B．1C．2D．314．下列图是欧拉图的是（）15．一棵树的3个4度点，4个2度点，其它的都是1度，那么这棵树的边数是（）A．13B．14C．15D．16二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。错填、不填均无分。16．请写出表示德摩根律的两个命题公式等价定理___________，___________。17．n个命题变元的___________称为小项，其中每个变元与它的否定不能同时出现，但两者必须___________。18．前提引入规则：在证明的任何步骤上都可以___________，简称___________规则。注：1、教师命题时题目之间不留空白；2、考生不得在试题纸上答题，教师只批阅答题册正面部分，若考生须在试题图上作解答，请另附该试题图。3、请在试卷类型、考试方式后打勾注明。（第3页）19．自由变元代入规则是指对某___________出现的个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入，且___________。20．设A=,B={2,4}，则((A))=___________，A×B___________。21．设A={1,2,3,4},A上的二元关系R={1,2,2,4,3,3},S={1,3,2,4,4,2}，则R2S=___________，(R-1)2=___________。22．设代数系统A,·,*是环，则A,·是___________，A,*是___________。23．在Z7-{0},7中，元素2的阶为___________，它生成的子群为___________，其中7为模7乘法。24．设A,≤是一个___________，如果A中任意两个元素都有___________，则称A,≤为格。25．若一条___________中，所有的___________均不相同，称为迹。三、计算题（本大题共6小题，每小题5分，共30分）26．给定论域D={1,2}，f(1)=2,f(2)=1,S(1)=F,S(2)=T,G(1,2)=T,G(2,1)=T,在该赋值下，求式子x(S(f(x))∧G(x,f(x)))的真值。27．请通过等值演算法求┐(P∧Q)→(P∨Q)的主析取范式。28．设A={1,2,3,4}，给定A上二元关系R={1,1,1,2,2,4,4,2}，求R的传递闭包。29．对题29图所示格，找出它的所有的4元子格。30．用矩阵的方法求题30图中结点u1，u5之间长度为2的路径的数目。31．求题31图的最小生成树。四、证明题（本大题共3小题，第32小题8分，第33、34小题各6分，共20分）32．用推理方法证明(A∨B)→(C∧D),(D∨F)→E├A→E。33．证明：设G,·是一个群，则对于任意a,b∈G，必存在惟一的x∈G使得a·x=b。34．设图G有n个结点，n+1条边，证明：G中至少有一个结点度数≥3。注：1、教师命题时题目之间不留空白；2、考生不得在试题纸上答题，教师只批阅答题册正面部分，若考生须在试题图上作解答，请另附该试题图。3、请在试卷类型、考试方式后打勾注明。（第4页）五、应用题（本大题共2小题，第35小题9分，第36小题6分，共15分）35．符合化下列命题，并构造推理证明：三角函数都是周期函数，有些三角函数是连续函数，所以有些周期函数是连续函数。36．两个等价关系的并集不一定是等价关系，试举例说明。一、单项选择题（本大题共15小题，每小题1分，共15分）1.D.2.B3.B4.A5.C6.C7.C8.C9.D10.A11.A12.B13.C14.D15.B二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。错填、不填均不得分。16.QPQP)(QPQP)(17.合取式恰出现其中之一18.引入前提P19.自由出现处处代入20.}},{{，21.{3,3，4,1}22.阿贝尔群半群23.3{1,2,4}24.偏序集最小上界和最大下界25.路边三、计算题（本大题共6小题，每小题5分，共30分）26．给定论域D={1,2}，f(1)=2,f(2)=1,S(1)=F,S(2)=T,G(1,2)=T,G(2,1)=T,在该赋值下，求式子x(S(f(x))∧G(x,f(x)))的真值。x值为1时，S(f(1))=1G(1,f(1))=1则x(S(f(x))∧G(x,f(x)))的值为真。27．请通过等值演算法求┐(P∧Q)→(P∨Q)的主析取范式。)()(QPQP)()(QPQPQPQP)()()()(QPQPQP)3,2,1(注：1、教师命题时题目之间不留空白；2、考生不得在试题纸上答题，教师只批阅答题册正面部分，若考生须在试题图上作解答，请另附该试题图。3、请在试卷类型、考试方式后打勾注明。（第5页）28．设A={1,2,3,4}，给定A上二元关系R={1,1,1,2,2,4,4,2}，求R的传递闭包。0010000010000011RM10000000001010112RM00100000100010113RM10000000001010114RM3分1010000010101011432RRRRMMMM}4,4,2,4,4,2,2,2,4,1,2,1,1,1{)(Rt29．对题29图所示格，找出它的所有的4元子格。{2,4,6,12}{1,2,3,6}{1,2,4,12}{1,3,6,12}30．用矩阵的方法求题30图中结点u1，u5之间长度为2的路径的数目。1111010001100111010111110)(GM4122322220323213223141223)(2GM则u1，u5之间长度为2的路径恰有4条。注：1、教师命题时题目之间不留空白；2、考生不得在试题纸上答题，教师只批阅答题册正面部分，若考生须在试题图上作解答，请另附该试题图。3、请在试卷类型、考试方式后打勾注明。（第6页）31．求题31图的最小生成树。1V3V2V1V6V4V5V746523注意最小生成树不唯一。四、证明题（本大题共3小题，第32小题8分，第33、34小题各6分，共20分）32．用推理方法证明(A∨B)→(C∧D),(D∨F)→E├A→E。（1）ACP（2）BAIT)1(（3）)()(DCBAP（4）DCIT)3)(2(（5）DIT)4(（6）FDIT)5(（7）EFD)(P（8）EIT)7)(6(（9）EACP33．证明：设G,·是一个群，则对于任意a,b∈G，必存在惟一的x∈G使得a·x=b。证明：注：1、教师命题时题目之间不留空白；2、考生不得在试题纸上答题，教师只批阅答题册正面部分，若考生须在试题图上作解答，请另附该试题图。3、请在试卷类型、考试方式后打勾注明。（第7页）Gba,。a有逆元Ga1。由封闭性，Gba1bbebaabaa)()(1134．设图G有n个结点，n+1条边，证明：G中至少有一个结点度数≥3。用反证法：若每个结点度数均小于等于2，则总度数小于等于2n总边数小于等于2n/2=n，与已知矛盾。五、应用题（本大题共2小题，第35小题9分，第36小题6分，共15分）35．符合化下列命题，并构造推理证明：三角函数都是周期函数，有些三角函数是连续函数，所以有些周期函数是连续函数。是三角函数xxP:)(。是周期函数xx:)(Q。是连续函数xx:)(R。前提：))(Q)(P)((xxx，))(R)(P)((xxx结论：))(R)(Q)((xxx证明如下（1）))(R)(P)((xxxP（2）)a(R)a(P)1(ES（3）)a(PT(2)I（4）))(Q)(P)((xxxP（5）)a(Q)a(P)4(US（6）)(QaIT)5)(3(（7）)(RaIT)2(（8）)(Q)(aaRIT)7)(6(（9）))(R)(Q)((xxx)8(EG36．两个等价关系的并集不一定是等价关系，试举例说明。注：1、教师命题时题目之间不留空白；2、考生不得在试题纸上答题，教师只批阅答题册正面部分，若考生须在试题图上作解答，请另附该试题图。3