離散數(shù)學(xué)課件2

1、1.2 重言式,2,真值表 設(shè)A是一個(gè)命題公式，P1 , P2 ,…,Pn是出現(xiàn)在公式A中的全部的命題變?cè)?公式 A 記為 A(P1 , P2 ,…,Pn)。給P1 ,P2 ,…,Pn分別賦以真值0或1得到一組真值，稱(chēng)為對(duì)A的一個(gè)指派(賦值或解釋)。 此時(shí)A就是一個(gè)確定的命題。含n個(gè)變?cè)墓焦灿?2n 種指派。真值表：A(P1 , P2 ,…,Pn)是一個(gè)含n個(gè)變?cè)墓?，將A在 2n 種指派下的取值情

2、況列成一個(gè)二維表，稱(chēng)為 A 的真值表。,3,對(duì)公式A構(gòu)造真值表的具體步驟為：（1）找出公式中所有命題變?cè)狿1 , P2 ,…,Pn (若無(wú)下標(biāo)按字母順序排列) ,（2）列出全部的2n組賦值，從00...0開(kāi)始，按二進(jìn)制加法每次加1，直到11...1，（3）對(duì)應(yīng)各組賦值計(jì)算出必要子公式的真值，（4）計(jì)算出公式A的真值，并將其列在對(duì)應(yīng)賦值的后面。,4,例1. 給出┐(P?Q)?(┐P?┐Q)的真值表：,5,例3：構(gòu)造 P?Q

3、和(P→Q)?(Q→P)的真值表,邏輯等價(jià)：若兩個(gè)命題公式在所有指派下取值相同（有相同的真值表）則稱(chēng)這兩個(gè)公式是邏輯等價(jià)命題。┐(P?Q) 和 (┐P)?(┐Q )是邏輯等價(jià)命題 P?Q 和(P→Q)?(Q→P)是邏輯等價(jià)命題,1.2.1 命題公式的分類(lèi)設(shè)A為任一命題公式，（1）若A在其所有指派下的取值均為真，則稱(chēng)A是重言式或永真式, 記為T(mén)或1。（2）若A在其所有指派下的取值均為假，則稱(chēng)A是矛盾式或永假式, 記為F或0。

4、 (3) 不是永真式，也不是永假式，這種命題公式叫偶然式。 (4) 如果A至少存在一個(gè)指派，使其值為真，則稱(chēng)A為可滿足的; (5)如果A至少存在一個(gè)指派，使其值為假，則稱(chēng)A為非永真。,注: (1)重言式一定是可滿足式,反之不真. (2)永真式的否定為永假式（¬Ｔ＝Ｆ）；永假式的否定為永真式（¬Ｆ＝Ｔ) (3)公式 A 是可滿足的，當(dāng)且僅當(dāng) ¬A 不是永真式 （4）兩個(gè)永

5、真式（永假式）的析取、合取、蘊(yùn)含、雙條件 均為永真式（永假式）。 （5）永真式（永假式）可代入規(guī)則。,1.2.2 恒等式定義 如果A?B為重言式，則A與B對(duì)任何指派都有相同的真值。 記為A ?B，叫做邏輯恒等式，讀做“A恒等于B”。 說(shuō)明： A ?B也就是上節(jié)說(shuō)的“A和B邏輯等價(jià)” “?”為等價(jià)關(guān)系符，Ａ?Ｂ表示Ａ和Ｂ有等價(jià)關(guān)系。 Ａ?Ｂ不為命題公式　 “?”為等

6、價(jià)聯(lián)結(jié)詞（運(yùn)算符），Ａ、Ｂ為命題公式，則（Ａ? Ｂ）也為一命題公式。,8,怎么證明是恒等式？例4：證明 ¬¬Ｐ?Ｐ； Ｐ→Ｑ?¬Ｐ∨Ｑ例1中的 ┐(P?Q)? (┐P)?(┐Q )例3中的 P?Q ?(P→Q)?(Q→P)這些都是一些最基本的恒等式。,9,基本邏輯恒等式,設(shè)P、Q和R代表任意命題，符號(hào)T代表真命題，符號(hào)F代表假命題。E1 雙重否定律

7、 ¬¬Ｐ?ＰE2 ∨的等冪律 Ｐ∨Ｐ?ＰE3 Λ的等冪律 ＰΛＰ?ＰE4 ∨的交換律 Ｐ∨Ｑ?Ｑ∨ＰE5 Λ的交換律 ＰΛＱ?ＱΛＰ,10,結(jié)合律 E6 ∨的結(jié)合律（Ｐ∨Ｑ）∨Ｒ?Ｐ∨（Ｑ∨Ｒ） E7 Λ的結(jié)合律 （ＰΛＱ）ΛＲ?ＰΛ

