離散數(shù)學(xué)復(fù)習(xí)資料

考綱：第一章

數(shù)理邏輯§1命題及其真值

命題概念，命題聯(lián)結(jié)詞，命題真值表，命題符號(hào)化§2重言式

命題公式的性質(zhì)，邏輯等價(jià)公式，永真蘊(yùn)含公式，命題公式推倒（化簡(jiǎn)與證明）§3范式

指派，析取范式，合取范式，極小項(xiàng)，極大項(xiàng)，主范式的求法，與真值表之間的關(guān)系§4聯(lián)結(jié)詞的擴(kuò)充與歸約

功能完備集，與非，或非§5推理規(guī)則和證明方法

CP規(guī)則，直接證明法、條件證明法、反證法，命題公式證明§6謂詞和量詞

全稱量詞，存在量詞，基于謂詞的命題符號(hào)化，公式的解釋§7謂詞演算的永真公式

謂詞公式的等價(jià)公式和永真蘊(yùn)含公式，前束范式§8謂詞演算的推理規(guī)則

基于謂詞的推理，ES、EG、US、UG規(guī)則

第二章

集合§1集合論的基本概念

集合的定義，表示方法§2集合的運(yùn)算

交，并，補(bǔ)，差，環(huán)和，環(huán)積，定義和謂詞表示方法，冪集§3自然數(shù)

定義（了解）§4集合的笛卡兒乘積

笛卡爾成績(jī)的計(jì)算

第三章二元關(guān)系§1關(guān)系的基本概念

二元關(guān)系的定義、性質(zhì)判斷及證明（自反，反對(duì)稱，對(duì)稱，反對(duì)稱，傳遞）、關(guān)系圖、關(guān)系矩陣§2關(guān)系的運(yùn)算

二元關(guān)系的合成運(yùn)算、逆運(yùn)算、矩陣表示，§3關(guān)系上的閉包運(yùn)算

自反閉包，對(duì)稱閉包，傳遞閉包，求法和性質(zhì)證明§4次序關(guān)系

篇序關(guān)系的定義，哈斯圖，8種特殊元素§5等價(jià)關(guān)系和劃分

等價(jià)關(guān)系的定義，等價(jià)劃分，等價(jià)關(guān)系的證明。

第四章函數(shù)

§1函數(shù)的基本概念

定義、合成運(yùn)算§2特殊函數(shù)類

單射，滿射，雙射的判斷§3逆函數(shù)

定義

第八章

圖論§1圖的基本概念

圖、點(diǎn)、邊的相關(guān)概念§2路徑和回路

基本路徑，簡(jiǎn)單路徑，基本回路，簡(jiǎn)單回路§3圖的矩陣表示

關(guān)聯(lián)矩陣，鄰接矩陣，可達(dá)性矩陣，權(quán)矩陣，最短路徑（迪克斯特拉算法）§4歐拉圖和哈密爾頓圖

歐拉圖的定義、判斷方法；哈密爾頓圖的應(yīng)用-最小哈密爾頓回路（TSP）問題（最鄰近算法）§5*二部圖和平面圖

定義，應(yīng)用§6樹

樹的定義，性質(zhì)，生成樹，最小生成樹（克魯斯克兒算法）§7有向樹

二元樹的定義，遍歷，二元樹與普通樹的轉(zhuǎn)換，表達(dá)式的計(jì)算等

試卷類型：閉卷題型：填空題、命題符號(hào)化、作圖、證明、計(jì)算離散數(shù)學(xué)練習(xí)題一、填空題1.僅用和┐寫出下列表達(dá)式的等價(jià)形式a)(PQ)Rb)A(DE)2.僅用和┐寫出下列表達(dá)式的等價(jià)形式a)(PQ)Rb)Q(PQ)；

3.構(gòu)造公式P(PQ)Q的真值表。

4.公式A有三個(gè)命題變?cè)狿、Q、R組成，其主合取范式為A017MMM，則其主析取范式為：

5.公式A有三個(gè)命題變?cè)狿、Q、R組成，其主析取范式為A0256mmmm，則其主合取范式為：

