第 3 次作业一、单项选择题（本大题共 30 分，共 10 小题，每小题 3 分）1. 在完全 m 叉树中，若树叶数为 t，分枝点数为 i，则有（） 。A. (m-1)i<t-1B. (m-1)i>t-1C. (m-1)i=t-1D. (m-1)i≤t-12. 一棵有向树，如果恰有一个节点的入度为０，其余所有节点的入度都为１，则称为____________A. 根树 B. 普通树C. 树根D. 树节点3. n 个节点的无向完全图 Kn 的边数为_________________ 2. 参考答案：解题方案：评分标准： 3. 参考答案：设任意 a∈A,则(a,a)∈A×A,因为 A×A=B×B,有(a,a)∈B×B,故 a∈B,因此A⊆B.对任意 b∈B,有(b,b)∈B×B,则(b,b)∈A×A,于是 b∈A,因此 B⊆A,所以 A=B. 解题方案：在每一节后面的证明题,若不能应用本节给出的定理,一般要考虑用定义证明。评分标准： A. B. C. D. 4. 在集合 A={1,2,3,⋯，10},问下面定义的二元运算*关于集合 A 是不封闭的（ ）。A. x*y=max(x,y) B. x*y=min(x,y)C. x*y=GCD(x,y)D. x*y=x+y5. 下图的最小生成树是（）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. 函数 f：R×R→R，f()=（x+y）/2 是( )函数。A. 入射B. 满射C. 双射 D. 以上答案都不对 8. 设 C(x)：x 是国家选手，G(x)：x 是健壮的。命题“没有一个国家选手不是健壮的”可符号化为( )A. ¬(∀x)(C(x)⋀¬G(x)B. ¬(∀x)(C(x)→¬G(x)C. ¬(∃x)(C(x)⋀¬G(x)D. ¬(∃x)(C(x)→¬G(x)9. 一阶逻辑公式∀x(F(x,y)⋀G(y,z) )→∀zF(z,y)是（）A. 前束范式B. 封闭公式C. 永真式D. 永假式10. 设有一组权为 2，3，5，7，11，13，17，19，23，29，31 则构造的最优二叉树权值为____________A. 495B. 505C. 515D. 520二、判断题（本大题共 30 分，共 10 小题，每小题 3 分）1. 判断对错：集合{2,4,6，•••2n}是无限集（ ）2. 下列句子的说法是否正确。 谓词演算的推理方法，可以看作是命题演算推理方法的扩张。 3. N 为自然数集，N 上的运算*定义为：x*y=min{x,y}，其中 x,y∈N，则是独异点。4. 对于图 G 着色时，需最少颜色数称为着色数。5. 群<G,*>中，除幺元 e 外，可能有任何别的等幂元。6. P→(┐Q)是命题公式。7. 蕴含式(P→Q)∧(Q→R)⇒ P→R 是正确的。8. 因为 P∨┐P 重言式，所以(P∧S)∨┐(P∧S)也是重言式。9. 设集合 A={1,2,3}，I_A 是 A 上的恒等关系，则 I_A={,,}.10. 设 A={1,2,8,24,48}，则 A 上的整除关系是 A 上的偏序，不是一个全序. （ ）三、计算题（本大题共 10 分，共 2 小题，每小题 5 分）1. 设集合 A={1,2,3,4}，A 上的二元关系 R={(x,y)|x,y∈A,且 x≥y},求 R 的关系图与关系矩阵2. 试将公式 P∧（P→Q）化为析取范式和合取范式： 四、简答题（本大题共 12 分，共 2 小题，每小题 6 分）1. S=Q×Q，Q 为有理数集，为 S 上的二元运算，∀ 〈a,b〉,〈x,y〉∈S 有〈a,b〉* 〈x,y〉=〈ax,ay+b〉问 * 运算是否有幺元、零元？如果有，请指出，并求 S 中所有可逆元素的逆元。2. 构造公式┐（P→Q）∧Q 的真值表，并解释其结果。五、证明题（本大题共 18 分，共 3 小题，每小题 6 分）1. 证明：(∃x)A(x)→(∀x)B(x)=>(∀x)(A(x)→B(x))2. 符号化下列命题并证明。每个考生或者勤奋或者聪明，所有勤奋的人都将有所作为，但并非所有考生都将有所作为。所以，一定有些考生是聪明的。3. 设 A，B，C 为三个任意集合，试证明若 A×A=B×B，则 A=B；答案：一、单项选择题（30 分，共 10 题，每小题 3 分）1. C 2. A 3. D 4. D 5. D 6. B 7. B 8. C 9. C 10. B 二、判断题（30 分，共 10 题，每小题 3 分）1. √ 2. √ 3. √ 4. √ 5. × 6. × 7. √ 8. √ 9. √ 10. × 三、计算题（10 分，共 2 题，每小题 5 分）1. 参考答案：R={(x,y)│x,y∈A,且 x≥y}={(1,1),(2,1),(3,1),(4,1),(2,2),(3,2),(4,2),(3,3),(4,3),(4,4) R 的关系图如图 3-1 所示。解题方案：评分标准：2. 参考答案：┐（P∨Q）↔（P∧Q）=(﹁（P∨Q）→（P∧Q）)∧(（P∧Q）→┐（P∨Q）)(等值律)=(（P∨Q）∨（P∧Q）) ∧(┐（P∧Q）∨┐（P∨Q）) (蕴涵律)=（P∨Q）∧(┐P∨┐Q)      (分配律) 合取范式=(┐P∨P) ∨(┐P∨Q)∨(┐Q∧P)∨(┐Q∧Q)  (分配律)析取范式解题方案：评分标准：四、简答题（12 分，共 2 题，每小题 6 分）1. 参考答案：容易验证〈1,0〉为幺元，没有零元。当 a≠0 时，〈a,b〉的逆元为〈1/a,b/a〉解题方案：评分标准： 2. 参考答案：真值表 P QP→Q    ┐（P→Q） ┐（P→Q）∧Q0 00 11 0 1 11 0 01 0 00 1 01 0 0可见：┐（P→Q）∧Q 是恒假的。解题方案：评分标准：五、证明题（18 分，共 3 题，每小题 6 分）1. 参考答案：证明：间接证法(1)¬(∀x)(A(x)→B(x))P(附加条件)(2)(∃x)¬(A(x)→B(x))        T(1)E(3)¬(A(c)→B(c))         ES(2)(4)¬(¬A(c)∨B(c))          T(3)(5)A(c)∧¬B(c)           T(4)E(6)(∃x)A(x)             EG(5)(7)(∃x)A(x)→(∀x)B(x)        P(8)(∀x)B(x)            T(6),(7)I(9)B(c)US(8)(10)¬B(c)            T(5)I(11)B(c)∧¬B(c)         T(9),(10) 矛盾解题方案：评分标准：