《离散数学》课程教学资源（试卷习题）试卷（题目）20

离散数学试卷（二十） 一、填空20%（每空2分） 1.n个命题变元有 ,个互不等价的极小项。 2.按De.M6rgan定理，4V4Vv4,=Y4= 3.公式P→（一QVR)的主析取范式为 4.设P(x):x是大象，Q(x):x是老鼠，R(xy):x比y重，则命题“大象比老鼠重”的符号化为 101） 5.设X={a,b,c,X上的关系R的关系矩阵是M。=110,则 111 6.在具有n个结点的有向图中，任何基本通路的长度都不超过 7.任何图的点连通度K(G),边连通度(G),最小点度8(G)的关系为 8.结点数n(n之3)的简单连通平面图的边数为m,则m与n的关系为 9.群G的非空子集H是G的子群当且仅当若x,yeH则】 10.代数系统是环，若对运算“·”还满足 则是整环。 二、选择10%（每小题2分） 1.集合A={xx=2",n∈N对( )运算封闭。 A、加法：B、减法：C、乘法：D、x-月。 2.设I为整数集合，m是任意正整数，Zm是由模m的同余类组成的同余类集合，在Zm上定义 运算[门×[U】=(i×)modm,则代数系统最确切的性质是( A、封闭的代数系统：B、半群：C、独异点：D、群。 130

离散数学试卷（二十） 130 一、填空 20%（每空 2 分） 1．n 个命题变元有 个互不等价的极小项。 2．按 De-Morgan 定理， i n i A  A   An =A =1 1 2  = 。 3．公式 P → (Q  R) 的主析取范式为 。 4．设 P(x)：x 是大象，Q(x)：x 是老鼠，R(x,y)：x 比 y 重，则命题“大象比老鼠重”的符号化为 。 5．设 X = {a,b, c}，X 上的关系 R 的关系矩阵是           = 1 1 1 1 1 0 1 0 1 M R ，则 MRR = 。 6．在具有 n 个结点的有向图中，任何基本通路的长度都不超过 。 7．任何图的点连通度  (G) ，边连通度 (G) ，最小点度  (G) 的关系为 。 8．结点数 n（ n  3 ）的简单连通平面图的边数为 m，则 m 与 n 的关系为 。 9．群 G 的非空子集 H 是 G 的子群当且仅当若 x , y  H 则 。 10．代数系统  A,+, •  是环，若对运算“· ”还满足 则  A,+, •  是整环。 二、选择 10%（每小题 2 分） 1．集合 A {x x 2 ,n N} n = =  对（ ）运算封闭。 A、加法； B、减法； C、乘法； D、 x − y 。 2．设 I 为整数集合，m 是任意正整数， Z m 是由模 m 的同余类组成的同余类集合，在 Z m 上定义 运算 [i][ j] = [(i  j)mod m] ，则代数系统  Zm , m  最确切的性质是（ ）。 A、封闭的代数系统； B、半群； C、独异点； D、群

离散数学试卷（二十） 3.设是偏序格，其中N是自然数集合，“≤”是普通的数间“小于等于”关系，则 a,beN有avb=( )。 A、aB、bC、maa,b)D、min(a,b) 4.连通非平凡的无向图G有一条欧拉回路当且仅当图G( )。 A、只有一个奇度结点：B、只有两个奇度结点： C、只有三个奇度结点：D、没有奇度结点。 5.设无向图G=是连通的且y=n,E=m若()则G是树。 A、MN+1;B、n=m+1:C、ms3n-6:D、n≤3m-6。 三、12%逻辑推理： 符号化命题“有些病人相信医生，但是没有病人相信法轮功，因此医生都不信法轮功”。 用演绎法证明其结论。(P(x):X是病人，D(x:x是医生，Qx:x是法轮功练习者，K,y): x相信y) 四、序关系8%： 设A={,x2,x,x4,x},偏序集的Has图为 求①A中最小元与最大元： ②{x,x4,x}的上界和上确界，下界和下确界。 五、函数8% 设∫：X→Y和g:Y→Z是映射且使得g°∫是满射，若g是入射，证明f是满射。 六、图8% 设G是连通简单平面图，结点数为n(n≥3)，边数为m,面数为，则r≤2n-4。 七、树的应用12% 设7个符号在通讯中使用的频率如下： a:35%,b:20%,c:15%,d:10%,e:10%,f5%,g:5% 编一个相应的二元前缀码，使通讯中出现的符号尽可能地减少，并画出对应的二叉树及求二 叉树的过程。 131

离散数学试卷（二十） 131 3．设  N, 是偏序格，其中 N 是自然数集合，“≤”是普通的数间“小于等于” 关系，则 a,b  N 有 a  b = （ ）。 A、a ； B、b ； C、max(a，b) ； D、min(a，b)。 4．连通非平凡的无向图 G 有一条欧拉回路当且仅当图 G ( )。 A、只有一个奇度结点； B、只有两个奇度结点； C、只有三个奇度结点； D、没有奇度结点。 5．设无向图 G = V, E  是连通的且 V = n , E = m 若（ ）则 G 是树。 A、M=N+1 ； B、n=m+1 ； C、 m  3n −6 ； D、n  3m−6 。 三、12%逻辑推理： 符号化命题“有些病人相信医生，但是没有病人相信法轮功，因此医生都不信法轮功”。 用演绎法证明其结论。（P(x)：x 是病人，D(x)：x 是医生，Q(x)：x 是法轮功练习者，L(x , y)： x 相信 y） 四、序关系 8%： 设 { , , , , } 1 2 3 4 5 A = x x x x x ，偏序集  A,R  的 Hass 图为 求 ① A 中最小元与最大元； ② { , , } 3 4 5 x x x 的上界和上确界，下界和下确界。 五、函数 8% 设 f :X →Y 和 g :Y → Z 是映射且使得 g  f 是满射，若 g 是入射，证明 f 是满射。 六、图 8% 设 G 是连通简单平面图，结点数为 n（ n  3 ），边数为 m，面数为 r，则 r  2n − 4 。 七、树的应用 12% 设 7 个符号在通讯中使用的频率如下： a：35% ，b：20% ，c：15% ，d：10% ， e：10% ，f：5% ，g ：5% 编一个相应的二元前缀码，使通讯中出现的符号尽可能地减少，并画出对应的二叉树及求二 叉树的过程

离散数学试卷（二十） 八、道路的基本性质10% 设u,v是树T的两个不同的结点，从u至v的基本通路（结点不同的道路）是T中最长的 基本道路，证明：d(u)=d(v)=1。 九、子群12% 若H是G的子群，a,b∈G,则b。a∈H台aH∩bH≠Φ。 132

离散数学试卷（二十） 132 八、道路的基本性质 10% 设 u ，v 是树 T 的两个不同的结点，从 u 至 v 的基本通路（结点不同的道路）是 T 中最长的 基本道路，证明：d(u)=d(v)=1。 九、子群 12% 若 H 是 G 的子群， a,b  G ，则      − b  a H aH bH 1