离散数学历年考试证明题

发布时间：2020-03-03 01:35:42 来源：范文大全收藏本文下载本文手机版

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)I

4、设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

将本文的Word文档下载到电脑，方便编辑。

推荐度：

点击下载文档