離散數(shù)學(xué)第一章知識點總結(jié)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上離散數(shù)學(xué)第一章知識點總結(jié)（僅供參考）1.判斷給定的句子是否為命題的基本步驟：首先應(yīng)是陳述句；其次要有唯一的真值。 例：（1）我正在說謊。 不是命題。因為無法判定其真假值，若假設(shè)它為假即我正在說謊，則意味著它的反為真，即我正在說實話，二者相矛盾；若假定它為真即我正在說實話，則意味著它的反為假，我正在說謊，二者也相矛盾。這其實是一個語義上的悖論。悖論不是命題 （2）x-y2。 不是命題。因為x, y的值不確定，某些x, y使xy2為真，某些x, y使xy2為假，即xy2的真假隨x, y的值的變化而變化。因此xy2的真假無法確定，所以xy2不是命題。 2.命題可以分為兩種類

2、型：原子命題（不能再分解為更簡單命題，又可稱為簡單命題）； 復(fù)合命題(通過聯(lián)結(jié)詞、標(biāo)點符號將原子命題聯(lián)結(jié)而成的命題）3. 命題常元：一個命題標(biāo)識符如果表示確定的簡單命題，就稱為命題常元 命題變元：如果一個命題標(biāo)識符只表示任意簡單命題的位置標(biāo)志，就稱它為命題變元注：當(dāng)命題變元P用一個特定的簡單命題取代時，P才能確定真值，這時也稱對P進行指派4.聯(lián)接詞：（1）否定聯(lián)接詞：假為真，真為假；還可以用“非”、“不”、“沒 有”、“無”、 “并不”等多種方式表示否定 （2）合取聯(lián)接詞：一個為假就為假還可用“并且”、“同時”、“以及”、“既 又”、“不但而且”、“雖然但是”等多種方 式表達合取 （3）析取聯(lián)

3、接詞：一個為真就為真；一般用或表示 注：聯(lián)結(jié)詞是可兼或，因為當(dāng)命題P和Q的真值都為真時， 其值也為真。但自然語言中的“或”既可以是“排斥或” 也可以是“可兼或”。 例1.6 晚上我們?nèi)ソ淌覍W(xué)習(xí)或去電影院看電影。（排斥或） 例1.7 他可能數(shù)學(xué)考了100分或英語考了100分。（可兼或） 例1.8 劉靜今天跑了200米或300米遠。（既不表示“可兼或” 也不表示“排斥或”，它只是表示劉靜所跑的大概路程， 因此它不是命題聯(lián)結(jié)詞，故例1.8是原子命題。） （4）蘊涵聯(lián)結(jié)詞： 前真后假才為假；還可以用當(dāng)則、因為所 以、僅當(dāng)、只有才、除非才、除非、 否則非 表示 (5)等價聯(lián)接詞： 同真同假才為真；還可以

4、用當(dāng)且僅當(dāng)、充分必要表示5.命題公式：1）單個命題變元是合式公式，并簡稱為原子命題公式； 2）如果A是合式公式，那么(A)也是合式公式； 3）如果A, B都是合式公式，那么(AB ), (AB ), (AB ), (A B )都是合式 公式； 4）當(dāng)且僅當(dāng)有限次地應(yīng)用1), 2), 3)所得到的包含命題變元、聯(lián)結(jié)詞和括號的字 符串是合式公式。 根據(jù)定義1.6可知，P, (P ), (P (PQ ), (PQ )P ), (P Q ) R ) 都是命題公式。而 (P ), (P Q, (P Q ) R )都不是命題公式。 6. n元命題公式：一個命題公式中總共包含有n個不同的命題變元7. 1）若

5、公式A是單個的命題變元，則稱A為0層公式。 2）稱A是n+1（n0）層公式是指下面情況之一： （1）A=B, B是n層公式； （2）A=BC,其中B, C分別為i層和j層公式，且n=max(i,j); （3）A=BC,其中B, C的層次同（2）; （4）A=BC,其中B, C的層次同（2）; （5）A=BC,其中B, C的層次同（2）; 3）若公式A的層次為k,則稱A是k層公式。例1.19 （PQ）R為3層公式。 (PQ）(RS) P) 為4層公式。8. 真值表p17可分為重言式（永真式）、矛盾式（永假式）、可滿足式9.邏輯等價：若對出現(xiàn)在A與B中的所有命題變元的任一組賦值，公式A和B的真值都