6.設(shè)Aa,b,c,d,A上的二元關(guān)系：Ra,a,a,b,b,d,c,a,c,c，Sa,c,b,b,c,b,c,c,d,d則S1RRSr(R)s(R)t(S)7.給定如圖所示的二元樹：

按先根次序遍歷訪問結(jié)點(diǎn)的順序?yàn)椋?/p>

按中根次序遍歷訪問結(jié)點(diǎn)的順序?yàn)椋?/p>

按后根次序遍歷訪問結(jié)點(diǎn)的順序?yàn)椋?/p>

8.A{1,2},B{a,b},AB2=

9.設(shè)解釋I如下：D={1，2}P(1，1)P(1，2)P(2，1)P(2，2)0110確定下列各式的真值：xP(x,2)_____;yP(1,y)_____;xyP(x,y))_____。xyP(x,y)___;10.集合A{{,2},{2}}的冪集(A)。11.設(shè)全集U={1,2,3,4,5,6,7,8,9,10},A={1,2,4,5,6},B={2,4,6,8,10},則：(A∪B)-B=

,BA=,BA=

,BA=12.A{{1,2}},B{a,b},AB=。13.給定集合S={a,b,c,d}，S上的等價(jià)關(guān)系R能產(chǎn)生劃分{{a},,{c,d}}，則R＝14.指出下列映射是單射、滿射、雙射還是既非單射也非滿射：a)f:ZR,f(x)lnx；(Z+:表示正整數(shù)集)

。b)f:RR，f(x)x21（R表示不小于0的實(shí)數(shù)）

。c)f:RR，f(x)x2（R表示不小于0的實(shí)數(shù)）

。d)f:AB,g:BC,gf是雙射，則f是e)f:RR，15.請(qǐng)說出以下二元關(guān)系是否滿足自反性、反自反性、對(duì)稱性、反對(duì)稱性和傳遞性。

(a)：

(b)：(c)：

(d)：16.某單位裝配了30輛汽車，其中15輛有錄音機(jī)，8輛有空調(diào)，6輛有座位調(diào)節(jié)，三種設(shè)備都有的有2輛，問這三種設(shè)備都不具備的汽車至少有輛？17.設(shè)無(wú)向圖中有6條邊，有一個(gè)3度結(jié)點(diǎn)和一個(gè)5度結(jié)點(diǎn)，其余結(jié)點(diǎn)的度數(shù)為2，則該圖的結(jié)點(diǎn)數(shù)為：

