华南理工《离散数学》模拟题及答案

1、1.A.1+101=110C.全体起立！B中国人民是伟大的。D计算机机房有空位吗?在上面句子中，是命题的是（2.设Q（X）：x是有理数,谓词逻辑中的符号化公式是（5）R（x）：x是实数。命题“某些实数是有理数”在B）A.(Vx)(Q(x)tR(x)丿6Vx9(Q(x)aR(x)C.Ox)(Q(x)tR(x)D(3x)fQ(x)aR(x)对于集合1,2,3,下列关系中不等价的是(B)AR=,B.R=,C.R=v1,1,v3,3,v3,2,DR=,V3,1”V3,3,V2,3,设A=1,2,3,4,5,B=a,b,c,d,e,以下哪个函数是从A到B的双射函数(B)AF=,E.F=1,O,C-F=,

2、DF=,下列判断不正确的是(D)jtiV2|nN)关于普通加法构成群iV2|nGN关于普通乘法构成独异点所有实数对。vc,d=va+c,b+d构成群D实数集R关于。运算构成半群，其中aob=2（a+b）二、判断题（本大题20分，每小题4分）1、命题公式p-（p/q）是重言式。()2、(Vx)A(x)tB)O(3x)(A(x)tE)。(_V)3、设A=a,b,c,RgAxAR=,则R是传递的。4、n阶无向完全图K“的每个顶点的度都是n。5、根树中除一个结点外，其余结点的入度为1。（X）三、解答题（计算或者证明题：本大题50分，每小题10分）设命题公式为iQ/（PtQ）t-P。高级语言程序设计I试

3、卷（A）第1页共11页高级语言程序设计I试卷（A）第3页共11页高级语言程序设计I试卷（A）第3页共11页高级语言程序设计I试卷（A）第2页共（1）求此命题公式的真值表；（2）求此命题公式的析取范式;（3）判断该命题公式的类型。pQQPtQ-iQa(PtQ)P-Q/(PtQ)t-iP0011111010101110100011101001(2)QA(P-Q)T-iPO-1(-QA(-PvQ)v-iPO(Qv-n(iPvQ)ViPO-1(-iPvQ)v(Qv-nP)O1(析取范式)O(P/Q)v(P/Q)v(P/Q)v(PaQ)(主析取范式)(3)该公式为重言式用直接证法证明：前提：(0 x)(

4、C(x)tW(x)AR(x),(3x)(C(x)AQ(x)结论：Gx)(Q(x)AR(x)oc(ccwRQX17X17x)zX17lzx)zX172345678z(vz(vz(vz(z(vz(vz(X/(Q(wRaq(ctar(x)ar(x)ARpES(1)PUS(3)T(2)IT(4,5)IT(6)IT(2)IT(7,8)I(3x)(Q(x)AR(x)EG(9)设R是集合A=1,2,3,4,6,12上的整除关系。给出关系R;给出COVA画出关系R的哈斯图；给出关系R的极大、极小元、最大、最小元。3、解R=,UIaCOV缶V12,V2,4,V2,6,作哈斯图如右：1叭极小元和最小元为1；4rX

5、极大元和最大元为12如图所示带权图，用避圈法（Kniskal算法）求一棵最小生成树并计算它的权值。高级语言程序设计I试卷（A）第3页共11页高级语言程序设计I试卷（A）第3页共11页高级语言程序设计I试卷（A）第2页共C(T)=l+3+4+5+2=155、设字母a,b,c,d,e,f在通讯中出现的频率为：a:30%b:25%c:20%,d:10%e:10%f:5%。试给出传输这6个字母的最佳前缀码？问传输1000个字符需要多少位二进制位？解先求传输100个字符所需要的位数。a:30,b:25,c:20,d:10,e:10,f:5是依照出现频率得出的个数。构造最优二义树如下:5101020253

6、01510202530252025302545304555100需要二进制位数为10W(T)=10 x4x(5+10)+3x10+2x(20+25+30)=2400高级语言程序设计I试卷(A)第 页共11页B设P,Q是命题公式，德摩根律为：-(P八Q)0(iPv-,Q)。令M(x)：x是大学生,P(y)：y是运动员，H(x,y)：x钦佩y。则命题“有些大学生不钦佩所有运动员。”可符号化为(3x(M(X)AVy(P(y)-H(x,y)o设集合匪a,b,c,E的幕集P(E)=(a,b,c,a,b,a,c,b,c,a,b,c)。设R为定义在集合A上的一个关系，若R是(自反的，对称的，传递的)，则R称

7、为是集合A上的等价关系。设集合A上的关系R和S,R=,S=,则MS二(,)。个代数系统VS,*,其中S是非空集合。*是5上的一个二元运算，如果(运算*是封闭的),则称代数系统VS,*为广群。设图G=，如果有图G=VV,E，且(VrcVrEcE),则称G，是G的子图。一棵有n个顶点的树含有(n-1)边。P322如果二元运算运算*对集合A封闭，则意味着对任意的a,bwA有(a*bWA)o设非空集合A的幕集为pZ则在代数系统丹，QU中，对于U运算的幺元是();设G是个具有5个结点的简单无向完全图，则6有(5*(5-1)/2)条边。设G是个无自环的无向图，其中有2个结点的度数为4,其余结点的度为2,有

8、6条边。则G中共有(2)个结点。因此，G是个(多重)图。判断下列命题的对错。正确的在括号内填错误的在括号内填X。TOC o 1-5 h z“我们要努力学习”是命题。(x)命题“如果雪是黑的，那么太阳从东方出”是假命题。(X)3(3x)(A(x)tB(x)O(Vx)A(x)(3x)B(x)。P70(V)命题公式(Q/(PtQ)TiP是重言式。P19,永真式(X)命题公式(P/Q)v(iRtT)是析取范式。P31析取范式定义(X)R(x)：“x是大学生。”是命题。(X)7设A,B是任意集合，则AGB=(A-B)U(B-A)P92(V)8集合A=12,3上的关系,是对称的。(X)集合A的幕集Q(刃上

9、的包含关系是偏序关系。P140TOC o 1-5 h z每个元素都有逆元的半群是群。不一定有幺元(X)设X=1,2,3,Y=a,bo关系F=,是函数。(X)P14712ii阶无向完全图Kn的每个顶点的度都是ii。顶点数-1(X)设I是整数集，+是I上的普通加法，则代数系统是群。(V)经过图中每条边一次且仅一次的回路称为汉密尔顿回路。(X)根树中除根结点外，其余结点的入度都为1。(V)设A,B都是合式公式，则AaBt-JB也是合式公式。(J)PtQOiPvQo(V)对谓词公式(Vx)(P(y)vQ(x,y)aR(x,y)中的自由变元进行代入后得到公式(Vx)(P(z)vQ(x,z)aR(x,y)

10、o(J)对任意集合A、B、C,有(A-B)-C=(A-C)-(B-C)oP95(V)20.三、在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的内。1.(1)如果天气好，那么我去散步。(3)x=3。在上面句子中一个结点到另一个结点可达或相互可达。P284(X)2.34.5.是命题。(2)天气多好呀！(4)明天下午有会吗?(1)设：P：王强身体很好；Q：王强成绩很好。命题“王强身体很好，成绩也很好。”在命题逻辑中可符号化为o(4)PvQ(2)PtQPa-,Q(4)PaQ设S(x)：x是学生，J(y)：y是教师，L(x,y)：x钦佩y。命题所有学生都钦佩一些教师”的符号化公式是。

11、(3)(1)(2)(4)Vx(S(x)aVy(J(y)aL(x,y)Vx3y(S(x)t(J(y)tL(x,y)Vx(S(x)-3y(J(y)aL(x,y)3yVx(S(x)t(J(y)aL(x,y)_o(2)P9(2)-i(Pa(QvR)(4)/QT/RtPo(4)下列式子是合式公式的是(PVQAQ)(3)(P-iQ)下列式子中正确的是(1)(2)(Vx)P(x)O(3x)P(x)-i(Vx)P(x)：(Vx)-iP(x)-1(3x)P(x)U(3x)-nP(x)(4)-!(3x)P(x)U(Vx)-.P(x)设S=d,3,a,a,则S的幕集P(S)有个元素。P858(2)12(3)16(4

12、)32设R为定义在集合A上的一个关系，若R是,则R为等价关系。(2)(1)反自反的，对称的和传递的(2)自反的，对称的和传递的(3)自反的，反对称的和传递的(4)对称的，反对称的和传递的设A=1,2,3,B=1,2,则下列命题不正确的是。(1)AAB=1,2(2)A-B=3P90(3)AB=2,3(4)BcA命题公式P蕴涵Q是指。(3)(1)P与Q都是重言式(2)P/Q是重言式(3)PQ为重言式(4)QhR为重言式设A=1,2,3,4,5,B=6,7,8,9,10,以下哪个关系是从A到B的入(单)射函数。(2)对应(1)F=,(2)F=,F=,(4)F=,笛.运算“一”是整数集I上的普通减法，

13、则代数系统满足下列性质o(4)(1)结合律(2)交换律(3)有零元(4)封闭性高级语言程序设计I试卷(A)第 #页共11页高级语言程序设计I试卷(A)第 #页共11页高级语言程序设计I试卷（A）第2页共高级语言程序设计I试卷(A)第 #页共11页高级语言程序设计I试卷(A)第 #页共11页高级语言程序设计I试卷（A）第2页共13.设I是整数集，N是自然数集，P(S)是S的幕集，“X,+,C”是普通的乘法，加法和集合的交运算。下面代数系统中是群。(1)(2)(3)(4)14.下列四个有6个结点的图是连通图。P281(3)高级语言程序设计I试卷(A)第 #页共11页高级语言程序设计I试卷(A)第

14、#页共11页高级语言程序设计I试卷（A）第2页共高级语言程序设计I试卷(A)第 #页共11页高级语言程序设计I试卷(A)第 #页共11页高级语言程序设计I试卷（A）第2页共P274(4)(1)(2)15有m条边的图的结点度数总和为(1)m(3)2(m-1)设：p：刘平聪明。q：刘平用功。在命题逻辑中，命题：“刘平不但聪明，而且用功”可符号化为：。(1)(1)PaQ(2)-.PVQ是重言式时，称“A蕴含B”，并(S)Pv-iQB0(2)高级语言程序设计I试卷（A）第 页共11页高级语言程序设计I试卷（A）第 #页共11页高级语言程序设计I试卷（A）第2页共(1)(2)AtE(3)AiB(4)iA

15、BTOC o 1-5 h z设Q(x)：x是有理数，R(x)：x是实数。命题“每一个有理数是实数”在谓词逻辑中的符号化公式是(1)(1)(Vx)(Q(x)-R(x)(2)(Vx)(Q(x)aR(x)(3)(3x)(Q(x)-R(x)(4)(3x)(Q(x)aR(x)19设a,b和(c,d)分别表示实数集上的闭区间和开区间，则(0,4n2,6)-(1,3)=(1)(1)3,4(2)(3,4)(3)3,4(4)0,1U3,620对于集合1,2,3,下列关系中不等价的是(2)R=,R=V1,1,V1,4R=,(4)R=vi,l,vi2,v2,l,vi,3,”,集合S的慕集P(S)关于集合的并运算“U

16、”的零元为(2)(1)e(2)S(3)没有(4)P(S)给定无孤立点无向图G的边集：(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),找出图G的一棵生成树为P324(1)(1)1(2)J:(1,2),(1,3),(:(1,2),(1,3),24),23),（3,5）（2,4）!(1,2),(1,3),：3,5),(4,5）(4)!(1,2),(3,4),Q）的真值表;（2）求命题公式（PA（Q-R）S的析取范式。真值表：PQQI001Q1iQa(PtQ)1-iPHQ/(PtQ)T-1P11010101110100011101001析取范式：P31(Pa(QtR

17、)tSO-i(Pa(-iQvR)vSO-iPv-i(-iQvR)vSOPv(Qa-iR)vS六、用推理规则证明P75六、用推理规则证明P75高级语言程序设计I试卷（A）第 #页共11页高级语言程序设计I试卷（A）第 页共11页高级语言程序设计I试卷（A）第2页共Vx(P(x)-Q(x)证明：(Vx)P(x)P(u)(Vx)(P(x)-Q(x)P(u)tQ(u)Q(u)(Vx)Q(x)(Vk)P(x)-(Hx)Q(x)VxP（x）tVxQ（x）P（附加前提）US（全称指定规则），PUS,T,，,5UG（全称推广规则），CP七、求下面公式的主析取范式与主合取范式，并写出相应的成真赋值(PtQ)/(

18、RtP)/(RtQ)tP)P34PQR-.(PtQ)/(RtP)v-i(Rt-!Q)t世)TTTFTTFTTFTTTFFTFTTFFTFTFFTFFFFF高级语言程序设计I试卷（A第10页共11页高级语言程序设计I试卷（A）第 #页共11页高级语言程序设计I试卷（A）第2页共高级语言程序设计I试卷（A第10页共11页高级语言程序设计I试卷（A）第 页共11页高级语言程序设计I试卷（A）第2页共主析取范式：iiiiiovinioivinioovmoio=(PAQA-iR)V(PA-iQAR)V(PAqQAqR)VhPAQAqR)主合取范式：mmAmonAmooiam00o=(PVQVR)A(-1PVQVR)AhPVqQVR