吉林大学2007级离散数学II试题(A)

第 1 页 共 6 页西南科技大学2006——2007学年第2学期《离散数学J 》期末考试试卷（A 卷）一、解：图（1）不能一笔画出，（1分）因为图（1）中奇度数顶点数为4。

（2分）图（2）能画出，比如：v3-v1-v2-v5-v4-v2-v3-v4。

(3分)二、解：图（1）存在哈密尔顿回路，比如：v1-v2-v3-v4-v1。

（3分）图（2）不存在哈密尔顿回路，（1分）因为，取V '={v1,v3}，则连通分支数w(G-V ')＝4＞|V '|＝2，因而该图不是哈密尔顿图。

(2分) 三、（4分）四、解：由握手定理有：()12deg ni i m v ==∑ （2分）故： 21×2 ＝ 12×3＋(n-12)×2n=15 （1分） 所以，G 的顶点数为15。

（1分）课程代码 1 4 3 1 4 0 32命题单位计算机科学与技术学院软件教研室西南科技大学2006——2007学年第2学期《离散数学J》期末考试试卷（A卷）五、解：最优二元树参考如下图：（4分）W(T)＝3×3＋4×3＋5×3＋6×3＋12×1＝66 （1分）六、解：前序遍历：＋÷－×＋a×bcde＋fg××hij （3分）中序遍历：a＋b×c×d－e÷f＋g＋h×i×j （3分）后序遍历：abc×＋d×e－fg＋÷hi×j×＋（3分）七、解：列公式(P→Q)∧(P→R)和P→(Q∧R)的真值表如下（真值表共8分，每项1分）：第 2 页共 6 页第 3 页 共 6 页西南科技大学2006——2007学年第2学期《离散数学J 》期末考试试卷（A 卷）P Q R (P→Q)∧(P→R)P→(Q∧R)0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 11 1 1因为真值表的最后两列完全相同，所以公式(P →Q)∧(P →R)和P →(Q ∧R)等值。

2006-2007学年第2学期2005级《离散数学2》期末考试试题(A卷)考试时间：2007年6月班级_______________________ 学号_____________________ 姓名_____________________请将答案写在答题纸上，写明题号，不必抄题，字迹工整、清晰；请在答题纸和试题纸上都写上你的班级，学号和姓名，交卷时请将试题纸、答题纸和草纸一并交上来。

一.综合体(30分，每题3分)1. 求( 1 3 5 ) (2 5 4 ) (3 4 )2. 只有两个生成元的循环群一定是有限循环群吗？并说明理由。

3. 有限循环群中是否一定存在周期与群的元数相等的元素？4. 下面哪个是域GF( 16)的真子域(A)GF (6) ;(B)GF ⑷;(C)GF(8);(D)GF(16)5. 有限布尔代数的元素个数必定是如下哪个形式？(A)2n;(B)n 2 ;(C)2 n;(D)4n.6. 下列代数系统(S, *)中，哪个是群？(A) S={0,1,3,5},* 是模7的乘法；(B) S是有理数集合，*运算是普通乘法；(C) S是整数集合，*是普通乘法；(D) S={1,3,4,9},* 是模11的乘法。

7. 设A={0,1,2,3,4},运算为模5加法，请给出A的所有子群。

8. n元恒等置换是奇置换还是偶置换？对换呢？9•请给出一个有余，但不是分配格的例子。

10.设R是模12的整数环，R={0,1,2,…,11},下面哪一个是极大理想：(A) 6R; (B)2R; (C)4R; (D)8R二.计算题(25分，每题5分)1. 计算分圆多项式①24(X).2. 设(Z,+)为整数加法群，(C*,??)为非零复数的乘法群，令f: n -i n ,是Z到C*中的同态映射，请求出f的同态核。

3. 在R上求出x+2除2X5+4X3+3X2+1所得的商式和余式。

4. 设G是3次对称群，H是由I和(13)作成的子群，求H得所有右陪集。

离散数学试题（A卷答案）一、（10分）某项工作需要派A、B、C和D 4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？(1)若A去，则C和D中要去1个人；(2)B和C不能都去；(3)若C去，则D留下。

解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。

则根据题意应有：A→C⊕D，⌝(B ∧C)，C→⌝D必须同时成立。

