期末習(xí)題定義必須背

1、命題邏輯(論域)定義：論域是一個數(shù)學(xué)系統(tǒng)，記為D。它由三部分組成：(1)一個非空對象集合S，每個對象也稱為；(2) 一個關(guān)于D 的函數(shù)集合F；(3)一個關(guān)于D 的關(guān)系集合R。（邏輯連接詞）定義設(shè)n0,稱為0,1n 到0,1的函數(shù)為n 元函數(shù)，真值函數(shù)也稱為聯(lián)結(jié)詞。若n =0，則稱為 0 元函數(shù)。（命題合式公式）定義：(1).0 和 1 是合式公式；(2).命題變元是合式公式；(3).若Q,R 是合式公式，則(Q)、(QR) 、(QR) 、(QR) 、(QR) 、(QR)是合式公式；(4).只有有限次應(yīng)用(1)(3)的公式是合式公式。（生成公式）定義 1.5 設(shè)S 是聯(lián)結(jié)詞的集合。由S 生成的公

2、式定義如下：若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=B1B2，或A=B1 B2，或A=B1 B2，或則FC (A)=maxFC(B1), FC(B2)+1。命題合式公式語義論域：研究對象的集合。解釋：用論域的對象對應(yīng)變元。結(jié)構(gòu)：論域

3、和解釋稱為結(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。若Q1,Q2 是合式公式若Q= Q1，則v(Q)= v(Q1)1 Q2，則v(Q)=v(Q1) v(Q2)若1Q2，則v(Q)=v(Q1)v(Q2)若1 Q2，則v(Q)=v(Q1) v(Q2)1 Q2，則v(Q)=v(Q1) v(Q2)若若若1 Q2，則v(Q)=v(Q1) v(Q2)（真值賦值）由S 生成的公式Q 在真

4、值賦值v 下的真值v(Q)定義如下：若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 是由

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

6、字的否定，則稱它們?yōu)橄喾次淖帧ＴO(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。它由三部分組成：(1)

7、一個非空對象集合D；(2) 一個關(guān)于D 的函數(shù)集合,也稱運(yùn)算；(3)一個關(guān)于D 的關(guān)系集合。（一階謂詞邏輯語言）簡稱一階邏輯語言邏輯符號：包括變元、聯(lián)接詞、量詞；非邏輯符號：包括、函詞、謂詞；僅有變元；按形成規(guī)則的合式公式集合（字符集）定義：邏輯符號，包括變元、聯(lián)接詞、量詞、逗號以及括號等，表示如下：變元：x1, x2, 聯(lián)接詞：,；詞：, ；量號：, ;逗號：(, )括非邏輯符號，包括、函詞、謂詞等，表示如下：常元：c1, c2 , 函詞：f11, f21,.；f12, f22,；謂詞：P11,P 21,.； P 12, P 22,。（項(xiàng)）定義：(1).是項(xiàng)；(2).變元是項(xiàng)；(3).若是t

8、1,tn 項(xiàng)，f in 是n 元函詞，則是f i (t1,tn)項(xiàng)。（合式公式）定義：合式公式是按如下規(guī)則的有窮長符號串。n(1).若是t1,tn 項(xiàng)，Qi 是n 元謂詞，則Q(2).若Q 是合式公式，則(Q)是合式公式；(3).若 Q 和R 是合式公式，則(QR)、(QR)、(QR) 、(QR)及(QR)是合式公式；1,tn)是合式公式。(4).若Q 是合式公式，x 是變元，則(xQ)及(xQ)是合式公式。(5).只有有限次應(yīng)用(1)(4)的公式是合式公式。（約束變元）定義：若(xQ)(或xQ)是公式，則稱變元x 在公式(xQ) (或xQ)中為約束出現(xiàn)，稱x 是約束變元，并稱 x 出現(xiàn)的轄域

