第六章集合代数
1. 集合，相等，（真）包含，子集，空集，全集，幂集
2. 交，并，（相对和绝对）补，对称差，广义交，广义并
3. 文氏图，有穷集计数问题
4. 集合恒等式（等幂律，交换律，结合律，分配律，德·摩根律，吸收律，零律，同一
律，排中律，矛盾律，余补律，双重否定律，补交转换律等）
学习要求
1. 熟练掌握集合的子集、相等、空集、全集、幂集等概念及其符号化表示
2. 熟练掌握集合的交、并、（相对和绝对）补、对称差、广义交、广义并的定义及其性
质
3. 掌握集合的文氏图的画法及利用文氏图解决有限集的计数问题的方法
4. 牢记基本的集合恒等式（等幂律、交换律、结合律、分配律、德·摩根律、收律、零
律、同一律、排中律、矛盾律、余补律、双重否定律、补交转换律）
5. 准确地用逻辑演算或利用已知的集合恒等式或包含式证明新的等式或包含式
6.1 集合的基本概念
一．集合的表示
集合是不能精确定义的基本概念。直观地说，把一些事物汇集到一起组成一个整体就叫集合，而这些事物就是这个集合的元素或成员。例如：
二．集合之间的关系
下面考虑在同一层次上的两个集合之间的关系。
定义6.1设A，B为集合，如果B中的每个元素都是A中的元素，则称B是A的子集合，
简称子集。这时也称B被A包含，或A包含B，记作B A。
如果B不被A包含，则记作B A。
包含的符号化表示为
B A x(x ∈B→x∈A)
例如N Z Q R C，但Z N。
显然对任何集合A都有A A。
定义6.2设A，B为集合，如果A B且B A，则称A与B相等，记作A＝B。
如果A与B不相等，则记作A≠B。
相等的符号化表示为
A＝B A B∧B A
定义6.3设A，B为集合，如果B A且B≠A，则称B是A的真子集，记作B A。
如果B不是A的真子集，则记作B A。
真子集的符号化表示为
B A B A∧B≠A
例如N Z Q R C，但N N。
定义6.4不含任何元素的集合叫做空集，记作。
空集可以符号化表示为
＝{x|x≠x}。
例如{x|x∈R∧x2+1=0}是方程x2+1=0的实数解集，因为该方程无实数解，所以是空集。定理6.1空集是一切集合的子集。
证：任何集合A，由子集定义有
A x(x ∈→x∈A)
右边的蕴涵式因前件假而为真命题，所以A也为真。
推论空集是唯一的。
定义6.5设A为集合，把A的全部子集构成的集合叫做A的幂集，记作P(A)(或PA，
2A)。
幂集的符号化表示为
P(A)＝{x|x A}
对于例6.1中的集合A有
P(A)＝{，{1}，{2}，{3}，{1，2}，{1，3}，{2，3}，{1，2，3}} 不难看出，若A是n元集，则P(A)有2n个元素。
定义 6.6在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个集合为全集，记作E。
全集是有相对性的，不同的问题有不同的全集，即使是同一个问题也可以取不同的全集。例如在研究平面上直线的相互关系时，可以把整个平面(平面上所有点的集合)取作全集，也可以把整个空间(空间上所有点的集合)取作全集。一般地说，全集取得小一些，问题的描述和处理会简单些。
6.2 集合的运算
一．集合的基本运算
集合的基本运算有并，交，相对补和对称差。
定义6.7设A，B为集合，A与B的并集A∪B，交集A∩B，B对A的相对补集
A－B分别定义如下：
A∪B＝{x|x∈A∨x∈B }
A∩B＝{x|x∈A∧x∈B }
A－B＝{x|x∈A∧x B }
由定义可以看出，A∪B是由A或B中的元素构成，A∩B由A和B中的公共元素构成，A－B由属于A但不属于B的元素构成。例如
A＝{a，b，c}，B＝{a}，C＝{b，d}
则有
A∪B＝{a，b，c}，A∩B＝{a}，A－B＝{b，c}，
B－A＝，B∩C＝
如果两个集合的交集为，则称这两个集合是不相交的。例如B和C是不相交的。
两个集合的并和交运算可以推广成n个集合的并和交：
A1∪A2∪…∪A n＝{x|x∈A1∨x∈A2∨…∨x∈A n}
A1∩A2∩…∩A n＝{x|x∈A1∧x∈A2∧…∧x∈A n}
上述的并和交可以推广成n个集合的并和交：
＝A1∪A2∪…∪A n
＝A1∩A2∩…∩A n
并和交运算还可以推广到无穷多个集合的情况：
＝A1∪A2∪…
＝A1∩A2∩…
定义6.8设A，B为集合，A与B的对称差集A B定义为：
A B＝(A－B)∪(B－A)
例如A＝{a，b，c}，B＝{b，d}，则A B＝{a，c，d}。
对称差运算的另一种定义是
A B＝(A∪B)－(A∩B)
可以证明这两种定义是等价的，证明可留作练习。
在给定全集E以后，A E，A的绝对补集～A定义如下：
定义6.9～A＝E－A＝{x|x∈E∧x A}
二．有穷计数集
使用文氏图可以很方便地解决有穷集的计数问题。首先根据已知条件把对应的
文氏图画出来。一般地说，每一条性质决定一个集合。有多少条性质，就有多少个集合。如果没有特殊说明，任何两个集合都画成相交的，然后将已知集合的元素数填入表示该集合的区域内。通常从n个集合的交集填起，根据计算的结果将数字逐步填入所有的空白区域。如果交集的数字是未知的，可以设为x。根据题目中的条件，列出一次方程或方程组，就可以求得所需要的结果。
例6.2对24名会外语的科技人员进行掌握外语情况的调查。其统计结果如下：会英、
日、德和法语的人分别为13，5，10和9人，其中同时会英语和日语的有2人，会英、德和法语中任两种语言的都是4人。已知会日语的人既不懂法语也不懂德语，分别求只会一种语言(英、德、法、日)的人数和会三种语言的人数。
解令A，B，C，D分别表示会英、法、德、日语的人的集合。根据题意画出文氏图如图6.3所示。设同时会三种语言的有x人，只会英、法或德语一种语言的分别为y1，y2和y3人。将x和y1，y2，y3填入图中相应的区域，然后依次填入其它区域的人数。
根据已知条件列出方程组如下：
解得x＝1，y1＝4，y2＝2，y3＝3。
三．广义交和广义并
以上定义的并和交运算称为初级并和初级交。下面考虑推广的并和交运算，即广义并和广义交。
定义6.10设A为集合，A的元素的元素构成的集合称为A的广义并，记为∪A。符号化表示为
∪A＝{x|z(z∈A∧x∈z)}。
例6.4设
A＝{{a,b,c},{a,c,d},{a,e,f}}
B＝{{a}}
C＝{a,{c,d}}
则
∪A＝{a,b,c,d,e,f}
∪B＝{a}
∪C＝a∪{c,d}
∪＝
根据广义并定义不难证明，若A＝{ A1,A2,…,A n}，则∪A＝A1∪A2∪…∪A n。
类似地可以定义集合的广义交。
定义6.11设A为非空集合，A的所有元素的公共元素构成的集合称为A的广义交，记为∩A。符号化表示为
∩A＝{x|z(z∈A→x∈z)}
考虑例6.4中的集合，有
∩A＝{a}，∩B＝{a}，∩C＝a∩{c，d}
细心的读者一定会注意到在定义6.11中特别强调了A是非空集合。对于空集可以进行广义并，即∪＝。但空集不可以进行广义交，因为∩不是集合，在集合论中是没有意义的。
和广义并类似，若A＝{A1,A2,…,A n}，则∩A＝A1∩A2∩…∩A n。
在后面的叙述中，若只说并或交，则这都是指集合的初级并或初级交；如果在并或交前边冠以“广义”两个字，则指集合的广义并或广义交。
为了使得集合表达式更为简洁，我们对集合运算的优先顺序做如下规定：称广义并，广义交，幂集，绝对补运算为一类运算，并，交，相对补，对称差运算为二类运算。
一类运算优先于二类运算。
一类运算之间由右向左顺序进行。
二类运算之间由括号决定先后顺序。
例如下面的集合公式：
∩A－∪B，∪P(A)，～P(A)∪∪B，～(A∪B)
都是合理的公式。
6.3 集合恒等式
一．基本集合恒等式
下面的恒等式给出了集合运算的主要算律，其中A，B，C代表任意集合。
幂等律A∪A＝A(6.1)
A∩A＝A(6.2)
结合律(A∪B)∪C＝A∪(B∪C)(6.3)
(A∩B)∩C＝A∩(B∩C)(6.4)
交换律A∪B＝B∪A(6.5)
A∩B＝B∩A(6.6)
分配律A∪(B∩C)＝(A∪B)∩(A∪C)(6.7)
A∩(B∪C)＝(A∩B)∪(A∩C)(6.8)
同一律A∪＝A(6.9)
A∩E＝A(6.10)
零律A∪E＝E(6.11)
A∩＝(6.12)
排中律A∪～A＝E(6.13)
矛盾律A∩～A＝(6.14)
吸收律A∪(A∩B)＝A(6.15)
A∩(A∪B)＝A(6.16)
德摩根律A－(B∪C)＝(A－B)∩(A－C) (6.17)
A－(B∩C)＝(A－B)∪(A－C)(6.18)
～(B∪C)=～B∩～C(6.19)
～(B∩C)=～B∪～C(6.20)
～＝E(6.21)
～E＝(6.22)
双重否定律～(～A)＝A(6.23)
我们选证其中的一部分，其余留给读者完成。在证明中大量用到命题逻辑的等值式，在叙述中采用半形式化的方法，其中表示当且仅当。
例6.6证明式6.17，即A－(B∪C)＝(A－B)∩( A－C)。
证对任意的x，
x∈A－(B∪C)
x∈A∧x B∪C
x ∈A∧┐(x∈B∨x∈C)
x∈A∧(┐x∈B∧┐x∈C)
x ∈A∧x B∧x C
(x ∈A∧x B)∧(x∈A∧x C)
x∈A－B)∧x∈A－C
x ∈(A－B)∩(A－C)
所以A－(B∪C)＝(A－B)∩( A－C)
例6.7证明式6.10，即A∩E＝A。
证对任意的x，
x∈A∩E x∈A∧x∈E x∈A(因为x∈E是恒真命题)，所以A∩E＝A。
以上证明的基本思想是：设P，Q为集合公式，欲证P＝Q，即证
P Q∧Q P为真。
也就是要证对于任意的x有
x∈P x∈Q和x∈Q x∈P
成立。对于某些恒等式可以将这两个方向的推理合到一起，就是
x ∈P x∈Q
不难看出，集合运算的规律和命题演算的某些规律是一致的，所以命题演算的方法是证明集合恒等式的基本方法。等式6.1～6.23都可以利用这个方法得到。
证明集合恒等式的另一种方法是利用已知的恒等式来代入。举例如下。
例6.8假设已知等式6.1～6.14，试证等式6.15即A∪(A∩B)＝A。
证A∪(A∩B)＝(A∩E)∪(A∩B) (由等式6.10)
＝A∩(E∪B) (由等式6.8)
＝A∩(B∪E) (由等式6.5)
＝A∩E (由等式6.11)
＝A (由等式6.10)
二．证明技巧
证明技巧一
除了以上算律以外，还有一些关于集合运算性质的重要结果。例如：
A∩B A，A∩B B(6.24)
A A∪B，
B A∪B(6.25)
A－B A(6.26)
A－B＝A∩～B (6.27)
我们只选证其中的一部分。
例6.9证明等式6.27，即A－B＝A∩～B。
证对于任意的x，
x∈A－B x∈A∧x B
x ∈A∧x∈～B
x ∈A∩～B
所以A－B＝A∩～B。
等式6.27把相对补运算转换成交运算，这在证明有关相对补的恒等式中是很有用的。
例6.10证明(A－B)∪B＝A∪B
证(A－B)∪B
＝(A∩～B)∪B
＝(A∪B)∩(～B∪B)
＝(A∪B)∩E
＝A∪B
证明技巧二
A ∪B＝
B A∩B＝A A－B＝(6.28)
例6.11证明命题6.28是真命题。
证先证A∪B＝B A B
对于任意的x，
x∈A x∈A∨x∈B x∈A∪B x∈B(因为A∪B＝B)
所以A B。
再证A B A∩B＝A。
显然有A∩B A，下面证A A∩B。
对于任意的x，
x∈A x∈A∧x∈A x∈A∧x∈B(因为A B)
x∈A∩B
由集合相等的定义有A∩B＝A。
然后证A∩B＝A A－B＝。
A－B
＝A∩～B
＝(A∩B)∩～B(因为A∩B＝A)
＝A∩(B∩～B)
＝A∩
＝
最后证A－B＝A∪B＝B。
由例6.10及A－B＝有
A∪B＝B∪(A－B)＝B∪＝B
式6.28给出了A B的另外三种等价的定义，这不仅为证明两个集合之间的包含关系提供了新方法，同时也可以用于集合公式的化简。
例6.12化简((A∪B∪C)∩(A∪B))－((A∪(B－C))∩A)。
解因为A∪B A∪B∪C，A A∪(B－C)，由式6.28有
((A∪B∪C)∩(A∪B))－((A∪(B－C))∩A)
＝(A∪B)－A
＝B－A
证明技巧三
A B＝
B A (6.29)
(A B)C＝A(B C) (6.30)
A＝A (6.31)
A A＝(6.32)
A B＝A C B＝C (6.33)
式6.29～6.33是关于对称差运算的算律，前四条可通过对称差的定义加以证明，最后一条叫做消去律，它的证明给在下面。
例6.13已知A B＝A C，证明B＝C。
证已知A B＝A C，所以有
A(A B)＝A(A C)
(A A)B＝(A A) C (由式6.30)
B＝ C (由式6.32)
B＝C(由式6.29)
B＝C (由式6.31)
第四章代数结构（作业） 作业：P86：4、7、9 4、 （1）若a和b是整数，则a+b+ab也是整数，故a*b也是整数，所以运算*是封闭的。（2）任选整数集合中的三个元素x,y和z。则有： (x*y)*z = (x+y+xy)*z = (x+y+xy)+z+(x+y+xy)×z = x+y+z+xy+xz+yz+xyz x*(y*z) = x*(y+z+yz) = x+(y+z+yz)+x×(y+z+yz) = x+y+z+yz+xy+xz+xyz = (x*y)*z 因此，*运算满足结合律。 （3）假设e为（Z,*）的幺元，则有： 任选整数集中的一个元素x，都有 0*x = 0+x+0×x=x且 x*0 = x+0+x×0=x 故0是(Z,*)的幺元。 7、N+上的所有元素都是（N+ ,*）等幂元； （N+ ,*）无幺元； （N+ ,*）的零元为1。 9、（A,*）中的等幂元：a、b、c、d； （A,*）中的幺元：b； （A,*）中的零元：c； a-1 = d，b-1 = b，c-1 不存在，d-1 = a， 作业：P87：12、13、18 12、（A，*）到（N4,⊕4）的同构映射f为： f(a)=0, f(b)=1, f(c)=2, f(d)=3; 或者： f(a)=0, f(b)=3, f(c)=2, f(d)=1; 13、同构映射f为： f(0)=?, f(1)={a}, f(2)={b}, f(3)={a,b};
或者： f(0)=?, f(1)={b}, f(2)={a}, f(3)={a,b}; 18、任选a ∈N +,b ∈N +, 只需证明f(a+b)=f(a)+f(b) 由f 的定义可知：f(a+b)=2a+2b=f(a)+f(b)，故f 是（N +,+）到(E +,+)的同态映射。 作业：P96：3，P97：7 3、(1)显然，*运算对Z 是封闭的。 (2) (a*b)*c = (3(a+b+2)+ab)*c = 3((3(a+b+2)+ab)+c+2)+(3(a+b+2)+ab)×c = 3(3a+3b+c+ab+8+ac+bc+2c)+abc = 3(3a+3b+3c+ab+ac+bc+8)+abc a*(b*c) = a*(3(b+c+2)+bc) = 3(a+(3(b+c+2)+bc)+2)+a(3(b+c+2)+bc) = 3(a+3b+3c+bc+8+ab+ac+2a)+abc = 3(3a+3b+3c+ab+ac+bc+8)+abc = (a*b)*c 故*运算满足结合律。 （3）任选a ∈Z ，(-2)*a=a 且a*(-2)=a ，所以-2是(Z,*)的幺元。 所以（Z,*）是独异点。 7、因为1为(A,*)运算的幺元，而且对任意A 的子集A ’,*在A ’上都是封闭和可结合的运算，因此，（A,*）的所有子独异点为(A ’,*)，其中A ’必须包含1。即：(A,*)的所有子独异点为： ({1},*),({1,2},*),({1,3},*),({1,4},*),({1,2,3},*),({1,2,4},*),({1,3,4},*),({1,2,3,4},*) P105：3、4、13 3、??????1100b a ×??????220 0b a ＝??? ?? ?212100b b a a ,a 1,a 2∈{1,-1}, 所以a 1×a 2∈{1,-1}，b 1×b 2∈{1,-1}。 故（G,×）是封闭的。 而 (??????1100b a ×??????2200b a )×??????3300b a =??????212 100b b a a ×????? ?3300b a =??????3213 2100b b b a a a ??????1100b a ×(????? ?22 00b a ×??????3300b a )=??????1100b a ×??????323 200b b a a =??????3213210 0b b b a a a 故（G,×）是可结合的。（也可以说因为矩阵乘法是可结合的。）
1.6 集合对等 习题1.6 1.证明: 任意无限集合均存在可数子集. 证 设A 是无限集合，取A a ∈0，则}{0a A -是无限集合. 取A a ∈1，则},{10a a A -是无限集合. 一直下去，即可得到无限集合A 的可数子集,...},...,{10n a a a . 2.证明: ]1,0[~)1,0(. 证 由于(0,1)是无限集合，而任意无限集合均存在可数子集，设,...},...,{10n a a a 是(0,1)开区间的一个可数子集合，令]1,0[)1,0(:→f ，满足下面的条件 1)(,0)(10==a f a f , 2,)(2≥=-i a a f i i ; ,...},...,,{,)(10n a a a x x x f ?=. 显然，f 是(0,1)到[0, 1]的一个双射. 故]1,0[~)1,0(. 3.证明: b a b a <],,[~]1,0[. 证 令],[]1,0[:b a f →，x a b a x f )()(-+=，容易证明f 是一个双射，进而],[~]1,0[b a . 4.有理数集合Q 是可数集合. 证 由于正有理数集合Q + = ??????≠∈互素与n m m n m m n ,0,N ,，令N N Q :?→+f ， ),(n m m n f =?? ? ??， 则f 是单射，所以|Q +| |N N |?≤. 由于N N ~N ?，于是|Q +| =≤|N |?0. 而Q +是无限集合，所以|Q +| =≥|N |?0. 于是|Q +| = ?0. 所以正有理数集合Q +是可数集合. 显然Q +与所有负有理数集合Q -对等，而Q = Q +?Q -?{0}，所有Q 是可数集合. 5.证明: 全体无理数组成的集合R – Q 与R 有相同的基数. 证 在全体无理数集合R – Q 中选取可数子集,...},...,{10n a a a ，因为Q 可
第6章 习题解答 6.1 A:⑨; B:⑨; C:④; D:⑥; E:③ 分析 对于给定的集合和运算判别它们是否构成代数系统的关键是检查集合对给定运算的封闭性,具体方法已在5.3节做过说明. 下面分别讨论对各种不同代数系纺的判别方法. 1°给定集合S 和二元运算°,判定
为格,且>∧∨<,,S 构成代数系统.若><,*, S 是代数系统且°和*运算满足交换律、结合律和吸收律，则><,*, S 构成格。 在此基础上作为分配格的充分必要条件是不含有与图6.3所示的格同构的子 格。而有补格和布尔格的判定只要根据定义进行即可。 注意对于有限格，只要元素个数不是2的幂，则一定 不是布尔格。但元素个数恰为n 2的有限格中只有唯一 的布尔格。 以本题为例具体的判定过程如下： （1） 由12S n n n ?=+可知1S 对+运算不封闭，根本不构成代数系统。 （2）由242*2S ?=可知2S 对*运算不封闭，也不构成代数系统。 （3）3S 关于,* 运算封闭，构成代数系统。且3S 关于模n 加法 满足交换群的定义，关于模n 乘法*满足关群的定义，且*对 有分配律。因而><,*,3 S 构成环。但当n=6时，有6.02*33*2S ==中含有零因子2和3，不是整环，也不是域。类似地分析可知，当n 为合数时，n S 不是域，但n 为素数时n S 构成域。 （4）4S 是偏序集。对于小于等于关系},max{},,min{,y x y x y x y x =∨=∧≤，显然有4,S y x y x ∈∨∧，构成格。但4S 不是有补格，2和3没有补元，也不是布尔代数。 （5）容易验证5S 关于矩阵加法构成群。 6．2 A:②; B:③; C:⑦; D:⑩; E:⑨ 分析 此处的G 实际上是n Z Z .4关于模n 加法构成群，但关于模n 乘法只构成独导点，而不构成群，因为0没乘法逆元。>⊕<,G 是循环群。2是2阶元 ，1和3是4阶元。 如何求群G 中元素的阶？如果n G =||，则,G x ∈?||x 是n 的正因子。首先找到n 的正因子，并从小到大列出来，然后依次检查每相正因子r 。使得e x r =的
离散数学辅助教材 概念分析结构思想与推理证明 第一部分 集合论
离散数学习题解答 习题一（第一章集合） 1. 列出下述集合的全部元素： 1）A={x | x ∈N∧x是偶数∧x＜15} 2）B={x|x∈N∧4+x=3} 3）C={x|x是十进制的数字} [解] 1）A={2，4，6，8，10，12，14} 2）B= 3）C={0，1，2，3，4，5，6，7，8，9} 2. 用谓词法表示下列集合： 1）{奇整数集合} 2）{小于7的非负整数集合} 3）{3，5，7，11，13，17，19，23，29} [解] 1）{n n∈I∧(?m∈I)(n=2m+1)}； 2）{n n∈I∧n≥0∧n<7}； 3）{p p∈N∧p>2∧p<30∧?(?d∈N)(d≠1∧d≠p∧(?k∈N)(p=k?d))}。 3. 确定下列各命题的真假性： 1） 2）∈ 3）{} 4）∈{} 5）{a，b}{a，b，c，{a，b，c}} 6）{a,b}∈(a，b，c，{a，b，c}) 7）{a，b}{a，b，{{a，b，}}} 8）{a，b}∈{a，b，{{a，b，}}} [解]1）真。因为空集是任意集合的子集； 2）假。因为空集不含任何元素； 3）真。因为空集是任意集合的子集； 4）真。因为是集合{}的元素； 5）真。因为{a，b}是集合{a，b，c，{a，b，c}}的子集； 6）假。因为{a,b}不是集合{a，b，c，{a，b，c}}的元素；
7）真。因为{a，b}是集合{a，b，{{a，b}}}的子集； 8）假。因为{a,b}不是集合{a，b，{{a，b}}}的元素。 4. 对任意集合A，B，C，确定下列命题的真假性： 1）如果A∈B∧B∈C，则A∈C。 2）如果A∈B∧B∈C，则A∈C。 3）如果A B∧B∈C，则A∈C。 [解] 1）假。例如A={a}，B={a，b}，C={{a}，{b}}，从而A∈B∧B∈C但A∈C。 2）假。例如A={a}，B={a，{a}}，C={{a}，{{a}}}，从而A∈B∧B∈C，但、A ∈C。 3）假。例如A={a}，B={a，b}，C={{a}，a，b}，从而ACB∧B∈．C，但A∈C。5．对任意集合A，B，C，确定下列命题的真假性： 1）如果A∈B∧B C，则A∈C。 2）如果A∈B∧B C，则A C。 3）如果A B∧B∈C，则A∈C。 3）如果A B∧B∈C，则A C。 [解] 1）真。因为B C x（x∈B x∈C），因此A∈B A∈C。 2）假。例如A={a}，B={{a}，{b}}，C={{a}，{b}，{c}}从而A∈B∧B C，但A C。 3）假。例如A={a}，B={{a，b}}，C={{a，{a，b}}，从而A B∧B∈C，但A C。 4）假。例如A={a}，B={{a，b}}，C={{a，b}，b}，从而A B∧B∈C，但A C。 6．求下列集合的幂集： 1）{a，b，c} 2）{a，{b，c}} 3）{} 4）{，{}} 5）{{a，b}，{a，a，b}，{a，b，a，b}} [解] 1）{，{a}，{b}，{c}，{a，b}，{a，c}，{b，c}，{a，b，c}} 2）{，{a}，{{b，c}}，{a，{a，b}}} 3）{，{}} 4）{，{}，{{}}，{，{}}}
习题5 1．设个体域D={a,b,c}，消去下列各式的量词： (1) x y(F(x)∧G(y)) (2) x y(F(x)∨G(y)) (3) xF(x)→yG(y) (4) x(F(x,y)→yG(y)) 答案 (1) x y(F(x)∧G(y)) xF(x)∧yG(y) (F(a)∧F(b))∧F(c))∧(G(a)∨G(b)∨G(c)) (2) x y(F(x)∨G(y)) xF(x)∨yG(y) (F(a)∧F(b)∧F(c))∨(G(a)∧G(b)∧G(c)) (3) xF(x)→yG(y) (F(a)∧F(b)∧F(c))→(G(a)∧G(b)∧G(c)) (4) x(F(x,y)→yG(y)) xF(x,y)→yG(y) (F(a,y)∨F(b,y)∨F(c,y))→(G(a)∨G(b)∨G(c)) 2．设个体域D={1,2}，请给出两种不同的解释I1和I2，使得下面公式在I1下都是真命题，而在I2下都是假命题。 (1) x(F(x)→G(x)) (2) x(F(x)∧G(x)) .(1) 答案 I1: F(x):x≤2,G(x):x≤3 F(1),F(2),G(1),G(2)均为真，所以 x(F(x)→G(x)) (F(1)→G(1)∧(F(2)→G(2))为真。 I2: F(x)同I1,G(x):x≤0 则F(1),F(2)均为真，而G(1),G(2)均为假， x(F(x)→G(x))为假。 (2)留给读者自己做。 3．给定解释I如下： (a) 个体域D={3,4}。 (b) (x)为(3)=4，(4)=3。 (c) (x,y)为(3,3)=(4,4)=0，(3,4)=(4,3)=1。 答案 试求下列公式在I下的真值： (1) x yF(x,y) (2) x yF(x,y)
数理逻辑部分 第1章命题逻辑 命题符号化及联结词 命题: 判断结果惟一的陈述句 命题的真值: 判断的结果 真值的取值: 真与假 真命题: 真值为真的命题 假命题: 真值为假的命题 注意: 感叹句、祈使句、疑问句都不是命题，陈述句中的悖论以及判断结果不惟一确定的也不是命题。 简单命题(原子命题)：简单陈述句构成的命题 复合命题：由简单命题与联结词按一定规则复合而成的命题 简单命题符号化 用小写英文字母p, q, r, … ,p i,q i,r i (i≥1）表示 简单命题 用“1”表示真，用“0”表示假 例如，令p：是有理数，则p 的真值为 0 q：2 + 5 = 7，则q 的真值为 1 联结词与复合命题 1.否定式与否定联结词“” 定义设p为命题，复合命题“非p”（或“p的否定”）称 为p的否定式，记作p. 符号称作否定联结词，并规定p为真当且仅当p为假. 2.合取式与合取联结词“∧” 定义设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q 的合取式，记作p∧q. ∧称作合取联结词，并规定 p∧q为真当且仅当p 与q同时为真 注意：描述合取式的灵活性与多样性 分清简单命题与复合命题 例将下列命题符号化. (1) 王晓既用功又聪明. (2) 王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学. 解令p：王晓用功，q：王晓聪明，则 (1) p∧q (2) p∧q (3) p∧q. 令r : 张辉是三好学生，s :王丽是三好学生 (4) r∧s. (5) 令t : 张辉与王丽是同学，t 是简单命题 . 说明:
第5章 一.填空题 1. 群中有唯一的（）。 2. 如果群运算是可交换的，则群为（）。 3. 设*是定义在集合A上的二元运算，如果对于A中任意的两个元素x,y，都有x*y∈A，则称二元运算*在A上是（）。 4. 设*是定义在集合A上的二元运算，如果对于A中任意的两个元素x,y，都有x*y=y*x，则称二元运算*在A上是（）。 5. 设★是定义在有理数集合Q上的二元运算，如果对于Q中任意的两个元素x,y，都有x★y=x+y-x*y，其中*表示普通乘法元算，则二元运算★在Q 上是（）。（填写可交互/不可交换） 6. 设*是定义在集合A上的二元运算，如果对于A中任意的元素x,y,z，都有(x*y)*z=x*(y*z) ，则称二元运算*在A上是（）。 7. 设★是定义在非空集合A上的二元运算，如果对于A中任意的两个元素x,y，都有x*y=y， 则二元运算★在A上是（）。（填写可结合/不可结合） 8. 设*，★是定义在集合A上的两个二元运算，如果对于A中任意的元素x,y,z，都有(x*y) ★z=（x★z）*(y★z)，z★(x*y)=(z★x)*(z★y),则称二元运算★对于*在A上是（）。 9. 设*，★是定义在集合A上的两个可交换的二元运算，如果对于A中任意的元素x,y，都有x*(x★y)=x, x★(x*y)=x,则称二元运算*对于★在A上满 足（）。 10. 设*是定义在集合A上的二元运算，如果对于A中任意的元素x，都有x*x=x，则称二元运算*是（）。 11. 设*是定义在集合A上的二元运算，如果在A中存在元素el，对于A中任意的元素x，都有el*x=x，则称el为A中关于运算*的（）。 12. 设*是定义在集合A上的二元运算，如果在A中存在元素ol，对于A中任意的元素x，都有ol*x=x，则称ol为A中关于运算*的（）。 13. 设*是定义在集合A上的二元运算，如果在A中存在元素er，对于A中任意的元素x，都有x*erl =x，则称er为A中关于运算*的（）。 14. 设*是定义在集合A上的二元运算，如果在A中存在元素or，对于A中任意的元素x，都有x*or=x，则称or为A中关于运算*的（）。 15. 如果对于集合中的二元运算*，存在左零元和右零元，且左零元等于右零元，则零元是（）。 16. 如果对于集合中的二元运算*，存在左么元和右么元，且左么元等于右么元，则么元是（）。 17. 设*是定义在集合A上的二元运算，且e是A中关于运算*的么元，如果对于A中的元素x，存在A中的元素y，有y*x=e，则称y为x的 （）。 18. 对于实数域上的乘法元算，每个元素（）逆元。（填写一定有/不一定有） 19. 对于实数域上的加法运算，（）零元。（填写存在/不存在） 20. 对于整数域上的加法运算，（）么元。（填写存在/不存在） 21. 对于非空集合S上二元运算*，是封闭且可结合的，那么
第一章，0命题逻辑 素数 = 质数，合数有因子 和或假必真同为真 (p→q)∧(q←→r)，(p∧q)∧┐r，p∧(q∧┐r)等都是合式公式，而pq→r，（p→(r→q)等不是合式公式。 若公式A是单个的命题变项，则称A为0层合式 (┐p∧q)→r，(┐(p→┐q))∧((r∨s)┐p)分别为3层和4层公式 【例】求下列公式的真值表，并求成真赋值和成假赋值。 (┐p∧q)→┐r 公式(1)的成假赋值为011，其余7个赋值都是成真赋值 第二章，命题逻辑等值演算 （1）双重否定律??A?A （2）等幂律 A∧A?A ； A∨A?A （3）交换律 A∧B?B∧A ； A∨B?B∨A （4）结合律（A∧B）∧C?A∧（B∧C）；（A∨B）∨C?A∨（B∨C） （5）分配律（A∧B）∨C?（A∨C）∧（B∨C）；（A∨B）∧C?（A∧C）∨（B∧C）（6）德·摩根律?（A∨B）??A∧?B ；?（A∧B）??A∨?B （7）吸收律 A∨（A∧B）?A；A∧（A∨B）?A （8）零一律 A∨1?1 ； A∧0?0 （9）同一律 A∨0?A ； A∧1?A （10）排中律 A∨?A?1 （11）矛盾律 A∧?A?0
（12）蕴涵等值式 A→B??A∨B （13）假言易位 A→B??B→?A （14）等价等值式 A?B?（A→B）∧（B→A） （15）等价否定等值式 A?B??A??B??B??A （16）归缪式（A→B）∧（A→?B）??A (p∧┐q)∨(┐q∧┐r)∨p (p∨q∨r)∧(┐p∨┐q)∧r 一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式 一个合取范式是重言式当且仅当它的每个简单析取式都是重言式 主范式【∧小真，∨大假】 ∧成真小写 【例】 (p→q)→(┐q→┐p) = ┐(┐p∨q)∨(q∨┐p) (消去→) = (p∧┐q)∨┐p∨q (┐内移) (已为析取范式) = (p∧┐q)∨(┐p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q) （*） = m2∨m0∨m1∨m1∨m3 = m0∨m1∨m2∨m3 (幂等律、排序) (*)由┐p及q派生的极小项的过程如下： ┐p = ┐p∧(┐q∨q) = (┐p∧┐q)∨(┐p∧q) q = (┐p∨p)∧q = (┐p∧q)∨(p∧q)
1.5集合的划分与覆盖 习题1.5 1.设},,,{d c b a A =，求出集合A 的所有不同的划分. 解 可以按照划分的块的数目依次求出A 的所有不同的划分共15个. 仅一个划分块:}},,,{{1d c b a =π. 有两个划分块: }},,{},{{2d c b a =π，}},,{},{{3d c a b =π， }},,{},{{4d b a c =π，}},,{},{{5c b a d =π； }},{},,{{6d c b a =π，}},{},,{{7d b c a =π， }},{},,{{8c b d a =π. 有三个划分块: }},{},{},{{9d c b a =π，}},{},{},{{10d b c a =π， }},{},{},{{11c b d a =π，}},{},{},{{12d a c b =π， }},{},{},{{13c a d b =π，}},{},{},{{14b a d c =π. 有四个划分块: }}{},{},{},{{15d c b a =π. 2.对于整数集合Z ，令 }Z |3{1∈=k k A ，}Z |13{2∈+=k k A ，}Z |23{3∈+=k k A , 则},,{321A A A 是Z 的划分. 试验证之. 解 因为(1)≠i A ?，3,2,1=i . (2)=?j i A A ?，3,2,1,,=≠j i j i . (3)=??321A A A Z. 所以，},,{321A A A 是Z 的划分. 3.设}|{I i A i ∈=π是集合A 的一种划分，对于集合B ，所有≠?B A i ?的B A i ?组成的集合是B A ?的划分. 试证明之. 证 对于任意j i ≠，因为=?j i A A ?，于是 =??=???B A A B A B A j i j i )()(?=?B ?.
离散数学第二版邓辉文编著第一章第二节习题答案 1.2 映射的有关概念 习题1.2 1. 分别计算?1. 5?，?-1?，?-1. 5?，? 1. 5?，?-1?，?-1. 5?. 解?1. 5?=2，?-1?=-1，?-1. 5?=-1，?1. 5?=1，?-1?=-1，?-1. 5?=-2. 2. 下列映射中，那些是双射? 说明理由. (1)f :Z →Z , f (x ) =3x . (2)f :Z →N , f (x ) =|x |+1. (3)f :R →R , f (x ) =x 3+1. (4)f :N ?N →N , f (x 1, x 2) =x 1+x 2+1. (5)f :N →N ?N , f (x ) =(x , x +1). 解 (1)对于任意对x 1, x 2∈Z ，若f (x 1) =f (x 2) ，则3x 1=3x 2，于是x 1=x 2，所以f 是单射. 由于对任意x ∈Z ，f (x ) ≠2∈Z ，因此f 不是满射，进而f 不是双射. (2)由于2, -2∈Z 且f (2) =f (-2) =3，因此f 不是单射. 又由于0∈N ，而任意x ∈Z 均有f (x ) =|x |+1≠0，于是f 不是满射. 显然，f 不是双射. (3)对于任意对x 1, x 2∈R ，若f (x 1) =f (x 2) ，则x 1+1=x 2+1，于是x 1=x 2，所以f 是单射. 对于任意y ∈R ，取x =(y -1) ，这时 1??3f (x ) =x +1=?(y -1) 3?+1=(y -1) +1=y ， ??33313 所以f 是满射. 进而f 是双射.
说明： 定义：红色表示。 定理性质：橙色表示。 公式：蓝色表示。 算法:绿色表示 页码：灰色表示 数理逻辑： 1.命题公式：命题，联结词(，，，，)，合式公式，子公式 2.公式的真值：赋值，求值函数，真值表，等值式，重言式，矛盾式 3.范式：析取范式，极小项，主析取范式，合取范式，极大项，主合取范式 4.联结词的完备集：真值函数，异或，条件否定，与非，或非，联结词完备集 5.推理理论：重言蕴含式，有效结论，P规则，T规则， CP规则，推理 6.谓词与量词:谓词，个体词，论域，全称量词，存在量词 7.项与公式:项，原子公式，合式公式，自由变元，约束变元，辖域，换名，代入 8.公式语义:解释，赋值，有效的，可满足的，不可满足的 9.前束范式:前束范式 10.推理理论:逻辑蕴含式，有效结论，-规则（US），+规则（UG），-规则(ES)， +规则(EG), 推理 集合论： 1.集合: 集合, 外延性原理, , , , 空集, 全集, 幂集, 文氏图, 交, 并, 差, 补, 对称差 2.关系: 序偶, 笛卡尔积, 关系, domR, ranR, 关系图, 空关系, 全域关系, 恒等关 系 3.关系性质与闭包:自反的, 反自反的, 对称的, 反对称的, 传递的,自反闭包 r(R), 对称闭包 s(R), 传递闭包 t(R) 4.等价关系: 等价关系, 等价类, 商集, 划分
5.偏序关系:偏序, 哈斯图, 全序(线序), 极大元/极小元, 最大元/最小元, 上界/下 界 6.函数: 函数, 常函数, 恒等函数, 满射,入射,双射，反函数, 复合函数 7.集合基数:基数, 等势, 有限集/无限集, 可数集, 不可数集 代数结构： 1.运算及其性质：运算，封闭的,可交换的,可结合的,可分配的,吸收律, 幂等的，幺 元,零元,逆元 2.代数系统：代数系统，子代数，积代数，同态，同构。 3.群与子群：半群,子半群,元素的幂，独异点，群，群的阶数，子群,平凡子群，陪集， 拉格朗日（Lagrange）定理 4.阿贝尔群和循环群：阿贝尔群(交换群)，循环群,生成元 5.环与域：环，交换环，含幺环，整环，域 6.格与布尔代数：格，对偶原理，子格，分配格，有界格，有补格，布尔代数，有限 布尔代数的表示定理 图论： 1.图的基本概念：无向图、有向图、关联与相邻、简单图、完全图、正则图、子图、 补图，握手定理，图的同构 2.图的连通性:通路，回路，简单通路，简单回路（迹）初级通路（路径），初级回路 （圈），点连通，连通图，点割集，割点，边割集，割边，点连通度，边连通度，弱连通图，单向连通图，强连通图，二部图（二分图） 3.图的矩阵表示：关联矩阵，邻接矩阵，可达矩阵 4.欧拉图与哈密顿图：欧拉通路、欧拉回路、欧拉图、半欧拉图，哈密顿通路、哈密 顿回路、哈密顿图、半哈密顿图 5.无向树与根树：无向树，生成树，最小生成树，Kruskal，根树，m叉树，最优二叉 树，Huffman算法 6.平面图:平面图，面，欧拉公式，Kuratoski定理
离散数学（第五版）清华大学出版社第6章习题解答 6.1 A:⑨; B:⑨; C:④; D:⑥; E:③ 分析对于给定的集合和运算判别它们是否构成代数系统的关键是检查集合对 给定运算的封闭性,具体方法已在 5.3节做过说明. 下面分别讨论对各种不同代数系纺的判别方法. 1°给定集合S和二元运算°,判定
习题13参考答案 1.图13.9中给出六个偏序集的哈斯图。判断其中哪些是格。如果不是格,说明理由。 图13.9 答案：(1),(3),(6)是格。(2)中的{e,d}没有最大下界。(4)中的{d,e}没有最大下界。(5)中的{a,b}没有最大下界。 2.下列各集合对于整除关系都构成偏序集,判断哪些偏序集是格。 (1) L={1,2,3,4,5} (2) L={1,2,3,6,12} (3) L={1,2,3,4,6,9,12,18,36} (4) L={1,2,22,...,2n},n∈Z+ 答案：(1)不是格,其他都是。
3.(1)画出Klein四元群的子群格。 (2)画出模12的整数群Z12的子群格。 (3)画出3元对称群S3的子群格。 答案：(1) (2) (3) 4.设L是格,求以下公式的对偶式: (1) a∧(a∨b) a (2) a∨(b∧c)(a∨b)∧(a∨c) (3) b∨(c∧a)(b∨c)∧a 答案：(1) a∨(a∧b) a (2) a∧(b∨c)(a∧b)∨(a∧c) (3) b∧(c∨a)(b∧c)∨a
5.设L是格,a,b,c∈L,且a b c,证明 a∨b=b∧c 答案：a∨b=b b∧c=b 6.针对图13.10中的格L1,L2和L3,求出他们的所有子格。 图13.10 答案： L1的子格：{a},{b},{c},{d},{a,b},{a,c},{a,d}, {b,d},{c,d},{a,b,d},{a,c,d},L1 L2的子格：{a1},{d1},L2 L3的子格：{a2},{b2},{c2},{d2},{a2,b2},{a2,c2}, {a2,d2},{b2,c2},{b2,d2},{c2,d2},{a2,b2,c2}, {a2,b2,d2},{a2,c2,d2},{b2,c2,d2},L3 7.针对图13.9中的每个格,如果格中的元素存在补元,则求出这些补元。 答案：（1）a与d互补；b,c没有补元。 （3）a与f互补；b的补元为c,d；c的补元为b,e；d的补元为b,e；e的补元为c,d. （6）a与f互补；b的补元为e；c和d没有补元；e的补元为b. 8.说明图13.9中的每个格是否为分配格、有补格和布尔格,并说明理由。 答案： （1）是分配格，因为不包含与钻石格和五角格同构的子格；不是有补格和布尔格，b,c没有补元。 （3）不是分配格，不是布尔格，因为包含五角格作为子格；是有补格，a与f互补，b和e的补元有c,d；c,d的补元有b,e. （6）是分配格，因为没有5元子格与钻石格或五角格同构；不是有
习题8 1. 设f：N→N，且 求f(0)，f({0})，f(1)，f({1})，f({0，2，4，6，…})，f({4，6，8})，f({1，3，5，7})。 2. 设A={1，2}，B={a，b，c}，求B A。 3.给定函数f和集合A，B如下： (1) f：R→R，f(x)=x，A={8}，B={4} (2) f：R→R+，f(x)=2x，A={1}，B={1，2} (3) f：N→N×N，f(x)=
第六章集合代数 1. 集合，相等，（真）包含，子集，空集，全集，幂集 2. 交，并，（相对和绝对）补，对称差，广义交，广义并 3. 文氏图，有穷集计数问题 4. 集合恒等式（等幂律，交换律，结合律，分配律，德·摩根律，吸收律，零律，同一 律，排中律，矛盾律，余补律，双重否定律，补交转换律等） 学习要求 1. 熟练掌握集合的子集、相等、空集、全集、幂集等概念及其符号化表示 2. 熟练掌握集合的交、并、（相对和绝对）补、对称差、广义交、广义并的定义及其性 质 3. 掌握集合的文氏图的画法及利用文氏图解决有限集的计数问题的方法 4. 牢记基本的集合恒等式（等幂律、交换律、结合律、分配律、德·摩根律、收律、零 律、同一律、排中律、矛盾律、余补律、双重否定律、补交转换律） 5. 准确地用逻辑演算或利用已知的集合恒等式或包含式证明新的等式或包含式
6.1 集合的基本概念 一．集合的表示 集合是不能精确定义的基本概念。直观地说，把一些事物汇集到一起组成一个整体就叫集合，而这些事物就是这个集合的元素或成员。例如： 方程x2－1＝0的实数解集合； 26个英文字母的集合； 坐标平面上所有点的集合； …… 集合通常用大写的英文字母来标记，例如自然数集合N(在离散数学中认为0也是自然数)，整数集合Z，有理数集合Q，实数集合R，复数集合C等。 表示一个集合的方法有两种：列元素法和谓词表示法，前一种方法是列出集合的所有元素，元素之间用逗号隔开，并把它们用花括号括起来。例如 A={a，b，c，…，z} Z={0，±1，±2，…} 都是合法的表示。谓词表示法是用谓词来概括集合中元素的属性，例如集合 B＝{x|x∈R∧x2－1＝0} 表示方程x2－1＝0的实数解集。许多集合可以用两种方法来表示，如B也可以写成{-1，1}。但是有些集合不可以用列元素法表示，如实数集合。 集合的元素是彼此不同的，如果同一个元素在集合中多次出现应该认为是一个元素，如{1，1，2，2，3}＝{1，2，3} 集合的元素是无序的，如 {1，2，3}＝{3，1，2} 在本书所采用的体系中规定集合的元素都是集合。 元素和集合之间的关系是隶属关系，即属于或不属于，属于记作∈，不属于记作，例如 A＝{a，{b，c}，d，{{d}}} 这里a∈A，{b，c}∈A，d∈A，{{d}}∈A，但b A，{d} A. b和{d}是A的元素的元素。可以用一种树形图来表示这种隶属关系，该图分层构成，每个层上的结点都表示一个集合，它的儿子就是它的元素。上述集合A的树形图如图6.1所示。图中的a，b，c，d也是集合，由于所讨论的问题与a，b，c，d的元素无关，所以没有列出它们的元素。鉴于集合的元素都是集合这一规定，隶属关系可以看作是处在不同层次上的集合之间的关系。
习题13 1.图13.9中给出六个偏序集的哈斯图。判断其中哪些是格。如果不是格,说明理由。 图13.9 答案：(1),(3),(6)是格。(2)中的{e,d}没有最大下界。(4)中的{d,e}没有最大下界。(5)中的{a,b}没有最大下界。 2.下列各集合对于整除关系都构成偏序集,判断哪些偏序集是格。 (1) L={1,2,3,4,5} (2) L={1,2,3,6,12} (3) L={1,2,3,4,6,9,12,18,36} (4) L={1,2,22,...,2n},n∈Z+ 答案：(1)不是格,其他都是。
3.(1)画出Klein四元群的子群格。 (2)画出模12的整数群Z12的子群格。 (3)画出3元对称群S3的子群格。 答案：(1) (2) (3) 4.设L是格,求以下公式的对偶式: (1) a∧(a∨b) a (2) a∨(b∧c)(a∨b)∧(a∨c) (3) b∨(c∧a)(b∨c)∧a 答案：(1) a∨(a∧b) a (2) a∧(b∨c)(a∧b)∨(a∧c) (3) b∧(c∨a)(b∧c)∨a 5.设L是格,a,b,c∈L,且a b c,证明 a∨b=b∧c
答案：a∨b=b b∧c=b 6.针对图13.10中的格L1,L2和L3,求出他们的所有子格。 图13.10 答案： L1的子格：{a},{b},{c},{d},{a,b},{a,c},{a,d}, {b,d},{c,d},{a,b,d},{a,c,d},L1 L2的子格：{a1},{d1},L2 L3的子格：{a2},{b2},{c2},{d2},{a2,b2},{a2,c2}, {a2,d2},{b2,c2},{b2,d2},{c2,d2},{a2,b2,c2}, {a2,b2,d2},{a2,c2,d2},{b2,c2,d2},L3 7.针对图13.9中的每个格,如果格中的元素存在补元,则求出这些补元。 答案：（1）a与d互补；b,c没有补元。 （3）a与f互补；b的补元为c,d；c的补元为b,e；d的补元为b,e；e的补元为c,d. （6）a与f互补；b的补元为e；c和d没有补元；e的补元为b. 8.说明图13.9中的每个格是否为分配格、有补格和布尔格,并说明理由。 答案： （1）是分配格，因为不包含与钻石格和五角格同构的子格；不是有补格和布尔格，b,c没有补元。 （3）不是分配格，不是布尔格，因为包含五角格作为子格；是有补格，a与f互补，b和e 的补元有c,d；c,d的补元有b,e. （6）是分配格，因为没有5元子格与钻石格或五角格同构；不是有补格，也不是布尔格，因为c和d没有补元。 9.对以下各小题给定的集合和运算判断它们是哪一类代数系统(半群,独异点,群,环,域,格,布尔代数),并说明理由。 (1) S1={0，1,-1}，运算为普通加法和乘法。 (2) S2={a1,a2,...,a n},a i,a j∈S2,a i*a j=a i.这里的n是给定的正整数,且n≥2. (3) S3={0,1},*为普通乘法。 (4) S4={1,2,5,7,10,14,35,70},和*分别表示求最小公倍数和最大公约数运算。 (5) S5={0,1,2},*为模3加法,为模3乘法。 答案：（1）不是代数系统，对于加法不封闭。 （2）半群，运算封闭，有结合律，没有单位元。 （3）半群与独异点，乘法封闭，有结合律，单位元是1，但是0没有逆元。 （4）格与布尔代数。两个运算满足交换、相互分配、同一律、补元律。 （5）环与域，{0,1,2}关于模3加构成交换群、{1,2}关于模3乘构成交换群，模3乘关于模3加有分配律。
第六章作业 评分要求： 1. 合计57分 2. 给出每小题得分(注意: 写出扣分理由). 3. 总得分在采分点1处正确设置. 一有限集合计数问题 (合计20分: 每小题10分, 正确定义集合得4分, 方法与过程4分, 结果2分) 要求: 掌握集合的定义方法以及处理有限集合计数问题的基本方法 1 对60个人的调查表明, 有25人阅读《每周新闻》杂志, 26人阅读《时代》杂志, 26人阅读《财富》杂志, 9人阅读《每周新闻》和《财富》杂志, 11人阅读《每周新闻》和《时代》杂志, 8人阅读《时代》和《财富》杂志, 还有8人什么杂志也不读. (1) 求阅读全部3种杂志的人数; (2) 分别求只阅读《每周新闻》、《时代》和《财富》杂志的人数. 解定义集合: 设E={x|x是调查对象}, A={x|x阅读《每周新闻》}, B={x|x阅读《时代》}, C={x|x阅读《财富》} 由条件得|E|=60, |A|=25, |B|=26, |C|=26, |A∩C|=9, |A∩B|=11, |B∩C|=8, |E-A∪B∪C|=8 (1) 阅读全部3种杂志的人数=|A∩B∩C| =|A∪B∪C|－(|A|+|B|+|C|)+(|A∩B|+|A∩C|+|B∩C|) =(60-8)－(25+26+26)+(11+9+8)=3 (2) 只阅读《每周新闻》的人数=|A－B∪C|=|A－A∩(B∪C)|=|A－(A∩B)∪(A∩C)| =|A|－(|A∩B|+|A∩C|－|A∩B∩C|)=25－(11+9-3)=8 同理可得只阅读《时代》的人数为10, 只阅读《财富》的人数为12. 2 使用容斥原理求不超过120的素数个数. 分析:本题有一定难度, 难在如何定义集合. 考虑到素数只有1和其自身两个素因子, 而不超过120的合数的最小素因子一定是2,3,5或7(比120开方小的素数), 也就是说, 不超过120的合数一定是2,3,5或7的倍数. 因此, 可定义4条性质分别为2,3,5或7的倍数, 先求出不超过120的所有的合数, 再得出素数的个数. 解定义集合: 设全集E={x|x∈Z∧1≤x∧x≤120} A={2k|k∈Z∧k≥1∧2k≤120}, B={3k|k∈Z∧k≥1∧3k≤120}, C={5k|k∈Z∧k≥1∧5k≤120}, D={7k|k∈Z∧k≥1∧7k≤120}. 则不超过120的合数的个数=|A∪B∪C∪D|－4 (因为2,3,5,7不是合数) =(|A|+|B|+|C|+|D|)－(|A∩B|+|A∩C|+|A∩D|+|B∩C|+|B∩D|+|C∩D|)+ (|A∩B∩C|+|A∩B∩D|+|A∩C∩D|+|B∩C∩D|)－|A∩B∩C∩D|－4 =(60+40+24+17)－(20+12+8+8+5+3)+(4+2+1+1)－0－4 (理由见说明部分) =89 因此不超过120的素数个数=120－1－89=30 (因为1不是素数) 说明: |A|=int(120/2); |A?B|=int(120/lcd(2,3)); |A?B?C|=int(120/lcd(2,3,5)); |A?B?C?D|=int(120/lcd(2,3,5,7)).