離散數(shù)學(xué)定義(必須背)

1、命題邏輯§ (論域)定義：論域是一個數(shù)學(xué)系統(tǒng)，記為D。它由三部分組成： (1)一個非空對象集合S，每個對象也稱為個體； (2) 一個關(guān)于D的函數(shù)集合F； (3)一個關(guān)于D的關(guān)系集合R。§ （邏輯連接詞）定義 設(shè)n>0,稱為0,1n到0,1的函數(shù)為n元函數(shù)，真值函數(shù)也稱為聯(lián)結(jié)詞。 若n =0，則稱為0元函數(shù)。§ （命題合式公式）定義： (1).常元0和1是合式公式； (2).命題變元是合式公式； (3).若Q,R是合式公式，則(ØQ)、(QÙR) 、(QÚR) 、(Q®R) 、(Q«R) 、(QÅR)

2、是合式公式； (4).只有有限次應(yīng)用(1)(3)構(gòu)成的公式是合式公式。§ （生成公式）定義1.5 設(shè)S是聯(lián)結(jié)詞的集合。由S生成的公式定義如下： 若c是S中的0元聯(lián)結(jié)詞，則c是由S生成的公式。 原子公式是由S生成的公式。 若n1，F(xiàn)是S中的n元聯(lián)結(jié)詞，A1,An是由S生成的公式，則FA1An是由S生成的公式。§ （復(fù)雜度）公式A的復(fù)雜度表示為FC(A) 常元復(fù)雜度為0。 命題變元復(fù)雜度為0，如果P是命題變元，則FC (P)=0。 如果公式A=ØB，則FC (A)=FC(B)+1。 如果公式A=B1 Ù B2，或 A=B1 Ú B2，或 A=B1&

3、#174;B2，或 A=B1« B2，或 A=B1 Å B2，或 則FC (A)=maxFC(B1), FC(B2)+1。§ 命題合式公式語義 論域：研究對象的集合。 解釋：用論域的對象對應(yīng)變元。 結(jié)構(gòu)：論域和解釋稱為結(jié)構(gòu)。 語義：符號指稱的對象。公式所指稱對象。合式公式的語義是其對應(yīng)的邏輯真值。§ （合式公式語義）設(shè)S是聯(lián)結(jié)詞的集合是Ø，Ù，Ú，Å ，®，«。由S生成的合式公式Q在真值賦值v下的真值指派v(Q)定義如下： v(0)=0, v(1)=1。 若Q是命題變元p，則v(A)= pv。

4、若Q1,Q2是合式公式§ 若Q= Ø Q1，則v(Q)= Ø v(Q1)§ 若Q=Q1 Ù Q2，則v(Q)=v(Q1)Ù v(Q2)§ 若Q=Q1Q2，則v(Q)=v(Q1)v(Q2)§ 若Q=Q1® Q2，則v(Q)=v(Q1)® v(Q2)§ 若Q=Q1 « Q2，則v(Q)=v(Q1)« v(Q2)§ 若Q=Q1Å Q2，則v(Q)=v(Q1)Å v(Q2)§ （真值賦值）由S生成的公式Q在真值賦值v下的真值v(Q)定

5、義如下： 若Q是S中的0元聯(lián)結(jié)詞c，則v(Q)=c。 若Q是命題變元p，則v(Q)= pv。 若Q是FQ1,Qn，其中n1， F是S中的n元聯(lián)結(jié)詞， Qi是公式，則v(Q)=v(FQ1Qn)=Fv(Q1)v(Qn)。§ （可滿足與有效）定義1.7 設(shè)Q是公式。 如果真值賦值v使得v(Q)=1，則稱v滿足Q。 如果每個真值賦值都滿足Q，則稱Q為有效式，或稱為永真式，也稱為重言式。 如果每個真值賦值都不滿足Q，則稱Q為永假式，也稱為矛盾式，不可滿足式。 如果至少有一個真值賦值滿足Q，則稱Q為可滿足式。§ 定理1.5（對偶定理） 設(shè)A,B是由0,1,Ø,生成的公式，A*

