华东交通大学历年离散数学试卷选编(参考答案)

1、历年离散数学试卷选编（参考答案）目录15101619242731试卷 试卷一 试卷三 试卷四 试卷五 式卷八 试卷七 试卷八读书是掌握知识的捷径，勤奋是开启知识大门的钥匙, 思考是理解知识的利器，练习是巩固知识的方法， 讨论是理解知识的妙招，探求是创新知识的途径。试卷一一、单项选择题（本大题共10小题，每小题2分，共20分）1 .下列不是命题的是C 。A. 7能被3整除.B. 5是素数当且仅当太阳从西边升起.C. x力口 7小于0.D.华东交通大学位于南昌北区.2 .设p:王平努力学习，q:王平取得好成绩，命题 除非王平努力学习，否则他不 能取得好成绩”的符号化形式为D 。A. p-qB. -

2、p一 qCq一 pD. q一 p3 .下面4个推理定律中，不正确的为D 。A. A=>(AV B)附加律)B. (AV B)A -A=>B 所取三段论)C. (A一 B八A=>B假言推理) D. (A一 B八B=>A拒取式)4 .设解释 I 如下，个体域 D=1,2,F(1,1)=(2,2)=0,F(1,2)=F(2,1)q 1 在解释 I 下，下 列公式中真值为1的是A 。A.-x yF(x,y)B.xyF(x,y)C. x-yF(x,y)D. - x yF(x,y)5 .下列四个命题中哪一个为真？ D 。A. 0C0B.0 aC.0 C 0D.6 .设 S=a,b,

3、c,d R=<a,a>,<b,b>,<d,d>则 R 的性质是B 。A.自反、对称、传递的B.对称、反对称、传递的C.自反、对称、反对称的D.只有对称性7 .设人=口处,0则下列是集合A的划分的是D 。A.b,c,c B.a,b,a,c C.a,b,c D.a,b,c8 .设集合Q("2) =a *b'2a,b" Q)关于普通数的乘法，不正确的有C 。A.结合律成立B.有幺元C.任意元素有逆元D.交换律成立9 .设A是非空集合，P(A) A的募集，n是集合交运算，则代数系统P(A),n 的幺元是C 。A. P(A) B.小 C.

