北京工业大学经管学院期末试卷
《离散数学》（A）
学号姓名：成绩
一、单项选择题（每题2分，共18分）
1．令P：今天下雪了，Q：路滑，则命题“虽然今天下雪了，但是路不．滑”可符号化为（D）A ．P→Q B．P ∨Q
C．P∧Q D．P ∧Q
p→q，蕴涵式，表示假设、条件、“如果，就”。
“→”与此题无关
2. 关于命题变元P和Q的极大项M1表示( C )。书P15-P19，此题换作p、q更容易理解
A.┐P∧Q
B.┐P∨Q p∨┐q ---- 01---- 1 ----- M1
C.P∨┐Q
D.P∧┐Q
3.设R（x）：x是实数；S（x,y）：x小于y。用谓词表达下述命题：不存在最小的实数。其中错误的表达式是：（D）
4.在论域D={a,b}中与公式（x?）A（x）等价的不含存在量词的公式是（B）
A.)b(
A
A∨
)a(
A
)a(
A∧ B. )b(
C. )b(
)b(
A→
A→ D. )a(
A
)a(
A
5．下列命题公式为重言式的是（C）
A．Q→（P∧Q）B．P→（P∧Q）
C．（P∧Q）→P D．（P∨Q）→Q
牢记→真假条件，作为选择题可直接代入0、1，使选项出现1→0，排除。熟练的可直接看出C不存在1→0的情况
6. 设A=｛1，2，3｝，B=｛a,b｝，下列二元关系R为A到B的函数的是( A )
A. R=｛<1,a>,<2,a>,<3,a>｝
B. R=｛<1,a>,<2,b>｝
C. R=｛<1,a>,<1,b>,<2,a>,<3,a>｝
D. R=｛<1,b>,<2,a>,<3,b>,<1,a>｝
-第1页
-第 2页
7.偏序关系具有性质（ D ） 背
A.自反、对称、传递
B.自反、反对称
C.反自反、对称、传递
D.自反、反对称、传递
8.设R 为实数集合，映射:,R R σ→2()21,x x x σ=-+-则σ 是( D ).
(A) 单射而非满射 (B) 满射而非单射 (C) 双射 (D) 既不是单射也不是满射.
书P96.设函数f ：A→B
（1）若ranf=B ，则f 是满射的【即值域为B 的全集，在本题中为R ，该二次函数有最高点，不满足】
（2）若对于任何的x 1,x 2∈A , x 1≠x 2,都有f(x 1)≠f(x 2)，则称f 是单射的【即x,y 真正一一对应，甚至不存在一个y 对应多个x 。显然，本题为二次函数，不满足】
（3）若f 既是满射的，又是单射的，则称f 是双射的【本题中两个都不满足，既不是单射也不是满射】
二、填空题（每空2分，共22分）
１.设Q 为有理数集，笛卡尔集S=Q×Q ，*是S 上的二元运算，?
２.在个体域D 中，公式)x (xG ?的真值为假当且仅当__某个G(x)的真值为假__，公式)x (xG ?的真值为假，当且仅当__所有G(x)的真值都为假__。
３.给定个体域为整数域，若F （x ）：表示x 是偶数，G （x ）：表示x 是奇数；那么，)x (G )x ()x (F )x (?∧?是一个 永真式 ；而))x (G )x (F )(x (∧?是一个 永假式 。
４.设{}{}===)R (r ,c ,b ,b ,a R A ,c ,b ,a A 则上的二元关系
{
s(R)= {
书P89、P85.
自反闭包：r(R) = R U R 0
={
-第 3页
传递闭包：t(R) = RUR 2 UR 3U……
５. 设X={1,2,3},Y={a,b}，则从X 到Y 的不同的函数共有___8___个.
书P96，B 上A 的概念：
设Ａ、Ｂ为集合，所有从Ａ到Ｂ的函数构成集合ＢA ，读作“B 上A ”
如果|A| = m ，|B| = n ，m 、n 不全是0，则|B A | = n m
即，若题中给出集合A 有m 个元素，B 有n 个元素，可直接用n m 计算出A 到B 的函数个数。本题中为23 = 8 ６.设,,G 是群*a,b ∈G ，则（a -1）-1= a ，（a *b ）-1= 。
书P84公式
7. 设X={1，2，3}，f ：X→X ，g ：X→X ，f={<1, 2>,<2,3>,<3,1>},
g={<1,2>,<2,3>,<3,3>}，则f g=__{<1,3>,<2,3>,<3,2>}___，g f=__{<1,3>,<2,1>,<3,1>}__。 合成：F G = {
三、计算题（每题9分，共36分）
1. 设集合A ＝{1, 2, 3,4,5}，A 上的关系R ＝{<1, 1>,<1, 2>,<2, 2>,<3, 2>,<3,
3>,<3,5>,<4,4>,<5,5>}
(1)
画出R 的关系图；
(2) 问R 具有关系的哪几种性质(自反、对称、传递、反对称).
自反性、传递性
书P87表格，根据关系图可直接判断性质……
(3) 给出R 的传递闭包。
R={<1, 1>,<1, 2>,<2, 2>,<3, 2>,<3, 3>,<3,5>,<4,4>,<5,5>}
R 2 = R R = {<1, 1>,<1,2>,<2,2>,<3,2>,<3,3>,<3,5>,<4,4>,<5,5>}
R 3 = R 2 R = {<1, 1>,<1,2>,<2,2>,<3,2>,<3,3>,<3,5>,<4,4>,<5,5>} ……
所以，t(R) = {<1, 1>,<1,2>,<2,2>,<3,2>,<3,3>,<3,5>,<4,4>,<5,5>}
-第 4页
2. 集合S={a,b,c,d,e}上的二元运算*的运算表如下，求出它的幺元，零元，及逆
元。
* a b c d e
a b a c c c
b a b
c
d e
c c c c c c
d e d c b a
e d e c d b
幺元：b
零元：c
逆元：a -1 =a,b -1 =b,c -1 =c,d -1 =d
书P123定义
3．求合式公式A=P→((P→Q)∧┐(┐Q ∨┐P))的主析取范式及成真赋值。
A = P→((┐P ∨Q)∧ (Q ∧P))
= P→((┐P ∨Q)∧ (Q ∧P))
= P→((┐P ∧Q ∧P)∨(Q ∧Q ∧P))
= P→(Q ∧P)
= ┐P ∨(Q ∧P)
= (┐P ∧(Q ∨┐Q ))∨(Q ∧P)
= (┐P ∧Q)∨(┐P ∧┐Q )∨(P ∧Q)
= (┐P ∧┐Q )∨(┐P ∧Q)∨(P ∧Q)
= m 0∨m 1∨m 3
成真赋值为00，01，11
4．求在1到1000000之间有多少个整数既不是完全立方数，也不是完全平方数？
韦恩图
完全平方数的个数：10002 =1000000，所以有1000个（即1到1000）
完全立方数的个数：1003 =1000000，所以有100个（即1到100）
既是完全平方数又是完全立方数的重复部分：106 =1000000，所以有10个（即16到106）所以既不是完全立方数，也不是完全平方数的整数有：1000000-(1000+100-10) = 998910
四、证明题（每题8分，共24分）
1．若公司拒绝增加工资，则罢工不会停止，除非罢工超过三个月且公司经理辞职。公司拒绝增加工资，罢工又刚刚开始。罢工是否能停止？（给出相应推理的证明过程）
2．给出关系不满足对称性的条件并证明。
3．如果关系R和S为X上的等价关系，证明：R S也是X上的等价关系。
-第5页
华南农业大学期末考试试卷（A 卷） 2013-2014学年第 一 学期 考试科目： 离散结构 考试类型：（闭卷）考试 考试时间： 120 分钟 学号 姓名 年级专业 ①本试题分为试卷与答卷2部分。试卷有四大题，共6页。 ②所有解答必须写在答卷上，写在试卷上不得分。 一、选择题（本大题共 25 小题，每小题 2 分，共 50 分） 1、下面语句是简单命题的为_____。 A 、3不是偶数 B 、李平既聪明又用功 C 、李平学过英语或日语 D 、李平和张三是同学 2、设 p:他主修计算机科学, q:他是新生，r:他可以在宿舍使用电脑，下列命题“除非他不是新生，否则只有他主修计算机科学才可以在宿舍使用电脑。”可以符号化为______。 A 、r q p →?∧? B 、r q p ?→∧? C 、r q p →?∧ D 、r q p ∧→ 3、下列谓词公式不是命题公式P →Q 的代换实例的是______。 A 、)()(y G x F → B 、),(),(y x yG y x xF ?→? C 、))()((x G x F x →? D 、)()(x G x xF →? 4、设个体域为整数集，下列公式中其值为 1的是_____。 A 、)0(=+??y x y x B 、)0(=+??y x x y C 、)0(=+??y x y x D 、)0(=+???y x y x
2 5、下列哪个表达式错误_____。 A 、 B x xA B x A x ∧??∧?)())(( B 、B x xA B x A x ∨??∨?)())(( C 、B x xA B x A x →??→?)())(( D 、)())((x xA B x A B x ?→?→? 6、下述结论错误的是____。 A 、存在这样的关系，它可以既满足对称性，又满足反对称性 B 、存在这样的关系，它可以既不满足对称性，又不满足反对称性 C 、存在这样的关系，它可以既满足自反性，又满足反自反性 D 、存在这样的关系，它可以既不满足自反性，又不满足反自反性 7、集合A 上的关系R 为一个等价关系，当且仅当R 具有_____。 A 、自反性、对称性和传递性 B 、自反性、反对称性和传递性 C 、反自反性、对称性和传递性 D 、反自反性、反对称性和传递性 8、下列说法不正确的是：______。 A 、R 是自反的，则2R 一定是自反的 B 、R 是反自反的，则2R 一定是反自反的 C 、R 是对称的，则2R 一定是对称的 D 、R 是传递的，则2R 一定是传递 9、设R 和S 定义在P 上，P 是所有人的集合，=R {x P y x y x ∧∈><,|,是y 的父亲}，=S {x P y x y x ∧∈><,|,是y 的母亲}，则关系{y P y x y x ∧∈><,|,是的x 外祖父}的表达式是：______。 A 、11--R R B 、11--S R C 、11--S S D 、11--R S 10、右图描述的偏序集中，子集},,{f e b 的上界为_____。 A 、c b , B 、b a , C 、b D 、c b a ,, 11、以下整数序列，能成为一个简单图的顶点度数序列的是_____。 A 、1，2，2，3，4，5
离散数学答案屈婉玲版 第二版高等教育出版社课后答案 第一章部分课后习题参考答案 16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r)?0∨(0∧1) ?0 （2）（p?r）∧(﹁q∨s) ?（0?1）∧(1∨1) ?0∧1?0. （3）（?p∧?q∧r）?(p∧q∧﹁r) ?（1∧1∧1）? (0∧0∧0)?0 (4)（?r∧s）→(p∧?q) ?（0∧1）→(1∧0) ?0→0?1 17．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 答：p: π是无理数1 q: 3是无理数0 r: 2是无理数 1 s: 6能被2整除1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。19．用真值表判断下列公式的类型： （4）(p→q) →(?q→?p) （5）(p∧r) ?(?p∧?q) （6）((p→q) ∧(q→r)) →(p→r) 答：（4） p q p→q ?q ?p ?q→?p (p→q)→(?q→?p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式
（5）公式类型为可满足式（方法如上例） （6）公式类型为永真式（方法如上例） 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)?(p→(q∧r)) (4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明（2）(p→q)∧(p→r) ?(?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r) （4）(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q)
第四章部分课后习题参考答案 3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值: (1) 对于任意x,均有错误！未找到引用源。2=(x+错误！未找到引用源。)(x 错误！未找到引用源。). (2) 存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解： F(x): 错误！未找到引用源。2=(x+错误！未找到引用源。)(x 错误！未找到引用源。). G(x): x+5=9. (1)在两个个体域中都解释为)(x xF ?，在（a ）中为假命题，在(b)中为真命题。 (2)在两个个体域中都解释为)(x xG ?，在（a ）(b)中均为真命题。 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x 能表示成分数 H(x): x 是有理数 命题符号化为: ))()((x H x F x ∧??? (2)F(x): x 是北京卖菜的人 H(x): x 是外地人 命题符号化为: ))()((x H x F x →?? 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x 是火车; G(x): x 是轮船; H(x,y): x 比y 快
命题符号化为: )) F x G x→ ∧ ? ? y y ( )) ( ) , x ((y ( H (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 命题符号化为: ))) x x F y y→ ?? ∧ ? G (y H ( , ( ) ( ( x ) 9.给定解释I如下: (a) 个体域D为实数集合R. (b) D中特定元素错误！未找到引用源。=0. (c) 特定函数错误！未找到引用源。(x,y)=x错误！未找到引用源。y,x,y D ∈错误！未找到引用源。. (d) 特定谓词错误！未找到引用源。(x,y):x=y,错误！未找到引用源。(x,y):x 《离散数学》期末复习题 一、填空题（每空2分，共20分） 1、集合A上的偏序关系的三个性质是、 和。 2、一个集合的幂集是指。 3、集合A={b,c}，B={a,b,c,d,e}，则A?B= 。 4、集合A={1,2,3,4}，B={1,3,5,7,9}，则A?B= 。 5、若A是2元集合, 则2A有个元素。 6、集合A={1,2,3｝，A上的二元运算定义为：a* b = a和b两者的最大值，则 2*3= 。 7、设A={a, b,c,d }, 则∣A∣= 。 8、对实数的普通加法和乘法，是加法的幂等元， 是乘法的幂等元。 9、设a,b,c是阿贝尔群 19、代数系统是指由及其上的或 组成的系统。 20、设 《离散数学》试卷（A 卷） 一、 选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数 二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???. 2、公式)(Q P Q ?∨∧的主合取范式为 。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。 三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。 （ F ） 2、“张刚和小强是同桌。”是复合命题。 （ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。 （ T ） 4、)(T S R T R S R ??????。 （ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。 （ T ） 6、若f 、g 分别是单射,则g f ?是单射。 （ T ） 7、若g f ?是满射，则g 是满射。 （ F ） 8、若A B ?，则)()(A P B P ?。 （ T ） 9、若R 具有自反性，则1-R 也具有自反性。 （ T ） 10、B A ∈并且B A ?不可以同时成立。 （F ） 四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？ 1.常用公式 p ∧(P →Q)=>Q 假言推论 ┐Q ∧(P →Q)=>┐P 拒取式 ┐p ∧(P ∨Q)=>Q 析取三段式 (P →Q) ∧(Q →R)=>P →R 条件三段式 (PQ) ∧(QR)=>PR 双条件三段式 (P →Q)∧(R →S)∧(P ∧R)=>Q →S 合取构造二难 (P →Q)∧(R →S)∧(P ∨R)=>Q ∨S 析取构造二难 (?x)((Ax)∨(Bx)) <=>( ?x)(Ax)∨(?x)(Bx) (?x)((Ax)∧(Bx)) <=>(?x)(Ax)∧(?x)(Bx) —┐(?x)(Ax) <=>(?x)┐(Ax) —┐(?x)(Ax) <=>(?x)┐(Ax) (?x)(A ∨(Bx)) <=>A ∨(?x)(Bx) (?x)(A ∧(Bx)) <=>A ∧(?x)(Bx) (?x)((Ax)→(Bx)) <=>(?x)(Ax)→(?x)(Bx) (?x)(Ax) →B <=>(?x) ((Ax)→B) (?x)(Ax) →B <=>(?x) ((Ax)→B) A →(?x)(Bx) <=>(?x) (A →(Bx)) A →(?x)(Bx) <=>(?x) (A →(Bx)) (?x)(Ax)∨(?x)(Bx) =>(?x)((Ax)∨(Bx)) (?x)((Ax)∧(Bx)) =>(?x)(Ax)∧(?x)(Bx) (?x)(Ax)→(?x)(Bx) =>(?x)((Ax)→(Bx)) 2.命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P ,Q,R 的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n 个变元共有n 2个极小项或极大项，这n 2为(0~n 2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P 规则，T 规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 3.谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n 个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 4.集合 1.N ，表示自然数集，1,2,3……，不包括0； 2.基：集合A 中不同元素的个数，|A|； 3.幂集：给定集合A ，以集合A 的所有子集为元素组成的集合，P(A)； 4.若集合A 有n 个元素，幂集P(A)有n 2个元素，|P(A)|=||2A =n 2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A 的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 5.关系 1.若集合A 有m 个元素，集合B 有n 个元素，则笛卡尔A ×B 的基数为mn ，A 到B 上可以定义mn 2种不同的关系； 2.若集合A 有n 个元素，则|A ×A|=2n ，A 上有22n 个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 全封闭环的性质：自反性，对称性，反对称性，传递性； 4.前域(domR)：所有元素x 组成的集合； 后域(ranR)：所有元素y 组成的集合； 5.自反闭包：r(R)=RU Ix ; 对称闭包：s(R)=RU 1-R ; 传递闭包：t(R)=RU 2R U 3R U …… 6.等价关系：集合A 上的二元关系R 满足自反性，对称性和传递性，则R 称为等价关系； 7.偏序关系：集合A 上的关系R 满足自反性，反对称性和传递性，则称R 是A 上的一个偏序关系； 8.covA={ 安徽大学20 09 — 20 10 学年第 1 学期 《离散数学（上）》考试试卷（A 卷） （时间120分钟） 院/系 专业 姓名 学号 题 号 一 二 三 四 五 总分 得 分 一、单选题（每小题2分，共20分） 1. 设A={a,b,c}，A 上二元关系R={〈a,a 〉，〈b,b 〉,〈a,c 〉}，则关系R 的对称闭包S(R)是( ) A.R ∪I A B.R C.R ∪{〈c,a 〉} D.R ∩I A 2. 设X={a,b,c},I x 是X 上恒等关系，要使I x ∪{〈a,b 〉，〈b,c 〉，〈c,a 〉，〈b,a 〉}∪R 为X 上的等 价关系，R 应取( ) A. ｛〈c,a 〉，〈a,c 〉｝ B.{〈c,b 〉，〈b,a 〉} C. {〈c,a 〉，〈b,a 〉} D.{〈a,c 〉，〈c,b 〉} 3. 下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 4. 设解释R 如下：论域D 为实数集，a=0, f(x,y)=x-y, A(x,y):x 一（6%）选择填空题。 (1) 设S = {1，2，3}，R 为S 上的二元关系，其关系图如右图所示，则R 具有（ ）的性质。 A. 自反、对称、传递； B. 反自反、反对称； C. 自反、传递； D. 自反。 (2) 设A = {1, 2, 3, 4}， A 上的等价关系 R = { (4)没有不犯错的人。 五（10%）在自然推理系统Ｐ中构造下面推理的证明： 如果他是计算机系本科生或者是计算机系研究生，则他一定学过DELPHI语言且学过C++语言。只要他学过DELPHI语言或者Ｃ++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。 六（10%）在自然推理系统中构造下面推理的证明（个体域：人类）： 每个喜欢步行的人都不喜欢坐汽车，每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车，因而有的人不喜欢步行。 七（14%）下图给出了一些偏序集的哈斯图，判断其是否为格，对于不是格的说明理由，对于是格的说明它们是否为分配格、有补格和布尔格（布尔代数）。 八（12%）设S = {1, 2, 3, 4, 6, 8, 12, 24}，“ ”为S上整除关系， (1)画出偏序集> ,S的哈斯图； < (2)设B = { 2, 3, 4, 6, 12}，求B的极小元、最小元、极大元、最大元，下界，上界。 九（8%）画一个无向图，使它是： (1)是欧拉图，不是哈密尔顿图； (2)是哈密尔顿图，不是欧拉图； (3)既不是欧拉图，也不是哈密尔顿图； 并且对欧拉图或哈密尔顿图，指出欧拉回路或哈密尔顿回路，对于即不是欧拉图也不是哈密尔顿图的说明理由。 十（8%）设6个字母在通信中出现的频率如下： 12 13 :c :b% 45 :a% % :e% :f 9 5 : d% % 16 用Huffman算法求传输它们的最佳前缀码。要求画出最优树，指出每个字母对应的编码，n个按上述频率出现的字母需要多少个二进制数字。 并指出传输)2 ( n 10≥ 安徽大学2006-2007学年第1学期 《离散数学》期末考试试卷（A卷） （时间120分钟） 开课院（系、部）姓名学号. 一、选择题（每小题2分，共20分）1．下列语句中，哪个是真命题（）A、 4 2= + x； B、我们要努力学习； C、如果ab为奇数，那么a是奇数，或b是偶数； D、如果时间流逝不止，你就可以长生不老。 2．下列命题公式中，永真式的是（） A、P Q P→ →) (； B、P P Q∧ → ?) (； C、Q P P? ? ∧) (； D、) (Q P P∨ →。3．在谓词逻辑中，令) (x F表示x是火车；) (y G表示y是汽车；) , (y x L表示x比y快。 命题“并不是所有的火车比所有的汽车快”的符号表示中哪些是正确的（） I.)),()()((y x L y G x F y x →∧??? II.)),()()((y x L y G x F y x ?∧∧?? III. )),()()((y x L y G x F y x ?→∧?? A 、仅I ； B 、仅III ； C 、I 和II ； D 、都不对。 4．下列结论正确的是：（ ） A 、若C A B A =，则 C B =； B 、若B A B A ?，则B A =； C 、若C A B A =，则C B =； D 、若B A ?且D C ?，则D B C A ?。 5．设φ=1A ，}{2φ=A ，})({3φρ=A ，)(4φρ=A ，以下命题为假的是（ ） A 、42A A ∈； B 、31A A ?； C 、24A A ?； D 、34A A ∈。 6．设R 是集合},,,{d c b a A =上的二元关系， },,,,,,,,,,,{><><><><><><=b d d b a c c a a d d a R 。下列哪些命题为真（ ） I.R R ?是对称的 II. R R ?是自反的 III. R R ?不是传递的 A 、仅I ； B 、仅II ； C 、I 和II ； D 、全真。 离散数学期末试卷(A) XXXX大学XX学院2007 ～2008学年第一学期《离散数学》期末试卷年级专业题号得分适用年级专业：2006级软件工程专业试卷说明：闭卷考试，考试时间120分钟一、单项选择题1．下列语句中只有不是命题。C A．今年元旦会下雪。B．1+1=10。C．嫦娥一号太棒了！D．嫦娥奔月的神话已成为现实。2．p?q 的主合取范式是。 B A．(p?q)?(p??q)B．(p??q)?(?p?q) C．(p?q)?(?p??q)D．(p?q)?(?p?q) 3．与p? q等值的命题公式是。D A．?p?q B．p??q C．p??q D．?p?q 4．在一阶逻辑中使用的量词只有个。B A．1B．2 C．3D．4 5．??xA(x)?。C A．??xA(x) B．?x?A(x) C．?x?A(x) D．?xA(x) 6．若|A|=4，则|P(A)|=。 C A．4B．8C．16 D．64 7．设A、B、C为任意集合，集合的对称差运算不具有的性质是。 D A．A?B = B?A B．(A?B)?C = B?(A?C) 班级学号一二三姓名____________ 四总分C．A?A = ?D．A?A = A 8．二元关系是。B A．两个集合的笛卡儿积B．序偶的集合C．映射的集合D．以上都不是9．下面关于函数的叙述中正确的是。D A．函数一定是满射B．函数一定是单射C．函数不是满射就单射D．函数是特殊的关系10．半群中的二元运算一定满足=。B A．交换律B．结合律C．分配律D．幂等律11．环中有个二元运算。 B A．一B．二C．三D．四12．群与独异点的区别是。 C A．满足交换律B．满足结中国石油大学大学《离散数学》期末复习题及答案
离散数学期末试卷A卷及答案
大学离散数学期末重点知识点总结(考试专用)
安徽大学期末试卷离散数学上卷及参考答案.doc
厦门大学离散数学2015-2016期末考试试题答案年
大学《离散数学》期末考试试卷及答案-(1)
离散数学期末试卷(A)
相关主题
文本预览