离散数学公式

基本等值式1.双重否定律A┐┐A2.幂等律AA∨A,AA∧A3.交换律A∨BB∨A，A∧BB∧A4.结合律(A∨B)∨CA∨(B∨C)(A∧B)∧CA∧(B∧C)5.分配律A∨(B∧C)(A∨B)∧(A∨C)（∨对∧的分配律）A∧(B∨C)(A∧B)∨(A∧C)（∧对∨的分配律）6.德·摩根律┐(A∨B)┐A∧┐B┐(A∧B)┐A∨┐B7.吸收律A∨(A∧B)A，A∧(A∨B)A8.零律A∨11,A∧009.同一律A∨0A，A∧1A10.排中律A∨┐A111.矛盾律A∧┐A012.蕴涵等值式A→B┐A∨B13.等价等值式AB(A→B)∧(B→A)14.假言易位A→B┐B→┐A15.等价否定等值式AB┐A┐B16.归谬论(A→B)∧(A→┐B)┐A求给定公式范式的步骤(1)消去联结词→、(若存在)。(2)否定号的消去(利用双重否定律)或内移(利用德摩根律)。(3)利用分配律：利用∧对∨的分配律求析取范式，∨对∧的分配律求合取范式。推理定律--重言蕴含式(1)A(A∨B)附加律(2)(A∧B)A化简律(3)(A→B)∧AB假言推理(4)(A→B)∧┐B┐A拒取式(5)(A∨B)∧┐BA析取三段论(6)(A→B)∧(B→C)(A→C)假言三段论(7)(AB)∧(BC)(AC)等价三段论(8)(A→B)∧(C→D)∧(A∨C)(B∨D)构造性二难(A→B)∧(┐A→B)∧(A∨┐A)B构造性二难(特殊形式)(9)(A→B)∧(C→D)∧(┐B∨┐D)(┐A∨┐C)破坏性二难设个体域为有限集D={a1,a2,…,an},则有（1）xA(x)A(a1)∧A(a2)∧…∧A(an)（2）xA(x)A(a1)∨A(a2)∨…∨A(an)设A(x)是任意的含自由出现个体变项x的公式，则（1）┐xA(x)x┐A(x)（2）┐xA(x)x┐A(x)设A(x)是任意的含自由出现个体变项x的公式，B中不含x的出现，则（1）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)（2）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)，B(x)是任意的含自由出现个体变项x的公式，则（1）x(A(x)∧B(x))xA(x)∧xB(x)（2）x(A(x)∨B(x))xA(x)∨xB(x)全称量词“”对“∨”无分配律。存在量词“”对“∧”无分配律。xA(x)xA(x)UI规则。或A(y)A(c)UG规则。A(y)xA(x)EG规则。A(c)xA(x)EI规则。xA(x)A∪B＝{x|x∈A∨x∈B}A(c)、A∩B＝{x|x∈A∧x∈B}A－B＝{x|x∈A∧xB}幂集P(A)＝{x|xA}对称差集AB＝(A－B)∪(B－A)AB＝(A∪B)－(A∩B)绝对补集～A＝{x|xA}广义并∪A＝{x|z(z∈A∧x∈z)}广义交∩A＝{x|z(z∈A→x∈z)}设A＝{{a,b,c},{a,c,d},{a,e,f}}B＝{{a}}C＝{a,{c,d}}则∪A＝{a,b,c,d,e,f}∪B＝{a}∪C＝a∪{c,d}∪＝∩A＝{a}∩B＝{a}∩C＝a∩{c,d}集合恒等式幂等律A∪A＝AA∩A＝A结合律(A∪B)∪C＝A∪(B∪C)(A∩B)∩C＝A∩(B∩C)交换律A∪B＝B∪AA∩B＝B∩A分配律A∪(B∩C)＝(A∪B)∩(A∪C)A∩(B∪C)＝(A∩B)∪(A∩C)同一律A∪＝AA∩E＝A零律A∪E＝EA∩＝排中律A∪～A＝E矛盾律A∩～A＝吸收律A∪(A∩B)＝AA∩(A∪B)＝A德摩根律A－(B∪C)＝(A－B)∩(A－C)A－(B∩C)＝(A－B)∪(A－C)～(B∪C)＝～B∩～C～(B∩C)＝～B∪～C～＝E～E＝双重否定律～(～A)＝A集合运算性质的一些重要结果A∩BA，A∩BBAA∪B，BA∪BA－BAA－B＝A∩～BA∪B＝BABA∩B＝AA－B＝AB＝BA(AB)C＝A(BC)A＝AAA＝AB＝ACB＝C对偶(dual)式：一个集合达式，如果只含有∩、∪、～、、E、＝、、，那么同时把∩与∪互换，把与E互换，把与互换，得到式子称为原式的对偶式。有序对具有以下性质：（1）当x≠y时，≠。（2）＝的充分必要条件是x＝u且y＝v。笛卡儿积的符号化表示为A×B＝{|x∈A∧y∈B}如果|A|=m,|B|=n,则|A×B|=mn。笛卡儿积的运算性质(1)对任意集合A，根据定义有A×＝,×A＝(2)一般的说，笛卡儿积运算不满足交换律，即A×B≠B×A(当A≠∧B≠∧A≠B时)(3)笛卡儿积运算不满足结合律，即(A×B)×C≠A×(B×C)(当A≠∧B≠∧C≠时)(4)笛卡儿积运算对并和交运算满足分配律，即A×(B∪C)=(A×B)∪(A×C)(B∪C)×A=(B×A)∪(C×A)A×(B∩C)=(A×B)∩(A×C)(B∩C)×A=(B×A)∩(C×A)(5)AC∧BDA×BC×D常用的关系对任意集合A，定义全域关系EA={|x∈A∧y∈A}=A×A恒等关系IA={|x∈A}空关系小于或等于关系：LA={|x,y∈A∧x≤y}，其中AR。整除关系：DB={|x,y∈B∧x整除y}，其中AZ*，Z*是非零整数集包含关系：R＝{|x,y∈A∧xy}，其中A是集合族。关系矩阵和关系图设A={1,2,3,4}，R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}，则R的关系矩阵和关系图分别是11000011MR00000100定义域domR＝{x|y(∈R)}值域ranR＝{y|x(∈R)}域fldR＝domR∪ranR例求R={<1,2>,<1,3>,<2,4>,<4,3>}的定义域、值域和域。解答domR＝{1,2,4}ranR＝{2,3,4}fldR＝{1,2,3,4}逆R-1＝{|∈R}右复合FG＝{|t(∈F∧∈G)}限制R↑A={|xRy∧x∈A}像R[A]=ran(R↑A)例设R＝{<1,2>，<1,3>，<2,2>，<2,4>，<3,2>}R↑{1}＝{<1,2>，<1,3>}R↑＝R↑{2,3}＝{<2,2>，<2,4>}，<3,2>}R[{1}]＝{2,3}R[]＝R[{3}]＝{2}设F是任意的关系，则(1)(F-1)-1＝F(2)domF-1＝ranF，ranF-1＝domF设F，G，H是任意的关系，则(1)(FG)H＝F(GH)(2)(FG)-1＝G-1F-1设R为A上的关系，则RIA＝IAR＝R设F，G，H是任意的关系，则(1)F(G∪H)＝FG∪FH(2)(G∪H)F＝GF∪HF(3)F(G∩H)FG∩FH(4)(G∩H)FGF∩HF设F为关系，A,B为集合，则(1)F↑(A∪B)＝F↑A∪F↑B(2)F[A∪B]＝F[A]∪F[B](3)F↑(A∩B)＝F↑A∩F↑B(4)F[A∩B]F[A]∩F[B]关系的幂运算设R为A上的关系，n为自然数，则R的n次幂定义为：（1）R0＝{|x∈A}＝IA（2）Rn+1＝RnR幂运算的性质设A为n元集，R是A上的关系，则存在自然数s和t,使得Rs=Rt。设R是A上的关系，m,n∈N，则(1)RmRn＝Rm+n(2)(Rm)n＝Rmn设R是A上的关系，若存在自然数s,t(s∈R)，反自反x(x∈A→R)，对称xy(x,y∈A∧∈R→∈R)反对称xy(x,y∈A∧∈R∧∈R→x=y)，传递xyz(x,y,z∈A∧∈R∧∈R→∈R)关系性质的等价描述设R为A上的关系，则（1）R在A上自反当且仅当IAR（2）R在A上反自反当且仅当R∩IA＝（3）R在A上对称当且仅当R＝R-1（4）R在A上反对称当且仅当R∩R-1IA（5）R在A上传递当且仅当RRR(1)若R1，R2是自反的和对称的，则R1∪R2也是自反的和对称的。(2)若R1和R2是传递的，则R1∩R2也是传递的。关系性质的特点自反性反自反性对称性反对称性传递性集合表达式IARR∩IA＝R＝R-1R∩R-1IARRR关系矩阵主对角线元素主对角线元素全矩阵是对称矩阵若rij＝1，且i对M2中1所在位全是1是0≠j，则rji＝0置，M中相应的位置都是1关系图每个顶点都有每个顶点都没有如果两个顶点之如果两点之间有如果顶点xi到xj环环间有边，一定是边，一定是一条有有边，xj到xk有一对方向相反的向边(无双向边)边，则从xi到xk边(无单边)也有边关系的性质和运算之间的关系自反性反自反性对称性反对称性传递性R1-1√√√√√R1∩R2√√√√√R1∪R2√√√××R1－R2×√√√×R1R2√××××闭包的构造

