【正文】 (3)∨ 是自然語言中的 “ 或 ” 和 “ 或者 ” 等的邏輯抽象；但 “ 或 ” 有 “ 可兼或 ” ﹑ “不可兼或 ” ﹑ “近似或 ” 三種 (4)P→Q是自然語言中的 “ 只要 P， 就 Q” ﹑ “因為P， 所以 Q” ﹑ “P僅當(dāng) Q”等的邏輯抽象 25/73 (5) ?是自然語言中的 “ 充分必要條件 ” 和 “ 當(dāng)且僅當(dāng) ” 等的邏輯抽象 (6)聯(lián)結(jié)詞連接的是兩個命題真值之間的聯(lián)結(jié) ， 而不是命題內(nèi)容之間的連接 ， 因此復(fù)合命題 的真值只取決于構(gòu)成他們的各原子命題的真 值 (7) ∧ ， ∨ ， ?具有對稱性 ， 而 172。， →沒有 (8) ∧ ， ∨ ， 172。與計算機(jī)中的與門 ， 或門 ， 非門電路是相對應(yīng)的 看 P67 例 ， P9 例 命題與命題聯(lián)結(jié)詞 26/73 ：命題公式 就像在代數(shù)學(xué)里引入變量一樣 ， 為了更廣泛的應(yīng)用命題演算 ， 在數(shù)理邏輯中也引入了命題變量 。 使得在研究時 ， 只需考慮命題的真值 ， 而不知曉命題的具體含義 。 ?定義 ： 一個特定的命題是一個常值命題 (Constant Proposition)， 它不是具有值 “ T”(“1”)， 就是具有值 “ F”(“0”)。 而一個任意的沒有賦予具體內(nèi)容的原子命題是一個變量命題 ， 常稱它為命題變量 (或命題變元 、 命題變項 )(Proposition Variable)。 命題變量無具體的真值 ， 它的值域是集合 {T， F}(或 {1， 0})。 公式的解釋與真值表 27/73 ?原子命題在不指派真值時稱為命題變元 ， 而復(fù)合命題由原子命題和聯(lián)結(jié)詞構(gòu)成 ， 可以看作是命題變元的函數(shù) ， 且該函數(shù)的值仍為“ 真 ” 或 “ 假 ” ， 可以稱為真值函數(shù) （ True Value Function） 或命題公式 。 但不是說原子命題和聯(lián)結(jié)詞的一個隨便的組合都可以為命題公式 ， 我們用遞歸的方法來定義命題公式 。 公式的解釋與真值表 28/73 公式的解釋與真值表 ?定義 ：命題公式 ， 也叫 （ 合式 ） 公式 (1).命題變元本身是一個公式； (2).如果 P是公式 ， 則 172。P 也是公式； (3).如果 P， Q是公式 ， 則 P∧ Q﹑ P∨ Q﹑ P→Q﹑ P?Q也是公式； (4).命題公式 (Prepositional Formula)是僅由有限步使用規(guī)則 (1)~(3)后產(chǎn)生的結(jié)果 。 公式常用符號G﹑ H… 等表示 。 ?例 ， (172。 P∧ Q)， (P→(172。P ∧ Q)) ， (((P∧ Q) ∧ (R ∨ Q)) ?(P →R))是命題公式 (P →Q )∧ 172。 Q)， (P →Q， (172。 P∨ Q ∨ (R， P∨ Q ∨ 不是命題公式 29/73 ?注意： –如果 G是含有 n個命題變元 P1, P2, … ,Pn的公式 ，通常記為 G（ P1, … ,Pn） 或簡記為 G。 –原子命題變元是最簡單的 （ 合式 ） 公式 ， 也叫原子 （ 合式 ） 公式 。 –合成公式?jīng)]有真值 ， 只有對其變元進(jìn)行指派后才有真值 。 –合成公式無限多 。 公式的解釋與真值表 30/73 公式的解釋與真值表 ?合成公式的層次： (1).若公式 A是一單個的命題變項 ， 則稱 A為 0層公式； (2).稱 A是 n+1(n≥0)層公式只需滿足下列情況只一： a). A=172。B， B是 n層公式； b). A=B∧ C， 其中 B， C分別為 i層和 j層公式 ,且n=max(i, j)； c). A=B∨ C， 其中 B， C的層次同 b； d). A=B→C， 其中 B， C的層次同 b； e). A=B?C， 其中 B， C的層次同 b； 從圖論的觀點來看每個多層公式可以用一個 “ 樹 ”來表示 。 31/73 公式的解釋與真值表 ：公式的解釋與真值表 公式本身沒有真值 ， 只有在對其所有命題變元指定真值后才變成一個具有真值的命題 。 ?定義 ： 設(shè)命題變元 P1, P2, … ,Pn是出現(xiàn)在公式 G中的所有命題變元 ， 指定 P1, P2, … ,Pn一組真值 ，則這組真值稱為 G的一個解釋 (Explanation),并記作 I。 一般來說 ， 若有 n個命題變元 ， 則應(yīng)有 2n個不同的解釋 。 ?定義 ： 公式 G在其所有可能的解釋下所取真值的表 ， 稱作 G的真值表 (Truth)。 32/73 公式的解釋與真值表 例 ： 5個聯(lián)結(jié)詞的真值表 (T： 1， F： 0) P Q 172。P P∧ Q P ∨ Q P→Q P?Q 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 1 33/73 公式的解釋與真值表 例 ： 設(shè)公式 G= ((P∧ Q) →R )∧ (P?Q)， 其中 P，Q， R是 G的命題變元 ， 則其真值表如下： P Q R P∧ Q (P∧ Q) →R P?Q ((P∧ Q) →R )∧ (P?Q) 0 0 0 0 1 1 1 0 0 1 0 1 1 1 0 1 0 0 1 0 0 0 1 1 0 1 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 1 0 0 34/73 公式的解釋與真值表 ：一些特殊的公式 例 ： 考慮： G1= 172。(P→Q) →P； G2=(P→Q) ∧ P； G3= 172。(P∧ 172。 Q) ? 172。 (P→Q) 公式 G1對所有可能的解釋都具有 “ 真 ” 值 ， G3對所有解釋都具有 “ 假 ” 值 ， 公式 G2則具有 “ 真 ”和 “ 假 ” 值 。 35/73 公式的解釋與真值表 ： ?定義 ： (1). 公式 G稱為永真公式 （ 重言式 ） ， 如果在它的所有解釋下都為 “ 真 ” ； (2). 公式 G稱為可滿足的 ， 如果它不是永假的； (3). 公式 G稱為永假公式 （ 矛盾式 ） , 如果在它的所有解釋下都為 “ 假 ” 。有時也稱永假公式為不可滿足公式 。 ?注意： (1). 重言式的否定是矛盾式 ， 矛盾式的否定是重言式 ， 所以研究其一就可以了； 36/73 公式的解釋與真值表 (2). 重言式的合取 ， 析取 ， 蘊含 ， 等值等都是重言式； (3). 重言式中有許多非常有用的恒等式和永真蘊含式 。 對任意的公式 ， 判定其是否為永真公式 ， 永假公式 ， 可滿足公式的問題稱為給定公式的判定問題 。 由于一個命題公式的解釋的數(shù)目是有窮的 ， 所以命題邏輯的判定問題是可解的 ， 即命題的永真 ， 永假性是可判定的 。 其判定方法有 真值表法 和 公式推演法 。 37/73 公式的解釋與真值表 ?例 ： 判定公式： (1).(P→Q) ?(172。 P∨ Q)。 (2). ((P→Q)∧ P) →Q； (3). P?(Q ∧ R)。 ： ?定義 ： 公式 G， H， 如果在其任意解釋下 ， 其真值相同 ， 則稱 G是 H的等價式 (Equivalent)或稱 G恒等于 H， 記作 G?H。 38/73 公式的解釋與真值表 ?定理 ： 對于公式 G和 H， G?H的充分必要條件是公式 G ?H是重言式 。 證明： 必要性： 假定 G?H， 則 G和 H在其任意解釋 I下 ，或同為真或同為假 ， 由 “ ?” 的意義知 ， G ?H在任意解釋 I下 ， 其真值為真 ， 即 G ?H為重言式； 充分性： 假設(shè)公式 G ?H是重言式 ， I是它的任意解釋 ， 在 I下 ， G ?H為真 ， 因此 ， G， H或同為真或同為假 ， 由于 I的任意性 ， 故有 G?H。 39/73 公式的解釋與真值表 ?注意 ?與 ?不同： (1). ? ：邏輯等價關(guān)系 ， G ? H不是命題公式； (2). ?：邏輯聯(lián)結(jié)詞 ， G ?H是命題公式； (3).計算機(jī)不能判斷 G， H是否邏輯等價 ， 而可計算 G ?H是否為重言式 。 40/73 公式的解釋與真值表 ?常用邏輯恒等式（ P， Q， R為任意命題， T為真命題， F為假命題）： E1 172。172。P=P 雙否定 E2 P∨ P=P ∨ 的冪等律 E3 P∧ P=P ∧ 的冪等律 E4 P∨ Q=Q∨ P ∨ 的交換律 E5 P∧ Q=Q∧ P ∧ 的交換律 E6 (P∨ Q) ∨ R=P∨ (Q∨ R) ∨ 的結(jié)合律 E7 (P∧ Q) ∧ R=P∧ (Q∧ R) ∧ 的結(jié)合律 E8 P∧ (Q∨ R) =P∧ Q∨ P∧ R ∧ 在 ∨ 上的分配律 E9 P∨ (Q∧ R) =(P∨ Q)∧ (P∨ R) ∨ 在 ∧ 上的分配律 E10 172。(P∨ Q) =172。P∧ 172。Q 德 摩根定律 E11 172。(P∧ Q) =172。P∨ 172。Q 41/73 公式的解釋與真值表 E12 P∨ (P∧ Q) =P 吸收律 E13 P∧ (P∨ Q) =P E14 (P→Q) =172。P∨ Q 蘊含等值式 E15 (P?Q) =(P→Q) ∧ (Q→P) 等價等值式 E16 P∨ T=T 零律 E17 P∧ F=F E18 P∨ F=P 同一律 E19 P∧ T=P E20 P∨ 172。P=T 排中律 E21 P∧ 172。P=F 矛盾律 E22 (P∧ Q→R) =(P→(Q→R)) 輸出律 E23 ((P→Q) ∧ (P→172。Q)) =172。P 歸謬律 E24 (P→Q) =172。Q→172。P 逆反律 42/73 公式的解釋與真值表 ： ?定義 ：若 A→B是一永真式 ， 那么稱為永真蘊含式 ， 記為 A?B， 讀作 A永真蘊含 B ?常用的永真蘊含式 I1 P=P∨ Q I2 P∧ Q=P I3 P∧ (P→Q) =Q I4 (P→Q) ∧ 172。Q=172。P I5 172。P∧ (P∨ Q) =Q I6 (P→Q) ∧ (Q→R) =(P→R) I7 (P→Q) =((Q→R) →(P→R)) I8 ((P→Q) ∧ (R→S)) =(P∧ R→Q∧ S) I9 ((P?Q) ∧ (R?S)) =(P?R) 43/73 公式的解釋與真值