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

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

2、型：原子命題（不能再分解為更簡(jiǎn)單命題，又可稱為簡(jiǎn)單命題）； 復(fù)合命題(通過(guò)聯(lián)結(jié)詞、標(biāo)點(diǎn)符號(hào)將原子命題聯(lián)結(jié)而成的命題）3. 命題常元：一個(gè)命題標(biāo)識(shí)符如果表示確定的簡(jiǎn)單命題，就稱為命題常元 命題變?cè)喝绻粋€(gè)命題標(biāo)識(shí)符只表示任意簡(jiǎn)單命題的位置標(biāo)志，就稱它為命題變?cè)ⅲ寒?dāng)命題變?cè)狿用一個(gè)特定的簡(jiǎn)單命題取代時(shí)，P才能確定真值，這時(shí)也稱對(duì)P進(jìn)行指派4.聯(lián)接詞：（1）否定聯(lián)接詞：假為真，真為假；還可以用“非”、“不”、“沒(méi) 有”、“無(wú)”、 “并不”等多種方式表示否定 （2）合取聯(lián)接詞：一個(gè)為假就為假還可用“并且”、“同時(shí)”、“以及”、“既 又”、“不但而且”、“雖然但是”等多種方 式表達(dá)合取 （3）析取聯(lián)

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

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

5、公式A是單個(gè)的命題變?cè)?，則稱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.邏輯等價(jià)：若對(duì)出現(xiàn)在A與B中的所有命題變?cè)娜我唤M賦值，公式A和B的真值都

6、相 同，則稱公式A與B是邏輯等價(jià)或稱邏輯相等，記作A B. 邏輯等價(jià)公式（熟記）：1）雙重否定 A A 2）冪等律AAA 、AAA 3）交換律ABBA、 ABBA 4）結(jié)合律 (AB)CA(BC) 、(AB)CA(BC) 5）分配律 A(BC) (AB)(AC) （對(duì)的分配律） A(BC) (AB)(AC) （對(duì)的分配律） 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）蘊(yùn)涵律 ABAB 13）等價(jià)律A B(AB)(BA) 14）假言易位律AB

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

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

9、有效的或正確的，并稱B是有效結(jié)論。 判斷推理有效性的方法：（1）真值表法、（2）邏輯等價(jià)演算法、（3）主析（合）取范式法 14. 命題演算推證的命題定律（9、10）和推理定律(熟記）p4315.題演算推證由三個(gè)要素組成：推理根據(jù)、推理規(guī)則和證明方法。 1）推理根據(jù)：命題演算推證的命題定律和推理定律；即主要指已知的基本邏輯等價(jià)式和 邏輯蘊(yùn)涵式（見(jiàn)表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é)論為蘊(yùn)涵式時(shí)使用） 例：構(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可邏輯地推出一個(gè)矛盾式。例：如果今天我沒(méi)課，則我去機(jī)房上機(jī)或去圖書(shū)館查資料；若機(jī)房沒(méi)有空機(jī)器，則我沒(méi) 法去上機(jī)；今天我沒(méi)課，機(jī)房也沒(méi)有空機(jī)器，所以我去圖書(shū)館查資料。證：設(shè)P：今天我沒(méi)課； Q：我去機(jī)房上機(jī)； R：我去圖書(shū)館查資料； S：機(jī)房沒(méi)有空機(jī)器 則上述語(yǔ)句可翻譯為命題關(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證