高級數(shù)理邏輯第3講

1、3 命題邏輯形式系統(tǒng)（FSPC）續(xù)3.4 命題邏輯語義P(X)àQ(F(Xa) A(X)->A(X)X是復(fù)數(shù)，則（x-a）平方大于等于0；X=RPx是復(fù)數(shù)Q(x)代表的是大于等于0F代表的是平方X復(fù)數(shù)T(P(X)=0.5P(X)à(Q(X)àP(X)AàB3.4.1 基本概念1、什么是形式系統(tǒng)的語義（1） 形式系統(tǒng)與具體的系統(tǒng)無關(guān)（2） 能夠用形式系統(tǒng)來描述現(xiàn)實系統(tǒng)（3） 把從形式系統(tǒng)解釋成“”現(xiàn)實系統(tǒng)的過程成為語義 語義有多種類型：指稱語義，克里普克語義，操作語義，公理語義等2語義構(gòu)成 (指稱語義)語義主要有兩部分：（1） 結(jié)構(gòu)：（有兩個主要部分

2、構(gòu)成）*確定研究對象集合，論域或個體域*把形式系統(tǒng)中的變量到論域中的一組規(guī)則映射規(guī)則（2） 域值：指一組給公式賦值的規(guī)則根據(jù)這項規(guī)則將 AtomicValue中3.4.2 命題邏輯語義1、語義結(jié)構(gòu)由于沒有變量，所以只有第二部分賦值，值域為0,1賦值規(guī)則：I.II.T(A)= 當(dāng)T（A）0時，T(A)=1。當(dāng)T（A）1時，T(A)=0。III.當(dāng)T(A)=T(B)=1時，T()=1，其他情況T()=0。IV.當(dāng)T(A)1或者T（B）1情況下，T（）1，其他情況T（）0。V.當(dāng)T(A)=0時候，T（）=1,當(dāng)T(B)=1時候，T（）=1。其他情況下T（）=0。AàBVI.2、 語義的特殊

3、公式1) 公式A為永真式，重言式tautologies，如果對一切賦值，.AàA=AvA(AàA)=1, Aà(BàA)=12) 公式A為永假式，矛盾式contradictions,如果對一切賦值，AA=03) A，B為邏輯等價的，如果對于一切賦值，記做AB(A|=|B)T(A)=T(B),對于任意TA->A A->(B->A) 4) 可滿足的，公式A為可滿足的，如果至少存在一個賦值，3、 真值計算有了賦值映射，我們可以計算任意公式的真值。通常真值計算的方法有：真值表計算方法和二叉樹計算方法等。1) 真值表真值表是計算真值的簡單工具。利

4、用這個工具可以計算任意公式的真值。例如：公式的真值表如下：000100110101011110011010110111112) 二叉樹利用二叉樹，可視化地計算公式的真值。例如：計算下面公式的真值，并給出他是否是重言式。 故A不為重言式，是可滿足的3) 習(xí)題 求以下公式的真值表：（1）（2）（3）pqr000100110101011110001011110011113.5 邏輯推論（邏輯演算）有了公式的真值以后，對于一些公式我們可以比較公式的真值得大小。從而可以討論公式真值之間的關(guān)系。討論公式之間真值關(guān)系的就是我們在語義上進(jìn)行演算的主要內(nèi)容。3.5.1 基本概念（1）邏輯推論：設(shè)是一個FSPC上

5、的公式集合，A是FSPC上的任一公式。A為的邏輯結(jié)果，記做|=A，當(dāng)且僅當(dāng)對任何賦值映射v，如果1時，則。|=讀作邏輯蘊涵。（2）邏輯等價：設(shè)公式A和公式B分別為FSPC上的兩個公式。A和B為邏輯等價的，記做A|=|B當(dāng)且僅當(dāng)A|=B和B|=A同時成立。（3）永真式：如果A為永真式，則公式集合為空集，即|=A。3.5.2 邏輯推論的主要方法（1）永真式代入原理（principle of substitution）設(shè)A(P)為一含有命題變元P的永真式，那么將A中P的每一次出現(xiàn)代換為公式B，所得公式A(B)仍為永真式。C->(B->C) = C->(X->C)（2）替換原理

