1、大一上,離散數學重要公式定理匯總,2020/6/17,2,基本的等價公式對合律PP冪等律PPPPPP結合律P(QR)(PQ)RP(QR)(PQ)R交換律PQQPPQQP分配律P(QR)(PQ)(PR)P(QR)(PQ)(PR)吸收律P(PQ)PP(PQ)P德摩根定律(PQ)PQ(PQ)PQ,Formula,2020/6/17,3,同一律PFPPTP零律PTTPFF互補律PPTPPF附加：PQPQPQQPPQ(PQ)(QP)PQ(PQ)(PQ)PQ(PQ)(PQ),Formula,2020/6/17,4,等價公式(前10個)與集合論的公式比較：對合律AAA表示A的絕對補集冪等律AAAAAA結合律

2、A(BC)(AB)C；A(BC)(AB)C交換律ABBAABBA分配律A(BC)(AB)(AC)A(BC)(AB)(AC)吸收律A(AB)AA(AB)A,Formula,2020/6/17,5,德摩根定律(AB)AB(AB)AB同一律AA;AEAE表示全集零律AEEA否定律AAEAA,Formula,2020/6/17,6,Definition,永真(重言)式（Tautology）公式中的命題變量元論怎樣指派，公式對應的真值恒為T。永假（矛盾）式（Contradiction)公式中的命題變量無論怎樣代入，公式對應的真值恒為F?？蓾M足公式（Satisfaction）公式中的命題變量無論怎樣代入，

3、公式對應的真值總有一種情況為T。一般命題公式（Contingency）既不是永真公式也不是永假公式。,2020/6/17,7,3.重要的重言蘊含式(如教材第43頁所示)I1.PQP,I2.PQQI3.PPQI4.QPQI5.PPQI6.QPQI7.(PQ)PI8.(PQ)QI9.P,QPQI10.P(PQ)QI11.P(PQ)QI12.Q(PQ)PI13.(PQ)(QR)PRI14.(PQ)(PR)(QR)RI15.AB(AC)(BC)I16.AB(AC)(BC),Formula,2020/6/17,8,蘊含的性質*若AB且A為重言式，則B必為重言式*若AB且BC，則AC(傳遞性)*若AB且A

4、C，則A(BC)*若AB且CB，則(AC)B證明見書P22,Formula,2020/6/17,9,conjunction,一、全功能真值表,PQ,QP,2020/6/17,10,3.析取范式與合取范式的化法化成限定性公式。公式E16PQPQ公式E21PQ(PQ)(PQ)公式E20PQ(PQ)(QP)公式E16PQ(PQ)(PQ)將否定聯(lián)結詞移到命題變量的前面。A(P1,P2,Pn)A*(P1,P2,Pn)(PQ)PQ、(PQ)PQ用分配律、冪等律等公式進行整理，使之成為所要求的形式。,normalform,2020/6/17,11,主析取范式定義析取范式A1A2.An,其中每個Ai(i=1,

5、2.n)都是小項，稱之為主析取范式。思考：主析取范式與析取范式的區(qū)別是什么？主析取范式的寫法方法：列真值表列出給定公式的真值表。找出真值表中每個“T”對應的真值指派再對應的小項。用“”聯(lián)結上述小項，即可。,normalform,2020/6/17,12,主合取范式定義合取范式A1A2.An,其中每個Ai(i=1,2.n)都是大項，稱之為主合取范式。主合取范式的寫法方法：列真值表列出給定公式的真值表。找出真值表中每個“F”對應的真值指派再對應的大項。用“”聯(lián)結上述大項，即可。,normalform,2020/6/17,13,BriefSummary,第一章小結,知識網絡：,2020/6/17,1

