1。 谓词公式的前束范式是__ ∃x∃y¬P（x)∨Q(y） __________。 2。 设全集则A∩B =__{2｝__，_{4，5｝____， __ ｛1，3,4，5} _____ 3. 设，则__ {｛c}，｛a,c}，｛b，c}，{a,b,c}} __________,_____Φ_______。 4. 在代数系统（N，+)中,其单位元是0，仅有 1 有逆元。 5．如果连通平面图G有个顶点，条边，则G有___e+2—n____个面. 二．选择题（每小题2分，共10分) 1. 与命题公式等价的公式是（ ) （A) （B） （C） （D)
2. 设集合,A上的二元关系不具备关系( ）性质
（A） (A)传递性 （B)反对称性 （C）对称性 (D)自反性 3。 在图中，结点总度数与边数的关系是（ ) （A) (B) （C)(D)
4。 设D是有n个结点的有向完全图，则图D的边数为（ ） (A) (B） (C） (D)
5. 无向图G是欧拉图,当且仅当（ )
(A) G的所有结点的度数都是偶数 （B)G的所有结点的度数都是奇数
（C）G连通且所有结点的度数都是偶数 （D) G连通且G的所有结点度数都是奇数. 三．计算题（共43分）
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.7
2. 设集合上的二元关系R的关系矩阵为,求的关系矩阵，并画出R,的关系图。（10分）
3 无向图G有12条边,G中有6个3度结点，其余结点的度数均小于3，问G中至少有多少个结点？（10分）
解：∵G(V，E）,｜ E |=V，d（Vi)〈3，
第 1 页 共 3 页
设至少有x个节点，由握手定理得: 2×12=∑d(Vi）〈6×3+（x—6)×3 2<（x-6) =＞ x〉8 故G中至少有9个节点。
4 求下面两个图的最小生成树。（12分） 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分） 1. 用推理规则证明。（10分）
证明： 编号 （1） （2） (3） （4） (5） （6) （7） （8）
公式 （¬B∨C）∧¬C ¬B∨C,¬C ¬B A→B ¬A ¬（¬A∧D) A∨¬D ¬D 依据 前提 (1） （2） （3） （3）（4） 前提 (6） (5）（6）
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）=g(x2，x1），取x1≠x2,即证得。
第 2 页 共 3 页
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）=2e d(Vi）≤6 ∴6×100≥2e e≤300
故最多只有300条边，即300对点距离恰好为1。
第 3 页 共 3 页
因篇幅问题不能全部显示，请点此查看更多更全内容