離散數(shù)學(xué)課程基本內(nèi)容

1、離散數(shù)學(xué)DISCRETE MATHEMATICS,教師:石兵Email:shibing_2009@scu.edu.cn,二零一三,重點(diǎn)詞 -- 定義命題(簡單命題\復(fù)合命題)命題表示基本連接詞重點(diǎn)掌握命題的翻譯,上次課重點(diǎn):,本次課重點(diǎn),命題公式解釋及真值表等價的定義證明推理的基礎(chǔ): 基本等價式,第二節(jié) 命題合適公式與真值表,一、命題合適公式定義1。原子命題標(biāo)識符是合適公式2。如果P、Q都是合適公式，則 ?

2、P、 ?Q、（P ? Q）、（P ? Q）、（P ?Q）、 （P ? Q）也都是合適公式。3。只有按照1 和 2 產(chǎn)生的公式是合適公式。,,約定： 1）以后我們用WFF (well-formed formula)表示術(shù)語“合適公式”。 2）簡稱合適公式為公式。 3）合適公式的外層括號可以去掉。例如 （（ P ?Q） ?（ ? P ?Q）） 可以寫成

3、 （P ?Q） ?（ ? P ?Q）。,二、子合適公式,定義： 設(shè)G是WFF，A是G的一部分，且A也是WFF，則稱 A是G的子合適公式。簡稱A 是G的子公式。 例如：P、Q、（P ? ? Q）、（P ?Q）都是（P ? ? Q） ?（P ?Q）的子公式。,三、命題公式的解釋,1。對公式G中的每個原子代以具體的命題稱為 對G的解釋。2。對原子代以真命題可以用對原子賦值

4、 1來表 達(dá)，對原子代以假命題可以用對原子賦值 0 來表達(dá)。3。公式在每種解釋下取得唯一的值。,例： 下面是對公式G=（R ? ? Q）?（P ?Q） 的一個解釋： P Q R 0 1 0

