离散数学试题一..doc

离散数学 试题一 一、填空20%（每空2分）： 1．若对命题P赋值1，Q赋值0，则命题（表示双条件）的真值为 0 。 2．命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号化为 ?P→?Q 3．公式的对偶公式为___?（P∧Q）∨（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| x≡y（mod3）}，则[1]=___ {……，-2,1,4，……}____ 。 10．代数系统是环，若对运算“· ”还满足a，b∈R，使得a?b≠0，可换，含幺元 则是整环。 二、选择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)) 制表如下： 编号 公式 依据 (?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 下界无 下确界无 五、8%：求集合的并与交。 六、15% 已知某树有2个2度结点、3个3度结点、4个4度结点，问有几个叶子点（无其它度数点） 解：设共有k个叶子点，总边数为x，则 2+3+4+k=x+1 2×2＋3×3＋4×4＋k=2x 解得：k=13，x=21 七、8% 若图G不连通，则G的补图是连通的。 证明：G不连通，则