高級(jí)數(shù)理邏輯第2講

1、3 命題邏輯形式系統(tǒng)（FSPC）3.1 命題邏輯與命題演算Leibniz提出邏輯推理變成符號(hào)演算不久，英國(guó)數(shù)學(xué)家BOOL提出了布爾代數(shù)。布爾代數(shù)把邏輯命題與邏輯推理歸結(jié)為代數(shù)計(jì)算。把命題看作是計(jì)算對(duì)象；把聯(lián)結(jié)詞看作算子；討論計(jì)算的性質(zhì)。1、 命題（Propositions）：可以判斷真假的陳述句。不涉及任何聯(lián)結(jié)詞的命題稱為原子命題。2、 聯(lián)結(jié)詞：, , , , 為聯(lián)結(jié)詞，用于聯(lián)結(jié)一個(gè)或者多個(gè)命題。A=1-A如果A成立則B成立，如果A成立則B成立，并且如果B成立則A成立；ABAB，或者A成立或者B成立；AB，A成立并且B成立。3、 真值表：命題的真假稱為命題的真值，用0表示假；用1表示真。ABT

2、(A)=1-T(A) A=1, A=0, 1-ATrue(A)1- True(A)，如果True(A)0，True(A)=1：True(A)=1, True(A)0T(AB)=1 或者A不成立，或者B成立； A=1, B=1, AB =1A=0, B=1, AB=1A=0, B=0, AB=1A=1,B=0 AB=0或者A=0, 或者B1 AvB=ABA=B;A=BA=0,B=1A=0時(shí)，B=?,1;A=1,B=1,1;A=1,B=0,0;A=0,B=0,T(AB)=1;A=0,B=1,T(AB)=1;A=1,B=0,T(AB)=1;A=1,B=1,T(AB)=1;A=0;T(AB)=1B=1