6、（principle of replacement）設(shè)命題公式A含有子公式C（C為命題公式），如果C|=|D，那么將A中子公式C提換為命題公式D，所得公式B滿足A|=B。（3） 邏輯等價性：邏輯等價且有自反性、對稱性和傳遞性。（4） 對偶原理： 設(shè)A是原子公式和聯(lián)結(jié)符號組成的公式，并且在A中交換以原子公式與其否定互換得到的公式A,稱A為A的對偶；A|=AA B(A B) （5） 演繹定理：設(shè)為FSPC的公式集合，A和B分別為FSPC上的公式。|=成立的充分必要條件是：|=。已知：存在一個證明序列A1,A2,An=AàB,An+1=A,An+2=B求證：存在另一個證明序列：從出發(fā)能夠得

7、到B。已知：對于任意一個賦值映射f,如果f()=1,則f(AàB)=1;求證：對于任意的賦值映射f,如果f(,A)=1，則f(B)=1證明：已知：對于任意的賦值映射f，如果f滿足f()=1,則f(AàB)=1.求證：對于任意的賦值映射f1,f1滿足f1()=1,且f1(A)=1；則f1(B)=1.證明：任意的賦值映射f,f滿足f1()=1,且f(A)=1.由于f1()=1，則f1(AàB)=1;由于f1(AàB)=1,并且f1(A)=1;條件：f()=1,且f(A)=1, f(AàB)=1，證明：f(B)=1由已知：f(AàB)=1.

8、因此，f(B)=1.因此，對于任意的賦值映射f,f滿足f()=1,且f(A)=1；則f(B)=1.必要性：已知：對于任意的賦值映射f,f滿足f()=1,且f(A)=1；則f(B)=1.求證：對于任意的賦值映射f1，如果f1滿足f1()=1,則f1(AàB)=1.對于任意的賦值映射f，使得f()=1.F1()=1,f1(A)=0 f1(AàB)=1F1()=1,f1(A)=1 ,f1(B)=1, f1(AàB)=1假設(shè)f1(A)=0;f1(AàB)=1.假設(shè)f1(A)=1, 由于已知條件可以知道f(B)=1.因此，f(AàB)=1.證明： a)首

9、先證明充分性：已知，證明成立。對于任意賦值映射v，如果1成立，則成立。對于成立有兩種情況，為了證明成立，只需考慮，使1的情況。如果賦值映射v，滿足1，1且，則有1。因此，成立。b)證明必要性：已知 ，證明成立。已知：如果對于任意的賦值映射且則；要證明：即證明對于任意賦值映射v，滿足，則有成立。任取賦值映射v，滿足，則有：當(dāng)0時，有當(dāng)1時，由已知1，因此3.5.3 邏輯推論性質(zhì)1、公理為重言式A1vA2vA3v2、推理規(guī)則保真性設(shè)A和B為FSPC上的公式；如果|=A且|=成立，則|=成立。3、重要永真式T1 T(P)<=T(P)T2 P<=Max(P,Q)T3 Min(P,Q)<

