【文章內(nèi)容簡介】 表 ： ? (1).若 A=B， B=C， 則 A=C；若 A=B， B=C， 則 A=C. (即邏輯恒等和永真蘊(yùn)含都是可傳遞的 ) 證明： A=B， B=C， 即 A?B， B?C為重言式 ， 對任意的解釋 I， A和 B， B和 C的真值相同 ，則 A和 C的真值相同 。 ∴ A ?C為重言式 ， 即 A=C； A=B， B=C， 即 A→B， B→C為真； ∴ (A→B)∧ (B→C)為真 ， 由公式 I6： A→C為重言式 ， 即 A=C。 44/73 公式的解釋與真值表 (2).若 A=B， A=C， 則 A=B∧ C. 證明： A為真時 ， B， C都為真 ， 則 B∧ C也為真 ，即 A→B∧ C為真； A為假時 ， 則不管 B∧ C是真還是假時 ， A→B∧ C均為真 ， 因此 A=B∧ C。 45/73 公式的解釋與真值表 ：代入規(guī)則和替換規(guī)則 當(dāng)一個公式是永真式或永假式時 ， 其公式的真值完全跟隨其命題變元的真值的變化而變化 ， 因此 ，當(dāng)用其他公式來取代公式中的命題變元時 ， 不會改變公式的永真性和永假性 ?定理 (代入定理 ) ： 設(shè) G(P1, … ,Pn)是一個命題公式 ， 其中 P1, … ,Pn是命題變元 ， G1(P1, … ,Pn), … Gn(P1, … ,Pn)為任意的命題公式 ， 此時若 G是永真公式或永假公式 ， 則用 G1取代 P1,… ,Gn取代 Pn后 ，得到的新的命題公式 G(G1,… ,Gn) = G’(P1, … ,Pn)也是一個永真公式或永假公式 。 46/73 公式的解釋與真值表 例 ： 設(shè) G(P, Q) = 172。(P→Q) →P；用 H(P, Q) =(P ∧ Q)； S(P, Q) =(P ?Q)代入 G驗證代入定理。 ?定理 (替換定理 ) ： 設(shè) G1是 G的子公式 ， H1是任意的命題公式 ， 在 G中凡出現(xiàn) G1處都以 H1替換后得到的新的命題公式 H， 若 G1=H1， 則 G=H。 例 ： 簡化開關(guān)電路： S S R Q P P 47/73 公式的解釋與真值表 例 ： 將下面程序語言進(jìn)行化簡： if A then if B then X else Y else if B then X else Y 例 ： 簡化邏輯電路： R Q P ∧ ∧ ∧ ∨ ∨ 48/73 公式的解釋與真值表 例 ： 求證： (1).P∨ 172。((P∨ 172。Q)∧ Q)是永真公式； (2).P→(Q→R)=(P∧ Q)→R。 (3).(P∧ (Q∨ R))∨ (P∧ 172。Q ∧ 172。R)=P。 (4).(172。P∧ (172。Q∧ R))∨ (Q∧ R)∨ (P∧ R)=R。 49/73 公式的解釋與真值表 ：對偶原理 ?定義 ： 設(shè)公式 A， 其中僅有聯(lián)結(jié)詞 ∧ ， ∨ ， 172。在 A中將 ∧ ， ∨ ， T， F分別換以 ∨ ， ∧ ， F， T得到公式 A*， 則 A*稱為 A的對偶公式 。 對 A*采取同樣的替換 ， 又得到 A， 所以 A也是 A*的對偶 ， 即對偶是相互的 。 例 ， 172。P ∨ (Q∧ R)和 172。P ∧ (Q∨ R)互為對偶； P∨ F和 P∧ T互為對偶 。 ?定理 ： 設(shè) A和 A*是對偶式 ， P1,P2, … ,Pn是出現(xiàn)于 A和 A*中所有命題變元 ， 于是 172。A(P1,P2, …,P n)=A*(172。P1, 172。P2, …, 172。P n) 公式 (1) 50/73 公式的解釋與真值表 ?定理 ： 若 A=B ， 且 A ， B 為 命 題 變 元P1,P2, … ,Pn及聯(lián)結(jié)詞 ∧ ， ∨ ， 172。構(gòu)成的公式 ， 則A*=B* (對偶原理 ) 例 ， 若 (P∧ Q)∨ (172。P∨ (172。P∨ Q)= 172。P ∨ Q， 則由對偶原理 ， 得 (P∨ Q)∧ (172。P∧ (172。P∧ Q)= 172。P ∧ Q ?定理 ： 如果 A=B ， 且 A ， B 為命題變元P1,P2, … ,Pn及聯(lián)結(jié)詞 ∧ ， ∨ ， 172。構(gòu)成的公式 ， 則B*=A* 51/73 聯(lián)結(jié)詞的完備集 我們知道 ， 命題公式通過等價公式的轉(zhuǎn)換 ， 可以以不同的形式表示出來 。 我們前面介紹了 5個聯(lián)結(jié)詞 ， 是否夠用呢 ？ 聯(lián)結(jié)詞的擴(kuò)充 ? 1. 一元運(yùn)算： 我們來看一個命題變元在一個一元運(yùn)算的作用下可能的真值表 。 P f1 f2 f3 f4 0 0 0 1 1 1 0 1 0 1 52/73 聯(lián)結(jié)詞的完備集 因此 ， 最多只能定義 4種運(yùn)算 ， 但除了否定之外 ， 永假 ，永真 ， 恒等作為運(yùn)算意義不大 ， 所以一般不再定義其它一元運(yùn)算 。 ? ： 考慮兩個變元在一個二元運(yùn)算作用下可能的真值表 。 P Q f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 f16 0 0 0 1 0 0 0 1 1 1 0 0 0 1 1 0 1 1 0 1 0 0 1 0 0 1 0 0 1 1 0 1 1 1 0 1 1 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 0 1 0 0 1 0 1 1 0 1 1 1 1 永假 或非 蘊(yùn)含否定 蘊(yùn)含否定 合取 非P 非Q 等價 異或 恒等Q 恒等P 與非 蘊(yùn)含 析取 蘊(yùn)含 永真 ☆ △ △ △ ◇ ◇ ◇ ◇ △ ☆ ☆ △ ◇ ◇ ◇ ☆ 53/73 聯(lián)結(jié)詞的完備集 ◇ ：已定義； ☆ ：意義不大； △ ：可再定義 f1=P∧ 172。P=F， f2= 172。(P∨ Q)， f3= 172。(P→Q)， f4= 172。(Q→P)， f5 =P∧ Q， f6 = 172。P， f7 = 172。Q， f8=(P?Q)， f9 = 172。(P?Q) f10=Q， f11=P， f12 = 172。(P∧ Q)， f13 =P→Q， f14 = P∨ Q， f15 = Q→P， f16 =P∨ 172。P=T， 其中： f2， f3(或 f4)， f9， f12都是兩個聯(lián)結(jié)詞的組合，為了敘述方便，可以引進(jìn)下列幾個聯(lián)結(jié)詞： 54/73 聯(lián)結(jié)詞的完備集 聯(lián)結(jié)詞 記號 復(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) ， P↑Q ? 172。(P∧ Q) ， P↓Q ? 172。(P∨ Q) ， 這 9個聯(lián)結(jié)詞構(gòu)成命題演算中的所有聯(lián)結(jié)詞 。 ?55/73 聯(lián)結(jié)詞的完備集 與非，或非，異或的性質(zhì) ： P↑Q?Q↑P， P↑P ? 172。P ， (P↑Q)↑(P↑Q)?P∧ Q， (P↑P)↑(Q↑Q)?P∨ Q ： P↓Q ? Q↓P， P↓P ? 172。P ， (P↓Q)↓(P↓Q)?P∨ Q， (P↓P)↓(Q↓Q)?P∧ Q ： P Q ? Q P， P (Q R) ? (P Q) R P P? 0， 0 P ? P， 1 P ? 172。P ? ? ? ? ? ?? ? ?56/73 聯(lián)結(jié)詞的完備集 ?：全功能聯(lián)結(jié)詞 ?定義 ： 設(shè) S是聯(lián)結(jié)詞的集合， (1)用 S中的聯(lián)結(jié)詞表示的公式，可以等價地表示任何命題公式，則稱 S是一個聯(lián)結(jié)詞完備集 (或全功能集合 ) (Adequate Set of Connectives)， (2)S是一個聯(lián)結(jié)詞的完備集，且 S中無冗余的聯(lián)結(jié)詞 (即集合中不存在可以被其中的其它聯(lián)結(jié)詞所定義的聯(lián)結(jié)詞 )，則稱 S為極小聯(lián)結(jié)詞完備集。 ?由前面 ， {172。,∧ ,∨ ,→,?}是一個聯(lián)結(jié)詞完備集，而 A→B=172。A∨ B， A?B=(A→B)∧ (B→A)，所以 →， ?是冗余的，故 {172。,∧ ,∨ }也是一個聯(lián)結(jié)詞完備集 ,而A∨ B=172。(172。A∧ 172。B)，所以 ∨ 也是冗余的 , ∴ {172。,∧ }也是一個聯(lián)結(jié)詞完備集，進(jìn)一步地 ,可知 {172。,∧ }是一個極小聯(lián)結(jié)詞完備集。 57/73 聯(lián)結(jié)詞的完備集 ?證明聯(lián)結(jié)詞完備集 {172。,∧ }是一個極小的。 ?同理， {172。,∨ }， {172。, →}， {172。, }也是極小完備集，此外由 ↑， ↓的性質(zhì)可知 ， {↑}， {↓}也是極小完備集； ? {∧ ,∨ ,→, ?}及其子集不是完備集； ?實際應(yīng)用中經(jīng)常采取的聯(lián)結(jié)詞集合為 {172。,∧ ,∨ }。 ?例 ： 試將公式 (P→(Q∨ 172。R))∧ (172。P∧ Q)用僅含{172。 ， ∨ }的公式等價地表示出來。 58/73 ：范式 ：范式 對于給定公式的判定問題，可用真值表方法加以解釋，但當(dāng)公式中命題變元的數(shù)目較大時，計算量較大，每增加一個命題變元，真值表的行數(shù)要翻倍，計算量加倍，此外，對于同一問題，可以從不同的角度去考慮，產(chǎn)生不同的但又等價的命題公式，即同一個命題可以有不同的表達(dá)形式。這樣給命題演算帶來了一定的困難，因此，有必要使命題公式規(guī)范化，為此，引入了范式的概念。 59/73 ：范式 ?定義 ： (1)：命題變元或命題變元的否定稱為文字； (2)：有限個文字的析取式稱為簡單析取式 (基本和 )，有限個文字的合取式稱為簡單合取式 (基本積 )； (3)：由有限個簡單合取式構(gòu)成的析取式稱為析取范式 (Disjunctive Normal From)，由有限個簡單析取式構(gòu)成的合取式