离散数学期末考试模拟题1
- 格式：doc
- 大小：122.00 KB
- 文档页数：6
离散数学期末考试模拟题１
一、单项选择题（每小题1分，共15分。
四选一）
1、设Φ是一个空集，则下列之一哪一个不成立（1 ）。
①、Φ∈Φ②、Φ⊆Φ③、Φ∈{Φ} ④、Φ⊆{Φ}
2、如果命题公式G=P∧Q，则下列之一哪一个成立（ 2 ）。
①、G=⌝(P→Q) ②、G=⌝(P→⌝Q) ③、G=⌝(⌝P→Q) ④、G=⌝(⌝P→⌝Q)
3、设X、Y是两个集合|X|＝n，|Y|＝m，则从X到Y可产生（ 4 ）个二元关系。
①、n m②、m n③、m×n ④、2m×n
4、在有补分配格<L，*，
⊕>中，∀a,b∈L，a≤b当且仅当下列（ ）成立。
①、a *b＝b ②、a
⊕b＝a ③、a＇
*b＝0 ④、a＇
⊕b＝1
5、若<G,*>是一个群，则运算“*”一定满足（ ）。
①、交换律②、消去律③、幂等律④、分配律
6、量词的约束范围称为量词的（ 3 ）。
①、定义域②、个体域③、辖域④、值域
7、下列公式中，（ 4 ）是析取范式。
①、⌝(P∧Q) ②、⌝(P∨Q) ③、(P∨Q) ④、(P∧Q)
8、设G是一个12阶循环群，则该群一定有（ ）个不变子群。
①、2 ②、4 ③、6 ④、8
9、图的构成要素是（3 ）。
①、结点②、边③、结点与边④、结点、变和面
10、下列图中，（ 3 ）是平面图。
①②③④
11、每个非平凡的无向树至少有（ 2 ）片树叶。
①、1 ②、2 ③、3 ④、4
12、每个无限循环群有（ ）个生成元。
①、1 ②、2 ③、3 ④、4
13、设R是集合A＝{1,2,3,4}上的二元关系，R＝{<2,1>,<2,3>,<1,3>},则下列（ 1）不成立。
①、R是自反关系②、R是反自反关系③、R是反对称关系④、R是传递关系
14、设G是一个24阶群，a是G中任意一个元素，则a的周期一定不是（ ）。
①、2 ②、8 ③、16 ④、24
15、下列命题中，（ 3 ）不是真命题。
①、海水是咸的当切仅当蝙蝠是瞎子②、如果成都是直辖市，那么北京是中国的首都
③、若太阳从西边落下，则2是奇数④、夏天冷当切仅当冬天热
二、多项选择题（每小题1分，共10分。
五选二至五）
1、设R是任意集合A上的空关系，则R是（ 2345 ）。
①、自反的②、反自反的③、对称的④、反对称的
⑤传递的
2、设G＝{a}，在G上定义一个二元运算“*”，则在G中运算*一定满足（ ）。
①、可结合②、可交换③、可幂等④、可消去
⑤可吸收
3、设S、R都是定义在集合A上的二元关系，则下列不成立的有（ 2345 ）。
①、若R、S是自反的，则R S也是自反的②、若R、S是反自反的，则R S也是反自反的
③、若R、S是对称的，则R S也是对称的④、若R、S是反对称的，则R S也是反对称的
⑤、若R、S是传递的，则R S也是传递的
4、下列哈斯图中，是格的有（ ）。
①②③④⑤
5、在整数个体域上，下列各式中，真值为真的有（ 235 ）。
①、(∀x)(∃y)(xy=1) ②、(∀x)(∃y)(xy=x)③、(∃y) (∀x) (xy=0)
④、(∀x)(∃y)(∀z)(x+y=z)⑤、(∀x)(∀y)(∃z)(x-y=z)
6、设G是一个13阶群，则G一定是一个（ ）。
①、可换群②、循环群③、变换群④、不变子群
⑤循环半群
7、设G＝⌝P∨Q，则G一定是一个（ 345 ）。
①、文字 ②、短语 ③、子句 ④、合取范式
⑤、析取范式
8、一棵非平凡的外向树，其对应矩阵满足（ 13 ）。
①、对角线全为零
②、仅有一行全为零 ③、仅有一列全为零
④、至少有二行全为零
⑤至少有二列全为零
9、下列图中，那些是右图的强分图。
（ 345 ）
①
②
③
④
⑤
10、下列图中，是二分图的有（
234 ）。
①
②
③
④
⑤
三、名词解释（每小题
2.5分，共10分） 1、试述谓词公式中解释的定义。
2、试述函数中单射函数的定义。
3、试述代数系统中子代数的定义。
4、试述一个简单有向图是单向连通图的定义。
四、判断分析改错题（每小题5分，共15分）
1、若R 是集合A 上的对称关系和传递关系，则R 一定是A 上的自反关系吗？为什么？ 不一定是，当A 是非空集合，R 是A 上的空关系时，R 就不是自反的 当R 不是A 上的空关系时，R 是自反的，证明如下：
<a,b>属于R ，以为R 是A 上的对称关系，所以<b,a>属于R ，又R 是A 上的传递关系，所以
<a,a>属于R ，所以R 是A 上的自反关系，证毕。
2、下面的图一是二分图吗？为什么？
图一 图二 图三
3、设<R ，+>是一个代数系统，R 是实数集合，“＋”是一般的加法运算，R 上的函数f 为：
f(x)=x+5，
则函数f 能构成代数系统的自同构吗？为什么？ 五、计算题（每小题7分，共28分）
1、求命题公式 (P →Q)↔R 的主析取范式和主合取范式
2、给定一个偏序的哈斯图如上面的图二，试求集合B={a,b,c,d}的八种特殊元素（如果有
的话）。
3、设有代数系统<I,*>，运算“*”定义如下：∀a,b ∈I ，有：
a*b=a+b+2 5
试验证该代数系统是否是一个循环群？如是，请求出该循环群的全部生成元，幺元，每个元素的逆元。
4、求上面图三的最小生成树，并求出该最小生成树的权值之和。
六、综合证明题（共22分）
1、符号化下列语句，并用演绎法加以证明。
（7分）
每个计算机专业的学生都要学习离散数学；有些大学生没有学习离散数学。
所以有的大学生不是计算机
专业的学生。
2、设<G,*>是一个群，定义集合G上的一个关系R如下：（7分）
R={<x,y>|(x,y∈G)且（存在Q∈G使得y=Q*x*Q-1）}
证明：R是集合G上的一个等价关系。
3、设<G,*>是一个群，B是G的一个非空子集，且满足2×|B|＞|G|，（8分）
证明：对G中的任意一个元素a，在B中必存在元素b
1，b
2
，使得
a=b
1*b
2。
（提示：考察集合C={a*b-1|b∈B}）。
