第一講前言一、課程內容·數理邏輯：是計算機科學的基礎，應嫻熟掌握將現實生活中的條件化成邏輯公式，并能做適合的推理，這對程序設計等課程是極實用途的。·會合論：數學的基礎，對于學習程序設計、數據結構、編譯原理等幾乎全部計算機專業課程和數學課程都很實用途。嫻熟掌握相關會合、函數、關系等基本看法。·代數結構：對于抽象數據種類、形式語義的研究很實用途。培育數學思想，將以前學過的知識系統化、形式化和抽象化。嫻熟掌握相關代數系統的基本看法，以及群、環、域等代數結構的基本知識。·圖論：對于解決很多實質問題很實用途，對于學習數據結構、編譯原理課程也很有幫助。要求掌握相關圖、樹的基本看法，以及如何將圖論用于實質問題的解決，并培育其使用數學工具成立模型的思想方式。·授課時間為兩個學期，第一學期解說數理邏輯與會合論，第二學期解說代數結構和圖論。考試內容限于書中的內容和難度，但授課內容不限于書中的內容和難度。二、數理邏輯發展史目的·認識相關的背景，加深對計算機學科的全面認識，特別是理論方面的認識，而不限于將計算機當作是一門技術或工程性的學科。·經過重要的歷史事件，認識計算機科學中的一些基本思想方式和一些基本問題。2.數理邏輯的發展先期·前史時期——古典形式邏輯時期：亞里斯多德的直言三段論理論·始創時期——邏輯代數時期（17世紀末）·資本主義生產力大發展，自然科學獲得了長足的進步，數學在認識自然、發展技術方面起到了相當重要的作用。·人們希望使用數學的方法來研究思想，把思想過程變換為數學的計算。·萊布尼茲(Leibniz,1646~1716)完美三段論，提出了成立數理邏輯或許說理性演算的思想：·提出將推理的正確性化歸于計算，這類演算能令人們的推理不依靠于對推理過程中的命題的含義內容的思慮，將推理的規則變為演算的規則。·使用一種符號語言來取代自然語言對演算進行描繪，將符號的形式和其含義分開。使得演算從很大程度上取決與符號的組合規律，而與其含義沒關。·布爾(G.Boole,1815~1864)代數：將相關數學運算的研究的代數系統推行到邏輯領域，布爾代數既是一種代數系統，也是一種邏輯演算。3.數理邏輯的奠定時期·弗雷格(G.Frege,1848~1925)：《看法語言——一種按算術的公式語言構成的純思想公式語言》版標記著數理邏輯的基礎部分——命題演算和謂詞演算的正式成立。

(1879)的出·皮亞諾

(GiuseppePeano,1858~1932)

：《用一種新的方法陳說的算術原理》

(1889)提出了自然數算術的一個公義系統。·羅素(BertrandRussell,1872~1970)：《數學原理》(與懷特黑合著，1910,1912,1913)從命題演算和謂詞演算開始，而后經過一元和二元命題函項定義了類和關系的看法，成立了抽象的類演算和關系演算。由此出發，在類型論的基礎上用連續定義和證明的方式引出了數學（主假如算術）中的主要看法和定理。·邏輯演算的發展：甘岑(G.Gentzen)的自然推理系統(NaturalDeductionSystem)，邏輯演算的元理論：公義的獨立性、一致性、完好性等。·各種各種的非經典邏輯的發展：路易斯(Lewis,1883~1964)的模態邏輯，實質蘊涵怪論和嚴格蘊涵、相關邏輯等，盧卡西維茨的多值邏輯等。會合論的發展·對待無量會合的兩種看法：實無量與潛無量·康托爾(G.Cantor,1845~1918)：以實無量的思想為指導，成立了樸實會合論·外延原則（會合由它的元素決定）和歸納原則（每一性質產生一會合）。·可數集和不行數集，確立無量會合的實質在于會合自己能與其子集一一對應。能與正整數會合對應的會合是可數的，不然是不行數的。證了然有理數集是可數的，使用對角線法證了然實數會合是不行數的。·超窮基數和超窮序數·樸實會合論的悖論：羅素悖論·公義會合論的成立：ZFC系統第三次數學危機與邏輯主義、直覺主義與形式主義·會合論的悖論使得人們感覺數學產生了第三次危機，提出了數學的基礎究竟是什么這樣的問題。·羅素等的邏輯主義：數學的基礎是邏輯，倡議全部數學可從邏輯符號推出，《數學原理》一書是他們這一思想的表現。為解決悖論產生了邏輯種類論。·布勞維爾(Brouwer,1881~1966)的直覺主義：數學是心靈的結構，只認可同結構的數學，重申結構的能行性，與計算機科學有重要的聯系。堅持潛無量，重申排中律不可以用于無量會合。海丁(Heyting)的直覺主義邏輯。·希爾伯特(D.Hilbert)的形式主義：公義化方法與形式化方法，元數學和證明論，倡議將邏輯演算和數學證明自己形式化，把用一般的語言傳達的內容上的數學科學變為用數學符號和邏輯符號按必定法例擺列的一堆公式。為了除去悖論，要數學成立在公義化基礎上，將各門數學形式化，構成形式系統，并證明其一致性，這是希爾伯特的數學大綱。數理邏輯的發展早期·哥德爾(Godel,1906~1978)不完好性定理：一個足夠強盛的形式系統，假如是一致的則不是完好的，即有的判斷在此中是不行證的，既不可以判定其為假，也不可以證明其為真。·各種計算模型：哥德爾的遞歸函數理論，邱吉爾的演算，圖靈機模型·這些計算模型是計算機科學的理論基礎，是計算機的理論模型。三、預備知識1.會合的基本看法·會合(set)：會合是數學中最基本的看法之一，不可以以更簡單的看法來定義(define)，只好給出它的描繪(description)。一些對象的整體就稱為一個會合，這個整體的每個對象稱為該會合的一個元素(member或element)。·用大寫字母A,B,C等表示會合，用小寫字母a,b,c等表示會合的元素aA表示：a是會合A的元素，或說a屬于會合AaA表示：a不是會合A的元素，或說a不屬于會合A會合中的元素是無序的，不重復的。往常使用兩種方法來給出一個會合：·列元素法：列出某會合的全部元素，如：·A={0,1,2,3,4,5,6,7,8,9}表示全部小于10的自然數所構成的會合·B={a,b,,z}表示全部小寫英文字母所構成的會合·性質歸納法：使用某個性質來歸納會合中的元素，如：A={n|n是小于10的自然數}C={n|n是質數}表示全部質數所構成的會合·會合由它的元素所決定，換句話說，兩個會合A和B相等，記為A=B，假如A和B擁有相同的元素，即a屬于會合A當且僅當a屬于會合B。·子集(subset)：說會合A是會合B的子集，記為AB，假如a屬于會合A則a也屬于會合B。所以A=B當且僅當AB且BA。說會合A是會合B的真子集(propersubset)，假如AB且A不等于B(AB)。·空集(emptyset)：商定存在一個沒有任何元素的會合，稱為空集，記為，有時也用{}來表示。按子集的定義，空集是任何會合的子集(為何？)。·冪集(powerset)：會合A的冪集，記為P(A)，是A的全部子集所構成的會合，即：·P(A)={B|BA}·比如，A={0,1}，則P(A)={{},{0},{1},{0,1}}·明顯，對任意會合A，有P(A)和AP(A)·補集(complementset)：會合A的補集，記為A，是那些不屬于會合A的元素所構成的會合，即A={x|xA}。往常來說，是在存在一個全集U的狀況下議論會合的補集。全集U是所議論的問題域中全部元素所構成的會合。·會合的并(union)：會合A和B的并AB定義為：AB={x|xA或許xB}，會合的并可推行到多個集合，設A1,A2,,An都是會合，它們的并定義為：A1AAn={x|存在某個i，使得xA}2i·會合的交(intersection)：會合A和B的并AB定義為：AB={x|xA并且xB}，會合的交也可推行到多個會合，設A1,A2,,An都是會合，它們的交定義為：A1AAn={x|對全部的i，都有xA}2i·會合的差(difference)：會合A和B的差AB定義為：AB={x|xA并且xB}。關系和函數的基本看法·有序對(orderedpair)：設A和B是兩個會合，aA,bB是兩個元素，a和b的有序對，記為<a,b>，定義為會合{{a},{a,b}}。·設<a,b>和<a,b>是兩個有序對，能夠證明<a,b>=<a,b>當且僅當a=a且b=b。(如何證？)112211221212·有序對可推行到n個元素，設A,A,,A是會合，a1A,aA,a,nA是元素，定義有序n元12n122n組(orderedn-tuple)<a1,a2,,an>為<<a1,a2,a,n-1>,an>，注意這是一個歸納(inductive)定義，將有序n元組的定義歸納為有序n-1元組的定義。·明顯有<a,a,a,>=<b,b,b,>當且僅當a=b且a=b且且a=b。12n12n1122nn·會合的笛卡爾積(cartesianproduct)：兩個會合A和B的笛卡爾積AB定義為：AB={<a,b>|aA且bB}·比如，設A={a,b,c}，B={1,2}，則：AB={<a,1>,<a,2>,<b,1>,<b,2>,<c,1>,<c,2>}·笛卡爾積可推行到多個會合的狀況，會合A1,A2,,An的笛卡爾積定義為：爾積關系

