離散數(shù)學(xué)筆記

《離散數(shù)學(xué)筆記》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、離散數(shù)學(xué)教案第一章命題邏輯內(nèi)容：命題及命題聯(lián)結(jié)詞、命題公式的基本概念，真值表、基本等價(jià)式及永真蘊(yùn)涵式，命題演算的推理理論中常用的直接證明、條件證明、反證法證明等方法教學(xué)目的：1．熟練掌握命題、聯(lián)結(jié)詞、復(fù)合命題、命題公式及其解釋的概念。2．熟練掌握常用的基本等價(jià)式及其應(yīng)用。3．熟練掌握（主）析/合取范式的求法及其應(yīng)用。4．熟練掌握常用的永真蘊(yùn)涵式及其在邏輯推理中的應(yīng)用。5．熟練掌握形式演繹的方法。教學(xué)重點(diǎn)：1．命題的概念及判斷2．聯(lián)結(jié)詞，命題的翻譯3．主析（合）取范式的求法4．邏輯推理教學(xué)難點(diǎn)：1．主析（合）取

2、范式的求法2．邏輯推理1.1命題及其表示法1.1.1命題的概念數(shù)理邏輯將能夠判斷真假的陳述句稱作命題。1.1.2命題的表示命題通常使用大寫(xiě)字母A，B，…，Z或帶下標(biāo)的大寫(xiě)字母或數(shù)字表示，如Ai，[10]，R等，例如A1：我是一名大學(xué)生。A1:我是一名大學(xué)生.[10]：我是一名大學(xué)生。R：我是一名大學(xué)生。1.2命題聯(lián)結(jié)詞1.2.1否定聯(lián)結(jié)詞﹁P01101.2.2合取聯(lián)結(jié)詞∧00001010011146離散數(shù)學(xué)教案1.2.3析取聯(lián)結(jié)詞∨0000111011111.2.4條件聯(lián)結(jié)詞→0010111001111.2.

3、5雙條件聯(lián)結(jié)詞0010101001111.2.6與非聯(lián)結(jié)詞↑001011101110性質(zhì)：（1）P↑P﹁（P∧P）﹁P；（2）（2）（P↑Q）↑（P↑Q）﹁（P↑Q）P∧Q；（3）（P↑P）↑（Q↑Q）﹁P↑﹁QP∨Q。1.2.7或非聯(lián)結(jié)詞↓001010100110性質(zhì)：（1）P↓P﹁（P∨Q）﹁P；（2）（P↓Q）↓（P↓Q）﹁（P↓Q）P∨Q；（3）（P↓P）↓（Q↓Q）﹁P↓﹁Q﹁（﹁P∨﹁Q）P∧Q。46離散數(shù)學(xué)教案1.3命題公式、翻譯與解釋1.3.1命題公式定義命題公式，簡(jiǎn)稱公式，定義為：（1）單個(gè)

4、命題變?cè)枪剑唬?）如果P是公式，則﹁P是公式；（3）如果P、Q是公式，則P∧Q、P∨Q、PQ、PQ都是公式；（4）當(dāng)且僅當(dāng)能夠有限次的應(yīng)用(1)、(2)、(3)所得到的包括命題變?cè)?、?lián)結(jié)詞和括號(hào)的符號(hào)串是公式。例如，下面的符號(hào)串都是公式：（（（（﹁P）∧Q）R）∨S）（（P﹁Q）（﹁R∧S））（﹁P∨Q）∧R以下符號(hào)串都不是公式：（（P∨Q）（∧Q））（∧Q）1.3.2命題的翻譯可以把自然語(yǔ)言中的有些語(yǔ)句，轉(zhuǎn)變成數(shù)理邏輯中的符號(hào)形式，稱為命題的翻譯。命題翻譯時(shí)應(yīng)注意下列事項(xiàng)：（1）確定所給句子是否為命題。

5、（2）句子中聯(lián)結(jié)詞是否為命題聯(lián)結(jié)詞。（3）要正確的選擇原子命題和合適的命題聯(lián)結(jié)詞。例：假如上午不下雨，我去看電影，否則就在家里讀書(shū)或看報(bào)。解：設(shè)P：上午下雨；Q：我去看電影；R：我在家里讀書(shū)；S：我在家里看報(bào)。本例可表示為：（PQ）∧（P（R∨S））。1.3.3命題公式的解釋定義設(shè)P1，P2，…，Pn是出現(xiàn)在命題公式G中的全部命題變?cè)?，指定P1，P2，…，Pn的一組真值，稱這組真值為G的一個(gè)解釋或賦值，記作I，公式G在I下的真值記作TI（G）。例如，G=（P∧Q）R，則I：110是G的一個(gè)解釋，在這個(gè)解釋下G

6、的真值為1，即TI（G）=1。1.4真值表與等價(jià)公式1.4.1真值表定義將公式G在其所有解釋下所取得的真值列成一個(gè)表，稱為G的真值表。構(gòu)造真值表的方法如下：（1）找出公式G中的全部命題變?cè)?，并按一定的順序排列成P1，P2，…，Pn。（2）列出G的2n個(gè)解釋，賦值從00…0（n個(gè)）開(kāi)始，按二進(jìn)制遞加順序依次寫(xiě)出各賦值，直到11…1為止（或從11…1開(kāi)始，按二進(jìn)制遞減順序?qū)懗龈髻x值，直到00…046離散數(shù)學(xué)教案為止），然后從低到高的順序列出G的層次。（3）根據(jù)賦值依次計(jì)算各層次的真值并最終計(jì)算出G的真值。例：G=

7、（P→Q）∧Q001000110010010111001.4.2命題公式的分類定義設(shè)G為公式：（1）如果G在所有解釋下取值均為真，則稱G是永真式或重言式；（2）如果G在所有解釋下取值均為假，則稱G是永假式或矛盾式；（3）如果至少存在一種解釋使公式G取值為真，則稱G是可滿足式。1.4.3等價(jià)公式定義設(shè)A和B是兩個(gè)命題公式，如果A和B在任意賦值情況下都具有相同的真值，則稱A和B是等價(jià)公式。記為AB。性質(zhì)定理設(shè)A、B、C是公式，則（1）AA（2）若AB則BA（3）若AB且BC則AC定理設(shè)A、B、C是公式，則下述等價(jià)

8、公式成立：（1）雙重否定律AA（2）等冪律A∧AA；A∨AA（3）交換律A∧BB∧A；A∨BB∨A（4）結(jié)合律（A∧B）∧CA∧（B∧C）（A∨B）∨CA∨（B∨C）（5）分配律（A∧B）∨C（A∨C）∧（B∨C）（A∨B）∧C（A∧C）∨（B∧C）（6）德·摩根律（A∨B）A∧B（A∧B）A∨B（7）吸收律A∨（A∧B）A；A∧（A∨B）A（8）零一律A∨11；A∧00（9）同一律A∨0A；A∧1