离散数学--总复习

第一部分：集合论知识点：集合关系（，,,,=）集合运算（并、交、差、对称差、补集、幂集），特殊集合（，E，P(A)）集合恒等式（幂等律、交换律、结合律、分配律、吸收律、德摩根律、补交转换律(A-B=A~B)、德·摩根律(BC)=BC，A(BC)=(AB)(AC)）证明集合包含或相等（根据定义,通过逻辑等值演算证明、利用已知集合等式或包含式,通过集合演算证明）1.证:A(BC)=(AB)(AC)证xxA(BC)xA(xBxC)(并,交的定义)(xAxB)(xAxC)(逻辑演算的分配律)x(AB)(AC)2.证明(A-B)-C=(A-C)-(B-C)证(A-C)-(B-C)=(A~C)~(B~C)(补交转换律)=(A~C)(~B~~C)(德摩根律)=(A~C)(~BC)(双重否定律)=(A~C~B)(A~CC)(分配律)=(A~C~B)(A)(矛盾律)=A~C~B(零律,同一律)=(A~B)~C(交换律,结合律)=(A–B)–C第二部分：逻辑学命题的定义（凡具有确定真假意义的陈述句均称为命题。）联结词（、∧、∨、、、、（公式转化为只含、的表达形式））例：将pq化为只含的公式pqpq(p∧q)pqp(q∧q)pqq命题符号化(1、王晓虽然聪明，但不用功.2、张辉与王丽都是三好生.3、张辉与王丽是同学.4、除非天冷，小王才穿羽绒服.5、除非小王穿羽绒服，否则天不冷.)等值演算（幂等律、交换律、结合律、分配律、吸收律、蕴涵等值式ABAB等价等值式AB(AB)(BA)假言易位等值式ABBA等价否定等值式ABAB）证明p(qr)(pq)r证p(qr)p(qr)（蕴涵等值式）(pq)r（结合律）(pq)r（德摩根律）(pq)r（蕴涵等值式）判断下列公式的类型q(pq)解q(pq)q(pq)（蕴涵等值式）q(pq)（德摩根律）p(qq)（交换律，结合律）p0（矛盾律）0（零律）该式为矛盾式.命题公式（重言式、矛盾式、可满足式），利用真值表判断，等值演算，范式。范式（析取范式、合取范式）求p(pqr)的主合取范式和主析取范式解p(pqr)(pqr)(pqr)(pqr)M4M5M6M7pqrM1得p(pqr)M1M4M5M6M7(1,4,5,6,7)(0,2,3)主析取范式的用途:(1)求公式的成真赋值和成假赋值例如(pq)rm0m2m4m5m6成真赋值:000,010,100,101,110;成假赋值:001,011,111(2)判断公式的类型Bp(pq)1m0m1m2m3重言式(3)判断两个公式是否等值p与(pq)(pq)解pp(qq)(pq)(pq)m2m3(pq)(pq)(pq)(pq)(pq)(pq)m2m3故p(pq)(pq)(4)选派人员某单位要从A,B,C三人中选派若干人出国考察,需满足下述条件:(1)若A去,则C必须去;(2)若B去,则C不能去;(3)A和B必须去一人且只能去一人.问有几种可能的选派方案?解记p:派A去,q:派B去,r:派C去(1)pr,(2)qr,(3)(pq)(pq)求下式的成真赋值A=(pr)(qr)((pq)(pq))求A的主析取范式A=(pr)(qr)((pq)(pq))(pr)(qr)((pq)(pq))((pq)(pr)(rq)(rr))((pq)(pq))((pq)(pq))((pr)(pq))((rq)(pq))((pq)(pq))((pr)(pq))((rq)(pq))(pqr)(pqr)成真赋值:101,010结论:方案1派A与C去,方案2派B去推理规则（附加律A(AB)化简律(AB)A假言推理(AB)AB拒取式(AB)BA析取三段论(AB)BA假言三段论(AB)(BC)(AC)）(1)直接证明法在自然推理系统P中构造下面推理的证明:前提:pq,qr,ps,s结论:r(pq)证明①ps前提引入②s前提引入③p①②拒取式④pq前提引入⑤q③④析取三段论⑥qr前提引入⑦r⑤⑥假言推理⑧r(pq)⑦④合取推理正确,rÙ(pÚq)是有效结论(2)附加前提证明法例4构造下面推理的证明:前提:pq,qr,rs结论:ps证明①p附加前提引入②pq前提引入③q①②析取三段论④qr前提引入⑤r③④析取三段论⑥rs前提引入⑦s⑤⑥假言推理推理正确,ps是有效结论(3)归谬法(反证法)构造下面推理的证明前提:(pq)r,rs,s,p结论:q证明用归缪法①q结论否定引入②rs前提引入③s前提引入④r②③拒取式(4)归结证明法用归结证明法构造下面推理的证明:前提:(pq)r,rs,s结论:(pq)(ps)解(pq)r(pq)r(pq)r(pr)(qr)rsrs(pq)(ps)(pq)(ps)(pq)(ps)p(qs)一个公安人员审查一件盗窃案，已知的事实如下：A或B盗窃了钻石；若A盗窃了钻石，则作案时间不能发生在午夜前；若B证词正确，则在午夜时屋里灯光未灭；若B证词不正确，则作案时间发生在午夜前；午夜时屋里灯光灭了。谁盗窃了钻石呢？一阶逻辑个体词、谓词与量词命题符号化(1)人都爱美;(2)有人用左手写字个体域分别取(a)人类集合,(b)全总个体域.解:(a)(1)设F(x):x爱美,符号化为xF(x)(2)设G(x):x用左手写字,符号化为xG(x)(b)设M(x):x为人，F(x),G(x)同(a)中(1)x(M(x)F(x))(2)x(M(x)G(x))M(x)称作特性谓词量词的辖域、约束出现、自由出现一阶逻辑等值演算消去量词等值式设D={a1,a2,…,an}xA(x)A(a1)A(a2)…A(an)xA(x)A(a1)A(a2)…A(an)量词辖域收缩与扩张等值式：关于全称量词的：x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x))BxA(x)关于存在量词的:x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x))BxA(x)量词否定等值式设A(x)是含x自由出现的公式xA(x)xA(x)xA(x)xA(x)量词分配等值式x(A(x)B(x))xA(x)xB(x)x(A(x)B(x))xA(x)xB(x)置换规则，换名规则，代替规则例：消去公式中既约束出现、又自由出现的个体变项x(F(x,y)yG(x,y,z))x(F(x,y)tG(x,t,z))换名规则或者x(F(x,t)yG(x,y,z))代替规则例：设个体域D={a,b,c},消去下面公式中的量词:(1)x(F(x)G(x))(F(a)G(a))(F(b)G(b))(F(c)G(c))前束范式例：求公式xF(x)xG(x)的前束范式解xF(x)xG(x)量词否定等值式x(F(x)G(x))量词分配等值式第三部分：关系有序对与笛卡儿积例：2,x+5=3y4,y，求x,y.解3y4=2,x+5=yy=2,x=3例：A={0,1},B={a,b,c}，求AB。AB={0,a,0,b,0,c,1,a,1,b,1,c}二元关系有序对集合或空集关系的表示（关系的集合表达式、关系矩阵、关系图）例：A={a,b,c,d},R={a,a,a,b,a,c,b,a,d,b},R的关系矩阵MR和关系图GR如下：关系的基本运算（逆、合成、幂运算）例：R={1,2,2,3,1,4,2,2}S={1,1,1,3,2,3,3,2,3,3}R1={2,1,3,2,4,1,2,2}R∘S={1,3,2,2,2,3}S∘R={1,2,1,4,3,2,3,3}幂运算：设R为A上的关系,n为自然数,则R的n次幂是(1)R0={x,x|x∈A}=IA(2)Rn+1=Rn∘R求法：关系矩阵乘法，关系图（走n步），集合表示（n个合成）关系性质（自反性与反自反性、对称性与反对称性、传递性）自反性反自反性对称性反对称性传递性关系矩阵主对角线元素全是1主对角线元素全是0矩阵是对称矩阵若rij＝1,且i≠j,则rji＝0对M2中1所在位置,M中相应位置都是1关系图每个顶点都有环每个顶点都没有环如果两个顶点之间有边,一定是一对方向相反的边(无单边)如果两点之间有边,一定是一条有向边(无双向边)如果顶点xi到xj有边,xj到xk有边,则从xi到xk也有边闭包集合表示(1)r(R)=R∪R0(2)s(R)=R∪R-1(3)t(R)=R∪R2∪R3∪…∪Rn矩阵表示Mr=M+EMs=M+M’Mt=M+M2+M3+…Mn关系图：加环，加双边，可达加边Warshall求对称闭包（效率高）0010000000010111特殊关系：等价关系与偏序关系等价关系(自反，对称，传递)如模n偏序关系（自反，反对称，传递）如小于等于关系可比，覆盖，哈斯图，最小（大）元，极小（大）元第四部分：图论无序对与多重集合度数，握手定理简单图（无平行边和环）、完全图（每点都与其他点相邻）、正则图（度都相等）、圈图、轮图、方体图子图（生成子图，导出子图）、补图图的连通性初级通路(回路)与简单通路(回路)短程线与距离点割集与边割集点连通度与边连通度图的矩阵表示（关联矩阵（点边），邻接矩阵（点点），可达矩阵（主对角线上的元素全为1））有向图中的通路数与回路数（利用邻接矩阵）特殊的图二部图充要条件：无奇数长度回路，可以用来分配工作问题欧拉图充要条件：连通的且无奇度顶点哈密顿图：必要条件：对于V的任意非空真子集V1均有p(GV1)|V1|.充分条件：设G是n(n3)阶无向简单图,任意两个不相邻的顶点的度数之和大于等于n应用：有7个人,A会讲英语,B会讲英语和汉语,C会讲英语、意大利语和俄语,D会讲日语和汉语,E会讲德语和意大利语,F会讲法语、日语和俄语,G会讲法语和德语.问能否将他们沿圆桌安排就坐成一圈,使得每个人都能与两旁的人交谈?解：作无向图,每人是一个顶点,2人之间有边他们有共同的语言平面图：平面图的面与次数：平面图各面的次数之和等于边数的2倍欧拉公式：设G为n阶m条边r个面的连通平面图,则nm+r=2第五部分：树无向树（连通无回路的无向图）、树叶，分支点性质（G是连通的且m=n1;G中无回路且m=n1;G是连通的且G中任意一条边均为桥）生成树、基本回路、基本割集带权图的最小生成树，kruskal法有向树、根树、根、叶、内点、分支点、层、树高求最优2元树的算法：哈夫曼(Huffman)算法最佳前缀码、用2元树产生2元前缀码的方法例：在通信中,设八进制数字出现的频率(%)如下:0:25,1:20,2:15,3: