精品文档院术师范学广东技模拟试题科目：离散数学120分钟考试时间:考试形式：闭卷姓名：学号：系别、班级：2分，共10分）一．填空题（每小题__________。?x?y?P(x)∨Q(y)1.谓词公式的前束范式是__)xxQ(xP(x)____，，2.设全集A_{4,5}B=__则A∩{2}__,,E1,2,3,4,55,A21,,32,B_______{1,3,4,5}?BAb,c}}__________，则3.设__，b,c,b,a,ABaB(A))(_____Φ_______。)(AB()4.在代数系统（N，+）中，其单位元是0，仅有_1___有逆元。ne条边，则G有___e+2-n____个面。5．如果连通平面图G有个顶点，二．选择题（每小题2分，共10分）P(QR)等价的公式是（1.与命题公式）（A）（B）（C）（D）RPQ)()R)R(QPP(QRQ)(Pbb,a,aAa,b,cR,不具备关系(2.设集合上的二元关系,A)性质（A）(A)传递性(B)反对称性(C)对称性(D)自反性GV,E中,结点总度数与边数的关系是3.在图()EEdeg(v)deg(v)2deg(v)Evdeg()2E(A)(C)(B)(D)iiiiVvVv4.设D是有n个结点的有向完全图,则图D的边数为()n(n1)n(n1)n(n1)/2n(n1)/2(A)(B)(D)(C)5.无向图G是欧拉图,当且仅当()(A)G的所有结点的度数都是偶数(B)G的所有结点的度数都是奇数精品文档．精品文档(C)G连通且所有结点的度数都是偶数(D)G连通且G的所有结点度数都是奇数。三．计算题（共43分）pqr的主合取范式与主析取范式。（1.求命题公式6分）解：主合取方式：p∧q∨r?(p∨q∨r)∧(p∨?q∨r)∧(?p∨q∨r)=∏0.2.4主析取范式：p∧q∨r?(p∧q∧r)∨(p∧q∧?r)∨(?p∧q∧r)∨(?p∧?q∧r)∨(p∧?q∧r)=∑1.3.5.6.710000111Md,Aa,b,c,的上的二元关集2.设合系R关系矩阵为求R00001000)tR(),(RsRr()(),(),(rRsRtR),的关系图。R的关系矩阵，并画出分）10（，3无向图G有12条边，G中有6个3度结点，其余结点的度数均小于3，问G中至少有多少个结点？（10分）精品文档．精品文档解：∵G（V,E），|E|=V，d（Vi）<3,设至少有x个节点，由握手定理得：2×12=∑d（Vi）<6×3+(x-6)×32<(x-6)=＞x>8故G中至少有9个节点。4求下面两个图的最小生成树。（12分）(z,)是否为格？说明理由。5.试判断（5分）解：（Z,≤）是格，理由如下：对于任意a∈Z，a≤a成立，满足自反性；对于任意a∈Z，b∈Z，若a≤b且b≤a，则a=b，满足反对称性；对于任意a，b，c∈Z，若a≤b，b≤c，则a≤c，满足传递性；而对于任意a，b∈Z，a≤b，b为最小上界，a为最大下界，故（Z，≤）是格。（注：什么是格？）精品文档．精品文档四．证明题（共37分）AB,(BC)C,(AD)D。（10分）1.用推理规则证明证明：编号公式依据前提（?B∨C）∧?C（1）（1）（2）?B∨C，?C（2）（3）?B（3）（4）A→B（3）（4）?A（5）前提）D?（?A∧）（6）（7（6）A∨?D（5）（8（）6?D）f和gaba,b):RRR,g(b(:fRRR,fa,b)ag求证：是实数集，，。设2.R都是满射，但不是单射。（10分）证明：要证f是满射，即?y∈R,都存在（x1，x2）∈R×R，使f（x1，x2）=y，而f（x1，x2）=x1+x2，可取x1=0，x2=y，即证得；再证g是满射，即?y∈R，,都存在（x1，x2）∈R×R，使g（x1，x2）=y，而g（x1，x2）=x1x2，可取x1=1，x2=y，即证得；最后证f不是单射，f（x1，x2）=f（x2，x1）取x1≠x2，即证得，同理：g（x1，x2），即证得。≠x2x1x1x2=g（，），取精品文档．精品文档3.无向图G有9个结点，每个结点的度数不是5就是6，求证：G中至少有5个6度结点或6个5度结点。（10分）证明：设G中至多有4个6度结点且5个5度结点，∴d（Vi）=49不是偶数，故它不是一个图，矛盾。（下面只供参考，个人答案）4.设平面上有100个点，期中任意两点间的距离至少是1，则最多有300对点距离恰好为1。（7分）证明：设任意两点间的读书和恰好为1，则满足：∑d（Vi）=2ed（Vi）≤6精品文档．精品文档∴6×100≥2ee≤300故最多只有300条边，即300对点距离恰好为1.精品文档．
