第一篇：離散數(shù)學(xué)證明題

離散數(shù)學(xué)證明題

離散數(shù)學(xué)證明題:鏈為分配格

證明設(shè)a,b均是鏈A的元素，因?yàn)殒溨腥我鈨蓚€(gè)元素均可比較，即有a≤b或a≤b，如果a≤b，則a,b的最大下界是a,最小上界是b，如果b≤a，則a,b的最大下界是b,最小上界是a，故鏈一定是格,下面證明分配律成立即可,對A中任意元素a,b,c分下面兩種情況討論:

⑴b≤a或c≤a

⑵a≤b且a≤c

如果是第⑴種情況,則a∪(b∩c)=a=(a∪b)∩(a∪c)

如果是第⑵種情況,則a∪(b∩c)=b∩c=(a∪b)∩(a∪c)

無論那種情況分配律均成立,故A是分配格.一.線性插值(一次插值)

已知函數(shù)f(x)在區(qū)間的端點(diǎn)上的函數(shù)值yk=f(xk),yk+1=f(xk+1),求一個(gè)一次函數(shù)y=p1(x)使得yk=f(xk),yk+1=f(xk+1),其幾何意義是已知平面上兩點(diǎn)(xk,yk),(xk+1,yk+1),求一條直線過該已知兩點(diǎn)。

1.插值函數(shù)和插值基函數(shù)

由直線的點(diǎn)斜式公式可知：

把此式按照yk和yk+1寫成兩項(xiàng):

記

并稱它們?yōu)橐淮尾逯祷瘮?shù)。該基函數(shù)的特點(diǎn)如下表：

從而

p1(x)=yklk(x)+yk+1lk+1(x)

此形式稱之為拉格朗日型插值多項(xiàng)式。其中,插值基函數(shù)與yk、yk+1無關(guān)，而由插值結(jié)點(diǎn)xk、xk+1所決定。一次插值多項(xiàng)式是插值基函數(shù)的線性組合,相應(yīng)的組合系數(shù)是該點(diǎn)的函數(shù)值yk、yk+1.例1:已知lg10=1,lg20=1.3010,利用插值一次多項(xiàng)式求lg12的近似值。

解:f(x)=lgx,f(10)=1,f(20)=1.3010,設(shè)

x0=10,x1=20,y0=1,y1=1.3010

則插值基函數(shù)為：

于是,拉格朗日型一次插值多項(xiàng)式為:

故:

即lg12由lg10和lg20兩個(gè)值的線性插值得到,且具有兩位有效數(shù)字(精確值lg12=1.0792).二.二次插值多項(xiàng)式

已知函數(shù)y=f(x)在點(diǎn)xk-1,xk,xk+1上的函數(shù)值yk-1=f(xk-1),yk=f(xk),yk+1=f(xk+1),求一個(gè)次數(shù)不超過二次的多項(xiàng)式p2(x),使其滿足,p2(xk-1)=yk-1,p2(xk)=yk,p2(xk+1)=yk+1.其幾何意義為:已知平面上的三個(gè)點(diǎn)

(xk-1,yk-1),(xk,yk),(xk+1,yk+1),求一個(gè)二次拋物線,使得該拋物線經(jīng)過這三點(diǎn)。

1.插值基本多項(xiàng)式

有三個(gè)插值結(jié)點(diǎn)xk-1,xk,xk+1構(gòu)造三個(gè)插值基本多項(xiàng)式，要求滿足：

(1)基本多項(xiàng)式為二次多項(xiàng)式;(2)它們的函數(shù)值滿足下表：

因?yàn)閘k-1(xk)=0,lk-1(xk+1)=0,故有因子(x-xk)(x-xk+1),而其已經(jīng)是一個(gè)二次多項(xiàng)式,僅相差一個(gè)常數(shù)倍,可設(shè)

lk-1(x)=a(x-xk)(x-xk+1),又因?yàn)?/p>

lk-1(xk-1)=1==>a(xk-1-xk)(xk-1-xk+1)=

1得

從而

同理得

基本二次多項(xiàng)式見右上圖(點(diǎn)擊按鈕“顯示Li”)。

2.拉格朗日型二次插值多項(xiàng)式

由前述,拉格朗日型二次插值多項(xiàng)式:

p2(x)=yk-1lk-1(x)+yklk(x)+yk+1lk+1(x),p2(x)

是三個(gè)二次插值多項(xiàng)式的線性組合,因而其是次數(shù)不超過二次的多項(xiàng)式,且滿足:

p2(xi)=yi,(i=k-1,k,k+1)。

例2已知：

xi101520

yi=lgxi11.17611.3010

利用此三值的二次插值多項(xiàng)式求lg12的近似值。

解：設(shè)x0=10,x1=15,x2=20,則:

故:

所以

7利用三個(gè)點(diǎn)進(jìn)行拋物插值得到lg12的值,與精確值lg12=1.0792相比,具有3位有效數(shù)字,精度提高了。

三、拉格朗日型n次插值多項(xiàng)式

