《計算機數(shù)學(xué)基礎(chǔ)(1)—離散數(shù)學(xué)》學(xué)習(xí)輔導(dǎo)
發(fā)布人： 日期：2007-03-21 00:00瀏覽次數(shù)：4274點贊次數(shù)：0
湛江開大,湛江開放大學(xué),湛江市財政職業(yè)技術(shù)學(xué)校,湛江市廣播電視大學(xué),湛江電大,中專教育,中職教育,成人教育,成人大專,成人本科，官網(wǎng),教育部電子注冊，國際學(xué)歷綠卡。湛江開放大學(xué)（湛江市廣播電視大學(xué)）辦學(xué)三十年來...
《計算機數(shù)學(xué)基礎(chǔ)(1)—離散數(shù)學(xué)》學(xué)習(xí)輔導(dǎo)
《計算機數(shù)學(xué)基礎(chǔ)（1）—離散數(shù)學(xué)》是中央廣播電視大學(xué)開放本科教育計算工程類計算機科學(xué)與技術(shù)專業(yè)教學(xué)中重要的核心基礎(chǔ)課程，它是學(xué)習(xí)專業(yè)理論中不可少的數(shù)學(xué)工具。
通過本課程的學(xué)習(xí)，要使學(xué)生具有現(xiàn)代數(shù)學(xué)的觀點和方法，并初步掌握處理離散結(jié)構(gòu)所必須的描述工具。同時，也要培養(yǎng)學(xué)生抽象思維和慎密概括的能力，使學(xué)生具有良好的開拓專業(yè)理論的素質(zhì)和使用所學(xué)知識，分析和解決實際問題的能力。
本課程包括數(shù)理邏輯、集合論、圖論和代數(shù)系統(tǒng)。這是一門理論性較強，應(yīng)用性較廣的課程。因此，通過本課程的學(xué)習(xí)，使學(xué)生：掌握離散數(shù)學(xué)的基本概念和基本原理，進一步提高抽象思維和邏輯推理的能力。
按照教學(xué)大綱，我們逐次分章進行輔導(dǎo)，供師生學(xué)習(xí)參考。
第1章 命題邏輯
一、教學(xué)基本要求
1. 理解命題概念，會判斷語句是不是命題。
2. 了解六個聯(lián)結(jié)詞概念，掌握由它們構(gòu)成的公式及真值表：①ØP(否定式); ②PÙQ(合取式);③PÚQ(析取式);④P®Q(蘊含式);⑤P«Q(等價式)；⑥P`VQ[不可兼或式(異或式)]。
熟練掌握求給定公式真值表的方法。
3. 理解公式、公式解釋、永真式(重言式)、永假式(矛盾式)和可滿足式等概念。
記住基本等值式，掌握用真值表法和等值演算法判別公式類型和公式等值變換的方法。
4. 理解析取(合取)范式概念，熟練掌握利用基本等值式或真值表將公式化為析取(合取)范式的方法。
5. 了解極小(大)項的概念，掌握求主析取(合取)范式的方法。
6. 了解有效結(jié)論(邏輯結(jié)果)的概念，掌握判斷重言蘊含式(推理是否有效)的五種方法
(1) 真值表法；(2) 等值演算法(記住基本等值式)；(3) 主析取(合取)范式法；
(4) 直接證法：掌握P規(guī)則和T規(guī)則，及常用重言蘊含式、等值式。
(5) 間接證法(反證法)：掌握PC規(guī)則。
本章重點：命題與聯(lián)結(jié)詞，公式與解釋，真值表，(主)析取(合取)范式，重言式的判定。
二、學(xué)習(xí)輔導(dǎo)
1.1 命題與聯(lián)結(jié)詞
命題是推理的基本要素。自然語言將命題表述為具有確定真假意義的陳述句。若該語句表述的意義符合事實，則稱其為真命題。若該語句表述的意義不符合事實，則稱其為假命題。我們用0或F表示假命題；用1或T表示真命題。判斷一個句子是否為命題，應(yīng)首先判斷它是否為陳述句。再判斷它是否有唯一的真值。可見命題必須具備二個條件：其一，語句是陳述句；其二，語句有唯一確定的真假意義。
例如，考察下列語句
“雪是黑的”，“北京是中國的首都”是陳述句，都有確定的真假意義，是命題，前者為假命題；后者為真命題。
“21世紀(jì)時有人住在月球上”是陳述句，今后若干年，可以證明它要么是真，要么是假，故是命題。
“你是誰?” 不是命題，它是疑問句，不是陳述句；
“x+y<7”不是命題。它的真假意義不確定。如x=100，y=-84，則“x+y<7”為假；而x=－91，y=78，則“x+y<7”為真。
以上所舉各陳述中都是簡單陳述句，它們不能再分解成更簡單的句子，這就是原子命題(簡單命題)。本章不再進一步分析原子命題的內(nèi)部結(jié)構(gòu)，下一章討論謂詞邏輯時再分析它的內(nèi)部結(jié)構(gòu)。
由若干個原子命題通過聯(lián)結(jié)詞構(gòu)成的命題就是復(fù)合命題。
我們講了六個聯(lián)結(jié)詞。
1. “Ø”否定聯(lián)結(jié)詞，P是命題，ØP是P的否命題。是由聯(lián)結(jié)詞 Ø 和命題P組成的復(fù)合命題。
例如，P：猩猩是人。
ØP：猩猩不是人。
P：上海是中國最大的城市。
ØP：上海不是中國最大的城市。
P與ØP的真假是相互對立的，P為真，則ØP為假；反之P為假，則ØP為真。
2. “Ù”合取聯(lián)結(jié)詞，P，Q是命題，PÙQ是P，Q的合取式，是聯(lián)結(jié)詞Ù和命題P，Q組成的復(fù)合命題?！?Ugrave;”在語句中相當(dāng)于“不但…而且…”，“既…又…”。PÙQ取值1，當(dāng)且僅當(dāng)P，Q均取1；PÙQ取值為0，只要P，Q之一取0。
例如，丘玉學(xué)習(xí)很好，而且非常努力。就可以符號化為：P：“丘玉學(xué)習(xí)很好”Q：“丘玉學(xué)習(xí)非常努力”，記作PÙQ。
3. “Ú”析取聯(lián)結(jié)詞，“`Ú”不可兼析取(異或)聯(lián)結(jié)詞，P，Q是命題，PÚQ是P，Q的析取式，是聯(lián)結(jié)詞Ú和命題P，Q組成的復(fù)合命題。P`ÚQ是P，Q的不可兼析取式，是聯(lián)結(jié)詞`Ú和命題P，Q組成的復(fù)合命題。聯(lián)結(jié)詞“Ú”或“`Ú”在一個語句中都表示“或”的含義，可以表示相容或，也可以表示排斥或。`Ú表示不相容的或。即“P`ÚQ”«“ØPÙQÚPÙØQ”。
如“趙志宏學(xué)習(xí)俄語或英語”，是相容或，記P：“趙志宏學(xué)習(xí)俄語”，Q：“趙志宏學(xué)習(xí)英語”，命題符號化為“PÚQ”；
又如“李宏生于1978年或1980年”，是排斥或，不可兼或，記P：“李宏生于1978年”，Q：“李宏生于1980年”，命題符號化為P`ÚQ。
PÚQ取值為1，只要P，Q之一取值為1，只有P，Q均取值為0時，PÚQ取值為0。
P`ÚQ取值為1當(dāng)且僅當(dāng)P，Q取值不同；P`ÚQ取值為0當(dāng)且僅當(dāng)P，Q取值相同。
4. “«” 等價聯(lián)結(jié)詞，P，Q是命題，P«Q是P，Q的等價式，是聯(lián)結(jié)詞«和命題P，Q組成的復(fù)合命題?！?laquo;”在語句中相當(dāng)于“…當(dāng)且僅當(dāng)…”，P«Q取值1當(dāng)且僅當(dāng)P，Q取值相同。
例如，“長城是中國的古代的偉大建筑”，“長江是中國最長的河流”。它們的真值是相同的，可記作P：“長城是中國古代的偉大建筑”，Q：“長江是中國最長的河流”，有P«Q真值是1。
又如A：“3×5＝12”，B：“石家莊是河南省會”，有A«B真值是1，
再如，P1：“北京的1月份最冷”，P2：“北方的7月份最熱”，有P1«P2真值為0。
5. “®”蘊含聯(lián)結(jié)詞，P，Q是命題，P®Q是P，Q的蘊含式，是聯(lián)結(jié)詞®和命題P，Q組成的復(fù)合命題。P®Q取值為0，只有P取值為1，Q取值為0時；其余各種情況，均有P®Q取值為1。
注意：在語句中，P®Q，有時也解釋為“若P，則Q”。似乎P®Q是“因果關(guān)系”，但是不一定總有因果關(guān)系。只要P，Q是命題(即有真值)，那么P®Q就是命題(即有真值)。
不管P，Q是否有無因果關(guān)系。
例如，P：今晚開會，Q：今晚我到校。
有P®Q，如果今晚開會，我今晚到校(有因果關(guān)系)。它的真值是1。
又如，A：雪是白的，B：太陽從西邊出來。
有A®B，如果雪是白的，太陽從西邊出來(沒有因果關(guān)系)，它的真值是0。
1.2 命題公式、永真性的判定或命題公式的分類
命題公式的永真性包括判定命題公式是永真的(重言式)、永假的(矛盾式)。具體判定方法有兩種：
其一是真值表法，對于任給一個公式，列出該公式的真值表，觀察真值表的最后一列是否全為1(或全為0)，若真值表的最后一列全為1，則該公式為永真式；若真值表的最后一列全為0，則該公式是永假式；若真值表的最后一列既非全為1，又非全為0，則該公式是可滿足式。
例1.1 判定公式P®Q與ØPÚQ是否等值。
解 列公式P®Q與ØPÚQ的真值表。如表1－1。
表1－1 公式P®Q與ØPÚQ的真值表
|
P |
Q |
P®Q |
ØP |
ØPÚQ |
P®Q«ØPÚQ |
|
0 |
0 |
1 |
1 |
1 |
1 |
|
0 |
1 |
1 |
1 |
1 |
1 |
|
1 |
0 |
0 |
0 |
0 |
1 |
|
1 |
1 |
1 |
0 |
1 |
1 |
由表可知，公式P®Q與公式ØPÚQ是等值的。
由表的最后一列可知，P®Q«ØPÚQ是重言式。
其二是推導(dǎo)法。利用基本等值式(雙重否定律、冪等律、交換律、結(jié)合律、分配律、吸收律、摩根律、同一律、零律、否定律、蘊含等值式、等價等值式、假言易位和等價否定等值式等)，對給定公式進行等值推導(dǎo)，若該公式的真值為1，則該公式是永真式；若該公式的真值為0，則該公式為永假式。
1.3 范式
求范式，包括求析取范式、合取范式、主析取范式和主合取范式。關(guān)鍵有兩點：其一是準(zhǔn)確掌握范式定義；其二是巧妙使用基本等值式中的分配律、同一律和摩根律，結(jié)果的前一步適當(dāng)使用冪等律。
在范式中只有聯(lián)結(jié)詞Ù和Ú，命題變項或其否定用聯(lián)結(jié)詞Ú，Ù把聯(lián)結(jié)起來。主范式要求命題變項齊全，按極小(大)項排列起來。
于是有求范式的步驟。
求析取(合取)范式的步驟：
① 將公式中的聯(lián)結(jié)詞都化成Ø，Ù，Ú，在析取(合取)范式中不能有聯(lián)結(jié)詞®，«，`Ú；
② 將否定聯(lián)結(jié)詞Ø消去或移到各命題變項之前；
③ 利用分配律、結(jié)合律等，將公式化為析取(合取)范式。
求命題公式A的主析取(合取)范式的步驟
① 求公式A的析取(合取)范式；
② “消去”析取(合取)范式中所有永假式(永真式)的析取項(合取項)，如PÙØP(PÚØP)用0(1)替代。用冪等律將析取(合取)范式中重復(fù)出現(xiàn)的合取項(析取項)或相同的變項合并，如PÙP(PÚP)用P替代，miÚmi(MiÙMi)用mI(Mi)替代。
③ 若析取(合取)范式的某個合取項(析取項)B不含有命題變項Pi或ØPi，則添加PiÚØPi(PiÙØPi)，再利用分配律展開，使得每個合取項(析取項)的命題變項齊全；
④ 將極小(極大)項按由小到大的順序排列，用S(P)表示。
1.4 命題演算的推理理論
掌握演繹或形式證明，進行邏輯推理時一是要理解并掌握14個重言蘊含式(即I1～I14)，17個等值式(E1～E17)；二是會使用三個規(guī)則(P規(guī)則、T規(guī)則和CP規(guī)則)。
要多做一些練習(xí)，重言蘊含式和等值式要靠練習(xí)加以記憶，而不能靠死記。
例 判別下列語句是否命題？如果是命題，指出其真值。
(1) 是無理數(shù)；
(2) 存在最大的質(zhì)數(shù)；
(3) 中國是一個人口眾多的國家；
(4) 這座樓可真高??！
(5) 你喜歡黃河嗎？
(6) 請你跟我走；
(7) 火星上也有人。
解 (1) 是命題，真值為1；
(2) 是命題，真值為0；
(3) 是命題，真值為1；
(4),(5),(6)不是命題。(4)，(5)不是陳述句,它們沒有確定的真值。(6)的真值無法確定。
(7) 是命題。真值是唯一的，遲早會被指出。
例8 將下列命題符號化：
(1) 雖然交通堵塞，但是老王還是準(zhǔn)時到達火車站；
(2) 黎明是計算機系的學(xué)生，他住在2號樓305室或412室；
(3) 張三和李四是好朋友；
(4) 張力是三好學(xué)生或優(yōu)秀共青團員
(5) 老李或小刁中有一個人去廣州出差。
解 (1) 首先用字母表示原子(簡單)命題。
P：交通堵塞，Q：老王準(zhǔn)時到達火車站。
因為本小題強調(diào)“交通堵塞”和“老王準(zhǔn)時到達火車站”這兩件事，因此該命題可以符號化為：PÙQ。
(2) 首先用字母表示原子(簡單)命題。
P：黎明是計算機系的學(xué)生； Q：黎明住在2號樓305室。
R：黎明住在2號樓412室。
因為黎明只能住在一個房間，305室或412室的“或”是排斥或。因此該命題符號化為
(3) “張三和李四是好朋友”是一個簡單命題。如果把它拆成“張三是好朋友”，“李四是好朋友”，就不成為完整的語句了。該命題符號化為P：張三和李四是好朋友。
(4) 首先用字母表示原子(簡單)命題。
P：張力是三好學(xué)生； Q：張力是優(yōu)秀共青團員。
此處的“或”是相容或，故該命題符號化為PÚQ。
(5) 首先用字母表示原子(簡單)命題。
P：老李去上海出差； Q：小刁去上海出差。
要求只能一個人出差，因此此處的“或”是排斥或，該命題符號化為P`ÚQ，也可以表示成(PÙØQ)Ú(ØPÙQ)