1、离散数学考试题(后附详细答案)一、 命题符号化（共6小题，每小题3分，共计18分）1. 用命题逻辑把下列命题符号化a) 假如上午不下雨，我去看电影，否则就在家里读书或看报。设P表示命题“上午下雨”，Q表示命题“我去看电影”，R表示命题“在家里读书”，S表示命题“在家看报”，命题符号化为：（PQ）(PRS)b) 我今天进城，除非下雨。设P表示命题“我今天进城”，Q表示命题“天下雨”，命题符号化为：QP或PQc) 仅当你走，我将留下。设P表示命题“你走”，Q表示命题“我留下”，命题符号化为： QP2. 用谓词逻辑把下列命题符号化a) 有些实数不是有理数设R(x)表示“x是实数”，Q(x)表示“x是
2、有理数”，命题符号化为：$x(R(x) Q(x) 或 x(R(x) Q(x)b) 对于所有非零实数x，总存在y使得xy=1。设R(x)表示“x是实数”，E(x,y)表示“x=y”,f(x,y)=xy, 命题符号化为： x(R(x) E(x,0) $y(R(y) E(f(x,y),1)c) f 是从A到B的函数当且仅当对于每个aA存在唯一的bB，使得f(a)=b.设F(f)表示“f是从A到B的函数”, A(x)表示“xA”, B(x)表示“xB”,E(x,y)表示“x=y”, 命题符号化为：F(f)a(A(a)$b(B(b) E(f(a),b) c(S(c) E(f(a),c) E(a,b)二、
3、 简答题（共6道题，共32分）1. 求命题公式(P(QR)(R(QP)的主析取范式、主合取范式，并写出所有成真赋值。（5分）(P(QR)(R(QP)（PQR）(PQR) (（PQR）(PQR) (PQR) （PQR）).(（PQR） (PQR) (PQR) （PQR）)(PQR) (PQR) 这是主合取范式公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为（PQR)（PQR)（PQR)（PQR)（PQR)（PQR)2. 设个体域为1,2,3，求下列命题的真值（4分）a) x$y(x+y=4)b) $yx (x+y=4)a) T b) F3. 求x(F(x)G(x
4、)($xF(x)$xG(x)的前束范式。（4分）x(F(x)G(x)($xF(x)$xG(x) x(F(x)G(x)($yF(y)$zG(z) x(F(x)G(x)y$z(F(y)G(z) $xy$z(F(x)G(x) (F(y)G(z)4. 判断下面命题的真假，并说明原因。（每小题2分，共4分）a) （AB）C=(A-B) (A-C)b) 若f是从集合A到集合B的入射函数，则|A|B|a) 真命题。因为（AB）C=（AB）C=（AC）（BC）=（A-C）（B-C）b) 真命题。因为如果f是从集合A到集合B的入射函数，则|ranf|=|A|，且ranfB,故命题成立。5. 设A是有穷集，|A|
5、=5，问（每小题2分，共4分）a) A上有多少种不同的等价关系？b) 从A到A的不同双射函数有多少个？a) 52 b) 5!=1206. 设有偏序集，其哈斯图如图1，求子集B=b,d,e的最小元，最大元、极大元、极小元、上界集合、下界集合、上确界、下确界，(5分)f g d e b ca图1B的最小元是b，无最大元、极大元是d和e、极小元是b、上界集合是g、下界集合是a,b、上确界是g、下确界是b.7. 已知有限集S=a1,a2,an,N为自然数集合，R为实数集合，求下列集合的基数S;P(S);N,Nn;P(N);R,RR,o,1N（写出即可）(6分)KS=n; KP(S)=; KN=0,KN
6、n=0, KP(N)=; KR=, K=RR= ,K0,1N= 三、 证明题（共3小题，共计40分）1. 使用构造性证明，证明下面推理的有效性。（每小题5分，共10分）a) A(BC),(EF)C, B(AS)BEb) x(P(x)Q(x), x(Q(x)R(x)，$xR(x) $xP(x)a) 证 （1）B P(附加条件) （2）B(AS) P (3) AS T(1)(2) I (4) A T(3) I (5) A(BC) P (6) BC T(4)(5) I (7) C T(6) I (8) (EF)C P (9) (EF) T(7)(8) I (10) EF T(9) E (11) E
7、T(10) I (12) BE CPb) 证 (1) $xR(x) P (2) R(c) ES(1) (3) x(Q(x)R(x) P (4) Q(c)R(c) US(3) (5) Q(c) T(2)(4) I (6) x(P(x)Q(x) P (7) P(c)Q(c) US(6) (8) P(c) T(5)(7) I (9) $xP(x) EG(8)2. 设R1是A上的等价关系，R2是B上的等价关系，A且B，关系R满足：,R，当且仅当R1且R2。试证明：R是AB上的等价关系。（10分）证 任取,ABxA yBR1R2,R，故R是自反的任取,RR1R2R1R2,R.故R是对称的。任取,R,RR
8、1R2R1R2(R1R1)(R2R2) R1R2,R, 故R是传递的。综上所述R是AB上的等价关系。3. 用伯恩斯坦定理证明（0,1和(a,b)等势。（10分）证 构造函数f：（0,1(a,b)，f(x)=,显然f是入射函数 构造函数g: (a,b)（0,1，,显然g是入射函数， 故（0,1和(a,b)等势。由于，所以4. 设R是集合A上的等价关系，A的元素个数为n，R作为集合有s个元素，若A关于R的商集A/R有r个元素，证明：rsn2。（10分）证 设商集A/R的r个等价类的元素个数分别为m1,m2,mr，由于一个划分对应一个等价关系，m1+m2+mr=n， 由于（r个数的平方的平均值大于等
9、于这r个数的平均值的平方），所以，即四、 应用题（10分）在一个道路上连接有8个城市，分别标记为a,b,c,d,e,f,g,h。城市之间的直接连接的道路是单向的，有ab, ac, bg, gb, cf, fe, bd, df.对每一个城市求出从它出发所能够到达的所有其他城市。解 把8个城市作为集合A的元素，即A=a,b,c,d,e,f,g,h，在A上定义二元关系R，<面定义的哪种运算关于集合A是不封闭的？（ ） A、 x*y=maxx,y B、 x*y=minx,y C、 x*y=GCD(x,y)，即x,y的最大公约数 D、 x*y=LCM(x,y)，即x,y的最小公倍数10、集合X中的关
10、系R，其矩阵是 ，则关于R的论述中正确的是（ ）。A、R是对称的 B、R是反对称的C、R是反自反的 D、R中有7个元素11. 下列各组数中，哪个可以构成无向图的度数列（ ）。A.1，1，1，2，2 B.2，2，2，2，3C.1，2，2，4，6 D.2，3，3，312. 是定义在Z上的二元运算，则的幺元和零元分别是（ ）。A.不存在，0 B.0，1C.1，不存在 D.不存在，不存在13. 设为自然数，且则分别是（ ）。A.0，0 B.0，0C.0，0 D.0，014. 下列命题公式中是矛盾式的有（ ）。A. B.C. D. 15. 下列各Hasse图中，是格的有（ ）。A. B. C. D.16
11、 下列命题公式中是永假式的有（ ）。A. B.C. D.17. 设命题公式(P(QP)，记作G，则使G的真值指派为0的P，Q的取值是( )。 A.(0,0) B.(0,1) C.(1,0) D. (1,1)18. 与命题公式P（QR）等值的公式是( )。 A.(PQ)R B.(PQ)R C.(PQ)R D. P(QR)19. 命题公式(PQ)P是( )。 A.永真式 B.永假式 C.可满足式 D.合取范式20. 设命题公式，则G与H的关系是( ) 。A. B. C. D.21谓词公式中量词x的辖域是( )。A B. P(x) C. D.22设个体域为整数集，下列公式中其值为1的是( )。A.
12、B.C. D.23设L(x)：x是演员，J(x)：x是老师，A(x,y)：x佩服y. 那么命题“所有演员都佩服某些老师”符号化为( )。A. B. C. D.24在谓词演算中，P(a)是的有效结论，根据是 ( )。 A.US规则 B.UG规则 C.ES规则 D.EG规则25. 在图G中，结点总度数与边数的关系是( )。A.deg(vi)=2E B. deg(vi)=E C. D. 26. 设G是有n个结点的无向完全图，则图G的边数为( )；设D是有n个结点的有向完全图，则图D的边数为( )。A. n(n1) B. n(n+1) C. n(n1)/2 D. n(n+1)/227. 仅有一个孤立结
13、点的图称为( )。A.零图 B.平凡图 C.补图 D.子图28. 设G为无向简单图，V=n，D(G)为G的最大度，则有（ ）。A. D(G)n D. D(G)n29. 图G与G的结点和边分别存在一一对应关系，是GG(同构)的( )。A.充分条件 B.必要条件 C.充分必要条件 D.既非充分也非必要条件30. 设，则与V能构成强连通图的边集合是( )。A.B.C.D.31. 相邻矩阵具有对称性的图一定是( )。A.有向图 B.无向图 C.混合图 D.简单图32. 无向图G是欧拉图，当且仅当( )。A.G的所有结点的度数全为偶数 B.G的所有结点的度数全为奇数C.G连通且所有结点的度数全为偶数 D
14、.G连通且所有结点的度数全为奇数33. 设为连通平面图且有r个面，则r( )。A. mn+2 B.nm2 C.n+m-2 D.m+n+234. 设G是由5个结点组成的完全图，则从G中删去( )条边可以得到树。 A.4 B.5 C.6 D.1035. 由5个结点可构成的根树中，其叉数m最多为( )。A.2 B.3 C.5 D. 436. 下图是( ) 。A.完全图 B. 哈密顿图 C.欧拉图 D.平面图h h h h h h 图 37. 设集合A1,2,3,10,在集合A上定义的运算，不是封闭的为( )。A.a,bA, a*b=lcma,b(最小公倍数) B.a,bA, a*b=gcda,b(最
15、大公约数)C.a,bA, a*b=maxa,b D.a,bA, a*b=mina,b38. 在自然数N上定义的二元运算，满足结合律的是( )。A.ab=ab B. ab=a+2b C. ab=maxa,b D. ab=ab39. 下列代数系统(G,*)中，其中*是加法运算. ( )不是群。A.G为整数集合 B.G为偶数集合 C.G为有理数集合 D.G为自然数集合40. 设s1，s2，s3是三个置换，其中 s1(1 2)(2 3)(1 3),s2=(2 4)(1 4),s3=(1 3 2 4)则s3可以表成( )。A. B.s1s2 C. D.s2s141. 下列图表示的偏序集中，是格的为( )
16、。A. B.C. D. 42. 设是布尔代数，则下式不成立的是( )。A. B. C. D.43. 布尔代数式=( )。A. B. C. D.44. 设集合A1,2，B=a,b,c,C=c,d, 则A(BC)( )。A., B., C., D.,45. 设A0,a,B=1,a,3,则AB的恒等关系是( )。A. , B., C., D. ,46. 设A=a，b，c，R=，则R具有性质（ ）。A.自反的 B.反自反的 C.反对称的 D.等价的47. 设集合是从A到B的函数， ，则s是( )。A.双射 B.满射但不是单射 C.单射但不是满射 D.非单射也非满射48.下列式子中正确的是（ ）。A.=
17、0 B. C.a,b D.49.有向图的邻接矩阵中，行元素之和是对应结点的( )，列元素之和是对应结点的( ) 。A.度数 B. 出度 C.最大度数 D.入度50. 给定无向图如下所示，下面给出的顶点集子集中，不是点割集的是（ ）。 a f b g c h 图d e A.b,d B.d C.e D.f,h 51 谓词公式xA(x)xA(x)的类型是（ ）。A.永真式 B.矛盾式C.非永真式的可满足式 D.不属于(A),(B),(C)任何类型52. 谓词公式取真值为1的充分必要条件是( )。A.对任意y，使P(y)都取真值1 B.存在一个y0，使P(y0)取真值1 C.存在某些y，使P(y)都取
18、真值1 D.存在y0，使P(y0)取真值053. 设G是群，当G有（ ）个元素时，不能肯定G是交换群。A.4 B.5 C.6 D.754若集合Aa,b,c,为空集合，则下列表示正确的是( )。A.aAB.aAC.aAD.A55. 设A, B, C都是集合，如果ACBC，则有( ) 。 A.AB B.AB C.当ACBC时,有A=B D.当C=U时, 有AB 56. 设S1，S2, S3P(), S4P()，以下命题为假的是( )。A.S2S4 B.S1 S3， C.S4 S2 D.S4 S357.设G是有6个元素的循环群，a是生成元素，则G的子集（ ）是子群。A.a B.a,e C.e,a3
19、D.e,a, a258.设集合A=a,b,c,d,e,半序关系R的哈斯图如下，假设A的子集B=c,d,e,则元素c为B的（ ）。A.下界 B.最大下界C.最小上界 D.以上答案都不对59. 设Gx$yP(x,y)Q(z,w)，下面三个命题为真的是( )。A.G是前束范式 B.G不是前束范式 C.G不是一阶公式 D.G是永真式60对任意集合S，SS，满足( )。A.幂等律 B.零一律 C.同一律 D.互补律61设命题公式，则使公式G取真值为1的P，Q，R赋值分别是( )。 A. 0，0，0 B. 0，0，1 C.0，1，0 D.1，0，062设a是集合A的元素，则以下正确的是( )。 A. B.
20、 C. D.63设集合A1，2，3，4，B：2，4，6，9，那么集合A，B的对称差AB( )。 A.1，3 B.2，4，6 C.1，3，6，9 D.1，2，3，4，6，964. 有向完全图D，则图D的边数是( )。 A.(E1)2 B.(一1)2 C.() D.()65设G是有n个结点，m条边的连通阻，必须删去G的( )条边，才能确定G的一棵生成树。 A.m一n1 B.n一m C.mn1D.nm166. 设N为自然数集合，在下面4种运算下不构成代数系统的是（ ）。A. xy = x+y2xy B.xy = x+y C. xy = xy D.xy = |x|+|y|67.已知图G的相邻矩阵为，则
21、G有（ ）。A.6个点，度为4 B.5个点，度为6 C.4个点，度为3 D.4个点，度为668. 设集合A=1，2，3，10，半序关系是A上的整除关系，则半序集（A，）上的元素10是集合A的（ ）。A.最大元 B.最小元 C.极大元 D.极小元二、填空题1. 代数格（L，）中的运算和满足的算律有_、_、_。2、A是含有3个元素的集合，在A上可以定义_个不同的等价关系。3、R是实数集合，R中的关系g= _ 从R到R的函数（填“是”或“不是”）。4、是群，|G|1，则G中的零元_。5、当n是_值时，无向完全图Kn是欧拉图。6、I是整数集合，代数系统（是通常乘法）的幺元是_, -1的逆元是_。7、元
22、素数目不超过_的格一定是链。8、公式的主合取范式为_。9、的有效结论是_。10、已知公式A(p，q，r)的主合取范式为MMM，它的主析取范式为(写成编码形式)_。11、设A=a,b，B=0,1,2，那么可定义_种不同的从A到B的单射。12. 已知集合A=，1，2，则A的幂集合r (A)=_。13、设是分配格，若对任意的a，c，cA，如果有ab=ac，ab=ac成立，则a_b。14、仅当n_时，Kn为平面图。15. pq 的主合取范式是_ 。 16. 语句“我在说谎”_命题。（填“是”或“不是”）。17. 设A=a,b,c,d，R是定义在A上的关系，R=, ，则r(R)= _。 18一个树林G有
23、三棵树，G的顶点数是20，则G的边数为_ 。 19P(P()=_ 。 20整数加法群中1的阶是_ 。 21设有向图D的邻接矩阵为A(D)=，那么E 。 22. 语句“这句话是错的” 命题。（填“是”或“不是”）。23设命题公式GP(QR)，则使G取真值为1的指派是 ， ，_。24. 已知命题公式为G(PQ)R,则命题公式G的析取范式是 。25. 公式的自由变元是 , 约束变元是 。26. 谓词逻辑公式的前束范式是 。27. 设个体域Da,b,消去公式中的量词，则 。28. 换名规则施于 变元，代入规则施于 变元。29. 设图G和G,若 ，则G是G的真子图，若 ，则G是G的生成子图。30. 在无
24、向图中，结点间的连通关系具有 性， 性， 性，是 关系. 。31. 无环有向图D的关联矩阵M(D)中，第i行值为1的元素个数为结点vi的 ，第j列值为1的元素个数为结点vj的 .。32. 设G是完全二叉树，G有15个结点，其中有8个是树叶，则G有 条边，G的总度数是 ，G的分支点数是 ，G中度数为3的结点数是 . 。33. 连通有向图D含有欧拉回路的充分必要条件是 。34. 设G是有n个结点的简单图，若G中每对结点的度数之和 ，则G一定是哈密顿图. 。35. 设G是有n个结点，m条边的连通图，ZTE终端用户在线升级操作指导 2012 - 04 目录 1、什么是终端软件在线升级 2、在线升级的作
25、用 3、推广对象和机型 4、客户端的安装与卸载 5、在线升级操作指导介绍 6、FAQ 1、什么是终端软件在线升级 终端软件在线升级客户端是以中兴智能手机用户为主，为提升用 户体验专门提供给用户自助升级的一种服务。该客户端支持同版 本升级和低版本向高版本的升级。支持在Windows XP /VISTA /WIN7 32和64位系统下运行。 具体实现原理： PC机与数据线连接中兴手机后，客户端会自动检索服务器并判断 版本升级是否需升级，然后下载升级包并实现自动升级的过程。 2、在线升级的作用 使用终端软件在线升级客户端后： 1）终端用户可以不用将机器返厂维修不用将机器返厂维修，直接从中兴官网 下载
26、客户端软件就能实现自助升级； 2）客户端支持同版本和低版本向高版本的自助更新，用户可以自自 行行Review和修复智能手机软件和修复智能手机软件BUG，实时保持最新版本。 3）只需联网就能实现在线升级，节约节约查找和维修代理维修时间和维修时间和 费用费用。 4）无需再上论坛寻找官方版本和驱动、平台的下载. 3、推广对象和机型 目前国内支持在线升级的中兴机型有： V880、N880 、 V9、V9E、X850、N700、N760、N880S、 V960 、V880+、N606、N600+、N600、N788、N960、V9C、 N780、V9A、V852、V788D、V889D、U812、U960s、V881、 N880E。 U812和U960S的操作方式请详见27页的FAQ。 试点阶段其他机型暂未开放、我们会在后期中增加更多ZTE终端发货机 型的支持。敬请关注！ 怎样下载客户端？ 国内终端用户国内终端用户可通过访问中兴官网中文版 （ 手机服务支持 请选择产品型 号中选择机型 下载获取。 1. 服务支持手机服务支持 2. 选择支持机型 选择机型选择机型. 4、客户端的安装与卸载 一、安装客户端一、安装客户端 （1）双击运行中兴官网下载的客户端软件XXXXSetup.exe，提示 “启动 InstallShield Wizard” （2）选择安装语言（默认安装