已知函數(shù)y=f(x)在n+1個(gè)不同的點(diǎn)x0,x1,…,x2上的函數(shù)值分別為

y0,y1,…,yn,求一個(gè)次數(shù)不超過n的多項(xiàng)式pn(x),使其滿足:

pn(xi)=yi,(i=0,1,…,n),即n+1個(gè)不同的點(diǎn)可以唯一決定一個(gè)n次多項(xiàng)式。

1.插值基函數(shù)

過n+1個(gè)不同的點(diǎn)分別決定n+1個(gè)n次插值基函數(shù)

l0(x),l1(x),…,ln(X)

每個(gè)插值基本多項(xiàng)式li(x)滿足：

(1)li(x)是n次多項(xiàng)式;

(2)li(xi)=1,而在其它n個(gè)li(xk)=0,(k≠i)。

由于li(xk)=0,(k≠i),故有因子:

(x-x0)…(x-xi-1)(x-xi+1)…(x-xn)

因其已經(jīng)是n次多項(xiàng)式，故而僅相差一個(gè)常數(shù)因子。令:

li(x)=a(x-x0)…(x-xi-1)(x-xi+1)…(x-xn)

由li(xi)=1,可以定出a,進(jìn)而得到：

2.n次拉格朗日型插值多項(xiàng)式pn(x)

pn(x)是n+1個(gè)n次插值基本多項(xiàng)式l0(x),l1(x),…,ln(X)的線性組合,相應(yīng)的組合系數(shù)是y0,y1,…,yn。即:

pn(x)=y0l0(x)+y1l1(x)+…+ynln(x),從而pn(x)是一個(gè)次數(shù)不超過n的多項(xiàng)式,且滿足

pn(xi)=yi,(i=0,1,2,…,n).例3求過點(diǎn)(2,0),(4,3),(6,5),(8,4),(10,1)的拉格朗日型插值多項(xiàng)式。

解用4次插值多項(xiàng)式對5個(gè)點(diǎn)插值。

所以

四、拉格朗日插值多項(xiàng)式的截?cái)嗾`差

我們在上用多項(xiàng)式pn(x)來近似代替函數(shù)f(x),其截?cái)嗾`差記作

Rn(x)=f(x)-pn(x)

當(dāng)x在插值結(jié)點(diǎn)xi上時(shí)Rn(xi)=f(xi)-pn(xi)=0,下面來估計(jì)截?cái)嗾`差：

定理1：設(shè)函數(shù)y=f(x)的n階導(dǎo)數(shù)y(n)=f(n)(x)在上連續(xù)，y(n+1)=f(n+1)(x)

在(a,b)上存在;插值結(jié)點(diǎn)為:

a≤x0

pn(x)是n次拉格朗日插值多項(xiàng)式;則對任意x∈有：

其中ξ∈(a,b),ξ依賴于x：ωn+1(x)=(x-x0)(x-x1)…(x-xn)

證明：由插值多項(xiàng)式的要求：

Rn(xi)=f(xi)-pn(xi)=0，(i=0,1,2,…,n);

設(shè)

Rn(x)=K(x)(x-x0)(x-x1)…(x-xn)=K(x)ωn+1(x)

其中K(x)是待定系數(shù);固定x∈且x≠xk，k=0,1,2,…,n;作函數(shù)

H(t)=f(t)-pn(t)-K(x)(t-x0)(t-x1)…(t-xn)

則H(xk)=0，(k=0,1,2,…,n),且H(x)=f(x)-pn(x)-Rn(x)=0,所以，H(t)在上有n+2個(gè)零點(diǎn)，反復(fù)使用羅爾中值定理:存在ξ∈(a,b),使;因pn(x)是n次多項(xiàng)式，故p(n+1)(ξ)=0,而

ωn+1(t)=(t-x0)(t-x1)…(t-xn)

是首項(xiàng)系數(shù)為1的n+1次多項(xiàng)式，故有

于是

H(n+1)(ξ)=f(n+1)(ξ)-(n+1)!K(x)

得：

所以

設(shè),則：

易知，線性插值的截?cái)嗾`差為:

二次插值的截?cái)嗾`差為:

下面來分析前面兩個(gè)例子(例1，例2)中計(jì)算lg12的截?cái)嗾`差：

在例1中，用lg10和lg20計(jì)算lg12,p1(12)=1.0602,lg12=1.0792

e=|1.0792-1.0602|=0.0190;

估計(jì)誤差：f(x)=lgx，當(dāng)x∈時(shí),2

第二篇：離散數(shù)學(xué)證明題

證明題

1.用等值演算法證明下列等值式：

（1）┐(P?Q)?(P∨Q)∧┐(P∧Q)

（2）(P∧┐Q)∨(┐P∧Q)?(P∨Q)∧┐(P∧Q)

證明：（1）

┐(P?Q)

?┐((P→Q)∧(Q→P))

?┐((┐P∨Q)∧(┐Q∨P))

?(P∧┐Q)∨(Q∧┐P)

