第 2 次作业一、单项选择题（本大题共 20 分，共 10 小题，每小题 2 分）1. 关*运算如下表所示，_________能使<{a,b},*>成为独异点。A. B. C. D. 2. 一棵有向树，如果恰有一个节点的入度为０，其余所有节点的入度都为１，则称为____________A. 根树B. ┐(p∨(┐p→(q∨(┐q→r))))⇔ (p∨┐q∨r) ∧(p∨┐q∨┐r)∧ (p∨q∨┐r)( ┐p∨q∨r)∧(┐p∨q∨┐r) ∧(┐p∨┐q∨r)∧ (┐p∨┐q∨┐r)(原公式否定的主合取范式)p∨ (┐p→(q∨ (┐q→r)))⇔ (┐p∧q∧┐r)∨(┐p∧q∧r)∨ (┐p∧┐q∧r) ∨(p∧┐q∧┐r)∨ (p∧┐q∧r) ∨(p∧q∧┐r)∨ (p∧q∧r)(主析取范式)解题方案：评分标准：2. 参考答案：（1）A∩～B={a，d}∩{c，d}={d}.(2) （A∩B）∪～C={a}∪{a,c,e}={a,c,e}.（3）～A∪（B－C）={b,c,e}∪{a,e}={a,b,c,e}.（4）ρ(A)={ϕ,{a},{d},{a,d}}.ρ(B)={ϕ,{a},{b},{e},{a,b},{a,e},{b,e},{a,b,e}}故 ρ(A)∩ρ(B)={ϕ,{a}}解题方案：评分标准：五、简答题（20 分，共 2 题，每小题 10 分）1. 参考答案：（1）是映射。domS_1={1,2,3,4}，R_(S_1 )={<1,4>,<2,3>,<3,4>}（2）是映射。dom S_2={1,2,3}，，R_(S_2 )={<2,3>,<3,2>,<3,4>}（3）不是映射。（4）是映射。dom S_4={1,2,3}，R_(S_4 )={<2,3>}解题方案： 注意区别 x 的像和{x}的像两个不同的概念。x 的像 f(x)∈Y，而像f({x})⊆Y。评分标准：2. 参考答案：g°f={<1,α>,<2,γ>,<3,β>},  〖(g°f)〗^(-1)={<α,1>,<β,3>,<γ,2>} f^(-1)={<c,1>,<a,2>,<b,3>},   g^(-1)={<α,c>,<β,b>,<γ,a>} f^(-1)°g^(-1)={<<α,1>,<β,3>,<γ,2>}可见，〖(g°f)〗^(-1)=f^(-1)°g^(-1) 解题方案：评分标准： 普通树C. 树根D. 树节点3. 下列代数系统中，_______是群。A. S={0,1,3,5}，*是模 7 加法B. S=Q（有理数集），*是普通乘法C. S=Z（整数集合），*是普通减法D. S={1,3,4,5,9}，*是模 11 乘法4. 图 G 所示平面图 deg(R3)为A. 4B. 5C. 6D. 35. 设无向图中有 6 条边，3 度与 5 度顶点各 1 个，其余顶点都是 2 度点，问该图有多少个顶点（）A. 5B. 4C. 2D. 66. （1）燕子北回，春天来了。设 P: 燕子北回。Q：春天来了。则（1）可以表示为。A. P→QB. Q→PC. P↔QD. P ∨Q7. 设U={1，2，3，4，5}，A={2，4}，B={4，3，5}，C={2，5，3}，确定集合(A-C)-B = （）。A. {1,4}B. {2,3,4,5}C. {4}D. ϕ8. 设 G 是有 6 个结点的完全图，从 G 中删去（）条边，则得到树。A. 6B. 9C. 10D. 159. 下列语句是命题，并且真值为 0 的是（）A. 雪式白的。B. 1+2>4。C. 天气真好啊！D. 我正在说谎。10. 下列公式中不是合式公式的是（）A. ┐(P∧Q)B. (P→(P∨┐Q))C. (P→Q)→(∧Q)D. P↔Q二、判断题（本大题共 20 分，共 10 小题，每小题 2 分）1. 集合 A={1,{2},3,4},B={a,b,{c}},判定下题的正确与错误：{1}∈A 2. 设 P、Q 为两个命题公式，若 P↓Q 的真值为 F，则 P 必为 1，Q 必为 0。3. 设代数系统 V=〈{a,b},*〉是半群，且 a*a=b,则 a*b=b*a。4. 设 A 是一个集合,如果 A 上的一个关系 R,满足自反性、对称性、传递性，则称 R 是 A 上的一个偏序关系，并把它记做“≤”；如果集合 A 上有偏序关系≤，则称 A 为偏序集，用序偶表示之。5. 连通图至少有一棵生成树。6. 判断该句是否为真命题。∀x(P→Q(x))∨R(e)),其中，P：3∅2。Q(x):x≤3。R（x）:x∅5。e:5 定义域：D={-2,3,6}.7. 设R={ <a,b>,<c,d> },S={ <b,e>,<d,c> }，则R°S={<a,e> ,<c,c>}。8. 若 P 的值为 1，Q 的值为 1，则(P→Q)∧(Q→P)的值为 0。9. 如果天气好，那么我去散步。10. 集合 A 的一个划分确定A 的元素间的一个等价关系。（）三、填空题（本大题共 20 分，共 4 小题，每小题 5 分）1. 在根树中，若从 Vi 到 Vj 可达，则称 Vi 是 Vj 的____________，Vj 是 Vi 的__________2. 设 A={a,b},B={1,2,3}，判断下列集合是否是 A 到 B 的函数。F_1={〈a,1〉,〈b,2〉},F_2={〈a,1〉,〈b,1〉}，F_3={〈a,1〉,〈a,2〉}, F_4={〈a,3〉}3. 判断以下集合是否为集合 A 的划分？A={ a,b,c,d,e,f }（1）S_1= {ϕ,{a,b,c,d},{f } }    （）（2）S_2= { {a,b},{c,d,e},{e,f } }  （）（3）S_3= { {a,b},{c,d},{e,f } }   （）（4）S_4= { {a},{b},{c},{d},{e},{f } （）（5）S_5= { {a,b,c,d,e,f } }    （）4. 判断下列命题正确与否：  令<A,≤ >为偏序集，且B⊆A 。  （1）若 b 为 B 的最大（最小）元，则 b 为 B 的极大（极小）元。（）  （2）若 B 有最大（最小）元，则 B 的最大（最小）元唯一。（）  （3）若 B 为有限集，则 B 的极大元、极小元恒存在。（）四、计算题（本大题共 20 分，共 2 小题，每小题 10 分）1. 试将下列公式化为主析取范式和主合取范式：p∨(┐p→(q∨(┐q→r)))2. 设全集合E={a，b，c，d，e}，A={a，d}，B={a，b，e}，C={b，d}，求下列集合：(1)A∩～B；（2）（A∩B）∪～C； （3）～A∪（B－C）；（4）ρ(A)∩ρ(B)五、简答题（本大题共 20 分，共 2 小题，每小题 10 分）1. 下列集合中，哪些是映射？并求映射的定义域和值域。（1）S_1={<1,<2,3≫,<2,<3,4≫,<3,<1,4≫,<4,<1,4≫}（2）S_2={<1,<2,3≫,<2,<3,4≫,<3,<3,2≫}（3）S_3={<1,<2,3≫,<1,<2,4≫,<2,<3,4≫（4）S_1={<1,<2,3≫,<2,<2,3≫,<3,<2,3≫2. 设 x={0,1,2},y={A,B,C},z={α,β,γ}，若有 f:x→Y,g:Y→Z，其中，f={<1,c>,<2,a>,<3,b>},g={a,γ>,<b,β>,<c,α>}，求〖(g°f)〗^(-1)和 f^(-1)°g^(-1)。答案：一、单项选择题（20 分，共 10 题，每小题 2 分）1. D 2. A 3. D 4. B 5. B 6. C 7. D 8. C 9. B 10. C 二、判断题（20 分，共 10 题，每小题 2 分）1. × 2. × 3. √ 4. √ 5. √ 6. × 7. √ 8. × 9. √ 10. √ 三、填空题（20 分，共 4 题，每小题 5 分）1. 参考答案：祖先；后代解题方案：评分标准： 2. 参考答案：F_1,F_2 是函数，F_3,F_4 不是函数。解题方案：若不强调是 A 到 B 的函数，则 F_4 是函数，其定义域为{a}。评分标准：3. 参考答案：（1）不是（2）不是（3）是（4）是最大划分（5）是最小划分解题方案：评分标准：我们看到对于一个给定集合, 划分不唯一。4. 参考答案：正确正确正确解题方案：评分标准：四、计算题（20 分，共 2 题，每小题 10 分）1. 参考答案：p∨(┐p→(q∨ (┐q→r)))⇔p∨(p∨(q∨ (q∨r)))⇔p∨q∨r(主合取范式)