【正文】 (3)：由有限個(gè)簡(jiǎn)單合取式構(gòu)成的析取式稱為析取范式 (Disjunctive Normal From)，由有限個(gè)簡(jiǎn)單析取式構(gòu)成的合取式稱為合取范式 (Conjunctive Normal From)。 58/73 ：范式 ：范式 對(duì)于給定公式的判定問題，可用真值表方法加以解釋，但當(dāng)公式中命題變?cè)臄?shù)目較大時(shí)，計(jì)算量較大，每增加一個(gè)命題變?cè)?，真值表的行?shù)要翻倍，計(jì)算量加倍，此外，對(duì)于同一問題，可以從不同的角度去考慮，產(chǎn)生不同的但又等價(jià)的命題公式，即同一個(gè)命題可以有不同的表達(dá)形式。P∧ Q)用僅含{172。 ?例 ： 試將公式 (P→(Q∨ 172。, }也是極小完備集，此外由 ↑， ↓的性質(zhì)可知 ， {↑}， {↓}也是極小完備集； ? {∧ ,∨ ,→, ?}及其子集不是完備集； ?實(shí)際應(yīng)用中經(jīng)常采取的聯(lián)結(jié)詞集合為 {172。,∨ }， {172。,∧ }是一個(gè)極小的。,∧ }是一個(gè)極小聯(lián)結(jié)詞完備集。B)，所以 ∨ 也是冗余的 , ∴ {172。(172。A∨ B， A?B=(A→B)∧ (B→A)，所以 →， ?是冗余的，故 {172。 ?由前面 ， {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。 ?55/73 聯(lián)結(jié)詞的完備集 與非，或非，異或的性質(zhì) ： P↑Q?Q↑P， P↑P ? 172。(P∧ Q) ， P↓Q ? 172。(P?Q) ， P Q ? 172。(P∧ Q)， f13 =P→Q， f14 = P∨ Q， f15 = Q→P， f16 =P∨ 172。Q， f8=(P?Q)， f9 = 172。(Q→P)， f5 =P∧ Q， f6 = 172。(P∨ Q)， f3= 172。 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 等價(jià) 異或 恒等Q 恒等P 與非 蘊(yùn)含 析取 蘊(yùn)含 永真 ☆ △ △ △ ◇ ◇ ◇ ◇ △ ☆ ☆ △ ◇ ◇ ◇ ☆ 53/73 聯(lián)結(jié)詞的完備集 ◇ ：已定義； ☆ ：意義不大； △ ：可再定義 f1=P∧ 172。 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)算 。構(gòu)成的公式 ， 則B*=A* 51/73 聯(lián)結(jié)詞的完備集 我們知道 ， 命題公式通過等價(jià)公式的轉(zhuǎn)換 ， 可以以不同的形式表示出來 。P∧ Q)= 172。P ∨ Q， 則由對(duì)偶原理 ， 得 (P∨ Q)∧ (172。P∨ (172。P n) 公式 (1) 50/73 公式的解釋與真值表 ?定理 ： 若 A=B ， 且 A ， B 為 命 題 變 元P1,P2, … ,Pn及聯(lián)結(jié)詞 ∧ ， ∨ ， 172。P1, 172。 ?定理 ： 設(shè) A和 A*是對(duì)偶式 ， P1,P2, … ,Pn是出現(xiàn)于 A和 A*中所有命題變?cè)?， 于是 172。P ∨ (Q∧ R)和 172。 對(duì) A*采取同樣的替換 ， 又得到 A， 所以 A也是 A*的對(duì)偶 ， 即對(duì)偶是相互的 。 49/73 公式的解釋與真值表 ：對(duì)偶原理 ?定義 ： 設(shè)公式 A， 其中僅有聯(lián)結(jié)詞 ∧ ， ∨ ， 172。P∧ (172。R)=P。 (3).(P∧ (Q∨ R))∨ (P∧ 172。((P∨ 172。 ?定理 (替換定理 ) ： 設(shè) G1是 G的子公式 ， H1是任意的命題公式 ， 在 G中凡出現(xiàn) G1處都以 H1替換后得到的新的命題公式 H， 若 G1=H1， 則 G=H。 46/73 公式的解釋與真值表 例 ： 設(shè) G(P, Q) = 172。 44/73 公式的解釋與真值表 (2).若 A=B， A=C， 則 A=B∧ C. 證明： A為真時(shí) ， B， C都為真 ， 則 B∧ C也為真 ，即 A→B∧ C為真； A為假時(shí) ， 則不管 B∧ C是真還是假時(shí) ， A→B∧ C均為真 ， 因此 A=B∧ C。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 公式的解釋與真值表 ： ? (1).若 A=B， B=C， 則 A=C；若 A=B， B=C， 則 A=C. (即邏輯恒等和永真蘊(yùn)含都是可傳遞的 ) 證明： A=B， B=C， 即 A?B， B?C為重言式 ， 對(duì)任意的解釋 I， A和 B， B和 C的真值相同 ，則 A和 C的真值相同 。Q=172。Q→172。Q)) =172。P=T 排中律 E21 P∧ 172。Q 41/73 公式的解釋與真值表 E12 P∨ (P∧ Q) =P 吸收律 E13 P∧ (P∨ Q) =P E14 (P→Q) =172。(P∧ Q) =172。Q 德 (P∨ Q) =172。172。 39/73 公式的解釋與真值表 ?注意 ?與 ?不同： (1). ? ：邏輯等價(jià)關(guān)系 ， G ? H不是命題公式； (2). ?：邏輯聯(lián)結(jié)詞 ， G ?H是命題公式； (3).計(jì)算機(jī)不能判斷 G， H是否邏輯等價(jià) ， 而可計(jì)算 G ?H是否為重言式 。 38/73 公式的解釋與真值表 ?定理 ： 對(duì)于公式 G和 H， G?H的充分必要條件是公式 G ?H是重言式 。 (2). ((P→Q)∧ P) →Q； (3). P?(Q ∧ R)。 37/73 公式的解釋與真值表 ?例 ： 判定公式： (1).(P→Q) ?(172。 由于一個(gè)命題公式的解釋的數(shù)目是有窮的 ， 所以命題邏輯的判定問題是可解的 ， 即命題的永真 ， 永假性是可判定的 。 ?注意： (1). 重言式的否定是矛盾式 ， 矛盾式的否定是重言式 ， 所以研究其一就可以了； 36/73 公式的解釋與真值表 (2). 重言式的合取 ， 析取 ， 蘊(yùn)含 ， 等值等都是重言式； (3). 重言式中有許多非常有用的恒等式和永真蘊(yùn)含式 。 35/73 公式的解釋與真值表 ： ?定義 ： (1). 公式 G稱為永真公式 （ 重言式 ） ， 如果在它的所有解釋下都為 “ 真 ” ； (2). 公式 G稱為可滿足的 ， 如果它不是永假的； (3). 公式 G稱為永假公式 （ 矛盾式 ） , 如果在它的所有解釋下都為 “ 假 ” 。 Q) ? 172。(P→Q) →P； G2=(P→Q) ∧ P； G3= 172。 32/73 公式的解釋與真值表 例 ： 5個(gè)聯(lián)結(jié)詞的真值表 (T： 1， F： 0) P Q 172。 一般來說 ， 若有 n個(gè)命題變?cè)?， 則應(yīng)有 2n個(gè)不同的解釋 。 31/73 公式的解釋與真值表 ：公式的解釋與真值表 公式本身沒有真值 ， 只有在對(duì)其所有命題變?cè)付ㄕ嬷岛蟛抛兂梢粋€(gè)具有真值的命題 。 公式的解釋與真值表 30/73 公式的解釋與真值表 ?合成公式的層次： (1).若公式 A是一單個(gè)的命題變項(xiàng) ， 則稱 A為 0層公式； (2).稱 A是 n+1(n≥0)層公式只需滿足下列情況只一： a). A=172。 –合成公式?jīng)]有真值 ， 只有對(duì)其變?cè)M(jìn)行指派后才有真值 。 P∨ Q ∨ (R， P∨ Q ∨ 不是命題公式 29/73 ?注意： –如果 G是含有 n個(gè)命題變?cè)? P1, P2, … ,Pn的公式 ，通常記為 G（ P1, … ,Pn） 或簡(jiǎn)記為 G。P ∧ Q)) ， (((P∧ Q) ∧ (R ∨ Q)) ?(P →R))是命題公式 (P →Q )∧ 172。 ?例 ， (172。P 也是公式； (3).如果 P， Q是公式 ， 則 P∧ Q﹑ P∨ Q﹑ P→Q﹑ P?Q也是公式； (4).命題公式 (Prepositional Formula)是僅由有限步使用規(guī)則 (1)~(3)后產(chǎn)生的結(jié)果 。 但不是說原子命題和聯(lián)結(jié)詞的一個(gè)隨便的組合都可以為命題公式 ， 我們用遞歸的方法來定義命題公式 。 命題變量無具體的真值 ， 它的值域是集合 {T， F}(或 {1， 0})。 ?定義 ： 一個(gè)特定的命題是一個(gè)常值命題 (Constant Proposition)， 它不是具有值 “ T”(“1”)， 就是具有值 “ F”(“0”)。與計(jì)算機(jī)中的與門 ， 或門 ， 非門電路是相對(duì)應(yīng)的 看 P67 例 ， P9 例 命題與命題聯(lián)結(jié)詞 26/73 ：命題公式 就像在代數(shù)學(xué)里引入變量一樣 ， 為了更廣泛的應(yīng)用命題演算 ， 在數(shù)理邏輯中也引入了命題變量 。是自然語(yǔ)言中的 “ 非 ” ﹑ “不 ” 和 “ 沒有 ” 等的邏輯抽象 (2)∧ 是自然語(yǔ)言中的 “ 并且 ” ﹑ “既 … 又 … ” ﹑ “且 ” ﹑ “和 ” 等的邏輯抽象 (3)∨ 是自然語(yǔ)言中的 “ 或 ” 和 “ 或者 ” 等的邏輯抽象；但 “ 或 ” 有 “ 可兼或 ” ﹑ “不可兼或 ” ﹑ “近似或 ” 三種 (4)P→Q是自然語(yǔ)言中的 “ 只要 P， 就 Q” ﹑ “因?yàn)镻， 所以 Q” ﹑ “P僅當(dāng) Q”等的邏輯抽象 25/73 (5) ?是自然語(yǔ)言中的 “ 充分必要條件 ” 和 “ 當(dāng)且僅當(dāng) ” 等的邏輯抽象 (6)聯(lián)結(jié)詞連接的是兩個(gè)命題真值之