6、相 同，則稱公式A與B是邏輯等價或稱邏輯相等，記作A B. 邏輯等價公式（熟記）：1）雙重否定 A A 2）冪等律AAA 、AAA 3）交換律ABBA、 ABBA 4）結(jié)合律 (AB)CA(BC) 、(AB)CA(BC) 5）分配律 A(BC) (AB)(AC) （對的分配律） A(BC) (AB)(AC) （對的分配律） 6）德摩根律(AB) AB (AB) AB 7）吸收律 A(AB) A A(AB) A 8）零律 A11 、A00 9）同一律 A 1A 、A 0A 10）排中律AA1 11）矛盾律 A A0 12）蘊涵律 ABAB 13）等價律A B(AB)(BA) 14）假言易位律AB

7、BA 15）等價否定律A BAB 16）歸謬律 (AB)(AB) A10.邏輯蘊含：設(shè)A、B是任意公式，若AB是重言式，則稱A邏輯蘊涵B，記為AB 邏輯蘊含公式（熟記）：1）附加律A (AB) 2）化簡律(AB )A 3）假言推理 (AB)A B 4）拒取式(AB)B A 5）析取三段論(AB)B A 6）假言三段論(AB)(BC)(AC) 11. 對偶：在給定的僅使用聯(lián)結(jié)詞, , 的命題公式A中，若把和互換，0和1互換 而得到一個命題公式A*，則稱A*是A的對偶式。 顯然，A也是A*的對偶式；可見，A*和A互為對偶式且(A*)*=A 注：設(shè)A和B是兩個命題公式，若AB，則A*B*12.范式：

8、1）一個簡單析取式是重言式當(dāng)且僅當(dāng)它同時含某個命題變元及它的否定式。 2）一個簡單合取式是矛盾式當(dāng)且僅當(dāng)它同時含某個命題變元及它的否定式。 析取、合取范式：1）由有限個簡單合取式構(gòu)成的析取式稱為析取范式。 2）由有限個簡單析取式構(gòu)成的合取式稱為合取范式。 3）析取范式與合取范式統(tǒng)稱為范式。 主范式、極小值、極大值p35-p37 求主析取范式、主合取范式的四個方法：p37-3913. 有效結(jié)論：設(shè)A1,A2,Ak和B都是命題公式，若對于A1,A2,Ak和B中出現(xiàn)的命題 變元的任意一組賦值， 或者A1A2 Ak為假， 或者當(dāng)A1A2 Ak為真時，B也為真， 則稱由前提A1,A2,Ak推出B的推理是

9、有效的或正確的，并稱B是有效結(jié)論。 判斷推理有效性的方法：（1）真值表法、（2）邏輯等價演算法、（3）主析（合）取范式法 14. 命題演算推證的命題定律（9、10）和推理定律(熟記）p4315.題演算推證由三個要素組成：推理根據(jù)、推理規(guī)則和證明方法。 1）推理根據(jù)：命題演算推證的命題定律和推理定律；即主要指已知的基本邏輯等價式和 邏輯蘊涵式（見表1.17） 2）推理規(guī)則: （1） 前提引入規(guī)則（P規(guī)則）：在推證的任何步驟上都可以引入前提。 （2） 結(jié)論引入規(guī)則（T規(guī)則）：在推證的任何步驟上所得到的結(jié)論都可以作為后繼 證明的前提。 （3）附加前提規(guī)則（CP規(guī)則）：若從A和B能有效地推出C，則從A

10、可有效地推 出BC。（通常在結(jié)論為蘊涵式時使用） 例：構(gòu)造下列推理的證明： 前提：(P Q )，(P R )，(QS ) 結(jié)論:SR。 證：(1) P Q P (2) QS P (3) Q S T (2) E (4) P S T (1)(3) I (5) S P T (4) E (6) P R P (7) SR T (5)(6) I (8) SR T (7) E (9) SR T (8) E 證畢 3)證明方法：a.直接證明法，如前例 b.反證法：設(shè)命題公式集合A1, A2, , Am是相容的，那么從A1, A2, ,Am出發(fā)可邏輯地推出結(jié)論B的充分必要條件是從A1, A2, , Am,B可邏輯地推出一個矛盾式。例：如果今天我沒課，則我去機房上機或去圖書館查資料；若機房沒有空機器，則我沒 法去上機；今天我沒課，機房也沒有空機器，所以我去圖書館查資料。證：設(shè)P：今天我沒課； Q：我去機房上機； R：我去圖書館查資料； S：機房沒有空機器 則上述語句可翻譯為命題關(guān)系式： PQR, SQ, P, S R (1) R P（結(jié)論的否定） (2) PQR P (3) P P (4) QR T (2)(3) I (5) Q T (4)(1) I (6) S Q P (7) S P (8) Q T (6)(7) I (9) QQ T (5)(8) I 證畢 c)附加前提證法：由(SB)C證