等價(jià)式和蘊(yùn)涵式ppt課件-在線瀏覽
2025-06-20 02:44本頁面
【正文】 T∨ P? T 所以， Q∨ ?（（ ?P∨ Q） ∧ P）是一個(gè)重言式。 例 化簡命題公式：（ ?P ∧ Q∧ R） ∨ （ P ∧ Q∧ R） 解：原式 ?（（ Q∧ R ） ∧ ?P） ∨ （（ Q∧ R） ∧ P） ?（ Q∧ R ） ∧ （ ?P∨ P） ?（ Q∧ R ） ∧ T ?（ Q∧ R ） ?從例中可看出，一個(gè)命題公式的表示形式并不是唯一的，可以有多種不同的表達(dá)式，通過等值演算可以尋求出最簡單的邏輯表達(dá)式。這一點(diǎn)我們在下一節(jié)中會看到。而 A? B? (A→B) ∧ (B→A) ，從而 A→B 與 B→A 都為重言式。 ?定義 當(dāng)命題公式 A→B 為永真式時(shí)，稱 A邏輯蘊(yùn)涵 B，記為 A? B，又稱它為 邏輯蘊(yùn)涵式 (logically implication)。 ?考慮“ ?”還是公式間的一個(gè)等價(jià)關(guān)系嗎？ ?我們可以很容易得出下面十分重要的邏輯蘊(yùn)涵式： 表 ?由定義，要證 A? B，只要證 A→B 為永真式，進(jìn)而用真值表或依據(jù)置換規(guī)則的等價(jià)變形都可以。因?yàn)?A真 B也一定為真的話，則 A→B不存在 A真 B假的情況，從而 A→B 永真。因?yàn)?B假 A也一定為假的話，則 A→B不存在 A真 B假的情況，從而 A→B 永真。 ? 例 A， B， C，證明： ? A∧ B?┐A→(C→B) ? 證： ? 法一：用后假推前假法 ? 假設(shè)后件 ┐A→(C→B) 為假，則 ┐A為真， C→B 為假，于是 A為假， C為真， B為假，從而 A∧ B為假，故A∧ B?┐A→(C→B) 。 ? 讀者還可以用真值表嘗試一下。 練習(xí) 8． 2 ? 試判定下列各式是三類公式的那一類： ? （ 1） (P→Q)→(Q→P) ? （ 2） ┐P→(P→Q) ? （ 3） Q∧ ┐(P→Q) ? （ 4） P∧ Q→(P ?Q) ? 證明下列邏輯等價(jià)式： ? （ 1） A?B? (A∧ B)∨ (┐A∧ ┐B) ? （ 2） A→(B→C) ?B→(A→C) ? （ 3） A→(B→C) ? (A→B)→(A→C) ? （ 4） ┐(┐A∨ ┐B)∨ ┐(┐A∨ B) ? A ? 證明下列邏輯蘊(yùn)涵式： ? （ 1） A∧ B? A?B ? （ 2） (A→B)→A ? A ? （ 3） A→B ? ((A?B)→A)→B ? （ 4） ┐(A∨ B)∨ C? A∨ (┐B∨ C) ? （ 5） (A∨ B)∧ (A→C) ∧ (B→C) ? C ? （ 6） ┐(A∨ B) ? A∨ (┐B∨ C) ? 化簡下列各式： ? （ 1）(A∨ ┐B)∧ (A∨ B)∧ (┐A∨ ┐B) ? （ 2） B∨ ┐((┐A∨ B)∧ A) ? （ 3） (P→Q) ? (┐Q→┐P) ? （ 4） (┐Q→P) →(P→Q) ? （ 5）(Q∧ (P→┐Q)→P) ∧ ┐(Q→P) 167。實(shí)際上，只有這五個(gè)是不夠用的，我們還會涉及其它的聯(lián)接詞。而比如一快餐館中寫到：一套快餐包括“主菜一個(gè)，湯或沙拉一份”，此句中的“或”不是可兼的。本節(jié)我們要引進(jìn)邏輯電路中涉及的 “異或（不可兼或）門”、 “與非門”、“或非門”等四個(gè)擴(kuò)充聯(lián)接詞。 ?“異或（不可兼或） ” ， 用符號（或 ?）表示，其含義可由下列等價(jià)式?jīng)Q定： ?PQ? (P∨ Q)∧ ┐(P∧ Q) ?┐(P? Q) ? (P∧ ┐Q) ∨ (┐P∧ Q) ?也就是說當(dāng) P， Q都為真時(shí) PQ為假。 ?“或非（ NOR） ”，用記號 ?表示，也稱為 皮爾斯 （ Peirce）箭頭，其含義可由下列等價(jià)式?jīng)Q定： ? P?Q?┐(P∨ Q) ? 這說明當(dāng) P， Q都為假時(shí) P?Q為真。但從我們本節(jié)引進(jìn)的四個(gè)擴(kuò)充聯(lián)接詞看，它們都能用前邊五個(gè)基本聯(lián)接詞表示，而由等價(jià)式知道， → 和 ?又能用 ┐， ∧ ， ∨ 來等價(jià)表示，同時(shí)由德摩根律 P∨ Q?┐(┐P∧ ┐Q)，P∧ Q?┐(┐P∨ ┐Q)又能將 ∧ 與 ∨ 互相轉(zhuǎn)換，因而 {┐， ∧ }和 {┐， ∨ }都是 完備聯(lián)接詞集（ plete group of connectives）。 ?常見的最小聯(lián)接詞集有 {┐， ∧ }， {┐， ∨ }，{┐， → }， {?}， {?}。{ ?}， {?}在大規(guī)模集成電路中有廣泛應(yīng)用。但 {┐， ∧ ， ∨ }是完備集，等價(jià)表示一公式也較簡單，因此是常用的聯(lián)接詞集。 析取范式和合取范式 ?我們已經(jīng)知道，對眾多的命題公式，可以依據(jù)它們之間的邏輯等價(jià)關(guān)系進(jìn)行分類，使相互邏輯等價(jià)的公式為一類。 ?定義 命題公式 A稱為 析取范式（ disjunctive normal form），當(dāng)且僅當(dāng)它具有型式： A1∨ A2∨ … ∨ An （ n≥1） ?其中 A1,A2,…,An 為由命題常元、變元及它們的否定組成的合取式。 ?定義 命題公式 A稱為 合取范式（ conjunctive normal form），當(dāng)且僅當(dāng)它具有型式： A1 A1∧ A2∧ … ∧ An （ n≥1） ?其中 A1,A2,…,An 為由命題常元、變元及它們的否定組成的析取式。 ?注： P， ┐P都可以看成特殊的析取范式和合取范式， ┐P∨ Q是析取范式，也可以看成是含有一個(gè)析取式的合取范式。 ? 解： P→┐(P→Q) ?P∨ ┐(┐P∨ Q) ??P∨ (P∧ ┐Q)( ?P)析取范式 ?? (P∨ P)∧ (P∨ ┐Q) ??P∧ (P∨ ┐ Q)( ?P)合取范式 ? 例 ┐(P∨ Q) ? (P∧ Q)的析取范式和合取范式。其等價(jià)推演的方法步驟是： ? 第一步，消去公式中的聯(lián)結(jié)詞 ?和 ?： ? 把公式中的 P→Q 化為 ┐P∨ Q； ? 把公式中的 P?Q化為 (┐P∨ Q)∧ (┐Q∨ P)或 (P∧ Q) ∨ (┐P∧ ┐Q)； ? 第二步，將否定聯(lián)結(jié)詞 ┐向內(nèi)深入，使之只作用于命題變元或命題變元的否定，然后將 ┐┐P化為 P； ? 第三步，利用分配律，將公式進(jìn)一步化為所需要的范式。例如， P既是 P→┐(P→Q) 的合取范式，又是它的析取范式。 ?上述兩點(diǎn)不能不說是析取范式和合取范式的缺點(diǎn)，因此，我們需要更加規(guī)范公式的范式，這就是下面的主范式。那么什么是小項(xiàng)，小項(xiàng)又有什么性質(zhì)呢？ ? 定義 在含 n個(gè)變元的合取式中，若每個(gè)變元與其否定二者必出現(xiàn)且僅出現(xiàn)一個(gè)，則
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1