离散数学期末考试试题(配答案)模拟题2

1模拟题2模拟试题科目：离散数学考试形式：闭卷考试时间:120分钟系别、班级：姓名：学号：一、填空20%（每空2分）：1．若对命题P赋值1，Q赋值0，则命题QP（表示双条件）的真值为0。2．命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号化为¬P→¬Q3．公式))(()(SQPQP的对偶公式为___¬（P∧Q）∨（P∧¬（Q∨¬S））____。4．图的对偶图为5.若关系R是等价关系，则R满足______自反性，对称性，传递性_____________________________。6．代数系统,A是群，则它满足____结合律，有幺元，每个元素都有递元______。7．若连通平面图EVG,共有r个面，其中eEvV,，则它满足的Euler公式为_____v-e+r=2__。8.n个结点的无向完全图Kn的边数为n（n-1）/2，欧拉图的充要条件是顶点都是偶顶点且是连通的。9.设I为整数集合，R={x,y|x≡y（mod3）}，则[1]=___{……，-2,1,4，……}____。10．代数系统,,A是环，若对运算“·”还满足a，b∈R，使得a•b≠0，可换，含幺元则,,A是整环。二、选择10%（每小题2分）21．集合},2{NnxxAn对（）运算封闭。A、加法；B、减法；C、乘法；D、yx。2．设I为整数集合，m是任意正整数，mZ是由模m的同余类组成的同余类集合，在mZ上定义运算]mod)[(][][mjiji，则代数系统mmZ,最确切的性质是）。A、封闭的代数系统；B、半群；C、幺元；D、群。3．设,N是偏序格，其中N是自然数集合，“≤”是普通的数间“小于等于”关系，则Nba,有ba（）。A、a；B、b；C、max(a，b)；D、min(a，b)。4．连通非平凡的无向图G有一条欧拉回路当且仅当图G()。A、只有一个奇度结点；B、只有两个奇度结点；C、只有三个奇度结点；D、没有奇度结点。5．设无向图EVG,是连通的且mEnV,若（）则G是树。A、m=n+1；B、n=m+1；C、63nm；D、63mn。三、12%符号化语句：“有些病人相信所有的医生，但是病人都不相信骗子，所以医生都不是骗子”。并推证其结论。解:设A(x):x是病人，B(x):x是医生，C(x):x是骗子，D(x,y):x相信y前提：∃(x)(A(X)∧(∀y)(B(y)→D(x,y)))(∀x)(∀y)(A(x)∧((y)→¬D(x,y))结论：(∀x)(B(x)→¬C(x))制表如下：编号公式依据（1）(∃x)(A(x)∧(∀y)(B(y)→D(x,y)))前提3（2）A(a)∧(∀y)(B(y)→D(a,y))(1),Es（3）A(a),(∀y)(B(y)→D(a,y))(2)（4）(∀x)(∀y)(A(x)∧C(y)→¬D(x,y))前提（5）(∀y)(A(a)∧C(y)→¬D(a,y))(4),Us（6）A(a)→(∀y)(C(y)¬D(a,y))(5)（7）(∀y)((C(y)→¬D(a,y))(3)(6)（8）B(d)→D(a,d)(3),Us（9）C(e)→¬D(a,e)(7),Us（10）B(d)→¬C(e)(8)(9)（11）(∀x)(B(x)→¬C(x))(10),UG四、8%：设},,,,{54321xxxxxA，偏序集RA,的Hass图为求①A中最小元与最大元；②},,{543xxx的上界和上确界，下界和下确界。解：（1）A中最小元：没有；最大元：x14（2）上界x1x3上确界x3下界无下确界无（注：离散数学及应用（温武）127页概念，自己去研究）五、8%：求集合),3,2,1(10nnxxAn的并与交。（注：写这个还真麻烦，丑，呃……）六、15%已知某树有2个2度结点、3个3度结点、4个4度结点，问有几个叶子点（无其它度数点）解：设共有k个叶子点，总边数为x，则2+3+4+k=x+12×2＋3×3＋4×4＋k=2x解得：k=13，x=21七、8%若图G不连通，则G的补图G是连通的。证明：G不连通，则G的连通分支有G1，G2，Gm,(m≥2)在补图非G中找两个顶点，u，v有两种情况：①u，v落在G的不同连通分支中，u∈Gi，v∈Gj，i≠j；5(u,v)是补图非G的一条边，故u，v连通。②u，v都在Gi中，则找另一个连通分支Gj，在Gj找任意一个顶点w，(u,w),(w,v)是G的边，则u，v在补图非G边连通。八、10%求图中的一棵最小生成树。解：九、9%若集合Ｘ＝｛（１，２），（３，４），（５，６），……｝}|,,,{12212211yxyxyxyxR1、证明R是X上的等价关系。2、求出X关于R的商集。证明：261.①自反性∀（x1，y1）∈x，由于x1+y1=y1+x1，所以＜（x1，y1），（x1，y1）＞∈R②对称性∀＜（x1，y1），（x2，y2）＞∈R,要证明＜（x2，y2），（x1，y1）＞∈R因为x1+y2=x2+y1及①自反性，可得:x2+y1=x1+y2所以具有对称性。③传递性∀＜（x1，y1），（x2，y2）＞∈R,∀＜（x2，y2），(x3,y3)＞∈Rx1+y2=y1+x2x2+y3=y2+x3因为①②可得：x1+y3=y1+x32.X关于R的商集：x/R={[(1,2)]}