8、（ＱΛＲ）（Ｐ?Ｑ） ?Ｒ?Ｐ? （Ｑ?Ｒ）？,11,分配律 E8 Λ在∨上的分配律ＰΛ（Ｑ∨Ｒ）?（ＰΛＱ）∨（ＰΛＲ） E9 ∨在Λ上的分配律 Ｐ∨（ＱΛＲ）?（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ）,12,德·摩根定律 E10 ¬（Ｐ∨Ｑ）?¬ＰΛ¬Ｑ E11 ¬（ＰΛＱ）?

9、2;Ｐ∨¬Ｑ　 允許合取式和析取式互相表達(dá)。,13,吸收律 E12 Ｐ∨（ＰΛＱ） ?Ｐ E13 ＰΛ（Ｐ∨Ｑ） ?Ｐ　 用于公式化簡(jiǎn),14,蘊(yùn)涵表達(dá)式 E14 Ｐ→Ｑ?¬Ｐ∨Ｑ 用真值表證明 允許蘊(yùn)含式用析取式表達(dá)。 例如前面例子 ：如果太陽(yáng)從西方升起，那么2是奇數(shù)。

10、可以換種說(shuō)法?！?¬（Ｐ→Ｑ）? ＰΛ ¬Ｑ。怎么說(shuō)？函數(shù)連續(xù)，不連續(xù)怎么說(shuō)？,15,逆反律 (假言易位) E24 Ｐ→Ｑ ?¬Ｑ→ ¬Ｐ 原命題和逆反命題等價(jià),16,等值表達(dá)式 E15 Ｐ?Ｑ?（Ｐ→Ｑ）Λ（Ｑ→Ｐ） 以前我們證明 P 當(dāng)且僅當(dāng)Q，要分兩步證明，充分性和必要性。這個(gè)表達(dá)式說(shuō)明

11、我們這樣做是對(duì)的。等價(jià)否定等值式: P?Q ?┐P?┐Q,17,零律 E16 Ｐ∨Ｔ?Ｔ E17 ＰΛＦ?Ｆ 同一律 E18 Ｐ∨Ｆ?Ｐ E19 ＰΛＴ?Ｐ,18,互補(bǔ)律 排

12、中律 E20 Ｐ∨¬Ｐ?Ｔ 矛盾律 E21 ＰΛ¬Ｐ?Ｆ,19,輸出律 E22 Ｐ→（Ｑ→Ｒ）? （ＰΛＱ）→Ｒ 一個(gè)大前提和一個(gè)小前提，可以把兩個(gè)前提放一起說(shuō)。證明 E22,20,21,,歸繆律 E23 （Ｐ→Ｑ）Λ（Ｐ→¬Ｑ）?&

13、#172;Ｐ 同一個(gè)前提推出兩個(gè)矛盾的結(jié)論，說(shuō)明前提是錯(cuò)的證明 E23,22,1.2.3 永真蘊(yùn)含式定義 如果A→B是一永真式，那么稱(chēng)為永真蘊(yùn)含式，記為A ?B，讀做“A永真蘊(yùn)含B” 常用的永真蘊(yùn)含式如下表,23,永真蘊(yùn)含式,永真蘊(yùn)含式也可用真值表證明，但也可用以下辦法證明: (1) 假定前件是真，若能推出后件是真，則此蘊(yùn)含式是真 　　 (2) 假定后件是假，若能推出前

14、件是假，則此蘊(yùn)含式是真(因按逆反律)。,26,例: 證明┐Q?（P→Q）?┐P1) 法1：真值表2) 法2：若 ┐Q?(P→Q)為真，則 ┐Q，P→Q為真， 所以Q為假，P為假，所以┐P為真。3) 法3：若┐P為假，則P為真，再分二種情況： ①若Q為真，則┐Q為假,從而┐Q?（P→Q） 為假.②若Q為假，則P→Q為假，則┐Q?（P→Q）為假.根據(jù)① ②，所以 ┐Q?（P→Q）

15、?┐P 上面給的永真蘊(yùn)含式都可以用上述方法加以推證.,27,,恒等式與永真蘊(yùn)含式的關(guān)系:定理 設(shè)P,Q為任意兩個(gè)命題公式,P?Q的充要條件為 P?Q且Q?P.證：若P?Q，則P?Q為永真式 因?yàn)?P?Q ?（P→Q）?（Q→P） 所以 P→Q，Q→P為永真式,從而 P?Q，Q?P. 反之，若P?Q，Q?P，則P→Q，Q→P為永真式, 所以（P→Q）?（Q→P）為

