《《命題演算》PPT課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《《命題演算》PPT課件（37頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、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、從簡(jiǎn)單命題(atomic proposition)到 復(fù)合命題(compositional proposition)3、從命題常量(propositional constant)到 命題變量(propositional variable) 4、從復(fù)合命題(compositional proposit

2、ion)到 命題公式(propositional formulas) 4/28/2021 1:22 AM Deren Chen, Zhejiang Univ. 3 永真命題公式（Tautology）公式中的命題變量無論怎樣代入，公式對(duì)應(yīng)的真值恒為T。 永假命題公式（Contradiction)公式中的命題變量無論怎樣代入，公式對(duì)應(yīng)的真值恒為F。 可滿足命題公式（Satisfaction）公式中的命題變量無論怎樣代入，公式對(duì)應(yīng)的真值總有一種情況為T。一般命題公式（Contingency）既不是永真公式也不是永假公式。 4/28/2021 1:22 AM Deren Chen, Zhejiang

3、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/

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. 邏輯等值，或邏輯等價(jià) 4/28/2021 1:22 AM Deren Chen, Zhejiang Univ. 7 Show that (p q) and p q are logically equivalent. Thi

5、s 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 possibl

6、e 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 ta

7、ble 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.

8、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

9、AM Deren Chen, Zhejiang Univ. 13 基本邏輯等價(jià)定理： 對(duì)于任意的命題公式p、q、r，下面的命題公式是等價(jià)的。 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

10、 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 判斷命題公式邏輯等價(jià)的方法： 1、真值表 2、命題公式的演算 基本等值定理； 公式的代入不變性； 等值關(guān)系的傳遞性。 4/28/2021 1:22 AM Deren Chen, Zhejiang Univ. 19 命題公式邏輯等價(jià)關(guān)系的應(yīng)用： 1、判定是否邏輯等價(jià)； 2

11、、判斷是否為永真公式或永假公式； 3、命題公式的化簡(jiǎn) 4/28/2021 1:22 AM Deren Chen, Zhejiang Univ. 20 什麼，如果她不來那么我也不去，沒有那回事。P：她來。Q：我去。 4/28/2021 1:22 AM Deren Chen, Zhejiang Univ. 21 進(jìn)一步的思考：一、命題公式的對(duì)偶性及其對(duì)偶處理。 4/28/2021 1:22 AM Deren Chen, Zhejiang Univ. 22 限定性命題公式： 最多僅含有否定、析取、合取邏輯聯(lián)結(jié)詞的命題公式。命題公式P的對(duì)偶公式（Dual）：將P中的 析取聯(lián)結(jié)詞換成合取聯(lián)結(jié)詞， 合取聯(lián)

12、結(jié)詞換成析取聯(lián)結(jié)詞， T換成F，F(xiàn)換成T（如果存在的話）。記為P* 4/28/2021 1:22 AM Deren Chen, Zhejiang Univ. 23 對(duì)偶原理（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 進(jìn)一步的思考：二、命題公式中的邏輯聯(lián)接詞的極小完備性。 4/28/2021 1:22 AM Deren Chen, Zhejiang Univ. 25 邏輯聯(lián)接詞組是功能完備的（Functiona

13、lly Complete）： 任一個(gè)命題公式都能夠等價(jià)于僅包含這些邏輯聯(lián)接詞聯(lián)結(jié)起來的公式。邏輯聯(lián)接詞組是極小功能完備的： 是功能完備的并且不能少一個(gè)。 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 進(jìn)一步的思考：三、命題公式的進(jìn)一步分類。命題公式的標(biāo)準(zhǔn)化-范式 4/28

14、/2021 1:22 AM Deren Chen, Zhejiang Univ. 28 文字（literal）/符號(hào)（symbol）： 原子命題或其否定小項(xiàng)（small item）/合取式（ conjunctive form ）: 若干個(gè)文字的合取。大項(xiàng)（large item）/析取式（ disjunctive form ）: 若干個(gè)文字的析取。 4/28/2021 1:22 AM Deren Chen, Zhejiang Univ. 29 合取范式（conjunctive normal form): 若干個(gè)大項(xiàng)的合取。析取范式（disjunctive normal form): 若干個(gè)小項(xiàng)的

15、析取。標(biāo)準(zhǔn)句(standard sentence)：合取范式或析取范式子句（clause）:合取范式中的大項(xiàng)或 析取范式中的小項(xiàng)。 4/28/2021 1:22 AM Deren Chen, Zhejiang Univ. 30 定理1：任意一個(gè)命題公式都存在與之等價(jià)的合取 范式和析取范式。定理的證明思路： 1、化成限定性公式； 2、將否定聯(lián)結(jié)詞移到命題變量的前面； 3、消除多余的否定聯(lián)結(jié)詞； 4、化成合取范式和析取范式。 4/28/2021 1:22 AM Deren Chen, Zhejiang Univ. 31 定理1的作用與局限： 1、標(biāo)準(zhǔn)化但僅僅是初步的 # 標(biāo)準(zhǔn)化的形式 # 不唯一性

16、 2、能夠判定是否為永真或永假公式但不方便 4/28/2021 1:22 AM Deren Chen, Zhejiang Univ. 32 定理2：一個(gè)命題公式是永真公式當(dāng)且僅當(dāng)與它等價(jià)的合取范式的每一個(gè)大項(xiàng)中包含了一個(gè)命題變量和它的否定； 一個(gè)命題公式是永假公式當(dāng)且僅當(dāng)與它等價(jià)的析取范式的每一個(gè)小項(xiàng)中包含了一個(gè)命題變量和它的否定； 4/28/2021 1:22 AM Deren Chen, Zhejiang Univ. 33 令A(yù)（a1、a2、an）包含有n個(gè)變量的公式，極小項(xiàng)(extremal ):小項(xiàng)中恰包含n個(gè)變量或其否定。極大項(xiàng)( extremal ):大項(xiàng)中恰包含n個(gè)變量或其否定。

17、主合取范式（Unique conjunctive normal form): 若干個(gè)極大項(xiàng)的合取。主析取范式（Unique disjunctive normal form): 若干個(gè)極小項(xiàng)的析取。 4/28/2021 1:22 AM Deren Chen, Zhejiang Univ. 34 定理3：令A(yù)（a1、a2、an）包含有n個(gè)變量的公式，則有：1、如果A存在與之等價(jià)的主析取范式，則必唯一；2、如果A存在與之等價(jià)的主合取范式，則必唯一；3、A是永真公式當(dāng)且僅當(dāng)與A等價(jià)的主析取范式恰有2n個(gè)極小項(xiàng)或沒有主合取范式；4、A是永假公式當(dāng)且僅當(dāng)與A等價(jià)的主合取范式恰有2n個(gè)極大項(xiàng)或沒有主析取范式

18、；5、兩個(gè)命題公式等價(jià)當(dāng)且僅當(dāng)它們有相同的主合取范式或相同的主析取范式。 4/28/2021 1:22 AM Deren Chen, Zhejiang Univ. 35 例6 張先生手中有代號(hào)為A、B、C、D、E的五種股票，根據(jù)當(dāng)前股市情況及張先生本人的經(jīng)濟(jì)需求，需要有若干個(gè)股票拋出，但又必須滿足如下復(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、命題公式的等價(jià)演算2、 命題公式的標(biāo)準(zhǔn)化描述 表達(dá)、分類、判定、應(yīng)用 4/28/2021 1:22 AM Deren Chen, Zhejiang Univ. 37 練 習(xí)Pp19 8(d), 15, 29 附加題