5、 在這個解釋下，公式G的值是 (0 ? 0） ? （0 ?1）=1。,四、公式的真值表,1。真值表：由公式的全部解釋構(gòu)成的表。 2。真值表類似于聯(lián)結(jié)詞功能表，公式的原子 列于最前幾列，表中每行對應(yīng)一種解釋。 3。如果公式中有n個原子，則表中有 2 n 個不 同的解釋行。,例： 構(gòu)造公式G=（R ? ? Q） ?（P ?Q） 的真值表。 解：公式中含

6、 3 個原子，故有 8 種可能的 解釋，見下表。,P Q R | R ? ? Q P ?Q | G0 0 0 | 0 1 | 10 0 1 | 1 1 | 10 1 0 | 0

7、 1 | 10 1 1 | 0 1 | 11 0 0 | 0 0 | 01 0 1 | 1 0 | 11 1 0 | 0

8、 1 | 11 1 1 | 0 1 | 1,例：構(gòu)造公式G1= P ?（P ?Q）和 G2= P ? ? (P? Q)的真值表。解：下面把兩個公式的真值表放在一起。P Q | P ?（P ?Q） | P ? ? （P ? Q） 0 0 |

9、 1 | 00 1 | 1 | 01 0 | 1 | 01 1 | 1 | 0,五、公

10、式的分類,1。永真式：在任何解釋下都取真值 1 的公式。 也叫做重言式，如P ?（P ?Q）。永真式 通常用符號T表示。2。永假式：在任何解釋下都取真值 0的公式。 也叫做矛盾式，如 P ? ? （P ? Q）。永假 式通常用符號F表示 。,3?？蓾M足式：至少在一種解釋下取真值 1 的公式。如 P ? Q等。 顯然，永真式是可滿足公式，而矛盾 式是不可滿足

11、公式。 作業(yè): 習(xí)題一 3,4(3) (7) 習(xí)題1. 2 1, 2(3)(7),第三節(jié) 命題公式的等價,一、定義：設(shè)A是 B兩個WFF，如果在任何解 釋下A和B都取相同的值，則說公式A和B 是等價的。1。A和 B等價記為 A ? B。2。定理1： A ? B當(dāng)且僅當(dāng)A ?B是永真式。,定理

12、1：證明要點(diǎn)： 當(dāng)A ? B時，任何解釋下A 和 B同值，因此 A ?B 是永真式。反之， 當(dāng)A ?B是永真式時，在任何解釋下A和 B必須同值，因此 A ? B。,例： 驗證 P ?Q ? ? P ? Q解：列出真值表如下：P Q | P ?Q |?P ? Q 0 0 | 1 | 10 1 | 1 |

13、 11 0 | 0 | 01 1 | 1 | 1從值表可以看出，等價式成立。,例： 驗證 ? （P ? Q） ? ? P ? ? Q解：列出真值表如下： P Q | ?（P ?Q） | ?P ? ? Q 0 0 | 1 |

14、 10 1 | 0 | 01 0 | 0 | 01 1 | 0 | 0從真值表可以看出，等價式成立。,二、基本等價式,在教材中列出了常用的 14個等價式，可以利用真值表加以驗證。它們表達(dá)了邏輯聯(lián)結(jié)詞滿足的運(yùn)算定律，

15、具有普遍意義，必須記住。 1。 ? （? P） ? P （雙重否定律） 2。P ? P ? P，P ? P ?P （冪等律） 3。P ? Q ? Q ? P，P ?Q ?Q ?P （交換律）,4。P ? （Q ? R）? （P?Q）? R （? P ?Q ? R） P ?（Q ? R） ?（P ?Q） ?R

16、 （? P ?Q ?R） （結(jié)合律）根據(jù)結(jié)合律，只含 ? 或只含? 的 公式，可以去掉括號。,5。 P ? （Q ?R） ? （P ? Q） ? （P ? R） P ? （Q ? R） ? （P ? Q） ? （P ? R）

17、 （分配律）6。 P ? （P ?R） ? P （吸收律） P ? （P ? R） ? P7。 ? （ P ? Q） ? ? P ? ? Q （德。摩根律） ? （P ? Q） ? ? P ? ? Q,8。P ? F ? P，P ?T ? P（同一律）9。P ? T ? T，P ? F ?F （零律）10。P ? ? P ? T，P ? ? P ?F（矛盾律）11。

18、 P ?Q ? ? P ? Q (條件詞轉(zhuǎn)化)12。 P ?Q ?（P ?Q）?（Q ?P） ? （P ? Q）? (? P ? ? Q ） (雙條件詞轉(zhuǎn)化),三、公式等價的性質(zhì),1。 A ? A （自反性）2。如果A ? B，則 B ? A （對稱性）3。如果A ? B， B ? C 則A ? C （傳遞性）

19、4。設(shè)A是公式 X 的一個子公式，且A ? B。 又設(shè)用 B取代X中的子公式A后得到的新 公式為Y，則 X ? Y。,證明要點(diǎn)：因為A ? B，因而在任何解 釋下，A和B取相同的值，因而X和 Y的 取值也都相同。 利用上面的性質(zhì)和基本等價式，就可以 使用等價變換的方法去證明公式的等價 問題，下面是兩個例子。,例1：證明 P ? Q ? ? Q ? ? P證明

20、： P ? Q ? ?P ? Q ? ? （? Q） ? ? P ? ?Q ? ?P,煤是黑的(原命題) 如果是煤,則是黑的( P->Q)煤是不黑的(否命題) ~(P->Q)黑的是煤(逆命題) 如果是黑的,則是煤( Q->P)不黑不是煤(逆否命題) 如果不黑,則不是煤( ~Q->~P)

21、,例2：證明(P ? Q) ? ( P ? R) ? P ?(Q ?R) 證明： （P ? Q） ? （ P ? R ) ?( ?P ? Q) ? ( ?P ? R) ? ?P ? ( Q ? R) ? P ?(Q ?R),

22、四、對偶式,1。定義：設(shè)G是不含? 和?的WFF。把G 中聯(lián)結(jié)詞 ? 換成 ? ，把 ? 換成 ? 、T換 成F、F換成T后得到的公式記為G*，稱 之為G的對偶式。 例如：G= ?P ? ( Q ? R) ，則G 的對偶式 為 G* = ?P ?（Q ? R）。,求一般WFF的對偶式，必須用基本等價 式先化去? 和? ，變成只含否定、析取、 合

23、取之類聯(lián)結(jié)詞的等價公式后再作。 2。 定理：設(shè)A、B都是WFF。如果A ? B， 則A* ? B*。,例如：設(shè)A = ?P ? ( Q ? R) B=（ ?P ? Q） ?（ ?P ? R) 顯然 ，A ? B。它們的對偶式分別是 A* = ?P ? ( Q ? R) B* =（ ?P ? Q）? （ ?P ? R) 同樣容