4、A D. E10 .下列四组数据中，不能成为任何 4阶无向简单图的度数序列的为C 。A. 2,2,2,2B. 1,1,1,3C. 1,1,2,3D. 1,2,2,3二、填空题(本题共10小题，每小题2分，共20分)1 .命题公式p-q的真值为假，当且仅当 _p=1,q=0一2 .公式p一(q 一啦联结词全功能集，八，v中等值形式之一为zpxZqvro3 .谓词公式 FxF(x) xG(x,勺前束范式为 -xmyrF(x户G(y).4 .设集合 A = 1, 4, B = 2, 4,则 P (A) - P (B) = 1,1,4。5 . R是非空集合上的偏序关系，当且仅当 R具有自反性、反对称性

5、、传递性。6 .设函数 f(x)=x + 1,g(x)=或 则 f o g =2X + 1。7 .设(7=(134)(25$) p =(25)(1643)贝Ur(1)(465)。8 .命题设G为任意的n阶简单的哈密尔图，则Vu,vC V(G),均有d(u)+d(v) > n" 的真值为_0_09 .无向连通图G是欧拉图，当且仅当G中每一个顶点的度数都为偶数。10 .设树T有m个顶点，n条边，则T中顶点与边的关系为 m=n+1。三、证明下式(6X2=12分)1、判断下面推理是否正确。如果你学习，那么你离散数学不会不及格。如果你不热衷于玩游戏，那么你将学习。但你离散数学不及格。因此

6、你热衷于玩游戏。设p:你学习，q:你离散数学及格，r:你热衷于玩游戏，则前提：p-*q,I p,q结论：r证明：p-*q前提引入q前提引入p拒取式ip前提引入(r)拒取式r置换2、在一阶谓词逻辑中构造下面推理的证明。前提：xF(x), x(F(x)V G(x) - H(x)结论：xH(x)证明：WF(x)前提引入F(a)三 Vx(F(x)V G(x) -H(x)前提引入F(a)V G(a) 一Ha)V-F(a)V G(a)附加H(a)假言推理WH(x)三十四、用等值演算法求公式(pV q)A (p-q)?(q p)的主合取范式与主析取范式。(10 分)解：原式 u(pV q)A (pV q)?

7、(qp)u(pAp) Vq)?(qp)u q?(q p)u (q(q-p)八(q-p) 一)U (qVLqVp) A(qVp) V q)u(qVp)A(qAp) V q)(一q V p)A q二 pA q(3) 主合取范式(0,1,2)主析取范式五、设Ri和2是集合X= 0,1 , 2,3,41的关系，Ri=<x , y>| y = 2x &=<x , y>| x= y + 1写出Ri、R2 ,写出R2的关系矩阵，并求出Ri欠2。(8分)解：Ri=<0,0>,<1,2>,<2,4>, R,=<1,0>,<1,

8、2>,<2,3>,<3,4>,R2的关系矩阵：(略)R1 R=<x , y>| y = 2(x-1) 六、设集合A=2,3,4,6,8,12,24, R为A上的整除关系，(1)画出偏序集<A, R>哈斯图；(2)出集合A中的最大元、最小元、极大元、极小元；(3)写出A的子集B=2,3,6,12»勺上界、下界、最小上界、最大下界。(8分)解：(1)哈斯图：A中的最大元：24,最小元：无，极大元：24,极小元：2、3B=2,3,6,12勺上界：12、24,下界：无,最小上界：12,最大下界：无七、设Z为整数集合，在Z上定义二元运算*,

9、 Vx,yCZ有x* y = x + y - 2。证明：<z, *>是一个群。(1。分)证明：显然，二元运算*满足交换律。(1)封闭性：vx,yez,显然 x* y = x + y2ez。(2)结合律：-x,y,zC乙(x*y)*z=(x+y-2)*z=x+y-2+z-2=x+y+z-4x*(y*z)=x*(y+z-2)=x+y+z-2-2=x+y+z-4(x*y)*z=x*(y*z)故二元运算*满足结合律。(3)设 eCZ, Vx Z,使得 x*e=x,即 x+e-2=x, e=2 故幺元 e=2.(4) Vx 乙设 yCZ,使得 x*y=e,即 x+y-2=2, y=4-x,故

10、 x-1=4-x。综上所述，<Z, *>是一个群。八、平面图G有两个连通分支，其顶点数为12,边数为34,问G有多少个面?(6分)解：设有x个面，根据欧拉公式：12-34+x=2+1,即 x=25所以，G有25个面。九、对下图，(1)求其邻接矩阵；(2)(2)长度小于3的通路和回路的总数。(6分)V2v3v5解题思路：先写出邻接矩阵 A,然后求A2,则矩阵A+A2中元素之和，即为长度 小于3的通路条数【10条】；而A+A2对角线上元素之和，即为长度小于 3的回路条数【0条】。大学是一个人的“精神账户"，你一辈子都要不断回来"提款"的。> X、八-

11、试卷一一、单项选择题(2分X 10=20分)1、下列语句是命题的有B 。A. x2+2y>1 ;B. 2010年的国庆节是晴天;C.青年学生多么朝气蓬勃呀！ D.学生不准吸烟！2中在命题逻辑中，任何命题公式的主合取范式都A.不一定存在；B.不存在；C.存在且唯一 ；D.存在但不唯一.3、设 S=1,2,3,4 R=<1,1>,<3,3>,<4,4>则 R满足的性质是C A.自反、对称、传递的； B.自反、对称、反对称的；C.对称、反对称、传递的； D.只有对称性.4 .与命题p A(pVq)等值的公式是A 。A. p；B. q；C. pV q；D. p

12、A q.5 .设 M=a,b,c, M 上的等价关系 R=<a,a>,<b,b>,<c,c>,<b,c>,<c,b>t的集合M的划分是D 。A.a,b,cB.a,c,b,c C.a,c,b D.a,b,c H(x,y): x 喜欢 y。6 .设D:全总个体域，F (x): x是花，M(x) : x是人, 则命题“每个人都喜欢某种花”的逻辑符号化为CA. Vx(M(x)八三y(F(y)T H(x,y);B. -x(M(x)T 三y(F(y)T H (x, y);C. Vx(M(x)t 3y(F(y)AH(x,y);D. x(M(x) y

13、(F(y) H(x,y).8.下列四组数据中，能作为某个 4阶无向简单图的度序列的为D 。A. 1,2,3,4; B. 2,2,2,3 C. 1,1,2,3D. 1,1,1,3.9. 一棵无向树T有8个顶点，4度、3度、2度的分枝点各1个，其余顶点 均为树叶，则T中有C 片树叶。A. 3;B. 4;C. 5;D. 6.10.下面偏序集B 能构成格ABCD二、填空题(2分X 10=20分)1 .当p=0,q=0时，命题公式p一 (pA q)的真值为1。2 .设p:我努力学习，q:我取得好成绩，命题“除非我努力学习，否则我不能 取得好成绩。”的符号化形式为 qz±p o3 .设解释 I

14、如下，个体域 D=1,2,F(1,1)=(2,2)=0,F(1,2)=F(2,1)=1ft解释 I 下, 5xF(x,2)的真侑为1。4 .谓词公式 3xF(x)A次G(x)的前束范式为三xmy( F(x)A G(y)。5 .设树T有n个顶点，m条边，则T中n与m的关系为m=n-1。6 .等价关系满足自反性、对称性和传涕性 三个性质。7 .设函数 f(x)=2x, g(x)= x2+1,贝U f o g = 2x2+_2_ 08 .无向连通图G是欧拉图，当且仅当G中每一个顶点的度数都为 偶数。9 .设|A|=3 ,则A上有29个二元关系。10 .设A为非空有限集，则代数系统P(A),U中的幺元

15、为名 o三、综合题(第1、2、4题10分，第3、5、7每题8分，第6题6分，共60 分)前提：p-(qvr),A F 结论：q.证明：p -sp-s一A 一r一r p-(qvr)q rq1 .构造下面推理的证明：(10分) p -s；前提引入化简化简前提引入假言推理前提引入假言推理析取三段论2 .用等值演算求下面公式 A的主析取范式和主合取范式，并列出A的成真赋值：(10 分)A=(p-q) (qr)解：A=(p-q) A(qr)=(P q) Tq r)三 (P q) (r r) (p _p) (_q r)三(p q r) (-p q -r) (p -q r) (p -q r)t M4 M5

16、M 2 M6二:(2,4,5,6)比合取范式=% (0,1,3,7)主析取范式A 的成真赋值：000, 001, 011,1113 .设集合A=a, b, c, d上的二元关系R=<a , b > ,< b , a > ,< b, c > , < c , d >求：(1)指出关系R满足的性质；(2)求出R的自反闭包、对称闭包。(8分)解：(1) R满足：反自反性(3) R 的自反闭包：r(R)=<a,a>,<b,b>,<c,c>,<d,d>,<a , b > ,< b , a &g

17、t; ,< b, c > , < c , d >R 的对称闭包：s(R)= <a , b > ,< b , a > ,< b, c > , <c,b>,< c , d >,<d,c>4 .设5=1 , 2,3,4, 6,8,12为 S 上的整除关系。(10 分)问：(1)偏序集S ,仝的Hass图如何？(2)偏序集S，令的极小元、最小元、极大元、最大元是什么 ？(3)在偏序集S，令中，B=4,6的上确界、下确界是什么？解：(1)哈斯图：(2) S , '的极小元：1,最小元：1,极大元：8、

18、12,最大元：无(3) B=4,6的上确界：12,下确界：25 .已知某有向图G的邻接矩阵如下：（8分）v1 '1 2 1 0、A 芋 0010 v3 0 1 0 1 v4 k0010 j问：（1）画出图Go（2）试用邻接矩阵求G中长度小于等于2的通路的条数，其中回路有 几条？（3）该图是为强连通图还是弱连通图？解：（1）（略）（2）长度小于等于2的通路的条数：22,其中回路数：5.（3）弱连通图。6 .设集合G=3nnwZ（其中：丸是普通乘法，Z是整数集），对代数系统G,说明：（1）是否满足封闭性、结合律？ （ 2）是否存在幺元？ （ 3）是否构成群？（6 分）解：（1）满足封闭性。

19、Vm,nZ, 3mM 3n=3m+nC 乙满足结合律：/m,n,kC Z, （3吗 3n） x 3k=3mx （3nM 3k ）=3m+n+k。（2）幺元为30=1。（3）由于 V nZ, （3n） -1=3-n,综合（1） （2）知，G，M构成群。7.图G是一个简单的连通平面图，其无限面的度数为5,其余面都为三角形，结点为8 ,请通过计算求平面图 G的边数和面数。（8分）解：设平面图G的边数和面数分别为：e、f,则8-e+f=2,5+3（f-1）=2e, 解上述方程得：e=16,f=10 。所以，平面图G的边数为16,面数为10。世上无难事，只要肯登攀。毛泽东试卷三单项选择题（每题2分，共2

20、0分）1,下列语句是命题的有B 。A.请保持安静！C. x<6;2 .下面哪个命题公式是重言式 A （P-> q）n（qT r）；C. （p vq） L（p Aq）；B. 2019年元旦是星期六;D.今天是星期五吗？B 。B P-* (q-* p);D. _|( p v q) a p oA. <a,b>C. <a,b>, <b,c>4.若A=a,b,c则下列集合中,A. ：',a,b,cC. a,b,cB. <a,b>, <b,a>D. <a,a>, <a,b>, <b,a> C

21、 是人的划分。B. a,b,b,cD. a,b3 .下列二元关系中，具有传递性的二元关系是 A 5. N是自然数集，定义f :NtN, f （x） = xmod3 （即x除以3的余数），则函数£是D A.满射非单射；B,单射非满射；C,双射；D,非单射非满射6 .下面集合C 关于减法运算不是封闭的。A. Z;B, 2x x ZC, 2x+1 x Z D. 07 .设R是实数集合，“父”为普通乘法，则<R, X> B 0A.是群；B.是独异点，不是群；C,是半群，不是独异点；D,是代数系统，不是半群8.下图中既不是Eular图，也不是汉密尔顿图的是B BC)(D9 .如左下

22、图，相对于5阶无向完全图K的补图为。本题图错误凶BK皿10.给定无向图G=<V，E>,下面哪个顶点子集是图 G的点割集A A. I）；B.L）； C. I' D. J5、填空题(每题2分，共20分)1 .设F(x): x是人；G(x): x会犯错误，则在谓词逻辑中，命题“没有不犯 错误的人”谓词符号化为mx(M(x)aG(x)更Vx(M(x)t G(x)。2 .设解释I如下，个体域D=1, 2, P(x) : x=1, Q(x): x=2,在解释I下, 公式三xP(x)t VxQ(x)的真值为003 .谓词公式 *P(x)t VxQ(x, y)的前束范式为 _ VxVz(P

23、(x)t Q(z,y)。4 .若人=中=现代,则BP(A) =粤。5 .若 A=a,b,c,d A上的等价关系 R=<a,b>, <b,a>, <c,d>, <d,c>U Ia,则 A在等价关系R下的商集A/R = _a,b,c.d_6 .若Z为整数集合，“x”为普通乘法，代数系统 <乙”中，则Z关于“父” 运算的幕等元有 _QL 。7 .设A=a, b, c , A上二元运算*如下：o则代数系统A, *中,8 .设 G=0,1,2,3,出4为模 4 加法，即 Vx,y三G, x©4y = (x+y) mod 4,贝U<G

24、,4 为循环群，该循环群的生成元为1, 3 Q9 . n个结点的无向完全图Kn为欧拉图的条件是n为奇数10 .若无向树T有1个3度结点，3个2度结点，其余结点都是树叶，则该 树有 3 片树叶。三、综合题（共60分）1 .在自然推理系统中，构造下面推理的证明。（6分）如果王菲是理科生，那么她一定学过高等数学；如果她不是文科生, 她一定是理科生；她没学过高等数学，所以她是文科生。设p：王菲是理科生，q：王菲学过高等数学，r：王菲是文科生前提：p-q,r-p,q结论：r证明：p-q飞-pF-pCr)r前提引入 前提引入 拒取式 前提引入 拒取式 置换2 .在命题逻辑中，构造下面推理的证明：（8分）前

25、提：p ，q r）, q （p -s）, t 一r结论：q- 't证明：q q (p s)前提引入附加前提p - sp p - (-q r)-q rr t - -r-t假言推理化简前提引入假言推理析取三段论前提引入拒取式3 .求公式 飞pT q) v(q-»)八)的主析取范式、主合取范式，及该公式的成 假赋值。(8分)解：原式二一(p q) (q r) r)=(p q) r=(p r) (一q r)= (p r) (q -q) (p -p) Cq r):二(p q r) (p q r) (p _q r) (_p -q r) 二 M0?M2?M2?M6(0,2,6)比合取范式=

26、% (1,3,4,5,7)-主析取范式成假赋值：000,010,1104 .设集合A=a, b, c , R是A上的二元关系，已知R的关系矩阵为 (8分)1 0 0M = 0 1 10 1k(1)并画出R的关系图；(2)求出R2的集合表达式；(3)说明R具有哪些性质。解：(1)(略)(2)=<1,1>,<2,2>,<3,3>,<2,3>,<3,2吊(3)自反性，对称性，传递性5.设5=1, 2, 3, 6, 12, 18, 36,设 为 S 上的整除关系。(8 分) 问：(1)画出偏序集S, 0的哈斯图。(2)在偏序集$, W中，B=2,

27、3, 6的极大元、极小元分别是什么? (3)在偏序集$, W中，C=6, 12, 18的最小上界、最大下界分别是什么？解：(1)哈斯图：(2) B=2, 3, 6的极大元:6,极小元：2、3。C=6, 12, 18的最小上界：36,最大下界：66.设G, *是群。若在G上定义运算,使得对于Vx, y=G,有：x产y*x 证明：G, 是群。(8分)证明：(1)满足封闭性。Vx,yWG,由于G,*是群，满足封闭性，有：x*y=y*xEG。(2)满足结合律。由于G, *是群，满足结合律，则Vx, y, zG,(x。) z= (y * x) =z* (y * x) =z*y * x,x . (y *z

28、) =x , (z * y) =(z*y )* x) =z*y * x.(3) 设e是G, *的幺元，贝U VxG,x*e=e*x=x, e *x=x*e =x即e也是G, 的幺元(4) vxeG,设x在G, *中的逆元是y,则x.y=y*x=e, y*x=x*y=e即y也是G, 中x的逆元。综上所述，G, 是群。7 .已知有向图G的邻接矩阵如下：(8分)0 1 0 1vl0 0 1 1 v2A =0 1 0 0 v3_1 0 0 11v4问：（1）画出图Go(2)试通过邻接矩阵A求图G中长度等于2的通路总数 (3)试求图G的可达性矩阵。(4)该图是否为强连通图?解：(1)(略)(2) 13

29、条(略)(4)是强连通图8 .设图G为n个顶点m条边的连通平面图，且每个面的次数至少为4,证明：m0 2n-4。(6 分)证明：设棉数为f,根据欧拉公式和平面图的握手定理：n-m+f=2,4f 2m,解之得：m0 2n-4。人生像一截木头，或者选择慢慢腐朽，或者选择熊熊燃烧。试卷四、单项选择题（每小题2分，共20分）:1.卜列选项中与AU B=A等价的是（_D_）_。A. AH B=AB, A B =C.AU B=B D BA2.卜列语句是命题的有（3.4.5.A.明年元旦会是晴天吗?C. xy >0当且仅当x和y都大于0;设S = 1，2,3 , S上关系R的关系图为D.我正在说谎。则

30、R具有（D ）性质。A.自反性、对称性、传递性;C.反自反性、反对称性、传递性;如图，给出格L则e的补元是B 0A.B.C.D.a；f；b；公式A = （P（X）T Q（x）的解释则A的真值为（A )0A. 1; B. 0;C.可满足式;6.在下述公式中（B.反自反性、反对称性;D.自反性bda为：个体域 D=2, P(x): x>3, Q(x): x=4D.无法判定。）为矛盾式A (P Q) >(P Q).B (P- Q卜(P > Q) (Q > P).口?C -(P，Q) Q .D. " ("Q)。7. 无向图的关联矩阵中，每列的元素之和为B 。

31、A.边数的2倍 B. 2C.该图的顶点总数 D.对应顶点的度数8. 5阶无向完全图(Ks)不是以下哪种图？ C。A.欧拉图 B,简单图 C.二部图 D.哈密顿图9. 下面哪一种图不是树？CA.无回路的连通图B.有n个结点，n 1条边的连通图；C.每对结点间都有初级通路的图；D.连通但删去一条边则不连通的图。10. 5阶无向完全图Ks的边数为(B )。A. 5 B .10 C .15 D .20填空题(每小题2分，共20分)1 .设P：我生病，Q：我去上课， 命题“虽然我生病，但我还是去上课了”符 号化为fq。2 . R为实数集合，若f和g都是R一R的函数，且f(x)=x+1, g(x)=2x,

32、则fog (2)=5 o3 .设集合 A= a, b, B=a, c则 A© (B A) =a, b,c (© 为对称差)4 .若关系 R=<1,2>, <2,1>则其传递闭包 t(R)为 /<1,2>, <2,1>,<1,1><2,2>_5 .设 A = a, b, c, d A上的等价关系 R= <a, c>, <c, a> Ia,则商集A/R= _/a.c.b.d_6 .公式三x F(x, y)"厚yG(y)的前束范式是 ：x三y (F(x, zbG(y)。7 .

33、设M(x): x是人，F(x): x吃饭。在一阶逻辑中，“没有不吃饭的人”符号化形式为 与 x(M(x) -F(x)。8,完全二部图K2,3是平面图，它的平面嵌入共有 3_个面。9 . 一个无向图有4个结点，4条边，其中的3个顶点度数分别为1, 2, 3,则 第4个结点度数一定是_2_010 .设S =1,2, 3 , S上定义的二元运算*如表所示，S中关于好运算的零元 是 1 0*1231112123313212 .证明等值式：Q一(PA (Q-P) u P VQ,并求该命题公式的成真赋值。证明：(略)3 . 一棵树T中，有3个2度结点,一个3度结点,其余结点都是树叶(1) T中有几个结点；

34、(2)画出具有上述度数的所有非同构的无向图。解：(1)设有x个结点，则3 2+3+(x-4)=2(x-1),解之得： x=7.(2)(略)4 .在命题逻辑中符号化以下文字，并证明其推理是正确的：“如果厂方拒绝给工人增加工资并且工厂不更换厂长，那么罢工就不会停止因此，如果罢工停止，则要么厂方给工人增加了工资，要么更换了厂长5 .设集合A= 1, 2, 3, 5, 6,7,15,35 R为整除关系(1)画出偏序集A, R勺哈斯图；(2)写出A的最大元，最小元；(3)写出A的子集B = 1,3,5勺上界，下界。解：(1)哈斯图：(2)最大元：无，最小元：1(3) B = 1,3,5勺上界：15,下界

35、：110 0 06.设有向图G的邻接矩阵为:10 1110 0 11 0 0 0(1)画出该图;(2)求该图中长度为2的通路总数。(3)该图是为强连通图还是单向连通图？(4)判断该图是否为欧拉图？说明理由。解：(1)(略)(2) 8 ;(3)单向连通图；(4)不是。7.设集合 S = R- _ 1(R为实数集)，a*b=a + b + abo(1)证明<S, *址群；(2)在S中解方程：x*4=5。(略)逆境能打败弱者而造就强者。-尼克松试卷五单项选择题(每题2分，共20分)1,下列语句是命题的有B 。A.请保持安静！C. x2+y< 0;2.下面哪个命题公式是矛盾式DA. (p-

36、> q)八(qT r)；1 . pvq)L(pLq);3 .下列二元关系中，不具有传递性的二元关系是A. <a,b>C. <a,b>, <b,c>4 .若A=a,b,c1则下列集合中，A. ：',a,b,cC. a,b,c5. N是自然数集，定义f :NtA.满射非单射；B. 2011年元旦是星期六；D.今天是星期五吗？。B. p-* (q-* p)；D. _,(p v q) a p 0C oB. <a,a>, <a,b>, <b,a>, <b,b>D. <a,b>, <a,a&

37、gt;A 不是A的划分。B. a,b,cD. a,b,cN, f(x) = x ,则函数 £是C 0B,单射非满射；C.双射;D.非单射非满射6.下面集合C 关于加法运算不是封闭的。A. Z(整数集合)；B. 2x|xeZC. 2x+1|xeZD. 07.设R是实数集合，“+”为普通乘法，则<R, +> B 。A.是群；B.是独异点，不是群；C,是半群，不是独异点；D,是代数系统，不是半群8,下列四组数据中，不能成为任何图的度数序列的为C 。A. 1,1,1,3B. 2,2,3,3C. 1,2,2,2D. 1,2,3,49 .无向图的关联矩阵中，每列的元素之和为B 。A.

38、边数的2倍 B. 2 C.顶点数 D,顶点的度数10 .在如下各图中，B 是欧拉图。二、填空题(每题2分，共20分)1 .设F(x): x是人；G(x): x会犯错误，则在谓词逻辑中，命题”所有的人都会犯错误”谓词符号化为。2 .设解释I如下，个体域D=1, 2, P(x) : x=1, Q(x): x=2,在解释I下， 公式VxP(x)T三xQ(x)的真值为。3 .谓词公式三xP(x, y)八VxQ(x)的前束范式为 三xz(P(x, y)八Q(z)一。4 .若 A=S,B=现代,则 BA =。5 .若A=a,b,c A上的等价关系R=<a,b>, <b,a>U Ia

39、,则A在等价关系R 下的商集 A/R= a,b,cA 6 .若Z为整数集合，+为普通加法，代数系统 <乙+>中，则Z关于+的幕 等元有一0 。7 .设A=a, b, c , A上二元运算*如下:*a b cabcabcbbbcba则代数系统A, *的零元为b 。8 .设 G=0,1,2,3, 中4为模 4 加法，即Vx,ywG, x©4y = （x+y） mod 4,贝UG , ©4为循环群。该循环群中，元素2的阶为 2 o9 . n个结点的无向完全图 Kn的边数为。10 .若无向树T有1个3度结点，2个2度结点，其余结点均为树叶，则该 树有 3 片树叶。三、综

40、合题（共60分）1 .在自然推理系统中，构造下面推理的证明。（6分）如果今天天晴，那么我将去爬山；今天天晴，所以我将去爬山。设p：今天天晴，q：我将去爬山，则前提：p-q, p结论：q证明：p-*q前提引入p前提引入q假言推理2 .在命题逻辑中，构造下面推理的证明：（8分）前提：p （-q r）, q- p, r - s结论：q- s证明：q附加前提引入qT p前提引入p假言推理pT （飞”前提引入-q rrr , ss假言推理析取三段论前提引入假言推理3 .求公式(pT q)Mr的主析取范式、主合取范式，及该公式的成假赋值。(8分)解：原式u -(-p q) r=(p q) r=(p r)

41、(q r)二 (p r) (q -q) (p -p) (-q r):二(p q r) (p q r) (p -q r) (_p _q r)= M0?M2?M2?M6:二:(0,2,6)-主合取范式:=' (1,3,4,5,7)注析取范式成假赋值：000,010,110(8分)4 .设集合A=a, b, c , R是A上的二元关系，已知R的关系矩阵为1 0 0M = 0 0 1：。1 1 _(1)并画出R的关系图；(2)求出R2的集合表达式；(3)说明R具有哪些性质。解：(1)(略)(2)R2=<1,1>,<2,2>,<3,3>,<2,3>

42、,<3,2>(3)满足：对称性 5.设5=1, 2, 3, 4, 6, 9,设为S上的整除关系。(8分)问：(1)画出偏序集<S, 0>的哈斯图(2)在偏序集$, &中,B=2, 3, 6的最大元、最小元分别是什么？(3)在偏序集$, W中，C=1, 2, 3的上界、下界分别是什么？解：(1)哈斯图：11(2) B=2, 3, 6的最大元：(3) C=1, 2, 3的上界：6、6 .设G, 十址群。G为整数集合， 分)(略)7 .已知后向图G的邻接矩阵如下一0 1 11vlA= 1 1 0v2-0 1 0_v3问：(1)画出图Go(2)试通过邻接矩阵A求(3)试

43、求图G的可达性矩F(4)该图是否为强连通图？解：(1)(略)一1 2 0 ，一、2(2) A = 1 2 11 1 0 _696,最小元：无；9,下界：1。+为普通加法运算，证明：G, +是群。(8:(8 分)图G中长度等于2的通路总数。车。长度为2的通路数：91 1 1(3) P = 1 1 111 1 一(4)强连通图8.图G是一顶点数为6的简单的连通的平面图，有 2个面的次数为4,其余面的次数都为3,求平面图G的边数和面数。(6分)解：设G的边数为e,面数为f,则根据欧拉公式和握手定理，有：6-e+f=2, 4 2+3 (f-2) =2e解上述方程式得：e=10, f=6,即图G的边数为

44、10,面数为6。能够快乐地学习和工作，这是精神上优秀的征兆。试卷六一、选择题(每题2分，共20分)1 .下列句子为简单命题的是D 。A.禁止吸烟！B.王红既聪明又美丽。C.我正在说谎。D.小王和小李是好朋友。2 .设D:全总个体域，F(x): x是优点，M(x) : x是人，H(x,y): x有y ,则命 题“每个人都有一些优点。”的逻辑符号化为C oA. -x(M(x) y(F(y) > H(x, y)B. -x(M(x) > y(F(y) > H (x, y)C. -x(M (x) ， y(F(y) H(x, y)D. x(M(x) > -y(F(y) H (x,

45、y)3 .下面命题公式是矛盾式的为C 。A. (p")vpb.pqC. 一（p，q） q（p q） （p 一 q）4.已知某班有35人，其中10人学习日语，20人学习英语，5人既学日语又学 英语，那么既不学日语也不学英语的人数是 B 。A. 5 B .10 C . 15 D . 20 5. Z是整数集合，定义f :Zt Z, f (x) = -x,则函数f是CA.满射非单射B.单射非满射C.双射D.非单射非满射6 .设Q是有理数集合, A.封闭性C.存在幺元* ”为普通乘法，则代数系统<Q, *>不满足的是B.可结合性D. Q中每个元素都存在逆元7 . <Z6,出&

46、gt;为循环群，其中Z6=0,1,2,3,4,5, ©为模6加法，该群中元素2的阶为C。A. 1B. 2C. 3D.8 .下列四组数据中，不能成为无向简单图的度数序列的是AA. 2,3,3,4B. 3,3,3,3C. 0,1,2,1D. 1,2,2,19 . 4阶无向完全图(K4)是以下哪种图？ B 。A.欧拉图 B .平面图 C .多重图 D .10 .图G如右图所示，则G的补图为C 。二、填空题(每题2分，共20分)1 .公式三xP(x) -Q(x,y)的前束范式为mx(P(x) -Q(z,y)。2 .设解释I如下，个体域D=a, b, P(x) : x=a, Q(x): x=b

47、。在解释I下，公式Vx(P(x) vQ(x)的直俏为 1。3 .设集合 A= a,b,c, B=b,c则 A B = a。4 .设集合 A=a,b,c,d,e A上的等价关系 R= <a, b>,<b, a>,<d, e>,<e, d> U Ia, 则商集 A/R= a,b,c,d,e。5 .给定人=1,2,3,4±的二元关系 R=<1,2>,<2,1>,<2,3>,<4,4弓R的对称闭包 s(R= <1,2>,<2,1>,<2,3>,<3,2>,

48、<4,4>。6 .若半群<G,。>含有 幺元 ，则称半群<6, 口 >为独异点。7 .若Z为整数集合,*为普通乘法，代数系统<Z,*>中，Z关于*的零元为 0。8 .无向连通图G是欧拉图当且仅当所有点的度数均为偶数。9 .设一个无向连通图G有10个顶点15条边，则图G的任意一棵生成树的总边 数为9条。10 .连通的简单平面图G有6个顶点，有5个面，则图G有 9 条边。三、综合题(每题10分，共60分)1 .求命题公式(r -* p)八q的主析取范式、主合取范式及该公式的成真赋值。解：原式：=(r p) q=(q r) (p q)u(qr) (p

49、p) (pq)(r r)u(Pq r) p q r)(pqr) (pq -r)= m7?m3?m6(3,6,7 ) 主析取范式二口(0,1,2,4,5 ) 主合取范式成真赋值：011,110,1112 .在自然推理系统中，构造下面推理的证明。前提：如果今天天气好，那么我去逛街或者去图书馆看书；如果图书馆关门， 那么我就没去图书馆看书；今天天气好并且图书馆关门。结论：所以我去逛街了。设p：今天天气好。q：我去逛街。r：我去图书馆看书。s：图书馆关 门。正确符号化前提和结论并证明推理的有效性。前提：p > (q ?r),s一 r,p ?s结论：q证明：p?s前提引入p化简s化简尸(q ?r)

50、前提引入q?r假言推理STrr前提引入r假言推理q析取三段论3 .设 A=1,2,3,4,有一个 A上的划分 S= 1, 2, 3, 4, 求：(1)写出由划分S确定的等价关系R的集合表达式。(2)证明关系R是等价关系。(3)写出R2的关系矩阵。解：(1) R=<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>(2)说明满足等价关系的条件：自反性、对称性、传递性(略)4、设集合 A=1 , 2,3问：(1)写出集合A的募集P(A)。(2)画出偏序集P(A)三的哈斯图。其中，工为P(A)上的包含关系。(3

51、)在偏序集P(A)£中，B= 1 , 2, 1,2 的最大元和下确界是什么？解：(1) P(A)丑？，1,2,3,1,2,1,3,2,3,1,2,3(略)(3)最大元：1,2,下确界：？。5 .设集合G =3n |nw Z(其中：乂是普通乘法，Z是整数集)，问集合G 和乘法运算煞能否构成交换群？并进行验证。(略)6 .已知有向图G的邻接矩阵如下：0 10 0vl0 10 1v2 A =2 0 0 1 v3-0 0 0 1 _v4问：(1)画出图Go(2)通过邻接矩阵A求图G中长度为2的通路总数。(3)该图是否为强连通图？说明理由。解：(1)(略)(2) 9 条(3)不是强连通图人心就

52、像容器，装的学习多了，空虚就少了试卷七一、选择题(每题2分，共20分)1 .下列句子是命题的是D 。A.禁止吸烟！B.你带了衣服吗?C. 2x+38。D.小红是大学生。2,对于公式Vx(F(x, y)T 3yH (x, y) aG(x, z),下列说法正确的是C .x是约束变元.Vx的辖域是F(x, y)B 。.矛盾式A. y是自由变元BC. z是自由变元D3 .命题公式(pT 4)八4的类型是A.重言式BC.非永真的可满足式D .等价式4 . A= a, b, c上的二元关系如下所示，具有传递性的是A 。A. <a,a>B. <b,c>,<a,b>C. &

53、lt;a,b>,<b,a> D . <b,a>, <a,c>, <c,b>5 .集合 1, 0, 1上的A 运算为二元运算(满足封闭性)。A.乘法B.除法C.加法D.减法6 . P(S足非空有限集合S的募集，则代数系统<P(S> U>中的零元是B 。A. P(S) B . S C . D . 7 .代数系统<G, +>中，+是普通加法，以下选项B 不是群。A. G为有理数集合B . G为自然数集合C. G为整数集合D . G为实数集合8 .无环有向图的关联矩阵中，每行中 1的个数是C oA.边数的2倍B.相关顶点的度C.相关顶点的出度D .相关顶点的入度9 . 6阶无向完全图的边数为A 。A. 15 B .30 C .0 D .1010.有向图的度数序列为(6,5,4,4,3),入度序列为(2,3,1,4,2),则以下选项C 是正确的出度序列。A. (2,3,1,4,2)B. (6,5,4,4,3)C. (4,1,3,1,1)D. (3,3,3,0,2)二、填空题