以下自考復習資料均由浙江自考網整理并發布，考生想要了解更多關于浙江自考報名、考試、成績查詢、畢業、歷年真題、常見問答等相關信息請關注浙江自考網，獲取浙江自考更多信息。

第一講 引言

一、課程內容

·數理邏輯：是計算機科學的基礎，應熟練掌握將現實生活中的條件化成邏輯公式，并能做適當的推理，這對程序設計等課程是極有用處的。

·集合論：數學的基礎，對于學習程序設計、數據結構、編譯原理等幾乎所有計算機專業課程和數學課程都很有用處。熟練掌握有關集合、函數、關系等基本概念。

·代數結構：對于抽象數據類型、形式語義的研究很有用處。培養數學思維，將以前學過的知識系統化、形式化和抽象化。熟練掌握有關代數系統的基本概念，以及群、環、域等代數結構的基本知識。

·圖論：對于解決許多實際問題很有用處，對于學習數據結構、編譯原理課程也很有幫助。要求掌握有關圖、樹的基本概念，以及如何將圖論用于實際問題的解決，并培養其使用數學工具建立模型的思維方式。

·講課時間為兩個學期，第一學期講授數理邏輯與集合論，第二學期講授代數結構和圖論。考試內容限于書中的內容和難度，但講課內容不限于書中的內容和難度。

二、數理邏輯發展史

1.目的

·了解有關的背景，加深對計算機學科的全面了解，特別是理論方面的了解，而不限于將計算機看成是一門技術或工程性的學科。

·通過重要的歷史事件，了解計算機科學中的一些基本思維方式和一些基本問題。

2.數理邏輯的發展前期

·前史時期——古典形式邏輯時期：亞里斯多德的直言三段論理論

·初創時期——邏輯代數時期（17世紀末）

·資本主義生產力大發展，自然科學取得了長足的進步，數學在認識自然、發展技術方面起到了相當重要的作用。

·人們希望使用數學的方法來研究思維，把思維過程轉換為數學的計算。

·萊布尼茲(Leibniz, 1646~1716)完善三段論，提出了建立數理邏輯或者說理性演算的思想：

·提出將推理的正確性化歸于計算，這種演算能使人們的推理不依賴于對推理過程中的命題的含義內容的思考，將推理的規則變為演算的規則。

·使用一種符號語言來代替自然語言對演算進行描述，將符號的形式和其含義分開。使得演算從很大程度上取決與符號的組合規律，而與其含義無關。

·布爾(G. Boole, 1815~1864)代數：將有關數學運算的研究的代數系統推廣到邏輯領域，布爾代數既是一種代數系統，也是一種邏輯演算。

3.數理邏輯的奠基時期

·弗雷格(G. Frege, 1848~1925)：《概念語言——一種按算術的公式語言構成的純思維公式語言》(1879)的出版標志著數理邏輯的基礎部分——命題演算和謂詞演算的正式建立。

·皮亞諾(Giuseppe Peano, 1858~1932)：《用一種新的方法陳述的算術原理》(1889)提出了自然數算術的一個公理系統。

·羅素(Bertrand Russell, 1872~1970)：《數學原理》(與懷特黑合著，1910, 1912, 1913)從命題演算和謂詞演算開始，然后通過一元和二元命題函項定義了類和關系的概念，建立了抽象的類演算和關系演算。由此出發，在類型論的基礎上用連續定義和證明的方式引出了數學（主要是算術）中的主要概念和定理。

·邏輯演算的發展：甘岑(G. Gentzen)的自然推理系統(Natural Deduction System)，邏輯演算的元理論：公理的獨立性、一致性、完全性等。

·各種各樣的非經典邏輯的發展：路易斯(Lewis, 1883~1964)的模態邏輯，實質蘊涵怪論和嚴格蘊涵、相干邏輯等，盧卡西維茨的多值邏輯等。

4.集合論的發展

·看待無窮集合的兩種觀點：實無窮與潛無窮

·康托爾(G. Cantor, 1845~1918)：以實無窮的思想為指導，建立了樸素集合論

