離散數(shù)學(xué)知識(shí)

1.1.31.1.41.1.5定義1.2.1A是合式公式，則A、(A)A、BAB、AB、AB、AB1.6定義1.6.1設(shè)A與C是兩個(gè)命題公式，AC，則稱CA的有效結(jié)論，或稱A可以邏輯推出C，記為A=>C（用等值演算或真值表）?：全稱量詞?一般情況下，如果個(gè)體變?cè)娜≈捣秶蛔鋈魏蜗拗萍礊槿倐€(gè)體域時(shí)，帶“全稱量詞”的謂詞公式形如R(x)x是兔子，T(x)xH(x,y)xy跑得快，L(x,y)xy一樣快，則兔子比烏龜跑得快表示為：?x?y(R(x)∧T(y)→H(x,y))定義2.2.1、非邏輯符號(hào)：個(gè)體常元(如a,b,c)、函數(shù)常元(如表示xH(x))

y2的f(x,y))、謂詞常元(2.2.2、邏輯符號(hào)：個(gè)體變?cè)?、量詞(??)、聯(lián)結(jié)詞(﹁∨∧→?)、逗號(hào)、括號(hào)。定義2.2.3、項(xiàng)的定義：個(gè)體常元、變?cè)捌浜瘮?shù)式的表達(dá)式稱為項(xiàng)(item)。tnA∨BA∧BA→BA?B合式(4)A合式，則?xA、?xA合式(5)有限次使用(2)~(4)得到的式子是合式。定義2.2.6量詞轄域：?xA和?xA中的量詞?x/?x的作用范圍，A就是作用范圍。2.2.7約束變?cè)涸?x和?xAx，稱為約束變?cè)?，這是與量詞相關(guān)的變?cè)?.2.8自由變?cè)褐^詞公式中與任何量詞都無關(guān)的量詞，稱為自由變?cè)?，它的每次出現(xiàn)稱為自由出現(xiàn)。一定義2.2.9閉公式是指不含自由變?cè)闹^詞公式從本例(已省)可知，不同的公式在同一個(gè)解釋下，其真值可能存在，也可能不存在，但是對(duì)于沒有自由變2.2.102.2.112.2.12定義2.2.13

p1,p2pn

A0,A1Ann詞公式，用Ai代替公式

piAA為

A(x)∨﹁A(x)，?xA(x)∨﹁xA(x)p∨p的代換實(shí)例，A(x)∧﹁A(x)，?xA(x)∧?xp∧p定理2.2.1命題邏輯的永真公式之代換實(shí)例是謂詞邏輯的永真公式，命題邏輯的永假公式之代換實(shí)例是謂詞2.3.1A、BAB等值，記為AB。當(dāng)AB時(shí)，根據(jù)定義可知，在任何解釋下，公式A與公式B的真值都相同，故A?B為永真式，故得2.3.2A、BABABAB一、利用代換實(shí)例可證明的等值式(p?﹁﹁p永真，代換實(shí)例xF(x)?﹁﹁xF(x)永真

}，則?xA(x)A(a1)∧A(a2)∧…∧Aan1、﹁?xA(x)?x﹁ 2、﹁?xA(x)?x﹁1、?x(A(x)∧B(x)) 2、?x(A(x)∨B(x))記憶方法：?與∧，一個(gè)尖角朝下、一個(gè)尖角朝上，相反可才分配。21式的對(duì)偶式A(x)x，Bx1、?/?(A(x)∨B) 2、?/?(A(x)∧B)A(x)?BBABCBACDAABA例2.5.1若在各種解釋下結(jié)論B。

A1

...An

B

定義2.5.2

A1

A1

