西北師范大學(xué)信息與計(jì)算科學(xué)專業(yè)

西北師范大學(xué)信息與計(jì)算科學(xué)專業(yè)專業(yè)必修課程學(xué)大綱離散數(shù)學(xué)一說（）課性離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支。離散數(shù)學(xué)研究離散量的結(jié)構(gòu)和相互之間的關(guān)系，凡以離散量作為其研究對(duì)象的數(shù)學(xué)均屬于離散數(shù)學(xué)于計(jì)算機(jī)有離散性的特點(diǎn)以散數(shù)學(xué)為計(jì)算機(jī)科學(xué)提供了有力的理論基礎(chǔ)和工具學(xué)還能培養(yǎng)學(xué)習(xí)者的抽象思維和邏輯推理能力離散數(shù)學(xué)是隨著計(jì)機(jī)的發(fā)展而建立的形成于七十年代初期是門新興的工具性學(xué)科。（）教目通過離散數(shù)學(xué)的學(xué)習(xí)，為更好地學(xué)習(xí)本專業(yè)的其它后續(xù)課程，如數(shù)據(jù)結(jié)構(gòu)、算法分析、系統(tǒng)結(jié)構(gòu)等打下基礎(chǔ)，并為學(xué)生今后處理離散信息專業(yè)水平，從事實(shí)際工作提供必備的數(shù)學(xué)工具。（）教內(nèi)主要介紹本專業(yè)最需要的離散數(shù)學(xué)基礎(chǔ)知識(shí)，包括數(shù)理邏輯、集合論、代數(shù)系統(tǒng)和圖論篇內(nèi)容，共章：命題邏輯、謂詞邏輯、集與關(guān)系、函數(shù)、代數(shù)系統(tǒng)和圖論。（）教時(shí)每周時(shí)，共計(jì)54學(xué)時(shí)。（）教方主要采用講授法，若有條件，可適當(dāng)使用多媒體課件上課。二本文第一篇

數(shù)理邏

邏輯是研究推理的科學(xué)數(shù)理邏輯是用數(shù)學(xué)方法研究形式邏輯的一門科學(xué)謂數(shù)學(xué)方法，主要是指引進(jìn)一套符號(hào)體系的方法，因此數(shù)理邏輯又叫符號(hào)邏輯?，F(xiàn)代數(shù)理邏輯有4大分支：證明論、模型論論和公理化集合論本篇介紹它們的共同基礎(chǔ)——命題邏輯和謂詞邏輯。第一章

命題邏教要：命題聯(lián)結(jié)詞命公式真表重言式蘊(yùn)式對(duì)與范式的定義命題符號(hào)化；常用的等價(jià)式與蘊(yùn)涵式命公的等值演算；給定公式的主析取范式、主和取范式演算的推理。教時(shí)：課時(shí)教內(nèi)：第一節(jié)命題及其表示法（時(shí)）理解命題的定義，掌握常見的個(gè)題聯(lián)結(jié)詞，并將不太復(fù)雜的命題符號(hào)化。第二節(jié)命題公式、真值表及等價(jià)公式（2學(xué)時(shí)）了解命題公式真表的定義理命題公式的等價(jià)，熟練掌握真值表的作法，熟練掌握常用的等價(jià)公式，掌握命題公式的等價(jià)演算。第三節(jié)重言式和蘊(yùn)含式學(xué)時(shí)）掌握重言式、蘊(yùn)涵式的定義，掌握蘊(yùn)涵式的證明方法，熟練掌握常用的蘊(yùn)涵式。第四節(jié)對(duì)偶與范式（時(shí)）了解對(duì)偶式的概念，理解范式的概念，熟練掌握主析取范式和主和取范式的作法。第五節(jié)推理理論（學(xué)時(shí)）掌握推理規(guī)則練應(yīng)用P規(guī)規(guī)進(jìn)行命題推理握規(guī)則和歸謬法的使用?？家簩⒉惶珡?fù)雜的命題符號(hào)化出給命題公式的真值表明題公式的等價(jià)明涵式，求命題公式的主析取范式和主和取范式，將不太復(fù)雜的命題推理使用推理規(guī)則證明。第二章