·外延原則（集合由它的元素決定）和概括原則（每一性質產生一集合）。

·可數集和不可數集，確定無窮集合的本質在于集合本身能與其子集一一對應。能與正整數集合對應的集合是可數的，否則是不可數的。證明了有理數集是可數的，使用對角線法證明了實數集合是不可數的。

·超窮基數和超窮序數

·樸素集合論的悖論：羅素悖論

·公理集合論的建立：ZFC系統

6.第三次數學危機與邏輯主義、直覺主義與形式主義

·集合論的悖論使得人們覺得數學產生了第三次危機，提出了數學的基礎到底是什么這樣的問題。

·羅素等的邏輯主義：數學的基礎是邏輯，倡導一切數學可從邏輯符號推出，《數學原理》一書是他們這一思想的體現。為解決悖論產生了邏輯類型論。

·布勞維爾(Brouwer, 1881~1966)的直覺主義：數學是心靈的構造，只承認可構造的數學，強調構造的能行性，與計算機科學有重要的聯系。堅持潛無窮，強調排中律不能用于無窮集合。海丁(Heyting)的直覺主義邏輯。

·希爾伯特(D. Hilbert)的形式主義：公理化方法與形式化方法，元數學和證明論，提倡將邏輯演算和數學證明本身形式化，把用普通的語言傳達的內容上的數學科學變為用數學符號和邏輯符號按一定法則排列的一堆公式。為了消除悖論，要數學建立在公理化基礎上，將各門數學形式化，構成形式系統，并證明其一致性，這是希爾伯特的數學綱領。

7.數理邏輯的發展初期

·哥德爾(Godel, 1906~1978)不完全性定理：一個足夠強大的形式系統，如果是一致的則不是完全的，即有的判斷在其中是不可證的，既不能斷定其為假，也不能證明其為真。

·各種計算模型：哥德爾的遞歸函數理論，邱吉爾的l演算，圖靈機模型

·這些計算模型是計算機科學的理論基礎，是計算機的理論模型。

三、預備知識

1.集合的基本概念

·集合(set)：集合是數學中最基本的概念之一，不能以更簡單的概念來定義(define)，只能給出它的描述(description)。一些對象的整體就稱為一個集合，這個整體的每個對象稱為該集合的一個元素(member或element)。

·用大寫字母A, B, C等表示集合，用小寫字母a, b, c等表示集合的元素

·a?A表示：a是集合A的元素，或說a屬于集合A

·a?A表示：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的子集，記為AíB，如果a屬于集合A則a也屬于集合B。因此A=B當且僅當AíB且BíA。說集合A是集合B的真子集(proper subset)，如果AíB且A不等于B(A 1 B)。

·空集(empty set)：約定存在一個沒有任何元素的集合，稱為空集，記為f，有時也用{}來表示。按子集的定義，空集是任何集合的子集(為什么？)。

·冪集(power set)：集合A的冪集，記為P(A)，是A的所有子集所構成的集合，即：

·P(A) = { B | B í A }

·例如，A = {0, 1}，則P(A) = { {}, {0}, {1}, {0, 1} }

·顯然，對任意集合A，有f? P(A)和A?P(A) 

·補集(complement set)：集合A的補集，記為A，是那些不屬于集合A的元素所構成的集合，即A = {x | x?A}。通常來說，是在存在一個全集U的情況下討論集合的補集。全集U是所討論的問題域中所有元素所構成的集合。

·集合的并(union)：集合A和B的并AèB定義為：AèB = {x | x?A或者x?B}，集合的并可推廣到多個集合，設A1, A2, …, An都是集合，它們的并定義為：

A1èA2…èAn = {x | 存在某個i，使得x?Ai}

·集合的交(intersection)：集合A和B的并A?B定義為：A?B = {x | x?A而且x?B}，集合的交也可推廣到多個集合，設A1, A2, …, An都是集合，它們的交定義為：

A1èA2…èAn = {x | 對所有的i，都有x?Ai}

·集合的差(difference)：集合A和B的差A-B定義為：A-B = {x | x?A而且x?B}。

2.關系和函數的基本概念

·有序對(ordered pair)：設A和B是兩個集合，a?A, b?B是兩個元素，a和b的有序對，記為<a, b>，定義為集合{{a}, {a, b}}。

·設<a1, b1>和<a2, b2>是兩個有序對，可以證明<a1, b1> = <a2, b2>當且僅當a1 = a2且b1 = b2。(如何證？)

·有序對可推廣到n個元素，設A1, A2, …, An是集合，a1?A1, a2?A2, …, an?An是元素，定義有序n元組(ordered n-tuple)<a1, a2, …, an>為<<a1, a2, …, an-1>, an>，注意這是一個歸納(inductive)定義，將有序n元組的定義歸結為有序n-1元組的定義。

·顯然有<a1, a2, …, an> = <b1, b2, …, bn>當且僅當a1 = b1且a2 = b2且…且an = bn。 

·集合的笛卡爾積(cartesian product)：兩個集合A和B的笛卡爾積A′B定義為：

A′B = {<a, b> | a?A且b?B}

·例如，設A = {a, b, c}，B = {1, 2}，則：

A′B = {<a, 1>, <a, 2>, <b, 1>, <b, 2>, <c, 1>, <c, 2>}

·笛卡爾積可推廣到多個集合的情況，集合A1, A2, …, An的笛卡爾積定義為：

A1′A2′…′An = {<a1, a2, …, an> | a1?A1且a2?A2且…且an?An} 

·集合之間的關系(relation)：定義n個集合A1, A2, …, An之間的一個n元關系R為集合A1, A2, …, An的笛卡爾積A1′A2′…′An的一個子集。設<a1, a2, …, an>?A1′A2′…′An，若<a1, a2, …, an>?R，則稱a1, a2, …, an間具有關系R，否則稱它們不具有關系R。特別地：

·當A1 = A2 = … = An = A時，稱R為A上的n元關系。

·當n = 2時，有RíA1′A2，稱R為A1與A2間的一個二元關系(binary relation)。這時若<a1, a2>?R則簡記為a1Ra2，否則（即<a1, a2>?R）記為a1Ra2。通常研究得最多的是二元關系，n元關系的許多性質可從二元關系的性質擴充而得到。如果沒有特別指明的話，說R是一個關系則是指R是一個二元關系。

·當n = 1時，這時可認為R是集合A上滿足某種性質的子集。

·關系的一些性質：設R是A上的二元關系：

·說R是自反的(reflexive)，如果對任意的a?A有aRa。

·說R是反自反的(irreflexive)，如果對任意的a?A有aRa。

·說R是對稱的(symmetric)，如果對任意的a, b?A有若aRb則bRa。

· 說R是反對稱的(antisymmetric)，如果對任意的a, b?A有若aRb且bRa則a = b。

·說R是傳遞的(transitive)，如果對任意的a, b, c ?A有若aRb且bRc則aRc。

·說R是等價關系(equivalence)，如果R是自反的、對稱的和傳遞的。 

·集合之間的函數(function，或說映射mapping)：定義集合A到B的函數f是A和B的笛卡爾積A′B的一個子集，且滿足若<x, y>?f及<x, z>?f則y = z。因此函數是A和B之間的一個特殊的二元關系。通常記集合A到B的函數f為f : A?B。

·函數f : A?B的定義域(domain)dom(f )定義為：

dom(f ) = {x | 存在某個y?B使得<x, y>?f }

·函數f : A?B的值域(range)ran(f )定義為：

ran(f ) = {y | 存在某個x?A使得<x, y>?f }

·若<x, y>?f，通常記y為f(x)，并稱y為x在函數f下的像(image)，x為y在函數f下的原像。

·函數也可推廣到n元的情形：f : A1′A2′…′An?B，意味著：

·f是A1′A2′…′An′B的一個子集，且

·<x1, x2, …, xn, y>? f且<x1, x2, …, xn, z>? f則y = z。 

