离散数学证明题

第一篇：离散数学证明题

离散数学证明题

离散数学证明题:链为分配格

证明设a,b均是链A的元素，因为链中任意两个元素均可比较，即有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是分配格.一.线性插值(一次插值)

已知函数f(x)在区间的端点上的函数值yk=f(xk),yk+1=f(xk+1),求一个一次函数y=p1(x)使得yk=f(xk),yk+1=f(xk+1),其几何意义是已知平面上两点(xk,yk),(xk+1,yk+1),求一条直线过该已知两点。

1.插值函数和插值基函数

由直线的点斜式公式可知：

把此式按照yk和yk+1写成两项:

记

并称它们为一次插值基函数。该基函数的特点如下表：

从而

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

此形式称之为拉格朗日型插值多项式。其中,插值基函数与yk、yk+1无关，而由插值结点xk、xk+1所决定。一次插值多项式是插值基函数的线性组合,相应的组合系数是该点的函数值yk、yk+1.例1:已知lg10=1,lg20=1.3010,利用插值一次多项式求lg12的近似值。

解:f(x)=lgx,f(10)=1,f(20)=1.3010,设

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

则插值基函数为：

于是,拉格朗日型一次插值多项式为:

故:

即lg12由lg10和lg20两个值的线性插值得到,且具有两位有效数字(精确值lg12=1.0792).二.二次插值多项式

已知函数y=f(x)在点xk-1,xk,xk+1上的函数值yk-1=f(xk-1),yk=f(xk),yk+1=f(xk+1),求一个次数不超过二次的多项式p2(x),使其满足,p2(xk-1)=yk-1,p2(xk)=yk,p2(xk+1)=yk+1.其几何意义为:已知平面上的三个点

(xk-1,yk-1),(xk,yk),(xk+1,yk+1),求一个二次抛物线,使得该抛物线经过这三点。

1.插值基本多项式

有三个插值结点xk-1,xk,xk+1构造三个插值基本多项式，要求满足：

(1)基本多项式为二次多项式;(2)它们的函数值满足下表：

因为lk-1(xk)=0,lk-1(xk+1)=0,故有因子(x-xk)(x-xk+1),而其已经是一个二次多项式,仅相差一个常数倍,可设

lk-1(x)=a(x-xk)(x-xk+1),又因为

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

1得

从而

同理得

基本二次多项式见右上图(点击按钮“显示Li”)。

2.拉格朗日型二次插值多项式

由前述,拉格朗日型二次插值多项式:

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

是三个二次插值多项式的线性组合,因而其是次数不超过二次的多项式,且满足:

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

例2已知：

xi101520

yi=lgxi11.17611.3010

利用此三值的二次插值多项式求lg12的近似值。

解：设x0=10,x1=15,x2=20,则:

故:

所以

7利用三个点进行抛物插值得到lg12的值,与精确值lg12=1.0792相比,具有3位有效数字,精度提高了。

三、拉格朗日型n次插值多项式

已知函数y=f(x)在n+1个不同的点x0,x1,…,x2上的函数值分别为

y0,y1,…,yn,求一个次数不超过n的多项式pn(x),使其满足:

pn(xi)=yi,(i=0,1,…,n),即n+1个不同的点可以唯一决定一个n次多项式。

1.插值基函数

过n+1个不同的点分别决定n+1个n次插值基函数

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

每个插值基本多项式li(x)满足：

(1)li(x)是n次多项式;

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

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

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

因其已经是n次多项式，故而仅相差一个常数因子。令:

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

由li(xi)=1,可以定出a,进而得到：

2.n次拉格朗日型插值多项式pn(x)

pn(x)是n+1个n次插值基本多项式l0(x),l1(x),…,ln(X)的线性组合,相应的组合系数是y0,y1,…,yn。即:

pn(x)=y0l0(x)+y1l1(x)+…+ynln(x),从而pn(x)是一个次数不超过n的多项式,且满足

pn(xi)=yi,(i=0,1,2,…,n).例3求过点(2,0),(4,3),(6,5),(8,4),(10,1)的拉格朗日型插值多项式。

解用4次插值多项式对5个点插值。

所以

四、拉格朗日插值多项式的截断误差

我们在上用多项式pn(x)来近似代替函数f(x),其截断误差记作

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

