第1章命題邏輯
本章重點：命題與聯結詞，公式與解釋，真值表，公式的型別及判定, (主)析取(合取)正規化，命題邏輯的推理理論.
一、重點內容
1. 命題
命題表述為具有確定真假意義的陳述句。命題必須具備二個條件：其一，語句是陳述句；其二，語句有唯一確定的真假意義.
2. 六個聯結詞及真值表
「」否定聯結詞，p是命題，p是p的否命題，是由聯結詞和命題p組成的復合命題.p取真值1，p取真值0，p取真值0，p取真值1. 它是一元聯結詞.
「」合取聯結詞，pq是命題p，q的合取式，是「」和p，q組成的復合命題. 「」在語句中相當於「不但…而且…」，「既…又…」. pq取值1，當且僅當p，q均取1；pq取值為0，只有p，q之一取0.
「」析取聯結詞，「」不可兼析取(異或)聯結詞， pq是命題p，q的析取式，是「」和p，q組成的復合命題. pq是聯結詞「」和p，q組成的復合命題. 聯結詞「」或「」在乙個語句中都表示「或」的含義，前者表示相容或，後者表示排斥或不相容的或.
即「pq」「(pq)(pq)」. pq取值1，只要p，q之一取值1，pq取值0，只有p，q都取值0.
「」蘊含聯結詞， pq是「」和p，q組成的復合命題，只有p取值為1，q取值為0時，pq取值為0；其餘各種情況，均有pq的真值為1，亦即10的真值為0，01，11，00的真值均為1. 在語句中，「如果p則q」或「只有q，才p，」表示為「pq」.
「」 等價聯結詞，pq是p，q的等價式，是「」和p，q組成的復合命題. 「」在語句中相當於「…當且僅當…」，pq取值1當且僅當p，q真值相同.
3. 命題公式、賦值與解釋，命題公式的分類與判別
命題公式與賦值，命題p含有n個命題變項p1，p2,…,pn，給p1，p2,…,pn各指定乙個真值，稱為對p的乙個賦值(真值指派). 若指定的一組值使p的真值為1，則這組值為p的真指派；若使p的真值為0，則稱這組值稱為p的假指派.
命題公式分類，在各種賦值下均為真的命題公式a，稱為重言式(永真式)；在各種賦值下均為假的命題公式a，稱為矛盾式(永假式)；命題a不是矛盾式，稱為可滿足式；
判定命題公式型別的方法：其一是真值表法，任給公式，列出該公式的真值表，若真值表的最後一列全為1，則該公式為永真式；若真值表的最後一列全為0，則該公式是永假式；若真值表的最後一列既非全1，又非全0，則該公式是可滿足式.其二是推導演演算法.
利用基本等值式(教材p.16的十六個等值式或演算律)，對給定公式進行等值推導，若該公式的真值為1，則該公式是永真式；若該公式的真值為0，則該公式為永假式.既非永真，也非用假，成為非永真的可滿足式.
其三主析取(合取)正規化法，該公式的主析取正規化有2n個極小項(即無極大項)，則該公式是永真式；該公式的主合取正規化有2n個極大項(即無極小項)，則該公式是永假式；該公式的主析取(或合取)正規化的極小項(或極大項)個數大於0小於2n,，則該公式是可滿足式.
等值式ab，命題公式a，b在任何賦值下，它們的真值均相同，稱a，b等值。
定理1 設(a)是含命題公式a的命題，(b)是用命題公式b置換(a)中的a之後得到的命題公式. 如果ab，則(a)(b).
4. 正規化
析取(合取)正規化，僅有有限個簡單合取式(析取式)構成的析取式(合取式)，就是析取(合取)正規化.
極小項(極大項)，n個命題變項p1,p2,…,pn，每個變項或它的否定兩者只有其一出現且僅出現一次，第i個命題變項或者其否定出現在從左起第i個位置上(無腳標時，按字典序排列)，這樣的簡單合取式(析取式)為極小項(極大項).
以兩個命題變項為例，m00=pq，m01=pq,m10=pq,m11=pq是極小項;m00=pq，m01=pq,m10=pq,m11=pq是極大項.
主析取正規化(主合取正規化) 含有n個命題變項的命題公式，如果與乙個僅有極小項(極大項)的析取(合取)構成的析取(合取)正規化等值，則該等值式稱為原命題公式的主析取(合取)正規化。
每項含有n個命題變項(變項字母齊全)的合取式(析取式)的析取(合取)為主析取(合取)正規化.
任意命題公式都存在與之等值的正規化，存在與之等值的主正規化，且是惟一的.
求正規化，包括求析取正規化、合取正規化、主析取正規化和主合取正規化. 關鍵有兩點：其一是準確掌握正規化定義；其二是巧妙使用基本等值式中的分配律、同一律和摩根律，結果的前一步適當使用冪等律.
求析取(合取)正規化的步驟：
① 將公式中的聯結詞都化成，，(即消去個數中的聯結詞，，)；
② 將否定聯結詞消去或移到各命題變項之前；
③ 利用分配律、結合律等，將公式化為析取(合取)正規化.
求命題公式a的主析取(合取)正規化的步驟
① 求公式a的析取(合取)正規化；
② 「消去」析取(合取)正規化中所有永假式(永真式)的析取項(合取項)，如pp(pp)用0(1)替代. 用冪等律將析取(合取)正規化中重複出現的合取項(析取項)或相同的變項合併，如pp(pp)用p替代，mimi(mimi)用mi(mi)替代.
③ 若析取(合取)正規化的某個合取項(析取項)b不含有命題變項pi或pi，則新增pipi(pipi)，再利用分配律展開，使得每個合取項(析取項)的命題變項齊全；
④ 將極小(極大)項按由小到大的順序排列，用()表示.
5. 命題演算的推理理論
設a1,a2,…,an,c是命題公式，如果是重言式，稱c是前提集合的有效結論或邏輯地推出c。記作
掌握演繹或形式證明. 要理解並掌握14個重言蘊含式(即i1～i14)，17個等值式(e1～e17)；二是會使用三個規則(p規則、t規則和cp規則)。
推理方法有：
真值表法；等值演演算法；主析取正規化法，構造證明法(直接證明法、附加前提證明法和間接證明法)
二、例項
例1.1 判別下列語句是否命題？如果是命題，指出其真值.
(1) 中國是乙個人口眾多的國家. (2) 存在最大的質數.
(3) 這座樓可真高啊4) 請你跟我走!
(5) 火星上也有人.
解 (1) 是命題，真值為12) 是命題，真值為0.
(3), (4)不是命題因為不是陳述句.
(5) 是命題. 真值是唯一的，遲早會被指出.
例1.2 將下列命題符號化：
(1) 雖然交通堵塞，但是老王還是準時到達火車站
(2) 張力是三好生，他是北京人或是天津人.
(3) 除非天下雨，否則我騎車上班.
解 (1) 設p：交通堵塞，q：老王準時到達火車站.
該命題符號化為：pq.
(2)設p：張力是三好生； q：張力是北京人，r：張力是天津人.
該命題符號化為p(qr ).
(3)設p：天下雨，q：我不騎車上班.
該命題符號化為：qp，義即「只有天下雨，我才不騎車上班」，不下雨是我騎車上班的必要條件。它的等價說法是「如果天不下雨，我就騎車上班」，即pq
「如果天下雨，我就不騎車上班」，這是蘊含關係，符號化為：pq
注：本例各小題都是復合命題。如「李枚和張櫻花是好朋友」是簡單命題，用字母p表示。顯然p：李枚是好朋友，q：張櫻花是好朋友，符號化為qp是不通的.
例1.3 證明：p(qr)pqr.
證明方法1 真值表法. 列公式p(qr)與pqr的真值表如表1－1. .
表1－1 公式p(qr)與pqr的真值表
由表可知，公式p(qr)與pqr的真值完全相同，故p(qr)pqr..
或由表的最後一列可知，pqpq是重言式，故p(qr)pqr.
注：作為本例的證明可以不要最後1列。若本例改為判斷p(qr)pqr的型別，由最後列可知p(qr)pqr是重言式.
方法2 等值演演算法.
p（qr）
p(qr等值蘊含式)
p(qr等值蘊含式)
（pq）r結合律)
(pq)r摩根律)
pqr等值蘊含式)
所以，p（qr）(pq)r
例中等值演算的每一步都用到了置換規則. 由等值演算的傳遞性，可知第乙個公式p(qr)和最後乙個公式pq)r等值.
方法3 主正規化法.
p(qr)p(qr)pqr(主合取正規化)
pqr(pq)rpqr(主合取正規化)
p(qr)與pqr的主合取正規化相同，故p(qr)pqr。
注：(1)容易寫出p(qr)與pqr的主析取正規化均為m0m1m2m3m4m5m7即pqr)(pqr)(pqr)
pqr)(pqr)(pqr) (pqr)
(2) 由真值表求公式p(qr)的主析取正規化，先列出p(qr)的真值表，見表1－1。主析取正規化是公式p(qr)真值為1的項的析取，真值為1的項，即極小項，有第1,2,3,4,5,6,8共7項. 而極小項是合取式，合取式為1，必定是每個變元或其否定為1，如表1－1中第1行p，q，r均取1，所以這一項為pqr，類似地，7個極小項為：
pqr，pqr，pqr，pqr，pqr，pqr，pqr
所以p(qr)的主析取正規化為：
(pqr)(pqr)(pqr)
pqr)(pqr)(pqr) (pqr)
例1.4 用等值演演算法判定公式p(qr)pqr是永真式？永假式？可滿足式？
解等值運演算法.
p(qr)pqr(p(qr)pqr
p(qr)p(qr))pqr
p(qr))(pqr))pqr
離散數學複習
例題1 設是群，是的子群，在g上定義關係r r 證明 r是集合g上的等價關係。證明 即證明r為自反 對稱和傳遞關係。1 證自反 是子群，則h中必然存在么元，設為e。則ag，eh，a a e，所以 r，所以，r為自反關係。2 證對稱 a,bg,若r，則hh，a b h，因為是子群，則h必然具有逆元h ...
離散數學複習指導
第一部分數理邏輯 第七章二元關係 9.1二元運算及其性質 11.1格的定義與性質 第五部分圖論 命題邏輯 一至三章 1 求命題公式的真值表 知識 p7表1.1 例題 p9例1.8 2等值演算 知識 p17基本等值式 例題 p19例2.3 3 判斷公式的型別 知識 p10定義1.10 例題 用真值表法...
離散數學複習提綱
3 設p，q 的真值為0，r，s的真值為1，則 的真值4 公式的主合取正規化為 5 若解釋i的論域d僅包含乙個元素，則在i下真值為 1.在自然推理系統p中構造下面推理的證明 只要a曾到過受害者房間並且11點以前沒離開，a就是 嫌犯。a曾到過受害者房間。如果a在11點以前離開，看門人會看見他。看門人沒...