《离散数学（微课版）》期末试卷（含答案）

学院系别姓名学号………密………封………线………以………内………答………题………无………效……第5页共6页电子科技大学二零二至二零二学年第二学期期末（B卷）课程考试题（分钟）考试形式：考试日期年月日一二三四五六七八九十总分评卷教师一、选择题（1～15是单选，16～20是多选，单选每小题1分，多选每小题2分，共计25分）1.下列公式中，那一个是永假的（ ）。 A、(P∧Q)→P B、(P∨Q)→P C、P→(P∨Q) D、((P∧Q)→Q）2.下列公式中，哪一个不是析取范式（ ）。 A、P∨Q B、P∧Q C、(P∨Q) D、(P∧Q)3、如果命题公式G=P∧Q，则下列之一哪一个等价（）。A、G=(P→Q) B、G=(P∨Q) C、G=(P→Q) D、G=(P→Q)4、设X、Y是两个集合|X|＝m，|Y|＝n，则从X到Y可产生（）个不同的函数。A、nm B、mn C、m×n D、2m×n5、设G是具有n个结点的有向完全图，则G中有（）条边。A、n2 B、n(n－1) C、2n(n－1) D、6、下列公式中，是永真式的是()。A、P∨1 B、P→T C、P∨T D、P∧T7、下列公式中，（）是析取范式。A、(P∧Q) B、(P∨Q) C、(P∨Q) D、(P∧Q)8、下面哪一种格不是特殊格（）。A、子格 B、分配格 C、模格 D、有界格9、5个结点7条边的简单图共有（）种。A、2 B、3 C、5 D、710、下列图中，（）是平面图。 A、B、 C、 D、11、每个无向树至少有（）片树叶。A、1B、2 C、3 D、412、每个无限循环群有（）个生成元。A、1 B、2 C、3 D、413、设R是集合A＝{1,2,3}上的二元关系，R＝{<2,1>,<2,3>,<1,3>},则下列（）不成立。A、R是自反关系 B、R是反自反关系 C、R是反对称关系 D、R是传递关系14、设G是一个18阶群，a是G中任意一个元素，则a的周期一定不是（）。A、2 B、4 C、9 D、615、命题公式A与B是等价的，是指（D）。A、A与B有相同的原子变元 B、A与B是可满足的C、当A的真值为真时，B的真值也为真 D、A与B有相同的真值16、设R、S是集合A上的关系，则下述（ ）不一定成立。A若R、S传递，则传递 B若R、S对称，则对称C若R、S自反，则自反 D若R、S反自反，则反自反5142376E若514237617、下列图中，那些是右图的强分图。（）1423142314231436565A B C D E18、下列图中，存在完美匹配的图是（）19、下列哈斯图中，不是格的有（）。 A B C D E20、若<G,*>是一个群，则运算“*”不一定满足（）。A、交换率 B、消去律 C、幂等律 D、分配律二、名词解释（每小题3分，共15分）1、什么叫谓词公式的解释。2、试述函数中满射函数的定义。3、叙述极大连通分支的定义。4、试述代数系统中子代数的定义。5、试述格的定义三、判断分析改错题（每小题5分，共10分）1、设<Z，+>是一个代数系统，Z是正整数集合，“＋”是一般的加法运算，Z上的函数f为：f(x)=5x-7，则函数f能构成代数系统的自同构吗？为什么？2、设A，B，C为任意命题公式。已知，问吗？bacdefgbacdefg1、设集合A＝｛a,b,c,d,e,f,g｝上的偏序关系如右图所示,求A的最大元、最小元、极大元和极小元，并求A的子集B＝｛a,b,c,d｝的上确界和下确界。2、设个体域D={a,b,c}，消去以下各式中的量词：（1）；（2）3、求命题公式(PQ)R的主析取范式和主合取范式。4、设是群，运算“”定义如下：，有：试验证该代数系统是否是一个循环群？如是，请求出该循环群的全部生成元，幺元，每个元素的逆元。五、综合证明题（共18分）将下面的推理符号化，然后用逻辑推理的方法证明之。 1、每个在学校读书的人都获得知识。所以如果没有人获得知识就没有人在学校读书。（个体域是人的集合）。2、设<G,*>是群，H，K是其子群，在G上定义二元关系R：使得。证明：R是G上的等价关系.答案1～15是单选，16～20是多选，单选每小题1分，多选每小题2分，共计25分）1.D2.C3、B4、A5、B6、A7、D8、B9、B10、C11、A12、B13、A14、B15、D16、A,E17、D,E18、D19、A,B,E20、A,C,D二、名词解释（略）三、判断分析改错题（每小题5分，共10分）1、答：不是。显然，Z上的函数f既是单射又是满射。但是对，有显然，，即不满足同态条件，因此函数f不能构成代数系统的自同构2、设A，B，C为任意命题公式。已知，问吗？答：不一定。因为当，时，有同样的真值T，此时，成立，但是，却不成立。四、计算题（每小题8分，共32分）1、最大元最小元极大元极小元上界下界上确界下确界gdgdgdgd2、解：（1）（2）3、解：方法1PQRP→Q(P→Q)R0001000111010100111110001101001101011111主析取范式为（使公式为1的解释所对应的极小项的析取）：(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)主合取范式为（使公式为0的解释所对应的极大项的合取）：(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)方法2：(P→Q)R=((P→Q)→R)∧(R→(P→Q))=((P→Q)∨R)∧(R∨(P→Q))=((P∨Q)∨R)∧(R∨P∨Q)=(((P)∧Q)∨R)∧(P∨Q∨R)=((P∧Q)∨R)∧(P∨Q∨R)=(P∨R)∧(Q∨R)∧(P∨Q∨R)=(P∨(Q∧Q)∨R)∧((P∧P)∨Q∨R)∧(P∨Q∨R)=(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)=(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R) 主合取范式=M0∧M2∧M5∧M6=m1∨m3∨m4∨m7=(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R) 主析取范式4、证明：a,b∈I，显然a*b=a+b+2∈I，所以“*”关于I是封闭的。a,b,c∈I,(a*b)*c=(a*b)+c+2=(a+b+2)+c+2=a+(b+c+2)+2=a+(b*c)+2=a*(b*c),所以“*”是可结合的。存在-2∈I，使得a∈I，都有(-2)*a=a*(-2)=a+(-2)+2=a，所以-2是<I,*>的幺元。a∈I，存在-a-4∈I，使得a*(-4-a)=(-4-a)*a=a+(-4-a)+2=-2，所以-4-a是a的逆元。故<I,*>是群。设a是<I,*>的生成元，则存在i,j∈I,使得1＝ai＝ia+2(i-1)，2＝aj＝ja+2(j-1)，所以1＝2-1=ja+2(j-1)-(ia+2(i-1))=a(j-i)+2(j-i)，所以，因为a∈I，所以j-i＝1或j-i＝-1，即a＝-1或a＝-3。当a＝-1时，x∈I，存在x+2∈I，使得x=(-1)x+2。当a＝-3时，x∈I，存在-x-2∈I，使得x=(-3)-x-2。故<I,*>是循环群，全部生成元为-1和-3，幺元为-2，每个元素a的逆元为-4-a。五、综合证明题（共18分）将下面的推理符号化，然后用逻辑推理的方法证明之。 1、解：设f(x)：x是在学校读书；g(x)：x获得知识，则句子可以符号化为：证明：使用CP规则。P（附加前提）T,(1),EUS,(2)PUS,(4)T,(3),(5),IUG,(6)T,(7),E2、证明：①a∈G，因为<G,*>是群，存在e∈G，使得a=e*a*e-1，由已知得<a,a>∈R，所以R是自反的。②a,b∈G，若<a,b>∈R，则存在Q,H∈G使得b=Q