当x在插值结点xi上时Rn(xi)=f(xi)-pn(xi)=0,下面来估计截断误差：

定理1：设函数y=f(x)的n阶导数y(n)=f(n)(x)在上连续，y(n+1)=f(n+1)(x)

在(a,b)上存在;插值结点为:

a≤x0

pn(x)是n次拉格朗日插值多项式;则对任意x∈有：

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

证明：由插值多项式的要求：

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

设

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

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

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个零点，反复使用罗尔中值定理:存在ξ∈(a,b),使;因pn(x)是n次多项式，故p(n+1)(ξ)=0,而

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

是首项系数为1的n+1次多项式，故有

于是

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

得：

所以

设,则：

易知，线性插值的截断误差为:

二次插值的截断误差为:

下面来分析前面两个例子(例1，例2)中计算lg12的截断误差：

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

e=|1.0792-1.0602|=0.0190;

估计误差：f(x)=lgx，当x∈时,2

第二篇：离散数学证明题

证明题

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．构造下列推理的证明：

（1）前提：(PQ)(RS)，(QP)R，R

前提：PQ。

（2）前提：Q →P, Q  S , S  M , M∧R前提：结论：P∧Q

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

结论：S →R（4）前提：(P∨Q)→(R∧S),(S∨M)→ U结论：P →U（5）前提：P →┐Q,┐R∨Q ,R∧┐S

结论：┐P（6）前提：P∨Q，P →R, Q → S结论：R∨S

证明：（1）

① R前提引入

②(QP)R前提引入

③ QP①②析取三段论

④ RS①附加规则

⑤ (PQ)(RS)前提引入

⑥ PQ④⑤拒取式

⑦(PQ)(QP)③⑥合取规则

⑧ PQ⑦置换规则

（2）

① M∧R前提引入

② M①化简规则

③ S  M前提引入

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

⑤ M → S④化简规则

⑥ S② ⑥假言推理

⑦ Q  S前提引入

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

⑨ S → Q⑧化简规则

⑩ 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)合取前提引入附加前提引入① ②假言推理 前提引入③④ 假言推理前提引入⑤⑥假言推理附加前提引入①附加规则前提引入②③ 假言推理④化简规则⑤附加规则前提引入⑥ ⑦假言推理结论否定引入前提引入① ②假言推理前提引入③④析取三段论前提引入⑥化简规则⑤⑦合取

① ┐(R∨S)结论否定引入

② ┐R∧┐S①置换规则

③ ┐R②化简规则

④ P →R前提引入

⑤ ┐P③④拒取

⑥ ┐S②化简规则

⑦ Q → S前提引入

⑧ ┐Q⑥ ⑦拒取

⑨ ┐P∧┐Q⑤⑧合取

⑩ ┐(P∨Q)⑨置换规则

(11)P∨Q前提引入

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

3．在命题逻辑中构造下列推理的证明：

（1）如果今天是星期六，我们就要到颐和园或圆明园去玩。如果颐和园游人太多，我们就不到颐和园去玩。今天是星期六。颐和园游人太多。所以我们到圆明园玩。

（2）明天是晴天，或是雨天；若明天是晴天，我就去看电影；若我看电影，我就不看书。所以，如果我看书，则明天是雨天。

（3）如果小王是理科学生，他必学好数学；如果小王不是文科生，他必是理科生；小王没学好数学。所以，小王是文科生。

解：（1）首先将命题符号化：

设P: 今天是星期六；Q: 我们到颐和园去玩；R:我们到圆明园去玩；S:颐和园游人多。

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

结论：R证明：

① ②假言推理

④ P前提引入

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

（2）首先将命题符号化：令P：明天是晴天，Q：明天是雨天，R：我看电影，S：我看书。① S → ┐Q前提引入②S前提引入③ ┐Q

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

结论： S→Q

证明：

① S

② R→┐S

③┐R

④ P→R

⑤ ┐P

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

⑦ Q⑤⑥析取三段论

（3）首先将命题符号化：

令P：小王是理科生，Q：小王是文科生，R：小王学好数学。

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

结论：Q

证明：

① P→R

② ┐R

③ ┐P

④ ┐Q→P

⑤ Q

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

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

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

证明：①

必要性。假设A∩B≠Φ，必有x属于A∩B，则x属于A同时属于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．设R是A上的二元关系，试证：R是传递的当且仅当R2R，其中R2表示RR。

