离散数学试卷(23) 一、单项选择题：（每小题1分，本大题共10分） 1.命题公式P→(QvP)是( A、矛盾式：B、可满足式：C、重言式：D、等价式。 2.下列各式中哪个不成立( A、x(P(x)vQ(x》台xPx)vxx) B、3x(P(x)VQ(x)台3rPx)v3xQx): C、x(P(x)AQ(x)白xPx)AxQx): D、x(P(x)AQ)白xPx)AQ 3.谓词公式x(P(x)V3R(y》→Q(x)中的x是( )。 A、自由变元： B、约束变元： C、既是自由变元又是约束变元：D、既不是自由变元又不是约束变元。 4.在0_中之间应填入( )符号。 A、=:B、C:C、e:D、E。 5.设<A,之>是偏序集，BA,下面结论正确的是( A、B的极大元b∈B且唯一 B、B的极大元b∈A且不唯一： C、B的上界b∈B且不唯一： D、B的上确界b∈A且唯一。 6.在自然数集N上，下列( )运算是可结合的。 (对任意a,b∈N) A、a*b=a-b: B、a*b=maNa,b): C、a*b=a+5b:D、a*b=a-bl. 7.Q为有理数集N,Q上定义运算◆为a*b=a+b-b,则<Q,>的么元为( )。 A、a:B、b: C、1:D、0。 8.给定下列序列，( )可以构成无向简单图的结点次数序列。 A、(1,1,2,2,3): B、(1,1,2,2,2: C、(0,1,3,3,3 D、(1,3,4,4,5)。 9.设G是简单有向图，可达矩阵P(G)刻划下列( )关系。 150
离散数学试卷（23） 150 一、单项选择题：（每小题 1 分，本大题共 10 分） 1．命题公式 P → (Q P) 是（ ）。 A、 矛盾式； B、可满足式； C、重言式； D、等价式。 2．下列各式中哪个不成立（ ）。 A、x(P(x) Q(x)) x P(x) x Q(x) ； B、 x(P(x) Q(x)) x P(x) x Q(x) ； C、x(P(x) Q(x)) x P(x) x Q(x) ； D、x(P(x) Q) xP(x) Q 。 3．谓词公式 x(P(x) yR( y)) → Q(x) 中的 x 是（ ）。 A、自由变元； B、约束变元； C、既是自由变元又是约束变元； D、既不是自由变元又不是约束变元。 4．在 0 之间应填入（ ）符号。 A、= ； B、 ； C、 ； D、 。 5．设< A ， > 是偏序集， B A ，下面结论正确的是（ ）。 A、 B 的极大元 bB 且唯一； B、 B 的极大元 b A 且不唯一； C、 B 的上界 bB 且不唯一； D、 B 的上确界 b A 且唯一。 6．在自然数集 N 上，下列（ ）运算是可结合的。 （对任意 a,b N ） A、 a b = a −b ； B、 a b = max( a,b) ； C、 ab = a +5b ； D、 a b = a − b 。 7．Q 为有理数集 N，Q 上定义运算*为 a*b = a + b – ab ,则<Q，*>的幺元为（ ）。 A、a； B、b； C、1； D、0。 8．给定下列序列，（ ）可以构成无向简单图的结点次数序列。 A、（1，1，2，2，3）； B、（1，1，2，2，2）； C、（0，1，3，3，3）； D、（1，3，4，4，5）。 9．设 G 是简单有向图，可达矩阵 P(G)刻划下列 （ ）关系
离散数学试卷(23) A、点与边：B、边与点：C、点与点：D、边与边。 10.一颗树有两个2度结点，1个3度结点和3个4度结点，则1度结点数为( A、5:B、7:C、9:D、8。 二、填空：（每空1分，本大题共15分） 1.在自然数集中，偶数集为N,、奇数集为N2,则N,⌒N2= N ON, 2.设X={1,2,3,4}，R={K1,2>,<2,4>,<33>},则 r(R)= :s(R)= :t(R)= 3.设R为集合A上的等价关系，对a∈A,集合[a]R= 称为元素a形成的R等价类，[ae≠中，因为 4.任意两个不同小项的合取为 ,全体小项的析取式为 5.设Q(x):x为偶数，P(x):x为素数，则下列命题：(1)存在唯一偶素数：(2)至多有一个 偶素数：分别形式化：(1) (2) 6.设T为根树，若」 ,则称T为m元树： 若 则称T为完全m叉树。 7.含5个结点，4条边的无向连通图（不同构）有 个， 它们是 三、判断改正题：（每小题2分，本大题共20分） 1.命题公式(A入(A→B)→B是一个矛盾式。 2.任何循环群必定是阿贝尔群，反之亦真。 3.根树中最长路径的端点都是叶子。 4.若集合A上的关系R是对称的，则R也是对称的。 5.数集合上的不等关系（≠）可确定A的一个划分。 6.设集合A、B、C为任意集合，若A×B=AxC,则B=C。 151
离散数学试卷（23） 151 A、点与边； B、边与点； C、点与点； D、边与边。 10．一颗树有两个 2 度结点，1 个 3 度结点和 3 个 4 度结点，则 1 度结点数为（ ）。 A、5； B、7； C、9； D、8。 二、填空：（每空 1 分，本大题共 15 分） 1．在自然数集中，偶数集为 N1 、奇数集为 N2 ，则 N1 N2 = ； N1 N2 = 。 2．设 X = {1,2,3,4} , R = { 1,2 , 2,4 ， 3,3 } ，则 r (R) = ；s (R) = ；t (R) = 。 3．设 R 为集合 A 上的等价关系，对 a A ，集合 a R [ ] = ， 称为元素 a 形成的 R 等价类， [a]R ，因为 。 4．任意两个不同小项的合取为 ，全体小项的析取式为 。 5．设 Q(x): x为偶数，P(x): x为素数 ，则下列命题：（1）存在唯一偶素数；（2）至多有一个 偶素数；分别形式化：（1） ； （2） 。 6．设 T 为根树，若 ，则称 T 为 m 元树； 若 则称 T 为完全 m 叉树。 7．含 5 个结点，4 条边的无向连通图（不同构）有 个， 它们是 。 三、判断改正题：（每小题 2 分，本大题共 20 分） 1．命题公式 (A (A → B)) → B 是一个矛盾式。 （ ） 2．任何循环群必定是阿贝尔群，反之亦真。 （ ） 3．根树中最长路径的端点都是叶子。 （ ） 4．若集合 A 上的关系 R 是对称的，则 −1 R 也是对称的。 （ ） 5．数集合上的不等关系（≠）可确定 A 的一个划分。 （ ） 6．设集合 A、B、C 为任意集合，若 A×B = A×C，则 B = C。 （ ）
离散数学试卷(23) 7.函数的复合运算“。”满足结合律。 ( 8.若G是欧拉图，则其边数e合结点数v的奇偶性不能相反。 () 9.图G为(n,m)图，G的生成树T必有n个结点。 1O.使命题公式P→(QVR)的真值为F的真值指派的P、Q、R值分别是T、F、F。 ( 四、简答题（每小题5分，本大题共25分） 1.设<H,0>和<K,0>都是群<G,0>的子群，问<HnK0>和<HUK,0>是否是<G0> 的子并说明理由。 2.设A={2,3,4,9},B={2,4,7,10,12},从A到B的关系 R={Ka,b>a∈A,b∈B,且a整除b,试给出R的关系图和关系矩阵，并说明此关系是 否为函数？为什么？ 3.设<S,*>是半群，O,是左零元，对任x∈S,x*O,是否是左零元？为什么？ 4.某次会议有20人参加，其中每人至少有10个朋友，这20人拟围一桌入席，用图论知识说明 是否可能每人邻做的都是朋友？（理由） 5.通过主合取范式，求出使公式一（一P→Q)VR的值为F的真值指派。 五、证明题：（共30分） 1.设R为集合A上的二元关系，如果R是反自反的和可传递的，则R一定是反对称的。 2.试证明若<G,*>是群，HG,且任意的a∈H,对每一个x∈G,有a*x=x幸a,则 <H,*>是<G,*>的子群
离散数学试卷（23） 152 7．函数的复合运算“。”满足结合律。 （ ） 8．若 G 是欧拉图，则其边数 e 合结点数 v 的奇偶性不能相反。 （ ） 9．图 G 为（n , m）图，G 的生成树 TG 必有 n 个结点。 （ ） 10．使命题公式 P → (Q R) 的真值为 F 的真值指派的 P、Q、R 值分别是 T、F、F。 （ ） 四、简答题（每小题 5 分，本大题共 25 分） 1．设 H, 和 K, 都是群 G, 的子群，问 H K, 和 H K, 是否是 G, 的子并说明理由。 2．设 A = {2，3，4，9}， B = {2，4，7，10 , 12} ，从 A 到 B 的关系 R ={ a , b a A , b B , 且a整除b} ，试给出 R 的关系图和关系矩阵，并说明此关系是 否为函数？为什么？ 3．设 S , 是半群， OL 是左零元，对任 OL xS , x 是否是左零元？为什么？ 4．某次会议有 20 人参加，其中每人至少有 10 个朋友，这 20 人拟围一桌入席，用图论知识说明 是否可能每人邻做的都是朋友？（理由） 5．通过主合取范式，求出使公式 (P → Q) R 的值为 F 的真值指派。 五、证明题：（共 30 分） 1．设 R 为集合 A 上的二元关系，如果 R 是反自反的和可传递的，则 R 一定是反对称的。 2．试证明若 G , 是群， H G ，且任意的 aH ，对每一个 xG ，有 a x = x a ，则 H, 是 G , 的子群
离散数学试卷(23) 3.设G是每个面至少由k(k≥3)条边围成的连通平面图。试证明e≤-2》，其中y为结 k-2 点数，e为边数。 4.符号化下列各命题，并说明结论是否有效（用推理规则）。任何人如果他喜欢美术，他就不喜 欢体有。每个人或喜欢体有，或喜欢音乐，有的人不喜欢音乐，因而有的人不喜欢美术。 153
离散数学试卷（23） 153 3．设 G 是每个面至少由 k （ k 3 ）条边围成的连通平面图，试证明 2 ( 2) − − k k v e ，其中 v 为结 点数， e 为边数。 4．符号化下列各命题，并说明结论是否有效（用推理规则）。任何人如果他喜欢美术，他就不喜 欢体育。每个人或喜欢体育，或喜欢音乐，有的人不喜欢音乐，因而有的人不喜欢美术