A1A2An={<a1,a2,a,n>|a1A1且a2A2且且anAn}·會合之間的關系(relation)：定義n個會合A1,A2,,An之間的一個n元關系R為會合A1,A2,,An的笛卡A1A2An的一個子集。設<a1,a2,a,n>A1A2An，若<a1,a2,a,n>R，則稱a1,a2,a,n間擁有R，不然稱它們不具相關系R。特別地：·當A1=A2==A=A時，稱R為A上的n元關系。n·當n=2時，有RA1A2，稱R為A1與A2間的一個二元關系(binaryrelation)。這時若<a,a>R則12簡記為a1Ra2，不然（即<a1,a2>R）記為a1Ra2。往常研究得最多的是二元關系，n元關系的很多性質可從二元關系的性質擴大而獲得。假如沒有特別指明的話，說R是一個關系則是指R是一個二元關系。·當n=1時，這時可認為R是會合A上知足某種性質的子集。·關系的一些性質：設R是A上的二元關系：·說R是自反的(reflexive)，假如對任意的aA有aRa。·說R是反自反的(irreflexive)，假如對任意的aA有aRa。·說R是對稱的(symmetric)，假如對任意的a,bA有若aRb則bRa。·說R是反對稱的(antisymmetric)，假如對任意的a,bA有若aRb且bRa則a=b。·說R是傳達的(transitive)，假如對任意的a,b,cA有若aRb且bRc則aRc。·說R是等價關系(equivalence)，假如R是自反的、對稱的和傳達的。·會合之間的函數(function，或說映照mapping)：定義會合A到B的函數f是A和B的笛卡爾積AB的一個子集，且知足若<x,y>f及<x,z>f則y=z。所以函數是A和B之間的一個特別的二元關系。往常記會合A到B的函數f為f:AB。·函數f:AB的定義域(domain)dom(f)定義為：dom(f)={x|存在某個yB使得<x,y>f}·函數f:AB的值域(range)ran(f)定義為：ran(f)={y|存在某個xA使得<x,y>f}·若<x,y>f，往常記y為f(x)，并稱y為x在函數f下的像(image)，x為y在函數f下的原像。·函數也可推行到n元的情況：f:A1A2AnB，意味著：·f是A1A2AnB的一個子集，且·<x1,x2,x,n,y>f且<x1,x2,x,n,z>f則y=z。·函數的一些性質：設f:AB是會合A到B的函數：·說f是全函數(totalfunction)，若dom(f)=A，不然稱f是偏函數(partialfunction)。下邊假如沒有特別指明的話，都是指全函數。·說f是滿射(surjection,或說fmapsAontoB)，假如ran(f)=B，即對任意的yB都有原像。·說f是單射(injection，或說fisone-one)，假如有f(x)=f(x)則x=x，即對任意的yB，假如它有原1212像的話，則有獨一的原像。·說f是雙射(bijection，或說f是一一對應)，假如f既是滿射，又是單射，即對任意的yB，都有獨一的原像，相同依據全函數的定義，對于任意xA都有獨一的像。這時能夠定義f的逆函數(inversefunction)，記為f-1:BA，f-1(y)=x當且僅當f(x)=y。明顯f-1也是雙射。·會合的基數(cardinalnumber)或說勢：會合A的基數記為|A|，且有：·對于有限會合A，令A的基數為A中元素的個數。·定義無窮會合，不直接定義基數，而是經過定義兩個會合之間的等勢關系來刻劃會合的基數或勢，說會合A和會合B是等勢的(equipotent)，假如存在一個從A到B的雙射。依據雙射的性質，能夠證明等勢是會合上的一個等價關系。·稱與自然數集等勢的會合為可列集(enumerable)，有限集和可列集統稱為可數集(countable)。·設A和B是有限會合，有|P(A)|=2|A|，|AB|=|A||B|。小結·下邊以樹的形式給出了以上主要看法之間的關系：會合子集冪集

會合的補、并、交、差

有序對笛卡爾積關系關系的自反、對稱、傳達性

函數單射、滿射、雙射歸納定義和歸納證明·一個會合的歸納定義(inductivedefinition)往常分為三步：·歸納基：一些基本的元素屬于該會合；·歸納步：定義一些規則（或許說操作），從該會合中已有的元向來生成該會合的新的元素；·最小化：該會合中的全部元素都是經過基本元素以及所定義的規則生成的，換句話說，該會合是由基本元素及規則所生成的最小的會合。·自然數集N的歸納定義：歸納基：0是一個自然數，即0N。[2].歸納步：若n是自然數，則n的后繼也是自然數。記n的后繼為succ(n)，即若nN，則succ(n)N。為方便起見，后邊也記n的后繼為n+1。[3].最小化：全部的自然都經過步驟[1]和[2]獲得，或許說自然數集是經過步驟[1]和[2]獲得的最小會合。·這類定義方式可推行到對其余一些看法的定義，比如上述多個會合的并、交、笛卡爾積以及多個元素的有序n元組都可經過遞歸的方式定義。比如，對于多個會合的并可定義為：·歸納基：A1A2={x|xA1或許xA2}·歸納步：A1AAn=(A1AAn-1)An22·這里不需要最小化，因為這里不是定義會合。·數學歸納法：對于自然數的很多性質都可經過數學歸納法來證明，對于性質R，假如它對0成立，并且如果對于n成立的話，能夠獲得它對于n+1也成立，那么性質R對全部的自然數成立。這類證明方法的正確性本身可經過自然數的歸納定義來獲得證明：·定義會合S={nN|性質R對n成立}·歸納基：依據上邊的定義有0S·歸納步：依據上邊的定義有假如nS，則n+1S，所以S是知足上邊自然數集的歸納定義中的1、2點的一個會合，而自然數集N是知足這兩點的最小會合，所以有NS，而明顯有SN，所以S=N。·數學歸納法舉例：使用數學歸納法證明1+2+n+=(n*(n+1))/2·歸納基：當n=0時明顯成立。·歸納步：假如對于n成立，則有1+2+n+=(n*(n+1))/2（這稱為歸納假定），此刻要證對于n+1也成立。明顯有：1+2+n++(n+1)=(n*(n+1))/2+(n+1)//依據歸納假定=(n*(n+1)+2*(n+1))/2=((n+1)*((n+1)+1))/2所以要證的公式對于n+1成立，所以對于全部的自然數成立。·明顯在數學歸納法中，對于歸納基改為R對于自然數k成立，歸納步不變的話，則可證明R對于全部大于k的自然數都成立。·在數學歸納法中，也可將歸納步改為假如R對于全部小于n的自然數成立，則推出R對于n也成立，即歸納步是假定對于全部小于n的自然數性質R成立來導出性質R對于自然數n成立。這類形式的數學歸納法通常稱為第二數學歸納法。形式系統·形式系統的定義：一個形式系統S由以下4個會合構成：·一個非空會合S，稱為形式系統S的字母表或說符號(Symbol)表；·一個由S中字母的有限序列（字符串）所構成的會合FS，稱為形式系統S的公式(Formula)集；·從FS中選用一個子集A，稱為形式系統S的公義(Axiom)集；S·F上有一個部分函數集R={R|R:FSFSFSF,n=1,2,}稱為形式系統，S的規則(Rule)SSnnS集，此中Rn:FSFSFSFS是n元的部分函數，我們稱其為n元規則。統