因此(A→C⊕D)∧⌝(B∧C)∧(C→⌝D)⇔(⌝A∨(C∧⌝ D)∨(⌝C∧D))∧(⌝B∨⌝C)∧(⌝C∨⌝D)⇔(⌝A∨(C∧⌝ D)∨(⌝C∧D))∧((⌝B∧⌝C)∨(⌝B∧⌝D)∨⌝C∨(⌝C∧⌝D))⇔(⌝A∧⌝B∧⌝C)∨(⌝A∧⌝B∧⌝D)∨(⌝A∧⌝C)∨(⌝A∧⌝C∧⌝D)∨(C∧⌝ D∧⌝B∧⌝C)∨(C∧⌝ D∧⌝B∧⌝D)∨(C∧⌝ D∧⌝C)∨(C∧⌝ D∧⌝C∧⌝D)∨(⌝C∧D∧⌝B∧⌝C)∨(⌝C∧D∧⌝B∧⌝D)∨(⌝C∧D∧⌝C)∨(⌝C∧D∧⌝C∧⌝D)⇔F∨F∨(⌝A∧⌝C)∨F∨F∨(C∧⌝ D∧⌝B)∨F∨F∨(⌝C∧D∧⌝B)∨F∨(⌝C∧D)∨F⇔(⌝A∧⌝C)∨(⌝B∧C∧⌝ D)∨(⌝C∧D∧⌝B)∨(⌝C∧D)⇔(⌝A∧⌝C)∨(⌝B∧C∧⌝ D)∨(⌝C∧D)⇔T故有三种派法：B∧D，A∧C，A∧D。

二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。

解：论域：所有人的集合。

S(x)：x是专家；W(x)：x是工人；Y(x)：x是青年人；则推理化形式为：∀x(S(x)∧W(x))，∃x Y(x)∃x(S(x)∧Y(x))下面给出证明：(1)∃x Y(x) P(2)Y(c) T(1)，ES(3)∀x(S(x)∧W(x)) P(4)S( c)∧W( c) T(3)，US(5)S( c) T(4)，I(6)S( c)∧Y(c) T(2)(5)，I(7)∃x(S(x)∧Y(x)) T(6) ，EG三、（10分）设A、B和C是三个集合，则A⊂B⇒⌝(B⊂A)。

一、简答题（共20小题，每小题2分，共40分，不必证明，直接给出答案即可）1. 设S={a,b,c,d}，定义ρ(S)上的二元运算“－”，使对于任意A 、B ∈ρ(S)，A －B={x|x ∈A 且x ∉B}，问：该运算满足消去律吗？ρ(S)上存在幂等元吗？2. 所有的4元群都同构吗？所有的7元群都同构吗？3. 整区中是否存在零因子？整区中所有非零元素的乘法周期都相等吗？4. 设循环群G=(a)，|G|=24，则G 中是否存在周期为5的元素？是否存在8元子群？5. 设a ∈GF(27)且a ≠0，求6a 和a 26。

6. 在R 13求424-。

7. 设（G ，·）是群，请给出满足方程a ·b ·x ·c =1的解x ，其中：1是G 的单位元，a 、b 、c ∈G 。

8. 设G={e,a,b,c,d,f,g},（G ，·）是群，e 是G 的单位元，计算a ·b ·c ·d ·f ·g 等于多少？9. 设循环群G=(a)，H 是G 子群，则H 是正规子群吗？10. 写出模12剩余环的一个极大理想。

11. 域F 上的非0多项式f(x)有k （k 为非负整数）重根，则f(x)一定可约吗？12. 给出多项式x 5+5x 4+2x 3+3x+1的一个有理根。

13. 在R 2上给出两个多项式f(x)和g(x)，满足f(x)≡g(x)但f(x)≠g(x)。

14. 在R 0上，多项式6x 5+14x 4+7x 3+21x 2-35x+7是否是质式？15. 求分圆多项式之积：Φ1(x)Φ2(x)Φ3(x)Φ6(x)。

16. q 元有限域中的非零元素一定都是多项式x q-1-1的根吗？17. 设(L ，≤)是一个半序格，与其等价的代数格为(L,×,⊕)，设S ⊆ L 。

若（S ，≤）是（L ，≤）的半序子格，则(S,×,⊕)一定是(L, ×, ⊕)的代数子格吗？18. 设（L ，≤）是一个半序格，其对应的代数格为（L ，×，⊕），则一定有a×b=a 吗？19.有余格一定是有界格吗？20.设S={a,b,c,d}，请给出集合代数（ρ（S），∩，∪，ˉ，φ，S）的基底。

离散数学试题（A 卷答案）一、（10分）求(P ↓Q )→(P ∧⌝(Q ∨⌝R ))的主析取范式 解：(P ↓Q )→(P ∧⌝(Q ∨⌝R ))⇔⌝(⌝( P ∨Q ))∨(P ∧⌝Q ∧R ))⇔(P ∨Q )∨(P ∧⌝Q ∧R ))⇔(P ∨Q ∨P )∧(P ∨Q ∨⌝Q )∧(P ∨Q ∨R ) ⇔(P ∨Q )∧(P ∨Q ∨R )⇔(P ∨Q ∨(R ∧⌝R ))∧(P ∨Q ∨R ) ⇔(P ∨Q ∨R )∧(P ∨Q ∨⌝R )∧(P ∨Q ∨R ) ⇔0M ∧1M⇔2m ∨3m ∨4m ∨5m ∨6m ∨7m二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。

乙说：王教授不是上海人，是苏州人。

丙说：王教授既不是上海人，也不是杭州人。

王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。

试判断王教授是哪里人？解 设设P ：王教授是苏州人；Q ：王教授是上海人；R ：王教授是杭州人。

则根据题意应有： 甲：⌝P ∧Q 乙：⌝Q ∧P 丙：⌝Q ∧⌝R王教授只可能是其中一个城市的人或者3个城市都不是。

所以，丙至少说对了一半。

因此，可得甲或乙必有一人全错了。

又因为，若甲全错了，则有⌝Q ∧P ，因此，乙全对。

同理，乙全错则甲全对。

所以丙必是一对一错。

故王教授的话符号化为：((⌝P ∧Q )∧((Q ∧⌝R )∨(⌝Q ∧R )))∨((⌝Q ∧P )∧(⌝Q ∧R ))⇔(⌝P ∧Q ∧Q ∧⌝R )∨(⌝P ∧Q ∧⌝Q ∧R )∨(⌝Q ∧P ∧⌝Q ∧R ) ⇔(⌝P ∧Q ∧⌝R )∨(P ∧⌝Q ∧R ) ⇔⌝P ∧Q ∧⌝R ⇔T因此，王教授是上海人。

三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。

证明 设R 是非空集合A 上的二元关系，则由定理4.19知，tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。

一、1.（1 3 2）（4 5）;2.不一定。

因为无限循环群恰有两个生成元;3.一定;4.B;5.C;6.D;7.一共两个子群，一个是{0}，一个是A;8.偶置换,奇置换;9.A={1，2，4，5，20}，关系是整除;10.B;二、1.x8-x4+1;2.4Z;3.商式：2x4+ x3 + 2x2+ 4x+2;余式：2；4.{I,(1 3)},{(1 2)，（1 3 2）},{(2 3),(1 2 3)}5.0的周期是1；1的周期是6；2的周期是3；3的周期是2；4的周期是3；5的周期是6。

三、证明：如果它可约必为一次式与四次及以下因式乘积或二次式与三次及以下因式乘积的形式。

（1）在R2上3x5+5x2+1是x5+x2+1，而f(0)=f(1)=10，所以它在R2上无一次质因式；（2）在R2上的二次质因式只有x2+x+1，而x5+x2+1=x2（x+1）(x2+x+1)+1，所以它在R2上也无二次质因式，因此它在R2上不可约，从而在R0上不可约。

四、1)由C的定义知C?G2)设(G,*)的单位元为e，则有e A和e B，所以e=e*e C；3)任取x, y C，令x=a1*b1, y=a2*b2，则x*y= (a1*b1)*(a2*b2)，因为*满足结合律和交换律，所以有x*y= (a1* a2)*( b1*b2) C，故*在C上是封闭的。

4)任取c C，令x=a*b，则x-1=(a*b)-1= b-1*a-1= a-1*b-1C，故C中每个元素都有逆元素。

因此结论成立。

五、显然X 非空，如（0，0）属于X根据运算的定义，在X上封闭，且满足交换律与结合律，(X, )的单位元是(0,0)，任取(a,b) X，(a,b)的负元是(-a,-b)。

所以(X, )是交换群。

运算在X上封闭，且满足结合律，所以(X, )是半群。

