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

模拟题2广东技术师范学院模拟试题 科 目：离散数学 考试形式：闭卷 考试时间: 120 分钟系别、班级： 姓名： 学号： 一、填空20%（每空2分）：1若对命题P赋值1，Q赋值0，则命题（表示双条件）的真值为 0 。2命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号化为 ¬P¬Q3公式的对偶公式为_¬（PQ）（P¬（Q¬S）_。4图 的对偶图为 5.若关系R是等价关系，则R满足_自反性，对称性，传递性_。 6代数系统是群，则它满足_结合律，有幺元 ，每个元素都有递元_。 7若连通平面图共有r个面，其中，则它满足的Euler公式为_v-e+r=2_。8. n个结点的无向完全图Kn的边数为 n（n-1）/2 ，欧拉图的充要条件是 顶点都是偶顶点且是连通的 。9. 设I为整数集合，R=<x, y>| xy（mod3），则1=_ ，-2,1,4，_ 。10代数系统是环，若对运算“· ”还满足a，bR，使得ab0，可换，含幺元 则是整环。二、选择10%（每小题2分）1集合对（ ）运算封闭。A、加法； B、减法； C、乘法； D、 。2设I为整数集合，m是任意正整数，是由模m的同余类组成的同余类集合，在上定义运算，则代数系统最确切的性质是 ）。A、封闭的代数系统； B、半群； C、幺元； D、群。3设是偏序格，其中N是自然数集合，“”是普通的数间“小于等于” 关系，则 有（ ）。A、a ； B、b ； C、max(a，b) ； D、min(a，b)。4连通非平凡的无向图G有一条欧拉回路当且仅当图G ( )。A、只有一个奇度结点； B、只有两个奇度结点； C、只有三个奇度结点； D、没有奇度结点。5设无向图是连通的且 若（ ）则G是树。 A、m=n+1 ； B、n=m+1 ； C、 ； D、 。三、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)前提（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%：设，偏序集的Hass图为求 A中最小元及最大元； 的上界和上确界，下界和下确界。解：（1）A中最小元：没有；最大元： x1（2）上界x1 x3上确界 x3 下界无 下确界无（注：离散数学及应用（温武）127页概念，自己去研究）五、8%：求集合的并及交。（注：写这个还真麻烦，丑，呃）六、15% 已知某树有2个2度结点、3个3度结点、4个4度结点，问有几个叶子点（无其它度数点）解：设共有k个叶子点，总边数为x，则2+3+4+k=x+12×23×34×4k=2x解得：k=13，x=21七、8% 若图G不连通，则G的补图是连通的。证明：G不连通，则G的连通分支有G1，G2，Gm,(m2)在补图非G中找两个顶点，u，v有两种情况：u，v落在G的不同连通分支中，uGi，vGj，ij；(u,v)是补图非G的一条边，故u，v连通。u，v都在Gi中，则找另一个连通分支Gj，在Gj找任意一个顶点w，(u,w),(w,v)是G的边，则u，v在补图非G边连通。八、10% 求图中的一棵最小生成树。解：2九、9% 若集合（，），（，），（，），1、证明R是X上的等价关系。2、求出X关于R的商集。证明：1.自反性（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)第 3 页