6、與A互為對偶式，B*與B互為對偶式。如果A Û B，則A* Û B*。§ （完全集）定義： 定義1.12設(shè)F是n元聯(lián)結(jié)詞，p1,p2,pn是不同的命題變元。如果公式A中不出現(xiàn)除p1,p2,pn之外的命題變元，并且AÛFp1,p2,pn，則稱A定義F。 設(shè)S是聯(lián)結(jié)詞集合。如果每個n(n>0)元的聯(lián)結(jié)詞都可由S定義，則稱S為完全集。 如果完全集S1中的每個聯(lián)結(jié)詞都可由聯(lián)結(jié)詞集合S2定義，則S2也是完全集。 如果從完全集S中去掉任何一個聯(lián)結(jié)詞就成為不完全的了，就稱S為極小完全集。§ (范式)定義： 原子公式和原子公式的否定統(tǒng)稱為文字。如果一個文

7、字恰為另一個文字的否定，則稱它們?yōu)橄喾次淖帧?設(shè)n是正整數(shù)，A1,An都是文字，稱A1An為簡單析取式，稱A1 An為簡單合取式。 定義 設(shè)n是正整數(shù)。若B1,Bn都是簡單合取式，則稱B1Bn為析取范式。若B1,Bn都是簡單析取式，則稱B1 Bn為合取范式。§ （邏輯推論）定義： 若真值賦值v滿足公式集合中的每個公式，則稱v滿足。若有真值賦值滿足，則稱是可滿足的，否則稱是不可滿足的。 設(shè)是公式的集合，A是公式。如果每個滿足的真值賦值都滿足A，則稱A是的邏輯推論， 記為|=A。若|=A不成立，記為|A。謂詞邏輯§ （論域）定義：論域是一個數(shù)學(xué)系統(tǒng)，記為D。它由三部分組成： (

8、1)一個非空對象集合D； (2) 一個關(guān)于D的函數(shù)集合,也稱運(yùn)算； (3)一個關(guān)于D的關(guān)系集合。§ （一階謂詞邏輯語言）簡稱一階邏輯語言 邏輯符號：包括變元、聯(lián)接詞、量詞； 非邏輯符號：包括常元、函詞、謂詞； 僅有個體變元； 按形成規(guī)則構(gòu)成的合式公式集合 （字符集）定義：§ 邏輯符號，包括變元、聯(lián)接詞、量詞、逗號以及括號等，表示如下：§ 變元：x1, x2, § 聯(lián)接詞：Ù,Ú,Ø,®,«,Å；§ 量 詞：", $；§ 逗 號：, ;§ 括 號：(, )&

9、#167; 非邏輯符號，包括常元、函詞、謂詞等，表示如下：§ 常 元：c1, c2 , § 函 詞：f11, f21,.；f12, f22,.；§ 謂 詞：P11,P 21,.； P 12, P 22,.。§ （項）定義： (1).個體常元是項； (2).個體變元是項； (3).若是t1,tn項，f in是n元函詞，則是f i (t1,tn)項。§ （合式公式）定義：合式公式是按如下規(guī)則構(gòu)成的有窮長符號串。 (1).若是t1,tn項，Qin是n元謂詞，則Qin(t1,tn)是合式公式。 (2).若Q是合式公式，則(ØQ)是合式公式；

