离散数学复习要点

离散数学复习要点离散数学复习要点离散数学复习要点离散数学复习要点编制仅供参考审核批准生效日期地址：电话：传真:邮编:离散数学复习要点第一章命题逻辑一、典型考查点1、命题的判断方法：陈述句真值唯一，特殊：反问句也是命题。其它疑问句、祈使句、感叹句、悖论等皆不是。详见教材P12、联结词运算定律┐∧∨→记住特殊的：1∧11，0∨00，1→00，111，001详见P53、命题符号化步骤：A划分原子命题，找准联结词。特殊自然语言：不但而且，虽然但是用∧，只有P才Q，应为Q→P；除非P否则Q，应为┐P→Q。B设出原子命题写出符号化公式。详见P54、公式的分类判定（重言式、矛盾式、可满足式）方法：其一根据所有真值赋值情况，其二根据等价演算来判断。详见P95、真值表的构造步骤：①命题变元按字典序排列，共有2n个真值赋值。②对每个指派，以二进制数从小到大或从大到小顺序列出。③若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。详见P8。6、基本概念：置换规则，P规则，T规则，详见P24；合取范式，析取范式，详见P15；小项详见P16；大项详见P18，最小联结词组详见P157、等价式详见P22表证明方法：①真值表完全相同②用等价演算③利用AB的充要条件是AB且BA。主要等价式：(1)双否定：AA。(2)交换律：A∧BB∧A，A∨BB∨A，ABBA。3)结合律：(A∧B)∧CA∧(B∧C)，(A∨B)∨CA∨(B∨C)，(AB)CA(BC)。(4)分配律：A∧(B∨C)(A∧B)∨(A∧C)，A∨(B∧C)(A∨B)∧(A∨C)。(5)德·摩根律：(A∧B)A∨B，(A∨B)A∧B。(6)等幂律：A∧AA，A∨AA。(7)同一律：A∧TA，A∨FA。(8)零律：A∧FF，A∨TT。(9)吸收律：A∧(A∨B)A，A∨(A∧B)A。(10)互补律：A∧AF，(矛盾律)，A∨AT。(排中律)(11)条件式转化律：A→BA∨B，A→BB→A。(12)双条件式转化律：AB(A→B)∧(B→A)(A∧B)∨(A∧B)8、蕴含式详见P23表证明方法：①前件真导后件真方法②后件假导前件假方法③真值表中，前件为真的行，后件也为真或者后件为假的行，前件也为假。④用定义，证AB，即证A→B是永真式。9、范式求法步骤：①使用命题定律，消去公式中除、和以外公式中出现的所有联结词；②使用(P)P和德·摩根律，将公式中出现的联结词都移到命题变元之前；③利用结合律、分配律等将公式化成析取范式或合取范式。10、主范式的求法重点步骤：(a)把给定公式化成析取（合取）范式；(b)删除析取范式中所有为永假的简单合取（析取）式；(c)用等幂律化简简单合取（析取）式中同一命题变元的重复出现为一次出现，如P∧PP。(d)用同一律补进简单合取（析取）式中未出现的所有命题变元，如Q，则PP∧（Q∨Q)或PP∨（Q∧Q)，并用分配律展开之，将相同的简单合取式的多次出现化为一次出现，这样得到了给定公式的主析取（合取）范式。注意：主析取范式与主合取范式之间的联系。例如：(PQ)Qm1m11、推理证明：重点方法：演算、演绎法（常用的格式）、反证法、CP规则即附加前提等。重点规则（主要蕴含式）：(1)P∧QP化简(2)P∧QQ化简(3)PP∨Q附加(4)PP→Q变形附加(5)QP→Q变形附加(6)(P→Q)P变形化简(7)(P→Q)Q变形化简(8)P，(P→Q)Q假言推理(9)Q，(P→Q)P拒取式(10)P，(P∨Q)Q析取三段论(11)(P→Q)，(Q→R)P→R条件三段论(12)(PQ)，(QR)PR双条件三段论文字证明推理三步：一命题符号化，二写出前提和结论，三进行证明。详见P21二、强化练习1.命题的是()A.走，看电影去+y>0C2.下列式子为重言式的是()→P∨QB.(┐P∧Q)∧(P∨┐Q)C.┐(PQ) D.(P∨Q)(P→Q)3．下列为两个命题变元P，Q的小项是（）A．P∧Q∧PB．P∨QC．P∧Q D．P∨P∨Q4．下列语句中是真命题的是（）A．我正在说谎B．严禁吸烟C．如果1+2=3，那么雪是黑的D．如果1+2=5，那雪是黑的5．设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（）A．P∧QB．P∨QC．（PQ） D．（P∨Q）6．命题公式（P∧（P→Q））→Q是（）A．矛盾式B．蕴含式C．重言式 D．等价式7．命题公式（P∧Q）→R的成真指派是（）A．000，001，110，B．001，011，101，110，111C8．设P：他聪明，Q：他用功，命题“他虽聪明但不用功”的符号化正确的是（）A．P∧Q B．P∧QC．P→Q D．P∨Q9．下面联结词运算不可交换的是（）A．∧ B．→C．∨ D．10下列命题公式不是重言式的是（）A．Q→（P∨Q） B．（P∧Q）→PC．（P∧Q）∧（P∨Q）D．（P→Q）（P∨Q）11.设命题变元为P，Q，R，则小项m100=________，大项M010=________。12.置换规则：在证明的任何步骤上，命题公式中的任何子命题公式都可以________，记为________规则。13.请用联结词┐，∧表示联结词∨和联结词：________，________。14．两个重言式的析取是________式，一个重言式与一个矛盾式的析取是________式。15．命题公式（PQ）→P的成真指派为__________，成假指派为__________。16.用等值演算求(P→Q)→R的主合取范式。17.列出(P→(Q∨R))(P→Q)的真值表。19．构造命题公式（（P∧Q）→P）∨R的真值表。20．求下列公式的主合取范式和主析取范式：P∨（P→（Q∨（Q→R）））21．构造命题公式（）→PR的真值表。22．求下列公式的主析取范式和主合取范式：（P→（QR））（P→（Q→R））。23.用推理方法证明：P∨Q，P→R，Q→S├R∨S。24．构造下面推理的证明。如果小张和小王去看电影，则小李也去看电影。小赵不去看电影或小张去看电影。小王去看电影。所以，当小赵去看电影时，小李也去。25．构造下面推理的证明。只要A曾到过受害者房间并且11点以前没离开，A就犯了谋杀罪。A曾到过受害者房间。如果在11点以前离开，看门人会看见他。看门人没有看见他。所以A犯了谋杀罪。离散数学复习要点第二章谓词逻辑一、典型考查点1、基本概念：个体词、个体域、谓词、特性谓词、辖域，详见P27；前束范式详见P362、谓词符号化步骤：①正确理解给定命题。必要时把命题改叙，使其中每个原子命题、原子命题之间的关系能明显表达出来。②把每个原子命题分解成个体、谓词和量词；在全总论域讨论时，要给出特性谓词。③找出恰当量词。应注意全称量词(x)后跟条件式，存在量词(x)后跟合取式。④用恰当的联结词把给定命题表示出来。详见P303、谓词公式类型的判定（永真式、永假式、可满足式）方法：利用论域翻译成自然语言后进行判断。详见P344、自由变元与约束变元的判定方法：按定义，关键是要看它在A中是约束出现，还是自由出现，若与量词的指导变元相同，就是约束出现，不同就是自由出现。详见P31。5、等价式(1)量词否定等价式：(a)(x)A(x)A(b)(x)A(x)A(2)量词辖域缩小或扩大等价式(a)(x)(A(x)∧B)(x)A(x)∧B(b)(x)(A(x)∨B)(x)A(x)∨B(c)(x)(A(x)→B)(x)A(x)→B(d)(x)(B→A(x))B→(x)A(x)(e)(x)(A(x)∧B)(x)A(x)∧B(f)(x)(A(x)∨B)(x)A(x)∨B(g)(x)(A(x)→B)(x)A(x)→B(h)(x)(B→A(x))B→(x)A(x)。(3)量词分配律等价式：(a)(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)(b)(x)(A(x)∨B(x))(x)A(x)∨(x)B(x)其中，A(x)，B(x)为有x自由出现的任何公式。详见P34356、蕴含式(a)(x)A(x)∨(x)B(x)(x)(A(x)∨B(x))(b)(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)(c)(x)(A(x)→B(x))(x)A(x)→(x)B(x)(d)(x)(A(x)→B(x))(x)A(x)→(x)B(x)其中，A(x)和B(x)为含有x自由出现的任意公式。详见P356、前束范式方法：①把量词全部通过等值演算化到整个谓词公式的前面②把量词前面的┐全部通过德摩根定律化到谓词公式的内部。详见P367、推理：方法：演绎（常用格式）、反证法、CP规则即附加前提等。对于命题逻辑中的所有规则都可用。特殊规则：(1)量词消去(简称UI或US规则)(x)A(x)A(c)(x)A(x)A(y)(x)A(x)A(c)量词产生规则(简称EG或UG规则)A(c)(y)A(y)A(x)(y)A(y)详见P38二、强化练习1.下列式子不是谓词合式公式的是()A.(x)(P(x)→(x)(Q(x)∧A(x，y))) B.(x)∧(y)∨P(x，y)C.(x)P(x)→R(y) D.(x)P(x)∧Q(y，z)2.设个体域为实数集，特定元素a=0，函数f(x，y)=x-y，特定谓词F(x，y)为x<y，下列公式真值为真的是()A.(x)(y)F(x，f(f(x，y)，y))B.(x)(y)(┐F(f(x，y)，x))C.(x)(y)(z)(F(x，y)→F(f(x，z)，f(y，z)))D.(x)F(f(a，x)，a)3.对于公式(x)(y)P(x，y)∨Q(x，z)∧(x)P(x，y)，下列说法正确的是()是自由变元 是约束变元C.(x)的辖域是P(x，y)∨Q(x，z) D.(x)的辖域是P(x，y)4.设论域为{1，2}，与公式(x)┐A(X)等价的是()A.┐A(1)∨┐A(2) B.┐A(1)→┐(A2)C.┐A(1)∧┐A(2) D.A(1)→A(2)5．在公式（）F（x，y）→（y）G（x，y）中变元x是（）A．自由变元 B．约束变元C．既是自由变元，又是约束变元 D．既不是自由变元，又不是约束变元6．下列等价式不正确的是（）A． B．C． D．7．设A（x）:x是人，B（x）：x犯错误，命题“没有不犯错误的人”符号化为（）A． B．B（x））C．D．B(x))二、填空题8.一个公式，如果量词均在全式的________，其作用域延伸到整个公式的________，则该公式称为前束范式。9．（x）（y）（P（x，y）Q（y，z））∧xP（x，y）中x的辖域为________，x的辖域为________。10．公式（）（F（x）→G(y)）→()(H(x))中的自由变元为_________，约束变元为__________。三、综合应用题11．符号化下面命题，并构造推理证明：人是要死的，苏格拉底是人，所以苏格拉底是要死的。离散数学复习第三章集合与函数一、典型考查点1、基本概念判断：函数的入射、满射、双射及定理、复合运算，详见P72，73，75。幂集、差集、对称差、笛卡尔积，详见P46，47，43，49。全序关系，详见P68.。方法：理解概念即可，按定义的步骤计算。2、关系的相关概念判断：①特殊关系：若R=，为空关系；若R=AB，为全域关系。R={<x,x>|xA}为A上的恒等关系，记为IA。方法：根据定义判断。②定义域:D(R)={x|(y)(xRy)}值域:R(R)={y|(x)(xRy)}域:F(R)=D(R)+R(R),方法：定义域就是关系R中第一位元素的集合，值域就是R中第二位元素的集合，域就是定义域并上值域。③表示方法：集合列举法\关系矩阵\关系图方法：根据题目条件，用列举法写出关系R，画出关系图（有向图）或写出关系矩阵。详见P50,51,52.3、关系的性质判断：判断方法如下：详见P54R是A上关系自反性反自反性对称性反对称性传递性定义xxAxRxxA<x,x>RxRy→yRxxRy→<y,x>R除x=yxRyyRz→xRz矩阵特征主对角线全为1主对角线全为0沿对角线对称沿主对角线不对称图特征每个顶点都有环每顶点都没有环有边则双向边若有边，则是单向边集合特征IARIAR=R-1=RIARIA4、关系的运算：①关系的集合运算，按集合的运算规律即可：交、并、补、差、对称差等。②复合运算：按顺序运算，逆运算，交换每个元的第一、二位元素的位置即<x,y>变<y,x>。③闭包运算：即先判断R本身是否具有自反（对称、传递），若有，则自反（对称、传递）闭包就是R本身，即r(R)=R(或s(R)=R,t(R)=R),若没有，则增加R的元素，加到恰好满足自反性为止，既不能多，也不少。详见P555、等价关系和划分的判断及证明：①等价关系的证明：自反、对称、传递三个性质逐一验证。要注意给出的等价关系的条件的变通。②等价关系与划分一一对应，等价关系的等价类即为确定的划分的分块，即有关系的，划在同一块。划分中凡在同一个分块中的元，都写成满足关系的元，这样写出的关系R就是一个等价关系。6、相容关系和覆盖的判断：相容关系两个性质：自反和对称，注意：相容关系图的画法省略了自反和对称。覆盖按定义判断即可。详见P617、偏序关系与哈斯图：①基本概念：三个性质：自反、反对称和传递；可比，就是有关系，a≤bb≤a；盖住，就是直接关系，中间没有第三个元，即若a<b且不存在cA，使得a<c<b。②偏序关系与哈斯图：画图注意四点：使用盖住的联系来表示，省略全部向上的箭头，省略自反性的自环，省略了传递性。反之，由哈斯图写偏序关系也要注意这四点，除了直接的盖住关系外，还有自反和传递也要写出来。8、求偏序关系的特殊元：设<A,≤>为偏序集，BA，bB，①若(x)(xBb≤x)为真，则称b为B的最小元。②若(x)(xBx≤b)为真，则称b为B的最大元。③若(x)(bxx≤b)为真，则称b为B的极小元。④若(x)(bxb≤x)为真，则称b为B的极大元。根据定义判断时，最小（大）元与极小（大）元是有区别的，最小（大）元是B中最小（大）的元素，它与B中其他元素都可比；而极小（大）元不一定与B中元素都可比，只要没有比它小（大）的元素，它就是极小（大）元。对于有穷集B，极小（大）元一定存在，且可能有多个，但最小（大）元不一定存在，若存在则必唯一。若B中只有一个极小（大）元，则它一定是B的最小（大）元。详见P689、求上界下界上确界和下确界：设<A,≤>为偏序集，BA，bA，①若(x)(xBb≤x)为真，则称b为B的下界。②若(x)(xBx≤b)为真，则称b为B的上界。③若b是一下界且对每一个B的下界b’有b’≤b，则称b为B的最大下界或下确界，记为glb。④若b是一上界且对每一个B的上界b’有b≤b’，则称b为B的最小上界或上确界，记为lub。判断时注意，上界下界上确界和下确界是A集合上来找的，B的上界，下界，最小上界，最大下界都可能不存在。若存在，最小上界和最大下界是唯一的。详见P69二、强化练习1.设Z+是正整数集，f：Z+×Z+→Z+，f(n，m)=nm，则f()A.仅是入射B.仅是满射C.是双射D.不是函数]2.关系矩阵所对应的关系具有自反性()A..D.3.设R1和R2是集合A上的相容关系，不是相容关系()4．集合A={1，2，…，10}上的关系R={<x，y>|x+y=10，x∈A，y∈A}，则R的性质是（）A．自反的B．对称的C．传递的、对称的 D．反自反的、传递的5．若R和S是集合A上的两个关系，则下述结论正确的是（）A．若R和S是自反的，则R∩S是自反的B．若R和S是对称的，则RS是对称的C．若R和S是反对称的，则RS是反对称的D．若R和S是传递的，则R∪S是传递的6．R={<1，4>，<2，3>，<3，1>，<4，3>}，则下列不是t（R）中元素的是（）A．<1，1>B．<1，2>C．<1，3>D．<1，4>7．设A={{1，2，3}，{4，5}，{6，7，8}}，下列选项正确的是（）A．1∈AB．{1，2，3}AC．{{4，5}}A D．∈A8．设M={x|f1(x)=0},N={x|f2(x)=0}，则方程f1(x)·f2(x)=0的解为（）A．M∩N B．M∪NC．MN D．M-N9．设A-B=，则有（）A．B= B．B≠C．AB D．AB10．A，B是集合，P（A），P（B）为其幂集，且A∩B=，则P(A)∩P(B)为（）A． B．{}C．{{}} D．{，{}}11．设A={1，2，3，4，5}，B={6，7，8，9，10}，以下关系是从A到B的入射函数的是A．f={<1,8>,<3,9>,<4,10>,<2,6>,<5,7>}B．f={<1,7>,<2,6>,<4,8>,<1,9>,<5,10>}C．f={<1,6>,<2,7>,<4,9>,<3,8>}D．f={<1,10>,<5,9>,<3,6>,<4,6>,<2,8>}12．下面关于关系R的传递闭包t(R)的描述最确切的是（）A．t(R)是包含R的二元关系 B．t(R)是包含R的最小传递关系C．t(R)是包含R的一个传递关系 D．t(R)是任何包含R的传递关系13.设A={l，2，3，4}，A上的二元关系R={<1，2>，<3，4>，<4，3>}，S={<l，3>，<3，4>，<4，1>}，则R～S=________，(RS)-1=________。14．设N是自然数集合，f和g是N到N的函数，且f（n）=2n+1，g（n）=n2，那么复合函数（ff）（n）=________（gf）（n）=________。15．设复合函数gf是从A到C的函数，如果gf是满射，那么________必是满射，如果gf是入射，那么________必是入射。16．设A={1，2}，B={2，3}，则A-A=________，A-B=________。17．设A={1，2}，B={2，3}，则AA=__________，AB=__________。18．设A={1，2，3，4}上关系R={<1,2>,<2,4>,<3,3>,<1,3>}，则R的自反闭包r(R)=_________，对称闭包S（R）=__________。19．设f:R→R,f(x)=x2-2,g:R→R,g(x)=x-1,那么复合函数=__________，=__________。20．设A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>},那么dom(A∪B)=_______,ran(A∩B)=__________。18．已知A={{}，{，1}}，B={{，1}，{1}}，计算A∪B，Aeq\o\ac(○,+)B，A的幂集P（A）。21．设A={a,b,c,d}，R={<a，b>，<a，d>，<b，c>，<c，a>，<d，a>}，求R的传递闭包。22.设A={2，3，6，12，24，36}，请画出A上整除关系的哈斯图，并给出子集{6，12，24，36}的下界、下确界、极大元、最大元。23．设A={1，2，3，4，6，8，12，24}，R为A上的整除关系，试画<A，R>的哈斯图，并求A中的最大元、最小元、极大元、极小元。24．若集合A={1，{2，3}}的幂集为P（A），集合B={{，2}，{2}}的幂集为P（B），求P(A)∩P(B)。25．X={1234}，R={<1,1>,<3,1>,<1,3>,<3,3>,<3,2>,<4,3>,<4,1>,<4,2>,<1,2>}。（1）画出R的关系图；（2）写出R的关系矩阵；（3）说明R是否具有自反、反自反、对称、传递性质。26．设A={a,b,c},P(A)是A的幂集，R为A上的包含关系，试给出<P(A),R>的哈斯图，并给出子集{{a,b},{a,c},{c}}的极大元、极小元、最大元、最小元。27．设R为N×N上的二元关系，对任意<a，b>,<c，d>∈N×N，<a，b>R<c，d>的充要条件是b=d，证明R为等价关系。28.设A={<a，b>|a，b∈Z+，Z+为整数集}，A上的关系R={<<a，b>,<c，d>>|ad=bc}，证明R是等价关系。29．R是集合A上自反和传递的关系，试证明：RR=R。离散数学复习第四章代数系统一、典型考查要点：1、运算的判断：方法：运算满足封闭性，即运算后产生的象仍在同一个集合中。详见P772、运算性质的判断：运算性质：封闭、结合、交换、分配、幂等、吸收、消去方法：根据定义，在所讨论的集中任取元素，符合定义即可。在运算表中可以判断：1）运算具有封闭性，当且仅当运算表中的每个元素都属于A。2）运算具有可交换性，当且仅当运算表关于主对角线是对称的。3）运算具有等幂性，当且仅当运算表的主对角线上的每一元素与它所在行（列）的表头元素相同。详见P793、代数系统中特殊元：么元（单位元）、零元、逆元判断方法：根据定义，在所讨论的集中找到特殊元，符合定义即可。在运算表中可以判断：1）A中关于运算具有零元，当且仅当该元素所对应的行和列中的元素都与该元素相同。2）A中关于运算具有幺元，当且仅当该元素所对应的行和列依次与运算表的行和列相一致。3）设A中关于运算具有幺元，a和b互逆，当且仅当位于a所在行和b所在列的元素及b所在行和a所在列的元素都是幺元。详见P804、子代数的判定：关键两个条件:BA,<B，>中的特殊元（么元或零元）与<A，>中相同。详见P825、特殊代数系统判定：（G，）封闭广群结合半群么元独异点可逆群，根据定义，满足条件即可。详见P866、群的证明：方法：根据群的四个条件，逐一验证即可，注意：对于么元和逆元，先根据运算特点解出么元和逆元，再验证。详见P867、群的性质：1、<G，⊙>是群∧|G|＞1<G，⊙>无零元。2、G，⊙>是群<G，⊙>中的唯一等幂元是幺元。3、群满足消去律：b⊙a=c⊙ab=c4、给定群<G，⊙>，则a⊙x=b群中方程解是唯一的。5、<G，⊙>是群(a⊙b)-1=b-1⊙a-1详见P878、子群及判定：三个判定定理根据已知条件选择，给定群<G，⊙>及非空HG，则1、<H，⊙>是<G，⊙>的子群a⊙b∈H，a-1∈H2、<H，⊙>是<G，⊙>的子群(a)(b)(a，b∈H→a⊙b-1∈H)非空有限集H则a⊙b∈H9、特殊群的判断：1、阿贝尔群即满足交换律的群2、循环群即群中每个元都由某一个元的n次幂生成，这个元就是生成元。3、同余类整数加法，乘法，<Z，+m><Z，×m>构成群：[i]+m[j]=[(i+j)(modm)][i]×m[j]=[(i×j)(modm)]10、环、整环、域之间的关系及判定：1、<R，+，·>，若①<R，+>是Abel群，②<R，·>是半群，③·对于+是可分配的，则称<R，+，·>是环2、可交换含幺环<R，+，·>，且无零因子，则称<R，+，·>为整环。3、可交换环<R，+，·>，若<R-{0}，·>为群，则称<R，+，·>为域4、环、整环、域之间的关系：域一定是整环，整环一定是环，反之不成立。详见P9311、格、子格、分配格、有补格的判定：1、格：即<A,≤>偏序集中，任意两个元素都有最小上界和最大下界。2、子格：子集，运算∨,∧封闭即可。3、分配格：含有五角格和钻石格为子图的都不是分配格，但链是分配格。4、有补格：每个元素都至少有一个补元素的有界格。求补元时，满足：a∨b=1(即全上界)，和a∧b=0(即全下界)详见P97二、强化练习1.在整数集上，不是二元运算()A.加法B.减法C.乘法D.除法2.设A是奇数集合，×为乘法运算，则<A，×>是()A.半群B.群C.循环群D.交换群3.不满足结合律是()*b=min(a，b)*b=max(a，b)*b=2(a+b) *b=2ab4．在N上，可结合的是（）A．ab=a-2bB．ab=min{a，b}C．ab=-a-bD．ab=|a-b|5．整环和域是（）A整环一定是域B域不一定是整环C域一定是整环D域一定不是整环6．设集合A={1，2，3，……，10}，A上是不封闭的是（）A．x*y=max{x,y} B．x*y=min{x,y}C．x*y=GCD{x,y},即x,y的最大公约数D．x*y=LCM{x,y},即x,y的最小公倍数7．设H，K是群（G，）的子群，下面代数系统是（G，）的子群的是（）A．（H∩K，） B．（H∪K，）C．（K-H，） D．（H-K，）4．下列所示的哈斯图所对应的偏序集中能构成格的是（）A．B．C． D．8.代数系统<A，*，>是整环，则<A，*>是________，<A，>是________，且无零因子。9.在实数集R上定义运算ab=a+b+ab，则幺元为________，元素2的逆元为________。10．设S是非空有限集，代数系统<P（S），∪>中，其中P（S）为集合S的幂集，则P（S）对∪运算的单位元是________，零元是________。11．在<Z6,eq\o\ac(○,+)>中，2的阶是________。12．设<A，≤>是格，其中A={1，2，3，4，6，8，12，24}，≤为整除关系，则3的补元是________。13．有理数集Q中的*运算定义如下：a*b=a+b-ab，则*运算的单位元是__________，设a有逆元，则其逆元a-1=__________。14．<Zn,>是一个群，其中Zn={0,1,2,……,n-1},xy=(x+y)modn，则在<Z6,>中，1的阶是__________，4的阶是__________。15．设H是形如的2×2阶矩阵的集合，H中定义通常的矩阵乘法运算。验证H是群，=。16．在整数集Z上定义：，证明：<Z，>是一个群。17．设H是G的有限子集，则<H，>是群<G，>的子群当且仅当<H，>是群<G，>的子代数。离散数学复习第五章图论一、典型考查要点1、图的基本概念：方法：度：点连接的边的条数，自环算2度；生成子图：点不减少，边减少；完全图：每个点都与余下的点有边；同构：两个图总可以画成相同的。详见P1102、握手定理：结点度数总和等于边数的两倍，即deg(v)=2|E|，用于边点度之间的计算。3、路的两个定理及证明：1、在一个具有n个结点的图中，如果从结点vj到vk存在一条路，则从结点vj到vk存在一条不多于n-1条边的路。推论：在一个具有n个结点的图中，若从结点vj到vk存在一条路，则必存在一条从vj到vk而边数小于n的通路。详见P1154、连通图的判定及证明：1、无向连通图：任意两点都有路，即都走得通，只有一个连通分支。2、有向图中：强连通，任意两点都有路，即都走得通；弱连通，去掉方向后才连通；单侧连通，每对点，只要一个点可达另一点。3、强连通的充要条件证明：一个有向图是强连通的充分必要条件是G有一个回路，它至少包含每个结点一次。详见P116-1175、边割集、点割集的判定及证明：点割集：图中去掉这些点及关联的边后，恰好不连通。定理：一个连通无向图G中的结点v是割点的充分必要条件是存在两个结点u和w，使得结点u和w的每一条路都通过v。边割集：图中去掉这些边后，恰好不连通，连通分支变为2。定理：G的一条边e不包含在G的回路中当且仅当e是G的割边。详见P116-1176、邻接矩阵、可达矩阵的表示：邻接矩阵：，表示图中点与点的关系，可以利用它的Ak来求长度为k的路的条数，即定理：设A为简单图G的邻接矩阵，则Ak中的i行j列元素akij等于G中联结vi到vj的长度为k的链(或路)的数目。可达矩阵：可以利用它来判定连通性，全为1，就是连通的。详见P117-1187、欧拉图及应用：欧拉路：边遍行且只能一次的路，点可以重复。欧拉回路：边遍行且只能一次的回路。判定：欧拉路存在当且仅当G连通，且有零个或两个奇数度结点。欧拉回路存在当且仅当G连通，并且所有点度数都为偶数。应用到一笔画问题，即有没有欧拉路。8、汉密尔顿图及应用：汉密尔顿路：点遍行且只能一次的路。汉密尔顿回路：点遍行且只能一次的回路。判定：1、必要条件：若图有汉密尔顿回路，则V的每个非空子集S均有W(G-S)≤|S|，其中W(G-S)是G-S的连通分支数。可以利用这个必要条件来判定有些图不是汉密尔顿图。2、充分条件：图G有n个点的简单图,如果每一对结点度数之和大于等于n-1,则G中存在一条汉密尔顿路。若每一对结点度数之和大于等于n,则存在汉密尔顿回路。3、应用到网路连通、朋友开会排座位等，就是先利用题目中的联系，有关系就确定一条边，构造一个图，找一条汉密尔顿路或汉密尔顿回路即可。详见P1219、平面图的判定：1、平面图：画在平面上，边不相交叉。判定：平面图不含与K3,3,或K5同胚的子图。K3,3,K5及彼得森图都不是平面图。2、欧拉公式：n-m+r=2,计算边点面之间的关系问题。面的次数即围着这个面的边的条数，单独的边要算2次。必要条件：给定连通简单平面图G=<V，E，>。若|V|≥3，则e≤3v-6。详见P12510、树的6个等价