方法

快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载

设R为A上的关系，则有（1）自反闭包r(R)＝R∪R0（2）对称闭包s(R)＝R∪R-1（3）t(R)＝R∪R2∪R3∪…关系性质与闭包运算之间的联系设R是非空集合A上的关系，（1）若R是自反的，则s(R)与t(R)也是自反的。（2）若R是对称的，则r(R)与t(R)也是对称的。（3）若R是传递的，则r(R)是传递的。等价类的性质设R是非空集合A上的等价关系，则（1）x∈A，[x]是A的非空子集。（2）x,y∈A，如果xRy，则[x]＝[y]。（3）x,y∈A，如果R，则[x]与[y]不交。（4）∪{[x]|x∈A}＝A。偏序集中的特殊元素设为偏序集，BA，y∈B。（1）若x(x∈B→y≤x)成立，则称y为B的最小元。（2）若x(x∈B→x≤y)成立，则称y为B的最大元。（3）若x(x∈B∧x≤y→x＝y)成立，则称y为B的极小元。（4）若x(x∈B∧y≤x→x＝y)成立，则称y为B的极大元2436B最大元最小元极大元极小元12{2,3,6,12,24,36}无无24，362,3{6,12}1261266{2,3,6}6无62,3{6}666623B上界下界上确界下确界{2,3,6,12,24,36}无无无无{6,12}12,24,362,3,6126{2,3,6}6,12,24,36无6无{6}6,12,24,36,2,3,6,66函数相等由定义可知，两个函数F和G相等,一定满足下面两个条件：（1）domF＝domG（2）x∈domF＝domG，都有F(x)＝G(x)所有从A到B的函数的集合记作BA，读作“B上A”，符号化表示为BA＝{f|f：A→B}。例：设A＝{1,2,3}，B＝{a,b}，求BA。BA＝{f0,f1,f2,f3,f4,f5,f6,f7}。其中f0＝{<1,a>,<2,a>,<3,a>}f1＝{<1,a>,<2,a>,<3,b>}f2＝{<1,a>,<2,b>,<3,a>}f3＝{<1,a>,<2,b>,<3,b>}f4＝{<1,b>,<2,a>,<3,a>}f5＝{<1,b>,<2,a>,<3,b>}f6＝{<1,b>,<2,b>,<3,a>}f7＝{<1,b>,<2,b>,<3,b>}设f:A→B，（1）若ranf＝B，则称f:A→B是满射(surjection)的。（2）若y∈ranf都存在唯一的x∈A使得f(x)＝y，则称f:A→B是单射(injection)的。（3）若f既是满射又是单射的，则称f:A→B是双射(bijection)1aaa1a112bb2b2b32cc3c3c43d4d4d单射双射函数满射例：判断下面函数是否为单射、满射、双射的，为什么?(1)f：R→R，f(x)=-x2+2x-1(2)f：Z+→R，f(x)=lnx，Z+为正整数集(3)f：R→Z，f(x)=x(4)f：R→R，f(x)=2x+1。解（1）f在x=1取得极大值0。既不是单射也不是满射的。（2）f是单调上升的，是单射的，但不满射。ranf={ln1,ln2,…}。（3）f是满射的，但不是单射的，例如f(1.5)=f(1.2)=1。（4）f是满射、单射、双射的，因为它是单调函数并且ranf=R。例：(1)给定无向图G＝，其中V＝{v1,v2,v3,v4,v5}，E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}.(2)给定有向图D=，其中V＝{a,b,c,d}，E＝{,,,,,,}。画出G与D的图形。邻域：NG(v1)＝{v2，v5}后继元集：Г+D(d)＝{c}闭邻域：NG(v1)＝{v1，v2，v5}先驱元集：Г-D(d)＝{a，c}关联集：IG(v1)＝{e1，e2，e3}邻域：ND(d)＝{a，c}闭邻域：ND(d)＝{a，c，d}d(v1)＝4(注意，环提供2度)，出度：d+(a)＝4，入度：d-(a)＝1△＝4，δ＝1，(环e1提供出度1，提供入度1)，v4是悬挂顶点，e7是悬挂边。d(a)＝4+1＝5。△＝5，δ＝3，△+＝4(在a点达到)度数列为4,4,2,1,3。δ+＝0(在b点达到)△-＝3(在b点达到)δ-＝1(在a和c点达到)按字母顺序，度数列：5,3,3,3出度列：4,0,2,1入度列：1,3,1,2设G＝是n阶m条边的无向图，则下面各命题是等价的：（1）G是树。（2）G中任意两个顶点之间存在唯一的路径。（3）G中无回路且m＝n1。（4）G是连通的且m＝n1。（5）G是连通的且G中任何边均为桥。（6）G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈。例题已知无向树T中，有1个3度顶点，2个2度顶点，其余顶点全是树叶，试求树叶数，并画出满足