?(P∨Q)∧(P∨┐P)∧(┐Q∨Q)∧(┐P∨┐Q)

?(P∨Q)∧┐(P∧Q)

（2）

(P∧┐Q)∨(┐P∧Q)

?(P∨┐P)∧(P∨Q)∧(┐Q∨┐P)∧(┐Q∨Q)

?(P∨Q)∧┐(P∧Q)

2．構(gòu)造下列推理的證明：

（1）前提：?(P?Q)??(R?S)，(Q?P)??R，R

前提：P?Q。

（2）前提：Q →P, Q ? S , S ? M , M∧R前提：結(jié)論：P∧Q

（3）前提：P →(Q → R), S → P , Q

結(jié)論：S →R（4）前提：(P∨Q)→(R∧S),(S∨M)→ U結(jié)論：P →U（5）前提：P →┐Q,┐R∨Q ,R∧┐S

結(jié)論：┐P（6）前提：P∨Q，P →R, Q → S結(jié)論：R∨S

證明：（1）

① R前提引入

②(Q?P)??R前提引入

③ Q?P①②析取三段論

④ R?S①附加規(guī)則

⑤ ?(P?Q)??(R?S)前提引入

⑥ P?Q④⑤拒取式

⑦(P?Q)?(Q?P)③⑥合取規(guī)則

⑧ P?Q⑦置換規(guī)則

（2）

① M∧R前提引入

② M①化簡規(guī)則

③ S ? M前提引入

④(S → M)∧(M → S)③置換

⑤ M → S④化簡規(guī)則

⑥ S② ⑥假言推理

⑦ Q ? S前提引入

⑧(S → Q)∧(Q → S)⑦ 置換

⑨ S → Q⑧化簡規(guī)則

⑩ Q⑥ ⑨假言推理

(11)Q →P前提引入

(12)P

(13)P∧Q

（3）

① S → P

②S

③ P

④ P →(Q → R)

⑤ Q → R

⑥ Q

⑦ R

（4）

① P

② P∨Q

③(P∨Q)→(R∧S)

④ R∧S

⑤ S

⑥ S∨M

⑦(S∨M)→ U

⑧ U

（5）

① P

② P →┐Q

③ ┐Q

④ ┐R∨Q

⑤ ┐R

⑥ R∧┐S

⑦ R

⑧ R∧┐R

（6）⑩(11)假言推理⑩(12)合取前提引入附加前提引入① ②假言推理 前提引入③④ 假言推理前提引入⑤⑥假言推理附加前提引入①附加規(guī)則前提引入②③ 假言推理④化簡規(guī)則⑤附加規(guī)則前提引入⑥ ⑦假言推理結(jié)論否定引入前提引入① ②假言推理前提引入③④析取三段論前提引入⑥化簡規(guī)則⑤⑦合取

① ┐(R∨S)結(jié)論否定引入

② ┐R∧┐S①置換規(guī)則

③ ┐R②化簡規(guī)則

④ P →R前提引入

⑤ ┐P③④拒取

⑥ ┐S②化簡規(guī)則

⑦ Q → S前提引入

⑧ ┐Q⑥ ⑦拒取

⑨ ┐P∧┐Q⑤⑧合取

⑩ ┐(P∨Q)⑨置換規(guī)則

(11)P∨Q前提引入

(12)┐(P∨Q)∧(P∨Q)⑨11 合取

3．在命題邏輯中構(gòu)造下列推理的證明：

（1）如果今天是星期六，我們就要到頤和園或圓明園去玩。如果頤和園游人太多，我們就不到頤和園去玩。今天是星期六。頤和園游人太多。所以我們到圓明園玩。

（2）明天是晴天，或是雨天；若明天是晴天，我就去看電影；若我看電影，我就不看書。所以，如果我看書，則明天是雨天。

（3）如果小王是理科學(xué)生，他必學(xué)好數(shù)學(xué)；如果小王不是文科生，他必是理科生；小王沒學(xué)好數(shù)學(xué)。所以，小王是文科生。

解：（1）首先將命題符號化：

設(shè)P: 今天是星期六；Q: 我們到頤和園去玩；R:我們到圓明園去玩；S:頤和園游人多。

前提：P →(Q∨R), S → ┐Q , P , S

結(jié)論：R證明：

① ②假言推理

④ P前提引入

⑤ P →(Q ∨ R)前提引入⑥ Q ∨ R④⑤假言推理 ⑦ R③⑥析取三段論

（2）首先將命題符號化：令P：明天是晴天，Q：明天是雨天，R：我看電影，S：我看書。① S → ┐Q前提引入②S前提引入③ ┐Q

前提：P∨Q, P→R, R→┐S

結(jié)論： S→Q

證明：

① S

② R→┐S

③┐R

④ P→R

⑤ ┐P

⑥ P∨Q 附加前提引入 前提引入 ①②拒取式 前提引入 ③④拒取式 前提引入

⑦ Q⑤⑥析取三段論

（3）首先將命題符號化：

