关闭

关闭

关闭

封号提示

内容

首页 离散数学

离散数学

离散数学

王乐乐 2010-12-19 评分 0 浏览量 0 0 0 0 暂无简介 简介 举报

简介:本文档为《离散数学pdf》,可适用于自然科学领域,主题内容包含离散数学    当前位置: 离散数学在线教程                      首页 学习空间    课程教学离散数学绪论集合论初步关系与映符等。

离散数学    当前位置: 离散数学在线教程                      首页 学习空间    课程教学离散数学绪论集合论初步关系与映射代数系统基础无限集重言式布尔代数及应用群论基础半群图论基本概念图的矩阵表示Euler,Hamilton图通路回路连通性命题及连接词命题公式基本逻辑等价式离散试卷习题讲解离散问题(集合论初步)离散问题(函数无限集)离散问题(二元关系)离散问题(代数系统)离散问题(图论)指导老师:李志林http:wwwjsipteducnycjyxxxxuexikongjianlssxlsxshtm::离散数学绪论离散数学绪论.计算机科学与离散数学计算机科学是与计算机软件硬件有关的各学科的总称,特点是离散性,离散数学是研究离散量的结构及其相互间关系的一门学科。【实例】布尔代数({,},,*,~)在电子科学和数理逻辑中可得到具体解释。【实例】计算机中鼓轮的设计用到图论知识。.离散数学的特征()研究离散量()重视能行性的研究.离散数学的内容http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoanxulunhtm::集合论初步集合论初步第一节集合理论基础.集合的概念一般认为集合是一些确定的对象的全体对象称为元素若a是集合A的元素则记为aA集合的表示方法:()列举法:列举出元素。()描述法:把元素的共同性质描述出来。()谓次表示法:{x|P(x)}(借助一些逻辑记号)常见的集合:()空集:{}或()单元素集合:只含一个元素()全集:所考虑的对象的全体()常用记号:N,Z,Q,R等.集合的关系【DEF】若集合A,B的元素相同则称A,B是相等的记为A=B否则A和B是不相等的记为AB【DEF】若aA一定有aB则称A是B的子集记为若但是AB则称A是B的真子集记为.集合的运算【DEF】集合A与B的交集AB={x|xA或xB}【DEF】并集AB={x|xA和xB}【DEF】A,B是分离的若AB=【DEF】集合A对B的差AB={x|xA和xB}【DEF】集合A的补集为全集E与A的差记为A’【DEF】集合A与B的对称差AB=(AB)(BA)http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoanjhlhtm(of)::集合论初步集合的运算律如下:()交换律AB=BAAB=BA()结合律(AB)C=A(BC)()分配律A(BC)=(AB)(AC)()等幂律AA=AAA=A()零一律AE=AA=AA=AE=E()互补律AA’=AA’=EA’’=A()DeMorgan律(AB)’=A’B’()吸收律A(AB)=AA(AB)=A运算律的特点:()对称性()对偶性第二节幂集n元有序组Descartes积.幂集【DEF】由A的所有子集组成的集合称为A的幂集记为P(A)或【DEF】集合A中元素的个数称为A的基数记为|A|【TH】A是有限集则||=【证明】设|A|=n则||=【TH】(包含排除原理)A,…,An是有限集则|AAn|=【证明】数学归纳法。【思考】()有一个班级个学生第一次考试有人得优第二次考试有人得优两次均未得优有人问多少人两次均得优?()求{a}幂集的幂集。()求到间能被,,,中任一个整除的整数个数。.n元有序组【DEF】按一定次序排列的两个客体a,b组成的序列称为序偶记为(a,b)【DEF】若a=ba=b则(a,a)=(a,b)【DEF】按一定次序排列的n个客体a,a,,an组成的序列称为n元有序组记为(aa,an)http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoanjhlhtm(of)::集合论初步【DEF】若ai=bi(i=,,,n)则(a,a,,an)=(b,b,,bn).Descartes积【DEF】集合A,B的Descartes积(又称为叉积)为AB={(a,b)|aA,bB}A称为前集B称为后集。【DEF】集合A,A,,An的Descartes积为AAn={(a,a,,an)|aiAi}【注记】()ABBA()AA记为A【思考】()A={,}B={,}求AB,AP(A)()判断下列各式是否正确:(AB)(CD)=(AC)(BD)(AB)(CD)=(AC)(BD)http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoanjhlhtm(of)::关系与映射关系与映射第一节关系的概念关系的定义【DEF】AB的子集R称为A到B的一个关系。当(a,b)R时称a与b有关系R记为aRbR的定义域为D(R)={a|存在b使得(a,b)R}R的值域为C(R)={b|存在a使aRb}A到A的关系R称为A上的关系。A上的关系R={(a,a)|aA}称为A上的恒等关系。【DEF】AA…An的子集R称为由A,A,…,An确定的n元关系。关系的表示一、关系图()A到B的关系图采用一般的映射图。()A上的关系图是图论中的有向图。二、关系矩阵设A={a,a,…,am}B={b,b,…,bn}z则A到B的关系R的矩阵为第二节关系的运算关系的补、并、交关系是集合故可以进行集合的运算设R、S是集合A到B的关系则http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoanrelativehtm(of)::R′=ABRRS={(a,b)|(aRb)(aSb)}复合关系【DEF】R是A到B的关系S是B到C的关系则R与S的复合关系为={(a,c)|aA,cC有bB使aRb,bSc}【TH】复合运算满足结合律。【DEF】R是A上的关系则R的幂为【TH】关系的逆【DEF】设R是A到B的关系则B到A的关系R~={(y,x)|(x,y)R}称为R的逆关系。【TH】第三节关系的性质本节讨论A上的二元关系的性质。【DEF】R是上的关系对每个a均有aRa则R称为自反关系(reflexive)【DEF】若对每个a均有则R是反自反的。【DEF】若(a,b)R(b,a)R则R称为对称的(Symmetric)【DEF】若xRy且yRxx=y则R称为反对称的(Antisymmetric)【DEF】若xRy,yRzxRz则R称为传递的。【注记】可以从关系图关系矩阵判断关系的性质R是自反的关系图中每点有环关系矩阵d的主对角元均为R对称关系图中边成对出现关系矩阵是对称阵。【思考】()判断A上的空关系Ф全关系AA恒等关系I的性质。()设A={,,,}写出关系R使得R不是自反的也不是反自反的。第四节关系的闭包关系与映射http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoanrelativehtm(of)::关系与映射【DEF】R是A上的关系若有另一个关系R’使得()R’是自反的(对称的传递的)()R’包含R()对任一个自反关系(对称关系传递关系)R’’若R’’包含R则R’’包含R’那么R’称为R的自反闭包(对称闭包传递闭包)记为r(R)(s(R),t(R))【TH】设R是A上的关系则r(R)=RII是A上的恒等关系。【TH】s(R)=RR~【TH】【TH】设|A|=n则【注记】闭包运算可以转化为矩阵运算。【思考】()A={}R={()()()}求r(R)s(R)t(R)()N上的关系为R={(,),(,),…,(n,n),…}求r(R)s(R)t(R)第五节次序关系偏序关系【DEF】设A是一个集合R是A上的关系R是自反的反对称的传递的则R称为A上的偏序(半序)()偏序R常记为A是R的偏序集记为(A,)【注记】()偏序关系的实质在于建立A的元素之间的可比结构。()偏序关系可用Hasse图(一种下行图)表示。【DEF】(A)是偏序集对任意a,bA必有aRb(ab)或bRa(ba)则称为全序。【DEF】设(A)是偏序集B是A的子集()若B中元素X比B中任何元素都要“大”(“小”)则X称为B的最大元(最小元)()若B中没有比X更大(更小)的元素则X称为B的极大元(极小元)http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoanrelativehtm(of)::关系与映射()集合A中比B中元素都大(小)的元素称为集合B的上界(下界)()B的最大的下界称为下确界记为GLB(B)B的最小的上界称为上确界记为LUB(B)【注记】()最大元最多一个极大元可能有多个。()最大元必是极大元反之不然。()最大元必是上确界反之不然()最大元极大元等均可从Hasse图中看出来。【思考】集合A={}A上关系R={(x,y)|x,yA且x|y}且B={}的最大元最小元极大元极小元上下确界。拟序【DEF】若A上的关系R是反自反的传递的则R称为A上的拟序记为<【TH】若R是A上的拟序则R是反对称的。【注记】()偏序是拟序地扩充拟序是偏序的缩减。()偏序拟序均称为次序。第六节相容关系【DEF】R是A上关系R是自反的对称的则R称为A上的相容关系。【例】设集合A={cat,teacher,cold,desk,knife,by}R={(x,y)|x,yA且x,y有相同的字母}则R是相容的。【DEF】设AФS={S,S,…,Sn}Si是A的非空子集且SS…Sn=A则S称为A的覆盖若又有SiSj=Ф(ij)则称为A的划分。【例】写出A={,,}的所有划分。【DEF】R是A上的相容关系Cr是A的子集Cr中任意的两个相容若ACr中没有元素与Cr中所有元素相容则Cr称为A的极大相容类。http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoanrelativehtm(of)::关系与映射【例】求例中的极大相容类。【DEF】A的极大相容类的集合称为A的完全覆盖。【TH】{A…,An}是A的一个覆盖则R=AA…AnAn是A上的相容关系。【TH】A上的相容关系R与完全覆盖是一一对应的。【例】求A={,,}上的覆盖л={{,},{,}}产生的相容关系R第七节等价关系【DEF】R是A上的的关系若R是自反的对称的传递的则R称为等价关系。【注记】()等价关系的实质在于给A建立分类结构。()等价关系的关系图呈一块或若干块。【DEF】设R是等价关系a={x|xAaRx}称为由a形成的等价类。等价类的集合{a|aA}称为A关于R的商集记为AR【TH】A上的等价关系R决定了A的一个划分且划分为AR【TH】A的任一个划分确定了A上的一个等价关系。【思考】()求I上的同余关系(为模的)R={(x,y)|x,y除以的余数相同}的商集。()求A={,,}上的所有等价关系。()A={,,,}在AA上定义等价关系R:(u,v)R(x,y)当且仅当uy=vx求由R确定的划分。()对集合A求AAAI(I是恒等关系)第八节映射(函数)函数的概念【DEF】f是X到Y的关系对任意的xX存在唯一yY使(x,y)f则f是X到Y的函数。当xfy时记为y=f(x)定义域D(f)=X值域C(f)={y|存在xX使(x,y)f}【DEF】f:XY是函数()若f(X)=Y则f称为满射()若对任意的a,b,abfhttp:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoanrelativehtm(of)::关系与映射(a)f(b)则f称为单射()若同时有()()则称为双射。函数的运算【DEF】设f:XYg:YZ是函数则gοf={(x,z)|xXzZ存在yY使y=f(x)z=g(y)}称为X到Z的关于f,g的复合函数。【DEF】设f:XY是双射则f~:YX也是双射称为f的逆函数。记为f【注记】()函数复合gοf与关系复合顺序相反。()函数作为关系也具有关系的性质。【思考】()A={,,}B={a,b}求A到B的所有函数的集合。()设f:II使f(x)=x,求f(f(x))和f的逆函数。http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoanrelativehtm(of)::代数系统第一节代数系统的基本概念.代数系统的一般概念【DEF】设A是非空集f是An到A的函数,则f是A上的n元运算表示An中元素在f下的运算结果。F常记为*ΔO等。【注记】计算机上常用的运算有,,*,,^,AND,OR,SQR等。【注记】二元运算习惯上记为【DEF】设是A上的运算,则叫代数系统。【DEF】设是代数系统B是A的子集若也是B上的封闭运算则称为的子代数系统【例】常见的代数系统:普通代数,逻辑代数(开关代数),集合代数【例】F是文件集P,P,…,Pn是系统程序则(F,P,P,…,Pn)是代数系统。.代数系统的基本性质本段讨论只具有二元运算的代数系统()结合律【DEF】(S,*)是代数系统S中任意x,y,z成立等式(x*y)*z=x*(y*z)则称*具有结合律。【注记】连续的运算不必加括号【注记】若(S,*)有结合律则其子代数也必有结合律此为遗传性。()交换律【DEF】(S,*)是代数系统S中任意的x,y成立等式x*y=y*x则称*具有交换律。【注记】交换律也具有遗产性。代数系统http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoandsxthtm(of)::代数系统()分配律【DEF】(S,*,)是代数系统对S中任意的x,y,z对有第一分配律:x*(yz)=(x*y)(x*z)对有第二分配律:(yz)*x=(y*x)(z*x)*对具有分配律:同时满足第一和第二分配律【例】(R,,)中对有分配律反之不然。【例】GCD,LCM分别表示自然数集上的求最大公约数最小公倍数运算则运算GCD,LCM是相互可分配的。【注记】可类似定义其他运算律如消去律吸收律幂等律()单位元(幺元)【DEF】*是S上的二元运算,若存在元素S中元素l使对任意的x有l*x=x*=x则l称为代数系统(S*)的单位元常记为【TH】若代数系统(S,*)有单位元则必唯一。【注记】若存在r有x*r=x则称为右单位元可类似定义左单位元。【例】求(R)(R)({断通}并联),({全体n阶矩阵})({A的幂集})等代数系统的单位元。()零元素【DEF】若*是S上的二元运算存在元素z使对任意的x有z*x=x*z=z则z称为代数系统(S*)的零元素常记为O【TH】若代数系统(S*)存在单位元l和零元z且S至少有两个元素则l不等于z【注记】可定义左零元和右零元。【例】求({a,b,c},*)的单位元和零元*abcaabchttp:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoandsxthtm(of)::代数系统bbbbccbc()逆元素【DEF】设(S,*)有单位元l对S中元素a若存在元素b使a*b=b*a=l则b称为a的逆元素常记为a【TH】设代数系统(S,*)有单位元有结合律每个元素有逆元则每个元素的逆元时唯一的。【例】设(R,#)中运算#定义为:对实数a,b有a#b=abab()求的逆元。()试讨论该代数系统的性质。.同构与同态(一)同构的概念【实例】({,}布尔加)({真假}或)({浅深}颜料合成*)结构相同。或假真*浅深假真假真真真浅深浅深深深【DEF】设有代数系统(X,*),(Y,)运算*,是同阶的(称为同类型的)不妨设为元运算若存在双射f:XY使得对任意的x,y有下式成立:f(x*y)=f(x)f(y)(称为同态公式)则称(X,*)与(Y,^)同构记为(X,*)~(Y,)【注记】一般的同态公式(*是n元运算)【例】证明【例】证明下列两代数系统是同构的http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoandsxthtm(of)::代数系统*^赵钱孙李赵钱孙李赵钱孙李钱赵赵孙钱李李孙赵钱孙李【TH】设代数系统(X*)与(Y,)同构()若*有结合律,则也有结合律。()若*有交换律则也有交换律。()若l是*的单位元则f(l)是的单位元。()若O是*的零元则f(O)是的零元。()若X中元素x有逆元x则Y中元素f(x)也有逆元且【证明】只证()其余类似可证。设a,b是Y中任意元素则存在X中元素x,y使a=f(x)b=f(y)于是有即也有交换律。得证。【注记】设(X*)与(Y*)同构(即两个运算均满足同态公式)则若*对有分配律则*对也有分配律。【注记】同构映射保持了除符号外的一切特征性质(平面镜射)【TH】设X={代数系统}则X上的同构映射是一个等价关系。(二)同态的概念【DEF】设有代数系统(X*)(Y)若存在映射f:XY使得对X中元素x,y有同态公式成立。f(x*y)=f(x)f(y)(即映射f是保持运算的)则称f是(X*)到(Y)的同态映射称代数系统(X*)和(Y)是同态的记为(X*)~(Y)【注记】若f是单射则f称为单同态映射若f是满射则f称为满同态映射若f是双射则f就是同构映射。【注记】同态映射粗线条地保持了原代数系统的部分性质。【例】证明(I)~({正负零}*)其中*定义为http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoandsxthtm(of)::代数系统*正负零正负零正负零负正零零零零【证】作f:I{正负零}使得f(n)=正(n>)f(n)=负(n<)f(n)=(n=)则对任意整数m,n有f(mn)=f(m)*f(n)故得证。【例】证明(N)~({})其中N={}是关于模的剩余类集模加定义为:对i,j{,,}有ij=ij【提示】构造映射f:NN使得f(i)=i【TH】设代数系统(X*)与(Y,^)同态()若*有结合律则^也有结合律。()若*有交换律则^也有交换律。()若l是*单位元则f(l)是的零元。()若O是*零元则f(O)是的单位元。()若X中元素x有逆元x则Y中元素f(x)也有逆元且【证明】同TH具体参见西安交通大学《离散数学》P这些性质只是单向保留的。【TH】设f是(X*)到(Y)的同态映射记f(X)={y|y=f(x)对任意}f(X)是Y的子集称为f的同态象则(f(X),^)是(Y)的子代数系统。【提示】只要证明在f(X)上是封闭运算事实上f(a)^f(b)=f(a*b)f(X)(三)一般同余关系与自然同态()一般同余关系【DEF】设(A,*)是代数系统R是A上的一个等价关系对任意的a,bA若aRx,bRy必有(a*b)R(x*y)则此时称关系R为集合A上的关于运算R的同余关系。由此同余关系(首先是等价关系)把A划分成的等价类称为同余类。【例】自然数集上的同余关系是特例如http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoandsxthtm(of)::代数系统mod(),mod()而mod()同余类为,,,()自然同态【DEF】设R是代数系统(X*)上的同余关系由R诱导的划分形成的商集是XR定义XR上的运算为:对任意的x,yXR有xy=x*y于是(XR)是一个代数系统称为(X*)的商代数。【TH】商代数(XR)是(X*)的同态象。可见有同余关系的代数系统到商代数的同态是自然存在的于是(X*)到(XR)的称为自然同态如前例f:NN使得f(i)=i就是自然同态。.特定的代数系统{()群环域域(A*)à*有交换律除环(A*)à{有单位元非零元关于*可逆环(A*)à{有结合律*对可分配交换群(A)àhttp:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoandsxthtm(of)::代数系统{有交换律群(A)à{有单位元每个元关于可逆半群(A)(有结合律)【例】(R)是实数域。(Rnn)是矩阵环。()格布尔代数代数系统(L)格布尔代数代数系统(B~*)布尔代数【例】开关代数系统({}~*)是最重要的布尔代数模型。http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoandsxthtm(of)::无限集无限集第一节无限集的性质【DEF】设集合A到B存在双射f则称A,B等势。记为A~B【例】NN~N【例】R~(,)但R与Q不等势。【DEF】与N等势的无限集称为可列集有限集与可列集称为至多可列集。【TH】A为可列集当且仅当A的元素可以排列为A={a,a,,an,}【TH】任意的无限集一定含有可数子集。【TH】任意的无限集一定含有与其等势的真子集。【注记】此为无限集的本质因而经常用来作为无限集的定义。【TH】可数集的无穷子集仍为可数集。【例】可数个可数集的并集是可数集。【例】设A,B是可列集则AB是可数集。【例】设A,B是可列集则AB是可数集。第二节集合的基数【DEF】集合的基数是一种衡量集合大小的标准记为|A|常见的基数有()|{}|=()|{,,,n}|=n()|N|=阿列夫()|R|=阿列夫【TH】实数集合R不可列。(Cantor,)【例】(,)(,)不可列。http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoaninfinitehtm(of)::无限集【DEF】若存在A到B单射则称|A||B|又若不存在双射则称|A|<|B|【TH】(CantorSchroderBernstein)若|A||B|,|B||A|则|A|=|B|【例】利用定理证明,~(,)【TH】若A为有限集则|A|<阿列夫<阿列夫【TH】Cantor设A是任意的集合则|A|<|A的幂集|证明参考西安交通大学“离散数学”该定理表明无限集的大小是永无尽头的。http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoaninfinitehtm(of)::        重言式1基本概念  DEF恒取真值的命题公式称为重言式(永真函数Tautology).恒取假值的命题公式称为矛盾式(永假函数Contradication).至少存在一个成真指派的公式叫可满足式。至少存在一个成假指派的公式叫非重言式。例下列公式是重言式:PP(PQ)(QP)(PQ)PQ.2逻辑等价关系DEF2对命题公式αβ若对任意的指派π均有α(π)=β(π)则称αβ是逻辑等价的(等价重言式)记为αβ也常记为α=β.TH1αβ当且仅当αβ是重言式。证明:利用重言式定义直接证明。判断αβ是否逻辑等价的方法:(1)真值表法(DEF2或TH1)。http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoancyshtm(of)::(2)形式推理。3逻辑蕴含关系DEF3对命题公式αβ若对任意的指派π当α(π)=1时必有β(π)=1则称α逻辑蕴含β(蕴含重言式)记为αβ。例(PQ)(QR)PR(PQ)QPTH2αβ当且仅当αβ是重言式。证明:利用重言式定义直接证明。TH3逻辑蕴含关系是所有命题公式集合上的偏序关系即有:(1)αα(2)若αββα则α=β(3)若αββγ则αγ.判断αβ是否逻辑蕴含的方法:(1)真值表法(DEF3或TH2)。(2)形式推理。(3)分析指派法。http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoancyshtm(of)::注记:(1)是命题公式中的运算符而是命题公式间的关系符。(2)真值表法是一种麻烦乏味的方法我们真正的目的在于“推理”。http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoancyshtm(of)::布尔代数的应用布尔代数的应用.布尔代数的公理化定义【DEF】设(B’*)是一个代数系统其中’是集合B上的一元运算*是B上的二元运算集合B中有不同元素且满足下列运算律(公理)()交换律ab=baa*b=b*a()分配律ab*c=(ab)*(ac)a*(bc)=a*ba*c()零一律a=aa*=a()互补律aa’=a*a’=则(B’*)称为一个代数系统。【注记】()B中的分别称为零元单位元。()规定求补’优于求积*(或记为)求积*优于求和故abc含义为a(bc)()公理有对偶性(即*互换互换仍成立)()有的体系包括结合律但它不是独立的。【例】下列代数系统是否是布尔代数:()开关代数({}’)()集合代数({集合A的幂集}ˉ)()({}’GCDLCM)布尔代数(B’*)的性质:设a,b,cB()等幂律aa=a,a*a=a()有界律a=,a*=()吸收律aa*b=a,a*(ab)=a()DeMorgan律(ab)’=a’*b’,(a*b)’=a’b’【例】化简下列布尔函数()f=xyz’xyzxy’z()f=((xy’)y)’x’(yz)w()f=x’y’zxy’zxy’z’x’yz【提示】可用定理及性质化简也可用图域(卡偌图)法。x’y’z’x’y’zx’yzx’yz’xy’z’xy’zxyzxyz’上表表示三变元图域每个方格表示一个最小项表示有补表示无补相邻格相加可消去一个变元步骤为:把布尔函数化为析取范式在每个最小项对应的方格中标上http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoanbuerhtm(of)::其余标上寻找标上的相邻格进行消元。.布尔代数在逻辑线路中的应用()线路的布尔表达式本段讨论的线路是指一些接点通过串联并联构成的二端网络(不考虑桥联)例如:x’x*yxy线路布尔式的构造原则:串联对应布尔式中的积并联对应布尔和。()线路的等效接通条件相同的线路称为等效线路找等效线路的目的是化简线路使线路中包含的接点尽可能地少。【例】化简下列线路线路的布尔表达式为f(x,y,z)=xyx’zyz=xyx’zyz(xx’)=xyx’z【思考】试写出上述线路的真值表。()线路的设计利用布尔代数可设计一些具有指定性质的节点线路数学上即是按给定的真值表构造相应的布尔表达式理论上涉及到范式理论但形式上并不难构造。【例】设计一个含三个开关的信号线路使两个或两个以上开关闭合时信号灯亮。xyzf设三个开关为x,y,z布尔表达式f的真值表如上f的析取范式为f=x’yzxy’zxyz’xyz(写出对应的最小项对应有补对应无补)上式化简为:f=xy(xy)z布尔代数的应用http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoanbuerhtm(of)::布尔代数的应用【思考】设计一个楼道路灯线路一个楼梯口路灯由楼上楼下两个开关控制无论扳动楼上开关还是楼下开关均使路灯由亮变灭或由灭变亮。http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoanbuerhtm(of)::第三节群论基础第三节群论基础群的基本概念DEF:设(G,*)是含幺半群若G中每个元素均有逆元则(G,*)叫群若*是可交换的则(G,*)称为可交换群(Abel群)若(G,*)的子代数系统(H,*)也是群则(H,*)称为(G,*)的子群。注记:群还有一些等价的其他定义。注记:群是应用最广泛的代数系统之一有许多特殊的群如循环群有限群置换群等等。例:下列代数系统(I)(R{})(Rnn,),({A的幂集})({})({})({所有函数}函数复合运算)({前后左右}左转度运算)(I)({A的幂集}对称差运算)是不是群?群的基本性质()设(G,*)是群则*有消去律。()群中不可能有零元。()群(G,*)中除单位元外无等幂元。()群(G,*)中一元一次方程a*x=b,y*a=b有唯一解且解为注记*:该性质常作为群的定义。()设(G,*)是一个群则对任意的元素a,bG,有()设(G,*)是有限群集合G的元素个数为n则在*的运算表中每一个元素在每行每列中出现且只出现一次。注记*:运算表中每行(列)的元素均为集合G中元素的一个排列(称为置换)。()设(G,*)是一个群H是G子集如果有则(H,*)是(G,*)子群。()设(G,*)是有限群H是G子集H为非空集则代数系统(H,*)是(G,*)子群的充分必要条件是http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoanqljchtm::第二节半群第二节半群.半群概念【DEF】设(S*)是代数系统*是S上的二元运算若*有结合律则(S*)称为半群若*还有交换律则(S*)称为可换半群(S*)的子代数称为子半群。【例】(I)(N)(Rnn,),({A的幂集})({})({})({所有函数}函数复合运算)({前后左右}左转度运算)等代数系统均为半群而其中的(Rnn,)不是可换半群(I)不是半群。.循环半群()元素的幂设(S*)是代数系统x的幂定义为()循环半群若半群(S*)中存在元素使得对任意均有则(S*)称为循环半群a称为生成元。【思考】上例中那些半群是循环半群?.含幺半群(单元半群)【DEF】含有单位元的半群(S*)称为含幺半群(又叫“独异点”)【例】(计算机形式语言中的)自由含幺半群V是非空有限字符集合(字母表)字符串是V上的n元序组长度为零的序组记为字符串集合记为V在V上定义“”运算(并置运算)对则()是自由含幺半群【注记】含幺半群(S*)的运算表中任意的两行两列是不同的。【DEF】设(S*)是含幺半群则其含幺子代数系统叫子含幺半群又若含幺半群(S*)中存在元素使得对任意均有则(S*)称为循环含幺半群【例】(N)是循环含幺半群而({})是其子含幺半群。【注记】循环含幺半群是可换半群。【注记】可换含幺半群中的等幂元全体全体构成子含幺半群。http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoanbanqunhtm::图论图论千言万语不及一张图F哈拉里第一节图论基本概念图论起源于Konigsberg城Pregel河上的七桥问题年Euler解决了这个问题并设计了十五桥问题。年Hamilton提出的环游世界问题是一个理论上尚未完全解决的图论问题。如今图论在计算机科学工程领域社会科学中具有广泛的应用。本课程将介绍图的基本知识和树的理论。http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoantulunhtm(of)::图论.图的模型举例()计算机算法框图如计算()甲烷族碳氢化合物CnHn的结构图。A上的关系图偏序的Hasse图也是图。http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoantulunhtm(of)::图论.图的基本概念【DEF】V是点集E是边集f:EVV则称系统G=(V,E,f)为有向图。简记为G=(V,E)【DEF】不考虑边方向的图为无向图。【注记】()n个顶点(结点)m个边的图称为(n,m)图(n阶图)()(n,)图称为空图。()具有相同起点终点的若干条边称为平行边若一条边的起点终点相同则称为环。不含平行边和环的图称为简单图。()边带有数字的图称为有权图。【DEF】G=(V,E),G=(V,E)若V是V的子集E是E的子集则G称为G的子图若V=V则G称为G的生成子图。【DEF】无向简单图中若每对节点间均有边则称为完全图n阶完全图记为Kn(有向图类似定义)。设G=(V,E)G=(V,E)若EE=ФG=(V,EE)是完全图则G称为G的补图。【例】写出K的所有生成子图。http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoantulunhtm(of)::图论【例】设G=(V,E)是n阶完全图则|E|=n(n)【例】有n个药箱每两个药箱有一种共同的药每种药恰好在两个药箱里出现问有多少种药?【提示】把n个药箱看成n个点两个药箱有一种共同的药则在这两个点之间连一条线于是得到一个完全图。【例】证明任意的个人中一定有个人互相认识或不认识。【提示】把个人看成个点若两个人认识则连一条红线若两个人不认识则连一条蓝线要在阶完全图中找一个同色三角形。.图的同构【DEF】设G=(V,E)G=(V,E)是有向图若存在双射f:VV使(Vi,Vj)E(f(Vi),f(Vj))E则称G,G同构。易知同构的图有相同点数边数。【例】【例】K的同构图【例】五边形与五角星同构http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoantulunhtm(of)::图论.图中节点的度【DEF】有向图G中以节点V为起点的边数称为V的出度记为deg(V),以V为终点的边数称为V的入度记为deg(V),V的出度与入度的和称为V的度记为deg(V)无向图中与节点V关联的边数称为V的度。度为奇数(偶数)的点称为奇顶点(偶顶点)【TH】(图论第一定理)设G=(V,E)则所有顶点的度数和为边数的两倍。【证明】因为每一边在计算度时被用了两次。【TH】(握无定理)一个图中奇顶点个数一定是偶数个。【例】无向简单图G中若顶点数至少为则至少有两点度数相同。【思考】()若无向图G中有n个点n条边则至少有一点度数不小于()若有向图G(V,E)中每两点之间有且只有一条边则每点出度平方和等于每点入度平方和。http:wwwjsipteducnycjyxxxxuexikongjianlssxjiaoantulunhtm(of)::图的矩阵表示图的矩阵表示.邻接矩阵设G=(V,E)V={V,,Vn}A=aijnn称为邻接矩阵当(Vi,Vj)E,aij=否则aij=【注记】邻接矩阵A是集合V上的关系矩阵。()有向图中点Vi的出度为有向图中点Vi的入度为()A的幂的元素的含义表示Vi到Vj长度为的通路数。表示Vi到Vj长度为的通路数。表示Vi到Vj长度为m的通路数。【例】求图中V到V的长度为的通路数。【提示】长为的通路数为VVVVVVVVVVVVVVVVVVVVV

用户评论(0)

0/200

精彩专题

上传我的资料

每篇奖励 +1积分

资料评分:

/13
仅支持在线阅读

意见
反馈

立即扫码关注

爱问共享资料微信公众号

返回
顶部

举报
资料