华南师范大学网络学院

1、题型:判断题，共10道，5分一道;计算题，2道，10分一道；证明题，3道，10分一道。第一章集合小结1集合：集合是不加定义的数学概念，用公理化方 法进行研究。只有有限个元素的集合称为有限集，有 无限个元素的集合称为无限集。为了叙述 方便，定义（4的元素的个数 龙是有限集=龙是无限集心（或国）表示A中所含元素的“个 数”。集合表示法。（1）列举法（有限个元素）（2）描述法集合具有(1)无重复性：例如:a、= /M/0(2)无次序性：例如:,G 刈=b,a,dtc不含任何元素的集合称为空集 集合间的关系定义:设A、B为集合，如果集合A的元 素都是集合B的元素，则称A是B的子集， 表示为匚3若 龙且

2、召匚点, 则称A与B相等，记作；若应匚3且小研则称A是B的真子集， 记作虹日定理:空集是一切集合的子集。定义:集合A的全体子集构成的集合叫作A的幕集，记作或 W 表示为=(suj定理:设A为有限集，则1如果一个集合包含了所要讨论的每一个集 合，则称该集合为全集，记为（或占）.1.1.2集合的基本运算，借助集合并U，交3差集,补集 的运算可以构造出新的集合。定义刃门3 = *|工刃且我旧月占的差集 月13 = 力|工已用且汗隹缶）儿称为R的补集，记为或互，即-A=A=UA = xxeUB.xA）集合运算的主要算律 幂等律心ArA = A结合律（此司 rmrivrio交换律分配律同一律MCMACU

3、 = A零律AU = U日门/= /排中律矛盾律瑚=/ 吸收律 AJ(ACB)=AAC(AJB) = A摩根律0 LJ 8)=3门。n、6 =bjc=HV =歹双重否定律( 1.1.3有限集的计数含有有限个元素的集合称作有限集.设A 为有限集，A中的元素数通常记为雄定理设心为有限集，则网皿=网+同-3| .（证明略）推论设 A,B,C 为有限集，则练习1 设 A=a，b，c，a, a，b，试指出 下列论断是否正确？a仁A(2) aA (3) a cA(4)0 A (5)0 A (6) b A (7) TOC o 1-5 h z GOGb A (8) b A (9) a，b A (10)GOOa

4、，b gA (11) cgA(12)c A (13) c A (14) a，b，c AGOO解：(1) (2) (3) (5) (6) (8) (9) (10) (12) 正确；(4) (7) (11) (13) (14)错误。2对于任意集合A、B和C,下述论断是否正 确？（1）若AR，BcC，则AC；（2）若AgB，Bu。，则入C；（3）若 AuB，B:C，则 AeC； （4）若 AuB，BeC，则 A：C。 解：（1）正确；其余错误。 3设集合A的元素个数#A=55，试问（1）A有多少子集？（2）有多少个子集的元素个数为27？ 有 多少个子集的元素为28？（3）有多少个子集的元素个数为偶数

5、？解：（1）因为#A=55，所以A的幂集元素个 数为255,即有2仍个子集。（2）集合是元素的组合，其具有无序性， 因此含有27个元素的子集个数即从55个元 素任意取出27个元素的组合数，即为C 27 ；55同理，含有28个元素的子集个数为c 28。55（3）在二项式定理 C0 + C1 + C2+ . + C =2“ 中，奇数项和偶数项的和是相等的，因此C 0 + C 2 + + C 54 = 255 - 2 = 254。455证明对任意集合A、B、C，等式(A-B) u (A-C)=A成立的充要条件是AnBnC2.设A、B、C是全集U的三个子集，证明A - (B n C) = (A - C

6、) u (A - B)设A、B是全集U的二个子集，证明2 A U 2 B o 2 AU B 设A、B是全集U的二个子集，证明2 a n 2 b = 2 Anb证明：(1)必要性 设(A-B) u (A-C)=A，因 为(A-B)U (A-C)=( AcB)u ( AcC)=An (BjC )=An (町c)=A-(BnC)=A所以对任意xeA，有x B C，金 n故 A n B n C2。A, 有 xG金充分性设A n B n C=0，则任意xBnC，即x G殆C，即A u肉yc。于是(A-B) u (A-C)= An (昭c)=A。,、a -( b n c)=a n bhc=a n( b u

7、 c)(2) / = (A n B) u (A n C) = (A - B) u (A - C)/q 4-% u A或x u B即x u A u B对 Vx e 2A u 2B，有所以x e 2aub，即原式成立(a右 u A且x u B即x u A n B对 Vx e 2 a n 2b，有匚二所以x e 2Anb ,即2a n 2b u 2anb-jfex g AnBx g A且x g B对 Vx e 2AnB，有所以x e 2a p| 2b ,2 aAb g 2a q 2b综上所述,原式成立.5某学校举行运动会，有短跑、铅球和跳高 三个项目。而年级共有170人，已知有25 人参加3个项目，

8、有62人参加了至少2个 项目，参加比赛的总人次为200，试问有多 少人没有参加任何项目？解：设U为全集，A为参加短跑的人的集合;B为铅球的人的集合；C为跳高的人的集合;则#U=170， # （AnBnC） =25，# （AnB） +# （AnC） +# （CnB） -2# （AnBnC）=62， #A+#B+#C=200，所求为#（U-（A。BuC）= #U-#（A。BuC）=#U-（#A+#B+#C-#（AnB） -#（AnC）-#（CnB）+#（AnBnC）=170-（200-112+25）=57 人。7设P是集合A上的自反关系，则P是传递 且对称的充分必要条件是：对任意a, b, c e

9、 A， 当 a,b,e p 时有b,ce p，试证明。证明:如果p是传递且对称的,且p是集合A 上的自反美系，当,eP时有, a,c p即 G p如果p是集合A上的自反关系，且当a.b ,g p 时有 e p 9 则 v a.b ,e p 时有,e p 时有 ,e p (对称)，则即.是传递的.8 记/ = 1,2,3, ,299,300,(1)求能被5整除而不能被3或7整除的数 的个数。(2)求能被7整除而不能被3或5整除的数 的个数。解:设a,分别表示能被3,5,7整除的数357的集合，则300I”,300“.=100 , A = 5 = 60 , A =344300”如勺=15 = 20

10、，人 4300 Q 444 r如 A7l = K = 8，件3 A5 气| =300, ”丁=42,300 |.如气1=y=14，300 = 2，所以a n An a = a - a n a - a n a + a n a n a = 3457537A7 n 气 n a = a - a n a - a n a + a n a n a = 22575371059集合A具有3个元素，集合B具有4个元 素，问A到B可以定义多少种不同的单射？ 解：集合A中的3个元素，必须在B中取出 3个不同的元素来一一对应，即单射种数为P3 = 24 o10集合A具有4个元素，集合B具有3个 元素，问A到B可以定义多

11、少种不同的满 射？ 解：题意相当于A中4个元素去对应B中所 有的3个元素，即从A中先取2个元素和B 中1个元素对应，剩下二个元素任意对应B 中二个，所以满射种数为C2P3 = 36 o11集合入具有4个元素，集合B具有4个 元素，问A到B可以定义多少种不同的双 射？ 解：同2、3题一样，可知种数为尸广24。12在1到2000的所有整数中，能宜只能被2、3、5之一整除的数有多少个？解:A = 1,2,.,2000， B = 能被2整除的数，C = 能被3整除的数 D = 能被5整除的数，贝A = 2000,B = 2000: 2 = 1000，C 尸2000 : 3 = 666，|D| = 2

12、: 5 = 400，B A C尸2000: 6 = 333，|B A D尸2000: 10 = 200，C A D = 2000: 15 = 133，件 A C A D = 2000:30 = 66，所求为B U C U D- B A C - |B A D - |C A D + 2|B A C A D| =B + C + |D| - 21B A C - 21B A D - 21C A D + 3lB A C A D=1000 + 666 + 400 - 666 - 400 - 266 +198 = 93213 一年级有100名学生，部分参加三科竞 赛，其中参加数学竞赛的有35人，参加物 理竞赛

13、的有43人，参加化学竞赛的有38人， 仅参加两科的有20人，三科都参加的有10 人，问没有参加任何一科竞赛的学生有多少？解 :4 = 一年纪所有学生，B = 参加数学竞赛的学生9C = 参加物理竞赛的学生 D = 参加化学竞赛的学生， 贝U |A = 100, B 35 9 |C| = 43, Z) = 38 ,件 Cl C Cl q = 1。I仅参加两科的学生I=|5nq+pnD|+|cnD|-3|BncnD| 所以 |Bnc|+|Bnr|+|cnz)|=5o|没有参加竟塞的学生| = |A|-pUCUD|= |A|-p|+|D|+|C|-(|Bnq+|5nD|+|cnD|)+pncnD|=

14、 100-(35 + 43 + 38-50 + 10) = 24第二章代数系统小结:定义：A T A上的映射称为一元运算，AX A t A上的映射称为运算Jk运算律: 幕等律;吸收律。 特殊元:二元运算，因此运算是特殊的映射。二元运算满足两个特点：A中 任两个元素均可运算且运算结果唯一。包括对于一个二元运算的运算律：交换律、结合律以及 一个二元运算对另外一个二元运算的运算律：分配律及 包括单位元、零元以及逆元并了解其唯一性，逆元的性质代数系统、子代数与积代数定义：集合G及G上的若干个运算构成的系统 称为代数系统。子代数：代数系统中集合的字集若对代数系统的运算仍封闭则称子集与运算构成的代数系统V

15、为原代数系统的子代数。积代数：两代数系统中两集合的笛卡儿乘积及定义新运算。： x , y 。 x , y = x。尤，1122112y。y 构成的代数系统。向态与同构定义：同态是一种特殊的映射，其保持两代数系统间的运算: 平(a。b)=甲(a)。甲(b)。同构的1定义及证诚：平是V到V的同态，若甲是双射，则称V121与V同构，记为k兰V。群21 2群的定义、交换群与循环群：群是满足三个条件的代数系统：满足结合律、 有单位元以及任一元素都有逆元。交换群是满足交换律的群。循环群是任 一元素都可以表示成a(k e Z)的群。群的性质：1、a。x =。有唯一解尤=a-1。b, y。a = b有唯一解