·形式系統中的定理(Theorem)：·歸納基：tAS是形式系統S中的定理。·歸納步：t1,t2,t,n是形式系統S中的定理，而Rn是S中的規則，那么S中的定理。·對于形式系統中的規則Rn:FSFSFSFS，往常表示成下邊的形式：t1,t2,t,nRn(t1,t2,t,n)

Rn(t1,t2,

t,n)也是形式系·形式系統擁有兩個特色：·形式化其實是一個可機械實現的過程，在它里面，符號、規則和演算等被表示得嚴實、精準。在形式系統S中，只好使用字母表S中的符號，只認可公式集FS中的符號串的合理性，只好由公義集，依據規則推出存心義的東西來。·形式系一致旦達成，就成了符號串及依據規則進行的符號串的改寫，系統與一確實質意義就絕不相關，或許說已經經過這類符號，從實質問題中抽象出了我們所需要研究的內容。在形式系統內部，所能認識的只好是符號串及其改寫，只好在形式系統外對這類符號串及規則給予意義。·對象語言(Objectlanguage)與元語言(Metalanguage)：·數理邏輯所研究的是“數學推理”，而使用的方法也是數學推理，所以有必需區分這兩個層次的推理。·把作為研究對象的“推理”形式化，使用形式語言來表示作為研究對象的“推理”的前提、結論和規則等，這類形式語言是我們所研究的對象語言。·另一方面，對于形式系統的性質、規律的表達和作為研究方面的推理方式使用另一種語言來表達，這個語言稱為研究的元語言，往常使用多半學化的自然語言。·形式語言的語法(Syntax)與語義(Semantic)：·形式語言的語法是構成形式系統的公式集、公義集和規則集的法例。·形式語言的語義是對于形式系統的解說和意思。·形式語言自己沒有含義，但我們在結構它們時是設想它們能代表某種意義的，特其余當我們在選擇形式系統的公義時，老是選擇所研究的問題域中那些最為明顯或最簡單公認為正確的性質。習題1.令會合A={n|n10且n是奇數}，B={n|n10且n是素數}，請回答以下問題：請用列元素的方法列出會合A和會合B，請問會合B是不是會合A的子集？b)請計算AB、AB、AB、AB以及P(A)(即A的冪集)。設關系R={<a,b>|a和b是互質的自然數}，請問R是自反的嗎？對稱的嗎？傳達的嗎？為何？3.設f:AB是函數，R是價關系。

A上的以下二元關系：R={<a,b>|a,bA,f(a)=f(b)}，證明R是A上的一個等使用數學歸納法證明：12+22+32++n2=(n*(n+1)*(2n+1))/65.設有函數f:NNN，f(n)=<n,n+1>，請問f是不是單射、滿射或雙射？*6.設R1和R2都是A上的等價關系，請問R1R2和R1R2能否仍是A上的等價關系？假如是請證明，不然請舉一反例。*7.設R是會合A上的等價關系，aA，可定義：a)[a]={bA|aRb}，稱[a]為a對于R的等價類；A/R={[a]|aA}，稱A對于R的商集。*8

設函數f:AA/R定義為對任意aA有f(a)=[a]，請問R知足如何的條件時f是單射？請給出<x,y,z>的會合方式的定義。若定義：[x,y,z]={{x},{x,y},{x,y,z}}，則假如有[x1,y1,z1]=[x2,y2,z2]能否意味著有x1=x2且y1=y2且z1=z2？第二講數理邏輯一、命題邏輯(PropositionalLogic)內容概括·簡單命題與復合命題：什么是命題？命題聯絡詞及其含義。·命題公式與賦值：命題邏輯公式的歸納定義，命題公式的真值表。·等值演算：命題公式的等值賦值，重要的等值式。·命題聯絡詞的齊備集：經過等值演算獲得命題聯絡詞的齊備集和極小齊備集。·命題公式的范式：析取范式與合取范式。·命題演算系統：使用命題邏輯公式進行推理的形式系統。·命題演算系統的語義與命題演算系統的元性質：注意差別形式系統的語法和語義。簡單命題與復合命題·命題(proposition)：經典命題邏輯中，稱能判斷真假但不可以既真又假的陳說句為命題。·命題對于命題邏輯來說是一個原始的看法，不可以在命題邏輯的范圍內給出它的精準定義，只好描繪它的性質。·命題一定為陳說句，不可認為疑問句、祈使句、嘆息句等，比以下述句子為命題：1.3是有理數2.8小于103.2是素數4.烏鴉是黑色的以下句子不是命題：1.這個小男孩多英勇啊！2.烏鴉是黑色的嗎？3.希望中國隊能取勝。4.請把門開一開！以下句子不行能判斷其為真或為假，所以也不是命題：1.x+y>102.我正在說謊·命題一定擁有真假值，從某種意義上來說，疑問句、祈使句、嘆息句沒有真假之分。但能判斷真假，其實不意味著此刻就能確立其是真仍是假，只需它擁有能夠獨一確立的真假值即可，比以下述陳說句是命題：1.明年的中秋節的夜晚是晴日3.21世紀末，人類將居住在太空

2.地球外的星球上存在生物4.哥德巴赫猜想是正確的·經典命題邏輯不區分此刻已確立為真，仍是未來可能確立為真這類狀況，辦理與時間相關的真值問題是時態邏輯的任務。經典命題邏輯也不區分是在技術上能夠確立為真，仍是此刻的技術條件下不可以夠確立為真的這類狀況，只認可在技術上，或許說能給出某種方法確立為真的那些東西才為真是直覺邏輯的看法。·真命題和假命題：命題是為真或為假的陳說句，稱這類真假的結果為命題的真值。如果命題的真值為真，則稱為真命題，不然稱為假命題。·命題常量與命題變量：使用符號來表示命題，往常用p,q或帶下標來表示命題常量或者變量。假如命題符號p代表命題常量則意味它是某個詳細命題的符號化，假如p代表命題變量則意味著它可指代任何詳細命題。假如沒有特別指明，往常來說命題符號p等是命題變量，即可指代任何命題。·簡單命題與復合命題：不可以分紅更簡單的陳說句的命題為簡單命題或原子命題，不然稱為復合命題，復合命題使用命題聯絡詞聯絡簡單命題而獲得。·復合命題的聯絡詞往常包含：·設p是任意命題，復合命題“非p”稱為p的否認（非），記為p。·設p和q是任意命題，復合命題“p且q”稱為p和q的合取（與），記為pq。·設p和q是任意命題，復合命題“p或q”稱為p和q的析取（或），記為pq。·設p和q是任意命題，復合命題“假如p則q”稱為p蘊涵q，記為pq。·設p和q是任意命題，復合命題“p當且僅當q”稱為p與q等價，記為pq。·上述定義中的非(negation)、合取(conjunction)、析取(disjunction)、蘊涵(implication)和等價(equivalence)是在命題邏輯中的術語，而引號中給出的復合命題是自然語言中的典型用法。自然，命題邏輯中符號化形式的復合命題在自然語言中有許很多多的表達方法，這也是為何自然語言有歧義的原由，參賜教材中的各例題，并注意以下幾點：·pq的邏輯關系是pq為真當且僅當p和q中起碼有一個為真。但自然語言中的“或”既可能擁有相容性，也可能擁有排擠性。命題邏輯中采納了“或”的相容性。·pq的邏輯關系是pq為假當且僅當p為真，而q為假，稱p為蘊涵式的前件，q為蘊涵式的后件。現實世界中的“假如則”與這類蘊涵有比較大的差別。簡單命題邏輯中的這類蘊涵經常稱為“實質蘊涵”，相對應地有“嚴格蘊涵（p嚴格蘊涵q，意味著p為真，則q不行能為假）”、“相關蘊涵”等。實質蘊涵意味著可從假的前提推出任何命題來，或兩個不沒有內在聯系的命題之間存在蘊涵關系。·將平時生活中的陳說句符號化為命題邏輯中的公式是在此后的程序編寫等課程中應用數理邏輯知識的重要基礎。但就數理邏輯這門課程自己而言，我們只關懷公式之間的真值關系，而不關懷公式所詳細指代的命題。·復合命題與簡單命題之間的真值關系可用下表給出，此中0代表假，1代表真：pqppqpqpqpq0010011011011010001001101111命題邏輯公式【定義1.1】命題邏輯公式(propositionallogicformula)由以下子句歸納定義：歸納基：命題常量或命題變量是命題邏輯公式，稱為命題邏輯公式的原子項。[2].歸納步：假如A,B是邏輯公式，則(A)、(AB)、(AB)、(AB)和(AB)也是命題邏輯公式。[3].最小化：全部的命題邏輯公式都經過1和2獲得。□在這里我們隱含地使用的字母表是大小寫的英文字母、命題聯絡符和園括號。英文字母還可帶下標。其余的符號都不屬于我們的符號表，即在命題邏輯公式中不可以出現這些符號。后邊我們將命題邏輯公式簡稱為命題公式，或在沒有二義的狀況下進一步簡稱為公式。【例子1.1】((pq)((p)(qr)))是命題公式，它經過以下步驟生成：1.p是公式；//依據定義1.1的[1]2.q是公式；//依據定義1.1的[1]3.(pq)是公式；//依據定義1.1的[2]4.(p)是公式；//依據定義1.1的[2]5.r是公式；//依據定義1.1的[1]6.(qr)是公式；//依據定義1.1的[2]7.((p)(qr))是公式；//依據定義1.1的[2]，以及4,68.((pq)((p)(qr)))是公式。//依據定義1.1的[2]，以及3,7這類生成過程，能夠形象地用下邊的一棵樹來表示：((p

