离散数学(本)2016年3月份试题
一、单项选择题(每小题3分,本题共15分)
1.设A={1, 3, 5, 7},B={2, 4, 6},A到B的关系R={
A. {<3, 2>, <5, 4>, <7, 6>}
B. {<1, 4>, <3, 6>}
C. {<1, 2>, <3, 4>, <5, 6>}
D. {<1, 3>, <3, 3>, <5, 3>, <7, 3>}
2.若集合A={a, b, c},则下列表述不正确的是( ).
A.??A B.a∈A
C.{a}∈A D.{a, b, c}?A
3.设A(x):x是学生,B(x):x是大学生,则命题“不是所有的学生都是大学生”可符号化为().
A.┐(?x)(A(x)∧B(x)) B.(?x)(A(x)∧B(x))
C.┐(?x)(A(x)∧┐B(x)) D.┐(?x)(A(x) →B(x))
4.设G为连通无向图,则()时,G中存在欧拉回路.
A.G不存在奇数度数的结点B.G存在偶数度数的结点
C.G存在一个奇数度数的结点D.G存在两个奇数度数的结点5.n阶无向完全图K n的边数是().
A. n(n-1),
B. n(n-1)/2
C. n-1
D. n(n-1)
二、填空题(每小题3分,本题共15分)
6.设集合A={1, 2, 3},B={2, 3, 4},C={3, 4, 5},则A∪(C-B )等于.7.设A={a, b},B={1, 2},C={a, b},从A到B的函数f={, },从B到C的函数g={<1, b>, <2, a >},则g? f等于.
8.对于任意的无向图,其所有结点的度数之和等于该图的边数的.9.设G是具有n个结点m条边k个面的连通平面图,则n+k -2等于.10.设个体域D={1, 2, 3, 4},A(x)为“x等于4”,则谓词公式(?x)A(x)真值为.
三、逻辑公式翻译(每小题6分,本题共12分)
11.将语句“如果小王来学校,则他会参加比赛.”翻译成命题公式.
12.将语句“今天天晴,昨天下雨.”翻译成命题公式.
四、判断说明题(判断各题正误,并说明理由.每小题7分,本题共14分)
13.设A={1,2,3 },R={<1,1 >, <1,2 >,<2,1 >, <3,3 >},则R是等价关系.14.(?x)P(x)∧Q(y)→R(x)中量词?的辖域为P(x)∧Q(y).
五.计算题(每小题12分,本题共36分)
15.设集合A={a, b, c},B={{a, b }, b},试计算
(1)A?B;(2)A - B;(3)A×B.
16.设G=
(3)求出每个结点的度数;(4)画出其补图的图形.
17.试利用Kruskal 算法求出如下所示赋权图中的最小生成树(要求写出求解步骤),并求此最小生成树的权.
六、证明题(本题共8分)
18.试证明:┐┐(P →Q )∧┐R ∧(Q →R )? ┐P .
ο ο ο ο ο v 6 v 1 v 2 v 5 v 3 ο v 4
1
6 2 4 5
7 9 3 1 5 2
离散数学(本)2016年3月份试题
参考解答
一、单项选择题(每小题3分,本题共15分)
1.B 2.C 3.D 4.A 5.B
二、填空题(每小题3分,本题共15分)
6.{1, 2, 3, 5}
7.{, }
8.两倍
9.m
10.真(或T ,或1)
三、逻辑公式翻译(每小题6分,本题共12分)
11.设P :小王来学校, Q :他会参加比赛. (2分) 则命题公式为: P → Q . (6分)
12.设P :今天天晴, Q :昨天下雨. (2分)
则命题公式为:P ∧Q . (6分)
四、判断说明题(每小题7分,本题共14分)
13.错误. (3分) R 不是等价关系,因R 中不包含<2,2 >,故不满足自反性. (7分)
14.错误. (3分) 辖域为紧接与量词?之后的最小子公式P (x ). (7分)
五.计算题(每小题12分,本题共36分)
15.解:(1)A ?B ={ b }; (4分)
(2)A - B={ a , c }; (8分)
(3)A ×B={, , , ,
16.解:(1)G 的图形表示如图一所示:
(3分)
图一 (2)邻接矩阵: ???????
?????????010*******
010110010010100 (6分) (3)v 1,v 2,v 3,v 4,v 5结点的度数依次为2,1,3,2,2. (9分)
(4)补图如图二所示:
(12分)
图二
17.解:用Kruskal 算法求产生的最小生成树。步骤为:
w (v 2,v 6) =1,选(v 2,v 6)
w (v 4,v 5) =1,选(v 4,v 5)
w (v 1,v 6) =2,选(v 1,v 6)
w (v 3,v 5) =2,选(v 3,v 5)
w (v 2,v 3) =4,选(v 2,v 3) (6分) 最小生成树如图三所示:
(9分)
图三
最小生成树的权w (T )=1+1+2+2+4=10. (12分)
六、证明题(本题共8分)
18.证明:
(1)┐┐(P →Q ) P (1分)
(2)P →Q T (1)E (3分)
(3)(Q →R ) P (4分)
(4)┐R P (5分)
(5)┐Q T (3)(4)I (6分)
(6)┐P T (2)(5)I (8分)
说明:
1.因证明过程中,公式引用的次序可以不同,一般引用前提正确得1分,利用两个公式得出有效结论得1或2分,最后得出结论得2或1分.
2.另,可以用真值表验证.
5 2 ο ο ο ο ο v
6 v 1 v 2 v 5 v 3 ο v 4 1 6 2 4
5 7 9 3 1
离散数学考试(试题及答案) 一、(10分)某项工作需要派A、B、C和D4个人中的2个人去完成,按下面3个条件,有几种派法?如何派? (1)若A去,则C和D中要去1个人; (2)B和C不能都去; (3)若C去,则D留下。 解设A:A去工作;B:B去工作;C:C去工作;D:D去工作。则根据题意应有:ACD,(B∧C),CD必须同时成立。因此 (ACD)∧(B∧C)∧(CD) (A∨(C∧ D)∨(C∧D))∧(B∨C)∧(C∨D) (A∨(C∧ D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D)) (A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D) ∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧ D∧C∧D) ∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D F∨F∨(A∧C)∨F∨F∨(C∧ D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F (A∧C)∨(B∧C∧ D)∨(C∧D∧B)∨(C∧D) (A∧C)∨(B∧C∧ D)∨(C∧D) T 故有三种派法:B∧D,A∧C,A∧D。 二、(15分)在谓词逻辑中构造下面推理的证明:某学术会议的每个成员都是专家并且是工人,有些成员是青年人,所以,有些成员是青年专家。 解:论域:所有人的集合。():是专家;():是工人;():是青年人;则推理化形式为: (()∧()),()(()∧())
下面给出证明: (1)() P (2)(c) T(1),ES (3)(()∧()) P (4)( c)∧( c) T(3),US (5)( c) T(4),I (6)( c)∧(c) T(2)(5),I (7)(()∧()) T(6) ,EG 三、(10分)设A、B和C是三个集合,则AB(BA)。 证明:ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA) x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB) (x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A)) (BA)。 四、(15分)设A={1,2,3,4,5},R是A上的二元关系,且R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>},求r(R)、s(R)和t(R)。 解 r(R)=R∪I A={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>} s(R)=R∪R-1={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>, <5,2>,<1,2>,<4,2>,<4,3>} R2={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>} R3={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<5,4>} R4={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>}=R2 t(R)=R i={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>,<5,5>}。
离散数学考试试题(A 卷及答案) 一、(10分)求(P ↓Q )→(P ∧?(Q ∨?R ))的主析取范式 解:(P ↓Q )→(P ∧?(Q ∨?R ))??(?( P ∨Q ))∨(P ∧?Q ∧R )) ?(P ∨Q )∨(P ∧?Q ∧R )) ?(P ∨Q ∨P )∧(P ∨Q ∨?Q )∧(P ∨Q ∨R ) ?(P ∨Q )∧(P ∨Q ∨R ) ?(P ∨Q ∨(R ∧?R ))∧(P ∨Q ∨R ) ?(P ∨Q ∨R )∧(P ∨Q ∨?R )∧(P ∨Q ∨R ) ?0M ∧1M ?2m ∨3m ∨4m ∨5m ∨6m ∨7m 二、(10分)在某次研讨会的休息时间,3名与会者根据王教授的口音分别作出下述判断: 甲说:王教授不是苏州人,是上海人。 乙说:王教授不是上海人,是苏州人。 丙说:王教授既不是上海人,也不是杭州人。 王教授听后说:你们3人中有一个全说对了,有一人全说错了,还有一个人对错各一半。试判断王教授是哪里人? 解 设设P :王教授是苏州人;Q :王教授是上海人;R :王教授是杭州人。则根据题意应有: 甲:?P ∧Q 乙:?Q ∧P 丙:?Q ∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以,丙至少说对了一半。因此,可得甲或乙必有一人全错了。又因为,若甲全错了,则有?Q ∧P ,因此,乙全对。同理,乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为: ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此,王教授是上海人。 三、(10分)证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系,则tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系,则由闭包的定义知r (R )?' R 。则sr (R )?s ('R )='R ,进而有tsr (R )?t ('R )='R 。
一、单项选择题(本大题共15小题,每小题1分,共15分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下列句子不是.. 命题的是( D ) A .中华人民共和国的首都是北京 B .张三是学生 C .雪是黑色的 D .太好了! 2.下列式子不是.. 谓词合式公式的是( B ) A .(?x )P (x )→R (y ) B .(?x ) ┐P (x )?(?x )(P (x )→Q (x )) C .(?x )(?y )(P (x )∧Q (y ))→(?x )R (x ) D .(?x )(P (x ,y )→Q (x ,z ))∨(?z )R (x ,z ) 3.下列式子为重言式的是( ) A .(┐P ∧R )→Q B .P ∨Q ∧R →┐R C .P ∨(P ∧Q ) D .(┐P ∨Q )?(P →Q ) 4.在指定的解释下,下列公式为真的是( ) A .(?x )(P (x )∨Q (x )),P (x ):x =1,Q (x ):x =2,论域:{1,2} B .(?x )(P (x )∧Q (x )),P (x ):x =1,Q (x ):x =2,论域: {1,2} C .(?x )(P (x ) →Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} D .(?x )(P (x )→Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} 5.对于公式(?x ) (?y )(P (x )∧Q (y ))→(?x )R (x ,y ),下列说法正确的是( ) A .y 是自由变元 B .y 是约束变元 C .(?x )的辖域是R(x , y ) D .(?x )的辖域是(?y )(P (x )∧Q (y ))→(?x )R (x ,y ) 6.设论域为{1,2},与公式(?x )A (x )等价的是( ) A .A (1)∨A (2) B .A (1)→A (2) C .A (1)∧A (2) D .A (2)→A (1) 7.设Z +是正整数集,R 是实数集,f :Z +→R , f (n )=log 2n ,则f ( ) A .仅是入射 B .仅是满射 C .是双射 D .不是函数 8.下列关系矩阵所对应的关系具有反对称性的是( ) A .???? ??????001110101 B .??????????101110001 C .??????????001100100 D .???? ??????001010101 9.设R 1和R 2是集合A 上的相容关系,下列关于复合关系R 1?R 2的说法正确的是( ) A .一定是等价关系 B .一定是相容关系
《离散数学》模拟题(补) 一.单项选择题 1.下面四组数能构成无向图的度数列的有( )。 A、 2,3,4,5,6,7; B、 1,2,2,3,4; C、 2,1,1,1,2; D、 3,3,5,6,0。 2.图的邻接矩阵为( )。 A、; B、; C、; D、。 3.设S1={1,2,…,8,9},S2={2,4,6,8},S3={1,3,5,7,9},S4={3,4,5},S5={3,5},在条件下X与()集合相等。 A、X=S2或S5 ; B、X=S4或S5; C、X=S1,S2或S4; D、X与S1,…,S5中任何集合都不等。 4.下列图中是欧拉图的有( )。 5.下述命题公式中,是重言式的为()。 A、; B、; C、; D、。 6.的主析取范式中含极小项的个数为()。 A 、2; B、 3; C、5; D、0 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 3 1 S X S X? ?且 ) ( ) (q p q p∨ → ∧)) ( )) (( ) (p q q p q p→ ∧ → ? ? q q p∧ → ?) (q p p? ? ∧) ( r q p wff→ ∧ ?) (
7.给定推理 ① P ② US ① ③ P ④ ES ③ ⑤ T ②④I ⑥ UG ⑤ 推理过程中错在( )。 A 、①->②; B 、②->③; C 、③->④; D 、④->⑤ 8.设S 1={1,2,…,8,9},S 2={2,4,6,8},S 3={1,3,5,7,9},S 4={3,4,5}, S 5={3,5},在条件 下X 与( )集合相等。 A 、X=S 2或S 5 ; B 、X=S 4或S 5; C 、X=S 1,S 2或S 4; D 、X 与S 1,…,S 5中任何集合都不等。 9.设R 和S 是P 上的关系,P 是所有人的集合, , 则表示关系 ( ) 。 A 、; B 、 ; C 、 ; D 、 。 10.下面函数( )是单射而非满射。 A 、 ; B 、 ; C 、 ; D 、。 ))()((x G x F x →?)()(y G y F →)(x xF ?)(y F )(y G )(x xG ?)())()((x xG x G x F x ??→?∴3 1S X S X ??且},|,{的父亲是y x P y x y x R ∧∈><=},|,{的母亲是y x P y x y x S ∧∈><=R S 1-},|,{的丈夫是y x P y x y x ∧∈><},|,{的孙子或孙女是y x P y x y x ∧∈><Φ},|,{的祖父或祖母是y x P y x y x ∧∈><12)(,:2-+-=→x x x f R R f x x f R Z f ln )(,:=→+的最大整数表示不大于x x x x f Z R f ][],[)(, :=→12)(,:+=→x x f R R f
2016年考研数学(三)真题 一、填空题:1-6小题,每小题4分,共24分. 把答案填在题中横线上. (1)()11lim ______.n n n n -→∞ +?? = ??? (2)设函数()f x 在2x =的某邻域内可导,且()() e f x f x '=,()21f =,则()2____.f '''= (3)设函数()f u 可微,且()1 02 f '=,则()224z f x y =-在点(1,2)处的全微分() 1,2d _____.z = (4)设矩阵2112A ?? = ?-?? ,E 为2阶单位矩阵,矩阵B 满足2BA B E =+,则=B . (5)设随机变量X Y 与相互独立,且均服从区间[]0,3上的均匀分布,则{}{} max ,1P X Y ≤=_______. (6)设总体X 的概率密度为()()121,,,,2 x n f x e x X X X -= -∞<<+∞为总体X 的简单随机样本,其 样本方差为2 S ,则2 ____.ES = 二、选择题:7-14小题,每小题4分,共32分. 每小题给出的四个选项中,只有一项符合题目要求,把所选项前的字母填在题后的括号内. (7)设函数()y f x =具有二阶导数,且()0,()0f x f x '''>>,x ?为自变量x 在点0x 处的增量,d y y ?与分别为()f x 在点0x 处对应的增量与微分,若0x ?>,则 (A) 0d y y <. (B) 0d y y <. (C) d 0y y ?<<. (D) d 0y y < . [ ] (8)设函数()f x 在0x =处连续,且()22 lim 1h f h h →=,则 (A) ()()000f f -'=且存在 (B) ()()010f f -'=且存在 (C) ()()000f f +'=且存在 (D)()()010f f +'=且存在 [ ] (9)若级数 1n n a ∞ =∑收敛,则级数 (A) 1n n a ∞ =∑收敛 . (B ) 1(1) n n n a ∞ =-∑收敛. (C) 11 n n n a a ∞ +=∑收敛. (D) 1 1 2n n n a a ∞ +=+∑收敛. [ ]
北京语言大学网络教育学院 《离散数学》模拟试卷一 注意: 1.试卷保密,考生不得将试卷带出考场或撕页,否则成绩作废。请监考老师负责监督。 2.请各位考生注意考试纪律,考试作弊全部成绩以零分计算。 3.本试卷满分100分,答题时间为90分钟。 4.本试卷分为试题卷和答题卷,所有答案必须答在答题卷上,答在试题卷上不给分。 一、【单项选择题】(本大题共15小题,每小题3分,共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的,请将正确选项前的字母填在答题卷相应题号处。 1、在由3个元素组成的集合上,可以有 ( ) 种不同的关系。 [A] 3 [B] 8 [C]9 [D]27 2、设{}{}1,2,3,5,8,1,2,5,7A B A B ==-=,则( )。 [A] 3,8 [B]{}3 [C]{}8 [D]{}3,8 3、若X 是Y 的子集,则一定有( )。 [A]X 不属于Y [B]X ∈Y [C]X 真包含于 Y [D]X∩Y=X 4、下列关系中是等价关系的是( )。 [A]不等关系 [B]空关系 [C]全关系 [D]偏序关系 5、对于一个从集合A 到集合B 的映射,下列表述中错误的是( )。 [A]对A 的每个元素都要有象 [B] 对A 的每个元素都只有一个象 [C]对B 的每个元素都有原象 [D] 对B 的元素可以有不止一个原象 6、设p:小李努力学习,q:小李取得好成绩,命题“除非小李努力学习,否则他不能取得好成绩”的符号化形式为( )。 [A]p→q [B]q→p [C]┐q→┐p [D]┐p→q 7、设A={a,b,c},则A 到A 的双射共有( )。 [A]3个 [B]6个 [C]8个 [D]9个
2016考研数学(一)真题完整版 一、选择题:1~8小题,每小题4分,共32分,下列每小题给出的四个选项中,只有一项符合题目要求的,请将所选项前的字母填在答题纸...指定位置上. (1)若反常积分 () 11b a dx x x +∞ +? 收敛,则( ) ()()()()11111111 A a b B a b C a a b D a a b <>>><+>>+>且且且且 (2)已知函数()()21,1 ln ,1 x x f x x x -?=? ≥??,则()f x 的一个原函数是( ) ()()()()()()()()()()()()()()()()22 22 1,11,1 ln 1,1ln 11,1 1,11,1 ln 11,1ln 11,1x x x x A F x B F x x x x x x x x x x x C F x D F x x x x x x x ??-<-?==?? -≥+-≥??????-<-?==?? ++≥-+≥???? (3)若( ) ( )2 2 2 211y x y x =+-=++是微分方程()()y p x y q x '+=的两 个解,则()q x =( ) ()()()() () ()222 2 313111x x A x x B x x C D x x +-+- ++ (4)已知函数(),0111 ,,1,2,1 x x f x x n n n n ≤?? =?<≤=?+?K ,则( ) (A )0x =是()f x 的第一类间断点 (B )0x =是()f x 的第二类间断点 (C )()f x 在0x =处连续但不可导 (D )()f x 在0x =处可导 (5)设A ,B 是可逆矩阵,且A 与B 相似,则下列结论错误的是( ) (A )T A 与T B 相似 (B )1A -与1 B -相似 ( C )T A A +与T B B +相似 (D )1 A A -+与1 B B -+相似 (6)设二次型()2 2 2 123123121323,,444f x x x x x x x x x x x x =+++++,则()123,,2f x x x =在 空间直角坐标下表示的二次曲面为( ) (A )单叶双曲面 (B )双叶双曲面 (C )椭球面 (C )柱面
离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】
326《离散数学》期末考试题(B ) 一、填空题(每小题3分,共15分) 1.设,,},,{{b a b a A =?},则-A ? = ( ),-A {?} = ( ), )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素,则A 上的二元关系有( )个,其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ,对于其上的整除关系“|”,元素( )不存在补元. 5.当n ( )时,n 阶完全无向图n K 是平面图,当当n 为( )时,n K 是欧拉图. 二.1. 若n B m A ==||,||,则=?||B A ( ),A 到B 的2元关系共有( )个,A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)},则( )是单射,( )是满射,( )是双射. 3. 下列5个命题公式中,是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(; (2))(q p p ∨→; (3))(q p p ∧→; (4)q q p p →∨∧?)(; (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合,“|”是其上的整除关系,则3的补元( ),4的补元( ),6的补元( ).
全国2009年4月自学考试离散数学试题(附答案) 课程代码:02324 一、单项选择题(本大题共15小题,每小题1分,共15分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下列为两个命题变元P,Q的小项是() A.P∧Q∧? P B.? P∨Q C.? P∧Q D.? P∨P∨Q 2.下列语句中是真命题的是() A.我正在说谎B.严禁吸烟 C.如果1+2=3,那么雪是黑的D.如果1+2=5,那么雪是黑的 3.设P:我们划船,Q:我们跑步。命题“我们不能既划船又跑步”符号化为() A.? P∧? Q B.? P∨? Q C.?(P?Q)D.?(? P∨? Q) 4.命题公式(P∧(P→Q))→Q是() A.矛盾式B.蕴含式 C.重言式D.等价式 5.命题公式?(P∧Q)→R的成真指派是() A.000,001,110,B.001,011,101,110,111 C.全体指派D.无 6.在公式(x ?)F(x,y)→(?y)G(x,y)中变元x是() A.自由变元B.约束变元 C.既是自由变元,又是约束变元D.既不是自由变元,又不是约束变元 7.集合A={1,2,…,10}上的关系R={
《离散数学》试卷(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)三门课程都不选的学生有多少? (2)只选修计算机课程的学生有多少?
全国2018年7月自学考试离散数学试题 课程代码:02324 一、单项选择题(本大题共15小题,每小题1分,共15分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下列句子不是 ..命题的是() A.中华人民共和国的首都是北京B.张三是学生 C.雪是黑色的D.太好了! 2.下列式子不是 ..谓词合式公式的是() A.(?x)P(x)→R(y) B.(?x) ┐P(x)?(?x)(P(x)→Q(x)) C.(?x)(?y)(P(x)∧Q(y))→(?x)R(x) D.(?x)(P(x,y)→Q(x,z))∨(?z)R(x,z) 3.下列式子为重言式的是() A.(┐P∧R)→Q B.P∨Q∧R→┐R C.P∨(P∧Q) D.(┐P∨Q)?(P→Q) 4.在指定的解释下,下列公式为真的是() A.(?x)(P(x)∨Q(x)),P(x):x=1,Q(x):x=2,论域:{1,2} B.(?x)(P(x)∧Q(x)),P(x):x=1,Q(x):x=2,论域: {1,2} C.(?x)(P(x) →Q(x)),P(x):x>2,Q(x):x=0,论域:{3,4} D.(?x)(P(x)→Q(x)),P(x):x>2,Q(x):x=0,论域:{3,4} 5.对于公式(?x) (?y)(P(x)∧Q(y))→(?x)R(x,y),下列说法正确的是() A.y是自由变元B.y是约束变元 C.(?x)的辖域是R(x, y) D.(?x)的辖域是(?y)(P(x)∧Q(y))→(?x)R(x,y) 6.设论域为{1,2},与公式(?x)A(x)等价的是() A.A(1)∨A(2) B.A(1)→A(2) C.A(1)∧A(2) D.A(2)→A(1) 7.设Z+是正整数集,R是实数集,f:Z+→R, f(n)=log2n ,则f() 1
模 拟 试 题 1 一.将下面命题写成符号表达式。(3,4题要使用句后给定的谓词。) 1.如果小张去,则小王与小李都不去,否则小王与小李不都去。 2.我们不能既划船又跑步。 3.有些运动员是大学生。(L(x):x 是运动员;,S(x):x 是大学生。) 4.每个运动员都钦佩一些教练。( L(x):x 是运动员,A(x,y):x 钦佩y ,J(x):x 是教练。) 二.写出命题公式 (Q →?P)→Q 的主合取范式。(要求有解题过程) 三.令集合A={1,{1}}, B={1}, P(A)表示A 的幂集 1.判断下面命题的真值。并说明原因,否则不给分。 (1) B ∈A, (2) P(B) ?P(A) (3) {Φ}?P(A) (4) {1}∈P(B) 2.分别计算: (1) A ×P(B) (2) A ⊕B (3) P(A)-P(B) 四.用谓词逻辑推理证明下面推理的有效性。 ?x(A(x)∧(B(x)→?C(x))), ?x(A(x) → (C(x) ∨?D(x))), ?x(A(x) →D(x)) ? ?x(A(x) ∧? B(x)) 五.令A={1,2,3,4 },给出A中关系R 1,R 2,R 3, R 4如下: R 3={<1,2>,<2,2>,<1,3>,<2,4>,<1,1>,<1,4>, <3,3>,<4,4>} R 4={<2,2>,<3,2>,<4,1>,<2,1>,<1,4>,<2,3>,<2,4>,<1,2>,<3,3>,<3,4>, <4,2>,<4,4>,<4,3>,<1,1>} 1.求复合关系~R 4oR 2c 。 2.分别画出R 1、R 3、R 4关系的有向图。 3.分别指出上面各个关系是否具有自反性、反自反性、对称性、反对称性、传递性。 4.上述四个关系中,哪些是等价关系?哪些是偏序关系?哪些是从A到A的函数?如果是等价关系,请写出该等价关系的各个等价类。 如果是函数,请指出该函数的类型。 六.设I 是整数集合,在I 上定义二元运算 * 如下:对于任何a,b ∈I a *b=a+ b +4 求证是个交换群。 R 2: 1 2 3 4 ???? ? ? ??? ???=0001111011101110M R1
2016考研数学三真题及答案 一、填空题:1-6小题,每小题4分,共24分. 把答案填在题中横线上. (1)()11lim ______.n n n n -→∞ +?? = ??? (2)设函数()f x 在2x =的某邻域内可导,且()() e f x f x '=,()21f =,则()2____.f '''= (3)设函数()f u 可微,且()1 02 f '= ,则()224z f x y =-在点(1,2)处的全微分() 1,2d _____.z = (4)设矩阵2112A ?? = ?-?? ,E 为2阶单位矩阵,矩阵B 满足2BA B E =+,则=B . (5)设随机变量X Y 与相互独立,且均服从区间[]0,3上的均匀分布,则 {}{}max ,1P X Y ≤=_______. (6)设总体X 的概率密度为()()121,,,,2 x n f x e x X X X -= -∞<<+∞为总体X 的简 单随机样本,其样本方差为2 S ,则2 ____.ES = 二、选择题:7-14小题,每小题4分,共32分. 每小题给出的四个选项中,只有一项符合题目要求,把所选项前的字母填在题后的括号内. (7)设函数()y f x =具有二阶导数,且()0,()0f x f x '''>>,x ?为自变量x 在点0x 处的增量,d y y ?与分别为()f x 在点0x 处对应的增量与微分,若0x ?>,则 (A) 0d y y <. (B) 0d y y <. (C) d 0y y ?<<. (D) d 0y y < . [ ] (8)设函数()f x 在0x =处连续,且()22 lim 1h f h h →=,则 (A) ()()000f f -'=且存在 (B) ()()010f f -'=且存在 (C) ()()000f f +'=且存在 (D)()()010f f +'=且存在 [ ] (9)若级数 1 n n a ∞ =∑收敛,则级数
一.判断题(共10小题,每题1分,共10分) 在各题末尾的括号内画 表示正确,画 表示错误: 1.设p、q为任意命题公式,则(p∧q)∨p ? p ( ) 2.?x(F(y)→G(x)) ? F(y)→?xG(x)。( ) 3.初级回路一定是简单回路。( ) 4.自然映射是双射。( ) 5.对于给定的集合及其上的二元运算,可逆元素的逆元是唯一的。( ) 6.群的运算是可交换的。( ) 7.自然数集关于数的加法和乘法
列为。 19.n阶无向简单连通图G的生成树有条边。 20.7阶圈的点色数是。 三、运算题(共5小题,每小题8分,共40分) 21.求?xF(x)→?yG(x,y)的前束范式。 22.已知无向图G有11条边,2度和3度顶点各两个,其余为4度顶点,求G 的顶点数。 23.设A={a,b,c,d,e,f},R=I A?{,},则R是A上的等价关系。求等价类[a]R、[c]R及商集A/R。 24.求图示带权图中的最小生成树,并计算最小生成树的权。 25.设R*为正实数集,代数系统< R*,+>、< R*,·>、< R*,/>中的运算依次为普通加法、乘法和除法运算。试确定这三个代数系统是否为群?是群者,求其单位元及每个元素的逆元。 四、证明题(共3小题,共20分) 26 (8分)在自然推理系统P中构造下述推理的证明: 前题:p→(q∨r),?s→?q,p∧?s 结论:r 27 (6分)设
全国2010年7月自学考试离散数学试题 课程代码:02324 一、单项选择题(本大题共15小题,每小题1分,共15分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下列句子不是..命题的是( D ) A .中华人民共和国的首都是北京 B .张三是学生 C .雪是黑色的 D .太好了! 2.下列式子不是..谓词合式公式的是( B ) A .(?x )P (x )→R (y ) B .(?x ) ┐P (x )?(?x )(P (x )→Q (x )) C .(?x )(?y )(P (x )∧Q (y ))→(?x )R (x ) D .(?x )(P (x ,y )→Q (x ,z ))∨(?z )R (x ,z ) 3.下列式子为重言式的是( ) A .(┐P ∧R )→Q B .P ∨Q ∧R →┐R C .P ∨(P ∧Q ) D .(┐P ∨Q )?(P →Q ) 4.在指定的解释下,下列公式为真的是( ) A .(?x )(P (x )∨Q (x )),P (x ):x =1,Q (x ):x =2,论域:{1,2} B .(?x )(P (x )∧Q (x )),P (x ):x =1,Q (x ):x =2,论域: {1,2} C .(?x )(P (x ) →Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} D .(?x )(P (x )→Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} 5.对于公式(?x ) (?y )(P (x )∧Q (y ))→(?x )R (x ,y ),下列说法正确的是( ) A .y 是自由变元 B .y 是约束变元 C .(?x )的辖域是R(x , y ) D .(?x )的辖域是(?y )(P (x )∧Q (y ))→(?x )R (x ,y ) 6.设论域为{1,2},与公式(?x )A (x )等价的是( ) A .A (1)∨A (2) B .A (1)→A (2) C .A (1)∧A (2) D .A (2)→A (1) 7.设Z +是正整数集,R 是实数集,f :Z +→R , f (n )=log 2n ,则f ( ) A .仅是入射 B .仅是满射 C .是双射 D .不是函数 8.下列关系矩阵所对应的关系具有反对称性的是( ) A .???? ? ?????001110101 B .???? ? ?????101110001
一、 填空 1.不能再分解的命题称为,至少包含一个联结词的命题称为。 2.一个命题公式A(P , Q, R)为真的所有真值指派是000, 001, 010, 100,则其主析取范式是,其主合取范式是。 3.设 {},{},{},则( A ? B ) ⊕C = 。 4.幂集 P(P(?)) = 。 5.设A 为任意集合,请填入适当运算符,使式子?;’=?成立。 6.设{0,1,2,3,6},{〈〉≠y ∧(∈A)∧y≡x( 3)},则D(R),R(R)。 7.称集合S 是给定非空集合A 的覆盖:若{S 1,S 2,…,},其中?,≠?,1,2,…,n ,且 ;进一步若 ,则S 是集合A 的划分。 8.两个重言式的析取是 式,一个重言式和一个永假式的合取式是 式。 9.公式 ┐(P ∨Q) ←→(P ∧Q)的主析取范式是 。 10. 已知Π={{a}{}}是{}的一个划分,由Π决定的A 上的一个等价关系是 。 二、 证明及求解 1.求命题公式(P →Q )→(Q ∨P )的主析取范式。 2.推理证明题 1)?P ∨Q ,?Q ∨R ,R →S ?P →S 。 2) (?x)(P(x)→Q(y)∧R(x)),(?x)P(x)?Q(y)∧(?x)(P(x)∧R(x)) 3.设{0,1,2,3},{〈〉∈A ∧(1∨2x )},{〈〉∈A ∧(2)}。试求οο。 4.证明:R 是传递的?R *R ?R 。 5.设R 是A 上的二元关系,{| 存在c ∈A ,使∈R ,且
离散数学试题(B卷答案1) 一、证明题(10分) 1)(P∧(Q∧R))∨(Q∧R)∨(P∧R)R 证明: 左端(P∧Q∧R)∨((Q∨P)∧R) ((P∧Q)∧R))∨((Q∨P)∧R) ((P∨Q)∧R)∨((Q∨P)∧R) ((P∨Q)∨(Q∨P))∧R ((P∨Q)∨(P∨Q))∧R T∧R(置换)R 2) x (A(x)B(x))xA(x)xB(x) 证明:x(A(x)B(x))x(A(x)∨B(x)) x A(x)∨xB(x) xA(x)∨xB(x) xA(x)xB(x) 二、求命题公式(P∨(Q∧R))(P∧Q∧R)的主析取范式和主合取范式(10分)。 证明:(P∨(Q∧R))(P∧Q∧R)(P∨(Q∧R))∨(P∧Q∧R)) (P∧(Q∨R))∨(P∧Q∧R) (P∧Q)∨(P∧R))∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R))∨(P∧Q∧R))∨(P∧Q∧R) m0∨m1∨m2∨m7 M3∨M4∨M5∨M6 三、推理证明题(10分) 1)C∨D,(C∨D)E, E(A∧B),(A∧B)(R∨S)R∨S证明:(1) (C∨D) E ?P (2) E(A∧B) ??P (3) (C∨D)(A∧B) T(1)(2),I (4) (A∧B)(R∨S)??P (5) (C∨D)(R∨S) ? T(3)(4),I (6) C∨D P (7) R∨S T(5),I 2) x(P(x)Q(y)∧R(x)),xP(x)Q(y)∧x(P(x)∧R(x)) 证明(1)xP(x) P
(2)P(a) T(1),ES (3)x(P(x)Q(y)∧R(x)) P (4)P(a)Q(y)∧R(a) T(3),US (5)Q(y)∧R(a) T(2)(4),I (6)Q(y) T(5),I (7)R(a) T(5),I (8)P(a)∧R(a) T(2)(7),I (9)x(P(x)∧R(x)) T(8),EG (10)Q(y)∧x(P(x)∧R(x)) T(6)(9),I 四、某班有25名学生,其中14人会打篮球,12人会打排球,6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。而6个会打网球的人都会打另外一种球,求不会打这三种球的人数(10分)。 解:A,B,C分别表示会打排球、网球和篮球的学生集合。则|A|=12,|B|=6,|C|=14,|A∩C|=6,|B∩C|=5,|A∩B∩C|=2。 先求|A∩B|。 ∵6=|(A∪C)∩B|=|(A∩B)∪(B∩C)|=|(A∩B)|+|(B∩C)|-|A∩B∩C|=|(A∩B)|+5-2,∴|(A∩B)|=3。 于是|A∪B∪C|=12+6+14-6-5-3+2=20。不会打这三种球的人数25-20=5。五、已知A、B、C是三个集合,证明A-(B∪C)=(A-B)∩(A-C)(10分)。 证明:∵x A-(B∪C) x A∧x(B∪C) xA∧(xB∧x C) (x A∧x B)∧(x A∧xC) x(A-B)∧x(A-C) x(A-B)∩(A-C) ∴A-(B∪C)=(A-B)∩(A-C) 六、已知R、S是N上的关系,其定义如下:R={
习题参考答案 1、设无向图G有16条边,有3个4度结点,4个3度结点,其余结点的度数均小于3,问:G中至少有几个结点。 阮允准同学提供答案: 解:设度数小于3的结点有x个,则有 3×4+4×3+2x≥2×16 解得:x≥4 所以度数小于3的结点至少有4个 所以G至少有11个结点 2、设无向图G有9个结点,每个结点的度数不是5就是6,证明:G中至少有5个6度结点或至少有6个5度结点。 阮允准同学答案: 证明:由题意可知:度数为5的结点数只能是0,2,4,6,8。 若度数为5的结点数为0,2,4个,则度数为6的结点数为9,7,5个结论成立。 若度数为5的结点数为6,8个,结论显然成立。 由上可知,G中至少有5个6度点或至少有6个5度点。 3、证明:简单图的最大度小于结点数。
阮同学认为题中应指定是无向简单图. 晓津证明如下:设简单图有n个结点,某结点的度为最大度,因为简单图任一结点没有平行边,而任一结点的的边必连有另一结点,则其最多有n-1条边与其他结点相连,因此其度数最多只有n-1条,小于结点数n. 4、设图G有n个结点,n+1条边,证明:G中至少有一个结点度数≥3 。阮同学给出证明如下: 证明:设G中所有结点的度数都小于3,即每个结点度数都小于等于2,则所有结点度数之和小于等于2n,所以G的边数必小于等于n,这和已知G有n+1条边相矛盾。所以结论成立。 5、试证明下图中两个图不同构。 晓津证明:同构的充要条件是两图的结点和边分别存在一一对应且保持关联关系。我们可以看出,(a)图和(b)图中都有一个三度结点,(a)图中三度结点的某条边关联着两个一度结点和一个二度结点,而(b)图中三度结点关联着两个二度结点和一个一度结点,因此可断定二图不是同构的。 6、画出所有5个结点3条边,以及5个结点7条边的简单图。 解:如下图所示:(晓津与阮同学答案一致)