令P：小王是理科生，Q：小王是文科生，R：小王學(xué)好數(shù)學(xué)。

前提:P→R, ┐Q→P, ┐R

結(jié)論：Q

證明：

① P→R

② ┐R

③ ┐P

④ ┐Q→P

⑤ Q

6.證明: 前提引入 前提引入 ①②拒取式 前提引入 ③④拒取式

①A-B=A ?A∩B=Φ。

②(A-B)-C =(A-C)-(B-C)

證明：①

必要性。假設(shè)A∩B≠Φ，必有x屬于A∩B，則x屬于A同時(shí)屬于B，即x屬于A但是x不屬于A-B。與A-B=A矛盾。

充分性。顯然A-B?A。任取x∈A，則如果x屬于B，則x屬于A∩B，與A∩B=Φ矛盾。因此x必不屬于B，即x屬于A-B。從而證明了A?A-B。命題得證。②

∵(A-B)-C =(A∩～B)∩～C

= A∩～B∩～C;

(A-C)-(B-C)

=(A∩～C)∩～(B∩～C)

=(A∩～C)∩(～B∪C)

=(A∩～C∩～B)∪(A∩～C∩C)

=(A∩～C∩～B)∪Φ

= A∩～B∩～C.∴(A-B)-C =(A-C)-(B-C)

7．設(shè)R是A上的二元關(guān)系，試證：R是傳遞的當(dāng)且僅當(dāng)R2?R，其中R2表示R?R。

（1）設(shè)R傳遞，?（x，y）∈R2，?t∈A使

，∈R（因?yàn)镽2＝R ?R）

∵R傳遞 ∴∈R

∴R2 ?R

（2）設(shè)R2?R，若，∈R

則∈R2，∵R2 ?R，∴∈R。即R傳遞。

8．設(shè)A是集合，R1,R2是A上的二元關(guān)系，證明：

若R1,R2是自反的和對稱的，則R1?R2也是自反的和對稱的。

證明:

(1)∵ R1,R2是A上的自反關(guān)系

∴ IA?R1?IA?R2

∴IA?R1?R2

∴ R1?R2是A上的自反關(guān)系

又∵ R1,R2是A上的對稱關(guān)系

∴ R1?R1?1?R2?R2?1

(R1?R2)?1?1?1?R1?R2?R1?R2∴ R1?R2 是A上的對稱關(guān)系

第三篇：離散數(shù)學(xué)歷年考試證明題

1、試證明集合等式A?(B?C)=(A?B)?(A?C)．

證明：

設(shè)S=A∩(B∪C)，T=(A∩B)∪(A∩C)，若x∈S，則x∈A且x∈B∪C，即 x∈A且x∈B 或 x∈A且x∈C，也即x∈A∩B 或 x∈A∩C，即 x∈T，所以S?T．

反之，若x∈T，則x∈A∩B 或 x∈A∩C，即x∈A且x∈B 或 x∈A且x∈C，也即x∈A且x∈B∪C，即x∈S，所以T?S． 因此T=S．

2、試證明集合等式A?(B?C)=(A?B)?(A?C)．

證明：設(shè)S= A?(B?C)，T=(A?B)?(A?C)，若x∈S，則x∈A或x∈B?C，即 x∈A或x∈B 且 x∈A或x∈C．

也即x∈A?B 且 x∈A?C，即 x∈T，所以S?T．

反之，若x∈T，則x∈A?B 且 x∈A?C，即x∈A或x∈B 且 x∈A或x∈C，也即x∈A或x∈B?C，即x∈S，所以T?S．

因此T=S．

3、試證明（?x）（P（x）∧R（x））?（?x）P（x）∧（?x）R（x）．

證明：

（1）（?x）（P（x）∧R（x））P（2）P（a）∧R（a）ES(1)

（3）P（a）T(2)I（4）（?x）P（x）EG(3)

（5）R（a）T(2)I（6）（?x）R（x）EG(5)

（7）（?x）P（x）∧（?x）R（x）T(5)(6)I4、設(shè)A，B是任意集合，試證明：若A?A=B?B，則A=B．

證明：設(shè)x?A，則?A?A，因?yàn)锳?A=B?B，故?B?B，則有x?B，所以A?B． 設(shè)x?B，則?B?B，因?yàn)锳?A=B?B，故?A?A，則有x?A，所以B?A． 故得A=B．

5、設(shè)G是一個(gè)n階無向簡單圖，n是大于等于2的奇數(shù)．證明G與G中的奇數(shù)度頂點(diǎn)個(gè)數(shù)相等(G是G的補(bǔ)圖)．

證明：因?yàn)閚是奇數(shù)，所以n階完全圖每個(gè)頂點(diǎn)度數(shù)為偶數(shù)，因此，若G中頂點(diǎn)v的度數(shù)為奇數(shù)，則在G中v的度數(shù)一定也是奇數(shù)，所以G與G中的奇數(shù)度頂點(diǎn)個(gè)數(shù)相等．

6．設(shè)連通圖G有k個(gè)奇數(shù)度的結(jié)點(diǎn)，證明在圖G中至少要添加

歐拉圖．

證明：由定理3.1.2，任何圖中度數(shù)為奇數(shù)的結(jié)點(diǎn)必是偶數(shù)，可知k是偶數(shù)．

又根據(jù)定理4.1.1的推論，圖G是歐拉圖的充分必要條件是圖G不含奇數(shù)度結(jié)點(diǎn)．因此只要在每對奇數(shù)度結(jié)點(diǎn)之間各加一條邊，使圖G的所有結(jié)點(diǎn)的度數(shù)變?yōu)榕紨?shù)，成為歐拉圖． 故最少要加k條邊才能使其成為2k條邊到圖G才能使其成為歐拉圖． 2

7．設(shè)R是集合A上的對稱關(guān)系和傳遞關(guān)系，試證明：若對任意a?A，存在b?A，使得?R，則R是等價(jià)關(guān)系．

證明：已知R是對稱關(guān)系和傳遞關(guān)系，只需證明R是自反關(guān)系．

?a?A，?b?A，使得?R，因?yàn)镽是對稱的，故?R；

又R是傳遞的，即當(dāng)?R，?R ??R；

由元素a的任意性，知R是自反的．

所以，R是等價(jià)關(guān)系．

8．若非空集合A上的二元關(guān)系R和S是偏序關(guān)系，試證明：R?S也是A上的偏序關(guān)系．

證明：.① ?x?A,?x,x??R,?x,x??S??x,x??R?S，所以R?S有自反性；②?x,y?A,因?yàn)镽，S是反對稱的，?x,y?R?S??y,x?R?S?(?x,y??R??x,y??S)?(?y,x??R??y,x??S)?(?x,y??R??y,x??R)?(?x,y??S??y,x??S)?x?y?y?x?x?y 所以，R?S有反對稱性．

③?x,y,z?A，因?yàn)镽，S是傳遞的，?x,y??R?S??y,z??R?S

??x,y??R??x,y??S??y,z??R??y,z??S

??x,y??R??y,z??R??x,y??S??y,z??S

??x,z??R??x,z??S??x,z??R?S

所以，R?S有傳遞性．

總之，R是偏序關(guān)系．

9．試證明命題公式(P?(Q??R))??P?Q與?（P??Q）等價(jià)．

證明：(P?(Q??R))??P?Q

?(?P?(Q??R))??P?Q?(?P?Q??R)??P?Q

?(?P??P?Q)?(Q??P?Q)?(?R??P?Q)

?(?P?Q)?(?P?Q)?(?P?Q??R)??P?Q（吸收律）

??(P??Q)（摩根律）

10．試證明（?x）（P（x）∧R（x））?（?x）P（x）∧（?x）R（x）．

證明：（1）（?x）（P（x）∧R（x））P

（2）P（a）∧R（a）ES(1)（3）P（a）T(2)I

（4）（?x）P（x）EG(3)（5）R（a）T(2)I

（6）（?x）R（x）EG(5)（7）（?x）P（x）∧（?x）R（x）T(5)(6)I

11．若無向圖G中只有兩個(gè)奇數(shù)度結(jié)點(diǎn)，則這兩個(gè)結(jié)點(diǎn)一定是連通的．

證明：用反證法．設(shè)G中的兩個(gè)奇數(shù)度結(jié)點(diǎn)分別為u和v．假設(shè)u和v不連通，即它們之間無任何通路，則G至少有兩個(gè)連通分支G1，G2，且u和v分別屬于G1和G2，于是G1和G2各含有一個(gè)奇數(shù)度結(jié)點(diǎn)．這與定理3.1.2的推論矛盾．因而u和v一定是連通的．

12．設(shè)G是一個(gè)n階無向簡單圖，n是大于等于2的奇數(shù)．證明圖G與它的補(bǔ)圖G中的奇數(shù)度頂點(diǎn)個(gè)數(shù)相等．

證明：設(shè)G??V,E?，??V,E??．則E?是由n階無向完全圖Kn的邊刪去E所得到的．所以對于任意結(jié)點(diǎn)u?V，u在G和G中的度數(shù)之和等于u在Kn中的度數(shù)．由于n是大于等于2的奇數(shù)，從而Kn的每個(gè)結(jié)點(diǎn)都是偶數(shù)度的（n?1(?2)度），于是若u?V在G中是奇數(shù)度結(jié)點(diǎn)，則它在G中也是奇數(shù)度結(jié)點(diǎn)．故圖G與它的補(bǔ)圖G中的奇數(shù)度結(jié)點(diǎn)個(gè)數(shù)相等．

13．設(shè)連通圖G有k個(gè)奇數(shù)度的結(jié)點(diǎn)，證明在圖G中至少要添加

歐拉圖． k條邊才能使其成為2

證明：由定理3.1.2，任何圖中度數(shù)為奇數(shù)的結(jié)點(diǎn)必是偶數(shù)，可知k是偶數(shù)．