10、(3).若Q和R是合式公式，則(QÙR)、(QÚR)、(Q®R) 、(Q«R)及(QÅR)是合式公式； (4).若Q是合式公式，x是變元，則("xQ)及($xQ)是合式公式。 (5).只有有限次應(yīng)用(1)(4)構(gòu)成的公式是合式公式。§ （約束變元）定義： 若("xQ)(或$xQ)是公式，則稱變元x在公式("xQ) (或$xQ)中為約束出現(xiàn)，稱x是約束變元，并稱 x出現(xiàn)的轄域為Q。§ （自由變元）定義： 如果變元x在公式Q中的出現(xiàn)不是約束出現(xiàn)，則稱x在Q中為自由出現(xiàn)。在公式Q中有自由出現(xiàn)的變元稱為

11、Q的自由變元，將Q中自由變元的集合記為Var(Q)。§ 定義：不出現(xiàn)變元的項稱為基項。§ 定義：沒有自由變元的公式稱為語句。§ 解釋（定義）：設(shè)D是論域，一個解釋I 由以下四部分組成： (1) 對于每個常元c，指派D 中一個元素c。 (2) 對于每個n元函詞f，指派一個D 上的一個n元運(yùn)算f。 (3) 對于每個n元謂詞Q，指派一個D 上的一個n元關(guān)系Q。§ （結(jié)構(gòu)）定義： 給定一階語言L以及論域D和解釋I，偶對<D, I>稱為L的結(jié)構(gòu)，記為S=<D, I>。§ （賦值）定義： 從變元到論域D 的函數(shù)稱為I中的賦值，記為:

12、V®D。§ （模型）定義： 給定一階語言L以及它的結(jié)構(gòu)S和賦值，偶對<S,>稱為L的模型，記為M=<S,>。§ （項的語義）定義：設(shè)L是一階語言，U是論域，I是解釋，語言L的項t的語義是D中一個對象，記為I(t)，簡記為(t) 。 (1) 若t是常元a，則(t) =aI。 (2) 若t是變元x，則(t) = (x)。 (3) 若t是f (t1, t2, , tn)，則(t) = f I(t1), (t2), , (tn)。§ （謂詞合式公式意義）定義 給定一階語言L，結(jié)構(gòu)S=<D, I>和賦值函數(shù):V®D，t

13、1, t2, , tn是項。在模型M=<S, >下，公式P,Q,R的語義是確定的邏輯真值。 (1) 若P是Q(t1, t2, , tn)，則(P) = QI(t1), (t2), , (tn)。 (2) 若P是ØQ，則(ØQ) = Ø(Q)。 (3) 若P是QÙR，則(QÙR) =(Q) Ù(R)。 (4) 若P是QÚR，則(QÚR) =(Q) Ú(R)。 (5) 若P是Q®R，則(Q®R) =(Q) ®(R)。 (6) 若P是Q«R，則(Q«

14、R) =(Q) «(R)。 (7) 若P是QÅR，則(QÅR) =(Q) Å(R)。 (8) 若P是"xQ(x)，則 (9) 若P是$xQ(x)，則§ （可滿足性）定義： 定義：給定一階語言L和它的公式Q，如果存在模型M=<S, >，使得(Q)=1成立，則稱公式Q關(guān)于模型<S, >是可滿足的，簡稱Q可滿足，也稱模型<S, >滿足Q，記為 M Q。 定義：給定一階語言L和它的公式Q，如果不存在模型M=<S, >，使得(Q)=1成立，則稱公式Q關(guān)于模型<S, >是不可滿足的，也稱

15、模型<S, >不滿足Q，記為|¹M Q。 定義：給定一階語言L和它的公式集合= Q1,.,Qn，如果存在模型M=<S, >，使得對于每個公式Qk，QkÎ，有(Qk)=1成立，則稱公式集合關(guān)于模型<S, >是可滿足的，簡稱可滿足，也稱模型<S, >滿足，記為 M，也記為()=1。§ （有效性）定義 定義：若合式公式Q對于一階語言L的任意模型M=<S, >均可滿足，即對任意結(jié)構(gòu)S和任意賦值成立，則稱公式集合Q是永真的或有效的，記為 Q。 定義：若合式公式集合對于一階語言L的任意模型M=<S, >均

16、可滿足，即對任意結(jié)構(gòu)S和任意賦值成立，稱公式集合是永真的或有效的，記為 。 定義：若公式Q對于一階語言L的任意模型M=<S, >均不可滿足，即對任意結(jié)構(gòu)S和任意賦值都不成立，稱公式集合Q是永假的，記為|¹ Q。§ （相等關(guān)系與推論關(guān)系）定義： 定義：給定一階語言L及它的兩個公式Q,R，如果存在模型M=<S, >，使得(Q) = (R), 則稱Q與R是在模型M等值，記為QÛMR。 定義：如果對于任意模型模型M=<S, >，都有 (Q) = (R), 則稱Q與R是邏輯等價，記為QÛR。 定義：給定一個語言L , 是一個公式

17、集合, Q 是一個公式。若存在模型M=<S, >，使得當(dāng)()=1時有(Q)=1，則稱Q 是關(guān)于模型的邏輯推論，記為MQ。 定義：給定一個語言L , 是一個公式集合, Q 是一個公式。若對于任意模型M=<S, >，使得當(dāng)()=1時有(Q)=1，則稱Q 是邏輯推論，或稱語義推出Q，記為Q。§ （代入與可帶入）定義： 定義：設(shè)L是一階語言，t和 t '是L的項，x是t中自由變元，若t中x的任何自由出現(xiàn)都替換為t ' ，則稱項t中的自由變元x被項t '代入 (substitution)。 定義：設(shè)L是一階語言，t是L的項， Q是合式公式，x是Q

18、中自由變元，若Q中x的任何自由出現(xiàn)都替換為t，則稱公式Q中的自由變元x被項t代入 (substitution)。 定義：設(shè)t是項，y是t中任一自由變元，Q是合式公式，x是Q中自由變元，如果Q中x的任何自由出現(xiàn)都不在"y($y)的轄域內(nèi)，則稱項t是對Q中自由變元x可代入的(substitutable)。 定理：設(shè)L是一階語言，M=<S, >是模型，若t和t '是L的項，則(tx/t')= (tx/(t')。 定理：設(shè)L是一階語言，模型M=<S, >，設(shè)t是L的項，Q是L的公式，若對于公式Q中的x是t可代入的，則(Qx/t)= (Qx/(t

19、)。§ （對偶性）定義： 定義：設(shè)合式公式Q是由原子公式、聯(lián)結(jié)詞（Ø ,Ù,Ú）、量詞（", $）生成的公式，并且在Q中聯(lián)結(jié)詞Ù和Ú互換，量詞"和$互換，原子公式和它的否定式互換，而得到公式Q'，則公式Q和Q'互為對偶式。 定理：設(shè)合式公式Q和Q'互為對偶式，則(Q) « (ØQ')。公理系統(tǒng)§ （形式系統(tǒng)）一個形式系統(tǒng)應(yīng)當(dāng)包括以下幾部分。 (1)各種初始符號。初始符號是一個形式系統(tǒng)的“字母”，經(jīng)解釋后其中一部分是初始概念。 (2)形成規(guī)則。規(guī)定初始符號

