离散数学公式

双重否定律A幂等 A A交换 A∨B A∧B结合 (A∨B)∨C (A∧B)∧C分配 A∨(B∧C) A∧(B∨C ┐(A∨B) ┐(A∧B)吸收 A∨(A∧B)A，A∧(A∨B)零 A∨11,A∧0同一 A∨0A，A∧1排中 A∨┐A矛盾 A∧┐A A→B AB A→B等价否定等值式AB归谬 (A→B)∧(A→┐B)A (A∧B (A→B)∧A (A→B)∧┐B (A∨B)∧┐B (A→B)(B→C (AB)∧(BC(A ) (A→B)∧(┐A→B)∧(A∨┐A)B (9)(A→B)∧(C→D)∧(┐B∨┐D)(┐A∨┐C)破坏性二难11设个体域为有限集D={a1,a2,…,an},（1）xA(x)（2）xA(x)设A(x)是任意的含自由出现个体变项x（1）┐xA(x)（2）┐xA(x)设A(x)是任意的含自由出现个体变项x的公式，B中不含x（1）x(A(x)∨B)x(A(x)∧B)x(A(x)→B)x(B→A(x))（2）x(A(x)∨B)x(A(x)∧B)x(A(x)→B)x(B→A(x))设A(x)，B(x)是任意的含自由出现个体变项x（1）x(A(x)∧B(x))（2）x(A(x)∨B(x))xA(x)∨UIUGEGEI

或

2SpongeBob2SpongeBob2A∪B＝{x|x∈A∨x∈B} A∩B＝{x|x∈A∧x∈B}A－B＝{x|x∈A∧xB幂 P(A)＝{x|对称差集绝对补集～A＝{x|xA广义并∪A＝{x| 广义交∩A＝{x|设 334SpongeBob排中 矛盾 吸收 德摩根 A∪B＝BABA∩B＝AA－B＝AB＝ACB＝C与E互换，把与有序对<x,y>具有以下性质（1）当x≠y时，<x,y>≠<y,x>（2）<x,y>＝<u,v>的充分必要条件是x＝u且y＝v。笛卡儿积的符号化表示为A×B＝{<x,y>|x∈A∧y∈B}(1)对任意集合A，根据定义有A×＝,×A＝ (A≠B≠A≠B时) (A≠B≠C≠时) (5)AC∧BDA×B对任意集合A全域关系恒等关系 44小于或等于关系：LA={<x,y>|x,y∈A∧x≤y}AR整除关系：DB={<x,y>|x,y∈B∧x整除y}AZ*，Z*是非零整数集包含关系：R＝{<x,y>|x,y∈A∧xy}，其中A是集合族。设则R的关系矩阵和关系图1100100 1 00000 001 domR＝{x|y(<x,y>∈R值域ranR＝{y|域fldR＝domRran例求R={<1,2>,<1,3>,<2,4>,<4,3>}的定义域、值域和域。domR＝{1,2,4}ranR＝{2,3,4}fldR＝{1,2,3,4}逆R-FG＝{<x,y>|限制像例设 R↑＝ R[]＝ 设FdomF-1＝ranF，ranF-1＝dom设F，G，H(2)(FG)-1＝G-1F-设R为A上的关系，则RIA＝IA设F，G，H(1)(2)5566SpongeBob设F为关系，A,B(1)设R为A上的关系，n为自然数，则R的n（1）（2）Rn+1＝Rn设A为n元集，R是A上的关系，则存在自然数st,Rs=Rt。设R是A上的关系，m,n∈N，则Rm 设R是A上的关系，若存在自然数s,t(s<t)使得Rs=Rt对任何k∈N有对任何k,i∈NRs+kp+i=Rs+i，其中p=t-令S={R0，R1，…，Rt-1}q∈N自反x(x∈A→<x,x>∈R)，x(x∈A→<x,x>R)，对称设R为A上的关系，则（1）R在A上自反当且仅当IA（2）R在A上反自反当且仅当（3）R在A上对称当且仅当R＝R-（4）R在A上反对称当且仅当R∩R-1（5）R在A上传递当且仅当R1R2R1∩R266IAR＝R-R∩R-1主对角线元素10则对M2中1所在位置，M中相应的1每个顶点都有如果两点之间有有边，xj到xk有边，则从xi到xkR1-√√√√√√√√√√√√√×××√√√×R1√××××设R为As(R)＝R∪R-设R是非空集合A上的关系，若R是自反的，则s(R)与t(R)若R是对称的，则r(R)与t(R)若R是传递的，则r(R)7788SpongeBob设R是非空集合Ax∈A，[x]是Ax,y∈A，如果xRy，则[x]＝[y]若x(x∈B→y≤x)成立，则称y为B若x(x∈B→x≤y)成立，则称y为B若x(x∈B∧x≤y→x＝y)y为B若x(x∈B∧y≤x→x＝y)y为B623B无无666无66666B无无无无6无6无66由定义可知，两个函数F和G相等,domF＝domx∈domF＝domG所有从A到BBA，读作“B上A”，符号化表示为BA＝{f|f：A→B}。例：设A＝{1,2,3}，B＝{a,b}BA。BA＝f0,f1,f2,f3,f4,f5,f6,f7}f ff ff ff f若y∈ranfx∈Af(x)＝yf:A→B是单射(injection)88ff:A→B是双射 b2b3 3 )=- 解（1）fx=10。既不是单射也不是满射的。（2）f是单调上升的，是单射的，但不满射。ranf={ln1,ln2（3）ff(1.5)=f(1.2)=1（4）f是满射、单射、双射的，因为它是单调函数并且ranf=R例：(1)给定无向图G＝<V,E>V＝{v1,v2,v3,v4,v5}，D=<V,E>V＝{a,b,c,d}，画出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)d(v1)＝4(注意，环提供2度 (e11v4是悬挂顶点，e7是悬挂边 △+＝4a点达到 δ+＝0(在b点达到△-＝3(b点达到δ-＝1(ac点达到)出度列 入度列99SpongeBobG＝<V,E>nm（1）G是树 （2）G中任意两个顶点之间存在唯一的路径（3）G中无回路且m＝n1 （4）G是连通的且m＝n1（5）GG（6）G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈。T13度顶点，22度顶点，其余顶点全是树叶，试求树叶数，并画出满足要xm＝n1x＝3T3T1、1、1、2、2、3。m条边按权从小到大排序：e1,e2,…,em。e1Te2,…,emej(j≥2)TejTejTG的最小生成树为止。 Tn(n≥2)T为根树—T0树根——0树叶——10内点——10v的层数——v树高——T树叶——8 内点——6 分支点——7 高度——1、1、2、3、4、5中序行遍法：ba(fdg)ce 前序行遍法：ab(c(dfg)后序行遍法：b((fgdecSpongeBob├断定符（公式在L╞满足符（公式在E上有效，公式在E→命题的“条件”运算↔命题的“双条件”运算的A<=>B命题A与B等价关系A=>B命题A与BA*公式A的对偶公式wff\hiff\h↑命题的“与非”运算（“\h与非门”↓命题的“或非”运算（“或非门”□模态词“必然”φ空集∈属于（∉不属于P（A）集合A|A|集合AR^2=R○RR^n=R^(n-1)○R]关系Rא⊆⊂（或下面加≠）真包含∪集合的并运算∩集合的交运算-（～）集合的差运算〡限制[X](右下角R)集合关于关系RA/R集合A上关于R[a]元素a产生的循环群IiZ/(n)模nr(R)关系Rs(R)关系的对称闭包CP命题演绎的定理（CP规则EG存在推广规则（\h存在量词引入规则ES\h存在量词特指规则（\h存在量词消去规则）UG全称推广规则（\h全称量词引入规则）US全称特指规则（\h全称量词消去规则）

R关系r相容关系R○S关系与关系的复合domf函数的\h定义域（前域）ranf函数的值域f:X→Yf是X到YGCD(x,yx,y\h最大公约数LCM(x,yx,y\haH(HaH关于a（右）Ker(f)同态映射f（或称f[1，n]1到nd(u,v)点u与点vd(v)点v的度数G=(V,E)点集为V,边集为EW(G)图G\h连通分支k(G)图G△（G)图GA(G)图G