又根據(jù)定理4.1.1的推論，圖G是歐拉圖的充分必要條件是圖G不含奇數(shù)度結(jié)點(diǎn)．因此只要在每對奇數(shù)度結(jié)點(diǎn)之間各加一條邊，使圖G的所有結(jié)點(diǎn)的度數(shù)變?yōu)榕紨?shù)，成為歐拉圖． 故最少要加k條邊到圖G才能使其成為歐拉圖． 2

第四篇：電大離散數(shù)學(xué)證明題參考題

五、證明題

1．設(shè)G是一個(gè)n階無向簡單圖，n是大于等于3的奇數(shù)．證明圖G與它的補(bǔ)圖G中的奇數(shù)度頂點(diǎn)個(gè)數(shù)相等． 證明：設(shè)G??V,E?，??V,E??．則E?是由n階無向完全圖Kn的邊刪去E所得到的．所以對于任意結(jié)

點(diǎn)u?V，u在G和G中的度數(shù)之和等于u在Kn中的度數(shù)．由于n是大于等于3的奇數(shù)，從而Kn的每個(gè)結(jié)點(diǎn)都是偶數(shù)度的（n?1(?2)度），于是若u?V在G中是奇數(shù)度結(jié)點(diǎn)，則它在G中也是奇數(shù)度結(jié)點(diǎn)．故圖G與它的補(bǔ)圖G中的奇數(shù)度結(jié)點(diǎn)個(gè)數(shù)相等．

k條邊才能使其成為歐拉圖．

2證明：由定理3.1.2，任何圖中度數(shù)為奇數(shù)的結(jié)點(diǎn)必是偶數(shù)，可知k是偶數(shù)．

又根據(jù)定理4.1.1的推論，圖G是歐拉圖的充分必要條件是圖G不含奇數(shù)度結(jié)點(diǎn)．因此只要在每對奇數(shù)度結(jié)點(diǎn)之間各加一條邊，使圖G的所有結(jié)點(diǎn)的度數(shù)變?yōu)榕紨?shù)，成為歐拉圖． k故最少要加條邊到圖G才能使其成為歐拉圖． 2

五、證明題

1．試證明集合等式：A?(B?C)=(A?B)?(A?C)．

證：若x∈A?(B?C)，則x∈A或x∈B?C，即x∈A或x∈B且x∈A或x∈C．

即x∈A?B且x∈A?C，即x∈T=(A?B)?(A?C)，所以A?(B?C)?(A?B)?(A?C)．

反之，若x∈(A?B)?(A?C)，則x∈A?B且x∈A?C，即x∈A或x∈B且x∈A或x∈C，即x∈A或x∈B?C，即x∈A?(B?C)，所以(A?B)?(A?C)? A?(B?C)．

因此．A?(B?C)=(A?B)?(A?C)．

2．對任意三個(gè)集合A, B和C，試證明：若A?B = A?C，且A??，則B = C．

證明：設(shè)x?A，y?B，則?A?B，因?yàn)锳?B = A?C，故? A?C，則有y?C，所以B? C．

設(shè)x?A，z?C，則? A?C，因?yàn)锳?B = A?C，故?A?B，則有z?B，所以C?B．

故得B = C．

3、設(shè)A，B是任意集合，試證明：若A?A=B?B，則A=B．

許多同學(xué)不會(huì)做，是不應(yīng)該的．我們看一看

證明：設(shè)x?A，則?A?A，因?yàn)锳?A=B?B，故?B?B，則有x?B，所以A?B．

設(shè)x?B，則?B?B，因?yàn)锳?A=B?B，故?A?A，則有x?A，所以B?A．

故得A=B．

2．設(shè)連通圖G有k個(gè)奇數(shù)度的結(jié)點(diǎn)，證明在圖G中至少要添加

1．試證明命題公式(P?(Q??R))??P?Q與?（P??Q）等價(jià)．

證：(P?(Q??R))??P?Q?(?P?(Q??R))??P?Q

?((?P?Q??R)??P)?Q

??P?Q（吸收律）

??(P??Q)（摩根律）

2．試證明(?x)(P(x)?R(x))?(?x)P(x)?(?x)R(x)．

分析：前提：(?x)(P(x)?R(x))，結(jié)論：(?x)P(x)?(?x)R(x)．

證明(1)(?x)(P(x)?R(x))P

(2)P(a)?R(a)ES(1)(存在指定規(guī)則)

(3)P(a)T(2)（化簡）

(4)(?x)P(x)EG(3)(存在推廣規(guī)則)

(5)R(a)T(2)（化簡）

(6)(?x)R(x)EG(5)(存在推廣規(guī)則)

(7)(?x)P(x)?(?x)R(x)T(4)(6)（合取引入）

2．設(shè)集合A={1,2,3,4}，B={2, 4, 6, 8}，判斷下列關(guān)系f：A→B是否構(gòu)成函數(shù)，并說明理由．

(1)f={<1, 4>,<2, 2,>,<4, 6>,<1, 8>}；(2)f={<1, 6>,<3, 4>,<2, 2>}；