16、永真式， 從而 P?Q為永真式，即P?Q.,1.2.4 恒等式和永真蘊(yùn)含式的性質(zhì)(1) 若A? B、B? C，則A?C; 若A?B、B ?C， 則A?C。邏輯恒等和永真蘊(yùn)含都是傳遞的。 (2) 若A?B、A?C，則A?B∧C。(3) 若A?B且C?B，則A?C?B,1.2.5 代入規(guī)則和替換規(guī)則代入規(guī)則 一重言式中某個(gè)命題變?cè)霈F(xiàn)的每一處均代入以同一公式后，所得

17、的仍是重言式。,代入規(guī)則給定一命題公式A(P1， P2，…，Pn )，Pi 是命題變?cè)?，若?）用某些命題公式 Qi 代換 A 中的一些命題變?cè)狿i （2）用命題公式Qi 代換Pi，則必須用Qi 代換Ｂ中的所有Pi由此而得到的新的命題公式 B 稱(chēng)為命題公式 A 的代入實(shí)例。若 A是重言式，則得到的代入實(shí)例 B 也是重言式。,30,替換規(guī)則 設(shè)有恒等式A?B，若A 是C的子公式，在C中出現(xiàn)A的地方用B

18、(不必每一處)替換而得到公式D，則C? D。,31,因此，我們可以說(shuō)前面兩個(gè)表中的字符P、Q和R不僅代表命題變?cè)?而且可以代表命題公式，T和F不僅代表真命題和假命題，而且可以代表重言式和永假式。,32,驗(yàn)證命題公式恒等的方法：1.真值表法 變?cè)容^少的情況下常用。2.等值演算法.基本恒等式和帶入，替換規(guī)則。3.蘊(yùn)含法 P?Q的充要條件為P?Q且Q?P.,34,例1： 證明 P?┐Q?Q ?P?Q證： (P?┐Q)?Q?

19、(P?Q)?(┐Q?Q)?(P?Q)?T?P?Q例2：證明（P→Q）→（Q?P）? P?Q?R證：（P→Q）→（Q?P） ?（┐P?Q）→（Q?R） ? ┐（┐P?Q）?（Q?R） ?（P?┐Q）?（Q?R） ?（P?Q?R）?（┐Q?Q?R） ? P?Q?R,例：證明： （（Ｐ∨Ｑ）Λ¬（¬ＰΛ（¬Ｑ∨¬Ｒ）））∨（¬ＰΛ¬Ｑ

20、）∨（¬ＰΛ¬Ｒ）為一永真式,35,例：證明： （（Ｐ∨Ｑ）Λ¬（¬ＰΛ（¬Ｑ∨¬Ｒ）））∨（¬ＰΛ¬Ｑ）∨（¬ＰΛ¬Ｒ）為一永真式證明： （（Ｐ∨Ｑ）Λ¬（¬ＰΛ（¬Ｑ∨¬Ｒ）））∨（¬ＰΛ¬Ｑ）∨（¬ＰΛ¬Ｒ） ?（（Ｐ∨Ｑ）Λ（Ｐ∨（ＱΛＲ）

21、））∨¬（Ｐ∨Ｑ）∨¬（Ｐ∨Ｒ）　 ? （（Ｐ∨Ｑ）Λ（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））∨¬（（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ）） ?（（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））∨¬（（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））?Ｔ∵它是Ｐ∨¬Ｐ（永真式）的代換實(shí)例，永真式的代換實(shí)例仍為永真式！,36,1.2.6 對(duì)偶原理限制性公式 如果命題公式 A 中只出現(xiàn)命題變?cè)⒚}常元 (T, F)、命題聯(lián)結(jié)詞符號(hào) ┐，Λ和∨，稱(chēng)A為限制

22、性（命題）公式。對(duì)偶公式 設(shè)A是限制性公式，將A中Λ換成∨，∨換成Λ，T換成F，F(xiàn)換成T，得到的公式稱(chēng)為A的對(duì)偶公式，記為 A*。,內(nèi)否公式 設(shè)A是限制性公式，將A中出現(xiàn)的所有原子項(xiàng)（命題變量或命題常量）Pi 換成 ┐Pi，得到的公式稱(chēng)為A的內(nèi)否公式，記為 A┐。,39,定理 : 設(shè)A，A*是對(duì)偶式， P1 , P2 ,…,Pn是出現(xiàn)于A和A*中的所有命題變?cè)?則 ┐A(P1 , P2 ,…,Pn )?A*（┐

23、P1 , ┐P2 ,…, ┐Pn） 是推廣的德·摩根定律 。 定理可表示為 ┐A ? (A*)┐,40,對(duì)偶原理 : 如果A和B是限制性公式，并且A?B ,則 A*?B*例1：因?yàn)椋?P?(P?Q)?P （吸收律） 由對(duì)偶原理: P?(P?Q) ?P例2: 若A?1 則 A*?(1)* 即 A*?0.例3: 設(shè)A為 (P?Q)?(┐P?(┐P?