任取(a1,b1)，(a2,b2) ，(a3,b3) X，有(a1,b1) ((a2,b2) (a3,b3))=(a1a2+a1a3,b1b2+b1b3)((a1,b1) (a2,b2)) ((a1,b1) (a3,b3))= (a1a2+a1a3,b1b2+b1b3)，再根据和满足交第 1 页共 2 页。

吉大离散数学试题及答案一、选择题1. 以下哪个选项不是离散数学中的基本概念？A. 集合B. 函数C. 微积分D. 关系答案：C2. 在集合论中，以下哪个操作不是基本的集合运算？A. 并集B. 交集C. 差集D. 微分答案：D3. 逻辑运算中的“与”操作，其结果为真当且仅当两个操作数都为真。

这个操作的符号是：A. ∧B. ∨C. ¬D. →答案：A二、填空题1. 一个集合的幂集包含该集合的所有_________。

答案：子集2. 如果函数f: A → B 是单射的，那么对于 A 中的任意两个不同的元素 a1 和 a2，f(a1) 和 f(a2) 在 B 中是_________的。

答案：不同的三、简答题1. 简述什么是图论中的“图”？答案：图是由顶点（或称为节点）和连接这些顶点的边组成的数学结构。

图可以是有向的或无向的，边可以是有权重的或无权重的。

2. 什么是逻辑中的“真值表”？答案：真值表是一种列出逻辑表达式中所有可能的真值组合及其结果的表格。

它用于展示逻辑表达式在不同输入值下的结果。

四、计算题1. 给定集合 A = {1, 2, 3} 和 B = {2, 3, 4}，请找出 A 和 B 的交集。

答案：A ∩ B = {2, 3}2. 假设有一个函数 f(x) = x^2，计算 f(-3) 和 f(3) 的值。

答案：f(-3) = 9，f(3) = 9五、论述题1. 论述离散数学在计算机科学中的应用。

答案：离散数学是计算机科学的基础，它提供了处理计算机科学问题所需的数学工具和理论。

例如，集合论是数据库理论的基础；图论在网络和算法设计中有着广泛应用；逻辑和布尔代数是计算机硬件设计和编程语言的基础。

2. 讨论命题逻辑和谓词逻辑的区别。

答案：命题逻辑关注简单命题及其逻辑关系，而谓词逻辑则引入了量词和变量，允许表达更复杂的逻辑关系。

命题逻辑使用逻辑连接词（如与、或、非等）来构建表达式，而谓词逻辑则使用量词（如全称量词∀和存在量词∃）来描述涉及个体的命题。

一、1.（1 3 2）（4 5）;2.不一定。

因为无限循环群恰有两个生成元;3.一定;4.B;5.C;6.D;7.一共两个子群，一个是{0}，一个是A;8.偶置换,奇置换;9.A={1，2，4，5，20}，关系是整除;10.B;二、1.x8-x4+1;2.4Z;3.商式：2x4+ x3 + 2x2+ 4x+2;余式：2；4.{I,(1 3)},{(1 2)，（1 3 2）},{(2 3),(1 2 3)}5.0的周期是1；1的周期是6；2的周期是3；3的周期是2；4的周期是3；5的周期是6。

三、证明：如果它可约必为一次式与四次及以下因式乘积或二次式与三次及以下因式乘积的形式。

（1）在R2上3x5+5x2+1是x5+x2+1，而f(0)=f(1)=10，所以它在R2上无一次质因式；（2）在R2上的二次质因式只有x2+x+1，而x5+x2+1=x2（x+1）(x2+x+1)+1，所以它在R2上也无二次质因式，因此它在R2上不可约，从而在R0上不可约。

四、1)由C的定义知C?G2)设(G,*)的单位元为e，则有e A和e B，所以e=e*e C；3)任取x, y C，令x=a1*b1, y=a2*b2，则x*y= (a1*b1)*(a2*b2)，因为*满足结合律和交换律，所以有x*y= (a1* a2)*( b1*b2) C，故*在C上是封闭的。

4)任取c C，令x=a*b，则x-1=(a*b)-1= b-1*a-1= a-1*b-1C，故C中每个元素都有逆元素。

因此结论成立。

五、显然X 非空，如（0，0）属于X根据运算的定义，在X上封闭，且满足交换律与结合律，(X, )的单位元是(0,0)，任取(a,b) X，(a,b)的负元是(-a,-b)。

所以(X, )是交换群。

运算在X上封闭，且满足结合律，所以(X, )是半群。

