离散数学王元元课后答案第五章

第十一章 群、环、域

11.1 半群

内容提要

11.1.1 半群及独异点

定义 11.1 称代数结构为半群（semigroups），如果 ? 运算满足结合律．当半群含有关于 ? 运算的么元，则称它为独异点（monoid），或含么半群．

定理11.1 设为一半群,那么

（1）的任一子代数都是半群，称为的子半群．

（2）若独异点的子代数含有么元e,那么它必为一独异点,称为的子独异点．

定理11.2 设,是半群,h为S到S’的同态,这时称h为半群同态．对半群同态有

（1）同态象为一半群．

（2）当为独异点时，则为一独异点.

定理11.3 设为一半群,那麽

SS

（1）为一半群，这里S为S上所有一元函数的集合，○ 为函数的合成运算．

S

（2）存在S到S的半群同态．

11.1.2 自由独异点

定义 11.2 称独异点为自由独异点（free monoid）,如果有A?S使得 （1）e?A．

（2）对任意u?S，x?A,u?x ? e . 自由独异点（free monoid）,如果有A?S使得 （3）对任意u,v?S，x,y?A,若u?x = v?y,那么u = v,x = y．

（4） S由A

第九章 特 殊 图

9.1 二分图

内容提要

9.1.1 二分图的基本概念

定义9.1 无向图G = 称为二分图（bipartite graph），如果有非空集合X，Y使X∪Y = V，X∩Y = ?，且对每一e?E，?(e) = (x, y)，x?X，y?Y。此时常用表示二分图G。若对X中任一x及Y中任一y恰有一边e?E，使?(e) = (x, y), 则称G为完全二分图（complete bipartite graph）。当?X? = m，?Y? = n时，完全二分图G记为Km,n。

定理9.1 无向图G为二分图的充分必要条件是，G至少有两个顶点,且其所有回路的长度均为偶数。

9.1.2 匹配

定义9.2 设G = 为二分图，M?E。称M为G的一个匹配（matching），如果M中任何两条边都没有公共端点。G的所有匹配中边数最多的匹配称为最大匹配（maximal matching）。如果X(Y)中任一顶点均为匹配M中边的端点，那么称M为X(Y)-完全匹配(perfect matching)。若M既是X-完全匹配又是Y-完全匹配，则称M为G的完全匹配。 定

第四篇 抽象代数

第十章 代数结构通论

10.1 代数结构 内容提要

10.1.1代数结构的意义

定义10.1 称 为集合S上的n元运算（operaters），如果 为Sn到S的一个函数。以下 常用以表示二元运算, ?(x,y)常记为x?y；?常用以表示一元运算。对二元运算，’: 称 运算满足结合律，若 xyz(x,y,z?S→x? (y? z) = (x?y) ?z) 称 运算满足交换律，若 xy(x,y?S→x?y= y?x) 称 运算对 ’ 运算满足分配律，若 xyz(x,y,z?S→x?(y?’z) = (x?y) ?’ (x?z))

定义10.2 代数结构（algebra structures）是由以下三个部分组成的数学结构： （1）非空集合S，称为代数结构的载体。 （2）载体S上的若干运算。

（3）一组刻划载体上各运算所满足性质的公理。 代数结构常用一个多元序组来表示，其中 S是载体，?，，…为各种运算。有时为了强调S有某些元素地位

5.10 假设对指令Cache的访问占全部访问的75%；而对数据Cache的访问占全部访问的25%。Cache的命中时间为1个时钟周期，失效开销为50 个时钟周期，在混合Cache中一次load或store操作访问Cache的命中时间都要增加一个时钟周期，32KB的指令Cache的失效率为0.39%，32KB的数据Cache的失效率为4.82%，64KB的混合Cache的失效率为1.35%。又假设采用写直达策略，且有一个写缓冲器，并且忽略写缓冲器引起的等待。试问指令Cache和数据Cache容量均为32KB的分离Cache和容量为64KB的混合Cache相比，哪种Cache的失效率更低？两种情况下平均访存时间各是多少？

