离散数学公式

1、基本等值式1 双重否定律Ao-I-IA2幕等律3交换律4.结合律5分配律A<=>AVA, A<=>AAAVBoBVA, ABoBA(AVB)VC OAV(BVC)(AAB)AC <=> AA(BAC)AV(BAC) (AVB)A(AVC)(V对A的分配律)AA(BVC) o (AAB)V(AAC)(/对V的分配律)6德摩根律7吸收律 &零律9同一律10.排中律11矛盾律"I (AVB) O - A"i B- (AAB) O * AV-I BAV(AB)A, AA(AVB) <=> AAVl O 1,A0<0AVO

2、OA, AAl OAAV-I AO 1AA-I A<=> O12 蕴涵等值式AfBO 1 AB13.等价尊值式A÷>B O (AfB)A(BfA)14假言易位AfB O 1 Bf-I A4 5等价否定等值式 A÷÷B o 1 A< B46.归谬论(AB)(A- B)O-IA求给定公式范式的步骤（1）消去联结词一、÷÷（若存在）。（2）否定号的消去（利用双重否泄律）或内移（利用徳摩根律）。（3）利用分配律：利用八对7的分配律求析取范式，V对八的分配律求合取范式。推理定律“重言蕴含式(1) A=> (AVB)附加律(2

3、) (AB)nA化简律(AB)A => B假言推理(4) (AfB)AIBnlA拒取式(5) (AVB)A-I B=>A析取三段论(6) (AfB) A (B-C) => (AfC)假言三段论(7) (AB) A (BC) => (AoC)等价三段论构造性二难 构造性二难（特殊形式）(8) (AfB)A(CfD)A(AXZC) =XBVD) (A-B)Ah A-B)A(AV-I A)=>B(9)(AfB)A(CfD)A(-1 BV-I D) =X-I AV-I C)破坏性二难极小项极大项公式I成真赋值名称公式成假赋值名称1 p qO OIrlOPVQO O pq

4、p QO 1叫PV-I qO 1Ml1 O21 PVQ1 O%1pq1 1m3l PV-I q1 1极小项公式成真赋值名称l p q rOOOIDOl p qr0 0 1Irlll pq T0 1 0r2l pqr0 1 1叩3p q T1 0 0n qr1 0 1>5pq r1 1 06pqr1 1 17极大项公式成假赋值名称PVqVr0 0 0MOPV qV r0 0 1MIpV qVr0 1 0M2pV qV r0 1 1M31 PVqVr1 0 0M4"I PVqVn r1 0 1M51 PV-I qVr1 1 0M6l pV qV T1 1 1M7设个体域为有限集D二