CPRNZQ表示有理數(shù)，C”或“不屬于”二種關(guān)系。3.1.1A，BABABABAABAB定義3.2.1設(shè)A、B為集合，A與BAB、A與BAB、A-B的定義：AB={x|xAxB}，AB={x|xAxB}，A-B={x|xAxB}定義3.2.2設(shè)ABA與BAB={x|(xAxB(AxB)}=AB-AB定義3.2.3設(shè)A、B是兩個(gè)集合，若AB、BA則A=B，即兩個(gè)集合相等。 AA=A、AA=A ABC=A(BC)=(AB)CABC=A(BC)=(AB)C交換 AB=BA、AB=BA A(BC)=(AB)(AC)A(BC)=(AB)(A A?=A、A?= AA=E、AA=吸收律(大吃小 A(BA)=A、A(B德摩 (AB)=AB、(AB)=A雙重否 3.3.1|

|=|A1|+|A2|-|

A23.4.2令<x,y>與<u,v>x=u、y=v，那么<x,y>=<u,v>即二個(gè)序偶相等。定義3.4.3如果<x,y>是序偶，且<<x,y>,z>也是一個(gè)序偶，則稱<x,y,z>為三元組。定義3.5.1令A(yù)B{<x,y>|xA,yB}ABAB則1、A(BCABA2、A(BCABA3、(BC)ABAC4、(BC)ABAC5、ABACBCCAC6、AB,CDACB定義3.5.2

A1,A2,...Annn元組的集合x1,x2,...,xnx1A1,x

An}，為A1,A2,...An的直積或笛卡爾積，記為A1

...An3.6.1R如在直積{1,2,3,4,5,6,7,8}{1,2,3,4,5,6,7,8}1個(gè)元素是第2R={<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<1,7>,<1,8>,<2,2>,<2,4>,<2,6>,<2,8>,3.6.2RR。定義3.7.1若關(guān)系FAA，關(guān)系GAA，稱集合{<x,y>|t使得<x,FGFG3.7.1A={1,2,3}，F(xiàn)={<1,1>,<1,2G={<2,2>,<1,3>,<1,1>}FG<1,3>,<1,1>,<1,2>}，GF={<1,2>,<1,1>}MFi行與MGj列相乘時(shí)，乘法是合取，加法是析取，如MF1的第3列相乘是：(11)(10)(00)，結(jié)果為1定義3.7.2若關(guān)系FAA，稱集合{<y,x>|<x,y>F為F的逆，記為F3.7.2A={1,2,3}，F(xiàn)={<1,2>,<1,3>,<2,1>}，則F1<2,1>,<3,1>,<1,2>}定義3.8.1若xA都有<x,x>RR是自反關(guān)系。(定義3.8.2若xA都有<x,x>R,則R是反自反的。(3.8.4如果所有形如<x,x>RRR為恒等關(guān)系，記為IA。定義3.8.5RAA，如果當(dāng)<x,y>R時(shí)<y,x>R，則稱R為對(duì)稱關(guān)系定義3.8.6RAA，如果當(dāng)<x,y>Rxy時(shí)<y,x>R，則稱R為反對(duì)稱關(guān)系定義3.8.8RAA，若當(dāng)<x,y>R,<y,z>R時(shí)有<x,z>RR為可傳遞關(guān)系RR0R的關(guān)系矩陣都出現(xiàn)，即MR

MRRR0元素出現(xiàn)在(1,1)，(1,3)，(2,2)，(2,4)R陣都沒出現(xiàn)，不滿足MRRMR1自反閉包3.10.1RAA，如果R是自反、對(duì)稱、可傳遞的關(guān)系則稱為等價(jià)關(guān)系定義3.10.2RAA，如果RBABR，則B是一個(gè)AR的商集A/R3.10.3若A0,A1Ak1A的子集，若i

j時(shí)

，并且

則稱A0,A1AkA的一個(gè)劃分定理3.10.1設(shè)RAA，RA0,A1Ak1是利用R得到的k個(gè)不同的等價(jià)類，則A0,A1Ak1A3.10.2設(shè)A0,A1Ak1AR

∪Ak1Ak1R3.11.1RAA，如果R是自反、反對(duì)稱、可傳遞的關(guān)系則稱為偏序關(guān)系。如：RR是偏序關(guān)系。定義3.11.2RAA，R偏序關(guān)系，x與yA中的元素，若序偶<x,y>與<y,x>至少有一個(gè)在R則稱x與y可比定義3.11.3RAA，R偏序關(guān)系，若A中任意二個(gè)元素都可比，則稱A為全序關(guān)系或線序關(guān)系。3.11.4RAA，R偏序關(guān)系，將關(guān)系圖繪制成所有箭頭都朝上，然后去掉所有箭頭、去掉自旋邊、3.11.5yxy蓋住x定義3.11.6RAA，R偏序關(guān)系，將偏序關(guān)系與集合A一塊稱為偏序集，記為<A,R>A上3.11.7在偏序集<A,R>中，BA，yB，若xB都有<x,y>Ry是最大元3.11.8在偏序集<A,R>中，BA，yB，若xB都有<y,x>Ry是最小元定義3.11.9在偏序集<A,R>中，BA，yBxB使得<y,x>R，則稱y是極大元B中不y“大”的元素。即極大元與B中有些元素是否可比不做要求。3.11.10在偏序集<A,R>中，BA，yBxB都有<x,y>Ry是極小元B定義3.11.11在偏序集<A,R>中，BA，yB，若任意xB都有<x,y>RyB的上界。與B中每個(gè)元素都可比，并且都B中的元素大。3.6.1給定集合Aρρ是自反的、對(duì)稱的ρA定義3.6.3給定非空集合ASS1,S2,...,Sn}Si

i=1,2,…,mSi∩

j)，則稱集合SA的3.6.1AS1,S2,...,Sn

Sn3.7.1RARR稱為等價(jià)關(guān)系。(定義3.7.2設(shè)給定非空集合A，若有集合SS1,S2,...,Sn}，其中Si

A且Si(i=1,2,…,m)Si∩

mmj)

AS為A(A

擬序關(guān)系(反自反的，傳