q)

((p)

(q

r)))(p

q)

((p)

(q

r))p

q

(p)

(q

r)p

q

r這類樹在形式語言與自動機中就稱為語法剖析樹。【反例1.2】·依據定義1.1，p·依據定義1.1，(p聯絡符都會對應一對園括號。·明顯(pqr)、(q

q不是公式，因為兩邊沒有園括號qr)不是公式，實質上，由定義(rp)等都不是公式。

1.1生成的公式，每個命題【定理1.2】設R是某個性質，假如有：[1].對于全部的原子項p，都知足性質R；[2].假如對任意的公式A和B都知足性質R，就有(A)、(AB)、(AB)、(AB)和(AB)也知足性質R。那么，全部的公式A就都知足性質R。□該定理的證明近似數學歸納法的證明，很簡單依據定義1.1獲得。【定義1.3】命題公式A的復雜程度deg(A)定義為：[1].假如A是原子項，則deg(A)=0；[2].deg(A)=deg(A)+1;[3].deg(A*B)=max(deg(A),deg(B))+1，此中*代表、、、之一。□此定義等價于教材p11的定義1.7。只可是我們在這里給出的是遞歸定義。使用歸納法，我們可證明下邊定理：【定理1.4】deg(A)小于等于命題公式A中的命題聯絡符號的數目。【證明】依據命題公式A的結構進行歸納證明：1.歸納基：假如A是原子項，則依據定義

1.3有deg(A)=0，明顯定理成立。歸納步：假定定理對于命題公式A和B成立（歸納假定），記命題公式A中的命題聯絡符號數為Sym(A)，即有deg(A)Sym(A)和deg(B)Sym(B)。那么因為deg(A)=deg(A)+1，而Sym(A)=Sym(A)+1，所以定理對于A也成立。相同因為deg(A*B)=max(deg(A),deg(B))+1，而Sym(A*B)=Sym(A)+Sym(B)+1，因此有deg(A*B)Sym(A*B)，進而定理對全部的命題公式都成立。□【定理1.5】任意命題邏輯公式A中出現相等數目的左右園括號，實質上，左右園括號的個數都等于A中的命題聯絡符號數。□【定理1.6】任意命題邏輯公式A擁有以下6種形式之一，且只擁有此中一種形式：[1].A為原子項；[2].(A)[3].(AB)[4].(AB)[5].(AB)[6].(AB)□定理1.6確實切含義包含以下幾點：1.任意命題公式必定擁有上述6中形式之一；2.這6中形式都互不相同；3.假如(A)與(A1)相同，則必有A與A1相同；4.假如(A*B)與(A1*B)相同，則必有A與A相同，且B與B相同。111依據定理1.5和定理1.6，我們不難理解例子1.1是如何獲得該此中命題公式的語法剖析樹的。實質上每個命題公式的最左側都是左園括號，假如從第二個符號不是左園括號，那么這個公式只有一個命題聯絡符。不然找與第二個左園括號配對的右園括號，進而將命題公式區分為這樣的形式：(()*(，))假如本來的命題公式為根的話，那么左右兩邊的兩個命題公式分別為它的左右子樹了，并且對這兩個公式可作近似的剖析，最后到原子項。在后邊，為了書寫方便起見，我們省略最外邊的括號，并規定各個命題聯絡符的優先級別為大于，大于，大于，大于，進而可省略命題公式中一些不用要的園括號，比如例子1.1中的公式可寫為：pqpqr。可是在后邊我們書寫公式的原則是盡量簡易，但又能讓讀者簡單理解。而相關命題公式的性質的議論，則只針對可由上邊定義所能生成的公式形式。

1.1上邊議論的命題公式的語法結構，下邊議論命題公式的賦值。【定義1.7】對命題公式的一次真值賦值t是從全部命題變量所構成的會合到會合{0,1}的函數。實質上，對于某個命題公式A來說，我們只關懷t在A中的命題變量上的值。這里我們假定存在一個全部命題變量所構成的會合U，或許說我們全部命題公式中的變量都取之于會合U，我們記命題公式A中的全部命題變量所構成的會合為Var(A)。設有一個真值賦值t:U{0,1}，而對于命題公式A的真值賦值來說，我們只關懷t在Var(A)上的值。【例子1.3】對于命題公式A=((pq)((p)(qr)))，有：Var(A)={p,q,r}這里不如假定U=Var(A)，真值賦值就是一個函數t:{p,q,r}{0,1}，比如可令：t(p)=0,t(q)=1,t(r)=0【定義1.8】命題公式A在真值賦值t:U{0,1}下的真值t(A)遞歸定義以下：[1].假如命題公式A是一個命題常量p，則假如p為真，t(A)=1，不然t(A)=0；[2].假如命題公式A是一個命題變量p，則t(A)=t(p)[3].若t(A)=0則t(A)=1，不然t(A)=0。[4].若t(A)=t(B)=1，則t(AB)=1，不然t(AB)=0。[5].若t(A)=t(B)=0，則t(AB)=0，不然t(AB)=1。[6].若t(A)=0或許t(B)=1，則t(AB)=1，不然t(AB)=0。[7].若t(A)=t(B)，則t(AB)=1，不然t(AB)=0。【例子1.3，續】對于命題公式A=((pq)((p)(qr)))，及真值賦值函數t：t(p)=0,t(q)=1,t(r)=0有：1.t(p)=0,t(q)=1;2.t(pq)=1;//依據定義1.8的[5]4.t(p)=1;//依據定義1.8的[3]5.t(r)=0;6.t(qr)=0;//依據定義1.8的[4]7.t((p)(qr))=0;//依據定義1.8的[7]8.t((pq)((p)(qr)))=0;//依據定義1.8的[6]所以命題公式A在上述真值賦值下的真值t(A)是0。不難看出，定義1.8與上一節中給出的復合命題與簡單命題之間的真值關系表是一致的。并且從上邊的例子與例1.1的比較也可看出，對于命題公式的真值，可依據該命題公式的生成步驟來獲得。命題公式的真值只與命題公式中所出現的命題變量的真值賦值相關，假如命題公式中含有n個命題變量，則對這些命題變量的真值賦值共有2n種不同狀況，可經過一個表，列出在這全部狀況下命題公式的真值，這類表稱為該命題公式的真值表，比如上述命題公式的真值表為：

Ap

q

r

(pq)

(p)

(qr)

((p)

(qr))

((pq)

((p)

(qr)))0

00

0

1

0

0

10

01

0

1

0

0

1010110000111111110010011101100111101001111110100【定義1.9】假如命題公式A在任意的真值賦值函數t:U{0,1}下的真值t(A)都為1,則稱命題公式A為永真式(tautology)（或稱重言式）；假如命題共A在任意的真值賦值函數下的真值都為0，則稱A為矛盾式(contradiction)；假如A不是矛盾式，則稱為可知足式。【例子1.4】依據命題公式A=((pq)((p)(qr)))的真值表，我們知該命題公式是可知足式，但不是永真式。而公式B=((p(qp))r)是永真式，其真值表為：pqr(qp)(p(qp))((p(qp))r)000011001011010111011111100111101111110111111111而公式((((pq))q)r)（教材14頁簡寫為(pq)qr）是矛盾式，其真值表為：pqr(pq)((pq))(((pq))q)((((pq))q)r)00010000011000010100001110001000100101010011010001111000【定義1.10】我們使用符號來表示一組命題公式所構成的會合。定義在真值賦值函數t:U{0,1}下的真值t()為：t()=1當且僅當對中任意公式A有t(A)=1，不然定義t()=0(注意只需中存在某個公式A使得t(A)=0，就有t()=0)。說是可知足的，假如存在某個真值賦值函數t使得t()=1，這時稱t知足。【定義1.11】設是一組命題公式的會合，說命題公式A是認為前提的永真式，假如知足對任意知足的真值賦值函數t都有t(A)=1，這時我們記為╞A。注意在定義1.11中，假如為空集，則╞A表示A為永真式，因為對于空集來說，明顯任意的真值賦值函數t都知足它（因為中沒有命題公式），進而╞A意味著對任意的真值賦值函數t都有t(A)=1，即A為永真式。4.等值演算【定義1.12】當={A1,A2,,An}時，我們也記╞A為A1,A2,,An╞A。假如有A╞B且B╞A，則稱命題公式A與B等值，記為AB。實質上公式A與B等值記為A╞╡B會更正確些，但教材采納了符號AB，為了不會過于混雜，我們也使用這類記號。實質上，依據定義1.11，AB就意味著對任意的真值賦值函數t有t(A)=1當且僅當t(B)=1，也就是說對任意的t有t(A)=t(B)。進而定義1.12與教材中對于命題公式等值的定義是等價的，即有下述定理：【定理1.13】AB當且僅當A

B是永真式。

□使用真值表，不難證明下邊的定理：【定理1.14】設A,B,C是任意的命題公式，有：兩重否認律：A((A))[2].等冪律：A(AA)A(AA)[3].互換律：(AB)(BA)(AB)(BA)[4].聯合律：((AB)B)(A(BB))((AB)B)(A(BB))[5].分派律：(A(BC))((AB)(AC))(A(BC))((AB)(AC))[6].德摩根律：((AB))((A)(B))((AB))((A)(B))[7].汲取律：(A(AB))A(A(AB))A[8].零律：(A1)1(A0)0[9].同一律：(A0)A(A1)A[10].排中律：(A(A))1[11].矛盾律：(A(A))0蘊涵等值式：(AB)((A)B)等價等值式：(AB)((AB)(BA))[14].假言易位：(AB)((B)(A))[15].等價否認等值式：(AB)((A)(B))[16].歸謬論：((AB)(A(B)))(A)□要注意的是，上述定理中的0代表真值為0的任意命題常量，而1代表真值為1的任意命題常量。因為命題聯絡符號和都知足聯合律，所以我們可有以下的簡寫：A1A2An依據以上簡寫，我們可推行定理1.13為以下定理1.15：【定理1.15】[1].A1,A2,,An╞A當且僅當╞((A1A2An)A)。[2].A1,A2,,An╞A當且僅當╞((A1(A2((AnA)))。□【引理1.16】設有AA'和BB'，則有：[1].(A)(A')[2].(AB)(A'B')[3].(AB)(A'B')[4].(AB)(A'B')[5].(AB)(A'B')□依據引理1.16，不難證明下邊的置換規則：【定理1.17】設有BC，而A'是命題公式A經過使用C替代A中出現的某些B（不需假如替代全部的B）而獲得的命題公式，則有AA'。【證明】對命題公式A的結構進行歸納。第一假如B=A，則有C=A'，進而有AA'。歸納基：假如A是命題變量和命題常量，那么必有B=A，所以定理成立。歸納步：依據定理1.6，命題公式A必為以下5種形式之一：A1,A1A,A1A,22A1A2,A1A2。設A的形式為A1，假如B=A則定理成立，不然必有B出現A1中，將A1中的B用C替代后獲得的為A1'，按歸納假定有A=A'，再依據引理1.15有A=A'。1111定理成立。若A的形式為A1*A2，則假如B=A則定理成立，不然必有B出此刻A1或A2中，或同時出此刻這二者中。設將A1中的B用C替代后獲得的為A1'，而將A2中的B用C替代后獲得的為A2'，按歸納假定有A1A1'和A2A2'，再依據引理1.15有A1*A2A1*A2，即定理成立。□【定義1.18】假如命題公式A中只出現命題變量、命題常量、命題聯絡符號、和則稱為限制性（命題）公式。定義：[1].對于限制性公式A，將此中的命題聯絡符號換成，命題聯絡符號換成得到的公式稱為A的對偶公式(dualformula)，記為Aop。[2].對于限制性公式A，將此中出現的全部原子項（命題變量或命題常量）p換成p獲得的公式稱為A的內否式，記為A。【例子1.5】設公式A=((pq)(r))，則：(1).A的對偶式Aop=((pq)(r))(2).A的內否式A=(((p)(q))r)【引理1.19】設公式A、B都是限制性公式，有：[1].(Aop)opA(A)A[2].(AB)opAopBop(AB)AB[3].(AB)opAopBop(AB)AB[4].(Aop)(A)op□引理1.19中的(恒等號)表示兩邊的公式在（語法）形式上完好相同，比如(Aop)opA表示對A的對偶公式Aop再做一次對偶操作獲得的就是A自己。而(Aop)(A)op表示對A做一次對偶操作獲得Aop，而后再求Aop的內否式，獲得的公式與先求A的內否式，而后再做對偶操作獲得的公式完好相同，用代數學的術語來說，就是這兩種操作可互換。引理1.19很簡單依據定義1.18證明，也可直觀理解引理1.19所代表的含義。讀者可通過對一些公式求它的對偶式和內否式來考證引理1.19的每個恒等式，比如：【例子1.5，續】設公式A=((pq)(r))，則：(1).Aop=((pq)(r)),(Aop)=(((p)(q))r)(2).A=(((p)(q))r),(A)op=(((p)(q))r)明顯有(Aop)(A)op。【定理1.20】設公式A是任意的限制性公式，有：[1].(A)op(Aop)(A)(A)[2].(Aop)A【證明】略□【推論1.21】設公式A和B都是限制性公式，有AB則(Aop)(Bop)【證明】依據引理1.16及(A)A不難獲得AB當且僅當AB。則：(Aop)AB(Bop)□在定理1.14中已經看到了推論1.21的很多旁證，比如對于汲取律(A(AB))A，其中(A(AB))的對偶公式是(A(AB))，進而有(A(AB))A，這與第二個吸收律公式(A(AB))A是相同的，因為A、B代表任意命題公式。【例子1.6】考證以下等值式(1).((pq)r)((qp)r)(2).(p(qr))((pq)r)(3).((pq)r)((pr)(qr))(4).((pq)r)((pr)(qr))(5).(p(qr))((pq)(pr))(6).(p(qr))((pq)(pr))【證明】證明的思路有兩種，第一種思路是經過列真值表，可看到上述等值式的兩邊在任何真值賦值下都有相同的真值，進而達成上述等值式的考證。讀者不如自己依照這類思路進行證明。第二種思路是利用定理1.14中的基本等值式來證明。能夠看到上述等值式主假如對于蘊涵的等值式，證明對于蘊涵的等值式的方法是利用定理1.14中的[12]將蘊涵化成只出現與、或、非的公式，再來考證它們的相等。(1).((pq)r)((pq)r)//定理1.14中的[12]：蘊涵等值式((pq))r//定理1.14中的[12]：蘊涵等值式(p(q))r//德摩爾根律((qp)r)//的互換律(2).(p(qr))(p(qr))//蘊涵等值式(p(qr))//蘊涵等值式((pq)r)//的聯合律((pq)r)//德摩爾根律，反向運用((pq)r)//蘊涵等值式，反向運用(3).((pq)r)((pq)r)//蘊涵等值式((pq)r)//德摩爾根律((pr)(qr))//分派律與互換律((pr)(qr))//蘊涵等值式(5).(p(qr))(p)(qr)//蘊涵等值式(p)(p)(qr)//的冪等律(pq)(pr)//的互換律和聯合律(pq)(pr)//蘊涵等值式(4)(6)留作練習□【例子1.7】德摩爾根律的推行：(1).(A1A2An)(A1)(A2)(An)(2).(A1A2A)(A)(A)(A)n12n【證明】對n實行數學歸納法，或直接從定理1.20[2]獲得。□聯絡詞的完好集【定義1.22】{0,1}上的n元函數f:{0,1}n{0,1}就稱為一個n元真值函數。聯絡詞實質上一個一元真值函數：f(0)=1,f(1)=0而聯絡詞、、和則都是二元真值函數：f(0,0)=0,f(0,1)=0,f(1,0)=0,f(1,1)=1f(0,0)=0,f(0,1)=1,f(1,0)=1,f(1,1)=1f(0,0)=1,f(0,1)=1,f(1,0)=0,f(1,1)=1f(0,0)=1,f(0,1)=0,f(1,0)=0,f(1,1)=1反過來，一個真值函數便可當作一個真值聯絡詞。設f:{0,1}n{0,1}是一個n元真值函數，則可以下定義一個n元真值聯絡詞Nf:對于n個命題變元p1,p2,p,n，命題公式Nf(p1,p2,p,n)在真值賦值函數<t1,t2,t,n>下的真值為f(t12,n,tt,)。明顯互不相同的n元真值函數的個數為2n，所以可定義2n個n元真值聯絡詞，比如122元真值函數有四個：f1:00,10f:00,11f:01,10f:01,11234而2元真值函數有16個，可定義16個真值聯絡詞，而我們常用的只可是是此中的4個。此刻的問題是，能否全部的真值函數都可使用常用的這5個真值聯絡詞來表示呢？【定義1.23】設是聯絡詞的一個會合，稱為聯絡詞的一個完好集，假如任意真值函數f都可用僅含中聯絡詞的命題公式A來表示，即對A中命題變元的任意一個真值賦值<t1,t2,t,n>，A在<t1,t2,t,n>下的真值為f(t1,t2,t,n)。【定理1.24】{,,,}是聯絡詞的一個完好集。【證明】依據定義1.23只需證明對任意n元真值函數都可由只含、、和的n元命題公式來表示即可。對真值函數的元數n進行歸納證明。歸納基：當n=1時，一元真值函數只有4個，可分別用p(p)、p、p和p(p)來表示，所以定理成立。歸納步：假定當n=k時定理成立，要證n=k+1定理也成立。設f(x,x,x,,xk+1)是12k一個k+1元真值函數，定義以下兩個k元真值函數：f1(x12k12x,k,0)f2(x12,k12k,x,x,)=f(x,x,,xx,)=f(x,x,x,,1)由歸納假定知f1和f2都可由只含、、和的k元命題公式來表示，設它們分別可由A1和A2表示，且假定A1和A2中的k個命題變元為p1,p2,,pk。此刻我們證f可由A=((pk+1)A1)(pk+1A2)表示，此中pk+1是不同于p1,p2,p,k的一個命題變元。即要證對命題變元p12kk+1的一個真值賦值12,kk+112kk+1)。,p,p,,p<t,tt,,t>時，A的真值是f(t,t,t,,t當tk+1=0時，即p被賦值為0，這時((pk+1)A)與A等值，而(pA2)的真值為1，所k+111k+1以A與A1等值，而按歸納假定有A1的真值為f1(t12k12k,t,t,)，即為f(x,x,x,,0)。同理可證當tk+1=1時A的真值是12,k,1)，進而A的真值是f(t12kk+1)。f(x,xx,,t,t,,t□【推論1.25】{,},{,}和{,}都是聯絡詞的完好集。【證明】1.要證{,}是聯絡詞的一個完好集，只需證任一命題公式可與一個只含和的命題公式等值，事實上有：(AB)((A)B)(AB)(((A)(B))){,}是聯絡詞的一個完好集，因為：(AB)(((A)(B)))(AB)((A)B){,}是聯絡詞的一個完好集，因為：(AB)

(((A)(B)))

(A

B)((A)B)事實上，上述每個會合都是極小的完好集，保持是完好集。

即不可以再從會合中去掉任意一個聯絡詞還可以□【定理

1.26】{

,,,

}不是聯絡詞的完好集。【證明】總取0值的真值函數不可以由只含此聯絡詞集中的聯絡詞的命題公式來表達，

因為這樣的命題公式當全部命題變元都真值賦值為1時真值為1，不行能為0。

□命題公式的范式【定義1.27】將命題符號（代表命題變元或命題常量）或命題符號的否認統稱為文字(literal)。僅由有限個文字構成的析取式稱為簡單析取式。僅由有限個文字構成的合取式稱為簡單合取式。【例子1.8】文字、簡單析取式與簡單合取式：p,q等為文字，也是一個文字的簡單析取式和簡單合取式(2)pq,p(q)等為兩個文字的簡單析取式，pq(r)為三個文字的簡單析取式(3)pq,p(q)等為兩個文字的簡單合取式，pq(r)為三個文字的簡單合取式【定理1.28】一個簡單析取式是永真式當且僅當它同時含一個命題符號及其否認，一個簡單合取式是矛盾式當且僅當它同時含一個命題符號及其否認。□【定義1.29】由有限個簡單合取式構成的析取式稱為析取范式(disjunctivenormalform)，由有限個簡單析取式構成的合取式稱為合取范式(conjunctivenormalform)。析取范式和合取范式統稱為范式(normalform)。【例子1.9】析取范式和合取范式：(1)(pq)(pq),(pr)(qrp)(rp)等是析取范式(2)(pq)(pq),(pr)(qrp)(rp)等是合取范式依據定義1.18知，一個析取范式的對偶式是合取范式，一個合取范式的對偶式是析取范式。【定理1.30】一個析取范式是矛盾式當且僅當它的每個簡單合取式都是矛盾式。一個合取范式是永真式當且僅當它的每個簡單析取式都是永真式。【定理1.31】（范式存在定理）任意命題公式都存在與之等值的析取范式與合取范式。求一個公式的范式的步驟以下：[1].利用蘊涵等值式(AB)(AB)和等價等值式(AB)(AB)(AB)除去公式中的聯絡詞和，使得公式中只含有聯絡詞、和。利用兩重否認律AA和德摩爾根律將否認放到命題符號前。[3].利用分派律，求析取范式利用對的分派律，求合取范式則利用對的分派律。【例子1.9】求命題公式的析取范式和合取范式(1).求(pq)(pr)的析取范式和合取范式(2).求(pq)(pr)的析取范式和合取范式【解答】(1)求(pq)(pr)的析取范式：(pq)(pr)(pq)(pr)//蘊涵等值式(pq)(pr)(pp)(pr)(qp)(qr)//兩重否認律和分派律(pr)(qp)(qr)//(pp)是矛盾式明顯(pq)(pr)的合取范式為(pq)(pr)。(2)求(pq)(pr)的合取范式：(pq)(pr)(pq)(pr)(pqp)(pqr)明顯(pq)(pr)的析取范式為(p)q(pr)。注意：一個命題公式的合取范式和析取范式不擁有獨一性。【定義1.32】在含有n個文字的簡單合取式中，若每個命題符號和其否認不同時存在，而二者之一一定出現且只出現一次，且第i個命題變元或許否認出此刻從左側算起的第i個地點上（若命題變元無下標，則按詞典次序擺列），這樣的簡單合取式稱為極小項。極小項是特別的簡單合取式。含n個文字的極小項中，因為每個命題變元以原形或否認出現且僅出現一次，所以n個命題變元共可產生2n個不同的極小項。若在極小項中，將命題變元的原形對應1，否認對應0，則每個極小項獨一地對應一個二進制數，該二進制數的每一位正是使該極小項的真值為1的真值賦值。【例子1.10】兩個命題變元p,q生成的pq對應00，記為m0pq對應10，記為m2由三個命題變元p,q,r生成的8個極小項為：pqr對應000，記為m0pqr對應010，記為m2pqr對應100，記為m4pqr對應110，記為m6

個極小項為：q對應01，記為m1q對應11，記為m2pqr對應001，記為m1pqr對應011，記為m3pqr對應101，記為m5pqr對應111，記為m7【定義1.33】若析取范式中的簡單合取式都是極小項，則稱該析取范式為主析取范式。【定理1.34】任何命題公式存在獨一的主析取范式。求一個公式的主析取范式是：先求該公式的一個析取范式。假如該析取范式的某個簡單合取式A中既不含某個命題變元p，也不含它的否認p，則該簡單合取式變為以下形式：(Ap)(Ap)。[3]除去重復出現的命題變元或命題變元的否認，矛盾式及重復出現的極小項，并將每個極小項的命題變元或其否認按下標次序或詞典次序擺列。【例子1.11】求命題公式的主析取范式(1).求(pq)(pr)的主析取范式(2).求(pq)(pr)的主析取范式【解答】(1)依據例子1.9知(pq)(p

r)的一個析取范式是

(pr)(q

p)(qr)，我們將此中的每個簡單合取式睜開為含有全部命題變元的極小項的析取：(pr)睜開為(pqr)(pqr)(qp)睜開為(pqr)(pqr)(qr)睜開為(pqr)(pqr)所以(pq)(pr)的主析取范式為(pqr)(pqr)(pqr)(pqr)，按極小項所對應的二進制數的大小從頭擺列為(pqr)(pqr)(pqr)(pqr)。(2)依據例子1.9知(pq)(pr)的一個析取范式為(p)q(pr)，將此中每個簡單合取式睜開為含有全部命題變元的極小項的析取：(p)睜開為(pqr)(pqr)(pqr)(pqr)q睜開為(pqr)(pqr)(pqr)(pqr)(pr)睜開為(pqr)(p所以(pq)(pr)的主析取范式為：(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)

qr)主析取范式也可從命題公式的真值表更簡單地獲得，對應地，依據命題公式的主析取范式也可簡單地結構其真值表、判斷其種類（矛盾式、可知足式仍是永真式）等。對于極大項、主合取范式等相關內容學生依據教材自學。作業：教材p60的9,10,11,15,17。命題演算系統命題演算系統是研究利用命題邏輯公式進行推理的形式系統。這里的推理指的是前提和結論之間的邏輯關系，所以這類形式系統自己不著重前提自己的正確性，而關懷的是能否能以前提有效地推出結論，議論什么是結論的有效證明。前提自己的正確性要在給予形式系統必定的解說的基礎上才能確立，這類解說能夠說是形式系統的語義。命題演算系統作為一個形式系統研究如何從公義，經過有限的規則來結構有效的證明，這類證明不過是符號的改寫，自己沒有什么含義。一個形式系統包含符號表、公式、公義及規則，符號表定義形式系統所使用的全部符號，公式是符號表上字符串，公式定義哪些字符串是形式系統所研究的合法對象。公義是結構一切證明的前提，公義自己的正確性在形式系統中不關懷，認為是不證自明的公式。自然在結構形式系統的時候，公義的選擇是必定的外在依照的。規則是從公義出發結構形式系統中定理的方法。定理就是從公義出發，使用規則能夠結構出有效證明的公式，形式系統就是研究能夠獲得什么定理。【定義1.35】命題演算系統P定義為：P的符號表包含：命題變元：小寫英文字母并可加下標聯絡詞：、協助符號：(,)（園括號）P的公式歸納定義為：命題變元是公式若A是公式，則(A)也是公式[3].若A和B是公式，則(AB)也是公式[4].全部公式都是經過有限次使用[1]、[2]和[3]獲得。P的公義有以下三類：[A1].(A(BA))[A2].((A(BC))((AB)(AC))[A3].(((A)(B))(BA))P的規則只有一條：分別規則：由A和(AB)可獲得B□【講解】對于以上定義，需要注意以下幾點：1.在系統P中只使用聯絡詞和，這使得系統P比較簡單，但也失掉了使用此外三個聯絡詞、和的方便之處，為此可作以下商定，對于P中公式A和B：(AB)代表((A)B)(AB)代表(((A)(B)))(AB)代表((AB)(BA))注意，、和不是系統P的符號，只可是是為了使用方便而引入的符號。2.上述給出的公義是一種模式，此中每一條公義實質上代表了無窮多個公式，因為其中的A,B,C是一個符號，實質上可代表任意的公式，比如對于[A2]，此中A可代表BC獲得：(((BC)(BC))(((BC)B)((BC)C))注意在使用公式A替代公式B的符號C時，要將公式A替代B中全部的C。相同分別規則也是一個模式。【定義1.36】命題演算系統P中的證明是由P中公式構成的一個序列：A1,A2,,An使得對每個i(1in)，以下兩個條件之一成立：(1).Ai是公義，或許(2).Ai是由上述序列中Ai以前的某兩個公式Aj,Ak(1j,kn)應用分別規則(M)獲得。此時A12,nnnn,A,A稱為A的一個證明，而A稱為P的一個內定理，記為├A。□【講解】對于以上定義，需要注意以下幾點：├也不是P中的符號，不過用├An來表示An是一個內定理。2.所謂的用兩個公式A,A應用分別規則(M)獲得，是指{A,A}={Aj,AjA}或{A,jkjkijA}={A,AkA}。kki3.若A1,A2,,An是An的一個證明，則對每個Ai(1in)都有├Ai。P的每個公義都是P中的內定理。5.要證明一個公式【例子1.12】設A,B

A為P的內定理，只需給出是P中的公式，證明：├(A

A的證明序列即可。B)(AA)【證明】(1).├A(2).├(A(3).├(A【例子1.13】設

(BA)(BA))((AB)(AB)(AA)A是P中的公式，證明：

A))├(A

A)

//公義[A1]//公義[A2]//分別規則

，此中C用A(M)及(1)和(2)

取代【證明】(1).├A((BA)A)//公義[A1](2).├(A((BA)A))((A(BA))(AA))//公義[A2](3).├((A(BA))(AA))//分別規則(M)及(1)和(2)(4).├(A(BA)//公義[A1](5).├(AA)//分別規則(M)及(3)和(4)【定理1.37】設A,B,C是P中的三個公式：若├A，且├AB，則├B[2].若├AB，且├BC，則├AC【證明】[1]就是分別規則。對于[2]，證明以下：(1).├(BC)(A(BC))//[A1](2).├(BC)//前提(3).├(A(BC))//分別規則(4).├(A(BC))((AB)(AC))//[A2](5).├(AB)(AC)//分別規則(6).├(AB)//前提(7).├(AC)//分別規則□此后稱此定理的[2]為傳達規則(Tr)。【例子1.15】證明：├(A)(AB)【證明】(1).(2).(3).

├(A)├((B)├(A)

((B)(A))(AB)

(A))(A

B)

//[A1]//[A3]//傳達規則【例子1.16】證明：├(A)A├A(A)證明】[1]的證明以下：(1).├(A)(AA)//例子1.15(2).├(AA)(AA)//[A3](3).├(A)(AA)//傳達規則(4).├(A(AA))((AA)(AA))//[A2](5).├(AA)(AA)//分別規則(6).├(AA)//例子1.13(7).├(AA)//分別規則的證明以下：(1).├(A)(A)//[1](2).├(AA)(AA)//[A3](3).├AA//分別規則【講解】經過以上例子，我們可發此刻結構公式的證明中可使用以下方法：1.可靈巧地使用公義，公義中的每個符號代表的是無窮多的公式，公義中某個符號的全部出現可用某個公式替代。但這與教材p43頁的置換規則不同，教材沒有為命題邏輯公式的推理成立形式系統，而是依據命題邏輯公式的真值來議論推理，所以有所謂的等值公式的置換，而我們這里所定義的形式系統還沒有波及到真值賦值，這里的證明不過是符號的改寫。成立形式系統的方法更切共計算機的思想方式，因為程序從實質來說也是個形式系統，計算機將輸入變換到輸出也不過符號的改寫，至于程序員所認為的程序功能，是程序員給予程序的解說，這類解說計算機其實不理解。也就是說，對于計算機學科，形式系統的推導和形式系統的含義是分開的，正是這類分別，才使得形式系統的推導可由計算機來機械地達成，而人們又能夠給予形式系統各種各種的解說來達成人們所需要的功能。可使用分別規則和傳達規則來結構證明。3.可使用已經證明過的內定理作為前提，這相當于教材p43頁的結論引入規則。4.教材中所議論的推理是在某種前提下的推理，下邊我們在命題演算系統P中來定義這類推理。【定義1.38】設是P中的一個公式集，稱P中的公式序列：A,A,,A12n為前提下推出An的一個證明，假如對每個i(1in)，以下三個條件之一成立：(1).Ai是公義，或許(2).Ai，或許(3).Ai是由上述序列中Ai以前的某兩個公式Aj,Ak(1j,kn)應用分別規則(M)獲得。此時記為├An。□【講解】對于上述定義，我們需要注意以下幾點：1.中的公式不必定是P中的公義或內定理，也不必定是有限會合。能夠說是假定的前提，在前提下的證明其實是將中的公式看作“暫時公義”的一個證明。易證：當=時，├A當且僅當├A，或許說├A就是沒有前提的證明。3.易證：對P中的任意公式A及公式集和'，若'，且'├A，則有├A。易證，若A，則有├A。【例子1.17】證明：{A,B(AC)}├(BC)【證明】(1).A//前提(2).A(BA)//公義[A1](3).(BA)//分別規則:(1)和(2)(4).(B(AC))//前提(5).(B(AC))((BA)(BC))//公義[A2](6).(BA)(BC)//分別規則:(4)和(5)(7).(BC)//分別規則:(3)和(6)下邊利用上述定義和定理來形式化地議論教材p42中給出的推理定律的正確性。這里形式化的含義是不經過對公式的真值議論，而不過依據P系統的公義和分別規則來證明那些推理定律，自然證明時同意使用我們已經證明過的內定理。為此，我們第一給出命題演算系統中最重要的一條定理，即演繹定理，經過演繹定理可將在某個前提下的證明與P系統中的內定理相聯系起來，并簡化內定理的證明。【定理1.39（演繹定理）】設是P中的公式集，A和B是P中的兩個公式，若{A}├B，則├AB。【證明】略。□【定理1.40（演繹定理的逆定理）】設是P中的公式集，A和B是P中的兩個公式，若├AB，則{A}├B。【證明】略。□由以上兩個定理，我們獲得：【推論1.41】{A1,A2,,A}├A當且僅當├(A1(A2(AnA)))□n當={A1,A2,,An}時，我們往常將├A寫為A1,A2,,An├A。依據演繹定理，分別規則可表示為A,AB├B，或用內定理表示為├A((AB)B)。對于傳達規則，可推行為：【定理1.42】設是P中的公式集，A1,A2,,An為P中的公式，如有├A1,├A2,,├An，且A1,A2,,An├A則├A。【證明】略。□對于上述定理1.39,1.40,1.42的證明可參照王悍貧編著的《失散數學第一分冊——數理邏輯》（北京大學第一版社，1997）的p70-75。我們可將├A1,├A2,,├An簡記為├A1,A,,A。2n【例子1.18】證明：{AB,A}├(B)【證明】(1).(A)A//例1.16(2).A//前提(3).A//(1)使用演繹定理，而后使用分別規則(4).AB//前提(5).B//分別規則(6).B(B)//例1.16(7).B//演繹定理及分別規則由此可得：├(AB)(AB)，又因為├(AB)(BA)（公義[A3]）獲得├(AB)(BA)。【例子1.19】證明：├A(B(AB))【證明】(1).├A((AB)B)//分別規則的內定理形式(2).├((AB)B)(B(AB))//例子1.18(3).├(B(AB))//傳達規則【定理1.43】合取的引入和除去：[1].A,B├AB//合取的引入[2].AB├A,B（這代表AB├A及AB├B）。//合取的除去【證明】第一注意到AB是(AB)的簡寫，即(AB)的簡寫。要證明[1]，依據演繹定理知就是要證明├A(B(AB))，這由例子1.19可得（將此中的B換成B即可）。要證明[2]，只需證明AB├A即可，因為AB├B可同理得證。要證明AB├A，按演繹定理，即要證├((AB))A，而依據例子1.15有├(A)(AB)，而依據公義[A3]有├(A)(AB)(((AB))A)，依據傳達規則有├((AB))A，再依據例子1.16有├(AA)，再依據傳達規則得├((AB))A。□實質上教材中的符號就是這里的├，再依據定理1.43就有教材p42的假言推理就是分別規則，合取的化簡就是定理1.43，拒取式就是例子1.18，假言三段論就是傳達規則。下邊給出對于析取的規則的證明，為此我們先給出下邊幾個例子：【例子1.20】證明：AB,AB,A├C【證明】(1).A//前提(2).AB//前提(3).B//分別規則(4).AB//前提(5).B//分別規則:(1)和(4)(6).B(BC)//例子1.15(7).BC//分別規則:(5)和(6)(8).C//分別規則:(7)和(3)該例子的直觀含義是，假如從命題A能推出B及B的否認，那么A能推出任何公式。由此可獲得├(AB)((AB)(AC))。【例子1.21】證明：AB,AB├B【證明】(1).(AB)(BA)//例子1.18(2).AB//前提(3).BA//分別規則(4).(AB)(BA)//公義[A3](5).AB//前提(6).BA//分別規則:(4)和(5)(7).(BA)((BA)(B(AB)))//例子1.20(8).(BA)(B(AB))//分別規則:(3)和(7)(9).B(AB)//分別規則:(6)和(8)(10).(B(AB))((AB)B))//公義[A3](11).(AB)B//分別規則:(9)和(10)(12).B//分別規則:(2)和(11)該例子的直觀含義是，假如命題B既能從A推出，又能從A推出，那么B就是永真的。由此可獲得├(AB)((AB)B)。這樣我們可證明對于析取的重要定理：【定理1.44】析取的引入和除去：[1].A├AB,A├BA//析取的引入，教材p42中的附帶定律[2].AB,CB,AC├B//析取的除去【證明】注意AC是(AC)的簡寫，那么依據演繹定理，[1]的前一個式子就是例子1.15，后一個式子則是公義[A1]。而[2]的證明以下：(1).AC//前提AC(2).CB//前提(3).AB//分別規則(4).AB//前提(5).B//例子1.21□依據演繹定理，定理1.44的[2]也可陳說為，如有A├B，且C├B，那么有AC├B。依據該定理，我們可獲得教材p42中對于析取的其余定律：【例子1.22】證明：[1].AB,B├A//析取三段論[2].AB,CD,AC├BD//結構性二難推理【證明】[1]的形式是AB,B├A，這可證明以下：(1).(AB)(BA)//公義[A3](2).AB//前提(3).BA//分別規則(4).B//前提(5).A//分別規則(6).AA//例子1.16(7).A//分別規則的證明以下：(1).AB//前提(2).BBD//定理1.44，析取的引入(3).ABD//分別規則(4).CBD//與(1)~(3)近似(5).AC//前提(6).BD//定理1.44，析取的除去【例子1.23】證明：├(AA)A【證明】只需證(AA)├A(1).A(A(AA))//例子1.15(2).(A(A(AA)))((AA)(A(AA)))//公義[A2](3).((AA)(A(AA)))//分別規則(4).AA//前提(5).A(AA)//分別規則:(3)和(4)(6).(A(AA))((AA)A)//公義[A3](7).(AA)A//分別規則:(5)和(6)(8).A//分別規則:(4)和(7)【例子1.24】證明：AB,AB├A【證明】(1).(AB)((AB)(AA))//例子1.20(2).(AB)//前提(3).(AB)(AA)//分別規則(4).AB//前提(5).(AA)//分別規則:(3)和(4)(6).(AA)A//例子1.23(7).A//分別規則:(5)和(6)讀者可很簡單地看出，教材p46的附帶前提證明法就是演繹定理的特別形式，而歸謬法則相當于例子1.24.最后我們來議論命題演算系統的元問題，即該形式系統的靠譜性、一致性和齊備性。可靠性是指命題演算系統P中的內定理能否都是永真式，一致性是指P能否存在公式A，使得├A和├(A)都成立，假如存在這樣的公式，則由例子1.20知P可推出任何公式，這時P便沒有任何意義。齊備性是指P能否能推出命題邏輯公式的全部永真