《北航《离散数学》模拟题!!!!》由会员分享，可在线阅读，更多相关《北航《离散数学》模拟题!!!!（33页珍藏版）》请在金锄头文库上搜索。
1、北北航航10 秋秋学学期期 离离散散数数学学模模拟拟题题一一本本复复习习题题页页码码标标注注所所用用教教材材为为：离散数学基础耿素云、屈婉玲1994 年北京大学出版社如学员使用其他版本教材，请参考相关知识点如学员使用其他版本教材，请参考相关知识点一、单项选择题（本大题共一、单项选择题（本大题共 1515 小题，每小题小题，每小题 2 2 分，共分，共 3030 分）分）1.中所有有限长度的串形成的集合记为* ，容易证得*上的连接运算不满足交换律，但满足（ A ）A结合律 B分配律 C幂等律 D吸收律2.Klein 群中元素 a,b,c 的阶为（ B ） 。A1 B2 C3 D43.群 G 的元
2、素 x 的所有幂的集合为 G 的子群,称由 x 生成的子群。记为（ A ）.A B(x) Cx Dx4.交换环是指乘法满足（ A ） 。A交换律 B结合律 C分配律 D吸收律5.至少有（ B ）元素的含单位元、无零因子环称为除环。A一 B二 C三 D四6.,满足( C )的格称为分配格A交换律 B结合律 C分配律 D幂等律7.若 L 为有限布尔代数,则（ B ）正整数 n，L 与含有 n 个元素的集合 A 的幂集同构。A不存在 B存在 C有可能存在 8.有向图 D 的顶点 v 作为边的始点的次数之和称为 v 的出度，记为 d+(v)， v 作为边的终点的次数之和称为 v 的入度，记为 d-(v
3、)，v 的度数 d(v)= ( A )。Ad+(v)+d-(v) Bd+(v) Cd-(v) Dd+(v)*d-(v)9.若通路 =v0e1v1e2e1v1 中所有顶点互不相同(所有边自然互不相同)时称为（ B ）A初级回路 B路径 C复杂通路 D迹10.在 n 阶图中，若一顶点存在到自身的回路，则必存在从该顶点到自身的长度不超过( B )的回路。An-1 Bn Cn+1 D2n11.“人总是要死的”谓词公式表示为（ C ） 。（论域为全总个体域）M(x)：x 是人；Mortal(x)：x 是要死的。A； B)()(xMortalxM)()(xMortalxMC； D)()(xMortalxM
4、x)()(xMortalxMx12.公式的解释 I 为：个体域 D=2，P(x)：x3, Q(x)：x=4)()(xQxPxA则 A 的真值为（ A ） 。A1； B0； C可满足式； D无法判定。13.下列等价关系正确的是（ B ） 。A；)()()()(xxQxxPxQxPxB；)()()()(xxQxxPxQxPxC；QxxPQxPx)()(D。QxxPQxPx)()(14.下列偏序集（ C ）能构成格。15.设，*为普通乘法，则S，*是（ D ） 。4,41, 3,31, 2,21, 1sA代数系统； B半群； C群； D都不是。参考答案：1-5 ABAAB 6-10 CBABB 11
5、-15 CABCD二、填空题（本大题共二、填空题（本大题共 4 4 题，题，1616 题题 2 2 分，其它每空分，其它每空 3 3 分，共分，共 2020 分）分）16、设格中表达式 E = (ab)(cd)，则 E 的对偶表达式 E*=_。考核知识点：格的对偶表达式 ，参见教材 P144 参考答案：（ab）（cd）17、设集合 A = a, b, c, d, e，A 上半序关系 R 的哈斯图如下图所示，则 A 的极大元为 _，极小元为_。考核知识点：半序关系的极值 ，参见教材 P93 参考答案：ac,d18、由集合运算的基本定律： （1）AA = A，满足_律； （2）AE = E，满足_
6、律； （3）AE = A，满足_律； （4）AA =，满足_律。考核知识点：集合的运算律 ，参见教材 P65-67 参考答案：等幂律零一律同一律互补律三、问答题（本大题共三、问答题（本大题共 3 3 小题，每小题小题，每小题 1010 分，共分，共 3030 分）分）19求命题公式的真值RPRQPPRQ)()(考核知识点：命题公式的真值表 ，参见教材 P5参考答案：RPRQPPRQ)()(RPRQPPRQ)()(RPQQRP)(120、设集合 A0，1，2，3，4，5，6上的偏序关系 R 如下：R,，,IA做偏序集的哈斯图，并求 B=0,2,3的极大元、极小元、最大元和最小元。 考核知识点：
7、偏序关系的极值 ，参见教材 P93 参考答案：A0,1,2,3,4,5,6, B=0，2，3， 哈斯图如右图 B 的极大元：2，3, B 的极小元：0 B 的最大元：无 B 的最小元：0 21、解释 N 如下： 个体域 DN 为全体自然数的集合 DN中特定元素 a=0DN上函数yxyxgyxyxf),(,),(D 上谓词为),(yxFyx 在解释 N 下，判断公式的真假： （1）个体域为自然数集合 DN；（2）DN上特定函数。yxyxgyxyxf),(,),(考核知识点： 前束范式 ，参见教材 P48 参考答案：（1）在解释 N 下， , 00),( xaxg,0),(xxaxgF公式成为具体
8、命题：“任自然数等于 0”。显然为假命题。xaxgxF),(2)在解释 N 下， zyxfzFyx),(成为，即“任二自然数的和仍为自然数”。显然为真命题。zyxzyx四、证明题（本题共四、证明题（本题共 2 2 小题，每小题小题，每小题 1010 分，共计分，共计 2020 分）分）22证明如果非空集合 A 上的二元关系 R 和 S 是偏序关系，则也是 A 上的偏序关系。SR 考核知识点： 偏序关系的判定 ，参见教材 P91参考答案： ，所以有自反性；SRxxSxxRxxAx,SR 因为 R，S 是反对称的， ,AyxyxxyyxSxySyxRxyRyxSxyRxySyxRyxSRxySRy
9、x ),(),(),(),(,所以，RS 有反对称性 ，因为 R，S 是传递的，Azyx,SRzySRyx,SzyRzySyxRyx,SzySyxRzyRyx,SRzxSzxRzx,所以，有传递性。SR 总之，R 是偏序关系。23设 A，B，C 为三个集合，证明若 CA则(AB)CA(BC) 考核知识点： 集合的运算 参见 P 65参考答案：CxBAxCBAx)(CxBxAx)()()(CxBxCxAx)()(CBAxCBxAx即 )()(CBACBA北北航航10 秋秋学学期期 离离散散数数学学模模拟拟题题二二本本复复习习题题页页码码标标注注所所用用教教材材为为：离散数学基础耿素云、屈婉玲19
10、94 年北京大学出版社如学员使用其他版本教材，请参考相关知识点如学员使用其他版本教材，请参考相关知识点一、单项选择题（本大题共一、单项选择题（本大题共 1515 小题，每小题小题，每小题 2 2 分，共分，共 3030 分）分）1.设集合 A1，2，3，A 上的关系 R(1，1)，(2，2)，则 R 不具有关系的（ A ）性质。A.自反性 B.对称性 C.传递性 D.反对称性2.设集合 Aa, b, c，A 上关系 R 的关系图如下图所示，则 R 具有（ B ） 。A.自反性、对称性、传递性 B.自反性、传递性C.对称性、反对称性D.对称性、反对称性、传递性3.设命题公式 G（PQ） ，HP（
11、QP） ，则 G 与 H 的关系是（ A ） 。A.HG B.GH C. GH D.以上都不是4.下面给出的一阶逻辑等价式中， （ B ）是错的。A. x（A(x) B(x)）x A(x) x B(x) B. x（A(x) B(x)）xA(x) xB(x) C. xA(x)x（A(x)） D. AxB(x)x（AB(x)） 5.如下图所示，半序集中哪个不是格？（ B ）6.设（B，0，1）是布尔代数，a，b 是 B 中元素，a b，则下面（ C ）公式不成立。A. ab= 0 B. ab = 1C. ab= 1 D. ab=a7.下图是（ C ） 。A.完全图 B.平面图 C.哈密顿图 D.欧
12、拉图8.已知图 G 的相邻矩阵为0101010010000011100000100，则 G 的边数与分枝数为（ B ）A. 5，3 B. 4，2 C. 5，1 D. 6，49.若干能等值地表示出全部(合式)公式(真值函数)的逻辑联结词集合称为（ A ）A 全功能集 B功能集 C全功能联结词集合 D特殊联结词集合 10. 下列不是极小全功能集的是（ D ）A , B, C , D , 11. 设，则 有（ D ）个元素。2 , 1,1 ,SS2A3； B6； C7； D8 。12. 设，定义上的等价关系 3 , 2 , 1 SSS 则由 , | ,cbdaSSdcSSbadcbaRR 产 生的上一个划分共有（ B ）个分块。SS A4； B5； C6； D9 。1
