离散数学重点笔记

1、第一章，0命题逻辑素数=质数，合数有因子和或假必真同为真(pfq)A(qr),(pAq)Ar,pA(qAr)等都是合式公式，而pqfr,(P-(r-q)等不是合式若公式A是单个的命题变项，则称A为0层合式(-1pAq)-r,(prq)A(rVs)I.p)分别为3层和4层公式【例】求下列公式的真值表，并求成真赋值和成假赋值。(pAq)一nr公式(1)的成假赋值为011,其余7个赋值都是成真赋值命题逻辑等值演算双重五定律AA等募律AAAA;AVAA(3)交换律AABBAA;AVBBVA(4)结合律(AAB)ACAA(BAC);(AVB)VCAV(BVC)分配律(AAB)VC(AVC)A(BVC;(

2、AVB)AC(AAC)V(BAC)德摩根律(AVB)AAB;(AAB)AVB吸收律AV(AAB)A;AA(AVB)A零一律AV11;AA00同一律AV0A;AA1A(10)排中律AVA1(11)矛盾律AAA0(12)蕴涵等值式AfBAVB(13)假言易位AfBBfA(14)等价等值式AB(AfB)A(B-A)(15)等价否定等值式ABABBA(16)归缪式(A-B)A(A-B)AAi（i=1,2，,s）为简单合取式，则A=AiVA2VVA为析取范式A=AiAA2AAAs为合取范式（pVqVr）八（pVq）Ar一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式一个合取范式是重言式当且仅当它

3、的每个简单析取式都是重言式主范式|【A小真，V大假】极小项极天项公式1 pAl q1 pAq pAl Q pAq成真赋值W而式吗m3pVq pVn q i dVq 1 pV-| q成假赋值00 11 0名称A成真小写极小项公式型真赋值名称1 pAn qAn T0 0 0叼1 pAi q/V0 0 1叫n pAqAn r0 10吸1 pAqAtQ 1 1叫pAh -iAn r10 0p/Vi q八工1 0 1吗p/Xq/Vl r110mspAAt 一 一 一1 1 1叫极大项公式名称pVqVr0 0 0pVqVn r0 0 1即pV-1 iVr0 1 0JpVn qVi t0 1 1叼-I pV

4、Vr10 01 pViVn t1 0 1眄n pVn1 1 0n pVi B4. 1比E】AnBn-iA5. (AVB)AnB=A6. A(B7)=(A-*C)7. (AOB)A(BoC)(AC)S.(A-E)A(CD)A(AVC)=(BVD)(A-B)A(nA-B)AAVnA)nB9.(A-B)A(C-D)A(-1BV-iD)化蔺律暇言推理拒取式折取三段论假言三段论等价三段论构造性二鹿为渣性一难(特殊形式)破坏性一难【例】用归缪法证明。前提：PV Q, P-R, QfS证明(1)(SV R)SA R(3) S(4) R(5) QfS(6) QV S Q(8) PV Q(9) P(10) Pf