(3)f={<1, 8>,<2, 6>,<3, 4>,<4, 2,>}．

解：(1)f不能構(gòu)成函數(shù)．

因?yàn)锳中的元素3在f中沒有出現(xiàn)．

(2)f不能構(gòu)成函數(shù)．

因?yàn)锳中的元素4在f中沒有出現(xiàn)．

(3)f可以構(gòu)成函數(shù)．

因?yàn)閒的定義域就是A，且A中的每一個(gè)元素都有B中的唯一一個(gè)元素與其對應(yīng)，滿足函數(shù)定義的條件．

三、公式翻譯題

1．請將語句“今天是天晴”翻譯成命題公式．

解：設(shè)P：今天是天晴；

則命題公式為： P．

問：“今天不是天晴”的命題公式是什么？

2．請將語句“小王去旅游，小李也去旅游．”翻譯成命題公式．

解：設(shè)P：小王去旅游，Q：小李去旅游，則命題公式為：P?Q．

注：語句中包含“也”、“且”、“但”等連接詞，命題公式要用合取“?”．

3．請將語句“他去旅游，僅當(dāng)他有時(shí)間．”翻譯成命題公式．

解：設(shè)P：他去旅游，Q：他有時(shí)間，則命題公式為：P?Q．

注意：命題公式的翻譯還要注意“不可兼或”的表示．

例如，教材第164頁的例6 “T2次列車5點(diǎn)或6點(diǎn)鐘開．”怎么翻譯成命題公式？這里的“或”為不可兼或．

4．請將語句“所有人都努力工作．”翻譯成謂詞公式．

解：設(shè)P(x)：x是人，Q(x)：x努力工作．

謂詞公式為：(?x)(P(x)? Q(x))．

第五篇：離散數(shù)學(xué)證明題解題方法

離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支，是計(jì)算機(jī)科學(xué)中基礎(chǔ)理論的核心課程。離散數(shù)學(xué)以研究離散量的結(jié)構(gòu)和相互間的關(guān)系為主要目標(biāo)，其研究對象一般地是有限個(gè)或可數(shù)個(gè)元素，因此他充分描述了計(jì)算機(jī)科學(xué)離散性的特點(diǎn)。

1、定義和定理多。

離散數(shù)學(xué)是建立在大量定義上面的邏輯推理學(xué)科。因而對概念的理解是我們學(xué)習(xí)這門學(xué)科的核心。在這些概念的基礎(chǔ)上，特別要注意概念之間的聯(lián)系，而描述這些聯(lián)系的實(shí)體則是大量的定理和性質(zhì)。

●證明等價(jià)關(guān)系：即要證明關(guān)系有自反、對稱、傳遞的性質(zhì)。

●證明偏序關(guān)系：即要證明關(guān)系有自反、反對稱、傳遞的性質(zhì)。（特殊關(guān)系的證明就列出來兩種，要證明剩下的幾種只需要結(jié)合定義來進(jìn)行）。

●證明滿射：函數(shù)f：XY，即要證明對于任意的yY，都有x

或者對于任意的f(x1)=f(x2)，則有x1=x2。

●證明集合等勢：即證明兩個(gè)集合中存在雙射。有三種情況：第一、證明兩個(gè)具體的集合等勢，用構(gòu)造法，或者直接構(gòu)造一個(gè)雙射，或者構(gòu)造兩個(gè)集合相互間的入射；第二、已知某個(gè)集合的基數(shù)，如果為?，就設(shè)它和R之間存在雙射f，然后通過f的性質(zhì)推出另外的雙射，因此等勢；如果為?0，則設(shè)和N之間存在雙射；第三、已知兩個(gè)集合等勢，然后再證明另外的兩個(gè)集合等勢，這時(shí)，先設(shè)已知的兩個(gè)集合存在雙射，然后根據(jù)剩下題設(shè)條件證明要證的兩個(gè)集合存在雙射。

●證明群：即要證明代數(shù)系統(tǒng)封閉、可結(jié)合、有幺元和逆元。（同樣，這一部分能夠作為證明題的概念更多，要結(jié)合定義把它們?nèi)扛阃笍兀?/p>

●證明子群：雖然子群的證明定理有兩個(gè)，但如果考證明子群的話，通常是第二個(gè)定理，即設(shè)是群，S是G的非空子集，如果對于S中的任意元素a和b有a*b-

1是的子群。對于有限子群，則可考慮第一個(gè)定理。

●證明正規(guī)子群：若是一個(gè)子群，H是G的一個(gè)子集，即要證明對于任意的aG，有aH=Ha，或者對于任意的hH，有a-1 *h*aH。這是最常見的題目中所使用的方法。●證明格和子格：子格沒有條件，因此和證明格一樣，證明集合中任意兩個(gè)元素的最大元和最小元都在集合中。

圖論雖然方法性沒有前幾部分的強(qiáng)，但是也有一定的方法，如最長路徑法、構(gòu)造法等等 下面講一下離散證明題的證明方法：

1、直接證明法

