东 北 大 学 继 续 教 育 学 院 离散数学X 试 卷（作业考核 线上2） A 卷...

李老师

东 北 大 学 继 续 教 育 学 院
      离散数学X  试 卷（作业考核 线上2）  A  卷（共   5   页）         
总分        题号        一        二        三        四        五        六        七        八        九        十
        得分                                                                               

一、单项选择题（每小题3分，共18分）
１.下列命题联结词集合中，哪个是最小联结词组？（　　）
A. {¬,→}     B. {¬,⋀,⋁}      C. {↑}     D. {⋀,→}
2. 命题公式P→(Q↓P)是（    ）
A．重言式     B.可满足式  C. 矛盾式   D. 等值式
3. 设 ，则下列命题哪个正确（   ）
A.Q⊂   B.Q⊆    C. P⊂Q      D.P=Q
4. 设个体域A={a,b}, 公式∀xP(x)⋀∃xS(x)在A中消去量词后应为（    ）
A.P(x)⋀S(x)      B.P(a)⋀(b)⋀(S(a)⋁S(b))  C.P(a)⋀ S(b)    D.P(a)⋀(b)⋀S(a)⋁S(b)
5. 设(L,≼)是一条链，其中|L|≽3, 则(L,≼)(     )
A. 不是格     B. 是有补格   C. 是分配格   D.是布尔格
6. 设有33盏灯，拟公用一个电源，则至少需要五插头的接线板数（    ）
A. 7  B. 8  C. 9  D. 14

二、判断题，对的或真值为1的填Y，错的或真值为假的填N，每小题2分，共20分
1.“计算机有空吗？” 是命题。（　　）
2. 命题“所有人都是要死的。”的否定是“有些人不会死。”（　　）
3. “如果我掌握了英语，法语，那么学习其他欧洲语言就容易得多。”是假命题。（　　）
4.集合Ａ＝｛１，２，３｝的任何关系 Ｒ都不可能既是对称的，又是反对称的。（　　）
5. 若 ，则B=C.  (     )
　　6. （Ｓ，＊）是可交换独异点 ，Ｔ＝｛ｘ｜ｘ＊ｘ＝ｘ，ｘ∈Ｓ｝，则Ｔ也是独异点。（ 　）
7. 具有两个或多个元素的格中不存在以自身为补元的元素。（   　）
8. n个节点的有向完全图边数是n(n-1).  （    ）
9. T是一棵树，则T是一个连通且无简单回路的图。（    ）
10. 素数阶群中的生成元一定是唯一的。（     ）

三、填空题，每小题2分，共12分。
1. 设A={a,b,c,d,e}，B={0,1}，那么可定义       种不同的A 到B 的函数。
2. 任意一个无限群有           个子群。
3. 在有界格中，具有补元的元素集合组成一个        格。
4. 若连通平面图G 有4 个结点，3 个面，则G 有       条边
5. 一个简单有向图是根树，它的邻接矩阵中           为树根。
6. 一个重言式与一个矛盾式的析取是           。
四、简答题，共５０分
1.（10分）使用命题：P：这个材料有趣。Q：这些习题很难。R：这门课程让人喜欢将下列句子用符号形式写出：（1）这个材料很有趣，并且这些习题很难。（2）这个材料无趣，习题也不难，而且这门课程也不让人喜欢。（3）如果这个材料无趣，习题也不难，那么这门课程就不会让人喜欢。（4）这个材料有趣，意味着这些习题很难，并且反之亦然。（5）或者这个材料有趣，或者这些习题很难，并且两者恰具其一。












     


2.（6分）用反证法证明





















3. （6分）求谓词公式 的前束范式。
















4.  (8分) 对于下面的布尔矩阵，确定对应的集合｛１，２，３｝上的关系Ｒ，并确定关系Ｒ2的关系























5. （8分）图２－１５给出了集合｛１，２，３，４｝上的四个偏序关系图，画出它们的哈斯图，并说明哪一个是全序，哪一个是良序？













６. (6分) 求图６－２１所示的带权图中的最优投递路线，邮局在Ｄ点。
  









７.（6分）已知一棵无向树Ｔ有三个３度结点，一个２度结点，其余都是１度结点。（１）Ｔ中有几个１度结点？（２）试画出两棵满足上述度数要求的非同构的无向树。