任取(a1,b1)，(a2,b2) ，(a3,b3) X，有(a1,b1) ((a2,b2) (a3,b3))=(a1a2+a1a3,b1b2+b1b3)((a1,b1) (a2,b2)) ((a1,b1) (a3,b3))= (a1a2+a1a3,b1b2+b1b3)，再根据和满足交换律，可得对满足分配律。

一、综合题（每题3分，共30分）1．有限群中消去律是否成立，无限群呢？2．设M={1,2,3,4,5,6,7,8}。

已知(1 2 3)=(1 2)(a b)(1 3)(c d)，试求对换(a b)和(cd)。

3．设（L ，×，⊕）和（S ，，）是两个格，若f 是L 到S 的同态映射，则f一定是保序映射么？如果g 是L 到S 的保序映射，g 一定是同态映射么？4．设1H 和2H 都是有限群G 的正规子群。

若21H H ，则12H G H G 是否成立？5．3x 1 (mod 14)有解吗？若有，请给出该方程的解。

6．设R 是一个环，S 是R 的子环。

若R 有壹，则S 是否一定有壹？若S 有壹，则R 是否一定有壹？7．设D 是集合S 上的整除关系，以下部分序集是否是格？(1)S={2, 4, 6, 8, 12, 24, 48}(2)S={2, 3, 6, 12, 24, 36}8．循环群的子群是否一定是正规子群？无限循环群的子群是否一定是无限循环群？9．设f 是代数系统(A, *)到(B, )的同态映射，如果(A, *)半群，则同态象(f(A), )也一定是半群么？如果f 是满射，(B, )也一定是半群么？10．设L 是格，L S 。

如果),(S 是),(L 的子格，则),,(S 也一定是),,(L 的子格吗？二、计算题（每题5分，共20分）1．设G 是4次对称群，H 是由{I, (1 2), (3 4), (1 2)(3 4)}作成的子群，求H 的所有右陪集。

2．设G={1，5，7，11}，(G , 12)为群，其中12为模12的乘法，请给出所有元素的周期和逆元，以及（G , 12）的真子群的个数。

3．在R 7中求多项式x+3除3x 5-2x 4+4x 3-5x+1的商式和余式。

4．设Z 18={0, 1, 2,…, 17}，(Z 18, 18, 18)是模18的整数环，18和18分别为模18的加法和乘法。

离散数学考试试题(A 卷及答案）一、证明题（10分） 1) (P ∧Q ∧AC )∧(A P ∨Q ∨C ) (A ∧(P Q ))C 。

P<->Q=(p->Q)合取（Q->p ）证明: (P ∧Q ∧A C )∧(A P ∨Q ∨C ) (P ∨Q ∨A ∨C )∧(A ∨P ∨Q ∨C )((P ∨Q ∨A )∧(A ∨P ∨Q ))∨C 反用分配律 ((P ∧Q ∧A )∨(A ∧P ∧Q ))∨C( A ∧((P ∧Q )∨(P ∧Q )))∨C 再反用分配律( A ∧(PQ ))∨C(A ∧(P Q ))C 2) (PQ)PQ 。

证明：(P Q)((P ∧Q))(P ∨Q))PQ 。

二、分别用真值表法和公式法求(P (Q ∨R ))∧(P ∨(Q R ))的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15分）。

主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。

主析取范式可由 析取范式经等值演算法算得。

证明：公式法：因为(P (Q ∨R ))∧(P ∨(Q R ))(P ∨Q ∨R )∧(P ∨(Q ∧R )∨(Q ∧R ))(P ∨Q ∨R )∧(((P ∨Q )∧(P ∨R ))∨(Q ∧R ))分配律 (P ∨Q ∨R )∧(P ∨Q ∨Q )∧(P ∨Q ∨R )∧(P ∨R ∨Q )∧(P ∨R ∨R )(P ∨Q ∨R )∧(P ∨Q ∨R )∧(P ∨Q ∨R )4M ∧5M ∧6M 使（非P 析取Q 析取R ）为0所赋真值，即100，二进制为4 0m ∨1m ∨2m ∨3m ∨7m所以，公式(P (Q ∨R ))∧(P ∨(Q R ))为可满足式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。

真值表法：P Q RQRP(Q∨R)P∨(Q R)(P(Q∨R))∧(P∨(Q R ))0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 1111111111111111111111为000、001、010、011、111：成假赋值为：100、101、110。