。二、命題符號(hào)化：18.李明和王平是大學(xué)同學(xué)。19.不是所有的哺乳動(dòng)物都是胎生的。20.任何一個(gè)公式總存在一個(gè)與之等價(jià)的主析取范式。21.有些人對(duì)某些藥品過敏。22.參加考試的人不一定取得好成績(jī)。23.發(fā)光的不都是金子。24.有的兔子比所有的烏龜跑的快。25.所有貓都是動(dòng)物，但有些動(dòng)物不是貓。三、作圖：26.用二元有序樹表示命題公式：（見課后習(xí)題P3202）27.將下圖所示的普通的樹轉(zhuǎn)換為等價(jià)的二叉樹。28.將下圖所示的二叉樹T轉(zhuǎn)換為等價(jià)的普通樹或樹林。29.用克魯斯克爾算法求出左圖的最小生成樹。（見課后習(xí)題P30911）四、證明題：30.ABCD,DEGAG31.證明下列論證：如果甲參加球賽，則乙或丙也將參加球賽；如果乙參加球賽，則甲不參加球賽；如果丁參加球賽，則丙不參加球賽；所以，如果甲參加球賽，則丁不參加球賽。32.設(shè)R為二元關(guān)系，S{a,b|c,a,cRc,bR}，證明，若R是等價(jià)關(guān)系，則S也是等價(jià)關(guān)系。33.試證明：在任何一棵樹T(n,m)中均有m=n-1。五、計(jì)算題：34.設(shè)集合A＝{2,3,4,5,6,8,12,18,36}，R是A上的整除關(guān)系，(1)畫出偏序集(A,R)的哈斯圖；(2)寫出集合A的最大元，最小元，極大元，極小元。(3)寫出A的子集{2,3,6}的上界，下界，最小上界，最大下界；(4)寫出A的子集{2,4,6}的上界，下界，最小上界，最大下界；35.在下圖中用迪克斯特拉算法求從a到z最經(jīng)濟(jì)道路的長(zhǎng)度以及該道路所經(jīng)過的結(jié)點(diǎn)，并給出求解過程。（見課后習(xí)題P27818）__答案：一.1.a：(PQ

B:ADE2.a:PQR

B:Q3.P

Q

PQ

P(PQ)

P(PQQ

0

0

0

0

1

0

1

1

0

0

1

0

1

1

0

1

1

1

1

14.AM2M3M4M5M65.AM2M3M4M76.{<c,a>,<c,b>,<b,d>,<b,a>,<b,c>,<c,c>}

{<a,c>,<a,b>,<b,d>,<c,c>,<c,b>}

{<a,a>,<b,b>,<c,c>,<d,d>,<a,b>,<b,d>,<c,a>}

{<a,a>,<a,b>,<b,a>,<b,d>,<d,b>,<c,a>,<a,c>,<c,c>}

{<a,c>,<b,b>,<c,b>,<c,c>,<d,d>,<a,b>}7.ABDGHCEFI

BGDHAECIF

GHDBEIFCA8.{<1,a,a>,<1,a,b>,<1,b,b>,<1,b,a>,<2,a,a>,<2,a,b>,<2,b,b>,<2,b,a>}9.1

0

0

110.{{1,5}

{2,4,6}

{1,5,8,10}

{2,3,4,6,7,9}12.{<{1,2},a>,<{1,2},b>}13.{<a,a>,<b,b>,<c,c>,<d,d>,<c,d>,<d,c>}14.單射

既非單射也非滿射

滿射

單射

雙射15.a：反自反，對(duì)稱，反對(duì)稱，傳遞

b:自反，反對(duì)稱，傳遞

c:自反，反對(duì)稱傳遞

d：自反，對(duì)稱傳遞16.517.4二18.設(shè)A是“李明”B是“王平”F（x，y）：“x與y是大學(xué)同學(xué)”，F(xiàn)（A,B）19.設(shè)P(x)為“x是哺乳動(dòng)物”Q(x)為“x是胎生的”?x（P(x)Q(x)）20設(shè)p(x)為“x是一個(gè)公式”，Q(x)為“x是一個(gè)主析取范式”,M(x,y)為“x與y等價(jià)”

x(P(x)y(Q(y)M(x,y))21.設(shè)P(x)為“x是人”Q(x)為“x是藥品”S(x,y)為“x對(duì)y過敏”xy(P(x)Q(y)S(x,y))

22.設(shè)P(x)為“參加考試的人”Q(x)為“x取得好成績(jī)”

x（P(x)?Q(x)）23設(shè)p(x)為“x發(fā)光”Q(x)為“x是金子”?x(P(x)Q(x))24設(shè)P(x)為“x是兔子”Q(x)為“x是烏龜”H(x,y)為“x比y跑的快”x(P(x)y(Q(y)H(x,y)))25設(shè)P(X)為“x是貓”，Q(x)為“x是動(dòng)物”x（P(x)Q(x)）想（Q(x)?P(x)）三：略四30設(shè)A成立則推出AB與ABCD則推出CD即D即DE又DEG故G則AG31設(shè)甲乙丙丁參加球賽為ABCDABCB?A

A?D

D?C又?ABC與?B?A推出C且?D?C故D聯(lián)立A?D得A?D32.①自反性x

R自反<x,x>R<x,x>Q<x,x>S②對(duì)稱性x,y若<x,y>Sc使<x,c>R<c,y>R

R對(duì)稱<y,c>R<C,x>R<t,x>S③傳遞性x,y,z若<x,y>S,<y,z>S

C1使<x,C1>R<C1y>R,C2使<y,C2>R<C2y>R

R是傳遞<x,y>R<Y,z>R<x,z>S34.①如圖

②A的最大元36最小元無(wú)極大元36極小元2，3，5③{2，3，6}上界6，12，18，36下界無(wú)最小上界6最大下界無(wú)④{2，4，6}上界12，16下界2最小上界12最大下界235node

P/T

prol(t)a

1b

2

a

①c

6

h

10

10

10

10

⑨d

4

e

6