20、組成各種合適符號序列的規(guī)則。經(jīng)解釋后合式符號序列是一子句，稱為系統(tǒng)里的合式公式或命題。 (3)公理。把某些所要肯定的公式選出，作為推導(dǎo)其它所要肯定的公式的出發(fā)點，這些作為出發(fā)點的公式稱為公理。 (4)變形規(guī)則。變形規(guī)則規(guī)定如何從公理和已經(jīng)推導(dǎo)出的一個或幾個公式經(jīng)過符號變換而推導(dǎo)出另一公式。經(jīng)過解釋，變形規(guī)則就是推理規(guī)則。§ （公理系統(tǒng)）定義： 從一些公理出發(fā)，根據(jù)演繹法，推導(dǎo)出一系列定理，形成的演繹體系叫作公理系統(tǒng)。 公理系統(tǒng)的組成： 符號集； 公式集：公式是用于表達(dá)命題的符號串； 公理集：公理是用于表達(dá)推理由之出發(fā)的初始肯定命題； 推理規(guī)則集：推理規(guī)則是由公理及已證定理得出新定理的

21、規(guī)則； 定理集：表達(dá)了肯定的所有命題。 定義：命題邏輯的公理系統(tǒng)定義: (1).符號集合： 1).命題變元Q1,Q2,Qn 2).聯(lián)結(jié)詞符號：Ø，® 3).括號：(,) (2).形成規(guī)則(公式定義)： 1).若Q是命題變元，則Q是公式； 2).若Q是公式，則(ØQ)是公式； 3).若Q,R是公式，則(Q®R)是公式。 (3).公理：公理模式中P,Q,R為任意公式 1).公理模式A1： R® (Q®R) 2).公理模式A2： (P® (Q®R) ® (P®Q) ® (P®R)

22、3).公理模式A3： (ØQ®ØR) ® (R®Q) (4).變形規(guī)則：推理規(guī)則(分離規(guī)則MP規(guī)則) 若Q和Q®R成立，則R成立。其中， Q和Q®R稱為前提，R稱為結(jié)論。 謂詞邏輯的公理系統(tǒng)定義： (1).符號集合： 1).個體變元：x1, x2, 2).個體常元：c1, c2 , 3).函詞符號：f11, f21,.；f12, f22,.； 4).謂詞符號：Q11,Q21,.；Q12, Q22,.; 5).運(yùn)算符號：", Ø, ®； 6).逗 號：, ; 7).括 號：(, ) (2).項定義

