02324 离散数学 密训资料

目录TOC\o"1-1"\h\z\u第1章命题与命题公式 2第2章命题逻辑的推理理论 4第3章谓词逻辑 5第4章集合 7第5章关系与函数 9第6章代数系统的一般概念 12第7章格与布尔代数 14第8章图 14第9章图的应用 161命题与命题联结词★★

1章命题与命题公式真值TF0。判断命题的条件①语句本身是个陈述句（疑问句、感叹句、祈使句等都不能是命题）；②有唯一的真值。原子命题不能再分解的命题。复合命题由原子命题通过联结词联结而成的命题。如“今天天气炎热，有雷阵雨”。联结词（设P，Q为两个命题）①否定：P¬PPT，¬PF；反之亦然。②合取：P和Q的合取记为P∧Q。当且仅当P、Q同时为T时，P∧Q的真值为T，其余情况为P∧QF。③析取：P和Q的析取记为P∨Q。当且仅当P、Q同时为F时，P∧Q的真值为FP∧QT。④条件：P和Q组成的条件命题记为P→Q。当且仅当P的真值为T，Q的真值F时，P→QFP→QT。⑤双条件：PQP↔QP、Q相同时，P↔QTP↔QF。真值表①找出公式中所含的全体命题变元，从F…F开始写依次写出每个赋值，直到真值表①找出公式中所含的全体命题变元，从F…F开始写依次写出每个赋值，直到T…T为止；②按从简到繁的顺序写出公式的各个子公式；③对于各个赋值计算出各子公式的真值，直到最后计算出公式的真值。等价命题公式A和BP1Pn为A和BP1Pn任一组真值指派，A和B真值都相同，称A和B是等值的或等价的，记为AB。若至少真值不同A和B不等值或不等价AB。例：用列真值表的方法说明下列等价式成立：(PQ)→R(P→R)(Q→R)TF10由真值表可知，对于PQR的任意指派，(PQ)→R和(P→R)(Q→R)真值都相同，所以(PQ)→R(P→R(Q→R)永真式A，若在它的各指派情况下，取值均为真A重言式或永真式。永假式A，若在它的各指派情况下，取值均为假A矛盾式或永假式。可满足式AAAAPQRPQ(PQ)→RP→RQ→R(P→R)(Q→R)00001111001011110101010001111111100100101011111111010000111111112结论①合式公式P是可满足式，等价于P至少存在一个成真赋值；②重言式一定是可满足式，但可满足式不一定是重言式；③若两个命题公式P和Q等价，则PQ是重言式。命题定律双重否定律A¬¬A幂等律AAA,AAA结合律(AB)CA(BC)；(AB)CA(BC)交换律ABBAABBA分配律ABC)(ABAC)（对的分配律）ABC)(ABAC)（对的分配律）吸收律A(AB)A，A(AB)A德摩根律(AB)AB，(AB)AB同一律AFA，ATA零律ATT,AFF排中律AAT否定律AAF蕴涵等值式ABAB等价等值式AB(AB)(BA)假言易位ABBA等价否定等值式ABAB归谬论(AB)(AB)A推理定律化简律PQP化简律PQQ附加律P(PQ)变形附加律PPQ变形附加律QPQ变形简化律(PQ)P变形简化律(PQ)Q假言推理P(PQ)Q拒取式(PQ)QP析取三段论(PQ)QP条件三段论(PQ)(QR)(PR)等价三段论(PQ)(QR)(PR)合取构造二难(PQ)(RS)(PR)QS析取构造二难(PQ)(RS)(PR)QS前后件附加PQ(PR)(QR)前后件附加PQ(PR)(QR)32.1.2小项与大项★★