6、4,如果是個不含客體變元x的謂詞公式，且不在x和x的轄域內，可以將放入x和x的轄域內。即得如下公式：1.xA(x)Bx(A(x)B)2.xA(x)Bx(A(x)B)3.xA(x)Bx(A(x)B)4.xA(x)Bx(A(x)B)5.BxA(x)x(BA(x)6.BxA(x)x(BA(x)7.xA(x)Bx(A(x)B)8.xA(x)Bx(A(x)B),量詞轄域的擴充公式,2020/6/17,15,1.x(A(x)B(x)xA(x)xB(x)2.x(A(x)B(x)xA(x)xB(x)3.x(A(x)B(x)xA(x)xB(x)4.xA(x)xB(x)x(A(x)B(x)證明：設論域為a1,a2

7、,.,an，x(A(x)B(x)(A(a1)B(a1)(A(a2)B(a2)(A(an)B(an)(A(a1)A(a2).A(an)(B(a1)B(a2).B(an)xA(x)xB(x),量詞分配公式,2020/6/17,16,其它公式,1.x(A(x)B(x)xA(x)xB(x)2.xA(x)xB(x)x(A(x)B(x),證明1：xA(x)xB(x)xA(x)xB(x)xA(x)xB(x)x(A(x)B(x)x(A(x)B(x),證明2：xA(x)xB(x)xA(x)xB(x)xA(x)xB(x)x(A(x)B(x)x(A(x)B(x),2020/6/17,17,量詞之間有如下公式：1.x

8、yA(x,y)yxA(x,y)2.xyA(x,y)yxA(x,y)3.yxA(x,y)xyA(x,y)4.xyA(x,y)xyA(x,y)5.yxA(x,y)xyA(x,y)6.xyA(x,y)yxA(x,y)7.yxA(x,y)xyA(x,y)8.xyA(x,y)yxA(x,y)注意：下面式子不成立xyA(x,y)yxA(x,y),2020/6/17,18,為了便于記憶，用圖形表示上面八個公式。,2020/6/17,19,第二章小結,集合的性質冪等律對任何集合A，有AA=A。交換律對任何集合A、B，有AB=BA。結合律對任何集合A、B、C，有(AB)C=A(BC)。同一律對任何集合A，有AE

9、=A。零律對任何集合A，有A=。ABAB=A。,交、并的性質冪等律對任何集合A，有AA=A。交換律對任何集合A、B，有AB=BA。結合律對任何集合A、B、C，有(AB)C=A(BC)。同一律對任何集合A，有A=A。零律對任何集合A，有AE=E。分配律對任何集合A、B、C，有A(BC)=(AB)(AC)。A(BC)=(AB)(AC)。,吸收律對任何集合A、B，有A(AB)=AA(AB)=A證明:A(AB)=(AE)(AB)(同一)=A(EB)(分配)=AE=A(零律)(同一)ABAB=B,差集的性質設A、B、C是任意集合，則A-=A-A=A-A=A-BAABA-B=(A-B)-C=(A-C)-(

10、B-C)A-(BC)=(A-B)(A-C)A-(BC)=(A-B)(A-C)A(B-C)=(AB)-(AC)注意：對-是不可分配的，如A(A-B)=A而(AA)-(AB)=,有關絕對補集的性質設A、B、C是任意集合，則E=E(A)=AAA=AA=EA-B=AB(AB)=AB(AB)=ABABBAA=B當且僅當AB=E且AB=,有關對稱差的性質交換律對任何集合A、B，有AB=BA。結合律對任何集合A、B、C，有(AB)C=A(BC)。教材里有證明。同一律對任何集合A，有A=A。對任何集合A，有AA=。對可分配A(BC)=(AB)(AC),一.自反性定義:設R是集合A中的關系，如果對于任意xA都有

11、R(xRx)，則稱R是A中自反關系。即R是A中自反的關系x(xAxRx)例如：在實數集合中,“”是自反關系，因為，對任意實數x，有xx.,關系的性質,從關系有向圖看自反性:每個結點都有環(huán)。從關系矩陣看自反性：主對角線都為1。,二.反自反性定義：設R是集合A中的關系，如果對于任意的xA都有R，則稱R為A中的反自反關系。即R是A中反自反的x(xAR)從關系有向圖看反自反性:每個結點都無環(huán)。從關系矩陣看反自反性：主對角線都為0。如實數的大于關系，父子關系是反自反的。注意：一個不是自反的關系，不一定就是反自反的。,三.對稱性定義:R是集合A中關系,若對任何x,yA,如果有xRy,必有yRx,則稱R為A

12、中的對稱關系。R是A上對稱的xy(xAyAxRy)yRx)從關系有向圖看對稱性:在兩個不同的結點之間，若有邊的話，則有方向相反的兩條邊。從關系矩陣看對稱性：以主對角線為對稱的矩陣。例鄰居關系和朋友關系是對稱關系。,四.反對稱性定義:設R為集合A中關系,若對任何x,yA,如果有xRy,和yRx,就有x=y,則稱R為A中反對稱關系。,由R的關系圖看反對稱性：兩個不同的結點之間最多有一條邊。從關系矩陣看反對稱性：以主對角線為對稱的兩個元素中最多有一個1。另外對稱與反對稱不是完全對立的，有些關系它既是對稱也是反對稱的，如空關系和恒等關系。,五.傳遞性定義:R是A中關系，對任何x,y,zA,如果有xRy

13、,和yRz,就有xRz,則稱R為A中傳遞關系。即R在A上傳遞xyz(xAyAzAxRyyRz)xRz)例實數集中的、，集合、是傳遞的。從關系關系圖和關系矩陣中不易看清是否有傳遞性。必須直接根據傳遞的定義來檢查。檢查時要特別注意使得傳遞定義表達式的前件為F的時候此表達式為T，即是傳遞的。即若R與R有一個是F時(即定義的前件為假)，R是傳遞的。,本節(jié)要求：1.準確掌握這五個性質的定義。2.熟練掌握五個性質的判斷和證明。R是A中自反的x(xAxRx)R是A中反自反的x(xAR)R是A上對稱的xy(xAyAxRy)yRx)R是A上反對稱的xy(xAyAxRyyRx)x=y)xy(xAyAxyxRy)y

14、x)R在A上傳遞xyz(xAyAzAxRyyRz)xRz)注意性質表達式的前件為F時此表達式為T，即R是滿足此性質的。(自反和反自反性除外),若RABSBCTBC則有,證明任取R(ST)b(bBRST)b(bBR(ST)）b(bBRS)(bBRT)b(bBRS)b(bBRT)RSRT(RS)(RT)所以R(ST)=(RS)(RT),R是從A到B的關系，則,2.RC的有向圖：是將R的有向圖的所有邊的方向顛倒一下即可。3.RC的矩陣M=(MR)T即為R矩陣的轉置。如,=,MR,c,三.性質令R、S都是從X到Y的關系，則1.(RC)C=R2.(RS)C=RCSC。3.(RS)C=RCSC。4.(RS

15、)C=RCSC。,5.RSRCSC。,6.(R)C=RC,7.令R是從X到Y的關系，S是Y到Z的關系，則(RS)C=SCRC。(注意RCSC),8.R是A上關系，則R是對稱的，當且僅當RC=RR是反對稱的，當且僅當RRCIA。,四.性質定理5.R是A上關系，則R是自反的，當且僅當r(R)=R.R是對稱的，當且僅當s(R)=R.R是傳遞的，當且僅當t(R)=R.定理6.R是A上關系，則R是自反的，則s(R)和t(R)也自反。R是對稱的，則r(R)和t(R)也對稱。R是傳遞的，則r(R)也傳遞。,定理7：設R1、R2是A上關系，如果R1R2，則r(R1)r(R2)s(R1)s(R2)t(R1)t(

16、R2)證明r(R1)=IAR1IAR2=r(R2)，類似可證。定理8：設R是A上關系，則sr(R)=rs(R)tr(R)=rt(R)st(R)ts(R)證明：sr(R)=r(R)(r(R)c=(RIA)(RIA)c=(RIA)(RcIAc)=RIARcIA=(RRc)IA=s(R)IA=rs(R)的證明用前邊證明的結論：(RIA)k=IARR2.Rk可證，這里從略。,六.函數的類型,一對一,一對一,滿射的,映內的,入射的單射的一對一的,雙射的一一對應的,函數復合的性質,1.定理5-2.1滿足可結合性f:XY,g:YZ,h:ZW是函數,則(hg)f=h(gf),2.定理5-2.2f:XY,g:Y

17、Z是兩個函數,則如果f和g是滿射的，則gf也是滿射的；如果f和g是入射的，則gf也是入射的；如果f和g是雙射的，則gf也是雙射的。,3.定理5-2.3如果gf是滿射的，則g是滿射的；如果gf是入射的，則f是入射的；如果gf是雙射的，則f是入射的和g是滿射的。4.定理5-2.4f:XY是函數,則fIX=f且IYf=f。,性質,1.定理5-3.1設f:XY是雙射的函數，則(f-1)-1=f。2.定理5-3.2設f:XY是雙射的函數，則有f-1f=IX且ff-1=IY。證明：先證明定義域、陪域相等。因為f:XY是雙射的，f-1:YX也是雙射的，所以f-1f:XX;IX:XX可見f-1f與IX具有相同

18、的定義域和陪域。再證它們的對應規(guī)律相同：xX,因f:XY,yY,使得y=f(x),又f可逆，故f-1(y)=x，于是f-1f(x)=f-1(f(x)=f-1(y)=x=IX(x)同理可證ff-1=IY。,3.定理5-3.3令f:XY,g:YX是兩個函數,如果gf=IX且fg=IY,則g=f-1。證明：證f和g都可逆。因為gf=IX，IX是雙射的，由關系復合性質3得，f是入射的和g是滿射的。同理由fg=IY，得g是入射的和f是滿射的。所以f和g都可逆。顯然f-1和g具有相同的定義域和陪域。證明它們的對應規(guī)律相同。任取yY，f-1(y)=f-1IY(y)=f-1(fg)(y)=(f-1f)g(y)=(IXg)(y)=g(y)所以f-1=g,順便說明：f-1=g的兩個條件必須同時滿足，缺一不可。例如,此例只滿足gf=IX,但f與g都非雙射，不可逆。,4.定理5-3.4,令f: