離散數學1/145離散數學:研究離散量關系一門科學。研究離散結構數學分科。（辭海）2/145離散數學內容：數理邏輯（MathematicsLogic)集合論(Sets)組合論（Combination)圖論（GraphTheory)代數結構（AlgbraStructure)線性代數(LinearAlgbra)概率論（PropobilityTheory)……3/145離散數學由來與發展:一、古老歷史:計數:自然數發展:圖論:Konigsberg七橋問題二、年青新生:計算機:二進制運算4/145離散數學課程設置：計算機系關鍵課程信息類專業必修課程其它類專業主要選修課程5/145離散數學后繼課程：數據結構、編譯技術、算法分析與設計、人工智能、數據庫、……6/145離散數學課程學習方法:強調：邏輯性、抽象性；重視：概念、方法與應用7/145用一組基本指令來編制一個計算機程序，非常類似于從一組公理來結構一個數學證實。8/145第一章 命題邏輯命題邏輯，也稱命題演算，記為Ls。它與謂詞邏輯組成數理邏輯基礎，而命題邏輯又是謂詞邏輯基礎。數理邏輯是用數學方法即經過引入表意符號研究推理學問。所以，數理邏輯又名為符號邏輯。命題邏輯是研究由命題為基本單位組成前提和結論之間可推導關系。退出9/1451.1命題與聯結詞1.2命題變元和合式公式1.3公式分類與等價公式1.4聯結詞擴充與功效完全組1.5公式標準型——范式1.6公式主范式1.7命題邏輯推理理論10/1451.1 命題與聯結詞

１.命題概念

11/145命題：能判斷真假陳說句。命題真值：命題判斷結果。它只有兩種可能：真用1或T表示，假用0或F表示。真值為1命題稱為真命題；真值為0命題稱為假命題。

12/145判斷一個句子是否為命題：首先判斷它是否陳說句，假如是陳說句，再判斷它是否含有唯一真值。(命題真值是含有客觀性質，而不是由人主觀決定。)13/145例判斷以下句子是否為命題（1）

3是素數。（2）

5.2是無理數。（3）

x大于y。（4）

月球上有冰。（5）

年元旦是晴天。（6）

π大于3嗎？14/145（7）

請不要吸煙！（8）

這朵花真漂亮啊！（9）

我正在說假話。解

：(6)、(7)、(8)、(3)、(9)不是命題，其余都是。

15/145所謂命題，是指含有非真必假陳說句。而疑問句、祈使句和感嘆句等因都不能判斷其真假，故都不是命題。命題僅有兩種可能真值—真和假，且二者只能居其一。因為命題只有兩種真值，所以稱這種邏輯為二值邏輯。16/145假如一陳說句再也不能分解成更為簡單語句，由它組成命題稱為原子命題或簡單命題。原子命題是命題邏輯基本單位。命題分為兩類，第一類是原子命題，原子命題用英文字母P，Q，R…及其帶下標Pi，Qi，Ri，…表示。17/145命題常項(元)：真值確定簡單命題。命題變項(元)：真值可變簡單陳說句。如上例中（3）。第二類是復合命題，它由原子命題、命題聯結詞和圓括號組成。18/145２.命題聯結詞定義1.1.1 設P表示一個命題，由命題聯結詞l和命題P連接成lP，稱lP為P否定式復合命題，lP讀“非P”。稱l為否定聯結詞。lP是真，當且僅當P為假；lP是假，當且僅當P為真。否定聯結詞“l”定義可由表1.1.1表示之。19/14520/145 因為否定”修改了命題，它是對單個命題進行操作，稱它為一元聯結詞。21/145例將以下命題符號化：（1）

張偉不是三好學生。（2）

不是有理數。解：記p：張偉是三好學生。q：是有理數。則:(1)┐p；(2)┐q22/145定義1.1.2 設P和Q為兩個命題，由命題聯結詞∧將P和Q連接成P∧Q，稱P∧Q為命題P和Q合取式復合命題，P∧Q讀做“P與Q”，或“P且Q”。稱∧為合取聯結詞。當且僅當P和Q真值同為真，命題P∧Q真值才為真；不然，P∧Q真值為假。合取聯結詞∧定義由表1.1.2表示之。23/14524/145例將以下命題符號化(1)

2和3都是素數.(2)

張偉既用功又好學.(3)

張偉不但用功而且聰明.(4)

張偉即使用功但不聰明.(5)

張偉和王輝都是三好學生.(6)

張偉和王輝是同學.25/145解:(1)令p:2是素數；q:3是素數，則：p∧q。(2)、(3)、(4)：令r:張偉用功；s:張偉好學，t:張偉聰明；則：r∧s;r∧t;r∧┐t。(5)令x:張偉是三好學生；y:王輝是三好學生，則：x∧y。(6)是原子命題。26/145定義1.1.3 設P和Q為兩個命題，由命題聯結詞∨把P和Q連接成P∨Q，稱P∨Q為命題P和Q析取式復合命題，P∨Q讀做“P或Q”。稱∨為析取聯結詞。當且僅當P和Q真值同為假，P∨Q真值為假；不然，P∨Q真值為真。析取聯結詞∨定義由表1.1.3表示之。27/14528/145由定義可知，析取聯結詞表示“可兼和”，“不可兼和”另有別聯結詞定義之。前者稱為相容或，后者稱為排斥或。與合取聯結詞一樣，使用析取聯結詞時，也不要求兩命題間一定有任何關系。29/145例將以下命題符號化（1）

2或4是素數。（2）

他想去唱歌或跳舞。（3）

老王只能住204房或206房。（4）

派老五或小李中一個去上海。30/145解：(1)令p:2是素數；q:4是素數，則：p∨q;(2)令r:他想去唱歌；s:他想去跳舞，則：r∨s;(3)令t:老王住204房；u:老王住206房，則:(t∧┐u)∨(┐t∧u);(4)令x：派老王去上海；y：派小李去上海，則：(x∧┐y)∨(┐x∧y)。31/145定義1.1.4 設P和Q為兩個命題，由命題聯結詞→把P和Q連接成P→Q，稱P→Q為命題P和Q蘊涵（條件）式復合命題，簡稱蘊涵（條件）命題。P→Q讀做“P蘊涵（條件）Q”或者“若P則Q”。稱→為蘊涵（條件）聯結詞。 當P真值為真而Q真值為假時，命題P→Q真值為假；不然，P→Q真值為真。條件聯結詞→定義由表1.1.4表示之。

32/14533/145在條件命題P→Q中，命題P稱為P→Q前件或前提，命題Q稱為P→Q后件或結論。條件命題P→Q有各種方式陳說：“假如P，那么Q”；“P僅當Q”；“Q每當P”；“P是Q充分條件”；“Q是P必要條件”；“只有q才p”，“除非q才p”,“除非q，不然非p”等。34/145在日常生活中，用條件式表示前提和結論之間因果或實質關系，這種條件式稱為形式條件命題。然而在命題邏輯中，一個條件式前提并不要求與結論有任何關系，這種條件式稱為實質條件命題。采取實質條件式作定義，不單是出于“善意推斷”，主要是因為前提與結論間有沒有因果和實質關系難以區分，而且實質條件式已包含了形式條件式，更便于應用。35/145例將以下命題符號化，并指出各復合命題真值。(1)

假如3+3=6,則雪是白色。(2)

假如3+3≠6,則雪是白色。(3)

假如3+3=6,則雪不是白色。(4)

假如3+3≠6,則雪不是白色。(5)

只要a能被４整除，則a一定能被２整除。(6)

a能被４整除，僅當a能被２整除。(7)

除非a能被２整除，a才能被４整除。(8)

除非a能被２整除，不然a不能被４整除。(9)

只有a能被２整除，a才能被４整除。(10)只有a能被４整除，a才能被２整除。(a是一個給定正整數）。36/145解：令p：3+3=6；q：雪是白色。則(1)到(4)符號化形勢分別為：p→q；┐p→q；p→┐q；┐p→┐q。它們真值分別為：１,１,０,１。令r：a能被４整除；s:a能被２整除。(5)到(9)都可符號化為:r→s,真值為１。(10)可符號化為s→r，真值視a值而定。37/145定義1.1.5 令P、Q是兩個命題，由命題聯結詞

把P和Q連接成P

Q，稱P

Q為命題P和Q雙條件式復合命題，簡稱雙條件命題，P

Q讀做“P當且僅當Q”，或“P等價Q”。稱

為雙條件聯結詞。當P和Q真值相同時，P

Q真值為真；不然，P

Q真值為假。雙條件聯結詞

定義由表1.1.5表示之。38/14539/145例將以下命題符號化，并討論它們真值。(1)

√3是無理數當且僅當加拿大位于亞洲。(2)

2+3=5充要條件是√3是無理數。(3)

若兩圓面積相等，則它們半徑相等，反之亦然。(4)

燕子飛向北方時，春天就來了；而當春天來時，燕子就會飛回北方。40/145解：(1)令p：√3是無理數；q：加拿大位于亞洲，則p?q,真值為0。（2）令r：2+3=5；令p：√3是無理數，則r?p,真值為1。（3）令s：兩圓面積相等；t：兩圓半徑相等，則s?t,真值為1。（4）令x：燕子飛回北方；y：春天來了，則x?y,真值為1。41/145本節小結以上定義五種最基本聯結詞組成一個聯結詞集{┐，∧，∨，→，?}。由其中某個聯結詞聯結兩個原子命題（┐聯結一個原子命題）所形成復合命題稱為基本復合命題，它們真值情況以下表。pq┐pp∧qp∨qp→qp?q000110111100000101111101100142/145

屢次使用聯結詞集中聯結詞，可組成更為復雜復合命題。求復雜復合命題真值時，可依據上述真值表逐次求取。但運算過程中應注意聯結詞優先次序(包含括號)：(),┐,∧,∨,→，?。對同一優先級聯結詞，按出現先后次序運算。43/145例令：p：北京比天津人口多；q：2+2=4；r：烏鴉是白色。求以下命題真值：(1)((┐p∧q)∨(p∧┐q))→r;(2)(q∨r)→(p→┐r);(3)(┐p∨r)?(p∧┐r).解：∵p,q,r真值分別為1,1,0，∴按照真值表及命題式，(1),(2),(3)真值分別為1,1,0。44/145在本節結束時，應強調指出是：復合命題真值只取決于各原子命題真值，而與它們內容、含義無關，與原子命題之間是否相關系無關。了解和掌握這一點是至關主要。45/1451.2命題變元和合式公式１.命題變元在命題邏輯中，命題又有命題常元和命題變元之分。一個確定詳細命題，稱為命題常元；一個不確定泛指任意命題，稱為命題變元。顯然，命題變元不是命題，只有用一個特定命題取代才能確定它真值：真或假。這時也說對該命題變元指派真值。46/145命題常元和命題變元均可用字母P等表示。因為在命題邏輯中并不關心詳細命題涵義，只關心其真值，所以，能夠形式地定義它們以下： 定義1.2.1 以真或1、假或0為其變域變元，稱為命題變元；真或1、假或0稱為命題常元。47/1452. 合式公式通常把含有命題變元斷言稱為命題公式。但這沒能指出命題公式結構，因為不是全部由命題變元、聯結詞和括號所組成字符串都能成為命題公式。為此常使用歸納定義命題公式，方便組成公式有規則可循。由這種定義產生公式稱為合式公式。定義1.2.2 單個命題變元和命題常元稱為原子命題公式，簡稱原子公式。48/145定義1.2.3 合式公式是由以下規則生成公式：①單個原子公式是合式公式。②若A是一個合式公式，則(lA)也是一個合式公式。③若A、B是合式公式，則(A∧B)、(A∨B)、(A→B)和(A

B)都是合式公式。④只有有限次使用①、②和③生成公式才是合式公式。49/145當合式公式比較復雜時，經常使用很多圓括號，為了降低圓括號使用量，可作以下約定：①要求聯結詞優先級由高到低次序為：l、∧、∨、→、

②相同聯結詞按從左至右次序計算時，圓括號可省略。③最外層圓括號能夠省略。為了方便計，合式公式也簡稱公式。50/145

定義(1)若命題公式A是單個命題(常項或變項)，則稱A為0層公式。(2)稱命題A是n+1(n≥0)層公式，只要A是以下情況之一：(a)A=┐B,B是n層公式;(b)A=B∧C,B,C分別為i層和j層公式，且max(i,j)=n。(c)A=B∨C,B,C分別為i層和j層公式，且max(i,j)=n。(d)A=B→C,B,C分別為i層和j層公式，且max(i,j)=n。(e)A=B?C,B,C分別為i層和j層公式，且max(i,j)=n。比如:(┐p∧q)→r,(┐(p→┐q))∧((r∨s)?┐p)分別為3層和4層公式。51/145

因為命題公式中含有命題變項，故其真值普通是不確定。當公式中全部命題變項都解釋成詳細命題后，命題公式就成了真值確定命題了。比如，在命題公式(p∨q)→r中，若將p解釋成命題：2是素數，q解釋成：3是偶數，r解釋成：是無理數，則命題公式(p∨q)→r就被解釋成了一個真命題：若2是素數或3是偶數，則是無理數。(因p,q,r真值為1,0,1)；另首先，假如p,q解釋不變，而將r解釋成：是有理數，則(p∨q)→r就被解釋成了一個假命題。52/145定義設在命題公式A中出現全部命題變項為p1

,

p2,

…

pn

，給它們各指定一個真值，稱為對公式A一個賦值(或解釋)。若一個賦值使A真值為1，則稱該賦值為A成真賦值(或真賦值)，不然稱為A成假賦值（或假賦值)。注：設A中變項為p1

,

p2

,

…,

pn

，給A賦值a1

,

a2

,

…

an是指p1=a1,p2

=a2,…,pn=an，其中ai

為0或1,(i=1,2,…,n)。比如：公式(┐p1∧┐p2∧┐p3)∨(p1∧p2)中，000(即p1

=0,p2

=0,

p3=0)和110(即p1=1,p2=1,p3=0)都是成真賦值；而001(即p1=0,p2=0,p3=1)和011(即p1

=0,p2

=1,p3=1)都是成假賦值。53/145３. 公式真值表定義1.2.4 對于公式中命題變元每一個可能真值指派，以及由它們確定出公式真值所列成表，稱為該公式真值表。定義1.2.5 假如B是公式A中一部分，且B為公式，則稱B是公式A子公式。

54/145用歸納法不難證實，對于含有n個命題變元公式，有2n個真值指派，即在該公式真值表中有2n行。為方便結構真值表，特約定以下：①命題變元按字典序排列。②對每個指派，以二進制數從小到大或從大到小次序列出。③若公式較復雜，可先列出各子公式真值(若有括號，則應從里層向外層展開)，最終列出所求公式真值。55/145

例

求以下公式真值表。(1)(┐p∧q)→┐r;(2)(p∧┐p)?(q∧┐q);(3)┐(p→q)∧q∧rpqr┐p┐r┐p∧q(┐p∧q)→┐r00000101001110010111011111110000101010100011000011101111解：

(┐p∧q)→┐r真值表

56/145

(p∧┐p)?(q∧┐q)真值表

pq┐p┐qp∧┐pq∧┐q(p∧┐p)?(q∧┐q)0011001011000110010011100001┐(p→q)∧q∧r真值表

pqrp→q┐(p→q)┐(p→q)∧q┐(p→q)∧q∧r0001000001100001010000111000100010010101001101000111100057/1454. 命題符號化把一個用文字敘述命題對應地寫成由命題標識符、聯結詞和圓括號表示合式公式，稱為命題符號化。符號化應該注意以下事項:①確定給定句子是否為命題。②句子中連詞是否為命題聯結詞。③要正確地表示原子命題和適當選擇命題聯結詞。58/145命題符號化是很主要，一定要掌握好，在命題推理中經常最先碰到就是符號化一個問題，處理不好，等于說推理首要前提沒有了。59/1451.3公式分類與等價公式１.公式分類定義1.3.1 設A為任意公式，則①對應每一個指派，公式A均對應確定真值為真，稱A為重言式，或永真式。②對應每一個指派，公式A均對應確定真值為假，稱A為矛盾式，或永假式。③最少存在一個指派，公式A對應確定真值為真，稱A為可滿足式。60/145由定義可知，重言式必是可滿足式，反之普通不真。重點將研究重言式，它最有用，因為它有以下特點：①重言式否定是矛盾式，矛盾式否定是重言式，這么只研究其一就能夠了。②兩重言式合取式、析取式、條件式和雙條件式等都仍是重言式。于是，由簡單重言式可結構出復雜重言式。③由重言式使用公認規則能夠產生許多有用等價式和蘊涵式。61/145判定給定公式是否為永真式、永假式或可滿足式問題，稱為給定公式判定問題。在Ls中，因為任何一個命題公式指派數目總是有限，所以Ls判定問題是可解。其判定方法有真值表法和公式推演法。62/145２. 等價公式定義1.3.2

設A,B是兩個命題公式，若A,B組成等價式A?B為重言式，則稱A與B是等值,記為A?B。

顯然，若公式A和B真值表是相同，則A和B等值。所以，驗證兩公式是否等值，只需做出它們真值表即可。63/145例判斷公式┐(p∨q)與┐p∧┐q是否等值。解：用真值表法判斷┐(p∨q)?┐p∧┐q是否為重言式,真值表以下：pq┐p┐qp∨q┐(p∨q)┐p∧┐q┐(p∨q)?(┐p∧┐q)00110111011010011001100111001001從表中可見，┐(p∨q)?(┐p∧┐q)是重言式，故┐(p∨q)與┐p∨┐q等值。64/145在這里，請讀者注意

和

區分與聯絡。

是邏輯聯結詞，屬于目口號言中符號，它出現在命題公式中；

不是邏輯聯結詞，屬于元語言中符號，表示兩個命題公式一個關系，不屬于這兩個公式任何一個公式中符號。65/145等值式有以下性質：①自反性，即對任意公式A，有A

A。②對稱性，即對任意公式A和B，若A

B，則B

A。③傳遞性，即對任意公式A、B和C，若A

B、B

C，則A

C。

66/145３.基本等值式——命題定律當命題公式中變項較多時，用上述方法判斷兩個公式是否等值計算量很大。為此，人們將一組經檢驗為正確等值式作為運算規則，經過公式間等值演算來判斷兩公式是否等值。在判定公式間是否等值，有一些簡單而又經常使用等值式，稱為基本等值式或稱命題定律。牢靠地記住它并能熟練利用，是學好數理邏輯關鍵之一，讀者應該注意到這一點。67/145慣用運算規則以下：1.雙重否定律：A?┐(┐A)2.冪等律：A?A∨A,A?A∧A3.交換律:A∨B?B∨A,A∧B?B∧A4.結合律:(A∨B)∨C?A∨(B∨C),(A∧B)∧C?A∧(B∧C)5.分配律：A∨(B∧C)?(A∨B)∧(A∨C)(∨對∧分配律)A∧(B∨C)?(A∧B)∨(A∧C)(∧對∨分配律)6.德摩根律：┐(A∨B)?┐A∧┐B,┐(A∧B)?┐A∨┐B7.吸收律：A∨(A∧B)?A,A∧(A∨B)?A68/1458.零律：A∨1?1,A∧0?09.同一律：A∨0?A,A∧1?A10.排中律：A∨┐A?111.矛盾律：A∧┐A?012.蘊含等值式：A→B?┐A∨B13.等價等值式:(A?B)?(A→B)∧(B→A)14.假言易位律:A→B?┐B→┐A（逆否律）15.等價否定律:A?B?┐A?┐B16.歸謬律:(A→B)∧(A→┐B)?┐A

69/145

利用這16組24個等值式能夠推演出更多等值式。由已知等值式推演出另一些等值式過程稱為等值演算。在等值演算中,經慣用到以下置換規則。置換規則:設Φ(A)是含公式A命題公式，Φ(B)是用公式B置換了Φ(A)中全部A后所得公式。若B?A,則Φ(B)?Φ(A)。此規則可用數學歸納法證實。70/145