（1）设R传递，（x，y）∈R2，t∈A使

，∈R（因为R2＝R R）

∵R传递 ∴∈R

∴R2 R

（2）设R2R，若，∈R

则∈R2，∵R2 R，∴∈R。即R传递。

8．设A是集合，R1,R2是A上的二元关系，证明：

若R1,R2是自反的和对称的，则R1R2也是自反的和对称的。

证明:

(1)∵ R1,R2是A上的自反关系

∴ IAR1IAR2

∴IAR1R2

∴ R1R2是A上的自反关系

又∵ R1,R2是A上的对称关系

∴ R1R11R2R21

(R1R2)111R1R2R1R2∴ R1R2 是A上的对称关系

第三篇：离散数学历年考试证明题

1、试证明集合等式A(BC)=(AB)(AC)．

证明：

设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)．

证明：设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、设A，B是任意集合，试证明：若AA=BB，则A=B．

证明：设xA，则AA，因为AA=BB，故BB，则有xB，所以AB． 设xB，则BB，因为AA=BB，故AA，则有xA，所以BA． 故得A=B．

5、设G是一个n阶无向简单图，n是大于等于2的奇数．证明G与G中的奇数度顶点个数相等(G是G的补图)．

证明：因为n是奇数，所以n阶完全图每个顶点度数为偶数，因此，若G中顶点v的度数为奇数，则在G中v的度数一定也是奇数，所以G与G中的奇数度顶点个数相等．

6．设连通图G有k个奇数度的结点，证明在图G中至少要添加

欧拉图．

证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k是偶数．

又根据定理4.1.1的推论，图G是欧拉图的充分必要条件是图G不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G的所有结点的度数变为偶数，成为欧拉图． 故最少要加k条边才能使其成为2k条边到图G才能使其成为欧拉图． 2

7．设R是集合A上的对称关系和传递关系，试证明：若对任意aA，存在bA，使得R，则R是等价关系．

证明：已知R是对称关系和传递关系，只需证明R是自反关系．

aA，bA，使得R，因为R是对称的，故R；

又R是传递的，即当R，R R；

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

所以，R是等价关系．

8．若非空集合A上的二元关系R和S是偏序关系，试证明：RS也是A上的偏序关系．

证明：.① xA,x,xR,x,xSx,xRS，所以RS有自反性；②x,yA,因为R，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，因为R，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是偏序关系．

9．试证明命题公式(P(QR))PQ与（PQ）等价．

证明：(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中的两个奇数度结点分别为u和v．假设u和v不连通，即它们之间无任何通路，则G至少有两个连通分支G1，G2，且u和v分别属于G1和G2，于是G1和G2各含有一个奇数度结点．这与定理3.1.2的推论矛盾．因而u和v一定是连通的．

12．设G是一个n阶无向简单图，n是大于等于2的奇数．证明图G与它的补图G中的奇数度顶点个数相等．

证明：设GV,E，V,E．则E是由n阶无向完全图Kn的边删去E所得到的．所以对于任意结点uV，u在G和G中的度数之和等于u在Kn中的度数．由于n是大于等于2的奇数，从而Kn的每个结点都是偶数度的（n1(2)度），于是若uV在G中是奇数度结点，则它在G中也是奇数度结点．故图G与它的补图G中的奇数度结点个数相等．

13．设连通图G有k个奇数度的结点，证明在图G中至少要添加

欧拉图． k条边才能使其成为2

证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k是偶数．

又根据定理4.1.1的推论，图G是欧拉图的充分必要条件是图G不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G的所有结点的度数变为偶数，成为欧拉图． 故最少要加k条边到图G才能使其成为欧拉图． 2

第四篇：电大离散数学证明题参考题

五、证明题

1．设G是一个n阶无向简单图，n是大于等于3的奇数．证明图G与它的补图G中的奇数度顶点个数相等． 证明：设GV,E，V,E．则E是由n阶无向完全图Kn的边删去E所得到的．所以对于任意结

点uV，u在G和G中的度数之和等于u在Kn中的度数．由于n是大于等于3的奇数，从而Kn的每个结点都是偶数度的（n1(2)度），于是若uV在G中是奇数度结点，则它在G中也是奇数度结点．故图G与它的补图G中的奇数度结点个数相等．

k条边才能使其成为欧拉图．

2证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k是偶数．

又根据定理4.1.1的推论，图G是欧拉图的充分必要条件是图G不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G的所有结点的度数变为偶数，成为欧拉图． 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．对任意三个集合A, B和C，试证明：若AB = AC，且A，则B = C．

证明：设xA，yB，则AB，因为AB = AC，故 AC，则有yC，所以B C．

设xA，zC，则 AC，因为AB = AC，故AB，则有zB，所以CB．

故得B = C．

3、设A，B是任意集合，试证明：若AA=BB，则A=B．

许多同学不会做，是不应该的．我们看一看

证明：设xA，则AA，因为AA=BB，故BB，则有xB，所以AB．

设xB，则BB，因为AA=BB，故AA，则有xA，所以BA．

故得A=B．

2．设连通图G有k个奇数度的结点，证明在图G中至少要添加

1．试证明命题公式(P(QR))PQ与（PQ）等价．

证：(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))，结论：(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)（化简）