解：（1）根据题意，约75%的访存为取指令。 因此，分离Cache的总体失效率为：（75%×0.15%）＋（25%×3.77%）＝1.055%； 容量为128KB的混合Cache的失效率略低一些，只有0.95%。 （2）平均访存时间公式可以分为指令访问和数据访问两部分：

平均访存时间＝指令所占的百分比×（读命中时间＋读失效率×失效开销）＋ 数据所占的百分比×（数据命中时间

习题3.7

1. 列出关系{?a，b，c，d?|a，b，c，d?Z且a?b?c?d?6}中所有有序4元解 {?a，b，c，d?|a，b，c，d?Z且a?b?c?d?6}

??组。

?{?1,1,1,6?,?1,1,6,1?,?1,6,1,1?,?6,1,1,1?,?1,1,2,3?,?1,1,3,2?,?1,2,1,3?,?1,3,1,2?,

?1,2,3,1?,?1,3,2,1?,?2,3,1,1?,?3,2,1,1?,?2,1,3,1?,?3,1,2,1?,?2,1,1,3?,?3,1,1,2?

2. 列出二维表3.18所表示的多元关系中所有5元组。假设不增加新的5元组，找出二维表3.18所有的主键码。

表3.18 航班信息

航空公司 Nadir Acme Acme Acme Nadir Acme Nadir

解 略

3. 当施用投影运算?2,3,5到有序5元组?a，b，c，d?时你能得到什么？

解 略

4. 哪个投影运算用于除去一个6元组的第一、第二和第四个分量？

解 略

5. 给出分别施用投影运算?1,2,4和选择运算?航空公司＝Nadir到二维表3.18以后得到的表。 解 对航班信息二维表进行投影运算?2,3,5

§1.1 命题和逻辑连接词

习题1.1

1. 下列哪些语句是命题，在是命题的语句中，哪些是真命题，哪些是假命题，哪些命题的真值现在还不知道？

（1）中国有四大发明。

（2）你喜欢计算机吗？ （3）地球上海洋的面积比陆地的面积大。 （4）请回答这个问题！ （5）632=+。

（6）107<+x 。 （7）园的面积等于半径的平方乘以圆周率。 （8）只有6是偶数，3才能是2的倍数。

（9）若y x =，则z y z x +=+。

（10）外星人是不存在的。 （11）2020年元旦下大雪。

（12）如果311=+，则血就不是红的。 解 是真命题的有：（1）、（3）、(7)、 (9) 、（12） ；是假命题的有：（5）、 (8) ；是命题但真值现在不知道的有： (10)、 (11)；不是命题的有：（2）、（4）、（6）。

2. 令p 、q 为如下简单命题：p ：气温在零度以下。q ：正在下雪。用p 、q 和逻辑联接词符号化下列复合命题。

（1）气温在零度以下且正在下雪。

（2）气温在零度以下，但不在下雪。

（3）气温不在零度以下，也不在下雪。

（4）也许在下雪，也许气温在零度以下，也许既下雪气温又在零度以下。

（5）若气温在零度以下，那一定在下雪。

（6）也许气温在零度以下，也许在下雪，但如果气温在零度以上就不下雪。 （7）气温在零度以下是下雪的充分必要条件。

解 （1

第五章 习题与思考题

◆◆ 习题 5-1 图P5－1是集成运放BG303偏置电路的示意图，已知VCC=VEE=15V，偏置电阻R=1MΩ(需外接)。设各三极管的β均足够大，试估算基准电流IREF以及输入级放大管的电流IC1、IC2。 解：VT4、VT3、R组成镜像电流源，流过R的基准电流IREF为： IREF?VCC?VEE?UBE15?15?0.7??A?29.3?A

R1 IC3?IREF11?2足够大??????IC3?IREF?29.3?A

?129.3IC3??A?14.7?A 22 VT1、VT2为差分对管，则有： IC1?IC2?本题的意图是理解镜像电流源的工作原理和估算方法。

◆◆ 习题 5-2 图P5－2是集成比较器BG307偏置电路的示意图。已知VEE=6V，R5=85Ω，R6=68Ω，R7=1.7kΩ。设三极管的β足够大，试问VT1、VT2的静态电流IC1、IC2为多大？ 解：

VT5、VT6为核心组成比例电流源，其基准电流IR7为：

IR7?0?2UBE?(?VEE)0?2?0.7?6?A?2.6mA

R6?R768?1700R6R68IC6?6IR7?(?2

第十章

一、选择题

1.某企业计划要求本月每万元产值能源消耗率指标比去年同期下降5%，实际降低了2.5%，则该项计划的计划完成百分比为（ D ）。

A. 50.0% B 97.4% C. 97.6% D. 102.6% 2.下列指标中属于强度相对指标的是（ A ）。 A.产值利润率 B.基尼系数 C.恩格尔系数 D.人均消费支出 3. 下列指标中属于狭义指数的是（ A ）。 A.某地区本月社会商品零售量为上月的110% B.某地区本月能源消耗总量为上月的110% C.某地区本月居民收入总额为上月的110% D.某地区本月居民生活用水价格为上月的110%

4.若为了纯粹反映价格变化而不受销售量结构变动的影响，计算价格总指数时应该选择的计算公式是（ A ）。

A.拉氏指数 B.帕氏指数 C.马埃指数 D.理想指数

5. 与帕氏质量指标综合指数之间存在变形关系的调和平均指数的权数应是（ B ）。 A. q0p0B. q1p1 C. q1p0 D. q0p1

6. 为了说明两个地区居民消费水平之间的差异程度，有关指数的计算最好采用（ C

简答题

5.1 什么是简谐运动？说明下列运动是否是简谐运动？ （1）活塞的往复运动； （2）皮球在硬地上的跳动；

（3）一小球在半径很大的光滑凹球面底部的来回滑动，且经过的弧线很短； （4）锥摆的运动。

答：质点的简谐振动一定要有平衡位置，以平衡位置作为坐标原点，如果以x表示质点偏离平衡位置的位移，质点所受合外力一定具有F??kx的形式。

（１）活塞的往复运动不是简谐运动，因为活塞受力的方向和它的位移是同一方向，任一时刻所受的合外力不具有F??kx的形式，所以活塞的往复运动是简谐运动。

（２）皮球在硬地上的跳动不是简谐运动，因为忽略空气阻力，皮球在上升和下落阶段，始终受到竖直向下的重力的作用，任一时刻所受的合外力不具有F??kx的形式，所以皮球的运动不是简谐运动。

（３）一小球在半径很大的光滑凹球面底部的来回滑动，且经过的弧线很短是简谐运动。符合简谐运动的定义。

（４）锥摆的运动不是简谐运动，此时锥摆受到重力和绳的拉力的作用，这两个力的合力的大小为恒量，而方向在不断的改变，任一时刻所受的合外力不具有F??kx的形式，所以锥摆的运动不是简谐运动。

5.2（1）试述相位和初相的意义，如何确定初相？

（2）在简谐振动表达式x?Acos(?t

习题5—1(A)

1．判断下列叙述是否正确？并说明理由：

（1）如果函数)(x f 仅在区间],[b a 上有界，它在],[b a 上未必可积，要使其可积，它在

],[b a 上必须连续；

（2）如果积分?b

a x x f d )(（

b a <）存在，那么n

a b i n a b a f x x f n i n b a --+=∑?=∞→)(lim d )(1； （3）性质5也常称为积分不等式，利用它（包括推论）结合第三章的有关知识，可以估计积分的值、判定积分的符号，也可证明关于定积分的某些不等式；

（4）定积分的中值定理是一个非常重要的定理，利用它能去掉积分号，同时该“中值”)(ξf 还是被积函数在积分区间上的平均值.

答：（1）前者正确．如狄利克雷函数???∈∈=c Q

x Q x x D ，，，01)(在区间][b a ，（其中a b >）上有界，但是它在区间][b a ，上不可积，事实上：将][b a ，任意分成n 个小区间][1i i x x ，-

)21(n i ，，， =，

（其中b x a x n ==，0）记第i 个小区间长度为i x ?，先在][1i i x x ，-上取i ξ为有理数，则a b x x D n i i n i i i -=?=?∑∑=→=