3、;T(AB)=1AB是或者A=0,或者B=1；=AvBAB)：True（A）True（B）A0,1；如果True(A)=1,則 True（B）=1,True(A-B)=1:或者True(A)=0或者True(B)=1：或者A不成立，或者B成立=AB；如果True(A)=0,則 True（B）=0，1；True(A)=True（B）；True(A) =True(B)，True(AB)=1；True(AB);A=1,B=0,1,A=1,B=1, 1;A=0,B=0,0,A=0,B=1,1.True(AB),A=1,B=0,0,A=1,B=1,1;1=0,B=0,0; A=0,B=1,0True(A

4、B)=max(True(A), True(B); True(AB)= min(True(A), True(B);4、 命題變?cè)阂哉嬷禐橹涤虻淖兞糠Q為命題變?cè)?。T(A)-0,15、 賦值映射：命題變?cè)系?,1上的函數(shù)。如果公式A對(duì)任意的賦值映射，取值為真，則稱A為永真式TAUTLOGY。如果公式A對(duì)于所有賦值映射為假，稱為A為矛盾式。對(duì)于任意賦值映射，公式A的真值等于公式B的真值，成A與B等價(jià)。(A(BC)(AB)(AC)=1AA 1 A(BA)= A=0, 1; A=1, 1;A&A =0T(AB)= T(AVB)A1A1=1=A1VA1A1A1=A1AA (AA)(AA) .AA AB

5、 或者A,或者A命題邏輯有以下特點(diǎn)：1、 從語(yǔ)義角度研究邏輯命題之間真值變化規(guī)律。對(duì)于任意公式可以給出其所有的真值可能性。2、 存在永真式，例如：等。3、 永真式通過三段論推理方法得到的公式，仍然為永真式?；谶@樣的事實(shí)，提出一個(gè)問題“是否有永真式的最小集合？”。答案是肯定的。公理方法的出現(xiàn)，使人們開始用公理方法研究邏輯系統(tǒng)。于是產(chǎn)生了命題邏輯形式系統(tǒng)。ABC(AVB)C000100110100011110001011110011113.2 命題邏輯形式系統(tǒng)（FSPC）PC最著名的形式化系統(tǒng)可能源于Whitehead和Russell 的數(shù)學(xué)原理(Principia Mathematica)。3

6、.2.1 FSPC定義1、 語(yǔ)言部分（1）符號(hào)集：（, ）, , , ,p1 ,p2 ,p3. ，其中, , , 為聯(lián)接詞；（，）為技術(shù)符號(hào)，即括號(hào)；p1 ,p2 ,p3為命題變量（命題變?cè)蛘呙}符號(hào)）。（2）項(xiàng)集：為空集。（3）公式集合：公式集合有以下遞歸定義。I. p1 ,p2 ,p3（命題變?cè)楣?，稱為原子公式。II. 如果A、B為公式，那么（），（），為公式。III. 所有的公式都是由1和2有限步驟得到的，除此之外沒有公式。語(yǔ)言部分定義了FSPC的公式（語(yǔ)言）產(chǎn)生規(guī)則。2、 推理部分（1）公理：FSPC包含下列三個(gè)公理模式：I A1II A2 III A3 -(A-A) ( )(

7、AA)A(AA)(A(BC)(AB)(AC)(A(BA)(AB)(AA)(A(AA)A)(A(AA)(AA)A(AA)A)(A(AA)(AA)(A(AA)AA(AB)(AA)B(AB)C(BA)AB形式化：ABAB111100001011語(yǔ)義上的理解(如果A成立，則B成立)如B(AA)(如果x是實(shí)數(shù)，則x2大于等于0B)AB001011101111A(x為實(shí)數(shù))B(x2大于等于0)如果(x不是實(shí)數(shù))則x2不一定大于0在x不是實(shí)數(shù)(A=0)的情況下；AB是否成立？1如果（x如果是超出4中數(shù)定義之外的數(shù)）則x2大于0(2) 推理規(guī)則集合：只有一條推理規(guī)則，稱為分離規(guī)則：分離規(guī)則（modus pon

8、eus）3.2.2 公式結(jié)構(gòu)1、公式產(chǎn)生序列：l 對(duì)于一個(gè)上的字符串A是公式的充分必要條件是存在一個(gè)公式序列其中為（1）到（3）中的一種：（1）：為原子公式（2）：存在，使得（3）：存在，使得l 公式生成過程舉例：例如公式：，的生成過程。（1）首先p、q、r為公式（原子公式）p, q, r, p, q, r, pq, qr, rp, p( qr),（2）（）、為公式（3）為公式（4）公式我們有樹能夠更清晰地給出公式的生成過程：為公式 3、公式結(jié)構(gòu)特點(diǎn)（1）括號(hào)是在公式中，是成對(duì)出現(xiàn)，左右括號(hào)數(shù)量相同。（2）在自然邏輯中，公式有否定式、合取式、析取式、蘊(yùn)涵式、等值式等不同類型的概念。（3）由于公

9、式采用遞歸定義的方法來(lái)定義，因此，對(duì)上的任意字符串能夠判斷是否為公式。（4）形式系統(tǒng)的聯(lián)結(jié)詞只有兩個(gè)，因?yàn)樵诿}邏輯的語(yǔ)義上，其他聯(lián)結(jié)詞可以有這兩個(gè)聯(lián)結(jié)詞表示。 , &（5）由于公式是采用遞歸定義方式來(lái)定義的，因此，對(duì)于公式的性質(zhì)通常采用遞歸證明方法來(lái)證明。例如：歸納法證明：R證明其在自然數(shù)集成立， （1）證明，當(dāng)1的時(shí)候，R成立（2）假設(shè)，當(dāng)K的時(shí)候，R成立（3）證明，當(dāng)k+1的時(shí)候R成立設(shè)：R是一個(gè)有關(guān)公式的性質(zhì)，如果要證明R對(duì)于所有公式有效則通過下面的證明步驟：I. 對(duì)于，則II. 假設(shè)公式A和B都具有RIII. ，且，則IV. 是公式，如果且，則由以上三條，可知R對(duì)于FSPC上的所有公

10、式成立。3.3 命題形式演算3.3.1 形式演算1、概念：演繹結(jié)果與定理：設(shè)A為FSPC上一公式，集合為FSPC上一公式集合。稱A為的演繹結(jié)果，記為，如果存在一個(gè)公式序列：A1, A2, A3, A4, A使得或者為形式系統(tǒng)FSPC的公理，或者為公式集合中的元素，或者為由推理規(guī)則r得到；則稱A為FSPC的演繹結(jié)果。當(dāng)時(shí)，稱A為定理FSPC上的定理。稱為A的證明序列。邏輯等價(jià)：公式A和B分別為兩個(gè)公式，如果A,B滿足B，且AB同時(shí)成立，則稱公式A和B為邏輯等價(jià)公式，記為AB。即A,B互為演繹結(jié)果。AvB=ABA,A2,B:B,A2,.,A例如：|，|，|。對(duì)偶：設(shè)A為FSPC上由聯(lián)結(jié)詞, , 和

11、原子公式構(gòu)成的公式。在A中交換和，以及原子公式和他的否定公式，得到公式，則稱為A的對(duì)偶。True(AB)=True(AB)=( AB)(AB) 2、形式演算舉例例：證明為FSPC的定理。證明：（1） A1 ：（2） A2 ：（3）A1 ：（4） （1）（2）（5）（3）（4）已知求證A成立A3.3.2 形式演算方法1、主要的證明方法與手段形式演算方法多種多樣，通常有以下方法：（1） 公理代入原理：設(shè)A(P)為含有變?cè)狿的公理（定理同樣適用），如果將公式A中的變?cè)狿替換為命題變?cè)狟，則A(B)仍為公理（定理）；（公理填充）A-(B-A), A-(A-A)-A)（2）等價(jià)替換原理：設(shè)命題公式A含有