·函數的一些性質：設f : A?B是集合A到B的函數：

·說f是全函數(total function)，若dom(f )=A，否則稱f是偏函數(partial function)。下面如果沒有特別指明的話，都是指全函數。

·說f是滿射(surjection, 或說f maps A onto B)，如果ran(f ) = B，即對任意的y?B都有原像。

·說f是單射(injection，或說f is one-one)，如果有f (x1) = f(x2)則x1 = x2，即對任意的y?B，如果它有原像的話，則有唯一的原像。

·說f是雙射(bijection，或說f是一一對應)，如果f既是滿射，又是單射，即對任意的y?B，都有唯一的原像，同樣根據全函數的定義，對于任意x?A都有唯一的像。這時可以定義f的逆函數(inverse function)，記為f -1 : B?A，f -1(y) = x當且僅當f(x) = y。顯然f -1也是雙射。 

·集合的基數(cardinal number)或說勢：集合A的基數記為|A|，且有：

·對于有限集合A，令A的基數為A中元素的個數。

·定義無限集合，不直接定義基數，而是通過定義兩個集合之間的等勢關系來刻劃集合的基數或勢，說集合A和集合B是等勢的(equipotent)，如果存在一個從A到B的雙射。根據雙射的性質，可以證明等勢是集合上的一個等價關系。

·稱與自然數集等勢的集合為可列集(enumerable)，有限集和可列集統稱為可數集(countable)。

·設A和B是有限集合，有|P(A)| = 2|A|，|A′B| = |A| ′ |B|。

. 歸納定義和歸納證明

·一個集合的歸納定義(inductive definition)通常分為三步：

·歸納基：一些基本的元素屬于該集合；

·歸納步：定義一些規則（或者說操作），從該集合中已有的元素來生成該集合的新的元素；

·最小化：該集合中的所有元素都是通過基本元素以及所定義的規則生成的，換句話說，該集合是由基本元素及規則所生成的最小的集合。

·自然數集N的歸納定義：

[1]. 歸納基：0是一個自然數，即0? N。

[2]. 歸納步：若n是自然數，則n的后繼也是自然數。記n的后繼為succ(n)，即若n?N，則succ(n)?N。為方便起見，后面也記n的后繼為n+1。

[3]. 最小化：所有的自然都通過步驟[1]和[2]得到，或者說自然數集是通過步驟[1]和[2]得到的最小集合。

·這種定義方式可推廣到對其他一些概念的定義，例如上述多個集合的并、交、笛卡爾積以及多個元素的有序n元組都可通過遞歸的方式定義。例如，對于多個集合的并可定義為：

·歸納基：A1èA2 = {x | x?A1或者x?A2}

·歸納步：A1èA2…èAn = (A1èA2…èAn-1) è An

·這里不需要最小化，因為這里不是定義集合。

·數學歸納法：關于自然數的許多性質都可通過數學歸納法來證明，對于性質R，如果它對0成立，而且如果對于n成立的話，能夠得到它對于n+1也成立，那么性質R對所有的自然數成立。這種證明方法的正確性本身可通過自然數的歸納定義來得到證明：

·定義集合S = {n?N | 性質R對n成立}

·歸納基：根據上面的定義有0?S

·歸納步：根據上面的定義有如果n?S，則n+1?S，所以S是滿足上面自然數集的歸納定義中的1、2點的一個集合，而自然數集N是滿足這兩點的最小集合，所以有N íS，而顯然有SíN，所以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成立。這種形式的數學歸納法通常稱為第二數學歸納法。

5. 形式系統

·形式系統的定義：一個形式系統S由下列4個集合構成：

·一個非空集合SS，稱為形式系統S的字母表或說符號(Symbol)表；

·一個由SS中字母的有限序列（字符串）所構成的集合FS，稱為形式系統S的公式(Formula)集；

·從FS中選取一個子集AS，稱為形式系統S的公理(Axiom)集；