2章命题逻辑的推理理论小项n个命题变元的简单合取式，称作布尔合取或极小项，简称为小项，其中每个命题变元与它的否定不能同时存在，但该命题变元必须出现且仅出现一次，或以变元的形式，或以变元的否定形式。n个命题变元有2n个小项。例如：两个命题变元P和Q4PQPQPQ和PQ。大项n个命题变元的简单析取式，称作布尔析取或极大项，简称为大项，其中每个命题变元与它的否定不能同时存在，但该命题变元必须出现且仅出现一次，或以变元的形式，或以变元的否定形式。例如：由两个命题变元P和Q构成的大项共有4PQPQ、PQ和PQ，小项：以m加下标来表示，其下标是一个n位的二进制数。在小项中，若出现命题二进制编码变元Pi，对应小项编码的第i位为1，若出现命题变元Pi的否定，则第i位为0，小项PQR011，所以表示为m011。为了简单起见，有时也用位二进制im3。大项Mn若出现的是命题变元Pii位为0，若出现的是命题变元Pi的否定，则对应的第i位为1。例如：大项PQ的编码为M10，也可表示为M2主析取范式对于给定的命题公式，如果有一个等价主析取范式对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称为原式的主析取范式。在公式的真值表中，所有真值为T的指派所对应的小项的析取，即构成该公式的主析取范式。主合取范式对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等价式称为原式的主合取范式。在公式的真值表中，所有真值为F的指派所对应的大项的合取，即为此公式的主合取范式。例：写出公式A(PQ)QR的主析取范式和主合取范式真值表法①构造该公式的真值表。011的小项只有m100，A主析取范式为(PQR)07项，M000，M001，M010，M011M101M110M111A主合取范式为：(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)等值演算法主析取范式：(PQ)QR(PQ)QR(PQ)QRPQR主合取范式：根据上述等式(PQ)QRPQRP和¬Q，¬R拼成未出现的变元，得到：(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)PQRPQ(PQ)QR(PQ)QR00010110001101000101001001110000100011111010110011010010111100004P→QPQ消去→②如果有在括号前；用德摩根律：(ABAB或(ABAB，等值演算法③如果不是析取、合取形式；用分配律：A(BC(AB)(ACA(BC)(AB(AC)④第③步结束后，可得到简单析取式，若简单析取式A中缺少变元P，通过如下变P：A(AP)(AP)(AP)(AP)，再使用分配律，去掉重复的小项即可得到主析取范式。自然推理系统★★★推理法①前提引入规则P。②结论引入规则：在证明的任何步骤上，所证明的结论都可作为后续证明的前提，T。③转换规则：在证明的任何步骤上，命题公式中的任何子命题公式都可以用与之等值的命题公式置换，如用PQ置换PQ。它亦记为T规则。例：构造下列推理的证明：如果他训练刻苦，他必赢得比赛；如果他赢得比赛，他必得到总理的接见；总理没有接见他；所以他训练不刻苦。解：P：他训练刻苦；Q：他赢得比赛；R：他得到总理的接见前提：PQ；QR；RP证明： （1）P→Q P规则（2）Q→R P（3）P→R T（1）（2）（4）R→P T（3）（5）R P（6）P T（4）（5）3.1谓词的概念与表示★

3章谓词逻辑谓词谓词A表示“是大学生”，w表示“王强”，则“王强是大学生”可表示为A(w)例：设a：小华，P(x)：x是教授，f(x)：x的父亲，则语句“小华的父亲是教授”可符号化为：P(f(a))全称量词P(x)P(x)对x在其论域的所有值为真xP(x)表示P(x)的全称量化，其中称为全称量词。例：令F(x)：x是实数，G(x)：x是有理数。命题“实数不全是有理数”的符号化形式为：¬∀x（F(x)→G(x)）存在量词P(x)的存在量化是命题“论域中存在一个元素x使P(x)为真”。符号xP(x)表示P(x)的存在量化，其中称为存在量词。真假判断论域中的所有值都使P(x)为真时，xP(x)才为真；而只需要有一个值使得P(x)为真时，xP(x)即为真。反过来，有一个值使得P(x)为假，xP(x)即为假；而所有的值均使P(x)为假，则xP(x)为假。复合谓词公式由一个或几个原子谓词公式以及逻辑联结词组合而成的表达式称为复合谓词公式。公式中使用的逻辑联结词包括：、、、和。合式公式A记为WffA。5变元给定谓词合式公式A，一部分公式为xB(x)或xB(x)，称、后面的x为指导变元，或作用变元。B(x)为相应量词的辖域（或作用域）。辖域中，x的一切出现称为约束出现。在B(x)中除去约束出现的其他变元的出现称为自由出现。（1）约束变元改名规则：将量词辖域中，量词的指导变元及其辖域中该变元的所变元改名有约束出现均改为本辖域中未曾出现过的个体变元，其余不变。规则（2）自由变元代入规则：把公式中的某一自由变元，用该公式中没有出现的个体变元符号替代，且要替换该自由变元在公式中的所有出现处。谓词演算的等价式与蕴涵式★★★定义3.7给定任何两个谓词公式WffA和WffB，设它们有共同的论域E，若对A和B的任A和B在E上是等价的，记作AB。例：论域为{2,3}，则xyP(x,yP(2,2)P(2,3)P(3,2)P(3,3)定义3.8给定任意谓词公式WffAEA的所有赋值WffA都为真WffA在E上是有效的（或永真的）。如果在所有赋值下WffA都为假，则称WffA为不可满足的。如果至少在一种赋值下为真，则称该WffA为可满足的。常见谓词等值式与蕴涵式前面所学到的所有等价公式和蕴含式都可以推广到谓词演算中使用。x(A(x)B(x))xA(x)xB(x)xA(x)Bx(A(x)B)x(A(x)B(x))xA(x)xB(x)AxB(x)x(AB(x))xA(x)xA(x)AxB(x)x(AB(x))xA(x)xA(x)xA(x)xB(x)x(A(x)B(x))x(AB(x))AxB(x)x(A(x)B(x))xA(x)xB(x)x(AB(x))AxB(x)xA(x)xB(x)x(A(x)B(x))x(A(x)B(x))xA(x)xB(x)xA(x)xB(x)xA(x)xB(x)xA(x)Bx(A(x)B)1：证明下列谓词公式为永真式∀y(∀xA(x)→A(y))证明：∀y(∀xA(x)→A(y))A(x)⇔T2ID={2,3F(2,2)=F(3,3)=0F(2,3)=F(3,2)=1f(2,2)=f(2,3)=2，I下的真值。解：∀x∀y(F(x,y)→F(f(x,y),x))⇔(F(2,2)→F(f(2,2),2))∧(F(2,3)→F(f(2,3),2))∧(F(3,2)→F(f(3,2),3))∧(F(3,3)→F(f(3,3),3))⇔(0→F(2,2))∧(1→F(2,2))∧(1→F(3,3))∧(0→F(3,3))⇔(0→0)∧(1→0)∧(1→0)∧(0→0)⇔1∧0∧0∧1⇔0前束范式★—个公式，如果量词均在全式的开头，它们的作用域，延伸到整个公式的末尾，则该公式称为前束范式。yxz(Q(x,y)R(z))xR(x)yS(x)则不是前束范式。6谓词演算的推理理论★★★全称量词消去规则P是谓词，而c是论域中的任意一个个体，如果论域中全部个体都有P(x)，那么对某个具体的个体c亦有P(x)，即可得到结论P(c)。（简记为)全称量词引入规则如果能够证明对论域中任一个体c谓词P(c)都成立，则可得到xP(x)为真。这里的个体c必须是论域中的任意一个元素，而不能是某个特定的元素。（简记为)如果已知xP(x)成立，则在论域中存在一个个体c使得P(c)为真。这里只知存在个体c，但不能选择任意的c，通常并不知道c的具体值。例如xP(x)和xQ(x)都为真，则对某些c和某些d，可以断定P(c)Q(d)为真，但是不能断定P(c)Q(c)为真，也不能断定P(d)Q(d)为真。（简记为)存在量词引入规则如果已知论域中某个个体c使得P(c)xP(x)（简记为)例：符号化下列命题，并构造推理证明。任何人如果他是素食者，他就不喜欢吃肉；每一个人或者喜欢吃肉或者喜欢吃蔬菜；有的人不爱吃蔬菜。因而不是所有的人都是素食者。P(x)：x是素食者；Q(x)：x喜欢吃肉；R(x)：x喜欢吃蔬菜前提：x（P(xQ(x)）；x（Q(xR(x)）；xR(x结论：xP(x)证明：（1）xR(x) P规则（2）R(c) -（1）（3）x（P(xQ(x)） P规则（4）P(c)→Q(c) -（3）（5）x（Q(xR(x)） P规则（6）Q(c)R(c) -（5）（7）Q(c)→R(c) T（6）（8）P(c)→R(c) T（4）（7）（9）R(c)→P(c) T（8）（10）P(c) T（2）（9）（11）xP(x) +（10）（12）xP(x) T（11）4.1集合的基本概念★★

4章集合属于若元素属于若元素a是集合AaAaAaAaA。相等设A、B是任意两个集合，称这两个集合是相等的，当且仅当它们含有相同的元素。集合A与B相等记为AB，集合A与B不相等记为AB空集不包含任何元素的集合称为空集，记为或。空集的基数为0，=0。对于任意集合A必有∅A。包含设A、B是任意两个集合，若A的每一个元素都属于B，则称A为B的子集，也称BA或AB内。记作AB或BA。对任意集合AB、C，必有ABBCAC基数集合A中的元素个数称为集合的基数或势，表示为A。幂集设AAA的幂集P(A)。若A是具有n个元素的有限集，则A的幂集P(A)2n个元素4.1集合的运算★★★★ 设任意两个集合A和B：交集由集合A和B的所有共同元素组成的集合S称为A和B的交集，记为AB。SABx(xA)(xB)并集所有属于A或属于B的元素组成的集合S称为A和B的并集，记作AUB。SABx(xA)(xB)补集由属于A但不属于B的所有元素组成的集合S，称为A与B的差集，也称为B对于A的补集，或相对补，记作AB。SABxxAxB。绝对补设E为全集，对任一集合A，关于E的补EA，称为集合A的绝对补~A或A~AEAxxExA，即所有不属于A的元素组成~A对称差A和B的对称差为集合S，其元素或属于A，或属于B，但不能既属于A，又属于B，记作AB。有定理ABBAAAAA；AB(A~B(~AB)(ABCABC)。定理ABA~B；ABA(AB)集合运算的恒等式幂等律AA=A；AA=A结合律(AB)CA(BC)；(AB)CA(BC)交换律ABBA；ABBA分配律A(BC)(AB)(AC)；A(BC)(AB)(AC)包含律ABA；ABB；AAB；BAB同一律AEA；A∅A；零律A∅=∅；AEE排中律A~AE矛盾律A~A∅吸收律A(AB)A；A(AB)AA(BC)(AB)(AC)；A(BC)(AB)(AC)德摩根律~(AB)~A~B；~(AB)~A~B； ∅E；~E∅双重否定律~(~A)A例：A，B，C是集合，证明：(A-B)-C=A-(B∪C)（考试可分排写出过程，此处为省篇幅）证明：(A-B)-C=(A~B~C=A(~B~C)=A~(BC)=A-(BC)4.3★★有序对由两个元素x和y(允许x=y)按一定顺序排列成的二元组称为一个有序对或序偶，记作x，y或(x,y)，其中x是该有序对的第一元素，y是该有序对的第二元素。笛卡尔积设A、B为集合。用A中元素x为第一元素，B中元素y为第二元素构成有序对，所有这样的有序对组成的集合叫做A和B的笛卡儿积，记作AB。也称为直积。A×B=x,yxAyB定理若集合A有m个元素，集合B有n个元素，则AB有mn个元素。例：设集合A={1,2,3}，集合B={a，b，c，d，e}，则|A×B|=（），而|P(A)×B|=（）|A×B|=3×5=15|P(A)×B|=2³×5=40。8关系及关系的性质★★★

5章关系与函数关系设A、B是任意两个集合，AB的子集R称为从A到B的二元关系，简称为关系。特别地，当A=B时，称R为Ax，yRxRyx与yR；如果x，yR，则记为xRy，称x与yR。定义域R中所有有序对的第一元素构成的集合称为R的定义域，记为domR，表示为domRxy(x,yR)值域R中所有有序对的第二元素构成的集合称为R的值域，记为ranR，ranRyx(x,yR)；域R的定义域和值域的并集称为R的域，记为fldRfldRdomRranR例：设R={<1，b>，<2，a>，<2，d>，<4，b>}是集合A={1，2，3，4}到集合B={a，b，c，d}ranR={a，b，d}，domR={1,2,4}。关系矩阵设给定两个有限集合Xx,x,...xYy,yyR为X到R的一个二元1 2 m 1 2 n关系，称矩阵MR(rij)mn对应于R的关系矩阵，其中r 1，当xiyjRij0，当xiyjR关系图设集合Xx,x,...,x到Yy,y,...,y的二元关系为R1 2 m 1 2 n点，其中一组顶点对应X中的元素，另一组顶点对应Y中的元素，两组顶点分别记作x1x2,...,xm和y1,y2,...,yn。如果xi与yj有关系，则自顶点xi至顶点yj画一条有向边（带方向的线段），边上的方向由xi指向yj；如果xi与yj没有关系，则xi与yj间没有边相连，由此得到R的关系图。关系的性质如果对aA，必有aRa，则称关系R在A上是自反的；如果对aA，必有aRa，则称关系R在A上是反自反的；对abA，若aRb必有bRa，则称关系R在A上是对称的；对abA，若aRb且bRa必有ab,则称关系R在A上是反对称的；对ab,cA,若aRb且bRc必有aRc，则称关系R在A上是传递的。例：给定A：{1，2，3，4}，考虑A上的关系R，若R={(1，3)，(1，4)，(2，3)，(2，4)，(3，4)，(4，4)R（传递的）。解析：R中不存在（1,1）所以不是自反的；R中存在（1,3）不存在（3,1）所以不是对称的；R中存在（4,4）所以不是反自反的。根据定义验证，(1，3)和(3，4)、(1，4)都存在，R例：设R={<1,4>，<2,1>，<2,3>，<3,1>，<4,2>，<4,3>}是A={1,2,3,4}上的关系。（1）写出R的关系矩阵。（2）画出R的关系图。（3）说明R是否具有自反、反自反、对称、反对称性质。00011010 <1,1>,<2,2,>,<3,3>,<4,4>都R，所以解：（1） ；（2） （3）1000 R是反自反的，不是自反的。0110 任何一个<a,b>R，必有<b,a>R， 所以R是反对称的，不是对称的。9关系的运算★★定理ZSXYZ、SXY的关系。逆关系RXYR中每一个二元组中的元素顺序互换，所得到的集合称为R的逆关系，简称为R的逆，记作R1或RC，即R1y,xxyR。设RR1R2都是从A到B的二元关系，则下列各式成立。（1）(R1)1R； （2）(RR)1R1R1；1 2 1 2~ ~（3）(RR)1R1R1； （4）(R)1R1；1 2 1 2（5）(AB)1BA； （6）(RR)1R1R1；1 2 1 2（7）若RR，则R1R1；（8）domR1ranR；1 2 1 2（9）ranR1domR。复合关系设R为A到B的关系，S为B到C的关系，则RS称为R和S的复合关系，表示为RSxyt(xtRtyS)。A={p，q，r，s},B={a,b},C={1,2,3,4},AB的关系R1BC的关系R2R1={<p,a>,<p,b>,<q,b>,<r,a>,<s,a>},R2={<a,1>,<a,2>,<b,4>},AC的复合关系。解：由于R1p,a>,<p,b>,<q,b>,<r,a>,<s,a>}R1R2={<p,1>,<p,2>,<p,4>,<q,4>,<r,1>,<r,2>,<s,1>,<s,2>}设F是X到YG是Y到ZH是Z到W的关系，则（1）(FGHFGH；（2）(FG)1G1F1。设R是集合A上的关系，幂Rnn1,2,...)递归地定义为R1RRnRn1R。A={a，b，c，d}，AR={<1,1>，<2,1>，<3,2>，<4,3>}，R²=<1,1>，<2,1>，<3,1>，<4,2>R1=<1,1>，<1,2>，<2,3>，<3,4>。关系的闭包RAR'满足下列条件：（1）R是自反的（对称的或传递的）；（2）RR（3）对于A上的任何包含R的自反的（对称的或传递的）关系R，有RR;称R'为R的自反（对称或传递）闭包，记作r(R)（s(R)或t(R)）。定理：①r(R)RIAs(R)RR；1③t(R)RR2Rnn是集合A中的元素的数目。例：设集合A={a，b，c，d}以及A上的一个二元关系R={<a，b>，<b，c>}，则对s(R)=（）t(R)=（）。解析：根据对称：<a，b>→<b，a>，<b，c>→<c，b>，所以则对称闭包s(R)={<a，b>，<b，c>，<b，a>，<c，b>}根据上述运算方法，传递闭包t(R)={<a，b>，<b，c>，<a，c>}10相容关系给定集合A相容关系给定集合A上的关系，若是自反的、对称的，则称是A上的相容关系。等价关系设R为非空集合A上的关系，若R是自反的、对称的和传递的，则称R为A上的等价关系。设R为等价关系，若xyR，称x等价于y，记作x~y。a，b为正整数}A上定义二元关系~如下：<a，b>~<c，d>a+b=c+d。证明：~是一个等价关系。证明：（1）自反性：a+b=a+b，即<a,b>~<a,b>对称性：若a+b=c+d，则必有c+d=a+b，即若<a,b>~<c,d>，则必有<c,d>~<a,b>传递性：若a+b=c+d，且c+d=e+f，则必有a+b=e+f，即若<a,b>~<c,d>，且<c,d>~<e,f>，则必有<a,b>~<e,f>综上所述，~是一个等价关系。划分非空集合A，若集合SS,SS，其中SAS∅（1im），且12 m i imSiSj∅（ij）同时有SiA，称S是A的划分，每个Si（1im）称为i1一个分块。A3A上的等价关系的个数为（5个）解析：不妨设A={a，b，c}；则A有5个划分{{a}，{b}，{c}}，{{a，b}，c}，{{a，c}，b}，{{b，c}，a}，{{a，b，c}}A5个偏序关系设A是一个非空集合，如果A上的关系R满足自反性、反对称性及传递性，则称R是A上的一个偏序关系，记作“≼”。集合A和A上的偏序关系≤一起称为偏序集，记为<A，≼>。若xy，读为“x小于或等于y”，记作xy。可比≤是非空集合AabA，若<ab且ab称a小于b，记ab;若a，b或b，a,称a与ba与b是不可比的。覆盖设A，为偏序集，对a，bA，若ab且不存在cA使得acb,则称ba。记COVAabaAbAb覆盖a。例：〈A，≼〉是一个偏序集，其中A是正整数12的正因子的集合，≼为整除关3的元素是（6）解：121,2,3,4,6,12。故在整除关系下，3≼6，3≼126≼1236.哈斯图①AabA，若ab，则将a画在b的下方；③abA，若b覆盖a，则在a与b之间画一条边；④图中省略从顶点到自身的边。定理设ABAyB。若x(xByx)成立，则称y为B的最小元。若x(xBxy)成立，则称y为B的最大元。若x(xBxyxy)成立，则称y为B的极小元。若x(xByxxy)成立，则称y为B的极大元。A={1，6，9，12，18，36}，≤为整除关系。画出<A，≤>的哈斯图。求子集B={6，12，18}的极大元、极小元、最大元、最小元。解：（1）画出的哈斯图如右图。66是最小元；1812整除，故不存在最大元666是极小元1212181812、18是极大元。11函数★★函数设F为二元关系，若xdomF都存在唯一的yranF，使xFy成立，则称F为函数，也称为映射。对于函数F，如果有xFy，则记为yF(x)，称xy为F在x的值，或在F作用下x的象。从x到y的函数F记为：F：xy或xy。F要对定义域中的所有元素都有定义；②对xdomF，只能有唯一的yranF，满足x，yF。单射函数函数f为一对一的，当且仅当对于f定义域中的所有x和y，fxfy蕴含着x=y。一对一函数也称为单射函数或入射函数。满射给定函数f:XY，当且仅当对yY,都有xX使得fxy，则函数f称为满射的或映上的。双射给定函数f:XY，函数f是满射的又是单射的，称f为一一对应的，也称双射的。只有双射函数才有反函数。复合函数设f:XY，gYZ，函数f和g的复合fgxgfx，具体表示为：fgxx,zxXzZyyYyfxzgy合成函数。简单地看，fg(x)gfx，如果f值域不是gfg。代数系统★★★

6章代数系统的一般概念定义6.3定义6.3设A为任意非空集合，*和是集合A上的二元运算，对ab,cA，若有abA则称运算*关于集合是封闭的；若abcabc，称运算在集合A上是可结合的，或称运算在A上满足结合律；若有abba，称运算在A上是可交换的，或运算在A上满足交换律；若有aaa，则称运算在A上是幂等的，或称运算在A上满足幂等律；（5）abcabac和bcabaca成立，则称运算对是可分配的，或称运算对满足分配律；（6）若和均满足交换律，而且有：aaba和aaba，则称运算和是可吸收的，或称运算和满足吸收律。幺元①设*为集合A上二元运算，若存在eLA，使得对于xAeLxx则称eL是A中关于运算的左幺元。②若有erA，使对于xA，都有xerx，称er是A中关于运算的右幺元。③若存在eA，既是左幺元，又是右幺元，称e是A中关于的幺元，也称单位元。显然，若e是A中关于的幺元，则对xA，都有exxex。零元①设是定义在集合AolAxA都有OlxOl，则称Ol为A中关于运算的左零元；②如果有一个元素OrA，对于任意元素xA，都有xOrOr，则称Or为A中关于运算的右零元；③如果存在OA，它既是左零元也是右零元，则称O为A上关于运算的零元。例：设例：设A为非空有限集合，P(A)为A的幂集，∪为集合的并运算，群<P(A)，∪>中，单位元是（），零元是（）BP(A)B=B，所以是单位元；B∪A=A，所以A为零元。半群设半群设VS,是代数系统，是集合S是封闭且是可结合的，则称V为半群。独异点若半群S,中存在一个幺元，则称S>为独异点（或含幺元半群）。群设G,是一个独异点，其中G是非空集合，是G上一个二元运算，对于xG都有逆元x1存在，则称G,是一个群。群要满足条件：封闭性、结合律及存在幺元，同时还要求对集合中的每个元素都要有逆元。例：在整数集Z上定义一个二元运算如下：ab=a+b+1，证明：<Z,>是群。证明：（1）封闭性：a,bZab=a+b+1Z，所以运算是封闭的（2）可结合：a,b,cZ，a(bc)=a(b+c+1)=a+b+c+2，(ab)c=(a+b+1)c=a+b+c+2所以a(bc)=(ab)c，即运算是可结合的（3）eae=a+e+1=ae=-1aZ，必有(-1)a=a(-1)=a，所以-1是<Z的幺元（4）Za的逆元a−1aa−1=a+a−1+1=-1，可得a−1=-a-2aZ，必有(-a-2)a=a(-a-2)=-1，所以-a-2是a的逆元综上所述，<Z,是一个群交换群设<G，>是一个群，若运算在G上满足交换律，称G为交换群或Abel群。K阶元设<G，>是群，e是幺元。对于aG，使得ake成立的最小正整数k称为a的阶，记作a，a称为k阶元。若不存在这样的正整数ka称为无限阶元。<Zn+>是一个群，其中Zn={012，…n-1}x+y=(x+y)modn，则在<Z10，+>1的阶为（10）9的阶为（10）解：(x+y)modn表示(x+y)除以nn=10时，Z10={0,1,2,3,4,5,6,7,8,9}有（0+x）mod10=（x+0）mod10=x，所以0是幺元；（9+9+9+9+9+9+9+9+9+9mod10=0|9|=10（1+1+1+1+1+1+1+1+1+1mod10=0|1|=10.环设A,,是一个代数系统，+和是二元运算，如果满足（1）A，+>是Abel群；（2）A，>是半群；（3）运算对于运算+是可分配的；则称<A,+，>是一个环。零因子设<R>是环，对abRa0b0，但ab0，则称a是R中的一个左零因子，b是R中一个右零因子；若一个元素既是左零因子，又是右零因子，则称它是一个零因子。定义设A,,（1）若环中乘法满足交换律，则A,,是可交换环。（2）若环中乘法存在幺元，即对aR，均有1aa1a，称<A，+，>为含幺元的环。1称为环<A>的幺元。（3）对于abR，若ab0,必有a=0或b0，称<A,+，>是一个无零因子环。（4）若<A>既是交换环、含幺环，也是无零因子环，则称<A，+，>为整环。13域设<R，+，>是一个整环，且R2，若对aRR0，都有a1R，则称<R>是域。因此，域一定是整环，整环不一定是域。7章格与布尔代数格★★设A是一个偏序集，对a,bAa,b在A中都有最大下界(也称为下确界，记为infa,b)和最小上界（也称为上确界，记为supa,b），则称A为格。设<A，丨>为偏序关系，其中丨为整除关系，即a丨b当且仅当a整除b。已A={1,2,3,5,6,15,30}。画出这个偏序关系的哈斯图，并判断其是否为格。解：该偏序关系的哈斯图如右图：任意两个元素都有上确界和下确界存在，故为格。分配格★设<A，V>是格，若对ab,cAabcabac；abcabacA,,是分配格。有补格★★设<A，V01>是一个有界格，若对于aAA中都有a的补元存在，则A称为有补格。7.3中的四个格。解：L1中，a与cb不存在补元。a是全下界，c是全上界。L2a与d互补，b与c互补。a是全下界，d是全上界。L3中，a与e互补。b、c、d三个元素中，对于任意一个，另外两个都是它的补元，即每个元素都存在两个补元。a是全下界，e是全上界。L4aeb的补元是cdcd的补元都是b。ae全上界。综上，L1不是有补格，其他三个都是有补格。图的基本概念★★

8章图图—个图包含顶点和边两部分。图用GV,E来表示，其中V是非空有限顶点集，E是边集，E中的每条边都是V中某一对顶点间的连接。当顶点分别是u，v时，连接这两个顶点的边可以表示为一个二元组u,v或是u,v点的有序对。图GVE中，顶点总数记为V，边的总数记为E。图中的边均为有向边的图称为有向图。如果图中仅含有无向边，称为无向图。度无向图GV,Ev关联的边数称作该顶点的度数degv。14对图G中的顶点v，若degv0v称为弧立点；若degv1v称为悬挂点；若v有环，则计算度时使degv增加2；若degv为奇数，称v为奇顶点或奇点；若degv为偶数，称v为偶顶点或偶点。出度和入度设GVE是有向图，以顶点v为起点的有向边个数称为v的出度，记degv；以顶点v为终点的有向边个数称为v的入度，记degv。顶点的出度与入度之和就是该顶点的度数，有向图中所有顶点的入度之和等于所有顶点的出度之和。n阶完全图设含n个顶点的简单无向图GVEn-1个顶点邻接，Gn阶（无向）完全图，记作Kn。n阶有向图设含n个顶点的简单有向图GVE中，若每个顶点都邻接到其余的n-1个顶Gn阶有向完全图。计算简单无向图的顶点度数总和等于边数的两倍，奇顶点必为偶数个。n阶（无向）完全图中共有nn1条边，n阶有向完全图中共有nn1条边。21：无向完全图K6的边的条数为（15）解：根据公式，6×5÷2=15152G745。证明：G5445G745，则有以下四种情况：G74G54，25G34，45G14，65综上所述，G54453Gnn+1G3。G3G2G2nGn，这与已知条件矛盾，故假设不成立，即图G中至少有一个结点度数≥3通路通路vivivi的长度0 1 n为n。若的所有边均不相同，则称为简单通路。当简单通路的起点与终点相同时，称为简单回路。若简单通路的所有顶点不同（除起点和终点可能相同外），则称为初级通路或路径。若初级通路的起点与终点相同时，称为初级回路。定理若无向图GVE中每个顶点的度数至少为2，则G包含一条初级回路。设GVE，Vn，若从顶点u到vuv存在通路，则从u到v必存在长度小于或等于n1的一条通路。连通图在无向图Gu和vu和顶点vG中任何两个不同顶点都是连通的，则称G为连通图，否则称G为不连通图。例：根据图8.5,举出通路、回路、简单通路、初级回路等例子。解：在图8.5所示的图中，通路：a,d,e,b,a,e,f,c,b,f,c,d是长度为11的通路，但不是简单通路，因为边f,c出现两次；a,b,e,d是长度为3的通路，且是简单通路；回路：b,c，f，e，b，f，e，b是长度为7的回路，但不是简单回路，因为其中含有重复的边；简单通路：a，d，c，f，e是长度为4的简单通路，也是初级通路；初级回路：b，c，f，e，b415图的表示★★★邻接矩阵设图GVEVv,vvn阶方阵Ma称为G的邻接矩阵，其1 2 n ijaij为图G中从vi到vj的边的数目。计算由邻接矩阵可以计算任意两顶点之间的通路数目。对于布尔矩阵M，定义它的幂M2MM,其中“×”是矩阵乘法。MkMMk1k1。设M是n个顶点的简单图GMkmk是M的kMk中的mkij ij等于顶点vi和vj之间长度为k的通路的数目。18.5（上页中）ad38.5M:010110 312122 494775 101011 141322 9694107010101 2 3 2213031 3492847M ；计算M和M:M ；M 101010 130312 748294110101 223141 7104969 011010 221213 577494 ad3M31477a，b，a，d；a，e，a，d；a，d，a，d；a，b，c，d；a，b，e，d；a，d，c，d；a，d，e，d。2G：（1）GM。（2）G40110 1101 1212