離散數(shù)學知識

1.1.31.1.41.1.5定義1.2.1A是合式公式，則A、(A)A、BAB、AB、AB、AB1.6定義1.6.1設A與C是兩個命題公式，AC，則稱CA的有效結論，或稱A可以邏輯推出C，記為A=>C（用等值演算或真值表）?：全稱量詞?一般情況下，如果個體變元的取值范圍不做任何限制即為全總個體域時，帶“全稱量詞”的謂詞公式形如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、非邏輯符號：個體常元(如a,b,c)、函數(shù)常元(如表示xH(x))

y2的f(x,y))、謂詞常元(2.2.2、邏輯符號：個體變元、量詞(??)、聯(lián)結詞(﹁∨∧→?)、逗號、括號。定義2.2.3、項的定義：個體常元、變元及其函數(shù)式的表達式稱為項(item)。tnA∨BA∧BA→BA?B合式(4)A合式，則?xA、?xA合式(5)有限次使用(2)~(4)得到的式子是合式。定義2.2.6量詞轄域：?xA和?xA中的量詞?x/?x的作用范圍，A就是作用范圍。2.2.7約束變元：在?x和?xAx，稱為約束變元，這是與量詞相關的變元，2.2.8自由變元：謂詞公式中與任何量詞都無關的量詞，稱為自由變元，它的每次出現(xiàn)稱為自由出現(xiàn)。一定義2.2.9閉公式是指不含自由變元的謂詞公式從本例(已省)可知，不同的公式在同一個解釋下，其真值可能存在，也可能不存在，但是對于沒有自由變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的代換實例，A(x)∧﹁A(x)，?xA(x)∧?xp∧p定理2.2.1命題邏輯的永真公式之代換實例是謂詞邏輯的永真公式，命題邏輯的永假公式之代換實例是謂詞2.3.1A、BAB等值，記為AB。當AB時，根據(jù)定義可知，在任何解釋下，公式A與公式B的真值都相同，故A?B為永真式，故得2.3.2A、BABABAB一、利用代換實例可證明的等值式(p?﹁﹁p永真，代換實例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))記憶方法：?與∧，一個尖角朝下、一個尖角朝上，相反可才分配。21式的對偶式A(x)x，Bx1、?/?(A(x)∨B) 2、?/?(A(x)∧B)A(x)?BBABCBACDAABA例2.5.1若在各種解釋下結論B。

A1

...An

B

定義2.5.2

A1

A1

CPRNZQ表示有理數(shù)，C”或“不屬于”二種關系。3.1.1A，BABABABAABAB定義3.2.1設A、B為集合，A與BAB、A與BAB、A-B的定義：AB={x|xAxB}，AB={x|xAxB}，A-B={x|xAxB}定義3.2.2設ABA與BAB={x|(xAxB(AxB)}=AB-AB定義3.2.3設A、B是兩個集合，若AB、BA則A=B，即兩個集合相等。 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>即二個序偶相等。定義3.4.3如果<x,y>是序偶，且<<x,y>,z>也是一個序偶，則稱<x,y,z>為三元組。定義3.5.1令AB{<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個元素是第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若關系FAA，關系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列相乘時，乘法是合取，加法是析取，如MF1的第3列相乘是：(11)(10)(00)，結果為1定義3.7.2若關系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是自反關系。(定義3.8.2若xA都有<x,x>R,則R是反自反的。(3.8.4如果所有形如<x,x>RRR為恒等關系，記為IA。定義3.8.5RAA，如果當<x,y>R時<y,x>R，則稱R為對稱關系定義3.8.6RAA，如果當<x,y>Rxy時<y,x>R，則稱R為反對稱關系定義3.8.8RAA，若當<x,y>R,<y,z>R時有<x,z>RR為可傳遞關系RR0R的關系矩陣都出現(xiàn)，即MR

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

j時

，并且

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

∪Ak1Ak1R3.11.1RAA，如果R是自反、反對稱、可傳遞的關系則稱為偏序關系。如：RR是偏序關系。定義3.11.2RAA，R偏序關系，x與yA中的元素，若序偶<x,y>與<y,x>至少有一個在R則稱x與y可比定義3.11.3RAA，R偏序關系，若A中任意二個元素都可比，則稱A為全序關系或線序關系。3.11.4RAA，R偏序關系，將關系圖繪制成所有箭頭都朝上，然后去掉所有箭頭、去掉自旋邊、3.11.5yxy蓋住x定義3.11.6RAA，R偏序關系，將偏序關系與集合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中每個元素都可比，并且都B中的元素大。3.6.1給定集合Aρρ是自反的、對稱的ρA定義3.6.3給定非空集合ASS1,S2,...,Sn}Si

i=1,2,…,mSi∩

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

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

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

mmj)

AS為A(A

擬序關系(反自反的，傳