06第六章集合代数
- 格式:ppt
- 大小:210.50 KB
- 文档页数:16
第六章作业评分要求: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).。
第六章集合代数§1 集合的基本概念集合用大写英文字母标记,A,B,C,…特别地,分别用N、Z、Q、R、C标记全体自然数的集合、全体整数的集合、全体有理数的集合、全体实数的集合、全体复数的集合。
元素用小写英文字母标记,a,b,c,…x∈A:x是A的元素,称x属于A。
x∉A:x不是A的元素,称x不属于A。
列元素法:{a1, a2, …, a n, …}谓词表示法:{x| F(x)}注①集合中的元素每个只写一次②集合中的元素不计排列次序A⊆B:A是B的子集,称A被B包含A B:A不是B的子集,称A不被B包含A=B ⇔A⊆B∧B⊆A:A与B相等A⊂B ⇔A⊆B∧A≠B:A是B的真子集N⊆Z⊆Q⊆R⊆C空集:是任意集合的子集,记为∅。
有限集,无限集n元集,k元子集n元集有2n个子集集合A的幂集P(A)(或2A)全集:E§2 集合的运算并:A∪B ={x| x∈A∨x∈B}交:A∩B ={x| x∈A∧x∈B}差(B对A的相对补集):A-B ={x| x∈A∧x∉B} 对称差:A⊕B=(A-B)(∪B-A)=(A∪B)-(A∩B)绝对补集(简称A的补集):∼A=A=E-A,文氏图:大矩形表示全集E,内部的圆表示不同集合。
例已知24人中,会英语的有13人,会日语的有5人,会德语的有10人,会法语的有9人。
其中,同时会英语和日语的有2人,同时会英语和德语、同时会英语和法语、同时会德语和法语的各有4人;此外,会日语的人不会德语和法语。
求只会英语、日语、德语、法语中一种语言的人数和同时会三种语言的人数。
解:设同时会三种 语言有x 人,只会只会 英语、法语、德语中一 种语言的人数分别为y 1、y 2、y 3人,则根据文氏图可得1231232(4)2132(4)92(4)103(4)24519y x x y x x y x x y y y x x +−++=⎧⎪+−+=⎪⎨+−+=⎪⎪+++−+=−=⎩解出x =1,y 1=4,y 2=2,y 3=3。
第一章,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)⇔⌝AA i(i=1,2,…,s)为简单合取式,则A=A1∨A2∨…∨A s为析取范式 (p∧┐q)∨(┐q∧┐r)∨p A=A1∧A2∧…∧A s为合取范式 (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)集合论是数学的基础,学习集合论有助于理解现代数学的公理化方法。
(2)集合论为应用领域提供建模和分析工具。
本讲学习集合论的基础知识,包括如下4个部分:1.集合代数:若干基本概念和集合运算及其运算定律。
2.二元关系:用集合定义二元关系,二元关系的分类和性质。
3.函数:用二元关系定义函数,函数的分类和性质。
4.ZFC公理系统:学习由Zermelo和Frankel等人所设计的10组集合论公理,并用以证明某些对象的分类是集合。
1.集合的概念和表达式我们所能感知的客观事物和思想中产生的观念,是我们的认知对象(object,entity)。
我们根据对象的各种共同性质把对象划分为不同的类(class)。
在数学中,我们通常把一个类称为集合(set),其中的对象称为该集合的成员(member)或者元素(element)。
通常用大写字母表示某集合,小写字母表示该集合中的元表示x是A的成员,读作“x属于A”。
这个素。
对于任何集合A,我们用x A成员隶属关系是集合论中的一个基本关系,可以定义其它的关系,包括两个集合相等、包含,等等。
在现代数学中,“集合”被选作为一个基础性概念,用以定义其它数学概念。
作为整个数学体系的第一概念,它自身是没有定义的,也是不可能被定义的。
尽管集合概念没有通用的定义,每个集合实例都是有严格定义的。
我们有两种定义集合实例的方法,即枚举法和概括法。
ZFC公理系统严格地描述了这两种定义集合的方法。
这里我们先对两种定义方法做直观的描述。
枚举法:也称列举法,明确地将一个集合的所有元素(的名字)排列在花括号内,元素之间用逗号分隔。
,V 中加法的定构成K 上的线性空向量组的线性相关与线性无关向量组的线性等价;极大线性无关组.,s α,又给定数域,s k ,称s s k k α+为向量组12,,,s ααα的一个4(线性表出内一个向量组,s α,设β是V 内的一个向如果存在K 内s ,s k ,使得122s s k k ααα+++,,,s α线性表出.向量组的线性相关与线性无关) 内一个向量组12,,αα,s k ,使得s s k α+=,s α线性相关;若由方程s s k α+=0s k ===则称向量组,s α线性无关.命题3 设12,,s V ααα∈,则下述两条等价:12,,s ααα线性相关;某个i α可被其余向量线性表示证明同向量空间.线性等价) 给定,r α (,s β (Ⅰ)中任一向量都能被线性表示,则称两向量组(极大线性无关部分组,s α,如果它有一个部分组,,,r i ααα满足如下条件,r i α线性无关;、原向量组中任一向量都能被,r i α线性表示,则称此部分组为原向量组的一个极大线性无关部分组.由于在向量空间中我们证明的关于线性表示和线性等价的一些命题中并没于是那些命题在线性空间中依然成立一个向量组的任一极大线性无关部分组中均包含相同,,n ε和1,,n ηη是两组基2121212122221122,,.n n n nn n n nn n t t t t t t t εεεεηεεε++++⎪⎨⎪⎪=+++⎩ 11121212221212,)(,,,)n n n n n n nn t t t t t t tt t ηεεε⎛⎫ ⎪ ⎪= ⎪ ⎪ ⎪⎝⎭. 我们称矩阵111212122212n n n n nn t t t t t t T tt t ⎛⎫ ⎪ ⎪= ⎪⎪⎪⎭,,n ε到1,,n ηη的过渡矩阵.6 设在n 维线性空间V/K 中给定一组基12,,,n εεε.T 是212,,,)(,,,).n n T ηηεεε=,n η是V/K 若12,,,n ηηη是线性空间,n η线性无关考察同构映射nK V ασ,:→,构造方程122)()(n k k ησηση+++1,2,,)n ,22)n n k k ηη++0n n k η+=,0n k ==⇒,()n σση线性无关.,()n ση构成了过渡矩阵的列向量,所以过渡矩阵可逆;若过渡矩阵可逆,则构造方程122n n k k ηηη+++=,(1,2,,)K i n =,作用,得到112()((n k k k σησηση++,120n k k k ⇒====.证毕向量的坐标变换公式;nK 中的两组基的过渡矩阵,n ε和12,,,n ηηη,又设,n ε下的),n a ,即1212(,,,)n n a a a εεε⎛⎫ ⎪ ⎪= ⎪ ⎪ ⎪⎝⎭,,,n η下的坐标为,,)n b ,即1212,,,)n n b b b ηη⎛⎫ ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭.现在设两组基之间的过渡矩阵为T,即1212(,,,)(,,,).n n T ηηηεεε=2n a ⎪⎪⎪⎪⎭,2n Y b ⎪= ⎪ ⎪ ⎪⎝⎭,12[(,,)]n Y T Y εεε=.122122212,),,,),(,,,).n n n n n nn a a a a a ε= 和122122212,),,,),(,,,).n n n n n nn b b b b b η=1212(,,,)(,,,).n n T ηηηεεε=的第i 个列向量分别是i η在基12,,,n εεε下的坐标.,n ε和1,,,n ηηη看作列向量分别排成矩阵111212122212n n n n nn a a a a a a A aa a ⎛⎫⎪ ⎪= ⎪ ⎪ ⎪⎝⎭;111212122212n n n n nn b b b b b b B b b b ⎛⎫⎪ ⎪= ⎪ ⎪ ⎪⎝⎭, AT =,将A 和B 拼成2n n ⨯分块矩阵()|A B ,利用初等行变换将左边矩化为单位矩阵E,则右边出来的就是过渡矩阵T,示意如下:)|()|(T E B A −−−→−行初等变换.ε为W ,r1,,r r εε+的一个子空间假设即可.二、子空间的交与和定义13 设,t V α∈}22|,1,2,,t t i k k k K i t αα+++∈=称为由12,,,t ααα生成的子空间,记为12(,,,)t L ααα生成的子空间的维数等于12,,,t ααα的秩.) 设12,V V 为线性空间V/K 的子空间,定义2{V v =∈称为子空间的交; 21{V v +=+称为子空间的命题9 12V V 和1V +证明:由命题4.7,只需要证明2V 和1V +12,V V αβ∈,则1,V αβ∈,,αβ12,V V αβ+∈,于是12V V αβ+∈,12V V 关于加法封闭;2V ,k ∈12,kv V kv V ∈∈,于是12kv V V ∈,12V V 关于数乘封1,V V β∈+111222,,,V V αβαβ∃∈∈,21,αββ=2V ,则,,m V 是2m V V 和m V +均为的子空间.维数公式.1 设V 为有限维线性空间,2dim()V .,12dim()V V r =,2V 的一组基,r ε(若2V V =0,则基为空集),将此基分别扩充为12,V V 的基1212,,,,,,,r s r εεεααα-, 1212,,,,,,,r t r εεεβββ-,1212,,,,,,,,,r s r t r εαααβββ--是12V V +见12V V +中的任一向量都可1212,,,,,,,,,r s r t r εαααβββ--线性表出.事实上,V γ∀∈12γ+,其中1122,V V γγ∈∈,而111221122,r r r r s s r k k k k k k γεεεααα++-=+++++++ 211221122.r r r r t t r l l l l l l γεεεααα++-=+++++++,i j k l K ∈被121212,,,,,,,,,,,r l r t r εεεαααβββ--线性表21212,,,,,,,,,,r l r t r εεαααβββ--线性无关即2211220s r s r t r t r a a b b b ααβββ----++++++=,11221r r s r s r k a a a V εααα--+++++∈,11222t r t r b b b V βββ------∈,112212r r s r s r a a a V V εααα--++++∈,记为,r ε线性表示,设22r r h h αεε++,12211220r r t r t r h h b b b εεβββ--+++++++=,12,,,,,r t r εβββ-是2V 的一组基,所以线性无关,则12120r t r h h h b b b -========,12120r s r k k a a a -========,21212,,,,,,,,,,r s r t r εεαααβββ--线性无关12,,,t V V 都是有限为线性空间V 的子空间,则:1212)dim dim dim t t V V V V V V +++≤+++.作归纳.,m V 是V ,,1,2,,m i i V i m αα+∈=.记为2m V V ⊕⊕⊕或1mi i V =⊕.,,m V 为数域K 上的线性空间V 上的有限为子空间,则下述四m V +是直和;零向量表示法唯一;1ˆ(){0},1,2,,im V V V i m ++++=∀=;1212dim()dim dim dim m m V V V V V V +++=+++.: 1)2)⇒显然.1)⇒设1212,m m ααααβββ=+++=+++则(m α+-1,2,,m ,21m V V V +++是直和个,1i i ≤≤1ˆ(){0}im V V V ++++≠存在向1ˆ()i im V V V V ∈++++,于是存在j V ,使得1ˆi m αααα=++++.由线性空间的定义,1ˆ()iim V V V V α-∈++++,()()0m αααα+-++=+-=,与零向量的表示法唯一矛盾1ˆ(){0},1,2,,i im V V V V i m ++++=∀=.2)⇒若2)不真,则有10i m ααα=++++,1,2,,)m 且0i α∃≠.于是1ˆˆ()i m i im V V V V αα+++∈++++,成立.作归纳.由维数公式得到121212dim dim dim()dim dim V V V V V V =+-=+.11)dim(),m m m V V ---+111垐()(){0}i m i i m V V V V V V V -++++⊆++++=由归纳假设,可以得到1212dim()dim dim dim m V V V V V +++=+++3)⇒,1i i m ∀≤≤,都有1112垐())dim()dim()dim(i m i i m V V V V V V V V V ++++=+++++-++1ˆ(){0},1,2,,im V V V i m ++++=∀=.证毕.推论 设12,V V 为V 的有限维子空间,则下述四条等价: 12V V +是直和; ii)零向量的表示法唯一; iii)2{0}V V =;12dim()V V +=二、直和因子的基与直和的基设1m V V V V =⊕⊕,则,m V 的基的并集为,r ii ε是i V 的组基,则V 121{,,,}r im i i i i εεε=线性表出.又1dim dim i m V r r =+,由命题4.5,它们线性无关,于是它们是V 的一组基. 证毕. 三、补空间的定义及存在性定义 设1V 为V 则称为1V 的补空间.命题 有限维线性空间的任一非平凡子空间都有补空间证明: 设V ,r ε,将,,)n ε,则有12V V =+,且,即2V 是1V.s n AX ⨯的线性映射.上连续函数的全体,它是R 上的线性空间,sin 2,,sin ),x nx,cos).nx,AX.单线性映射(monomorphism)满线性映射(endmorphism)fα().α∈U'/kerγ.于是=,fα)('),t V α∈22()(t k k ϕαϕα+++,1122()t t k k k ϕααα+++t t k α+=则120t k k k ====,ii)成立;iii)若取组基12,,,n εεε,则,()n ϕε而im ϕ中任意向,()n ϕε线性表出12(),(),,()n εϕεϕε构成成立;⇒i)由/ker im U ϕ≅dimker dimim ϕ=即有ker ϕ=。