5、a1,a2,.,an,则有(1) VXA(X) <> A(a1 )A(a2).A(an)(2) 3xA(x) <> A(a1)VA(a2)V.VA(an)设A(X)是任意的含自由出现个体变项X的公式则(1) I VXA(X) O 3x A(X)(2) 1 3xA(x) O x A(X)设A(X)是任意的含自由出现个体变项X的公式，B中不含X的出现，则(1) VX(A(X)VB) <> VxA(X)VBx(A(x)B) <>xA(x) ABDx(A(X)-B) O 2xA(x)f BDX(BfA(X) O BfXZXA(X)(2) 3x(A(X)V

6、B) O 3xA(x)VB3x(A(X)AB) <>3xA(x)B3x(A(x)-*B) O VXA(X)-*B3x(B-A(x) O BfmXA(X)设A(x), B(X)是任意的含自由出现个体变项X的公式，则(1) VX(A(X)B(x) <=> VXA(X)AVXB(X)(2) 3x(A(X)VB(X) <>3xA(x)V 3xB(x)全称量词对“ V ”无分配律。 存在量词幻”对“人”无分配律。Ul规则。VxA (x)xA (x).A(y).A(c)UG规则。A (y). VXA (x)EG规则。A(C). 3xA (x)El规则。3xA (x).A

7、(c)AUB=xxAVxBAB=xxAxBA-B=xxAxgB 幕集 P(A)=x I xA 对称差集 AB=(A-B)U(BA)A B = (AUB) (ACB)绝对补集A=xx*AArB=0 A(BA-BAUB上B AnB)-C图6. 2广义交 QA=x I VZ(ZWAfxz)C=a,c,d广义并 UA=x I 3z(zAxz)设 A=a,b,c,a,c,d,a,e,fB=a则UA=a,b,c,d,e,fU B=aUC=aUc,dU0=0A=aB=aC=ac,dAA=A (AB)C=A(BC) AB=BA集合恒等式幕等律 AUA=A结合律 (AUB)UC=AU(BUC)交换律 AUB=B

8、UA分配律AU (BC)=(AUB) (AUC)A(BUC)=(AB)U(AC)同一律AU0=AAE=A零律AUE=EA0=0排中律AU A=E矛盾律ACA=0吸收律AU(AB)=AA(AUB)=A德摩根律A-(BUC)=(A-B)A(A-C)A-(BAC)=(A-B)U(A-C)(BUC)=Brl C(BC) =BUC0=EE=0双重否定律(A)=A集合运算性质的一些重要结果ABA, AaBUBAuAUB, BCAUBA-BGAAB=A BAU B=B OAUB OAaB=AOA-B=0AB=BA(AB)eC=A(BeC)A0e=AAA=0AB=AC => B=C对偶(dual)式：一

9、个集合表达式，如果只含有C、U、0、E、=、匸、,那么同时把 门与U互换，把0与E互换，把匸与n互换，得到式子称为原式的对偶式。有序对v,y>具有以下性质：(1)当XHy时，<x,y><y,x>(2) <x,y>=<u,v>的充分必要条件是X=U且y=v。笛卡儿积的符号化表示为AXB=<x,y>xAZyB如果 A=m,B=n,则 IAXBl=mru笛卡儿积的运算性质(1) 对任意集合A，根据立义有A×0=0, 0×A=0(2) 般的说，笛卡儿积运算不满足交换律，即A×BB×A (当 AH0

10、 A B0 A AHB 时)(3) 笛卡儿积运算不满足结合律，即(A×B)×CA×(B×C)(当 A0 A B0 A C0 时)(4) 笛卡儿积运算对并和交运算满足分配律，即A×(BUC)=(A×B)U(A×C)(BUC)× A=(BXA) U (CXA)A×(BC)=(A×B)(A×C)(BC)×A=(B×A)(C×A)(5) ACC A BD>A×BC×D常用的关系对任意集合A,泄义全域关系 EA=<x,y> IX

11、AyA=A×A恒等关系 IA=<x,x>xA空关系 0小于或等于关系：LA=<x,y>x,yAxy.其中A©R”整除关系：DB=<x,y>x,yBx整除y,其中AcZ* , Z*是非零整数集 包含关系：R=<x,y>x,yAxy,其中A是集合族。关系矩阵和关系图设 A=1,2,3,4* R=<1 J>,<1,2>,<2,3>,<2,4>,<4,2>t则R的关系矩阵和关系图分别是定义域 dom R = x I 3y(<x,y>R )值域 ran R=y |3

12、 x(<x,y>R)域 fid R=dom R U ran R例求R=<1,2>,<1,3>,<2,4>,<4,3>的泄义域、值域和域。 解答 dom R=1,2,4 ran R=2,3,4 fid R=1,2,3,4逆 R-1=<x,y><y,x>R右复合 F0G=<x,y> | 3t(<x,t> FA <t,y> G)限制 R t A=<x,y>xRyxA像 RA=ran(R t A)例 设 R=<1,2>, <1,3>> <

13、;2,2>, <2,4>, <3,2>Rt 1=<1,2>, <1,3> Rt 0 =0 Rt 2,3=<2,2>, <2,4>, <3,2> R1=2,3R0 =0R3=2设F是任意的关系，则(1) (F-I)-I=F(2) dom F-I =ran F, ran F-I =dom F设F, G» H是任意的关系，则(1) (FOG)OH = FO(GoH)(2) (FOG)-I=G-I OF-I设R为A上的关系，则ROlA=IAOR=R设F, G, H是任意的关系，则(1) FO(GUH)

14、= FOGUFoH(2) (GUH)OF=GOFUHoF F(GQH)匸产GQFoH (4) (GH)oFcGoFHoF 设F为关系，A,B为集合，则 Ff(AUB) = FfAUFfB(2) FAUB=FAUFB(3) Ft (AnB) = Ft AFt B FFAGBluFfAlQFFBl关系的慕运算设R为A上的关系，n为自然数，则R的n次帚左义为：(1) RO=<x,x> xA=IA(2) Rn+1=RnoR幕运算的性质设A为n元集，R是A上的关系，则存在自然数S和t,使得RS=Rt°设R是A上的关系，m,nN,贝IJ(URrn o Rn = Rm+n(2)(Rm)

15、n = Rmn设R是A上的关系，若存在自然数s,t(s<t)使得Rs=Rt,贝IJ(1) 对任何 kN 有 Rs+k=Rt+k(2) 对任何 k,iN 有 Rs+kp+i=Rs+b 其中 p=t-s 令S=RO, R1, ., Rt-1,则对于任意的qN有RqS自反 VX(XA-<x,x> R),反自反 Vx(xA-*<x,x>eR),对称 VXVy(X,y AA <x,y> R-<y,x> R)称 VXVy(X,yAA<x,y>R<y,x>R-*x=y),传递 VXVyVZ(X,y,zAA<x,y>R&

16、lt;y,z>R-*<x,z>R)关系性质的等价描述设R为A上的关系，则(1) R在A上自反当且仅当IACR(2) R在A上反自反当且仅当RIA=0(3) R在A上对称当且仅当R=R-I(4) R在A上反对称当且仅当RR-1 ClA(5) R在A上传递当且仅当RORCR若R1, R2是自反的和对称的，则R1UR2也是自反的和对称的。(2)若Rl和R2是传递的，则R1R2也是传递的。关系性质的特点自反性反自反性对称性反对称性传递性集合表达式 IACRRIA=0R=R-IRR-1 C IARORCR关系矩阵 主对角线元主对角线元素矩阵是对称矩若rij = 1,且i对M2中1所在

17、素全是1 全是0阵j,则rji=O位置，M中相应的位垃都是1关系图每个顶点都每个顶点都没如果两个顶点如果两点之间如果顶点Xi到有环有环之间有边，一有边，一定是Xj有边，Xj到 定是一对方向一条有向边(无Xk有边，则从 相反的边(无双向边)Xi到Xk也有边单边)关系的性质和运算之间的关系自反性反自反性对称性反对称性传递性Rl-IR1R2R1UR2×XR1-R2×XRl o R2×X×X闭包的构造方法设R为A上的关系，则有(1) 自反闭包r(R) = RURO(2) 对称闭包 S(R) = RUR-I(3) t(R) = RUR2UR3U关系性质与闭包运算之

18、间的联系设R是非空集合A上的关系，(1) 若R是自反的，则S(R)与t(R)也是自反的。(2) 若R是对称的,则r(R)与t(R)也是对称的。(3) 若R是传递的，则r(R)是传递的。等价类的性质设R是非空集合A上的等价关系，则(1) VxA, x是A的非空子集。(2) x,yA,如果 xRy 则x = y°(3) Vx,yA,如果x,ygR,则冈与y不交。(4) Ux xA=Ao偏序集中的特殊元素设A, W为偏序集，BcA, yB0(1)若Vx(xByx)成立，则称y为B的最小元。(2) 若x(xB-xy)成立，则称y为B的最大元。(3) 若VX(XBxy-*x=y)成立，则称y为

19、B的极小元。(4) 若VX(XBAyWx-x=y)成立，则称y为B的极大元B上界B最大最小极大元极小元元元2,3,6,12,24,36无无24, 36 2,36,121261262,3,66无62,3下界6上确界下确界6666无无 无2,3,6,12,24,36无12,24,362,3,6122,3,66,12,24,36 无66,12,24,36,2,3,6,6函数相等由泄义可知，两个函数F和G相等，一泄满足下而两个条件:(1) dom F=dom G(2) Vxdom F=dom G,都有 F(X)=G(X)所有从A到B的函数的集合记作BA,读作忆上A”，符号化表示为BA=办A-B O 例

20、：设 A=1,2,3, B=a,b,求 BAOBA=fOf /1, f2, /3, /4, /5, /6, /7。其中f 0=<1 ,a>,<2,a>,<3,a>f1 =<1 ,a>2,a>,<3,b>/ 2=<1 ,a>,<2,b>,<3,a>f3=<1,a>,<2,b>,<3,b>4=<1,b>,<2,a>,<3,a>/5=<1,b>,<2,a>,<3,b>f 6=<1,b&g

21、t;,<2,b>,<3,a>f 7=<1,b>,<2,b>,<3,b>设(1)若 ran f =B,则称 f:AfB 是满射(SUrjeCtiOn)的。(2) 若Vyran / 都存在唯一的 x4 使得 f(x)=y,则称 /:4- 是单(injection).(3) 若f既是满射又是单射的，则称f:A-B是双(bijection)单射双射函数满射例：判断下面函数是否为单射、满射、双射的，为什么？(1) R-R，f(x)= -x2+2x-1(2) f： Z+-R, f(x)=lnx, Z+为正整数集(3) RZ, /(x)=LXJ(4

22、) f： R_R, f(x)=2x+1。解(1) f在x=1取得极大值6既不是单射也不是满射的。(2) f是单调上升的，是单射的,但不满射。ran f=lnlf ln2f.,(3) f是满射的，但不是单射的，例如f(l.5)=f(l.2)=o(4) f是满射、单射、双射的，因为它是单调函数并且ran =Ro例:(1)给定无向图 G = <V,E>,其中 V=v1,v2,v3,v4,v5, E=(v1, v1), (Vl ,v2), (v2,v3), (v2,v3), (v2,v5), (Vl, v5), (v4, v5).(2)给定有向图 D=<V,E>,其中 V=a,

23、b,c,d,E=<a,a>,<a,b>,<a,b>,<a,d>,<c,d>,<d,c>,<c,b>o 画岀G与D的图形。邻域:NG(Vl) =v2, v5 闭邻域：NG(Vl) =v1, v2, v5 关联IG(VI) =e1, e2, e3d(v1)=4(注意,环提供2度)， =4, =1,Wl是悬挂顶点，刃是悬挂边。度数列为4,4,2,1,3o后继元集：1+D(d) =c 先驱元集:I'-D(d) =, c 邻域：ND(d) =, c闭邻域：ND(d ) =a, G d出度：d+(a)=4,入度:d-(a)=1(环6提供出度1,提供入度1), d(a)=4+1 =5o = 5, § =3, +=4 (在a点达到) +=0(在b点达到)-=3(在b点达到) -=1(在a和C点达到)按字母顺序，度数列：5,3,3,3出度列：4,0,2,1 入度列:1,3,1,2设G=<V,E>是门阶m条边的无向图，则下而各命题是等价的：(1)G是树。(2) G中任意两个顶点之间存在唯