16、= b。a-1；2、消去律：a。b = a。c n b = c, b。a = c。a n b = c;3、(a。b) -1 = b -1。a -1是群，非空丑c G，也是群，则称v H,。是v G,。的子群。子群的充要条件是：对Vx, y e H有x。y-1 e H。群的同态：保持两个群之间的运算的映射：中(a 1 b) *(a)。2 (b)。称K = a|中(a) = e2为中的核。格、布尔代数：定义：格是含两个二元运算V、的代数系统:V、都满足交换律、 结合律，并且V和满足吸收律。格格与偏序集：利用格可定义偏序集，给一个偏序集可定义一个格，其中：V= v x, y | x, y e L且x

17、 v y = y性质：1、a b, c d n a v c b v d, a c b d;2、a v (b c) (a v b) (a v c),(a b) v (a c) a (b v c);3、a c n a v (b c) (a v b) c布尔代数基本定义：含有三个运算。、。2、。3、满足四个条件的代数系统：。、。可交换；。、。互可分配;。、。有单位元e ,e ； Va e 8有12121212a。(。(a) = e , a。(。(a) = e。132231基本运算：满足10条运算律。布尔表达式简介：由8中任何元素、任何变元及有限次V、八、-、运算生成的符号串。练习1 设 是格，a,b

18、, c e L，若 a b c 试证明a/b - b /c证明：因为a罚，所以% = b；因为队c,所 W Z? a c = Z? 因此 av b = b /c设是格，a,b,c,d e L ,试证明(1 A /?) V(C A /) (1 V C)A (/? V d)证明：(1 A/?) V (c A/) = (a a/?) vc a(Z ) v d, 而 由于有(a 展)VC Vavc, a/bb(a/b)vd bvd 9 所以( A Z?) V (c A J) (J V c) A (Z? v d)设。：Z2 Z,xo y = X+ y-2 (其中+，-分别是 普通加法和普通乘法)，验证

19、是否 是群。所以解：群必须满足三个条件：结合律,有单位 元，每一元素都有逆元.设有x,y,zeZ (xoy)oz = (x+y2) + z2 = xo(yoz) 所以VZ,。满足 结合律；对VxeZ，若。是单位元，则 xo, = x + .-2 = x所以 = 2即单位元存在；对楫寥， 若y是其逆元，则 xy-x+y-l-yx-y + x- l- e- l，即 y = 4-x 每一元素都有逆元，因此是群。Q为有理数集，Q上定义运算为：*ab = a + b-ab 9 求：（1） 的单位元0*（2） *中元素的逆元（若存在逆元） 灯,* a解：（1）因为若e是单位元，则a*e = a + eae

20、 = a解得e = 0（2） ab-a-b-ab = e = 0解得人= 。Da-15 Z为整数集，Z上定义乘法为： .ab = a + 2 + b 9 试证：z,是交换群。证明:a*e a + 2 + e a所以e = 2 即单位.元；（a*b） + 2 + c a + b + c + 2a（b*c） = a + 2 + （b*c） = a + b + c + 2满足结 口律；对V。b = a + 2 + b = e = -2得 a-i = b = -4 - a 即任意元素都有逆元；Qb=a+2+b=b。 满足交换律。所以z,是群。第三章图论小结设A、B为集合，则称 (a,) a e A,b

21、 e B为A、B的无序积，记为A&B,由定义知: A&B=B&A一个无向图G是一个二元组，即G =,其中v = v1,v2，,v是非空集合，称为G的顶 点集，V中元素称为顶点或结点； E = e1,乌,e 是无序积V&V的一个多重 子集(元素可以重复出现的集合)，称E为 G的边集,E中的元素称为无向边或简称边。设e = (v ,v )是无向图G的边，则称结点v ,vi ji j是邻接的，称边e关联结点vi (v )。定理1 (握手定理) 图的结点，则设 vv2,，vn 是(m，n)z deg(v ) = 2mii=1不含环及平行边的图称为简单图，任意两个 结点都有边相连的简单图称为完全图。I1

22、TJ若r中的所有边匕,匕互不相同，则称r 为简单通路。若回路中所有的边互不相同， 则称此回路为简单回路。若通路的所有顶点七,七,匕互不相同（从 而所有的边互不相同），则称此通路为初级 通路，如果初级通路的长度大于2,且 %=匕，则称r为初级回路。定义5设G =为无向图，若它的任 意两个不同结点之间都存在通路，则称G是 连通的。一个有向图D是一个二元组D =，其 中（1）集合V K，称为D的顶点集，V中 元素为顶点；（2）E是vxV的多重子集，其元素为有 向边。设D =为一有向图，u作为边的始点 j的次数之和为七的出度，记作deg+(u ),作为边的终点的次数之和为u的入度；记作jdeg (uj

23、), uj 的度数deg(%) = deg +(Uj) + deg (uj)称度数为0的顶点为孤立点。设u1,U2，,匕是(m,n)有向图D的结点，则i=1 de%(叩= deg_(匕)土 i=1iirJ若有向通路(回路)r的所有有向边互不 相同，则称r为D的简单有向通路(回路)。若有向通路r的所有结点互不相同，则称r 为D的初级有向通路。若除了 r的起点和终 点相同外，其它的结点互不相同，则称r为 D的初级有向回路。 TOC o 1-5 h z 设u ,u，,u是无向图G的所有结点，则称 12 n矩阵A = (a) nxn为G的邻接矩阵，其中a为结点u ,u之间的边数(i壬j)，当(u ,u

24、 )是环i ji i时，a = 2，否则a = 0。设u ,u ,u是简单iiii12 n图G的n个结点，则称矩阵c = (c )为G 的连接矩阵，其中y心J1,若V., v连接 七=|0,若V： v不连接I i j设图G =是无环的，其中 TOC o 1-5 h z V = v ,v，,v , E = e ,e ,e ，令 12 n12 n1,若e.关联v.气=。，若e不关联vl ji则称矩阵M =(叩心为G的关联矩阵。设v ,v，,v是有向图D的结点，则称矩阵 12 nA = (q)”n为D的邻接矩阵，其中a是以的为 始点，二为终点的边的条数。设v1，%,.,vn是简单有向图D的结点，则称

25、P=(p )n x n是、的可达矩阵，其中1,若v.可达v.%0,若v不可达vI ij设D =是无环有向图，V = Vi，V，V )，E = e，e，e ) 令mij1,若v,是匕的始点 =2)阶简单图G的每一对不 邻接的结点度数之和都大于或等于n-1，则G中存在哈密尔顿通路.(2)设n (n3)阶简单图G的每一对不 邻接的结点度数之和都大于或等于n，则G 中存在哈密尔顿回路，即G是哈密尔顿图。不包含回路的连通图称为树，记为T.I1TJ性质1设七,七是T的两个不同结点，则连 接七,七有且仅有一条通路，而且这条通路是 初级通路.性质2设V , v是T的两个结点.如果V , V不 1212邻接，则

26、在T中添加边气,v2）后所得的图有 且仅有一条回路，而且这条回路是初级回路.性质3从树T中删除任意一条边后所得的图是不连通的.liiJ性质4设T是（m，n）树，则m=n-1.性质5设树T的结点数为n （n2），则T 至少有两片树叶.练习1、设树T有6片树叶，3个二度结点，其余 都是4度结点，求4度结点的个数。解：设4度结点的个数为x,边数为y,则2 j = 6 + 6 + 4 尤,且 T是树，有j +1 =6 + 3 + x, 解 得 x=2.2设简单图G共有9个结点，其中6个结点 的度数为3,其余三个结点的度数都小于3, 问G至多有几条边。解：设简单图G有x条边，结点的度数之和 为边数的两倍

27、，因此2x 6 x 3 + 3 x 3 = 27，即x A (12)Aa(AvB) A (13)同一律 Av F (14)ATA (15)零律 AwT oT (16)A八 F。F (17)排中律AvToT (18)矛盾律AaTo F (19)蕴涵等值式A BoTvB (20)等价等值式 A B o (A t B) a (B t A) (21)假言易位 A t B o -B tA (22)等价否定等值式AB o A .-B (23)归谬论(A t B) a (A -t -B) o -A ( 24 )设(A)是含命题A的命题公式，A o B , 则可用B置换(A)中的A，得(B) .则(A) o

28、(B).若(A1 a A2 a -a A) t B为重言式，则称A,A,：,A?推出结论B的推理正确，B是A1, A,. . .,An的逻辑结论或有效结论。推理定律(重言蕴涵式)A n (A v 8)附加A a B n A化简At B, AnB假言推理A t B, B n-A 拒取式A v B, A n B析取三段论A t B, B t C n (A t C)假言三段论A t B, C T D, A v C n B v D 构造性二难A,B n A a B合取引入简单命题分解成J个体同)捐独立存在的客体谓词 刻画个体词的性质或个体词之间关系的词由一个谓词，一些个体变项组成的表达式 称为简单命题函数(简称命题函数)。全称量词：用符号V表示对个体域里的 所有个体，VxF (x)表示个体域里的所有个体 都有性质F；存在量词：用符号3表示存在个体域里 的个体，BxF(x)表示存在个体域里的个体具 有性质F。设A,B为任两个谓词公式，若A - B为永 真式，则称A与B是等值的，记作Ao B.量词否定等值式VxA(x) o 3xA(x)3xA(x) o VxA(x)I三|=|量词辖域收缩与扩张等值式: Vx