比如，對公式(p→q)→r,假如用┐p∨q置換其中p→q,則得(┐p∨q)→r.因為p→q?┐p∨q，故(p→q)→r?(┐p∨q)→r。類似地，可進行以下等值演算：(p→q)→r?(┐p∨q)→r(蘊含等值式，置換規則）?┐(┐p∨q)∨r(蘊含等值式，置換規則）?(p∧┐q)∨r(德摩根律，置換規則）?(p∨r)∧(┐q∨r)(分配律，置換規則）為簡便起見,以后凡用到置換規則時,均無須標出。71/145例用等值演算證實:(p∨q)→r?(p→r)∧(q→r)證：(p→r)∧(q→r)?(┐p∨r)∧(┐q∨r)(蘊含等值式)?(┐p∧┐q)∨r(分配律)?┐(p∨q)∨r(德摩根律)?(p∨q)→r(蘊含等值式)

注：用等值演算證實等值式時，既能夠從左向右推演，也能夠從右向左推演。72/145例證實：(p→q)→r?p→(q→r）證方法一：真值表法，略。方法二：觀察法。易見010是(p→q)→r成假賦值，而它卻是p→(q→r)成真賦值，故(p→q)→r?p→(q→r)。方法三:記A=(p→q)→r,B=p→(q→r)。先將A,B等值演算化成易于觀察真值公式，再進行判斷。

A=(p→q)→r?(┐p∨q)→r(蘊含等值式)?┐(┐p∨q)∨r(蘊含等值式)?(p∧┐q)∨r(德摩根律)B=p→(q→r)?┐p∨(┐q∨r)(蘊含等值式)?┐p∨┐q∨r(結合律)

易見，000，010是A成假賦值，而它們是B成真賦值。故(p→q)→r?p→(q→r)。73/145例用等值演算判斷以下公式類型(1)（p→q)∧p→q;(2)┐(p→(p∨q))∧r;(3)p∧(((p∨q)∧┐p)→q).解:(1)（p→q)∧p→q?(┐p∨q)∧p→q(蘊含等值式)?┐((┐p∨q)∧p)∨q(蘊含等值式)?(┐(┐p∨q)∨┐p)∨q(德摩根律)?((p∧┐q)∨┐p)∨q(德摩根律)?((p∨┐p)∧(┐q∨┐p))∨q(分配律)?(1∧(┐q∨┐p))∨q(排中律)?(┐q∨┐p)∨q（同一律）?(┐q∨q)∨┐p（交換律，結合律）?1∨┐p（排中律）?1（零律）故(p→q)∧p→q是重言式。74/145(2)┐(p→(p∨q))∧r?┐(┐p∨p∨q)∧r(蘊含等值式，結合律）

?(p∧┐p∧┐q)∧r(德摩根律）

?(0∧┐q)∧r(矛盾律）

?0∧r(零律)

?0(零律）故┐(p→(p∨q))∧r是矛盾式。75/145(3)p∧(((p∨q)∧┐p)→q)?p∧(┐((p∨q)∧┐p)∨q)(蘊含等值式)?p∧(┐((p∧┐p)∨(q∧┐p))∨q)(分配律)?p∧(┐(0∨(q∧┐p))∨q)(矛盾律)?p∧(┐(q∧┐p))∨q)(同一律)?p∧((┐q∨p)∨q)(德摩根律，雙重否定律)?p∧((┐q∨q)∨p)(交換律，結合律)?p∧(1∨p)（排中律）?p∧1（零律）?p（同一律）

可見，（3）中公式不是重言式，因為00，01都是成假賦值；它也不是矛盾式，因為10，11都是其成真賦值，故它是可滿足式。76/1451.4聯結詞擴充與功效完全組１.聯結詞擴充定義1.4.1設P和Q是任兩個原子命題，①由合取非聯結詞↑和P，Q連接成P↑Q，稱它為P和Q合取非式復合命題，讀作“P合取Q非”。P↑Q真值由命題P和Q真值確定：當且僅當P和Q均為Ｔ時，P↑Q為Ｆ，不然P↑Q為Ｔ。“合取非”又常稱為“與非”。77/145②由析取非聯結詞↓和P，Q連接成P↓Q，稱它為P和Q析取非式復合命題，讀作“P析取Q非”。P↓Q真值由P和Q真值確定：當且僅當P和Q均為Ｆ時，P↓Q為Ｔ，不然P↓Q為Ｆ。“析取非”又常稱為“或非”。③由異或(排斥或)聯結詞把P，Q連接成PQ，稱它為P和Q異或(排斥或)。PQ真值由P和Q真值確定：當且僅當P和Q真值不一樣時，PQ為Ｔ，不然PQ為Ｆ。78/14579/145由表可知，①P

Q

(P

Q) ②P

Q

(P

Q) ③PQ

(P

Q)

(

P

Q)

(P

Q)80/145２.與非、或非和異或性質與非、或非以及異或在計算機科學中是經常使用3個聯結詞，所以，掌握它們性質是十分必要。令P、Q和R是原子命題變元。①與非性質(a)P↑Q

Q↑P(b)P↑P

P(c)(P↑Q)↑(P↑Q)

P∧Q(d)(P↑P)↑(Q↑Q)

P∨Q81/145②或非性質(a)P↓Q

Q↓P(b)P↓P

P(c)(P↓Q)↓(P↓Q)

P∨Q(d)(P↓P)↓(Q↓Q)

P∧Q從上述性質可知，聯結詞

、

和

可分別用聯結詞

或者

取代，讀者能夠自行驗證，

和

都不滿足結合律。82/145③異或性質(a)P

Q

Q

P(b)P

(Q

R)

(P

Q)

R(c)P∧(Q

R)

(P∧Q)

(P∧R)(d)P

P

F，F

P

P，T

P

P(e)若P

Q

R，則Q

R

P，P

P

Q，且 P

Q

R

F。83/145以上全部性質，用真值表或命題定律都是不難證實。定義稱映射F:{0,1}n→{0,1}為n元真值函數。其中{0,1}n表示由0，1組成長為n字符串集合。2元真值函數有222=16個(每個真值函數可對應無窮多個命題公式,它們之間是等值.)84/145pqF0(2)F1(2)F2(2)F3(2)F4(2)F5(2)F6(2)F7(2)0000000000010000111110001100111101010101pqF8(2)F9(2)F10(2)F11(2)F12(2)F13(2)F14(2)F15(2)001111111101000011111000110011110101010185/145３.聯結詞全功效集已知有8個聯結詞就夠用了，能不能少呢？若能少，表明有些聯結詞邏輯功效可由其它聯結詞替換。實際上，也確實如此，因為有以下等價式：P

Q

(P

Q)P

Q

(P

Q)PQ

(P

Q)可見，擴充3個聯結詞

，

和能由原有5個聯結詞分別替換之。86/145又由命題定律：P

Q

(

P

Q)

(

Q

P)P

Q

P

QP

Q

(

P

Q)P

Q

(

P

Q)可知，原有5個聯結詞

，

，

，

和

又能由聯結詞組{

，

}或{

，

}取代。那么，終究最少用幾個聯結詞？就是說，用最少幾個聯結詞就能等價表示全部命題公式。或者說，用最少幾個聯結詞就能替換全部聯結詞功效。這便是所要定義聯結詞全功效集。87/145定義1.4.2稱G為聯結詞全功效集，假如G滿足條件：由G中聯結詞組成公式能等值表示任意命題公式；若還有G中任一聯結詞不能用其余下聯結詞等價表示，則稱它是極小全功效集。能夠證實，{

，

，，，?}，{，，

}，{

，，}都是聯結詞全功效集，而不是極小全功效集。{

，

}，{

，

}，{

，

}，{

}，{

}都是聯結詞極小全功效集。但為了表示方便，仍經常使用聯結詞組{

，

，

}。88/145注：能夠證實{∧,∨,→,?}不是聯結詞全功效集，其任何子集，如{∧}，{∨}，{∧,→}，{∧,∨,→}，{∧,∨,?}等也不是聯結詞完備集。設S1和S2是兩個不一樣聯結詞全功效集。用S1中聯結詞組成任何公式，必可等值轉化成用S2中聯結詞組成公式，反之亦然。所以，在某一特定系統中，只需采取一個聯結詞全功效集即可。但在不一樣應用中，人們往往采取不一樣聯結詞全功效集。比如，在計算機硬件設計中，慣用以下“與非門”或者“或非門”來設計邏輯線路。89/1451.5公式標準型——范式１.簡單合取式與簡單析取式定義1.5.1在一公式中，僅由有限個命題變元及其否定組成合取式，稱該公式為簡單合取式，其中每個命題變元或其否定，稱為合取項。定義1.5.2在一公式中，僅由有限個命題變元及其否定組成析取式，稱該公式為簡單析取式，其中每個命題變元或其否定，稱為析取項。90/145比如，公式P，

Q，P

Q和

P

Q

P等都是簡單合取式，而P，Q和

P為對應簡單合取式合取項；公式P，

Q，P

Q，

P

Q

P等都是簡單析取式，而P，Q和

P為對應簡單析取式析取項。注意，一個命題變元或其否定既能夠是簡單合取式，也可是簡單析取式，如例中P，

Q等。91/145定理1.5.1簡單合取式為永假式充要條件是：它同時含有某個命題變元及其否定。定理1.5.2簡單析取式為永真式充要條件是：它同時含有某個命題變元及其否定。92/145２.析取范式與合取范式定義1.5.3一個命題公式A稱為析取范式，當且僅當A可表為有限個簡單合取式析取。定義1.5.4一個命題公式A稱為合取范式，當且僅當A可表為有限個簡單析取式合取。93/145定理1.5.3對于任何一命題公式，都存在與其等價析取范式和合取范式。求范式算法：①使用命題定律，消去公式中除

、

和

以外公式中出現全部聯結詞；②使用

(

P)

P和德·摩根律，將公式中出現聯結詞

都移到命題變元之前；③利用結合律、分配律等將公式化成析取范式或合取范式。94/145例求公式(p→q)?r析取范式與合取范式。解:(1)合取范式：(p→q)?r?(┐p∨q)?r(消去→)

?((┐p∨q)→r)∧(r→(┐p∨q))

(消去?)

?(┐(┐p∨q)∨r)∧(┐r∨(┐p∨q))(消去→)

?((p∧┐q)∨r)∧(┐p∨q∨┐r)(否定號內移,結合律,交換律)

?(p∨r)∧(┐q∨r)∧(┐p∨q∨┐r)(∨對∧分配律)(2)析取范式(p→q)?r?((p∧┐q)∨r)∧(┐p∨q∨┐r)(見上述第一至四步)?(p∧┐q∧┐p)∨(p∧┐q∧q)∨(p∧┐q∧┐r)∨(r∧┐p)∨(r∧q)∨(r∧┐r)(∧對∨分配律)?(p∧┐q∧┐r)∨(┐p∧r)∨(q∧r)(矛盾律和同一律)95/145３.范式應用利用析取范式和合取范式可對公式進行判定。定理1.5.4公式A為永假式充要條件是A析取范式中每個簡單合取式最少包含一個命題變元及其否定。定理1.5.5公式A為永真式充要條件是A合取范式中每個簡單析取式最少包含一個命題變元及其否定。96/145４.范式不唯一性97/145對偶式在上節介紹命題定律中，多數是成對出現，這些成對出現定律就是對偶性質反應，即對偶式。利用對偶式命題定律，能夠擴大等價式個數，也可降低證實次數。98/145定義在給定僅使用聯結詞

、∧和∨命題公式A中，若把∧和∨交換，F和T交換而得到一個命題公式A*，則稱A*為A對偶式。顯然，A也是A*對偶式。可見A與A*互為對偶式。99/145定理(對偶定理)設A和A*互為對偶式，P1，P2，…，Pn是出現A和A*中原子命題變元，則①

A(P1，P2，…，Pn)

A*(

P1，

P2，…，

Pn)②A(

P1，

P2，…，

Pn)

A*(P1，P2，…，Pn)①表明，公式A否定等價于其命題變元否定對偶式；②表明，命題變元否定公式等價于對偶式之否定。100/145定理設A和B為兩個命題公式，若A

B則A*

B*。101/1451.6公式主范式范式基本處理了公式判定問題。但因為范式不唯一性，對識別公式間是否等價帶來一定困難，而公式主范式處理了這個問題。下面將分別討論主范式中主析取范式和主合取范式。102/145１.主析取范式(1)極小項概念和性質定義1.6.1在含有n個命題變元簡單合取式中，若每個命題變元與其否定不一樣時存在，而二者之一出現一次且僅出現一次，則稱該簡單合取式為極小項。103/145比如，兩個命題變元P和Q，其組成極小項有P

Q，P

Q，

P

Q和

P

Q；而三個命題變元P、Q和R，其組成極小項有P

Q

R，P

Q

R，P

Q

R，P

Q

R，

P

Q

R，

P

Q

R，

P

Q

R，

P

Q

R。能夠證實，n個命題變元共形成2n個極小項。104/145假如將命題變元按字典序排列，而且把命題變元與1對應，命題變元否定與0對應，則可對2n個極小項依二進制數編碼，記為mi，其下標i是由二進制數轉化十進制數。用這種編碼所求得2n個小項真值表，可顯著地反應出極小項性質。下表分別給出了2個命題變元P和Q、3個命題變元P、Q和R極小項真值表。105/145極小項極大項公式成真賦值名稱公式成假賦值名稱┐p∧┐q00m0p∨q00M0┐p∧q01m1p∨┐q01M1p∧┐q10m2┐p∨q10M2p∧q11m3┐p∨┐q11M3兩個變項p、q形成極小項與極大項

106/145極小項

極大項

公式成真賦值名稱公式成假賦值名稱┐p∧┐q∧┐r000m0p∨q∨r000M0┐p∧┐q∧r001m1p∨q∨┐r001M1┐p∧q∧┐r010m2p∨┐q∨r010M2┐p∧q∧r011m3p∨┐q∨┐r011M3p∧┐q∧┐r100m4┐p∨q∨r100M4p∧┐q∧r101m5┐p∨q∨┐r101M5p∧q∧┐r110m6┐p∨┐q∨r110M6p∧q∧r111m7┐p∨┐q∨┐r111M7三個變項p,q,r形成極小項與極大項107/145從表中可看出，極小項有以下性質：(a)沒有兩個極小項是等值，即是說各小項真值表都是不一樣；(b)任意兩個不一樣極小項合取式是永假：mi∧mj

Ｆ，i≠j。(c)全部極小項之析取為永真：mi

Ｔ。(d)每個極小項只有一個解釋為真。108/145(2)主析取范式定義與存在定理定義1.6.2在給定公式析取范式中，若其簡單合取式都是極小項，則稱該范式為主析取范式。定理1.6.1任意含n個命題變元命題公式A都存在主析取范式，而且是唯一。（見書上定理1.5）109/145(3)主析取范式求法主析取范式求法有兩種：真值表法和公式化歸法。定理1.6.1證實已給出了用真值表求主析取范式方法，而公式化歸法給出以下：(a)把給定公式化成析取范式；(b)刪除析取范式中全部為永假簡單合取式；110/145(c)用等冪律化簡簡單合取式中同一命題變元重復出現為一次出現，如P∧P

P。(d)用同一律補進簡單合取式中未出現全部命題變元，如Q，則P

P∧

Q∨Q)，并用分配律展開之，將相同簡單合取式屢次出現化為一次出現，這么得到了給定公式主析取范式。111/145２.主合取范式(1)極大項概念和性質定義1.6.3在n個命題變元簡單析取式中，若每個命題變元與其否定不一樣時存在，而二者之一必出現一次且僅出現一次，則稱該簡單析取式為極大項。112/145比如，由兩個命題變元P和Q，組成極大項有P

Q，P

Q，

P

Q，

P

Q；三個命題變元P，Q和R，組成P

Q

R，P

Q

R，P

Q

R，P

Q

R，

P

Q

R，

P

Q

R，

P

Q

R，

P

Q

R。能夠證實，n個命題變元共有2n個極大項。113/145假如將n個命題變元排序，而且把命題變元與０對應，命題變元否定與１對應，則可對2n個極大項按二進制數編碼，記為Mi，其下標i是由二進制數化成十進制數。用這種編碼所求2n個極大項真值表，能直接反應出極大項性質。114/145類似可給出３個命題變元Ｐ、Ｑ和Ｒ全部極大項真值表，留給大家完成。從前表中可看出極大項性質：(a)沒有兩個極大項是等價。(b)任何兩個不一樣極大項之析取是永真，即Mi∨Mj

Ｔ，i≠j。(c)全部極大項之合取為永假，即Mi

Ｆ。(d)每個極大項只有一個解釋為假。115/145(2)主合取范式定義與其存在定理定義1.6.4在給定公式合取范式中，若其全部簡單析取式都是極大項，稱該范式為主合取范式。定理1.6.3任意含有n個命題變元非永真命題公式A，都存在與其等價主合取范式。定理1.6.4任意含n個命題變元非永真命題公式A，其主合取范式是唯一。主合取范式求法也有兩種，類似于主析取范式求法。116/145３.主析取范式與主合取范式關系因為主范式是由極小項或極大項組成，從極小項和極大項定義，可知二者有以下關系：

mi

Mi

Mi

mi所以，主析取范式和主合取范式有著“互補”關系，即是由給定公式主析取范式能夠求出其主合取范式。117/145

設命題公式A中含有n個命題變元，且A主析取范式中含k個極小項，則

A主析取范式中必含有2n-k個極小項，不妨設為，，…，，即

A

∨∨…∨。于是

A

A

( ∨∨…∨ )

∧

∧…∧

∧∧…∧118/145由此可知，從A主析取范式求其主合取范式步驟為：(a)求出A主析取范式中沒有包含極小項。(b)求出與(a)中極小項下標相同極大項。(c)做(b)中極大項之合取，即為A主合取范式。比如，(P

Q)

Q

m1

m3，則(P

Q)

Q

M0

M2。119/145例求公式(p→q)?r主析取范式和主合取范式。解:(1)主析取范式由前例知，(p→q)?r?(p∧┐q∧┐r)∨(┐p∧r)∨(q∧r)∵(┐p∧r)?┐p∧(┐q∨q)∧r

?(┐p∧┐q∧r)∨(┐p∧q∧r)

?m1∨m3(q∧r)?(┐p∨p)∧q∧r?(┐p∧q∧r)∨(p∧q∧r)?m3∨m7（p∧┐q∧┐r)?m4∴(p→q)?r?m1∨m3∨m4∨m7120/145(2)

主合取范式由前例知，(p→q)?r?(p∨r)∧(┐q∨r)∧(┐p∨q∨┐r)∵(p∨r)?p∨(q∧┐q)∨r?(p∨q∨r)∧(p∨┐q∨r)?M0∧M2(┐q∨r)?(p∧┐p)∨┐q∨r?(p∧┐q∨r)∧(┐p∨┐q∨r)?M2∧M6(┐p∨q∨┐r)?M5∴(p→q)?r?M0∧M2∧M5∧M6121/145４.主范式應用利用主范式能夠求解判問題或者證實等價式成立。（1）判定問題依據主范式定義和定理，也能夠判定含n個命題變元公式，其關鍵是先求出給定公式主范式Ａ；其次按以下條件判定之：(a)若A

Ｔ，或A可化為與其等價、含2n個小項主析取范式，則A為永真式。122/145(b)若A

Ｆ，或A可化為與其等價、含2n個大項主合取范式，則A為永假式。(c)若A不與Ｔ或者Ｆ等價，且又不含2n個小項或者大項，則A為可滿足。（2）證實等價式成立因為任一公式主范式是唯一，所以將給定公式求出其主范式，若主范式相同，則給定兩公式是等價。123/145例利用公式主析取范式判斷公式類型：(1)┐(p→q)∧q;(2)p→(p∨q);(3)(p∨q)→r解：(1)┐(p→q)∧q?┐(┐p∨q)∧q?p∧┐q∧q?0.

故

┐(p→q)∧q是矛盾式。

(2)p→(p∨q)?┐p∨p∨q

?(┐p∧(┐q∨q))∨(p∧(┐q∨q))∨((┐p∨p)∧q)

?(┐p∧┐q)∨(┐p∧q)∨(p∧┐q)∨(p∧q)∨(┐p∧q)∨(p∧q)

?(┐p∧┐q)∨(┐p∧q)∨(p∧┐q)∨(p∧q)

?m0∨m1∨m2∨m3`該主析取范式含全部22個極小項，故p→(p∨q)是重言式。注：另一個推演：p→(p∨q)?┐p∨p∨q?1∨q?1?m0∨m1∨m2∨m3124/145(3)（p∨q)→r?┐(p∨q)∨r

?(┐p∧┐q)∨r

?(┐p∧┐q∧(┐r∨r))∨((┐p∨p)∧(┐q∨q)∧r)?(┐p∧┐q∧┐r)∨(┐p∧┐q∧r)∨(┐p∧┐q∧r)∨(┐p∧q∧r)∨(p∧┐q∧r)∨(p∧q∧r)

?m0∨m1∨m3∨m5∨m7故該公式是可滿足式,但不是重言式。

125/1451.7命題邏輯推理理論在邏輯學中，把從前題（又叫公理或假設）出發，依據公認推理規則，推導出一個結論，這一過程稱為有效推理或形式證實。所得結論叫做有效結論，這里最關心不是結論真實性而是推理有效性。前提實際真值不作為確定推理有效性依據。不過，假如前提全是真，則有效結論也應該真而絕非假。126/145在數理邏輯中，集中注意是研究和提供用來從前提導出結論推理規則和論證原理，與這些規則相關理論稱為推理理論。提請注意，必須把推理有效性和結論真實性區分開。有效推理不一定產生真實結論，產生真實結論推理過程未必一定是有效。再說，有效推理中可能包含假前提；而無效推理卻可能包含真前提。127/145可見，推理有效性是一回事，前提與結論真實是否是另一回事。所謂推理有效，指它結論是它前提合乎邏輯結果，也即，假如它前提都為真，那么所得結論也必定為真，而并不是要求前提或結論一定為真或為假。假如推理是有效話，那么不可能它前提都為真時而它結論為假。128/145１.推理基本概念和推理形式推理也稱論證，它是指由已知命題得到新命題思維過程，其中已知命題稱為推理前提或假設，推得新命題稱為推理結論。在數理邏輯中，前提H是一個或者n個命題公式H1,H2,···Hn；結論是一個命題公式C。由前提到結論推理形式可表為H1,H2,···,Hn

C，其中符號

表示推出···。可見，推理形式是命題公式一個有限序列，它最終一個公式是結論，余下為前提或假設。129/145定義1.7.1假如存在H1，H2，…，Hn，C一個指派，使得每個Hi(1≤i≤n)為真而C為假推理形式H1，H2，…，Hn

C是無效；不然，推理是有效，此時稱C是H1，H2，…，Hn有效結論，或稱C是從前提H1，H2，…，Hn邏輯推出結論。定理1.7.1推理形式H1，H2，…，Hn

C是有效，當且僅當命題公式(H1∧H2∧…∧Hn)→C是永真式，亦即(H1∧H2∧…∧Hn)

C。130/1452.推理定律在研究推理過程中，人們發覺了一些主要重言蘊含式，并將它們作為推理定律，在推理過程中可直接引用。慣用推理定律有：(1)附加律:A

A∨B(2)化簡律:A∧B

A(3)假言推理:(A→B)∧A

B(4)拒取式:(A→B)∧┐B

┐A(5)析取三段論:(A∨B)∧┐B

A131/145假言三段論:(A→B)∧(B→C)

(A→C)等價三段論:(A?B)∧(B?C)

(A?C)結構性二難:(A→B)∧(C→D)∧(A∨C)

(B∨D)結構性二難(特殊形式):(A→B)∧(┐A→B)∧(A∨┐A)

B破壞性二難:(A→B)∧(C→D)∧(┐B∨┐D)

(┐A∨┐C)132/145另外,前面給出24個等值式中每一個都派生出兩條推理定律.比如┑┑A

A產生出┑┑A

A和A

┑┑A.還有一些等值式和重言蘊含式可在推理中引用。如:A

(A∧B)∨(A∧┐B)┐(A→B)

A∧┐BA→(B→C)

(A∧B)→C(A?B)

(A∧B)∨(┐A∧┐B)133/145┐(A?B)

A?┐B┐A

A→BB

A→BA→B

(A∨C)→(B∨C)A→B

(A∧C)→(B∧C)因為推理定律是確定有效結論不可缺乏主要依據，所以要切記并熟練利用它們。134/1453.推理規則在數理邏輯中，從前提推導出結論，要依據事先提供公認推理規則，它們是：①Ｐ規則(也稱前提引入規則)：在推導任一步驟上，前提可視需要引入使用。②Ｔ規則(也稱結論引入規則)：在推導任一步驟上，前面已導出有效結論都可作為后續推導前提引入。③置換規則：在證實任何步驟上,命題公式中子公式都能夠用與之等值公式置換。之前九條推理定律能夠按照結論引入規則在證實中引用。（見教材第23頁）135/145例.結構下面推理證實:前提:p∨q,q→r,p→s,┐s結論:r∧(p∨q)證實:①p→s前提引入②

┐s前提引入③

┐p①②拒取式④

p∨q前提引入⑤q③④析取三段式⑥q→r前提引入⑦r⑤⑥假言推理⑧r∧(p∨q)⑦④合取136/145前提:┐p∨q,r∨┐q,r→s結論:p→s證實:┐p∨q前提引入p→q①置換r∨┐q前提引入q→r③置換p→r②④假言三段論r→s前提引入⑦p→s