謂詞邏教要：

客體詞和謂詞的概念，量詞的定義詞公式的等價(jià)式和蘊(yùn)涵式前范式的概念，謂詞演算的推理理論。教時(shí)：時(shí)教內(nèi)：第一節(jié)

謂詞、客體詞和量詞（學(xué)）理解客體詞和謂詞的概念，掌握量詞的定義，能將不太復(fù)雜的命題符號(hào)化。第二節(jié)

謂詞公式的等價(jià)式和蘊(yùn)涵式（學(xué)）了解謂詞公式的定義，了解轄域理解常用的等價(jià)式和蘊(yùn)涵式。第三節(jié)

前束范式（1學(xué)）了解謂詞公式的范式。第四節(jié)

謂詞演算的推理理論2學(xué)）掌握謂詞演算的推理規(guī)則USUGESEG并熟練應(yīng)用規(guī)則對(duì)不太復(fù)雜的推理進(jìn)行謂詞演算的證明?？家耗軐⒉惶珡?fù)雜的命題符號(hào)化量詞的概念不太復(fù)雜的謂詞推理使用推理規(guī)則證明。第二篇集論集合論是現(xiàn)代各科數(shù)學(xué)的基礎(chǔ)。它的創(chuàng)始人是康脫，1845-1918他創(chuàng)立的樸素集合論，由于在定義集合的方法上缺乏限制，導(dǎo)致了許多悖論20世初由策墨羅（Z等人創(chuàng)立了公理化集合論，使該學(xué)科成為數(shù)學(xué)中發(fā)展最為迅速的一個(gè)分支。集合論能直接應(yīng)用后續(xù)專業(yè)課程的學(xué)習(xí)與研究中。本篇介紹集合論的基本內(nèi)容。第三章集與關(guān)系教要：集合的概念、集合的運(yùn)算、冪集的概念、笛卡兒積；關(guān)系的概念、關(guān)系的運(yùn)算、關(guān)系的性質(zhì)以及特殊的一些二元關(guān)系。教時(shí)：

學(xué)時(shí)教內(nèi)：第一節(jié)

集合的概念及其運(yùn)算2學(xué)）主要介紹集合的概念、集合的表示、集合間的關(guān)系、集合的并、交、差、對(duì)稱差運(yùn)算，冪集的概念以及集合的笛卡兒積。第二節(jié)

二元關(guān)系（1學(xué)）主要講授序偶的定義，關(guān)系的定義，關(guān)系的表示，特別是關(guān)系圖和關(guān)系矩陣第三節(jié)

關(guān)系的性質(zhì)（2學(xué)）主要講授關(guān)系的自反性、對(duì)稱性、傳遞性、反自反性及反對(duì)稱性等性質(zhì)的定義和判斷方法。第四節(jié)

關(guān)系的運(yùn)算（3學(xué)）介紹關(guān)系的并、交、補(bǔ)、差運(yùn)算，講關(guān)系授復(fù)合關(guān)系和逆關(guān)系的定義、計(jì)算及運(yùn)算性質(zhì)，講授關(guān)系的自反閉包、傳遞閉包、對(duì)稱閉包的定義、計(jì)算及運(yùn)性質(zhì)。第五節(jié)

等價(jià)關(guān)系及劃分學(xué)時(shí)）講授等價(jià)關(guān)系、等價(jià)類、商集的定義、性質(zhì)，劃分的定義，等價(jià)關(guān)系與劃分的關(guān)系定理。第六節(jié)

序關(guān)系（2學(xué)）主要講授偏序關(guān)系的定義、性質(zhì)，用Hasse圖示偏序關(guān)系，偏序集上的特殊素，介紹擬序關(guān)系、全序關(guān)系、良序關(guān)系?？家侯I(lǐng)會(huì)集合、關(guān)系的概念，掌握集合的運(yùn)算及性質(zhì)，熟練掌握關(guān)系的表示、性質(zhì)、運(yùn)算以及等價(jià)關(guān)系和偏序關(guān)系的性質(zhì)。第四章

