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