直接證明法是最常見的一種證明的方法，它通常用作證明某一類東西具有相同的性質(zhì)，或者符合某一些性質(zhì)必定是某一類東西。

直接證明法有兩種思路，第一種是從已知的條件來推出結(jié)論，即看到條件的時(shí)候，并不知道它怎么可以推出結(jié)論，則可以先從已知條件按照定理推出一些中間的條件（這一步可能是沒有目的的，要看看從已知的條件中能夠推出些什么），接著，選擇可以推出結(jié)論的那個(gè)條件繼續(xù)往下推演；另外一種是從結(jié)論反推回條件，即看到結(jié)論的時(shí)候，首先要反推一下，看看S,則X，使得f(x)=y。●證明入射：函數(shù)f：XY，即要證明對于任意的x1、x2X，且x1≠x2，則f(x1)≠f(x2)；

從哪些條件可以得出這個(gè)結(jié)論（這一步也可能是沒有目的的，因?yàn)椴⒉恢酪玫侥膫€(gè)條件），以此類推一直到已知的條件。通常這兩種思路是同時(shí)進(jìn)行的。

2、反證法

反證法是證明那些“存在某一個(gè)例子或性質(zhì)”，“不具有某一種的性質(zhì)”，“僅存在唯一”等的題目。

它的方法是首先假設(shè)出所求命題的否命題，接著根據(jù)這個(gè)否命題和已知條件進(jìn)行推演，直至推出與已知條件或定理相矛盾，則認(rèn)為假設(shè)是不成立的，因此，命題得證。

3、構(gòu)造法

證明“存在某一個(gè)例子或性質(zhì)”的題目，我們可以用反證法，假設(shè)不存在這樣的例子和性質(zhì)，然后推出矛盾，也可以直接構(gòu)造出這么一個(gè)例子就可以了。這就是構(gòu)造法，通常這樣的題目在圖論中多見。值得注意的是，有一些題目其實(shí)也是本類型的題目，只不過比較隱蔽罷了，像證明兩個(gè)集合等勢，實(shí)際上就是證明“兩個(gè)集合中存在一個(gè)雙射”，我們即可以假設(shè)不存在，用反證法，也可以直接構(gòu)造出這個(gè)雙射。

4、數(shù)學(xué)歸納法

數(shù)學(xué)歸納法是證明與自然數(shù)有關(guān)的題目，而且這一類型的題目可以遞推。作這一類型題目的時(shí)候，要注意一點(diǎn)就是所要?dú)w納內(nèi)容的選擇。

學(xué)習(xí)離散數(shù)學(xué)的最大困難是它的抽象性和邏輯推理的嚴(yán)密性。在離散數(shù)學(xué)中，假設(shè)讓你解一道題或證明一個(gè)命題，你應(yīng)首先讀懂題意，然后尋找解題或證明的思路和方法，當(dāng)你相信已找到了解題或證明的思路和方法，你必須把它嚴(yán)格地寫出來。一個(gè)寫得很好的解題過程或證明是一系列的陳述，其中每一條陳述都是前面的陳述經(jīng)過簡單的推理而得到的。仔細(xì)地寫解題過程或證明是很重要的，既能讓讀者理解它，又能保證解題過程或證明準(zhǔn)確無誤。一個(gè)好的解題過程或證明應(yīng)該是條理清楚、論據(jù)充分、表述簡潔的。針對這一要求，在講課中老師會(huì)提供大量的典型例題供同學(xué)們參考和學(xué)習(xí)。

在學(xué)習(xí)離散數(shù)學(xué)中所遇到的這些困難，可以通過多學(xué)、多看、認(rèn)真分析講課中所給出的典型例題的解題過程，再加上多練，從而逐步得到解決。在此特別強(qiáng)調(diào)一點(diǎn)：深入地理解和掌握離散數(shù)學(xué)的基本概念、基本定理和結(jié)論，是學(xué)好離散數(shù)學(xué)的重要前提之一。所以，同學(xué)們要準(zhǔn)確、全面、完整地記憶和理解所有這些基本定義和定理。

學(xué)好高數(shù)＝基本概念透＋基本定理牢＋基本網(wǎng)絡(luò)有＋基本常識記＋基本題型熟。數(shù)學(xué)就是一個(gè)概念＋定理體系(還有推理)，對概念的理解至關(guān)重要，比如說極限、導(dǎo)數(shù)等

再快樂的單身漢遲早也會(huì)結(jié)婚,幸福不是永久的嘛！

愛就像坐旋轉(zhuǎn)木馬，雖然永遠(yuǎn)在你愛人的身后，但隔著永恒的距離。

相互牽著的手,永不放開,直到他的出現(xiàn),你離開了我.時(shí)光就這樣靜靜的流淌,那些在躺在草地上曬太陽的時(shí)光,那些拂面吹來的風(fēng).明知道是讓對方痛苦的愛就不要讓它繼續(xù)下去，割舍掉。如果不行就將它凍結(jié)在自己內(nèi)心最深的角落。