12、子公式C（C為命題公式），如果CD，那么將A中子公式C提換為命題公式D（不一定全部），所得公式B滿足AB。（3）對(duì)偶原理：設(shè)A為FSPC上的公式，為其對(duì)偶，則A。（4）形式演算規(guī)則：在FSPC之上，利用分離規(guī)則擴(kuò)展的推理規(guī)則。例如：AA（自反規(guī)則）；如果A，則A，其中為一個(gè)公式集合（引入規(guī)則）等。這樣擴(kuò)充后的系統(tǒng)被稱為自然推理系統(tǒng)。(公理比較多，連接詞貼近自然語(yǔ)言)（公理只有3個(gè)，連接詞少計(jì)算機(jī)可以使用）（5）聯(lián)結(jié)詞運(yùn)算規(guī)則：針對(duì)聯(lián)結(jié)詞的運(yùn)算規(guī)律。例如：交換律、結(jié)合律、莫根定律等。對(duì)于（1）是對(duì)于任何證明序列所必須的。其他的定律都可以由分離規(guī)則產(chǎn)生。2、不同類型的證明方法在命題演算時(shí)，主要是證

13、明以下問題：1) 命題2) 命題3) 命題4) 命題5) 命題6) 命題針對(duì)這些要證明的問題，通常有以下方法來(lái)證明：1) 命題：l 自反規(guī)則：l 證明，只需證明0中，0l 銷去：如果 則（分離規(guī)則）l 銷去（反證法）：如果， ， 則-BA1,A2,A3=A1A2A3(BB)-(A-B-C)l 包含：l 銷去：如果則2) 命題 （同上）3) 命題 ，則）（演繹定理）A1,An=AB, A,B;4) 命題5) 命題如果或者或者B則6) 命題如果并且B則例：證明：（1），包含（2），包含（3）（反證規(guī)則）3.3.3 形式演算性質(zhì)形式演算主要有以下特點(diǎn)：1) 緊致性：設(shè)為FSPC上的公式集合，A為FS

14、PC的公式。如果，則存在的有限子集0 使得0 。由已知，存在A的一個(gè)證明序列：A1,.Am=A;其中，Ai或者是公里，或者是中的元素，或者是由i前邊的通過分離規(guī)則得到的。Ai, Aj= 0我們將這個(gè)證明序列中，所有中的元素抽取出來(lái)構(gòu)成新的集合：0，這個(gè)0 是 的子集。A1,.Am是由0 證明A的一個(gè)證明序列。所以，0 可以推倒出A來(lái)。A1,A2,A3,A4=A假設(shè)A1公理，A2是,A3是分離得到，A4=A,分離規(guī)則A2AA2,A3,A5,A6,A,A2A A2) 傳遞性：設(shè)和1為FSPC上的公式集合，A為FSPC的公式。如果1 ，1；則成立。B1,B2,B3=1=B1B2B3公式集合公式|-B

15、1 A11, A1,2, ., A1m=B1 A2,1., A2m=B2 A31,.,A3m=B3B0, A11, A1,2, ., A1m,B2,B3 ,B4, Bn =A由于1 可以推倒出A來(lái)，因此存在一個(gè)證明序列：A1An=A，其中Ai或者為公里，或者為1 中的元素，或者為前邊的公式推倒出來(lái)的。假設(shè)Aj是1 元素且是證明中的元素。只要證明存在一個(gè)1 中的證明序列可以證明Aj就可以了。由于已知，因此對(duì)于每個(gè)1 的元素都存在一個(gè) 上的證明序列。因此，Aj存在一個(gè) 上的證明序列的。將所有的A1An證明序列中，屬于1 的元素的證明序列按照先后順序排成一個(gè)證明序列，那么這個(gè)證明序列就是由 推導(dǎo)A的

16、一個(gè)證明序列。因此， 可以推導(dǎo)出A，AA1,A2,A3,A4=B1,B2=1C1,C2,B1,C3,B2,AC4,A2,A1,B1C5,A3,A4,A2,B2C1,C2,C4,A2,A1,B1,C3,C5,A3,A4,A2,B2,A例：證明（1）前提（2）A1 （3）（1）（2）分離規(guī)則（4）(AA)(AA)A3（5）（3）（4）（6）A3（7）（5）（6）（8）* 公理推演系統(tǒng)模式單一，易于機(jī)械化，而推理過程復(fù)雜。* 自然推演系統(tǒng)，模式復(fù)雜，相對(duì)證明過程簡(jiǎn)單。證明：已知A(BC), B, 證明:AC是已知的邏輯結(jié)果。A(BC),B,A C（1） A(BC) 前提（2） A 前提（3） BC 1,2分離（4） B 前提（5） C 3，4分離證明：只需證明對(duì)于任何賦值映射f，如果f使得f(A(BC)=1,并且f(B)=1,則f使得f(AC)=1。由已知可以知道：f(B)=1,f(A)=0或者f(BC)=1。因此分兩種情況：1、假設(shè)f(A)=0;則f(AC)=1.2、假設(shè)f(A)!=0,那么f(BC)=1.f(B)=1,則f(C)=1.因此，f(AC)=1.由此，命題成立。證明：A(BC), B, A，證明CA(BC)1B2A3BC 4（1，3）C5（2，4）證明：如果A(BC), B成立，則AC成立。題目：如果一個(gè)賦值映射