第 3 次作业一、单项选择题（本大题共 20 分，共 10 小题，每小题 2 分）1. 任意一个具有多个等幂元的半群，它______。A. 不能构成群B. 不一定能构成群C. 必能构成群D. 能构成交换群2. 设 B 是不含变元 x 的公式，谓词公式((∀x)(A(x)→B)等价于( )A. (∃x)A(x)→BB. (∀x)A(x)→BC. A(x)→BD. (∀x)A(x)→(∀x)B3. T 是一棵树,有两个 2 度结点，一个 3 度结点，三个 4 度结点，T 有几片树叶（）A. 6. 若┐P→┐Q 的值为 0，则 P 的值为 0，Q 的值为 0。7. P、Q 为两个命题，若 P、Q 有一个为真，则 P∨Q 为真。8. P：√2 是无理数。命题 P 的真值为 1.9. 集合之间的⊆关系是自反的、反对称的和可传递的。10. 设 R 是 X 上的二元关系，那么a）R 是自反的，当且仅当 r(R) = R 。b）R 是对称的，当且仅当s(R) = R 。c）R 是传递的，当且仅当t(R) = R。四、简答题（本大题共 18 分，共 3 小题，每小题 6 分）1. 确定下列集合的幂集：(1) A={a，{b}}；（2）B={1，{2，3}}；（3）C={ϕ，a，{b}}；（4）D=ρ(ϕ)={ϕ}2. 3. 集合 A={1,2,3,4}，A 上的关系 R 的关系矩阵为： 图3.5.1-1 R 的关系图 讨论 R 的性质。五、证明题（本大题共 24 分，共 3 小题，每小题 8 分）1. 设<G,*>是一个群，x∈G，定义：∀a,b∈G,a∘b=a*x*b。证明：<G, ∘>也是一个群。2. 符号化下列命题并证明。今天天气不好，就一定有考生不能提前进入考场；当且仅当所有考生提前进入考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好。3. 反证法证明 p→┐q，q∨┐r，r∧┐s ⇒┐p答案：一、单项选择题（20 分，共 10 题，每小题 2 分）1. A 2. B 3. C 4. B 5. A 6. B 7. C 8. D 9. B 10. D 二、多项选择题（18 分，共 6 题，每小题 3 分）1. BC 2. ABCD 3. BC 4. ABC 5. AD 6. AD 三、判断题（20 分，共 10 题，每小题 2 分）1. √ 2. × 3. × 4. √ 5. √ 6. × 7. √ 8. √ 9. √ 10. √ 四、简答题（18 分，共 3 题，每小题 6 分）1. 参考答案：分析与提示：欲求一个给定集合的幂集合，首先把这个给定集合的所有子集列出，并检验所列子集的个数是否等于 2^n 个,n 为给定集合的元数,当然,熟练者可以省略这一步骤。  答案：（1）因为 A 的所有子集为 ϕ，{a}，{{b}}，{a，{b}}，所以ρ(A)={ϕ,{a},{{b} },{a,{b} }}.   （2）因为 B 的所有子集为 ϕ，{1}，{{2，3}}和{1，{2，3}}。所以 ρ(B)={ϕ,{1},{{2,3} },{1<{2,3} }}.    （3）因为 C 的所有子集为 ϕ，{ϕ}，{a},{{b}},{ϕ,a},{ϕ,{b}},{a,{b}},{ϕ,a,{b}},所以ρ(C)={ϕ，{ϕ}，{a},{{b} },{ϕ,a},{ϕ,{b} },{a,{b} },{ϕ,a,{b} }}解题方案：评分标准：2. 参考答案：{<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>}解题方案：评分标准：3. 参考答案：从 R 的关系矩阵和关系图容易看出，R 是自反的、对称的。解题方案： 一般地，我们有：（1）若关系 R 是自反的，当且仅当其关系矩阵的主对角线上的所有元素都是1；其关系图上每个结点都有自环。（2）若关系 R 是对称的，当且仅当其关系矩阵是对称矩阵；其关系图上任意两个结点间若有定向弧，必是成对出现的。（3）若关系 R 是反自反的，当且仅当其关系矩阵的主对角线上的元素皆为 0；关系图上每个结点都没有自环。（4）若关系 R 是反对称的，当且仅当其关系矩阵中关于主对角线对称的元素不能同时为 1；其关系图上任意两个不同结点间至多出现一条定向弧。评分标准：五、证明题（24 分，共 3 题，每小题 8 分）1. 参考答案：证明：显然∘是二元运算，根据群的定义，需要证明运算满足结合律、有单位元和每个元素均有逆元。∀a,b,c∈G，有(a∘b)∘c=(a*x*b)*x*c=a*x*(b*x*c)=a∘(b∘c)可知运算∘是可结合的。∀a∈G，有a∘x^(-1)=a*x*x^(-1)=ax^(-1)∘a=x^(-1)*x*a=a故 x^(-1)是单位元。∀a∈G，有a∘〖(x〗^(-1)*a^(-1)*x^(-1))=a*x*x^(-1)*a^(-1)*x^(-1)=x^(-1)〖(x〗^(-1)*a^(-1)*x^(-1))∘a=x^(-1)*a^(-1)*x^(-1)*x*a=x^(-1)故∀a∈G，x^(-1)*a^(-1)*x^(-1)是 a 的逆元。综上所述，<G, ∘>是一个群。解题方案：评分标准：2. 参考答案： 解题方案：评分标准：3. 参考答案：(1)   p     附加前提(2)   p→┐q   前提(3)   ┐q    (1)，(2)(4)   q∨┐r   前提(5)   ┐r    (3)，(4)(6)    r∧┐s  前提(7)    r    (6)(8)    r∧┐r （矛盾）(5)，(7)解题方案：评分标准： 7B. 8C. 9D. 104. 欧拉公式的原型________________A. v+e+r＝2B. v-e+r＝2C. v-e-r＝2D. v+e-r＝25. 命题 a）：如果天下雨，我不去。写出命题 a）的逆换式。 A. 如果我不去，天下雨。B. 如果我去，天下雨。C. 如果天下雨，我去。D. 如果天不下雨，我去。6. (P→Q)→R 的合取范式为。A. (┐P∨R)∧(Q∨┐R)B. (P∨R)∧(┐Q∨R)C. P∧Q∧RD. P∨Q∨R7. 是命题的是（）。 A. x 大于 y B. d 是整数C. 他昨天做了十五道题D. a 是大学生8. 设 A、B 两个集合，当（）时 A-B=B。A. A=BB. A⊆BC. B⊆AD. A=B=ϕ9. 如果有限个数的乘积为零，那么至少有一个因子等于零。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=CC. 若 A-B=A-C，则B=CD. 若∼A=∼B，则A=B二、多项选择题（本大题共 18 分，共 6 小题，每小题 3 分）1. 下图是（）。A. 是强连通的B. 是弱连通的C. 是单侧连通的D. 是不连通的2. 下列集合关于指定的运算能构成半群的是（）A. G={a^n│n∈Z}（a 是正实数），运算*是普通乘法B. R 为实数集，运算*定义为：∀a,b∈R，a*b=a+b+abC. Q^+为正有理数集，运算+为普通加法D. Q^+为正有理数集，运算+为普通乘法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. 不是反对称的6. 设 A={1,2,3}，则集合 A 上的关系 R={<1,1>,<2,2>,<2,1>,<3,3>}是（）关系；A. 自反B. 反自反C. 不是自反D. 不是反自反三、判断题（本大题共 20 分，共 10 小题，每小题 2 分）1. 一般情况下，笛卡尔积不满足交换律和结合律。（）2. P→(∧Q)是命题公式。3. 我们将结点 a、b 的无序结点对记为<a,b>，有序结点对记为(a,b)。4. 下图的一个生成子图为5. 给出下图的三种遍历结果前根：a,b,d,g,e,h,i,c,f 中根：g,d,b,g,e,i,a,c,f 后根：g,d,h,i,e,b,f,c,a