要求

对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗

的非同构的无向树。解答设有x片树叶，于是结点总数n＝1+2+x＝3+x由握手定理和树的性质m＝n1可知，2m＝2(n1)＝2×(2+x)＝1×3+2×2+x解出x＝3，故T有3片树叶。故T的度数应为1、1、1、2、2、3。求最小生成树的算法（避圈法(Kruskal)）(1)设n阶无向连通带权图G＝有m条边。不妨设G中没有环（否则，可以将所有的环先删去），将m条边按权从小到大排序：e1,e2,…,em。(2)取e1在T中。(3)依次检查e2,…,em，若ej(j≥2)与已在T中的边不构成回路，取ej也在T中，否则弃去ej。(4)算法停止时得到的T为G的最小生成树为止。例：求下图所示两个图中的最小生成树。W(T1)＝6W(T2)＝12T是n(n≥2)阶有向树，(1)T为根树—T中有一个顶点入度为0，其余顶点的入度均为1(2)树根——入度为0的顶点(3)树叶——入度为1，出度为0的顶点(4)内点——入度为1，出度不为0的顶点(5)分支点——树根与内点的总称(6)顶点v的层数——从树根到v的通路长度(7)树高——T中层数最大顶点的层数根树的画法：树根放上方，省去所有有向边上的箭头。树叶——8片内点——6个分支点——7个高度——5求带权为1、1、2、3、4、5的最优树。W(T)=38中序行遍法：ba(fdg)ce前序行遍法：ab(c(dfg)e)后序行遍法：b((fgd)ec)a├断定符（公式在L中可证）EG存在推广规则（存在量词引入规则）╞满足符（公式在E上有效，公式在E上可满足）ES存在量词特指规则（存在量词消去规则）┐命题的“非”运算UG全称推广规则（全称量词引入规则）∧命题的“合取”（“与”）运算US全称特指规则（全称量词消去规则）∨命题的“析取”（“或”，“可兼或”）运算→命题的“条件”运算↔命题的“双条件”运算的A<=>B命题A与B等价关系A=>B命题A与B的蕴涵关系R关系r相容关系A*公式A的对偶公式R○S关系与关系的复合wff合式公式domf函数的定义域（前域）iff当且仅当ranf函数的值域↑命题的“与非”运算（“与非门”）f:X→Yf是X到Y的函数↓命题的“或非”运算（“或非门”）GCD(x,y)x,y最大公约数□模态词“必然”LCM(x,y)x,y最小公倍数◇模态词“可能”aH(Ha)H关于a的左（右）陪集φ空集Ker(f)同态映射f的核（或称f同态核）∈属于（∉不属于）[1，n]1到n的整数集合P（A）集合A的幂集d(u,v)点u与点v间的距离|A|集合A的点数d(v)点v的度数G=(V,E)点集为V,边集为E的图R^2=R○R[R^n=R^(n-1)○R]关系R的“复合”W(G)图G的连通分支数阿列夫k(G)图G的点连通度א⊆包含△（G)图G的最大点度⊂（或下面加≠）真包含A(G)图G的邻接矩阵∪集合的并运算P(G)图G的可达矩阵∩集合的交运算M(G)图G的关联矩阵-（～）集合的差运算C复数集〡限制N自然数集（包含0在内）[X](右下角R)集合关于关系R的等价类N*正自然数集A/R集合A上关于R的商集P素数集[a]元素a产生的循环群Q有理数集I(i大写)环，理想R实数集Z/(n)模n的同余类集合Z整数集r(R)关系R的自反闭包Set集范畴s(R)关系的对称闭包Top拓扑空间范畴CP命题演绎的定理（CP规则）Ab交换群范畴Grp群范畴Mon单元半群范畴Ring有单位元的（结合）环范畴Rng环范畴CRng交换环范畴R-mod环R的左模范畴mod-R环R的右模范畴Field域范畴Poset偏序集范畴