離散數學課件：1-2 命題公式及分類

1、 命題公式命題公式(合式公式合式公式) (wff, well formed formula) ：(1)單個命題變元本身是一個命題公式單個命題變元本身是一個命題公式.(2)如果如果A和和B是命題公式，那么是命題公式，那么 A, (A B), ( A B), (A B), (A B)都是命題公式都是命題公式.(3)當且僅當能夠當且僅當能夠有限次有限次地應用地應用(1), (2)生成的公式是命生成的公式是命題公式題公式.(一一) 命題公式的概念命題公式的概念 用定義說明下列字符串是否為合式公式用定義說明下列字符串是否為合式公式解題思想：解題思想：嚴格按定義判斷，但習慣上可嚴格按定義判斷，但習慣上可以

2、省去外層括號。以省去外層括號。(1) (P Q)(2)P (P Q)(3) ( P Q) (P R)(5) PQR 二、命題公式及分類二、命題公式及分類(4) (P Q) ( Q)(6)(P Q, (P Q) Q) 聯結詞運算的次序聯結詞運算的次序&沒有括號時按強弱先后順序執(zhí)行沒有括號時按強弱先后順序執(zhí)行.&運算符結合力的強弱順序約定為：運算符結合力的強弱順序約定為： , , , , .&要養(yǎng)成要養(yǎng)成“先先 后后 ”的習慣的習慣.&相同運算符按從左至右順序執(zhí)行，括號可省去相同運算符按從左至右順序執(zhí)行，括號可省去.例如，例如， (A B) C與與A B C運算順序

3、一樣運算順序一樣.&最外層的括號總可以省去最外層的括號總可以省去.例如，例如， (A B) 常寫為常寫為A B.下式的運算順序是怎樣的？下式的運算順序是怎樣的？ P S Q R R P Q與與( P S) ( Q R) (R P) Q)運算順序相同運算順序相同.答：答：二、命題公式及分類二、命題公式及分類(二二)命題公式的指派命題公式的指派 P1, P2, , Pn為出現在為出現在A中中的所有的命題變項的所有的命題變項,由由A的真值將每次賦值分為的真值將每次賦值分為成真成真指派指派和和成假成假指派指派. 設設A為一命題公式，為一命題公式， 一個含有命題變元的命題公式的真值是不確一個含有

4、命題變元的命題公式的真值是不確定的，因此有必要對它的真值進行具體的分析定的，因此有必要對它的真值進行具體的分析.二、命題公式及分類二、命題公式及分類 P1, P2, , Pn指定一組真值，指定一組真值，就是對就是對A的一個的一個指派指派.真值表：真值表：將含有將含有n個命題變個命題變元元的命題公式按的命題公式按字典字典順序進行順序進行2n組賦值后所得真值表組賦值后所得真值表, 稱為稱為該命題公式的真值表該命題公式的真值表.(三三)真值表真值表二、命題公式及分類二、命題公式及分類(1) 將變元按一定順序排出，再按從內到外將變元按一定順序排出，再按從內到外的順序列出公式的各個的順序列出公式的各個運

5、算層次運算層次，將它，將它們排在表頭上；們排在表頭上；(2) 如有如有n個變元，則所有可能的賦值有個變元，則所有可能的賦值有2n組，組，每組可用每組可用n位的二進制數表示，按字典順位的二進制數表示，按字典順序每行排一組序每行排一組;(3) 在表上由左到右填寫相應的真值在表上由左到右填寫相應的真值.二、命題公式及分類二、命題公式及分類真值表的構造真值表的構造構造構造 P Q 的真值表的真值表.解：解：PQ P P QTTTFFTFFF F TTT F TT二、命題公式及分類二、命題公式及分類真值表的構造真值表的構造構造構造 (P Q) ( P Q)的真值表的真值表.解：解：PQP Q P TTT

6、FFTFFT F FFF F TT (P Q)F T T T Q F T FT P QF T TT二、命題公式及分類二、命題公式及分類PQTTTFFTFF (P Q)F T T T P QF T TT (P Q) ( P Q)T T TT& (P Q) ( P Q)的真值全為真，這類公式稱為的真值全為真，這類公式稱為永真永真公式公式，記為，記為T.(另有另有永假公式永假公式，記為，記為F. )& (P Q) 與與 ( P Q)的所有真值相同，稱二者是的所有真值相同，稱二者是等價等價的的.真值表的構造真值表的構造構造構造 (P Q) ( P Q)的真值表的真值表.解：解：二、命題

7、公式及分類二、命題公式及分類(四四)命題公式的類型命題公式的類型&重言式重言式(tautology)(永真公式永真公式)：無論對分量作：無論對分量作怎樣的指派，其對應的真值永為怎樣的指派，其對應的真值永為T，記為記為T.例如，例如， (P Q) ( P Q) 是是重言式重言式.&任何兩個重言式的合取或析取，仍然是一個任何兩個重言式的合取或析取，仍然是一個重言式重言式.(A為為T，B為為T，A與與B合取合取(或析取或析取)仍仍為為T.)&一個重言式，對同一分量都用任何一個重言式，對同一分量都用任何Wff置換，置換，其結果仍為一重言式其結果仍為一重言式.(因為重言式的真值與因為重言式的真值與分量的指派無關分量的指派無關.)二、命題公式及分類二、命題公式及分類&矛盾式矛盾式(contradiction or absurdity)(永假公式永假公式)：無論對分量作怎樣的指派，其對應的真值永為無論對分量作怎樣的指派，其對應的真值永為F ，記為記為F.&任何兩個矛盾式的合取或析取，仍然是一個任何兩個矛盾式的合取或析取，仍然是一個矛盾式矛盾式.&一個矛盾式，對同一分量都用任何一個矛盾式，對同一分量都用任何Wff置換