10、;=PT4 P<=Q, Q<=R, P<=R T5 P=Q,Q=R, P=R4、重要等價式E1 P=1-(1-P)=P E2 （等冪律） E3 (交換律)E4 E5 （分配律）E6 （德摩根定律）E7 E8 E9 Pv(QàR) =Pv(QvR)=(PvQ)vR=(Q P)vR=(P Q)àR如果P=1，則QàR=1;如果min(Q,P)=1,則R=1.E10 (PvQ) (QvP)=(PvQ)Q)v(PvQ) P)=(QP)v(PQ)E11 E12 Max(P, Min(P,Q)=P MIN(P,Q)<PMIN(P,MAX(P,Q)=PM

11、AX(P,Q)>=P. （吸收律）3.6 公式化簡3.6.1 基本概念有了賦值規(guī)則和上述的等價公式后，我們就可以將公式進(jìn)行等價形式的轉(zhuǎn)化。轉(zhuǎn)換的目標(biāo)是獲得一個標(biāo)準(zhǔn)的公式形式，從而使公式計算更簡單，同時使計算機(jī)能夠進(jìn)行基于符號的演算和推理過程。范式是常用的公式的標(biāo)準(zhǔn)形式。1、范式：設(shè)A和B為FSPC上的兩個公式，稱公式B為公式A的析?。ê先。┓妒?，如果B|=A，并且B型如：C1, C2, C3, ,Cm L1Vl2， L2vL1 L2P(x), P(5+y)= x=5+y, P(5y) P(5+y)其中，稱為B的子句（Clause），子句型如：Ci=其中為原子公式或其否定式，被稱為文字。2

12、、對于FSPC上的任意公式A，存在一個析取（合?。┓妒脚c其邏輯等值。3、舉例：求的析取范式。如果P與Q同時成立，則R成立的同時Q不成立。(PQ) v(QR)=(PvQ)v(QR)= PvQv(QR)= PvQ（1）（2）（3）（4）（5）3.6.2 化簡過程由以上的論述可知，對于任意公式，存在與其等價的析?。ê先。┓妒健τ谌我夤紸，可以通過以下步驟得到他的析取（合?。┓妒?。（1）銷去：利用E7 ，E10 和E11 銷去公式中存在的聯(lián)結(jié)詞，和。（2）深入：將深入到原子公式之前。（3）利用E4 和E5將公式展開。 3.6.3 聯(lián)結(jié)詞完備集在自然推理系統(tǒng)中，聯(lián)結(jié)詞有, , , , （還可以有其他

13、多種聯(lián)結(jié)詞，如異或等）。在TASKI語義下，聯(lián)結(jié)詞可以由其他的聯(lián)結(jié)詞表示。那么是否存在一個最小的聯(lián)結(jié)詞的集合，能夠表示所有的其他聯(lián)結(jié)詞？答案是肯定的。1、聯(lián)結(jié)詞的完備集：聯(lián)結(jié)詞的集合為完備的，當(dāng)且僅當(dāng)對于其他的聯(lián)結(jié)詞都可以由這個聯(lián)結(jié)詞的集合中的元素來表示。2、FSPC中的完備集：、等。如果引入異或，那么異或與也構(gòu)成一個完備集合。3.7 元理論與元語言3.7.1 基本概念1、對象語言：形式語言本身，他是用來描述形式系統(tǒng)研究的對象的。AàB2、元語言：用來描述對象語言性質(zhì)的語言。Meta math=meta data 3、元語言的組成：（1）形式系統(tǒng)各組成部分的稱謂，如：公式、公理等。（

14、2）對形式分析討論時所使用的邏輯術(shù)語，如：如果.，那么.等。（3）描述形式系統(tǒng)有關(guān)性質(zhì)的語言，如：一致性、完備性等。4、元理論：研究形式系統(tǒng)所得到的定理和性質(zhì)等。3.7.2 元理論的內(nèi)容元理論是數(shù)理邏輯研究的主要內(nèi)容之一，元理論主要包含以下內(nèi)容：1、語法構(gòu)成研究（Syntax）：主要是關(guān)于形式系統(tǒng)語言構(gòu)成規(guī)律的研究。研究符號串的推演規(guī)律（重寫規(guī)則）。2、語義研究（Semantics）：在這類研究中，符號被賦予一定的意義。研究在這種意義下，對公式作出各種解釋的性質(zhì)，特別是真值性質(zhì)的研究。3、語法與語義關(guān)系：這種關(guān)系主要研究，語法演算與語義推理之間的性質(zhì)。主要研究語法與語義之間能否具有一致性關(guān)系。

15、3.8 命題邏輯元理論根據(jù)元理論的主要內(nèi)容，有語法、語義和語法與語義關(guān)系。形式化系統(tǒng)à語義結(jié)構(gòu)à元理論à自動化3.8.1 語法研究1. 語法構(gòu)成語法構(gòu)成研究形式系統(tǒng)語言構(gòu)成規(guī)律。主要研究推演（重寫）規(guī)律；主要規(guī)律：（1）獨立性：如果形式系統(tǒng)中每一個公理都是獨立的，即把任一公里A從形式系統(tǒng)中刪除后，所得形式系統(tǒng)FS不滿足FSA（即A不是FS的定理），則稱形式系統(tǒng)為獨立的；l 獨立形式系統(tǒng)是簡潔的；（2）一致性：形式系統(tǒng)FS稱為一致性，或相容的（consistent）如果不存在FS的公式A，使得A，同時成立；l 所有形式系統(tǒng)都應(yīng)該是一致的；（3）完全性：形式系統(tǒng)為完全

16、的，如果對形式系統(tǒng)中任意公式A，或者A成立，或者成立；l 完全性的形式系統(tǒng)，一切都是可知的；因此，幾乎沒有價值；A并且是定理：1. 有限步驟內(nèi)，可以給出證明2. 有限步驟內(nèi)，不能給出證明A不是定理1. 有限步驟內(nèi)，可以給出不是定理的證明2. 有限步驟內(nèi)，不能給出不是定理的證明（4）可判定性：形式系統(tǒng)FS稱為可判定的，如果存在一個算法，對FS對的任一公式A，可確定A是否成立，否則稱FS是可判定的；如果上述算法對定理能作出判斷，而對于非定理未必終止（作判斷），稱FS為半可判定的；l FS為可判定的，當(dāng)且僅當(dāng)定理集合為遞歸集；（5）公式集合一致性：稱形式系統(tǒng)的公式集合為一致的，如果形式系統(tǒng)是一致的，

17、且不存在公式A使A ， 同時成立。2. 命題邏輯系統(tǒng)的語法構(gòu)成命題邏輯主要以下定理：1) FSPC一致性：FSPC是一致的，即不存在公式A，使A ，同時成立，l 若公式（FSPC）集可滿足的，則為一致的。2) FSPC不完全性：FSPC不是完全的，即存FPSC的公式A，使A ， 都不成立。證明：只需證明原子命題和其否定式，不是FSPC的定理。設(shè)P為FSPC的任意命題變元，如果P是定理，如果 P，則存在P的證明序列：其中或者為公理或者由 由rmp的到；由代入原理可知，為永真式；這與P不是永真式矛盾。3) FSPC可判定性：FSPC是可判定的。4) FSPC是獨立的3.8.2 語義研究可滿足性：F

