资源描述：
《离散最后总结》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、主要内容：1.命题符号化：命题逻辑和谓词逻辑都有考察。否定式与否定联结词”“非P”合取式与合取联结词“A”“P并且q”析取式与析取联结词“V”“P或q”蕴涵式与蕴涵联结词“T”“如果p,则q”相同的表达为“若P，就q”“只要P，就q”“P仅当q”“只有q才P”“除非q,才P”“除非q，否则非P”练习：如果交通不阻塞，他就不会迟到；除非交通阻塞，否则他不会迟到.2.判断两个命题公式是否等值，判断公式的类型(重言式，矛盾式，可满足式)：会用真值表和等值演算或主析取范式法(主合取范式)。若等价式ATB是重言式，则称A与B等值，记作AOB,并称A与B是等值式判断公式类型：重言式，矛盾式，可满足式；
2、主要用真值表和等值演算或主析取范式法儿个常用的等值演算蕴涵等值式：AtBotWB等价等值式：(A->B)a(B^A)假言易位：A—>B<=>-iB—>-iA等价否定等值式：AoBo「Ao「B归谬论：(AtB)a(At「B)A主析取范式——由极小项构成的析取范式主合取范式——由极人项构成的合取范式例如，n=3,命题变项为p,q,r时，(-«pa-)qar)v(-)paqar)<=>mlvm3主析取范式(-«pv-iqv-«r)a(pvqv-r)u>M7vMl主合取范式练习：证明p->(q->r)$(pTq)Tr3.命题逻辑推理理论：推理定律的考察P45-P46O重要的推理定律附加律化简律假言
3、推理拒取式析取三段论假言三段论等价三段论构造性二难构造性二难(特殊形式)破坏性二难r：我冇课，s：我备课A=>(AvB)(AaB)=>A(A->B)aA=>B(A—>B)a—iB=>—iA(AvB)a-.Bz=>A(AtB)a(BtC)=>(AtC)(A<^B)a(BoC)=>(AoC)(A^B)a(C^D)a(AvC)=>(BvD)(AtB)a(「AtB)/(A—A)=>B(A->B)a(C->D)a(-iBviD)=>(-,Av-.C)例子：构造证明形式结构前提：(pvq)->r,结论：-iPA-iq证明r—>s,-is%1tts%1一4、是星期三,③④⑤⑥4.5.-ir(pvq)TT-i(pvq)-iPA-)q谓词逻辑：①②拒取式前提引入③④拒収式⑤置换给定谓词公式的最词辖域的判断；自由变元，约束变元的判断。关系的合成运算。R°S=
5、
6、3y«x,y>eRAeS)例如R二{<1,2>,<2,3>,<1,4>,<2,2>}S={<1,1>,<1,3>,<2,3>,<3,2>,<3,3>}6.设f：(1)(2)(3)函数满射、单射、双射的判断。A->B,g：B->C.如果f：AT,g：B_C都是满射的,如果f：A->B,g：B->C都是单射的,如果f：A-B,g：B->C都是双射的,则fog：A-C也是满射的
7、.则fog：A-*C也是单射的.则fog：A->C也是双射的.7.简单通路的判断。所冇边各异(都不相同)，则称「为简单通路，又若巾二仏则称「为简单回路8.二元关系的定义。定义7.3如果一个集合满足以下条件之一：(1)集合非空，且它的元素都是有序对(2)集合是空集记作R例如：WR,可记作xRy；如果〈x,y>^R,则记作xXY9.图的顶点和边的关系(握手定理)oG中每条边(包括环)均有两个端点，所以在计算&中各顶点度数之和吋，每条边均捉供2度，当然/〃条边共提供2/〃度.10.树的定义，充分必要条件。(1)&是树(2)&中任意两个顶点之间存在惟一的路径.(3)&中无回路且iipn-
8、i.(4)&是连通的且/7F/2-1.11.无向完全图Kn的定义(点和边的关系)。(1)/7(/7>1)阶无向完全图——每个顶点与其余顶点均相邻的无向简单图.简单性质:边数心冒,△"*1(2)n(虑1)阶冇向完全图——每对顶点Z间均冇两条方向相反的冇向边的冇向简单图.简单性质:m=n（n-】）,△=5=2（/?一1）,A+==n-12.代数系统同类型的判定：子群的判定定义：两个系统冇相同元数运算符，都有单位元，零元子群的判定定义10.5：设G是群，H是G的非空子集，如果H关于G中的运算构成群，则称H是G的子群，记作HWG.i设G是群，II是G的非空了集，则II是G的了群的充要条件是：(1
9、)a,bell有abWlL(2).aeii有eH.TT设G为群，H是G的非空了集.H是G的了群当H.仅当a,bell有iii设G为群，H是G的非空有焙集,则H是G的子群当且仅当a,ben有abWH.7.群：给定一个群，计算-其中元素的“阶”例：定理11.4G为群，aGGA
10、a
11、=r.设k是整数，则(1)ak=e当H•仅当r
12、k(2)
13、a'1
14、=
15、a
16、8.集合计数(包含排斥原理)，集合的元素与集合的关系判断，看第六章的PP
