离散数学重点笔记

1、离散数学重点笔记第一章，0命题逻辑素数=质数，合数有因子和或假必真同为真(pTq)A(q<->r),(pAq)Anr,pA(qAnr)等都是合式公式，而若公式A是单个的命题变项，则称A为0层合式npAq)tr,(n(pq)A(rVs)斥甬p)分别为3层和4层公式r,(pr(rtq)等不是合式公式。pAq)Tnr【例】求下列公式的真值表，并求成真赋值和成假赋值。公式(1)的成假赋值为011，其余7个赋值都是成真赋值(1)双重否定律(2)等幂律AA;AV(3)交换律AA,AA;AVVA(4)结合律(AAB)AA(BAC);(5)分配律(AAB)VC(AVC)A(BVC)(6)德摩根律(

2、AVB)AAB;(7)吸收律AV(AAB)A;AA(AVB)(8)零一律AV11；AA00(9)同一律AV0A；AA1A(10)排中律AVA1(11)矛盾律AAA0(12)蕴涵等值式ATVB(13)假言易位AtA(14)等价等值式(AtB)A(BtA)第二章，命题逻辑等值演算A(AVB)V；(AVB)(AAB)V(BVC)AC(AAC)V(BAC)AVB7/16离散数学重点笔记(1,2,-)为简单合取式，则1VA2VV为析取范式(pAnq)V(nqAnr)Vp1AA2AA为合取范式(pVqVr)A(npVnq)Ar(15) 等价否定等值式(16) 归缪式(AtB)A(AtB)A一个析取范式是矛

3、盾式当且仅当它的每个简单合取式都是矛盾式一个合取范式是重言式当且仅当它的每个简单析取式都是重言式|极小项极大项公式成真赋值名称公式成假赋值名称1pAlq00pVq00"ohpAq01眄pVnq01pAnq10ndVq10pAq11ipVnq11主范式【A小真，V大假】A成真小写极小项极大项1盘我真赋值名称舍式1成假赋值名称-1pAiqAit000pV<jVtI000npAn小工001pVqVnr001pAqAnt010血2pVnqVr010npA<iAt011口3pVnqVnt011pAn100npV-iVr100pAi101TLI51pVqVnt101r110mstpV

4、nqVr110pA-qAr111IDynpVnaVnrill【例】(pTq)t(nqp)=n(npVq)V(qVn=(pAnq)VnpVq=(pAnq)V(npAnp)(消去宀)(n内移)(已为析取范式)q)V(npAq)V(npAq)V(pAq)(*)=m2Vm0VmlVmlVm3=m0VmlVm2Vm3(幂等律、排序)(*)由np及q派生的极小项的过程如下:np=npA(nqVq)=(npAnq)V(npAq)q=(npVp)Aq=(npAq)V(pAq)熟练之后，以上过程可不写在演算过程中。该公式中含2个命题变项，它的主析取范式中含了00,01,10,11全为成真赋值。22=4个极小项，