23、： 1).個體常元是項； 2).個體變元是項； 3).若是t1,tn項，則是fkn (t1,tn)項。 (3).公式集合： 1).若是t1,tn項，則Q kn (t1,tn)是公式。 2).若Q是公式，則(ØQ)是公式； 3).若Q和R是公式，則(Q®R)是公式； 4).若Q是公式，則("xQ)是公式。 (4).公理集合： 1).公理模式A 1：Q® (R®Q) 2).公理模式A 2：(P® (Q®R) ® (P®Q) ® (P®R) 3).公理模式A 3：(ØQ®

24、ØR) ® (R®Q) 4).公理模式A 4："xQ(x)®Q(x)x/t 其中，項t對于Q中的x是可代入的。 5).公理模式A 5："x(Q®R(x) ® (Q®"xR(x) 其中x不是Q中自由變元。 (5).推理規(guī)則 1).分離規(guī)則（簡稱MP規(guī)則）：從Q和Q®R推出R。 2).概括規(guī)則（簡稱UG規(guī)則）：從Q(x)推出("xQ)。 常用定理 (P®(Q®R) ®(Q®(P®R) (Q ® R)®(P

25、74;Q)®(P®R) (P® Q)®(Q®R)®(P®R) (P® Q)®(P®R) ®P®(Q ®R) Q®Q ØØQ®Q Q®ØØQ QÚQ ®Q Ø(QÙØQ) (QÚØQ) (ØØQ®ØØR)®(Q®R) (Q®R)®(Ø

26、;ØQ®ØØR) (Q®R)®(ØR®ØQ) (ØQ®R)®(ØR®Q) (Q ®ØR )®(R®ØQ) ØQ®(Q® R) (ØQ®Q)®(R®Q) (ØQ®Q)®Q (Q®R) Ú (R®Q) (Q® R)Ú(Q ®ØR) Q®

27、;(Q®R)® R) QÙ(Q®R)®R (P®Q) ®(Q ®R) ®(P ®R) (ØQ®R) ®(ØQ®ØR) ®Q) (Q®R) ®(Q®ØR) ®ØQ) (ØQ®R ÙØR) ®Q (PÙQ ®R) ®(P ®(Q ®R) Q®(R®(QÙR) (P®Q) Ù(P®R) ®(P®Q Ù R) (P®R) ®(Q®R) ®(PÚQ) ®R) "xR(x) « "y R(y) $xR(x) « $y R(y) Q(c) ®