(4)(x)P(x)EG(3)(存在推广规则)

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

(6)(x)R(x)EG(5)(存在推广规则)

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

2．设集合A={1,2,3,4}，B={2, 4, 6, 8}，判断下列关系f：A→B是否构成函数，并说明理由．

(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不能构成函数．

因为A中的元素3在f中没有出现．

(2)f不能构成函数．

因为A中的元素4在f中没有出现．

(3)f可以构成函数．

因为f的定义域就是A，且A中的每一个元素都有B中的唯一一个元素与其对应，满足函数定义的条件．

三、公式翻译题

1．请将语句“今天是天晴”翻译成命题公式．

解：设P：今天是天晴；

则命题公式为： P．

问：“今天不是天晴”的命题公式是什么？

2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式．

解：设P：小王去旅游，Q：小李去旅游，则命题公式为：PQ．

注：语句中包含“也”、“且”、“但”等连接词，命题公式要用合取“”．

3．请将语句“他去旅游，仅当他有时间．”翻译成命题公式．

解：设P：他去旅游，Q：他有时间，则命题公式为：PQ．

注意：命题公式的翻译还要注意“不可兼或”的表示．

例如，教材第164页的例6 “T2次列车5点或6点钟开．”怎么翻译成命题公式？这里的“或”为不可兼或．

4．请将语句“所有人都努力工作．”翻译成谓词公式．

解：设P(x)：x是人，Q(x)：x努力工作．

谓词公式为：(x)(P(x) Q(x))．

第五篇：离散数学证明题解题方法

离散数学是现代数学的一个重要分支，是计算机科学中基础理论的核心课程。离散数学以研究离散量的结构和相互间的关系为主要目标，其研究对象一般地是有限个或可数个元素，因此他充分描述了计算机科学离散性的特点。

1、定义和定理多。

离散数学是建立在大量定义上面的逻辑推理学科。因而对概念的理解是我们学习这门学科的核心。在这些概念的基础上，特别要注意概念之间的联系，而描述这些联系的实体则是大量的定理和性质。

●证明等价关系：即要证明关系有自反、对称、传递的性质。

●证明偏序关系：即要证明关系有自反、反对称、传递的性质。（特殊关系的证明就列出来两种，要证明剩下的几种只需要结合定义来进行）。

●证明满射：函数f：XY，即要证明对于任意的yY，都有x

或者对于任意的f(x1)=f(x2)，则有x1=x2。

●证明集合等势：即证明两个集合中存在双射。有三种情况：第一、证明两个具体的集合等势，用构造法，或者直接构造一个双射，或者构造两个集合相互间的入射；第二、已知某个集合的基数，如果为א，就设它和R之间存在双射f，然后通过f的性质推出另外的双射，因此等势；如果为א0，则设和N之间存在双射；第三、已知两个集合等势，然后再证明另外的两个集合等势，这时，先设已知的两个集合存在双射，然后根据剩下题设条件证明要证的两个集合存在双射。

●证明群：即要证明代数系统封闭、可结合、有幺元和逆元。（同样，这一部分能够作为证明题的概念更多，要结合定义把它们全部搞透彻）。

●证明子群：虽然子群的证明定理有两个，但如果考证明子群的话，通常是第二个定理，即设是群，S是G的非空子集，如果对于S中的任意元素a和b有a*b-

1是的子群。对于有限子群，则可考虑第一个定理。

●证明正规子群：若是一个子群，H是G的一个子集，即要证明对于任意的aG，有aH=Ha，或者对于任意的hH，有a-1 *h*aH。这是最常见的题目中所使用的方法。●证明格和子格：子格没有条件，因此和证明格一样，证明集合中任意两个元素的最大元和最小元都在集合中。

图论虽然方法性没有前几部分的强，但是也有一定的方法，如最长路径法、构造法等等 下面讲一下离散证明题的证明方法：

1、直接证明法

直接证明法是最常见的一种证明的方法，它通常用作证明某一类东西具有相同的性质，或者符合某一些性质必定是某一类东西。

直接证明法有两种思路，第一种是从已知的条件来推出结论，即看到条件的时候，并不知道它怎么可以推出结论，则可以先从已知条件按照定理推出一些中间的条件（这一步可能是没有目的的，要看看从已知的条件中能够推出些什么），接着，选择可以推出结论的那个条件继续往下推演；另外一种是从结论反推回条件，即看到结论的时候，首先要反推一下，看看S,则X，使得f(x)=y。●证明入射：函数f：XY，即要证明对于任意的x1、x2X，且x1≠x2，则f(x1)≠f(x2)；

从哪些条件可以得出这个结论（这一步也可能是没有目的的，因为并不知道要用到哪个条件），以此类推一直到已知的条件。通常这两种思路是同时进行的。

2、反证法

反证法是证明那些“存在某一个例子或性质”，“不具有某一种的性质”，“仅存在唯一”等的题目。

它的方法是首先假设出所求命题的否命题，接着根据这个否命题和已知条件进行推演，直至推出与已知条件或定理相矛盾，则认为假设是不成立的，因此，命题得证。

3、构造法

证明“存在某一个例子或性质”的题目，我们可以用反证法，假设不存在这样的例子和性质，然后推出矛盾，也可以直接构造出这么一个例子就可以了。这就是构造法，通常这样的题目在图论中多见。值得注意的是，有一些题目其实也是本类型的题目，只不过比较隐蔽罢了，像证明两个集合等势，实际上就是证明“两个集合中存在一个双射”，我们即可以假设不存在，用反证法，也可以直接构造出这个双射。

4、数学归纳法

数学归纳法是证明与自然数有关的题目，而且这一类型的题目可以递推。作这一类型题目的时候，要注意一点就是所要归纳内容的选择。

学习离散数学的最大困难是它的抽象性和逻辑推理的严密性。在离散数学中，假设让你解一道题或证明一个命题，你应首先读懂题意，然后寻找解题或证明的思路和方法，当你相信已找到了解题或证明的思路和方法，你必须把它严格地写出来。一个写得很好的解题过程或证明是一系列的陈述，其中每一条陈述都是前面的陈述经过简单的推理而得到的。仔细地写解题过程或证明是很重要的，既能让读者理解它，又能保证解题过程或证明准确无误。一个好的解题过程或证明应该是条理清楚、论据充分、表述简洁的。针对这一要求，在讲课中老师会提供大量的典型例题供同学们参考和学习。

在学习离散数学中所遇到的这些困难，可以通过多学、多看、认真分析讲课中所给出的典型例题的解题过程，再加上多练，从而逐步得到解决。在此特别强调一点：深入地理解和掌握离散数学的基本概念、基本定理和结论，是学好离散数学的重要前提之一。所以，同学们要准确、全面、完整地记忆和理解所有这些基本定义和定理。

学好高数＝基本概念透＋基本定理牢＋基本网络有＋基本常识记＋基本题型熟。数学就是一个概念＋定理体系(还有推理)，对概念的理解至关重要，比如说极限、导数等

再快乐的单身汉迟早也会结婚,幸福不是永久的嘛！

爱就像坐旋转木马，虽然永远在你爱人的身后，但隔着永恒的距离。

相互牵着的手,永不放开,直到他的出现,你离开了我.时光就这样静静的流淌,那些在躺在草地上晒太阳的时光,那些拂面吹来的风.明知道是让对方痛苦的爱就不要让它继续下去，割舍掉。如果不行就将它冻结在自己内心最深的角落。