函數(shù)教要：函數(shù)的概念，復(fù)合函數(shù)、逆函數(shù)，集合的基數(shù)。教時(shí)：時(shí)

教內(nèi)：第一節(jié)

函數(shù)（2學(xué)）講授函數(shù)的概念，單射、滿射及雙射的概念，復(fù)合函數(shù)及逆函數(shù)的定義和運(yùn)算性質(zhì)。第二節(jié)

集合的基數(shù)（2學(xué)）介紹基數(shù)的概念，可數(shù)集的性質(zhì)及基數(shù)的比較?？家赫莆蘸瘮?shù)的定義，區(qū)別單射、滿射及雙射，掌握復(fù)合函數(shù)及逆函數(shù)的定義和運(yùn)算性質(zhì)基數(shù)的概念，可數(shù)集的性質(zhì)及基數(shù)的比較。第三篇

代數(shù)系代數(shù)也代數(shù)結(jié)構(gòu)或代數(shù)系統(tǒng)同的代數(shù)系統(tǒng)可以具有一些相同的性質(zhì)以將某一代數(shù)系統(tǒng)的理論與方法推廣到與其同構(gòu)的其它代數(shù)系統(tǒng)中僅介紹一些基本概念和群的簡單性質(zhì)。第五章

代數(shù)結(jié)教要：代數(shù)系統(tǒng)的基本概念，半群，群與子群，同態(tài)與同構(gòu)，環(huán)和域。教時(shí)：學(xué)時(shí)教內(nèi)：第一節(jié)

代數(shù)系統(tǒng)的基本概念2學(xué)）主要講授代數(shù)系統(tǒng)的基本結(jié)構(gòu)，幺元、零元和逆元的定義及性質(zhì)，運(yùn)算及其性質(zhì)。第二節(jié)

半群、群與子群學(xué)時(shí)）主要講授半群的定義及性質(zhì)，獨(dú)異點(diǎn)的定義，群與子群的定義與性質(zhì)。第三節(jié)

阿貝爾群和循環(huán)群（學(xué)）主要介紹阿貝爾群和循環(huán)群的定義與性質(zhì)。第四節(jié)

同構(gòu)與同態(tài)（2學(xué)）

主要講授兩個(gè)代數(shù)系統(tǒng)之間的同構(gòu)與同態(tài)關(guān)系，介紹代數(shù)系統(tǒng)上的同余關(guān)系。第五節(jié)

環(huán)和域（2學(xué)）主要介紹環(huán)和域的定義與性質(zhì)?？家簳?huì)求給定代數(shù)系統(tǒng)中運(yùn)算的幺元、零元和逆元，掌握半群，群與子群的判斷方法和域，應(yīng)用基本概念分析給定代數(shù)系統(tǒng)的簡單性質(zhì)。第四篇圖論圖論是數(shù)學(xué)的一個(gè)分支來到迅速發(fā)展泛應(yīng)用到信息科學(xué)的各個(gè)領(lǐng)域，成為重要工具。本篇對(duì)它的基本概念、基本性質(zhì)作概要的介紹。第六章

圖論教要：圖的基本概念，路、回路與圖的連通性，圖的矩陣表示，歐拉圖和哈密頓圖，二分圖、平面圖及圖的著色，樹。教時(shí)：學(xué)時(shí)教內(nèi)：第一節(jié)

圖的基本概念（2學(xué)）主要講授圖的定義及基本性質(zhì)定理，圖的同構(gòu)的概念，圖的補(bǔ)圖、子圖。第二節(jié)

路與回路（2學(xué)）主要講授路與回路的概念，圖的連通性的定義，介紹賦權(quán)圖及最短路的算法。第三節(jié)

圖的矩陣表示（2學(xué)）主要講授圖的鄰接矩陣、關(guān)聯(lián)矩陣、可達(dá)性矩陣的定義、意義。第四節(jié)歐拉圖和哈密頓圖（學(xué)）主要講授歐拉圖和哈密頓圖的定義、判斷方法，介紹旅行售貨員問題。

第五節(jié)平面圖與著色（學(xué)）介紹二分圖的概念，講授平面圖的定義、性質(zhì)及判斷，介紹圖的著色。第