·FS上有一個部分函數集RS = {Rn | Rn : FS ′ FS ′…′ FS ?FS , n = 1, 2, …}，稱為形式系統S的規則(Rule)集，其中Rn : FS ′ FS ′…′ FS ?FS是n元的部分函數，我們稱其為n元規則。

·形式系統中的定理(Theorem)：

·歸納基：t ? AS 是形式系統S中的定理。

· 歸納步：t1, t2, …, tn是形式系統S中的定理，而Rn?是S中的規則，那么Rn(t1, t2, …, tn)也是形式系統S中的定理。

·對于形式系統中的規則Rn : FS ′ FS ′…′ FS ?FS，通常表示成下面的形式：

t1, t2, …, tn

Rn(t1, t2, …, tn)

·形式系統具有兩個特征：

·形式化實際上是一個可機械實現的過程，在它里面，符號、規則和演算等被表示得嚴密、精確。在形式系統S中，只能使用字母表SS中的符號，只承認公式集FS中的符號串的合理性，只能由公理集，根據規則推出有意義的東西來。

·形式系統一旦完成，就成了符號串及根據規則進行的符號串的改寫，系統與一切實際意義就毫不相干，或者說已經通過這種符號，從實際問題中抽象出了我們所需要研究的內容。在形式系統內部，所能認識的只能是符號串及其改寫，只能在形式系統外對這種符號串及規則賦予意義。 

·對象語言(Object language)與元語言(Meta language)：

·數理邏輯所研究的是“數學推理”，而使用的方法也是數學推理，所以有必要區分這兩個層次的推理。

·把作為研究對象的“推理”形式化，使用形式語言來表示作為研究對象的“推理”的前提、結論和規則等，這種形式語言是我們所研究的對象語言。

·另一方面，關于形式系統的性質、規律的表達和作為研究方面的推理方式使用另一種語言來表達，這個語言稱為研究的元語言，通常使用半數學化的自然語言。

·形式語言的語法(Syntax)與語義(Semantic)：

·形式語言的語法是構成形式系統的公式集、公理集和規則集的法則。

·形式語言的語義是關于形式系統的解釋和意思。

·形式語言本身沒有含義，但我們在構造它們時是假想它們能代表某種意義的，特別的當我們在選擇形式系統的公理時，總是選擇所研究的問題域中那些最為明顯或最容易公認為正確的性質。

6. 習題

1. 令集合A = { n | n ￡ 10且n 是奇數}，B = {n | n ￡ 10且n是素數}，請回答下列問題：

a) 請用列元素的方法列出集合A和集合B，請問集合B是否是集合A的子集？

b) 請計算AèB、A?B、A-B、A′B以及P(A)(即A的冪集)。

2. 設關系R = {<a, b> | a和b是互質的自然數}，請問R是自反的嗎？對稱的嗎？傳遞的嗎？為什么？

3. 設f : A?B是函數，R是A上的如下二元關系：R = {<a, b> | a, b?A, f (a) = f (b) }，  證明R是A上的一個等價關系。

4. 使用數學歸納法證明：12 + 22 + 32 + … + n2 = (n * (n + 1) * (2n + 1)) / 6

5. 設有函數f : N?N ′ N，f(n) = <n, n+1>，請問f是不是單射、滿射或雙射？

*6.設R1和R2都是A上的等價關系，請問R1èR2和R1?R2是否還是A上的等價關系？如果是請證明，否則請舉一反例。

*7.設R是集合A上的等價關系，a?A，可定義：

a) [a] = {b?A | aRb }，稱[a]為a關于R的等價類；

b) A/R = {[a] | a?A}，稱A關于R的商集。

設函數f : A?A/R定義為對任意a?A有f(a) = [a]，請問R滿足怎樣的條件時f是單射？

*8 請給出<x, y, z>的集合方式的定義。若定義：[x, y, z] = {{x}, {x, y}, {x, y, z}}，則如果有[x1, y1, z1] = [x2, y2, z2]是否意味著有x1 = x2且y1 = y2且z1 = z2？

3.命題邏輯公式

【定義1.1】命題邏輯公式(propositional logic formula)由以下子句歸納定義：

[1]. 歸納基：命題常量或命題變量是命題邏輯公式，稱為命題邏輯公式的原子項。

[2]. 歸納步：如果A, B是邏輯公式，則(?A)、(AùB)、(AúB)、(A?B)和(A?B)也是命題邏輯公式。

[3]. 最小化：所有的命題邏輯公式都通過1和2得到。

在這里我們隱含地使用的字母表是大小寫的英文字母、命題聯結符和園括號。英文字母還可帶下標。其它的符號都不屬于我們的符號表，即在命題邏輯公式中不能出現這些符號。后面我們將命題邏輯公式簡稱為命題公式，或在沒有二義的情況下進一步簡稱為公式。

【例子1.1】((p ú q) ? ((?p) ? (q ù r)))是命題公式，它通過以下步驟生成：

1.p是公式；  // 根據定義1.1的[1]

2.q是公式；  // 根據定義1.1的[1]

3.(p ú q)是公式；// 根據定義1.1的[2]

4.(?p)是公式； // 根據定義1.1的[2]

5.r是公式；  // 根據定義1.1的[1]

6.(q ù r)是公式；// 根據定義1.1的[2]

7.((?p) ? (q ù r))是公式；// 根據定義1.1的[2]，以及4, 6

8.((p ú q) ? ((?p) ? (q ù r)))是公式。  // 根據定義1.1的[2]，以及3, 7

【定理1.2】設R是某個性質，如果有：

[1]. 對于所有的原子項p，都滿足性質R；

[2]. 如果對任意的公式A和B都滿足性質R，就有(?A)、(AùB)、(AúB)、(A?B)和(A?B)也滿足性質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，顯然定理成立。

2. 歸納步：假設定理對于命題公式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]. (AùB)

[4]. (AúB)[5]. (A?B)[6]. (A?B)

【定理1.6】的確切含義包括以下幾點：

1. 任意命題公式必然具有上述6中形式之一；

2. 這6中形式都互不相同；

3. 如果(?A)與(?A1)相同，則必有A與A1相同；

4. 如果(A * B)與(A1 * B1)相同，則必有A與A1相同，且B與B1相同。 

根據定理1.5和定理1.6，我們不難明白例子1.1是如何得到該其中命題公式的語法分析樹的。實際上每個命題公式的最左邊都是左園括號，如果從第二個符號不是左園括號，那么這個公式只有一個命題聯結符。否則找與第二個左園括號配對的右園括號，從而將命題公式劃分為這樣的形式：((…) * (…))，如果原來的命題公式為根的話，那么左右兩邊的兩個命題公式分別為它的左右子樹了，而且對這兩個公式可作類似的分析，最后到原子項。

在后面，為了書寫方便起見，我們省略最外邊的括號，并規定各個命題聯結符的優先級別為?大于ù，ù大于ú，ú大于?，?大于?，從而可省略命題公式中一些不必要的園括號，例如例子1.1中的公式可寫為：p ú q ? ?p ? q ù r。不過在后面我們書寫公式的原則是盡量簡便，但又能讓讀者容易理解。而有關命題公式的性質的討論，則只針對可由上面定義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 = ((p ú q) ? ((?p) ? (q ù r)))，有：

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(AùB) = 1，否則t(AùB) = 0。

[5].若t(A) = t(B) = 0，則t(AúB) = 0，否則t(AúB) = 1。

[6].若t(A) = 0或者t(B) = 1，則t(A?B) = 1，否則t(A?B) = 0。

[7].若t(A) = t(B)，則t(A?B) = 1，否則t(A?B) = 0。

【例子1.3，續】對于命題公式A = ((p ú q) ? ((?p) ? (q ù r)))，及真值賦值函數t：

t(p) = 0, t(q) = 1, t(r) = 0

有：

1.  t(p) = 0, t(q) = 1;

2.  t(p ú q) = 1;// 根據定義1.8的[5]

4.  t(?p) = 1;// 根據定義1.8的[3]