4/30/2022命題演算11.2 命題演算命題演算 Propositional Equivalences4/30/2022命題演算2 1、命題、命題(Proposition) 2、從簡單命題、從簡單命題(atomic proposition)到到 復(fù)合命題復(fù)合命題(compositional proposition)3、從命題常量、從命題常量(propositional constant)到到 命題變量命題變量(propositional variable) 4、從復(fù)合命題、從復(fù)合命題(compositional proposition)到到 命題公式命題公式(propositional formulas)4/30/2022命題演算3永真命題公式（永真命題公式（Tautology）公式中的命題變量無論怎樣代入，公式對應(yīng)的真值恒為公式中的命題變量無論怎樣代入，公式對應(yīng)的真值恒為T。 永假命題公式（永假命題公式（Contradiction)公式中的命題變量無論怎樣代入，公式對應(yīng)的真值恒為公式中的命題變量無論怎樣代入，公式對應(yīng)的真值恒為F。 可滿足命題公式（可滿足命題公式（Satisfaction）公式中的命題變量無論怎樣代入，公式對應(yīng)的真值總有一種公式中的命題變量無論怎樣代入，公式對應(yīng)的真值總有一種情況為情況為T。一般命題公式（一般命題公式（Contingency）既不是永真公式也不是永假公式。既不是永真公式也不是永假公式。4/30/2022命題演算4We can construct examples of tautologies and contradictions using just one proposition. Consider the truth tables of p p and p p, shown in Table 1. Since p p is always true, it is a tautology. Since p p is always false, it is a contradiction.4/30/2022命題演算54/30/2022命題演算6 The propositions p and q are called logically equivalent if p q is a tautotogy. The notation p q denotes that p and q are logically equivalent.邏輯等值，或邏輯等價4/30/2022命題演算7 Show that (pq) and p q are logically equivalent. This equivalence is one of De Morgans laws for propositions, named after the English mathematician Augustus De Morgan, of the mid-nineteenth century.Solution: The truth tables for these propositions are displayed in Table 2. Since the truth values of the propositions (pq) and p q agree for all possible combinations of the truth values of p and q, it follows that these propositions are logically equivalent.4/30/2022命題演算84/30/2022命題演算9 Show that the propositions pq and pq are logically equivalent.Solution: We construct the truth table for these propositions in Table 3. Since the truth values of pq and pq agree, these propositions are logically equivalent.4/30/2022命題演算104/30/2022命題演算11 Show that the propositions p(qr) and (pq)(pr) are logically equivalent.This is the distributive law of disjunction over conjunction.Solution: We construct the truth table for these propositions in Table 4. Since the truth values of p(qr) and (pq)(pr) agree, these propositions are logically equivalent.4/30/2022命題演算124/30/2022命題演算13基本邏輯等價定理：基本邏輯等價定理： 對于任意的命題公式對于任意的命題公式p、q、r，下面的命題公，下面的命題公式是等價的。式是等價的。4/30/2022命題演算144/30/2022命題演算15p (p q) p Absorption Laws/吸收律p (p q) pp q p qp q (p q) ( q p)4/30/2022命題演算16 Show that (p( pq) and p q are logically equivalent.4/30/2022命題演算17 Show that (pq) (pq) is a tautology. 4/30/2022命題演算18判斷命題公式邏輯等價的方法：判斷命題公式邏輯等價的方法： 1、真值表、真值表 2、命題公式的演算、命題公式的演算 基本等值定理；基本等值定理； 公式的代入不變性；公式的代入不變性； 等值關(guān)系的傳遞性。等值關(guān)系的傳遞性。4/30/2022命題演算19命題公式邏輯等價關(guān)系的應(yīng)用：命題公式邏輯等價關(guān)系的應(yīng)用： 1、判定是否邏輯等價；、判定是否邏輯等價； 2、判斷是否為永真公式或永假公式；、判斷是否為永真公式或永假公式； 3、命題公式的化簡、命題公式的化簡4/30/2022命題演算20什麼，如果她不來那么我也不去，沒有那回事。什麼，如果她不來那么我也不去，沒有那回事。P：她來。：她來。Q：我去。：我去。4/30/2022命題演算21進(jìn)一步的思考：進(jìn)一步的思考：一、命題公式的對偶性及其對偶處理。一、命題公式的對偶性及其對偶處理。4/30/2022命題演算22限定性命題公式限定性命題公式： 最多僅含有否定、析取、合取最多僅含有否定、析取、合取邏輯聯(lián)結(jié)詞的命題公式。邏輯聯(lián)結(jié)詞的命題公式。命題公式命題公式P的的對偶公式（對偶公式（Dual）：將：將P中的中的 析取聯(lián)結(jié)詞換成合取聯(lián)結(jié)詞，析取聯(lián)結(jié)詞換成合取聯(lián)結(jié)詞， 合取聯(lián)結(jié)詞換成析取聯(lián)結(jié)詞，合取聯(lián)結(jié)詞換成析取聯(lián)結(jié)詞， T換成換成F，F(xiàn)換成換成T（如果存在的話）。（如果存在的話）。記為記為P*4/30/2022命題演算23對偶原理（對偶原理（Duality Principle) 設(shè)設(shè)P、Q是限定性命題公式。如果是限定性命題公式。如果 P Q 則則 P* Q* 例：A： （P Q） Q B： P Q4/30/2022命題演算24進(jìn)一步的思考：進(jìn)一步的思考：二、命題公式中的邏輯聯(lián)接詞的極小完備性。二、命題公式中的邏輯聯(lián)接詞的極小完備性。4/30/2022命題演算25邏輯聯(lián)接詞組是邏輯聯(lián)接詞組是功能完備的功能完備的（Functionally Complete）：）： 任一個命題公式都能夠等價于僅包含這些邏任一個命題公式都能夠等價于僅包含這些邏輯聯(lián)接詞聯(lián)結(jié)起來的公式。輯聯(lián)接詞聯(lián)結(jié)起來的公式。邏輯聯(lián)接詞組是邏輯聯(lián)接詞組是極小功能完備的極小功能完備的： 是功能完備的并且不能少一個。是功能完備的并且不能少一個。4/30/2022命題演算26例例2：否定和合取組成的邏輯聯(lián)結(jié)詞組是：否定和合取組成的邏輯聯(lián)結(jié)詞組是極小功能極小功能完備的。完備的。例例3：否定和析取組成的邏輯聯(lián)結(jié)詞組是否定和析取組成的邏輯聯(lián)結(jié)詞組是極小功能極小功能完備的。完備的。例例1：否定、析取、合取組成的邏輯聯(lián)結(jié)詞組：否定、析取、合取組成的邏輯聯(lián)結(jié)詞組是功能完備的，但不是是功能完備的，但不是極小功能完備的。極小功能完備的。4/30/2022命題演算27進(jìn)一步的思考：進(jìn)一步的思考：三、命題公式的進(jìn)一步分類。三、命題公式的進(jìn)一步分類。命題公式的標(biāo)準(zhǔn)化命題公式的標(biāo)準(zhǔn)化-范式范式4/30/2022命題演算28文字（文字（literal）/符號（符號（symbol）：）： 原子命題或其否定原子命題或其否定小項（小項（small item）/合取式（合取式（ conjunctive form ）: 若干個文字的合取。若干個文字的合取。大項（大項（large item）/析取式（析取式（ disjunctive form ）: 若干個文字的析取。若干個文字的析取。4/30/2022命題演算29合取范式（合取范式（conjunctive normal form): 若干個大項的合取。若干個大項的合取。析取范式（析取范式（disjunctive normal form): 若干個小項的析取。若干個小項的析取。標(biāo)準(zhǔn)句標(biāo)準(zhǔn)句(standard sentence)：合取范式或析取范式：合取范式或析取范式子句（子句（clause）:合取范式中的大項或合取范式中的大項或 析取范式中的小項。析取范式中的小項。4/30/2022命題演算30定理定理1：任意一個命題公式都存在與之等價的合?。喝我庖粋€命題公式都存在與之等價的合取 范式和析取范式。范式和析取范式。定理的證明思路：定理的證明思路： 1、化成限定性公式；、化成限定性公式； 2、將否定聯(lián)結(jié)詞移到命題變量的前面；、將否定聯(lián)結(jié)詞移到命題變量的前面； 3、消除多余的否定聯(lián)結(jié)詞；、消除多余的否定聯(lián)結(jié)詞； 4、化成合取范式和析取范式。、化成合取范式和析取范式。4/30/2022命題演算31定理定理1的作用與局限：的作用與局限： 1、標(biāo)準(zhǔn)化但僅僅是初步的、標(biāo)準(zhǔn)化但僅僅是初步的 # 標(biāo)準(zhǔn)化的形式標(biāo)準(zhǔn)化的形式 # 不唯一性不唯一性 2、能夠判定是否為永真或永假公式但不方便、能夠判定是否為永真或永假公式但不方便4/30/2022命題演算32定理定理2：一個命題公式是永真公式當(dāng)且僅當(dāng)與它等：一個命題公式是永真公式當(dāng)且僅當(dāng)與它等價的合取范式的每一個大項中包含了一個命題變量價的合取范式的每一個大項中包含了一個命題變量和它的否定；和它的否定； 一個命題公式是永假公式當(dāng)且僅當(dāng)與它等價的一個命題公式是永假公式當(dāng)且僅當(dāng)與它等價的析取范式的每一個小項中包含了一個命題變量和它析取范式的每一個小項中包含了一個命題變量和它的否定；的否定；4/30/2022命題演算33令令A(yù)（a1、a2、an）包含有）包含有n個變量的公式，個變量的公式，極小項極小項(extremal ):小項中恰包含小項中恰包含n個變量或其否定。個變量或其否定。極大項極大項( extremal ):大項中恰包含大項中恰包含n個變量或其否定。個變量或其否定。主合取范式（主合取范式（Unique conjunctive normal form): 若干個極大項的合取。若干個極大項的合取。主析取范式（主析取范式（Unique disjunctive normal form): 若干個極小項的析取。若干個極小項的析取。4/30/2022命題演算34定理定理3：令：令A(yù)（a1、a2、an）包含有）包含有n個變量的個變量的公式，則有：公式，則有：1、如果、如果A存在與之等價的主析取范式，則必唯一；存在與之等價的主析取范式，則必唯一；2、如果、如果A存在與之等價的主合取范式，則必唯一；存在與之等價的主合取范式，則必唯一；3、A是永真公式當(dāng)且僅當(dāng)與是永真公式當(dāng)且僅當(dāng)與A等價的主析取范式恰有等價的主析取范式恰有2n個極小項或沒有主合取范式；個極小項或沒有主合取范式；4、A是永假公式當(dāng)且僅當(dāng)與是永假公式當(dāng)且僅當(dāng)與A等價的主合取范式恰有等價的主合取范式恰有2n個極大項或沒有主析取范式；個極大項或沒有主析取范式；5、兩個命題公式等價當(dāng)且僅當(dāng)它們有相同的主合取、兩個命題公式等價當(dāng)且僅當(dāng)它們有相同的主合取范式或相同的主析取范式。范式或相同的主析取范式。4/30/2022命題演算35例例6 張先生手中有代號為張先生手中有代號為A、B、C、D、E的五種股票，根據(jù)的五種股票，根據(jù)當(dāng)前股市情況及張先生本人的經(jīng)濟(jì)需求，需要有若干個股票拋當(dāng)前股市情況及張先生本人的經(jīng)濟(jì)需求，需要有若干個股票拋出，但又必須滿足如下復(fù)雜的要求：出，但又必須滿足如下復(fù)雜的要求：（1）若）若A拋出，則拋出，則B也拋出；也拋出；（2）B和和C要留一種股票且只能留一種；要留一種股票且只能留一種；（3）C和和D要么全拋，要么都不拋；要么全拋，要么都不拋；（4）D和和E兩種股票中必然有一種或兩種要拋出；兩種股票中必然有一種或兩種要拋出；（5）若）若E拋出，則拋出，則A、B也拋出。上述五種條件全部滿足，問也拋出。上述五種條件全部滿足，問有幾種合理的方案供張先生選擇。有幾種合理的方案供張先生選擇。4/30/2022命題演算36小小 結(jié)結(jié)1、命題公式的等價演算、命題公式的等價演算2、 命題公式的標(biāo)準(zhǔn)化描述命題公式的標(biāo)準(zhǔn)化描述 表達(dá)、分類、判定、應(yīng)用表達(dá)、分類、判定、應(yīng)用 4/30/2022命題演算37練練 習(xí)習(xí)Pp19 8(d), 15, 29 附加題附加題