18、SPC的公式A稱為可滿足的，如果存在賦值V使V(A)1，否則稱A為不可滿足的；3.8.3 語法語義關(guān)系語法和語義關(guān)系是元理論中最重要的內(nèi)容，語法語義關(guān)系評價了一個形式系統(tǒng)的性質(zhì)。語法語義關(guān)系的核心問題是合理性與完備性。形式：A1,A2,An=Af(A1)=1,.f(An)=1: f(A)=0 語法à語義 合理性語義à語法 完備性I 語法和語義關(guān)系研究語法語義關(guān)系，首先關(guān)心的問題是在語法上的形式演算，在語義的邏輯推論上是否成立。這個問題被稱作合理性（Soundness）。其次，是對于語義上的邏輯推理，在形式演算上是否成立。這個問題是完備性（Completeness）。這兩個問

19、題是語法語義關(guān)系的核心。: A1,.An=AF()<=f(A)F()=1,F(A)=1,F(B)=1,F(C)=1.1) 合理性（soundness）：稱形式系統(tǒng)FS是合理的，F(xiàn)S的任意公式A有：FS，則|=M，M為所有結(jié)構(gòu)；2) 完備性（Completeness）：稱形式系統(tǒng)FS是完備的，如果對FS的任意公式有：若|=M，則FS，這里M為FS所討論的一類結(jié)構(gòu)；3) 緊致性：稱形式系FS是緊致的，如果對FS的任意公式集有：如果公式集的所有窮子集是可滿足的，那么公式集也是可滿足的；II FSPC語法語義關(guān)系1、FSPC合理性：FSPC是合理的，即對FSPC中任一公式A，如果A成立，則|=v

