第 1 次作业一、单项选择题（本大题共 20 分，共 10 小题，每小题 2 分）1. 设有向图（a）、（b）、（c）、（d）如下图所示，则下列结论成的是（）A. （a）是强连通的B. （b）是强连通的C. （c）是强连通的D. （d）是强连通的2. 设有 33 盏灯，拟公用一个电源，则至少需要（）个 5 插头的接线板?A. 4B. 6 n 为何值时，无向完全图 Kn 是欧拉图？n 为何值时，无向完全图 Kn 仅存在欧拉道路而不存在欧拉回路？2. 下列关系是否具有如下性质：自反性，对称性，反对称性，传递性？ R_1={(x,y)|x,y∈I,x>y}⑴ ；(2)R_2={(x,√x)|x≥0, 且 x 为实数；A⑶ 上的恒等关系 R_3={(x,x)|x∈；A={1,2,3•••⑷ ，10}上的空关系 ϕ。3. 五、证明题（本大题共 24 分，共 3 小题，每小题 8 分）1. 设<G,*>是群，对任一 a ∈G，令 H={y | y*a=a*y,y∈G}，试证明：<H,*>是<G,*>的子群。2. 证明任何阶大于 1 的简单无向图必有两个结点的度相等。3. 用 CP 规则证明由 P→(Q→S)，┐R∨P，Q 能有效推出 R→S。答案：一、单项选择题（20 分，共 10 题，每小题 2 分） 1. A 2. C 3. C 4. A 5. B 6. C 7. B 8. C 9. B 10. D 二、多项选择题（15 分，共 5 题，每小题 3 分）1. BC 2. ACD 3. BC 4. ABC 5. AD 三、判断题（20 分，共 10 题，每小题 2 分）1. × 2. √ 3. √ 4. × 5. × 6. √ 7. √ 8. √ 9. √ 10. √ 四、简答题（21 分，共 3 题，每小题 7 分）1. 参考答案：当 n 为大于 2 的奇数时，无向完全图 Kn 是欧拉图，因为每个节点的度数为偶数。当 n 为 2 时，K2，是唯一存在两个奇度点的完全图，因此此图只存在欧拉道路解题方案：评分标准：2. 参考答案：R1⑴ 具有反对称性与传递性； R2⑵ 具有反对称性； R3⑶ 具有自反性，对称性，反对称性与传递性； A⑷ 上的空关系具有对称性，反对称性与传递性。解题方案：评分标准：3. 参考答案：{<1,3>,<1,2>,<2,4>,<3,3>,<3,2>}{<1,1>,<1,3>,<2,4>,<3,4>}{<1,1>,<1,2>,<1,4>,<3,1>,<3,2>,<3,3>}{<1,1>,<1,3>,<2,1>,<3,3>,<4,2>}{<2,2>,<2,3>,<3,1>,<4,4>}{<1,1>,<3,1>,<4,2>,<4,3>} 解题方案：评分标准：五、证明题（24 分，共 3 题，每小题 8 分）1. 参考答案：证明:显然 HG.运算在 H 中满足结合律。∀ p,q∈H, a ∈Gp*a=a*p,  q*a=a*q故(p*q)*a=p*(q*a)=p*(a*q)=(p*a)*q=(a*p)*q=a*(p*q)从而 p*q∈H。这说明 H 对运算*是封闭的。由于 e*a=a*e，所以 e∈H。对于任意的 p∈H，由于 p*a=a*p，有p^(-1)*(p*a)*p^(-1)=p^(-1)*(a*p)*p^(-1)所以 a*p^(-1)=p^(-1)*a,故 p^(-1)∈H。综上所述，<H,*>是<G,*>的子群。解题方案：评分标准：2. 参考答案： 证明：设简单无向图 G 有 n 个结点，则每个结点的度最多为 n-1。如果存在某个结点的度为 n-1，则任何结点都不可能为孤立点，于是，任何结点的度均大于等于 1，小于等于 n-1，由抽屉原理知，这样的 n 个数中至少有两个是相同的。所以必有两个结点的度相等。解题方案：评分标准：3. 参考答案：（1）R    P（附加前提）（2）┐R∨P    P（3）P      T(1)(2)I（4）P→(Q→S)   P（5）Q→S     T(3)(4)I（6）Q      P（7）S      T(5)(6)I（8）R→S　　CP解题方案：评分标准： C. 8D. 103. 下列关系中哪些能构成函数？（）A. {〈x,y〉|x,y∈ N,x+y<10} B. {〈x,y〉|x,y∈ N,x+y=10}C. {〈x,y〉|x,y∈ R,|x|=y} D. {〈x,y〉|x,y∈ R,x=|y|}4. 假设 A={a,b,c,d},考虑子集 S={{a,b},{b,c},{d}}，则下列选项正确的是（）。A. S 是 A 的覆盖B. S 是 A 的划分C. S 既不是划分也不是覆盖 D. 以上选项都不正确5. 令 S={a，b}，S 上有 4 个二元运算：*，°，∙，∆分别由表 5.2.2-1、表5.2.2-2、表 5.2.2-3 和表 5.2.2-4 确定。 表 5.2.2-1 表 5.2.2-2 表 5.2.2-3 表 5.2.2-4 下面说法正确的是A. 运算* 的幺元是 a，无零元B. 运算° 的幺元是 a，无零元C. 运算∙的幺元是 a，无零元D. 运算∆的幺元是 a，无零元 6. 如果小王和小张都不去，则小李去。设 P：小王去。Q：小张去。R：小李去。则命题符号化为。A. ┐Q∧┐P∨RB. (Q→P)∧RC. (┐P∧┐Q)→RD. (P∧Q)→R7. 下列语句是命题，并且真值为 0 的是（）A. 雪式白的。B. 1+2>4。C. 天气真好啊！D. 我正在说谎。 8. 下列公式中不是合式公式的是（）A. ┐(P∧Q)B. (P→(P∨┐Q))C. (P→Q)→(∧Q)D. P↔Q9. 如果有限个数的乘积为零，那么至少有一个因子等于零。N(x)：x 是有限个数的乘积。Z(y)：y 为 0。P（x）：x 的乘积为 0 。F（y）：y 为乘积中的一个因子则命题可表示为（）。A. (∃x)(N(x)→P(x)∧(∃y)(F(y)⋀(Z(y)))B. (∃x)(N(x)⋀P(x))→(∃y)(F(y)⋀(Z(y)))C. (∃x)(N(x)→P(x)∧(∃y)(F(y)→(Z(y)))D. (∀x)(N(x)→P(x)∧(∃y)(F(y)⋀(Z(y)))10. 设 A、B、C 是任意集合，判断下述论断是否正确，并将正确的题号填入括号内（）。A. 若 A∪B=A∪C，则B=C B. 若 A∩B=A∩C ，则B=C C. 若 A-B=A-C，则B=CD. 若∼A=∼B，则A=B二、多项选择题（本大题共 15 分，共 5 小题，每小题 3 分）1. 下图是（）。A. 是强连通的B. 是弱连通的C. 是单侧连通的D. 是不连通的2. 判别有效结论的过程就是论证过程。常见的证明方法有三种、、。 A. 真值表法B. 逆向推理C. 直接证法D. 间接证法3. 间接证法主要有两种，一种称之为，还有一种是。A. 真值表法B. CP 规则C. 反证法（也叫归谬法）D. 直接推理4. 函数 f：R×R→R×R,f(<x，y>)=<x+y，x-y>是(  )函数。A. 入射B. 满射C. 双射D. 以上答案都不对5. 设 A={1,2,3}，则集合 A 上的关系R={<1,1>,<1,3>,<3,1>,<2,3>,<3,2>}是（）关系。A. 对称的B. 反对称的C. 不是对称的 D. 不是反对称的三、判断题（本大题共 20 分，共 10 小题，每小题 2 分）1. 判断对错：{1，2,花，班级}是一个集合（）。2. 用描述法表示下列集合A={0,2,4,…,200}，表示为{2x|x∈Z 且x≤100}。3. 判断对错：集合{2,3,4，•••}是无限集（）。4. 粗线描绘出的是下图的最小生成树。5. 若 A↔B，则 B↔┐A。6. 设代数系统 V=〈{a,b},*〉是半群，且 a*a=b,则 a*b=b*a。7. 设集合 A={216，243，357，648}.定义 A 上的关系R={〈x,y〉|x,y∈A，且 x 与 y 中至少有一个相同数字}。则 R 是 A 上的一个相容关系，R不是等价关系。8. 判断该句是否为真命题。∀x(P(x)∨Q(x))，其中，P(x)：x=1。Q(x):x=2。定义域：D={1,2};9. 试判断命题是否正确：两个函数的复合是一个函数。（）10. 小明爱吃面包。可符号化为：(F(a)→G(a))其中，F(x)：x 是人，G(x):x爱吃面包，a:小明。四、简答题（本大题共 21 分，共 3 小题，每小题 7 分）1.