9、為Q。（變元）定義：如果變元x 在公式Q 中的出現(xiàn)不是約束出現(xiàn)，則稱 x 在Q 中為出現(xiàn)。變元的集在公式Q 中有合記為 Var(Q)。出現(xiàn)的變元稱為Q 的變元，將Q 中定義：不出現(xiàn)變元的項(xiàng)稱為基項(xiàng)。定義：變元的公式稱為語句。解釋（定義）：設(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，偶對稱為L 的結(jié)構(gòu)，記為S=。（賦值）定義：從變元到論域D 的函數(shù)稱為I 中的賦值，記為 :VD。（

10、模型）定義：給定一階語言 L 以及它的結(jié)構(gòu)S 和賦值 ，偶對稱為L 的模型，記為 M=。（項(xiàng)的語義）定義：設(shè)L 是一階語言，U 是論域，I 是解釋，語言L 的項(xiàng)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=和賦值函數(shù) :VD，t1, t2, , tn 是項(xiàng)。在模型 M=下，公式 P,Q,R 的語義是確定的邏輯真值。(1) 若P 是Q(t1, t2,

11、, tn)，則(P) = QI(t1), (t2), , (tn)。若P 是Q，則(Q) = (Q)。若P 是QR，則(QR) =(Q) (R)。若P 是QR，則(QR) =(Q) (R)。若P 是QR，則(QR) =(Q) (R)。若P 是QR，則(QR) =(Q) (R)。若P 是QR，則(QR) =(Q) (R)。若P 是xQ(x)，則(9) 若P 是xQ(x)，則（可滿足性）定義：定義：給定一階語言 L 和它的公式 Q，如果存在模型M=，使得(Q)=1 成立，則稱公式Q 關(guān)于模型是可滿足的，簡稱 Q 可滿足，也稱模型滿足Q，記為 M Q。定義：給定一階語言L 和它的公式Q，如果不存在模

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

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

14、 Q 是一個公式。若對于任意模型 M=，使得當(dāng)()=1 時有(Q)=1，則稱Q稱 語義推出Q，記為Q。是 邏輯推論，或（代入與可帶入）定義：定義：設(shè) L 是一階語言，t 和 t 是 L 的項(xiàng)，x 是 t 中變元，若 t 中 x出現(xiàn)都替換為 t ，則稱項(xiàng) t 中的變元 x 被項(xiàng) t 代入的任何(substitution)。定義：設(shè) L 是一階語言，t 是 L 的項(xiàng)， Q 是合式公式，x 是 Q 中變元，若 Q 中x 的任何項(xiàng)t 代入 (substitution)。出現(xiàn)都替換為t，則稱公式 Q 中的變元x 被定義：設(shè) t 是項(xiàng)，y 是 t 中任一變元，Q 是合式公式，x 是 Q 中變元，如果 Q

15、中x 的任何出現(xiàn)都不在y(y)的轄域內(nèi)，則稱項(xiàng) t 是對Q 中變元x 可代入的(substitutable)。定理：設(shè) L 是一階語言，M=是模型，若 t 和t 是L 的項(xiàng)，則 (tx/t)=(tx/(t)。定理：設(shè) L 是一階語言，模型 M=，設(shè) t 是L 的項(xiàng)，Q 是L 的公式，若對于公式Q 中的x 是t 可代入的，則(Qx/t)= (Qx/(t)。（對偶性）定義：定義：設(shè)合式公式Q 是由原子公式、聯(lián)結(jié)詞（ ,）、量詞（, ）生成的公式，并且在Q 中聯(lián)結(jié)詞和互換，量詞和互換，原子公式和它的否定式互換，而得到公式Q，則公式Q 和Q互為對偶式。定理：設(shè)合式公式Q 和 Q互為對偶式，則 (Q)

16、(Q)。公理系統(tǒng)個形式系統(tǒng)應(yīng)當(dāng)包括以下幾部分。（形式系(1)各種初始符號。初始符號是一個形式系統(tǒng)的“字母”，經(jīng)解釋后其中一部分是初始概念。(2)形成規(guī)則。規(guī)定初始符號組成各種合適符號序列的規(guī)則。經(jīng)解釋后合式符號序列是一子句，稱為系統(tǒng)里的合式公式或命題。(3)公理。把某些所要肯定的公式選出，作為推導(dǎo)其它所要肯定的公式的出發(fā)點(diǎn)，這些作為出發(fā)點(diǎn)的公式稱為公理。(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)的組成：符號集；

17、公式集：公式是用于表達(dá)命題的符號串；公理集：公理是用于表達(dá)推理由之出發(fā)的初始肯定命題；推理規(guī)則集：推理規(guī)則是由公理及已證定理得出新定理的規(guī)則；定理集：表達(dá)了肯定的所有命題。定義：命題邏輯的公理系統(tǒng)定義:(1).符號集合：1).命題變元Q1,Q2,Qn2).聯(lián)結(jié)詞符號：，;3).括號：(,)(2).形成規(guī)則(公式定義)：1).若Q 是命題變元，則Q 是公式；若Q 是公式，則(Q)是公式；若Q,R 是公式，則(QR)是公式。(3).公理：公理模式中 P,Q,R 為任意公式R (QR)(P (QR) (PQ) (PR)1).公理模式A1：2).公理模式A2：(QR) (RQ)3).公理模式A3：(4

18、).變形規(guī)則：推理規(guī)則(分離規(guī)則MP 規(guī)則)若Q 和QR 成立，則R 成立。其中， Q 和QR 稱為前提，R稱為結(jié)論。謂詞邏輯的公理系統(tǒng)定義：(1).符號集合：1).變元：x1, x2, 2).：c1, c2 , 3).函詞符號：f 1, f 1,.；f 2, f 2,；121224).謂詞符號：Q11,Q21,.；Q12, Q2 ,;5).運(yùn)算符號：, , ；6).逗號：, ;7).括號：(, )(2).項(xiàng)定義：1).是項(xiàng)；2).變元是項(xiàng)；3).若是t1,tn 項(xiàng)，則是fkn (t1,tn)項(xiàng)。(3).公式集合：1).若是t1,tn 項(xiàng)，則Q kn (t1,tn)是公式。2).若Q 是公式，

19、則(Q)是公式；3).若Q 和R 是公式，則(QR)是公式；4).若Q 是公式，則(xQ)是公式。(4).公理集合：1).公理模式A 1：Q (RQ)2).公理模式A 2：(P (QR) (PQ) (PR)3).公理模式A 3：(QR) (RQ)xQ(x)Q(x)x/t4).公理模式A：4其中，項(xiàng)t 對于Q 中的x 是可代入的。A： x(QR(x)(QxR(x)5). 公 理 模 式其中x 不是Q 中5變元。(5).推理規(guī)則1).分離規(guī)則（簡稱MP 規(guī)則）：從 Q 和QR 推出 R。2).概括規(guī)則（簡稱 UG 規(guī)則）：從 Q(x)推出(xQ)。常用定理 (P(QR) (Q(PR)(Q R)(PQ)(PR)(P Q)(QR)(PR)(P Q)(PR)(P(Q R) QQQ(QQ)(QQ) (QR)(QR) (QR)(QR)(QR)(RQ)(QR)(RQ)(Q R )(RQ) Q(Q R)()(RQ)Q(QR) (RQ)(Q R)(Q R)Q(QR)