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

西北師范大學(xué)信息與計算科學(xué)專業(yè)專業(yè)必修課程學(xué)大綱離散數(shù)學(xué)一說（）課性離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個重要分支。離散數(shù)學(xué)研究離散量的結(jié)構(gòu)和相互之間的關(guān)系，凡以離散量作為其研究對象的數(shù)學(xué)均屬于離散數(shù)學(xué)于計算機(jī)有離散性的特點以散數(shù)學(xué)為計算機(jī)科學(xué)提供了有力的理論基礎(chǔ)和工具學(xué)還能培養(yǎng)學(xué)習(xí)者的抽象思維和邏輯推理能力離散數(shù)學(xué)是隨著計機(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ù)學(xué)工具。（）教內(nèi)主要介紹本專業(yè)最需要的離散數(shù)學(xué)基礎(chǔ)知識，包括數(shù)理邏輯、集合論、代數(shù)系統(tǒng)和圖論篇內(nèi)容，共章：命題邏輯、謂詞邏輯、集與關(guān)系、函數(shù)、代數(shù)系統(tǒng)和圖論。（）教時每周時，共計54學(xué)時。（）教方主要采用講授法，若有條件，可適當(dāng)使用多媒體課件上課。二本文第一篇

數(shù)理邏

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

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

謂詞邏教要：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

集合的基數(shù)（2學(xué)）介紹基數(shù)的概念，可數(shù)集的性質(zhì)及基數(shù)的比較。考要：掌握函數(shù)的定義，區(qū)別單射、滿射及雙射，掌握復(fù)合函數(shù)及逆函數(shù)的定義和運算性質(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)和域。教時：學(xué)時教內(nèi)：第一節(jié)

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

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

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

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

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

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

圖論教要：圖的基本概念，路、回路與圖的連通性，圖的矩陣表示，歐拉圖和哈密頓圖，二分圖、平面圖及圖的著色，樹。教時：學(xué)時教內(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ì)及判斷，介紹圖的著色。第