【正文】 P(2)$x216。xC(x)$x216。216。解論域：所有人的集合。T三、（10分）在謂詞邏輯中構(gòu)造下面推理的證明：每個喜歡步行的人都不喜歡做汽車，每個人或者喜歡坐汽車或者喜歡騎自行車。T)∧(T174。((T∧T)∨(T∧T)))219。(T174。((Q(1)∧R(1，1))∨(Q(2)∧R(1，2))))∧(P(2)174。((Q(1)∧R(x，1))∨(Q(2)∧R(x，2))))219。$y(Q(y)∧R(x，y)))219。F)219。(T174。((F∧F)∨(F∧F)))∧(T174。((Q(1)∧R(2，1))∨(Q(2)∧R(2，2))))219。(P(1)174。x(P(x)174。若P(1)＝P(2)＝T，Q(1)＝Q(2)＝F，R(1，1)＝R(1，2)＝R(2，1)＝R(2，2)＝F，則 x(P(x)174。$y(Q(y)∧R(x，y)))為真的解釋和為假的解釋。m0∨m1∨m3∨m5所以，其相應(yīng)的成真賦值為000、000110111：成假賦值為：0100、110。Q∨R)219。Q∨R)∧(216。P∨216。(216。P)∨216。P∨(Q∧216。Q)∨R 219。(216。216。（2）(P∨Q)174。(P174。Q)∧(Q174。P∨R)219。P∨R)∧(216。P∨R)219。(P∧216。R∨216。Q)∨((Q∨216。P∨R 219。Q)∨(Q∧216。P∨R)219。P∨Q)∧(216。216。(P174。Q)∧(Q174。R的主析取范式與主合取范式，并寫出其相應(yīng)的成真賦值和成假賦值。(P174。Q)∧(Q174。說明：打*號的內(nèi)容為選學(xué)內(nèi)容，不作為考核內(nèi)容。理解：代數(shù)系統(tǒng)的概念；代數(shù)運算的概念；代數(shù)運算的性質(zhì)、半群、群與子群的概念及其基本性質(zhì)；同態(tài)與同構(gòu)的概念。掌握：命題符號化；簡單的謂詞公式的解釋。第七章 謂詞邏輯教學(xué)內(nèi)容謂詞的概念，量詞的概念謂詞公式的解釋范式（前束范式）的概念與求法謂詞公式的等值式與蘊涵式謂詞邏輯的推理理論教學(xué)要求了解：謂詞邏輯的基本概念、基本理論與方法。理解：命題公式的概念，命題聯(lián)結(jié)詞的概念；范式的概念；命題邏輯的等值式與蘊涵式的概念。掌握：最小生成樹的Kruskal算法，求最優(yōu)樹的Huffman算法，前綴碼的求法。第五章 樹及其應(yīng)用教學(xué)內(nèi)容樹的定義及性質(zhì)生成樹與最小生成樹的概念與求解算法（Kruskal算法）根樹的概念及性質(zhì)最優(yōu)樹的概念與求解算法（Huffman算法）最優(yōu)樹的應(yīng)用（前綴碼的求法）教學(xué)要求了解：樹在計算機領(lǐng)域中的應(yīng)用。理解：歐拉回路與歐拉圖、漢密爾頓回路與漢密爾頓圖、平面圖等的概念及性質(zhì)。掌握：圖的表示方法；圖的路、回路及連通性的判斷；連通度的計算；相鄰矩陣及可達(dá)矩陣的有關(guān)計算。第二部分 圖論第三章 圖的基本概念與性質(zhì)教學(xué)內(nèi)容圖的概念與表示，有向圖、無向圖、度，圖同構(gòu)，子圖、補圖路與回路的概念圖的連通性與連通度概念、判定，點割集與割點，邊割集與割邊圖的矩陣表示及計算教學(xué)要求了解：圖論的基本內(nèi)容及其在計算機領(lǐng)域中的應(yīng)用；最短路的算法。理解：關(guān)系的概念，關(guān)系的性質(zhì)；復(fù)合關(guān)系、逆關(guān)系及關(guān)系的閉包的概念；等價關(guān)系與等價類、序關(guān)系等的概念；函數(shù)的概念及其性質(zhì)；逆函數(shù)與復(fù)合函數(shù)的概念。掌握：集合的表示與集合的運算，利用容斥原理進(jìn)行計數(shù)的方法。第一部分 集合論 第一章 集合教學(xué)內(nèi)容集合的概念與表示，集合間的關(guān)系和特殊集合 集合運算容斥原理教學(xué)要求了解：集合論的內(nèi)容；集合論方法的作用。第三部分 教學(xué)內(nèi)容和教學(xué)要求緒論教學(xué)內(nèi)容離散數(shù)學(xué)在計算機科學(xué)與技術(shù)專業(yè)學(xué)習(xí)中的作用離散數(shù)學(xué)的發(fā)展現(xiàn)狀學(xué)習(xí)本課程的目的與方法教學(xué)要求了解：離散數(shù)學(xué)課程的內(nèi)容。期末終結(jié)性考核由中央電大根據(jù)本課程教學(xué)大綱和考核說明的要求統(tǒng)一命題，統(tǒng)一考試時間。作業(yè)題目應(yīng)根據(jù)教學(xué)基本要求選擇，題量要適度，由易到難。3．充分利用多媒體資源通過網(wǎng)絡(luò)教學(xué)平臺，利用各種網(wǎng)上教學(xué)活動方式與教師、同學(xué)討論交流，及時解決學(xué)習(xí)中遇到的問題。要注意培養(yǎng)學(xué)生分析問題、解決問題的能力。要運用啟發(fā)式，采用講解、討論、答疑等方式，為學(xué)生進(jìn)行面授輔導(dǎo)或答疑。2．面授輔導(dǎo)與自學(xué)面授輔導(dǎo)是廣播電視大學(xué)遠(yuǎn)程開放教育的重要教學(xué)方式之一，也是學(xué)生與老師面對面交流、獲得疑難解答的重要途徑。1．視頻課視頻課是本課程的重要教學(xué)環(huán)節(jié)之一，是學(xué)生獲得本課程知識的主要學(xué)習(xí)方式之一，其包含電視課程與網(wǎng)絡(luò)流媒體課件兩部分。3．網(wǎng)上教學(xué)通過網(wǎng)上教學(xué)輔導(dǎo)、答疑、階段性總結(jié)和復(fù)習(xí)，提高學(xué)生自主學(xué)習(xí)的興趣，幫助學(xué)生掌握基本概念和基本方法，提高學(xué)生的動手能力以及解決實際問題的能力。文字教材中的每個學(xué)習(xí)單元附有相應(yīng)的輔導(dǎo)內(nèi)容，每章附有相應(yīng)的習(xí)題。1．文字教材文字教材是主要教學(xué)媒體，是教學(xué)和考核的基本依據(jù)，對其他教學(xué)媒體起紐帶作用，具有導(dǎo)學(xué)功能。下表給出該課程的主要教學(xué)內(nèi)容，視頻課程和輔導(dǎo)課程的學(xué)時分配。掌握：要求學(xué)生在理解的基礎(chǔ)上能夠應(yīng)用所學(xué)知識解決實際問題。了解：要求學(xué)生能正確判別有關(guān)概念、結(jié)論和方法。3．充分利用網(wǎng)絡(luò)教學(xué)技術(shù)進(jìn)行授課、答疑和討論。四、課程的教學(xué)方法和教學(xué)形式建議1．根據(jù)課程特點，建議采用多種教學(xué)媒體講解、應(yīng)用事例介紹等教學(xué)手段相結(jié)合的教學(xué)模式進(jìn)行教學(xué)。本課程主要內(nèi)容包括集合論、圖論與數(shù)理邏輯等三個方面的內(nèi)容。二、與相關(guān)課程的銜接、配合、分工后續(xù)課程：數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫應(yīng)用技術(shù)、操作系統(tǒng)等課程。同時，也要培養(yǎng)學(xué)生抽象思維和慎密概括的能力，使學(xué)生具有良好的開拓專業(yè)理論的素質(zhì)和使用所學(xué)知識，分析和解決實際問題的能力，為學(xué)生以后學(xué)習(xí)計算機基礎(chǔ)理論與專業(yè)課程打下良好的基礎(chǔ)。離散數(shù)學(xué)是計算機科學(xué)與技術(shù)專業(yè)的基礎(chǔ)核心課程。第一篇：離散數(shù)學(xué)教學(xué)大綱《離散數(shù)學(xué)》教學(xué)大綱第一部分 大綱說明一、課程的性質(zhì)、目的與任務(wù)離散數(shù)學(xué)是中央廣播電視大學(xué)電子信息類計算機科學(xué)與技術(shù)專業(yè)的一門統(tǒng)設(shè)必修學(xué)位課程。該課程的主要內(nèi)容包括：集合論、圖論、數(shù)理邏輯等。通過本課程的學(xué)習(xí)，使學(xué)生具有現(xiàn)代數(shù)學(xué)的觀點和方法，并初步掌握處理離散結(jié)構(gòu)所必須的描述工具和方法。本課程是一門理論性較強的課程，要求在完成基礎(chǔ)知識教學(xué)任務(wù)的同時，通過適當(dāng)?shù)膶嶋H應(yīng)用的介紹，提高學(xué)生的實際應(yīng)用能力的培養(yǎng)。三、課程的基本教學(xué)要求本課程是計算機科學(xué)與技術(shù)專業(yè)的基礎(chǔ)核心課程，教學(xué)內(nèi)容以基本概念、結(jié)論、算法、推理與證明方法，以及一般應(yīng)用方法的介紹為主，課程內(nèi)容突出簡明扼要、體系結(jié)構(gòu)清楚為原則。具體要求為：1．了解離散數(shù)學(xué)的主要組成部分，各個部分所涉及的基本內(nèi)容，及其在計算機科學(xué)與技術(shù)領(lǐng)域中的應(yīng)用；2．理解離散數(shù)學(xué)的的基本概念、結(jié)論、算法、應(yīng)用方法及適用范圍；3．掌握離散數(shù)學(xué)的的基本推理與證明過程、基本算法及應(yīng)用方法。2．保證提供一定的教學(xué)輔導(dǎo)手段與途徑，及時解答學(xué)生的疑問，同時注意培養(yǎng)學(xué)生獨立思考問題和解決問題的能力。五、教學(xué)要求的層次課程的教學(xué)要求分為了解、理解和掌握三個層次。理解：要求學(xué)生能正確理解有關(guān)概念、結(jié)論、算法和方法的含義，并且能進(jìn)行一定的邏輯推理與數(shù)學(xué)證明。第二部分 教學(xué)媒體與教學(xué)過程建議一、學(xué)分與學(xué)時分配課程教學(xué)的課內(nèi)時數(shù)為72學(xué)時，4學(xué)分，第二學(xué)期開設(shè)。課內(nèi)學(xué)時序號 教學(xué)內(nèi)容電視課學(xué)時 流媒體課件學(xué)時 5 6 6 2合計3 2 10輔導(dǎo)學(xué)時 2 3 4 5 緒論 集合論 圖論 數(shù)理邏輯 復(fù)習(xí)16 2 48二、多種媒體教材的總體說明本課程的教學(xué)媒體包括文字教材、視頻教材、CAI課件、網(wǎng)絡(luò)課程和網(wǎng)上教學(xué)等多種媒體。本課程文字教材的內(nèi)容與結(jié)構(gòu)采用主輔學(xué)習(xí)內(nèi)容合一、理論陳述與例題講解相結(jié)合的方式組織。2．視頻教材視頻教材是輔助教學(xué)媒體，包含電視課程與網(wǎng)絡(luò)流媒體課件兩部分，主要講授課程的重點、難點以及相關(guān)的習(xí)題等內(nèi)容，是對文字教材的強化和補充。三、教學(xué)環(huán)節(jié)本課程將利用多種媒體、采用多種方式進(jìn)行教學(xué)，使學(xué)生在自主學(xué)習(xí)的基礎(chǔ)上通過多種方法獲得知識和方法。有條件的地方應(yīng)盡量多組織學(xué)生收看視頻教學(xué)內(nèi)容，督促學(xué)生充分利用網(wǎng)絡(luò)教學(xué)資源。面授輔導(dǎo)課要緊密配合視頻和文字教材，依據(jù)教學(xué)大綱進(jìn)行輔導(dǎo)講解。要認(rèn)真?zhèn)湔n，批改作業(yè)。自學(xué)是電大學(xué)生獲得知識的重要方式，自學(xué)能力的培養(yǎng)也是高等教育的目的之一，要注意對學(xué)生自學(xué)能力的培養(yǎng)，學(xué)生自己更應(yīng)重視自學(xué)和自學(xué)能力的提高。4．作業(yè)獨立完成作業(yè)是學(xué)好本課程的重要手段。5．考核方式本課程采用形成性考核和期末終結(jié)性考核相結(jié)合的方式考核學(xué)生成績。形成性考核由各教學(xué)點組織，具體實施按照本課程的教學(xué)設(shè)計方案和考核說明中的要求進(jìn)行。理解：離散數(shù)學(xué)課程的在計算機專業(yè)學(xué)習(xí)中的重要性。理解：集合的概念，容斥原理。第二章 關(guān)系與函數(shù)教學(xué)內(nèi)容笛卡兒積，關(guān)系的概念、表示方法及性質(zhì)復(fù)合關(guān)系與逆關(guān)系的概念與計算，關(guān)系的閉包的概念及計算等價關(guān)系的概念與判定，等價類的概念與求解序關(guān)系的概念與判定復(fù)蓋集與哈斯圖的概念與求解函數(shù)的概念及性質(zhì)逆函數(shù)與復(fù)合函數(shù)的概念與計算 教學(xué)要求了解：函數(shù)與關(guān)系的區(qū)別。掌握：笛卡兒積，關(guān)系的表示；復(fù)合關(guān)系、逆關(guān)系及關(guān)系的閉包的運算；等價關(guān)系的判定，等價類的計算，序關(guān)系的判定，復(fù)蓋集與哈斯圖等的計算；函數(shù)的判定，逆函數(shù)與復(fù)合函數(shù)的計算。理解：圖的基本概念，圖同構(gòu)、子圖、補圖概念；路與回路、圖的連通性與連通度等概念；理解矩陣變換與圖的關(guān)系。第四章 幾種特殊圖教學(xué)內(nèi)容歐拉圖與漢密爾頓圖的概念、性質(zhì)、判定平面圖的概念、性質(zhì)、判定對偶圖及著色的概念教學(xué)要求了解：幾種特殊圖在圖論發(fā)展中的作用。掌握：對歐拉圖、漢密爾頓圖的判定方法。理解：樹、生成樹、有向樹、根樹、最優(yōu)樹的概念。第三部分 數(shù)理邏輯 第六章 命題邏輯教學(xué)內(nèi)容命題的概念、命題聯(lián)結(jié)詞的概念命題公式的解釋范式（合取、析取、主合取、主析取范式）的概念與求法命題公式的等值式與蘊涵式命題邏輯的推理理論教學(xué)要求了解：命題邏輯的基本概念、基本理論與方法。掌握：命題符號化、求命題公式的真值表；合取范式、析取范式、主合取范式及主析取范式的求解；等值式與蘊涵式的基本證明方法；命題邏輯的推理理論。理解：謂詞公式的概念；謂詞邏輯的等值式與蘊涵式的概念。* 第四部分 代數(shù)結(jié)構(gòu) 第八章 代數(shù)系統(tǒng)教學(xué)內(nèi)容代數(shù)系統(tǒng)的概念代數(shù)運算的概念及性質(zhì)半群、群與子群的概念及其基本性質(zhì)同態(tài)與同構(gòu)的概念教學(xué)要求了解：代數(shù)系統(tǒng)的基本內(nèi)容及其在計算機領(lǐng)域中的應(yīng)用。掌握：代數(shù)系統(tǒng)的判定、運算性質(zhì)的判定、半群、群與子群的的判定。第二篇：離散數(shù)學(xué)離散數(shù)學(xué)試題（A卷答案）一、（10分）（1）證明(P174。R)222。R)（2）求(P∨Q)174。解：（1）因為((P174。R))174。R)219。((216。Q∨R))∨(216。(P∧216。R)∨216。(P∧216。P∨R)∧(216。P∨R))219。Q)∨(Q∨216。(P∨Q∨216。Q∨Q∨216。T 所以，(P174。R)222。R)。R219。(P∨Q)∨R219。P∧216。(216。Q)∨R)∧((P∧216。Q∨R)219。P∨Q∨R)∧(216。Q∨R)∧(P∨216。P∨216。M2∧M4∧M6 219。二、（10分）分別找出使公式x(P(x)174。解：設(shè)論域為{1，2}。$y(Q(y)∧R(x，y)))219。((Q(1)∧R(x，1))∨(Q(2)∧R(x，2))))219。((Q(1)∧R(1，1))∨(Q(2)∧R(1，2))))∧(P(2)174。(T174。((F∧F)∨(F∧F)))219。F)∧(T174。F 若P(1)＝P(2)＝T，Q(1)＝Q(2)＝T，R(1，1)＝R(1，2)＝R(2，1)＝R(2，2)＝T，則 x(P(x)174。x(P(x)174。(P(1)174。((Q(1)∧R(2，1))∨(Q(2)∧R(2，2))))219。((T∧T)∨(T∧T)))∧(T174。(T174。T)219。有的人不喜歡騎自行車，因而有的人不喜歡步行。A(x)：x喜歡步行；B(x)：x喜歡坐汽車；C(x)：x喜歡騎自行車；則推理化形式為：x(A(x)174。B(x))，x(B(x)∨C(x))，216。A(x)下面給出證明：(1)216。C(x)T(1)，E(3)216。216。216。A(c)T(6)(8)，I(10)$x216。(2)若A∩B＝A∩C，則B＝C。B＝A197。解(1)不一定。(2)不一定。(3)成立。B＝A197。x207。B222。A197。x∈A∩C222。C；當(dāng)x207。A∩B，而x∈B222。B222。C，但x207。C。B。B＝A197。五、（10分）若R是集合A上的自反和傳遞關(guān)系，則對任意的正整數(shù)n，R＝R。設(shè)n＝k時，Rk＝R。下面由R是自反和傳遞的推導(dǎo)出R*R＝R即可。R。R*R。由數(shù)學(xué)歸納法知，對任意的正整數(shù)n，Rn＝R。RR，f定義為：f()＝。(2)證明f是滿射。(4)求復(fù)合函數(shù)f－1of和fof。(2)對任意的∈RR，令x＝uw2u+w2－1，y＝uw2，則f()＝u+w2＋uw2，u+w2－＝，所以f是滿射。x+y+xy2x+y(xy)2(4)fof()＝f(f())＝f()＝＝ fof()＝f(f())＝f()＝＝。(2)寫出R的關(guān)系矩陣。解(1)R的關(guān)系圖如圖所示：(2)R的關(guān)系矩陣為：230。231。1231。1232。247。 0247。0247。(3)對于R的關(guān)系矩陣，由于對角線上不全為1，R不是自反的；由于對角線上存在非0元，R不是反自反的；由于矩陣不對稱，R不是對稱的；經(jīng)過計算可得 230。231。1231。1232。247。=M(R)，所以R是傳遞的。0247。248。對任意的a、b∈H有a*b－1∈H。充分性：由H非空，必存在a∈H。任取a∈H，由e、a∈H得a－1＝e*a－1∈H。又因為H是G非空子集，所以*在H上滿足結(jié)合律。九、（10分）給定二部圖G＝，且|V1∪V2|＝m，|E|＝n，證明n≤m/4。因為(m2m1)2179。mm1m1，所以n≤m2/4。P∨216。(P171。Q)(2)(P175。(P∧216。R))解：（1）因為(216。Q)174。216。216。P∨216。Q)∨(216。(P∧Q)∨(P∧216。P∧Q)219。M0所以，公式(216。Q)174。216。（2）因為(P175。(P∧216。R))219。(216。Q∧R))219。Q∧R))219。Q)∧(P∨Q∨R)219。(P∨Q∨(R∧216。(P∨Q∨R)∧(P∨Q∨216。M0∧M1219。Q)174。(Q∨216。二、（15