西工大明德学院离散数学试卷A.doc

诚信保证本人知晓我院考场规则和违纪处分条例的有关规定，保证遵守考场规则，诚实做人。 本人签字： 编号： 西北工业大学明德学院考试试题（卷） 学年第 学期开课单位 课程 学时 考试日期 命题教师 审题教师 考试时间 小时 考试形式（）（）卷 题号一二三四五六七总分得分考生班级序号学号姓名一、选择题 1下列是两个命题变元p，q的小项是（）AppqBpq CpqDppq2设P：我将去镇上，Q：我有时间。命题“我将去镇上，仅当我有时间时”符号化为（）A.PQB.QPC.P QD.QP3谓词公式(x)(y)(A(x,y)B(y,z)($x)A(x,y)中量词(x)的辖域是（ ） A(y)(A(x,y)B(y,z) B(y)(A(x,y) CA(x,y)B(y,z)D(y)(A(x,y)4设A=a,b,c,d，A上的等价关系R=,IA，则对应于R的A的划分是（）Aa,b,c,dBa,b,c,d Ca,b,c,dDa,b,c,d5以下关系属于偏序关系的是（ ）。（A）实数集上两实数间的“等于”关系 （B） 同余关系（C）整数集上两实数间的“大于”关系 （D） 良序关系 6. 在自然数集N上，下列定义的运算中不可结合的只有（）Aa*b=min(a,b)Ba*b=a+bCa*b=GCD(a,b)(a,b的最大公约数)Da*b=a(modb)7设R为实数集，R+=x| xR x0，*是数的乘法运算，是一个群，则下列集合关于数的乘法运算构成该群的子群的是（）AR+中的有理数BR+中的无理数CR+中的自然数D1，2，38. 下列哪一组命题公式是等值的？（）A. PQ,PQB.A(BA),A(AB)C.Q(PQ),Q (PQ)D.A (AB),B9. 下面哪一个命题是假命题？（）A.如果2是偶数，那么一个公式的析取范式惟一B.如果2是偶数，那么一个公式的析取范式不惟一C.如果2是奇数，那么一个公式的析取范式惟一D.如果2是奇数，那么一个公式的析取范式不惟一10. 下列运算中，哪种运算关于整数集不能构成半群？（）A.ab=maxa,bB.ab=bC.ab=2abD.ab=|a-b|11. 设A=a,b,c上的关系如下，有传递性的有（）A.1=,B.2=,C.3=,D.4=12. 设D=为有向图，则有（）A.EVVB.EVVC.VVED.VV=E13. 设G为有n个结点的简单图，则有（）A.(G)nD.(G)n14. 设|V|1，D=是强连通图，当且仅当（）A. D中至少有一条通路B. D中至少有一条回路C. D中有通过每个结点至少一次的通路D. D中有通过每个结点至少一次的回路二、填空题(每空3分，共30分) 1. 设F(x): x是人，G(x): x用右手写字，命题“有的人并不用右手写字”在一阶逻辑中符号化的形式为_。 2. 设A=1,2,3，f，g，h是A到A的函数，其中f(1)=f(2)=f(3)=1；g(1)=1，g(2)=3，g(3)=2；h(1)=3，h(2)=h(3)=1，则 是单射； 是满射； 是双射。 3. 设图D=；V=v1,v2,v3,v4，若D的邻接矩阵，则deg-(v1)= ,deg+(v4)= ，从v2到v4长度为2的通路有 条。 4. 设A=1,2,3上的关系R=,，则关系R具备 性，不具备 性。 5. 设A=1,2,3,4上关系R=,，则r(R)= ，s(R)= 。6. 令R(x)：x是实数，Q(x)：x是有理数。(1) 命题“并非每个实数都是有理数”。其符号化为 。(2) 命题“虽然有些实数是有理数，但并非一切实数都是有理数”。则其符号化可表示为 。7. .Q(P(PQ) 可化简为 。8. 后面是图的题 33.A=2,3,4,5,6,8,10,12,24，R是A上的整除关系。那么A的极大元是 ，极小元是 。 假如上午不下雨，我去看电影，否则就在家里读书或看报符号化形式为_。P: 上午下雨。 Q:我去看电影。 R:我在家里读书。 S:我在家里看报。(PQ)(P(RS)由n个命题变元组成不等值的命题公式的个数为（）A.2nB.2nC.n2D.1. 设P：我将去镇上，Q：我有时间。命题“我将去镇上，仅当我有时间时”符号化为（）A.PQB.QPC.P QD.QP2. 设P：我们划船，Q：我们跑步。命题“我们不能即划船又跑步”符号化为（）A. pQB. PQC. (PQ)D.PQ3. 设P：张三可以作这件事，Q：李四可以作这件事。命题“张三或李四可以做这件事”符号化为（）A.PQB.PQC.PQD. (PQ)4. 下列语句中哪个是真命题？（）A.我正在说谎。B.严禁吸烟。C.如果1+2=3，那么雪是黑的。D.如果1+2=5，那么雪是黑的。 2. 谓词公式x(P(x)$yR(y)Q(x)中量词x的作用域是（）A. x(P(x)$yR(y)B.P(x)C. (P(x)$yR(y)D.P(x)，Q(x)3. 谓词公式x(P(x)$yR(y)Q(x)中变元x是（）A.自由变量B.约束变量C.既不是自由变量也不是约束变量D.既是自由变量也是约束变量4. 设C(x)：x是运动员，G(x)：x是强壮的。命题“没有一个运动员不是强壮的”可符号化为（）A.x(C(x)G(x)B.x(C(x)G(x)C.$x(C(x)G(x)D.$x(C(x)G(x)5. 设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)6. 令F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快。则语句“某些汽车比所有的火车慢”可表示为（）A.$y(G(y)x(F(x)H(x,y)B.$y(G(y)x(F(x)H(x,y)C.x$y(G(y)(F(x)H(x,y)D.$y(G(y)x(F(x)H(x,y)2. f:ZZ，对任意的iZ，有f(i)=i(mod 8)，则f是（）A.不是双射B.单射C.满射D.双射2. 设集合A=1,2,3,10，下面定义的哪种运算关于集合A是不封闭的？（）A. x*y=maxx,yB. x*y=minx,yC. x*y=GCD(x,y)，即x，y的最大公约数D. x*y=LCM(x,y)，即x，y的最小公倍数7. Q是有理数，(Q,*)（其中*为普通乘法）不能构成（）A.群B.独异点C.半群D.交换半群8. R为实数集，运算*定义为：a,bR，a*b=a|b|，则代数系统(R,*)是（）A.半群B.独异点C.群D.阿贝尔群下列代数系统(S,*)中，哪个是群？（）A. S=0,1,3,5，*是模7的加法B. S=Q(有理数集合)，*是一般乘法C. S=Z(整数集合)，*是一般乘法D. S=1,3,4,5,9，*是模11的乘法10.具有如下定义的代数系统(G,*)，哪个不够成群？（）A. G=1,10，*是模11的乘法B. G=1,3,4,5,9，*是模11的乘法C. G=Q，*是普通加法D. G=Q，*是普通乘法2. 下面哪一个偏序集（其中均略去了反映自反关系的序对）能构成格？（）A.A=a,b,c,d,=,B.A=a,b,c,d,e,=,C.A=a,b,c,d,e,f,g,=,D.A=1,2,3,4,=,3. 下面哪个偏序集构成有界格？（）A.(N,)B.(Z,)C.(2,3,4,6,12,|)D.(P(A),)其中|为整除关系，A=a,b,c。7. 用谓词和量词将下列命题符号化：(1).没有不犯错误的人；(2).尽管有人聪明，但未必一切人都很聪明；(3).每个计算机系的学生都学离散数学；(4).所有的人都学习和工作；(5).并非一切推理都能用计算机完成；(6).任何自然数都有惟一的一个后继数。2. 设G=为无环的无向图，|V|=6，|E|=16，则G是（）A.完全图B.零图C.简单图D.多重图3. 含5个结点、3条边的不同构的简单图有（）A.2个B.3个C.4个D.5个4. 任何无向图中结点间的连通关系是（）A.偏序关系B.等价关系C.相容关系D.拟序关系2.设A=1,2,3,4,5，=|ij,i,jA，则的性质是（）A.对称的B.自反的C.反对称的D.反自反、反对称、传递的设集合A=a,b,c，R是A上的二元关系，R=,，那么R是（）A.反自反的B.反对称的C.可传递的D.不可传递的 5. 下列句子中，是命题的有 (1).我是教师。(2).禁止吸烟！(3).蚊子是鸟类动物。(4).上课去！(5).月亮比地球大。6. 设P：我生病，Q：我去学校(1).命题“我虽然生病但我仍去学校”符号化为 。(2).命题“只有在生病的时候，我才不去学校”符号化为 。(3).命题“如果我生病，那么我不去学校”符号化为 。7. 证明下列命题的等值关系：(1).(PQ)(RQ)(PR)Q(2).(PQAC)(APQC)(A(PQ)C(3).P(QP)Q(PR)(4).(PQ)(PR)P(QR)(5).(PQ)(PQ)(PQ)3.设(A,)是格，其中A=1,2,3,4,6,8,12,24，为整除关系，则3的补元是28. 用CP规则证明A(BC)，(EF)C，B(AS)BE。 (PP)(PQ)P(PQ) (P(QQ)(PQ) (PQ)(PQ)(PQ)a) 4.设G是n阶m条边的无向简单边通图，则G的任何生成树对应的G的基本割集系统中均有_个元素。 5.完全二部图Kr,s的边连通度等于_。 6.以1，1，1，1，2，2，4为无向树的度数列，可以生成_棵非同构的无向树。 7.设A=a,b，则A上共有_个不同的偏序关系。 8.设A=a,b,c，B=1,2,3，则A到B共可产生_个不同的双射函数。 9.设A是n(n1)元集，则A上共有22n个二元运算，其中有_个是A到A的函数。 10.设A=1, 2, 3，在A上定义二元运算如下： x,y ? A, x*y=minx,y则*的运算表为_。 三、计算题(共43分) 1.求P(P(QP)的主析取范式（写出过程）。（6分） 2.求公式 的前束范式。（6分） 证明：（）A(BA) A(AB) A(BA) A(BA) A(AB) A(AB) A(AB)（）(ABC)D)(C(ABD) (C(AB)D)(ABC)D)(C(ABD) (ABC)D)(C(ABD) (ABC)D)(ABC)D) (ABC)(ABC)D (ABC)(ABC)D (ABC)(ABC)D (AB)(AB)C)D (C(AB)D)（）(AD)(BD) (AB)D (AD)(BD)(AD)(BD) (AB)D (AB)D (AB)D4 检验下述论证的有效性。如果我学习，那么我数学不会不及格。如果我不热衷于玩扑克，那么我将学习。但我数学不及格。因此我热衷于玩扑克。解：P：我学习 Q：我数学不及格 R：我热衷于玩扑克。如果我学习，那么我数学不会不及格： PQ如果我不热衷于玩扑克，那么我将学习: RP 但我数学不及格: Q因此我热衷于玩扑克。 R即本题符号化为：(PQ)(RP)QR证：证法1：(PQ)(RP)Q)R (PQ)(RP)Q) R (PQ)(RP)QR (QP)(QQ)(RR)(RP) QPRP T所以，论证有效。证法2：设(PQ)(RP)Q为T，则因Q为T，(PQ) 为T，可得P为F，由(RP)为T，得到R为T。故本题论证有效。5.定义正整数集I+上两个二元运算为：a*b=ab，ab=ab， a，bI+。证明*对是不可分配的；对*也不可分配。证：对于I+中任意a,b,c。 a*（bc）= a*（bc）= abc。（a*b）（a*c）= abac= abac= ab+c。因b+c不等于bc，所以*对是不可分配的。a（b*c）= a（bc）= abc，而（ab）*（ac）=（ab）*（ac）=（ab）ac =a acbac，显然对*也不可分配。 6. 写出以下无向图的邻接矩阵并画出其补图。 （7分）7 关系R如图所示，试写出关系矩阵并求出R的自反闭包，对称闭包和传递闭包。 （12分）七、对于代数系统R+,和R,+，其中R+为正实数（不含0）集，R为实数集，为普通乘法，为普通加法：（1）说明R+,和R,+都是群。（2）证明自然对数函数Ln(x)是R+,到R,+的同构。（3）若Ax | Ln(x)H且H,+为R，的子群，证明A，为R+,的子群。 （15分） 二、 用符号写出下列各式并且验证论证的有效性。如果6是偶数，则7被2 除不尽。或5 不是素数，或7被2除尽。但5是素数。所以6是奇数。解：P：6是偶数 Q：7被2除尽 R：5是素数如果6是偶数，则7被2除不尽 PQ或5不是素数，或7被2除尽 RQ5是素数 R所以6是奇数 P即本题符号化为：（PQ）（RQ）R P证：证法1：(PQ)(RQ)R)P (PQ) (RQ) R) P (PQ) (RQ) R) P (PP) (PQ) (RR) (RQ) (PQ) (RQ)T所以，论证有效，但实际上他不符合实际意义。证法2：(PQ)(RQ)R为T，则有R为T，且RQ 为T，故Q为T，再由PQ为T，得到P为T。证明：a)(PQ)，QR，RP(1) RP(2) QR P(3) Q (1)(2)T,I(4) (PQ) P(5) PQ (4)T,E(6) P (3)(5)T,Ib)J(MN)，(HG)J，HGMN(1) (HG) J P(2) (HG) P(3) J (1)(2)T,I(4) J(MN) P(5) MN (3)(4)T,Ic)BC，(BC)(HG) GH(1) BC P (2) B(1)T,I(3) C (1)T,I(4) BC(2)T,I(5) CB (3)T,I(6) CB(4)T,E(7) BC (5)T,E(8) BC (6)(7)T,E(9) (BC) (HG) P(10) HG(8)(9)T,Id)PQ，(QR)R，(PS) S(1) (QR) R (2) QR (1)T,I(3) R (1)T,I(4) Q (2)(3)T,I(5) PQ P(6) P (4)(5)T,I(7) (PS) P(8) PS (7)T,E(9) S (6)(8)T,I(2) 证明：a)AB，CBAC(1) (AC) P (2) A (1)T,I(3) C (1)T,I(4) AB P(5) B (2)(4)T,I(6) CB P(7) B (3)(6)T,I(8) BB 矛盾。(5),(7)b)A(BC)，(CD)E，F(DE) A(BF)(1) (A(BF) P(2) A (1)T,I(3) (BF) (1)T,I(4) B (3)T,I(5) F (3)T,(6) A(BC) P(7) BC (2)(6)T,I(8) C (4)(7)T,I(9) F(DE) P (10) DE (5)(9)T,I(11) D (10)T,I(12) CD (8)(11)T,I (13) (CD) E P(14) E (12)(13)T,I(15) E (10)T,I(16) EE 矛盾。(14),(15)c)ABCD，DEFAF(1) (AF) P(2) A (1)T,I(3) F (1)T,I(4) AB (2)T,I(5) (AB) CD P(6) CD (4)(5)T,I(7) C (6)T,I(8) D (6)T,I(9) DE (8)T,I(10) DEF P(11) F(9)(10)T,I(12) FF矛盾。(3),(11)d)A(BC)，BD，(EF)D，B(AE) BE(1) (BE) P(2) B (1)T,I(3) E (1)T,I(4) BD P(5) D (2)(4)T,I(6) (EF) D P (7) (EF) (5)(6)T,I(8) E (7)T,I(9) EE 矛盾e)(AB)(CD)，(BE)(DF)，(EF)，ACA(1) (AB) (CD) P(2) AB (1)T,I(3) (BE) (DF) P(4) BE (3)T,I(5) AE (2)(4)T,I(6) (EF) P(7) EF (6)T,E(8) EF (7)T,E(9) AF (5)(8)T,I(10) CD (1)T,I(11) DF (3)T,I(12) CF (10)(10)T,I(13) AC P(14) AF (13)(12)T,I(15) FA (14)T,E(16) AA (9)(15)T,I(17) AA (16)T,E(18) A (17) T,E(3) 证明：a)AB，CBAC(1) A P(2) AB P(3) B (1)(2)T,I(4) CB P(5) C (3)(4)T,I(6) AC CPb)A(BC)，(CD)E，F(DE) A(BF)(1) A P(2) A(BC) P(3) BC (1)(2)T,I(4) B P(5) C (3)(4)T,I(6) (CD) E P(7) C(DE) (6)T,E(8) DE (5)(7)T,I(9) DE (8)T,E(10) (DE) (9)T,E(11) F(DE) P(12) F (10)(11)T,I(13) BF CP(14) A(BF) CPc)ABCD，DEFAF(1) A P(2) AB (1)T,I(3) ABCD P(4) CD(2)(3)T,I(5) D(4)T,I(6) DE (5)T,I(7) DEF P(8) F(6)(7)T,I(9) AF CPd)A(BC)，BD，(EF)D，B(AE) BE(1) B P(附加前提)(2) BD P(3) D (1)(2)T,I(4) (EF)D P(5) (EF)(3)(4)T,I(6) E (5)T,I(7) BE CP(4)证明：a) RQ，RS，SQ，PQP(1) RQ P(2) RS P(3) SQ P(4) Q (1)(2)(3)T,I(5) PQ P(6) P (4)(5)T,Ib) SQ，SR，R，PQP证法一：(1) SR P(2) R P(3) S (1)(2)T,I(4) SQ P(5) Q (3)(4)T,I(6) PQ P(7)(PQ)(QP) (6)T,E(8) PQ (7)T,I(9) P (5)(8)T,I证法二：（反证法）(1) P P（附加前提）(2) PQP(3)（PQ）（ QP） (2)T，E(4) PQ(3)T,I(5) Q (1)(4)T,I(6) SQ P(7) S (5)(6)T,I(8) SR P(9) R (7)(8)T,I(10) R P(11) RR 矛盾（9）（10）T，Ic)(PQ)(RS)，(QP)R)，RPQ(1) R P(2) (QP) R P(3) QP (1)(2)T,I(4)(PQ) (RS) P(5) (RS) (PQ)(4)T,E(6) RS (1)T,I(7) PQ(5)(6)(8) (PQ) (QP)(3)(7)T,I(9) PQ (8)T,E求下列各式的主析取范式及主合取范式，并指出下列各式哪些是重言式。b) (PQ)(PQ) c) Q(PQ) d) P(P(Q(QR)e) (P(QR)(P(QR)f) (Q