20、A成立。已知：A是定理求證：A是永真的由于A是定理，存在一個證明序列A1,A2,An=A。N=1時：A1=A。由于A1或者為公理或者是前邊的公式通過推理規(guī)則得到。因此，A1是公理，也就是A是公理。對于任意的賦值映射f，則f(A)=1。假設(shè)：n<m時，命題成立：A是定理則A是永真的。證明：當(dāng)n=m時，命題成立。A1,A2,Am-1, Am=A1, Am是公理：公理是永真的，因此命題成立。2, Am是前邊通過推理規(guī)則得到的。推理分離規(guī)則，三段論。假設(shè)Am是由Ai和Aj通過分離規(guī)則得到。假設(shè)Aj=AiàAm或者Ai=AjàAm。我們I,j <m。由于歸納假設(shè)，Ai和A

21、j都是永真的。由于推理規(guī)則保真性，那么Am是永真的。因此，命題成立。1. 證明序列àT1<=T22. 一致可滿足3. 序列證明則一定存在邏輯結(jié)果4. 存在邏輯結(jié)果，一定存在證明序列證明：（1）由于A成立，因此存在A的證明序列；（2）對A的證明序列長度歸納證明；（3）當(dāng)1時，A為公理；由于公理都為永真式，因此A為永真，即vA成立；（4）假設(shè)當(dāng)<m時成立；（5）當(dāng)m時A或者為公理，如果為公理由（3）可知vA ；或者A由，通過分離規(guī)則（rmp）得到；（6）由于，的序列長度<m；（7）所以有B，；（8）由分離規(guī)則（rmp）保真性，則A成立。l 推論：設(shè)為FSPC的公式集合，

22、A為FSPC的公式；如果A成立，則|=A成立。2、FSPC完備性：FSPC是完備的，即對FSCP的任意公A，如果|=A成立，則A成立。l 推論：設(shè)是FSPC的公式集合，A為FSPC的公式；如果|=A成立，則A成立。1、 若FSPC的公式集是一致的，那么是可滿足的，且其逆亦真。充分性：已知是一致的，證明是可滿足的。4、 FSPC緊致性：FSPC具有緊致性，即對于FSPC的公式集合，如果其所有的有窮子集為可滿足的，則是可滿足的。已知：所有的有窮子集都是可滿足的求證：為可滿足的假設(shè)為不可滿足的，由于上邊的定理，可知是不一致的。因此，|-A,又可以推導(dǎo)出|-A因此，A和A都同時存在證明序列。假設(shè)證明分

23、別為：A1,An Ai或者為公理，或者為中的元素，或者為推理規(guī)則得到。1B1,BmBi或者為公理，或者為中的元素，或者為推理規(guī)則得到。2可滿足，證明：任意FSPC的公式集合，其所有有窮子集為可滿足的；假設(shè)為不可滿足的，則為不一致的，即存在公式A，使得：A，A同時成立；由FSPC的完備性，可知：A，A同時成立。因此，存在A和A的證明序列。假設(shè)A的證明序列中，包含的公式組成的集合為1，假設(shè)A的證明序列中包含的公式組成公式集合為2；則1A，2A，同時成立。A；因此，為不可滿足的。與題設(shè)矛盾，因此為可滿足的。形式化和演算：語義：元理論：簡化：計算機(jī)推理：3.9 總結(jié)3.9.1 主要內(nèi)容回顧1. 形式系統(tǒng)的結(jié)構(gòu)符號公式 可判定遞歸集合公理 獨立性，完全的，一致的，可判定推理規(guī)則 分離規(guī)則，是n元關(guān)系2. 命題邏輯系統(tǒng)Ø 符號：命題變元，聯(lián)結(jié)詞（），技術(shù)符號，（，）Ø 公理：A1 A2 A3 Ø 公式：遞歸集合Ø 推理規(guī)則：A，AB，B3. 語義： *結(jié)構(gòu)（U，Z）P(X)àQ(F(x) 賦值：Atomic,映射范式，完備集的概念4