【正文】 ∨ ， 172。 使得在研究時(shí) ， 只需考慮命題的真值 ， 而不知曉命題的具體含義 。 而一個(gè)任意的沒有賦予具體內(nèi)容的原子命題是一個(gè)變量命題 ， 常稱它為命題變量 (或命題變?cè)?、 命題變項(xiàng) )(Proposition Variable)。 公式的解釋與真值表 27/73 ?原子命題在不指派真值時(shí)稱為命題變?cè)?， 而復(fù)合命題由原子命題和聯(lián)結(jié)詞構(gòu)成 ， 可以看作是命題變?cè)暮瘮?shù) ， 且該函數(shù)的值仍為“ 真 ” 或 “ 假 ” ， 可以稱為真值函數(shù) （ True Value Function） 或命題公式 。 公式的解釋與真值表 28/73 公式的解釋與真值表 ?定義 ：命題公式 ， 也叫 （ 合式 ） 公式 (1).命題變?cè)旧硎且粋€(gè)公式； (2).如果 P是公式 ， 則 172。 公式常用符號(hào)G﹑ H… 等表示 。 P∧ Q)， (P→(172。 Q)， (P →Q， (172。 –原子命題變?cè)亲詈?jiǎn)單的 （ 合式 ） 公式 ， 也叫原子 （ 合式 ） 公式 。 –合成公式無限多 。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； 從圖論的觀點(diǎn)來看每個(gè)多層公式可以用一個(gè) “ 樹 ”來表示 。 ?定義 ： 設(shè)命題變?cè)?P1, P2, … ,Pn是出現(xiàn)在公式 G中的所有命題變?cè)?， 指定 P1, P2, … ,Pn一組真值 ，則這組真值稱為 G的一個(gè)解釋 (Explanation),并記作 I。 ?定義 ： 公式 G在其所有可能的解釋下所取真值的表 ， 稱作 G的真值表 (Truth)。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的命題變?cè)?， 則其真值表如下： 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∧ 172。 (P→Q) 公式 G1對(duì)所有可能的解釋都具有 “ 真 ” 值 ， G3對(duì)所有解釋都具有 “ 假 ” 值 ， 公式 G2則具有 “ 真 ”和 “ 假 ” 值 。有時(shí)也稱永假公式為不可滿足公式 。 對(duì)任意的公式 ， 判定其是否為永真公式 ， 永假公式 ， 可滿足公式的問題稱為給定公式的判定問題 。 其判定方法有 真值表法 和 公式推演法 。 P∨ Q)。 ： ?定義 ： 公式 G， H， 如果在其任意解釋下 ， 其真值相同 ， 則稱 G是 H的等價(jià)式 (Equivalent)或稱 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。 40/73 公式的解釋與真值表 ?常用邏輯恒等式（ P， Q， R為任意命題， T為真命題， F為假命題）： E1 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∧ 172。摩根定律 E11 172。P∨ 172。P∨ Q 蘊(yùn)含等值式 E15 (P?Q) =(P→Q) ∧ (Q→P) 等價(jià)等值式 E16 P∨ T=T 零律 E17 P∧ F=F E18 P∨ F=P 同一律 E19 P∧ T=P E20 P∨ 172。P=F 矛盾律 E22 (P∧ Q→R) =(P→(Q→R)) 輸出律 E23 ((P→Q) ∧ (P→172。P 歸謬律 E24 (P→Q) =172。P 逆反律 42/73 公式的解釋與真值表 ： ?定義 ：若 A→B是一永真式 ， 那么稱為永真蘊(yùn)含式 ， 記為 A?B， 讀作 A永真蘊(yùn)含 B ?常用的永真蘊(yùn)含式 I1 P=P∨ Q I2 P∧ Q=P I3 P∧ (P→Q) =Q I4 (P→Q) ∧ 172。P I5 172。 ∴ A ?C為重言式 ， 即 A=C； A=B， B=C， 即 A→B， B→C為真； ∴ (A→B)∧ (B→C)為真 ， 由公式 I6： A→C為重言式 ， 即 A=C。 45/73 公式的解釋與真值表 ：代入規(guī)則和替換規(guī)則 當(dāng)一個(gè)公式是永真式或永假式時(shí) ， 其公式的真值完全跟隨其命題變?cè)恼嬷档淖兓兓?， 因此 ，當(dāng)用其他公式來取代公式中的命題變?cè)獣r(shí) ， 不會(huì)改變公式的永真性和永假性 ?定理 (代入定理 ) ： 設(shè) G(P1, … ,Pn)是一個(gè)命題公式 ， 其中 P1, … ,Pn是命題變?cè)?， G1(P1, … ,Pn), … Gn(P1, … ,Pn)為任意的命題公式 ， 此時(shí)若 G是永真公式或永假公式 ， 則用 G1取代 P1,… ,Gn取代 Pn后 ，得到的新的命題公式 G(G1,… ,Gn) = G’(P1, … ,Pn)也是一個(gè)永真公式或永假公式 。(P→Q) →P；用 H(P, Q) =(P ∧ Q)； S(P, Q) =(P ?Q)代入 G驗(yàn)證代入定理。 例 ： 簡(jiǎn)化開關(guān)電路： S S R Q P P 47/73 公式的解釋與真值表 例 ： 將下面程序語言進(jìn)行化簡(jiǎn)： if A then if B then X else Y else if B then X else Y 例 ： 簡(jiǎn)化邏輯電路： R Q P ∧ ∧ ∧ ∨ ∨ 48/73 公式的解釋與真值表 例 ： 求證： (1).P∨ 172。Q)∧ Q)是永真公式； (2).P→(Q→R)=(P∧ Q)→R。Q ∧ 172。 (4).(172。Q∧ R))∨ (Q∧ R)∨ (P∧ R)=R。在 A中將 ∧ ， ∨ ， T， F分別換以 ∨ ， ∧ ， F， T得到公式 A*， 則 A*稱為 A的對(duì)偶公式 。 例 ， 172。P ∧ (Q∨ R)互為對(duì)偶； P∨ F和 P∧ T互為對(duì)偶 。A(P1,P2, …,P n)=A*(172。P2, …, 172。構(gòu)成的公式 ， 則A*=B* (對(duì)偶原理 ) 例 ， 若 (P∧ Q)∨ (172。P∨ Q)= 172。P∧ (172。P ∧ Q ?定理 ： 如果 A=B ， 且 A ， B 為命題變?cè)狿1,P2, … ,Pn及聯(lián)結(jié)詞 ∧ ， ∨ ， 172。 我們前面介紹了 5個(gè)聯(lián)結(jié)詞 ， 是否夠用呢 ？ 聯(lián)結(jié)詞的擴(kuò)充 ? 1. 一元運(yùn)算： 我們來看一個(gè)命題變?cè)谝粋€(gè)一元運(yùn)算的作用下可能的真值表 。 ? ： 考慮兩個(gè)變?cè)谝粋€(gè)二元運(yùn)算作用下可能的真值表 。P=F， f2= 172。(P→Q)， f4= 172。P， f7 = 172。(P?Q) f10=Q， f11=P， f12 = 172。P=T， 其中： f2， f3(或 f4)， f9， f12都是兩個(gè)聯(lián)結(jié)詞的組合，為了敘述方便，可以引進(jìn)下列幾個(gè)聯(lián)結(jié)詞： 54/73 聯(lián)結(jié)詞的完備集 聯(lián)結(jié)詞 記號(hào) 復(fù)合命題 讀法 記法 備注 f9 異或 P不可兼或 Q P異或 Q P Q 邏輯電路中的異或門 f3， f4 蘊(yùn)含否定 P和 Q的蘊(yùn)含否定 P蘊(yùn)含否定 Q P Q f12 與非 ↑ P和 Q的與非 P與非 Q P↑Q 邏輯電路中的與非門 f2 或非 ↓ P和 Q的或非 P或非 Q P↓Q 邏輯電路 中的或非門 ? ?P Q ? 172。(P→Q) ， P↑Q ? 172。(P∨ Q) ， 這 9個(gè)聯(lián)結(jié)詞構(gòu)成命題演算中的所有聯(lián)結(jié)詞 。P ， (P↑Q)↑(P↑Q)?P∧ Q， (P↑P)↑(Q↑Q)?P∨ Q ： P↓Q ? Q↓P， P↓P ? 172。P ? ? ? ? ? ?? ? ?56/73 聯(lián)結(jié)詞的完備集 ?：全功能聯(lián)結(jié)詞 ?定義 ： 設(shè) S是聯(lián)結(jié)詞的集合， (1)用 S中的聯(lián)結(jié)詞表示的公式，可以等價(jià)地表示任何命題公式，則稱 S是一個(gè)聯(lián)結(jié)詞完備集 (或全功能集合 ) (Adequate Set of Connectives)， (2)S是一個(gè)聯(lián)結(jié)詞的完備集，且 S中無冗余的聯(lián)結(jié)詞 (即集合中不存在可以被其中的其它聯(lián)結(jié)詞所定義的聯(lián)結(jié)詞 )，則稱 S為極小聯(lián)結(jié)詞完備集。,∧ ,∨ ,→,?}是一個(gè)聯(lián)結(jié)詞完備集，而 A→B=172。,∧ ,∨ }也是一個(gè)聯(lián)結(jié)詞完備集 ,而A∨ B=172。A∧ 172。,∧ }也是一個(gè)聯(lián)結(jié)詞完備集，進(jìn)一步地 ,可知 {172。 57/73 聯(lián)結(jié)詞的完備集 ?證明聯(lián)結(jié)詞完備集 {172。 ?同理， {172。, →}， {172。,∧ ,∨ }。R))∧ (172。 ， ∨ }的公式等價(jià)地表示出來。這樣給命題演算帶來了一定的困難，因此，有必要使命題公式規(guī)范化，為此，引入了范式的概念。 60/73 ：范式 ?例如， ①： P， 172。R ； ③： 172。P∧ Q)； ⑤： (P∨ Q)∧ (172。