《离散数学》第六章 集合代数

第六章作业评分要求：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)).二集合关系证明1 设A,B,C是任意集合, 证明(1) (A－B)－C=A－(B∪C)(2) A∩C⊆B∩C ∧A－C⊆B－C ⇒A⊆B(合计12分: 每小题6分; 格式3分, 过程每错一步扣1分)证明(1) 逻辑演算法: ∀x,x∈(A－B)－C⇔x∈(A－B)∧¬x∈C (－定义)⇔(x∈A∧¬x∈B)∧¬x∈C (－定义)⇔x∈A∧(¬x∈B∧¬x∈C) (∧的结合律)⇔x∈A∧¬(x∈B∨x∈C) (德摩根律)⇔x∈A∧¬x∈B∪C (∪定义)⇔x∈A－B∪C (－定义)所以(A－B)－C=A－(B∪C).集合演算法(A－B)－C=(A∩~B)∩~C (补交转换律)=A∩(~B∩~C) (∩的结合律)=A∩~(B∪C) (德摩根律)=A－(B∪C) (补交转换律)得证.(2) 逻辑演算法: ∀x,x∈A⇔x∈A∩(C∪~C) (排中律, 同一律)⇔x∈(A∩C)∪(A∩~C) (∪对∩的分配率)⇔x∈A∩C∨x∈A－C (∪的定义, 补交转换律)⇒x∈B∩C∨x∈B－C (已知条件A∩C⊆B∩C与A－C⊆B－C) ⇔x∈(B∩C)∪(B－C) (∪的定义)⇔x∈(B∩C)∪(B∩~C) (补交转换律)⇔x∈B∩(C∪~C) (∩对∪的分配率)⇔x∈B (排中律, 同一律)所以A⊆B.集合演算法A=A∩(C∪~C) (同一律, 排中律)=(A∩C)∪(A∩~C) (∩对∪的分配率)=(A∩C)∪(A－C) (补交转换律)⊆(B∩C)∪(B－C) (已知条件A∩C⊆B∩C与A－C⊆B－C)=(B∩C)∪(B∩~C) (补交转换律)=B∩(C∪~C) (∩对∪的分配率)=B (排中律, 同一律)得证.方法三因为A∩C⊆B∩C, A－C⊆B－C, 所以(A∩C)∪(A－C)⊆(B∩C)∪(B－C)|, 整理即得A⊆B, 得证.2 求下列等式成立的充分必要条件(1) A－B=B－A(2) (A－B)∩(A－C)=∅(合计10分: 每小题5分; 正确给出充分必要条件2分, 理由3分)解(1) A－B=B－A方法一两边同时∪A得: A=(B－A)∪A=B∪A ⇒B⊆A; 同理可得A⊆B, 综合可得A=B.另一方面, 当A=B时显然有A－B=B－A. 因此所求充要条件为A=B.方法二∀x,x∈A－B∧x∈B－A⇔x∈(A－B)∩(B－A)⇔x∈∅所以A－B=B－A⇔A－B=∅∧B－A=∅⇔A⊆B ∧B⊆A⇔A=B因此A=B即为所求.(2) (A－B)∩(A－C)=∅⇔(A∩~B)∩(A∩~C)=∅⇔A∩(~B∩~C)=∅⇔A∩~(B∪C)=∅⇔A－(B∪C)=∅⇔A⊆B∪C所以A⊆B∪C即为所求充要条件.说明: 这类题型一般先求出必要条件, 再验证其充分性.三设全集为n元集, 按照某种给定顺序排列为E={x1,x2,…,x n}. 在计算机中可以用长为n的0,1串表示E的子集. 令m元子集A={x i1,x i2,…,x im}, 则A所对应的0,1串为j1j2…j n, 其中当k=i1,i2,…,i m时j k=1, 其它情况下j k=0.例如, E={1,2,…,8}, 则A={1,2,5,6}和B={3,7}对应的0,1串分别为11001100和00100010.(1)设A对应的0,1串为10110010, 则~A对应的0,1串是什么?(2) 设A与B对应的0,1串分别为i1i2…i n和j1j2…j n, 且A∪B, A∩B, A－B, A⊕B对应的0,1串分别为a1a2…a n, b1b2…b n, c1c2…c n, d1d2…d n, 求a k,b k,c k,d k, k=1,2,…,n.(合计15分: (1)3分; (2)12分, 每个结果正确2分, 求解过程4分)解下述运算是二进制数的位运算(1) 01001101(2) a k=i k∨j k, b k=i k∧j k, c k=i k∧¬j k, d k=(i k∧¬j k)∨(¬i k∧j k).说明: 这里c k和d k的求解可以使用主范式求解.c k,d k的真值表如下k kc k⇔m2=i k∧¬j kd k⇔m1∨m2=(¬i k∧j k)∨(i k∧¬j k).。

离散数学结构第6章集合代数第六章集合代数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}在本书所采⽤的体系中规定集合的元素都是集合。

第六章几个典型的代数系统6.1 半群与群引言：简略介绍群论产生的背景1. 图形的对称性如正三角形、正方形（一般地正n 边形）、长方形、 等腰三角形、等腰梯形等；三维空间中的正四面体、 正方体、长方体等都各有自己的对称性。

画图解释：2．用根式求解代数方程的根（1）一元二次方程：20x bx c ++=⇒122b x -±=，。

注：①约公元前2000年即出现二次方程求根问题； ②约公元9世纪时，阿拉伯人花拉子米首次得到上述求根公式。

（2）三次及四次方程的求根公式一般三次方程: 320x ax bx c +++=。

先作变换：用3a x -代替x 后可化成 3x mx n +=（不含二次项）， （*）其中 332,3327a ab a m b n c =-=--。

利用恒等式：333()3()u v uv u v u v -+-=-，把它与（*）比较得：33,3,x u v uv m u v n =-=-=。

由后面两个关于33,u v 的方程可得u x u v v ⎫⎪=⎪⇒=-= （即*方程的解） 以上求解三次方程的公式叫做卡丹公式， 出现在公元1545年出版的著作《大书》中。

关于四次方程的求根公式这里从略，可以肯定的是， 四次一般方程也有求根公式，并且也叫卡丹公式。

（3从1545年之后的近300年间，人们都没能找到五次(当然，这并不排除对 某些特殊的五次及五次以上的方程可以求出它们的根）。

直到1830年由法国人Galois （伽珞瓦）解决，证明出：五次及五次以上的一般方程不存在用加、减、乘、除及开方表示的求根公式，所用方法就是现在已广为接受的群的思想。

可是在当时，很多同时代的大数学家都无法理解和接受他的思想方法。

3．群在其它方面的应用：如编码理论、计算机等。

一．群的定义及简单性质1定义：设,G ⋅是一个具有二元运算⋅的代数系统，如果⋅同时满足（1）结合律：即,,a b c G ∀∈，()()a b c a b c ⋅⋅=⋅⋅总成立；（2）存在单位元（也称为幺元，记为e ），即 ,;a e e a a a G ⋅=⋅=∀∈（3）中每个元素a 都有逆元（记为1a -）：即存在1a G -∈，使得11a a a a e --⋅=⋅=，则称G 关于运算⋅构成一个群。