5、 R(11) PVR结论：SV R附加前提引入规则(1)置换规则(2)化简规则(2)化简规则前提引入规则(5)置换规则(3) (6)析取三段论前提引入规则(7) (8)析取三段论规则前提引入规则(10)置换规则n(AV-C)例用附加前提证明法证明下面推理前提：P-(Q-R),SVP,Q结论：SR证明：(1)SVP前提引入规则(2)S附加前提引入规则(3)P(1)(2)析取三段论规则(4)P(Q-R)前提引入规则(5)QfR(3)(4)假言推理规则(6)Q前提引入规则R(5)(6)假言推理规则(13) RA R(12) RVxF (x O X/xF (x, O VXF (x,(9)(11)析取三

6、段论规则(4) (12)合取引入规则(1) VxF(x,y,z)-myG(x,y,z)(2) vx(F(x,y)fmyG(x,y,z)解(1)y,z)fmyG(x,y,z)OVtFft,y,w)fm#G(x,nz)(换名规则)OVtF(t,y,z)qwG(x,w,z)(换名规则)2)y,z)(代替规则)V,z)(代替规则)(2)/k(F(x,y)/myG(x,y,z)OVX(F(x,t)-myG(x,y,z)(代替规则)Vx(F(k,y)3yG(x,v,z)oyx(F(x,y)-3tG(x,t,z)(换名规则)(1)Vx(A(x)VB(x)vxA(x)VVxB(x)八Ea)8AG)八mxB(x

7、)全称量词“对”,无分配律。同样的，存在量词对A无分配律例5.3设个体域为d=g,btu,蒋下面各公式的量词消去,(1) vx(F(支)-G3)(2)tfx(F(x)VayG(y)(3)3xv.yF(xty)解xfy,(F(x)fGG)o(F(a)f)A(F(b)-*G(b)A(F(c)-*G(c)(2) vx(F(x)V3yG(y)OVa)V3yG(y)(公式5一3)o(F(a)AF(b)AF(c)V(G(a)VGVG(c)由邱(x,y)x(F(x,a)AF(x,b)AF(x,c)(F(a,a)AF(a,b)AF(a,c)V(F(b,a)AF(b,b)AF(b,c)V(F(c,a)FF(c,

8、b)AF(c,c)谓词逻辑的等价公式定理1设A(x)是谓词公式，有关量词否定的两个等价公式：(1)xA(x)xA(x)(2)xA(x)xA(x)定理2设A(x)是任意的含自由出现个体变项x的公式，B是不含x出现的公式，则有(1)x(A(x)VB)x(A(x)AB)(3) x(A(x)-B)(4) x(B-A(x)(5) x(A(x)VB)(6) x(A(x)AB)x(A(x)-B)(8)x(B-A(x)xA(x)VBxA(x)ABxA(x)-BB-xA(x)xA(x)VBxA(x)ABxA(x)-BB-xA(x)定理3设A(x)、B(x)是任意包含自由出现个体变元x的公式，则有:(1) x(A

9、(x)AB(x)(2) x(A(x)VB(x)定理4下列蕴涵式成立(1) xA(x)VxB(x)(2) x(A(x)AB(x)(3) x(A(x)-B(x)(4) x(A(x)-B(x)(5) xA(x)-xB(x)xA(x)AxB(x)xA(x)VxB(x)x(A(x)VB(x)xA(x)AxB(x)xA(x)-xB(x)xA(x)-xB(x)x(A(x)告B(x)L全称量词消去规则(简记为UI规则或2.全称量词引入规则(简记为匚G规则或:am3,存在量词引入规则(简称EG规则或EG业)4.存在量词消去规则简记为EI规则或EI)【例】【例】设F(x)飞为自然数.G(x):x为整数.提论明前结

10、证；yx(F(X)G(x),SxF(x)：3xG(x)Z!xF(x)Fyx(F8)fG(工)F一G G(c) 3xGx)前提引入EI规则前提引入11规则假言推理EG规则1-证明下列等值式(1)1y0三CF(上)八-ICS)(2)13x(F(x)AnG(x)qykCfCiJ-gCx)(3/x5(K)f/F(F(y)All(再y)f1l(i,y)O，-Vfy(F()AF5/HfilCaH)(l)1Vx(F(x)-,hG(x)三hi(F(x)-G(x)C量词否定等值式)03tnFWVGW)(蕴涵等值式)OmMFGOAiG(k)(德孽根律至此,回答了第四童习题课中题2申(3)的两种符号比形式是等值的。

11、(2) 13k(F(k)AiGG0)U(F(i)AnG(x)OV式iF(i)VG(x)Oyx(F(x)-*G(x)这又证明了第四童打题课题2中(量词否定等值式)(德.摩根律)(蕴涵等值式)(4)的两种符号化形式是等值的。(3) y/y(FCy)AH(x，Wf1L(x,y)(辖域扩张等值式)(董涵等值式)(德.摩根律)蕴涵等值式)OV(F(y)AH(4y)fiL(i,y)oVVytnI(x)v(n(F(y)AhCz,y)VnL(x,y)OVxVy(n(FnL(&G)2.设个体域D=国旭c,消去下列各公式的量词(1) yx3y(F(i)VG(y)(2) 33=2y(G(a)VG(b)VG(c)(在

12、自然推理系统F中构造下面推理的证明1前提：3xF(x)-*-VxG(x)结论tV(x)-*G(I)2)前提：.工结论：yxFCzJyxC(z)(3)前提：1(?(i)-*(G(a)AR(x),三xFQ)结论：3x(F(k)AR(x)1)方法一。直接证明。证明：三/(x)fVxG(x)myFfYxC(x)/第VX(F(y)fG(k)F(s)fGCz)方法二。归修法。1yX(F(z)-G(x)3x_lF(x)-*G(x)1(FQ)fC(c)n(_iF(c)VG(c)F(c)AnG(c)xF(x)-RlVxGCx)3zF(r)-*VxG(i) 0/2/x(F(z)-G(X)F(c)fG(OF(c)G

13、MnC(c) 13G(g)AiGS)前提引入翦投换名飘贝11)置换UIUIUG结论否定的引入EI置换4置换 前提引入gUI化简9X10)假言推理5化简。1。2合取为矛盾式，由归语法可知，推理正确.【例】注意:本题不能用附加前提证明法。(2)用附加前提证明法证明，附加前提引入UI 前提引入U1假言推理UCW工月Q)FCy)yK(Fcto)FCy)-G(y)CCy)/hG(k)思考：为何2)能用附加前提证明法，而(1)不能？(3)证明：三冥曙口前提引入K(c)EHVKFG)f(G(a)ARq)前提引入UI假言推理化简合取ECF(c)-(G(ti)AR(cGCa)AR(c)RCc)F(g)AR(c)

14、3x(F(k)AR(z)注意：在此证明中？要先消去存在量词。【例】在一阶逻辑自然推理系统F中构造下面推理的证明(1)所有的人或者是吃素的或者是吃荤的,荤的。(个体域为人的集合)。(2)每个喜欢步行的人都不喜欢骑自行车,有的人不喜欢乘汽车，所以有的人不喜欢步行。吃素的常吃豆制品，因而不吃豆制品的人是吃每个人或者是喜欢骑自行车或者喜欢乘汽车,(个体域为人的集合)。1)由于个体域为人类集合？所以不用引入特性谓词，令F(x)；x是吃重机G(z)：算是吃荤的，日(拼又吃豆制品.前提；yx(F-x)VG(i),V晨F(x)fH(x；)证明；Vx(F(x)VG(x)FW)VG(y)1 F(y)fC(y) y

15、 x(FGc)f H(*) F(y)f H(y)n F(y) Vfl(y)-iF(y) V x (i HG)fG(x)(2)令FG)：,喜欢步行, G(x)： 笛提：y s(F(x)-*-i C(x)； 结论;3 X-| F(x)证明；0 3 KI H(x) H(c) W 翼(gGWhQDG(c)VH(c)C(c) V 晨FG)f i G(x)F(c) + i C(c)1 F(c) 3 xn F (x)注意，要先消去存在量词，前提引入IH雷换前提引入UI置损贸换国假言三段论UGK喜欢骑自行车，HO)： M喜欢乘汽车Y x(G(x) VH(x) j 3 xi H (z)前提引入酊 前提引入 IH

16、析取三段论 前提引入 UI拒取式 EG否则会犯错误。【例】符号化下面的命题所有的有理数都是实数，所有的无理数也是实数，任何虚数都不是实数，所以任何虚数既不是有理数也不是无理数”，并推证其结论。证明设：P (x) : x是有理数。Q (x) : x是无理数。R (x) : x是实数。S (x) : x是虚数。本题符号化为：x (P (x) - R (x) ) , x (Q (x) - R (x),x (S (x) -R (x) ) x (S (x) -P (x)(1) x (S (x) - R (x) S (y) - R (y)(3) x (P (x) - R (x)(4) P (y) - R

17、(y)R (y) - P (y)(6) x (Q (x) - R (x) Q (y) - R (y)R (y) - Q (y)(9) S (y) -P (y)(10) S (y) - Q (y)(11) (S (y) -P (y) ) A ( S (y)-Q(y)R (x)PUS (1)PUS (3)T (4) EPUS (6)TET (2) ( 5) IT (2) (8) IT (9) ( 10) I(12) (S (y) VP (y) ) A (S (y) VQ (y) ) T (11) ET (12) E(13)S(y)V(P(y)(14) S(y)-(P(y)AQ(y)T(13)E(1

18、5) x(S(x)-P(x)AR(x)UG(14)第六章，集合代数自然数集合N(在离散数学中认为0也是自然数)，整数集合Z,有理数集合Q,实数集合R,复数集合C全集U,空集是一切集合的子集(1)募等律：AAA=AAUA=A(2)同一律：AHU=A(3)零律：AH=AUE=E(4)结合律：(AAB)nrAn(BAC)(AUB)UC=AU(BUC)(6) 分配律(5)交换律：AnB=BnAAUB=BUAAn(BUC)=(APB)U(Anc)AU(BAC)=(AUB)n(AUC)吸收律AU(APB)=AAn(AUB)=A同一律AU=AAnE=AA-B称为集合B关于A的补集A-B=x|xA且xB补集t

19、己作A(AUB)=AHB(ACB)=AUB(1)双重否定律：(A)=A摩根律：=UU=A-(BUC)=(A-B)n(A-C)A-(BAC(A-B)U(A-C)(BUC)=BAC(BAC尸BUC(4)矛盾律：An(A)=排中律：AU(A)=U集合A和B的对称差记作AB,它是一个集合，其元素或属于A,或属于B,但不能既属于A又属于BoAB=(AUB)-(AAB)(1)AA=A=A(3) AU=A(4) AB=BA(AB)C=A(BC)(6) AB=(A-B)U(B-A)例69证明等式6,27,即AB=ACBd证对于任意的k.BoxWA八匡B4八k三EO,三A.1B例6.10证明(AB)UB=AUB

20、证(AB)UB=(AH-B)UB=(AUB)n(-BUB)=(AUB)nE=AUB证明:a-E)-c=an)rrc=s“Enp；(a-c)-(b-c)=rrc)n，(RCc)=&nncue)二ancnuancnc)=ancnu0=Arrerre.,二元关系AXB=x6AAy6BAxB=a,bxc,d=,自反性和反自反性定义设R是集合A上的二元关系，如果对于每个xA,都有R,则称二元关系R是自反的。R在A上是自反的x(xAR)定义设R是集合A上的二元关系，如果对于每个xA,都有R,则称二元关系R是反自反的。R在A上是反自反的x(xAR)4.4.2 对称性和反对称性定义设R是集合A上的二元关系，如

21、果对于每个x,yA,当R,就有R,则称二元关系R是对称的。R在A上是对称的xy(xAAyAARR)定义设R是集合A上的二元关系，如果对于每个x,yA,当R和R时，必有x=y,则称二元关系R是反对称的。4.4.3 传递性定义设R是集合A上的二元关系，如果对于任意x,y,zA,当R,R,就有R,则称二元关系R在A上是传递的。R在A上是传递的xyz(xAAyAAzAARARR)例设人=但，b,c,R,S,T是A上的二元关系，其中R=,S=,T=说明R,S,T是否为A上的传递关系。解根据传递性的定义知，R和T是A上的传递关系，S不是A上的传递关系，因为R,R,彳！R。如果R是自反的、反对称的和传递的，则称R为A上的偏序关系，记作吗。设H取偏序关系，如果6口|则记作xQy,读作小于或等于定义。24设为偏序集，yeBc(1；若耳K(城三B成立，则称为的七卜兀二2)若(工EBf.y)成立t则称为B的最大元.若寸x=y)成立，则称y为B的极1.(4)若尸元(冗ebAymkx招)成立，则称y为B的极大元.定义工25设6为偏序集，BcA,yEA；(1)若卡工Q三Bf其成立，则称y为B的界匚(2)若(工ERfy成立，则称y为B的卜种匚(3)C=/为3的上界,则称C的最小元为B的最小上界或上确界:令口=口V为B的下界】，贝!)称D的最大元为