5、故它为重言式,离散数学重点笔记【例】(pfq)Anp(分配律、幕等律)已为析取范式=(npVq)Anp=npV(npAq)=(npAnq)V(npAq)=m0Vml【例】(pAnq)V(npAq)=(pVnp)A(pVq)A(nqVnp)A(nqVq)=(pVq)An(pAq)重言蕴涵式1*g(AVB)附加律2.(AAB)nA化简律IKWft理4.AtB二iA拒耻式5.(AVB)AnBnA析取三段沦&(A-B)A(B-C)n(A-*C)假言三段论7.gR)A(BC)n(AC)等价三段论8.(AB)A(CD>A(AVC)=>(BVD>At-1A-JA-1A)nB构适性二

6、难构這性一难(特硃形式)9.(A-B)A(C-D)A(-1BVnD)n(nAvn门破坏性二难【例】用附加前提证明法证明下面推理。前提：Pf(CfR),SVP,Q结论：SfR证明：(1)SVP前提引入规则(2)S附加前提引入规则(3)P(1)(2)析取三段论规则(4)Pf(CfR)前提引入规则(5)CfR(3)(4)假言推理规则(6)Q前提引入规则(7)R(5)(6)假言推理规则结论：SVR附加前提引入规则(1)置换规则(2)化简规则(2)化简规则前提引入规则(5)置换规则【例】用归缪法证明。前提：PVQPfR,CfS证明(1)(SVR)(2) SAR(3) S(4) R(5) QS(6) QV

7、S离散数学重点笔记(7)Q(3)(6)析取三段论(8)PVQ前提引入规则(9)P(7)(8)析取三段论规则(10)PtR前提引入规则(11)PVr(10)置换规则(12)R(9)(11)析取三段论规则(13)RAR(4)(12)合取引入规则(1)VxF(x,ytz)-*3yG(x,y,z)Vx(F(x,y)-*gyG(x,y,z)解(1)yxF(x,ytz)-*gyG(x,y,z)OVtF(t,y)z)-3yG(x,y,z)(换名规则)o甘tF(t,y,z)3wG(x,w,z)(换名规则)VxF(x,y,忑)fmyG(x,y,z)OVxF(x,t3远)fmyG(x,y,z)(代替规则)

8、1;VxF(x,t,z)日yG(w,y,z)(代替规则)vx(F(x,y)myG(x,y,z)OVxtFtx,t)-3yG(x,y,z)(代替规则)Vx(F(x,y)myG(凡y,z)OVx(F(x,y)3tG(x,t,z)(换名规则)(1) yxtA(x)VB(x)<x>tfxA(x)VvxB(x)同样的,(2) 3xfAx)AB(x)<x>3xA(x)A3xB(x)全称量词”对”v”无分配律。存在量词”对"人"无分配律离散数学重点笔记例乩3设个体域为D=a,b?cFT為下面各公式的量词消去(1) vx(F(x)-*G(x)(2) vx(F(x)V

9、3yGty)gxyyF(xpy)解(1)対用G(x)o(F(a)-G(a)A(F(b)-G(b)A(F(c)-*G(c)(2)vx(F(x)V3yG(y)ogF心a)V3yG(y)(公戎匚3)o(F(a)AF(b)AF(c)V(G(a)VG(b)VG(c)()x(F()AF()AF()(F()AF()AF()V(F()AF()AF()V(F()AF()AF()谓词逻辑的等价公式(1)(2)定理4(1)(2)(3)(4)(5)x(A(x)AB(x)x(A(x)VB(x)下列蕴涵式成立xA(x)VxB(x)xA(x)VxB(x)x(A(x)AB(x)x(A(x)fB(x)x(A(x)fB(x)xA

10、(x)txB(x)x(A(x)VB(x)xA(x)AxB(x)xA(x)txB(x)xA(xxB(x)x(A(xB(x)(1)x(A(x)VB)xA(x)VB(2)x(A(x)AB)xA(x)AB(3)x(A(x)tB)xA(xB(4)x(BA(x)BtxA(x)(5)x(A(x)VB)xA(x)VB(6)x(A(x)AB)xA(x)AB(7)x(A(xB)xA(x)tB(8)x(BA(x)BtxA(x)定理3设A(x)、B(x)是任意包含自由出现个体变元定理1设A(x)是谓词公式，有关量词否定的两个等价公式：(1) xA(x)xA(x)(2) xA(x)xA(x)定理2设A(x)是任意的含自

11、由出现个体变项x的公式，B是不含x出现的公式，则有x的公式，则有:L全称量词消去规则(简记为口规则或口)第或鵠离散数学重点笔记离冃攵数学重点笔记2.全称量词引入规则(简记为l?G规则或10<y)3.存在量词引入规则(简称EG规则或EG)恥)丄存在量词消去规则(简记为EI规则或EI):.A(c)设F(x):x为自然数*G(x);x为整数©:yx(FU)-G<x),存FOO:3xG(x)前结证淫论明【例】1:3xF(x) F(c) 0x(F(x)fG®) F(c)(c) G(c) xG(x)前提引入EI规则前提引入门规则假言推理FG规则【例】1-证明下列等值式(1)

12、-IVmGO"13x(FG)AnGa»oVx(F(計fGd”(3)VJ!(F(x)-Vy(F(y)AH(J.y)-nLgy)OVxtf叽FCx)Ar(y)AECx,y)fiL(z；y)11/16（量词否定等值式）（蕴涵等值式（徳摩根律）(1) -I和g)T(£)cm20(F(x)-*G(x)O3y_lf3Vg<M)<z>3i(F(k)AiG(z)至此回答了第囚童习题课中题龙中0的两种符号化形式是等值的(2) nmxtFGO/XiG(x)O目(F(x)A-)G<x)U>寸心F(x)VQ(i)O/x(F(x)-*G(k)这又证明了第四童习

13、题课题2中（量词否定等值式）德摩根律）（臨涵等值式（4）的两种符号化形式是等值的。(3) /x(F(x)/y(P(y)AH(xsL(y)（辖域扩张等值式）（蕴涵等值式）（德.摩根律）f蕴涵等值式）O丫atW巩斤住)(F(y)AH(ify)-nL(i,y)OHpyCiFSNCn(F(y)AH(x,y)ViL(y)»OVVyCFCi)AF(y)AHCy)VnL(k3y)<VVy(F(i)AF(y)AH(xty)nL(t,y)N设个体域D=U7b,cL帮去下列各公式的量词<1>0TF(F(x)VG(y)(2)xy(F(i)VG(y)<3)y)-3yG(y)【例】&l

14、t;1)(F(a)AF(b)AF(c)V(G(a)VG(b)VG(c)(2) (F(a)VF(b)VF(c)V(C(a)VC(WVC(c)<3>(F(a>y)VF(b,y)VF©y)f(G(a>VG(b)VG(c)前提引入 置换(换名规则) 置换 UIUIUG结论否定的引入<L>置换<2>E1<3>赛换<4>S3前提引入<6>H<7>sa<8>UI<D化简<9><1O>1KS推理<5>化简<11><L2>h取离散

15、数学重点笔记-衽自然推理系统F中构造下面推理的证明<1>前提；3绪论iV(x)-*G(x)(2) 前提：寸俺绪论；yxP(z)-*yiG(x)(3) 前提：/x(F(x)(C(a)AR(x),3zF(z)篙论！3j(F(z)AR(x)(1) 方法一。直接证明、证明： m汕(x)-*ktfxG(x) 3yF(y)-*7xG<H)>VH(F(QrG(X)©F(z)fC(z)VH(F(x)fG(x)方法二。归谬法。<1>1Vz(F(x)G(x)<2>3(F(x)-G(k)31(F(c)-G(cJ)<4>n(nF(c)VG(c>

16、;)<5>F(c)AnC(c)<6>3xF(x)-VxG(x)<7>3zFxG(x)8yz/x(F(z)C(x)O>F(c)-G(c><10>F(c)<U>C(c)<12>nG(c)<13>G(g)2G(g)<13>?J矛盾式由归谨法可知，推理正确。【例】注倉：本题不能用附舸前提证明法。（2）用附力口前提证明法弓由3附加前捱引入卩（y）m前提引入UISfiiB推理UG思考：対何（2）能用附加前提证明迭，而（1）不龍辛（3证明；前提引入®EI目点9（韵八R（G）前提引入®

17、;F(c)-*-(Gta)AR(c)©UIAR(c)假言推理化简F(c)AR(c>合取®3x<F(k)AR(t)®EG注意：在此证明中"要先消去存在量词。（个体域为【例】在一阶逻辑自然推理系统F中构造下面推理的证明（1）所有的人或者是吃素的或者是吃荤的，吃素的常吃豆制品，因而不吃豆制品的人是吃荤的。人的集合）。（2）每个喜欢步行的人都不喜欢骑自行车，每个人或者是喜欢骑自行车或者喜欢乘汽车，有的人不喜欢乘汽车，所以有的人不喜欢步行。（个体域为人的集合）。<1)由于个体域为人类集合P所臥不用引入特性谓词，令卩(X)：焜吃秦肉，G(x)：x是

18、吃荤的.，H(d：*吃豆制品前提：yi(F(x)Vg(x),y结论:Vi(nH(x)G(x)证明；OvHFU)VG(x) F(y)VG(y) iF(y)-*-G(y)©vk<F(x)H(x)®F(y)H(y)1F(y)VH(y)®nH(y)-MF(y)®nH(y)(y)®V)c<-iH(i)G(x)(2)令F(x):工喜欢步行*G(x):箭提：vifCF(x)-*"iC(x)；结论：3xnF(x)证明：©3xnHiH(c)®VfcCi)VH(z)G(c)VH(c) G(亡) #-id F(c)fiG(c

19、)®nF(c)3xnF(x)前提引入 UI 羞换前提引入UI直置换赳换假言三段论®UG£喜欢骑自行车，H(x):X喜欢乘汽车yx(G(i)Vh(i)j3ina(x)前提引入Oei前提引入®UI析取三段论前提引入UI拒取式®EC15/16；主意;要先消去存任量词,否则会犯错误。【例】符号化下面的命题所有的有理数都是实数，所有的无理数也是实数，任何虚数都不是实数，所以任何虚数既不是有理数也不是无理数”，并推证其结论。证明设：P(x):x是有理数。(x)x是无理数。(x)x是实数。R(x)(1)(3)(4)E(6)(7)ET(2)(5)IT(2)(8

20、)IT(9)(10)IS(x):x是虚数。x(Q(x)7R(x),本题符号化为：x(P(x)TR(x),x(S(xR(x)x(S(xP(x)(1) x(S(x)7R(x)P(2) S(y)tR(y)(3) x(P(x)R(x)P(4) P(y)7R(y)(5) R(y)7p(y)T(6) x(Q(x)7R(x)P(7) Q(y)7R(y)(8) R(y)7Q(y)T(9)S(y)7p(y)(10) S(y)7Q(y)(11) (S(y)7P(y)A(S(y)7Q(y)(12)(S(y)VP(y)A(S(y)VQ(y)T(11)E(13) S(y)V(P(y)AQ(y)(14) S(y(P(y)

21、AQ(y)(15) x(S(x)tP(x)AR(x)离散数学重点笔记T(12)ET(13)E(14)第六章，集合代数自然数集合N在离散数学中认为0也是自然数)，整数集合乙有理数集合Q,实数集合R,复数集合C全集U，空集是一切集合的子集(1) 幕等律：AAA=AAUA=A(2) 同一律：AAU=A(3) 零律：AA=AUE=E(4) 结合律：(AAB)AC=AA(BAC)(AUB)UC=AU(BUC)(5) 交换律：AAB=BAAAUB=BUA(6)分配律AA(BUC)=(AAB)U(AAC)AU(BAC)=(AUB)A(AUC)吸收律AU(AAB)=AAA(AUB)=A称为集合B关于A的补集A

22、=A且补集记作(AUB)=A(AAB)=U(1)双重否定律：()=A(2)摩根律：=U=A-(BUC)=(A-B)A(A-C)A-(BAC)=(A-B)U(A-C)(BUC)=BAC(BAC)=BUC(4)矛盾律：AA()=(5)排中律：AU()=U集合A和B的对称差记作，它是一个集合，其元素或属于A，或属于B,但不能既属于A又属于B。=(AUB)-(AAB)(1)(2) A=A(3) AU=A(4) =(5) ()C=A()(6) =()U()例6.9证明等式6,27,即A-B=An-B=证对于任意的x,荒uA囂匡疋芷BoxAFIB例6.10证明(A-B)UB=AUB证(AB)UB=(AnB

23、)uB=(AUB)n(BUB)-(AUB)AE=AUB证明：a-E)-c二(AnEjn'c=Annc；a-o(B-c)=oq七)rr(Errc=(Ari"on("buo=(Ann)uancno=uncnE)U0=mFg第七章，二元关系Ax,y>xAAyBAxa,bxc,d=<a,c>,<a,d>,<b,c>,<b,d>自反性和反自反性离散数学重点笔记定义4.10的。设R是集合A上的二元关系，如果对于每个，都有<x，x>R，则称二元关系R是自反R在A上是自反的x(定义4.11设R是集合A上的二元关系，如

24、果对于每个反的。R在A上是反自反的x(4.4.2对称性和反对称性定义4.12设R是集合A上的二元关系，如果对于每个称二兀关系R是对称的。<x,x>R),都有<x,x>R，则称二元关系R是反自<x,x>R)x,，当<x,y>R,就有<y,x>R,则R在A上是对称的(AA<x,y>R<y,x>R)定义4.13设R是集合A上的二元关系，如果对于每个x,，当<x,y>R和<y,x>R时，必有,则称二元关系R是反对称的。4.4.3传递性定义4.14设R是集合A上的二元关系，如果对于任意x,y,，当

25、<x,y>R,<y,z>R,就有<x,z>R,则称二元关系R在A上是传递的。R在A上是传递的(AAA<x,y>RA<y,z>R<x,z>R)例4.13设a,b,c,R,S,T是A上的二元关系，其中<a,a>,<b,b>,<a,c><a,b>,<b,c>,<c,c><a,b>说明R,S,T是否为A上的传递关系。解根据传递性的定义知，R和T是A上的传递关系，S不是A上的传递关系，因为<a,b>R,<b,c>R,但<

26、a,c>R。如果R是自反的、反对称的和传递的，则称R为A上的偏序关系，记作二。设匚为偏序关系，如果<x,y>_,贝U记作_,读作“小于或等于”定义7,24宅为偏序集，BcA,yGBc(L)若w葢(叢U¥葢)成立，口1称y为B的、孑(2)若vxfxeB立，则称y为B的最大元°3)若x=y)成立，则称、'为B的卜几(4)若亍疋仗氐成立.则称亍为B的定义7.25设d吒为偏序集yEAI(1) 若vz(x立,则称y为B的L4二(2) 若vx(xEB-y<x)成立,则称y为日的1(3) 令C=小为P的上界,贝|称C的最小元为B的址丄二或：|.(4；令D=

27、y|y为B的下界、，则称D的最大元为D的或。#/16离冃攵数学重点笔记2.设A二山2,3打R=<x,y>IX,yeAflx+3y<8),S=<2,3>,<432>J,求下列各式;<1)R的集合表达式R'1,h(3) domR7ranRrfldR;RoS7R3?【例】<5)r(R),s(R),t(R).(L>RKl,IX<1,2X<2,IX<31(2) L>,<2,1>,<1,2<1,3>f%=<L3>,<Z2<爲3>,<3,2>f<3,3>1j(3) doniR二1,2,3,ranRll,2,2,3$(4) RoSKl,3>fRaij<1,2>f<2tl>f<2,2>f<3,l>f<3,3>5(5) r(R)=<l,l>f<L,2>,<2fL>,<2,2>f<3,l>f<3,3>*sCR)=l<lJ1>,<L,2>,<2,L>j<3