1、本科离散数学、单项选择题1设P: a是偶数，Q : b是偶数。R： a + b是偶数，则命题“若a是偶数，b是偶数，则a + b也是偶数”符号化为（D 2 表达式 x (P (x，y) Q (z)y (Q (x，y) zQ (z)中x 的辖域是(P (x，y) Q (z) o3 设 Si,S2 , S3P（ ）, S4 P（）则命题为假的是（S2 S4 ）o4.设G是有n个结点的无向完全图，则G 的边数(1/2 n ( n-1)5.设G是连通平面图，有 v个结点，e条边，r个面，则r= （ e-v+2）6若集合A=1，2，1，2，则下列表述正确的是（1 A ）.7.已知一棵无向树 T中有8个顶
2、点，4度、3度、2度的分支点各一个，T的树叶数为（5 ）011 11100 118.设无向图G的邻接矩阵为 100 00则G的边数为（7 ）.110 01110 109.设集合A= a，则A的幂集为（，a)10 .下列公式中（A B （A B）为永真式.11.若G是一个汉密尔顿图，则 G 一定是（连通图）.12集合A=1,2, 3, 4上的关系R=|x=y且x, y A，则R的性质为（传递的 ）.13.设集合A=1，2，3，4，5，偏序关系 是A上的整除关系，则偏序集 上的元素5是集合A的（极大元）.14.图G如图一所示，以下说法正确的是 （a, d） ,（b, d）是边割集）. 图一15设A
3、 （x） : x是人，B （x） : x是工人，则命题“有人是工人”可符号化为（ （x）（A（x） A B（x）.16若集合A=1，2，B=1，2，1，2，则下列表述正确的是（A B，且A B ）.17.设有向图（a）、（ b）、（6与（d）如图一所示，则下列结论成立的是 （d）是强连通的）.何 (d)18 .设图G的邻接矩阵为0 110 00 0 110 0 0 0则G的边数为(5 ) 0 10 0 10 10 1019 .无向简单图G是棵树，当且仅当（G连通且边数比结点数少1 )20下列公式(P ( Q P) ( P (P Q)为重言式.21若集合A = a，a，1，2，则下列表述正确的是
4、（a A）.22.设图G = ，v V,则下列结论成立的是 （ deg（v） 2 E ）v V23.命题公式（PV Q）- R的析取范式是（PA Q）V R ）24.下列等价公式成立的为 （P （ Q P） P （P Q）.25. 设 A=a, b, B=1,2 , Ri, R2, R3是 A 到 B 的二元关系，且 Ri=, , R2=, , , Ra=, ，则（R2 ）不是从A到B的函数.26设A=1,2, 3, 4, 5, 6, 7, 8 , R是A上的整除关系，B=2, 4, 6,则集合B的最大元、最小元、上界、下界依次为 （无、2、无、2）.27若集合A的元素个数为10，则其幂集的元
5、素个数为（1024）.28 如图一所示，以下说法正确的是（e是割点）.图一29 .设完全图K n有n个结点（n 2），m条边，当n为奇数）时，K n中存在欧拉回路.30 .已知图G的邻接矩阵为勺ci 1 r1 0 0 C l000111010111110i，则G有（5点，7边）.二、填空题（每小题 3分，共15分）1.设A， B为任意命题公式，C为重言式，若 A C B C，那么A B是重言_式（重言式、矛盾式或可满足式）。2命题公式（P-Q P的主合取范式为 （P Q） （ P Q） 。3.设集合 A= ，a，则 P（A） =_ , , a, ,a 。4.设图 G = V，E，G = V，E
6、，若 V =V,E E ,则 G是 G 的生成子图。r5在平面g = V，e中，则 deg（rJ=/|E| _，其中ri（ i=1，2，r）是g的面。6命题公式P P的真值是 假i 1（或F，或0） .7.若无向树 T有5个结点，则 T的边数为 4 .8.设正则 m叉树的树叶数为t，分支数为i，则（m-1）i= .9设集合A=1，2上的关系R= ,，则在R中仅需加一个元素 ，就可使新得到的关系为对称的.10.（ x）（A（x）-B（x，z）V C（y）中的自由变元有 z，y .11若集合 A=1，3，5，7，B=2，4，6, 8，则 AQ B=空集（或 ） .12.设集合 A=1 , 2 ,
7、3上的函数分别为：f=, , g=,则复合函数 g f = , ,.13设G是一个图，结点集合为 V,边集合为E,则G的结点度数之和为 2|E| （或“边数的两倍” ） .14.无向连通图 G的结点数为v,边数为e,贝U G当v与e满足 e=v-1 关系时是树.15设个体域D = 1,2, 3 , P（x）为“x小于2”，则谓词公式（x）P（x）的真值为 假（或F,或0） .16命题公式P （Q P）的真值是 T （或1） .17若图G=中具有一条汉密尔顿回路，则对于结点集 V的每个非空子集S,在G中删除S中的所有结点得到的连通分支数为W,则S中结点数|S与 W满足的关系式为 W |S| .1
8、8给定一个序列集合000 , 001, 01, 10, 0，若去掉其中的元素 0 ，则该序列集合构成前缀码.19已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为 5 20 ( x)(P(x)t Q(x) V R(x，y)中的自由变元为 R(x，y )中的 y 21设集合 A=0,1, 2, 3，B=2, 3, 4, 5，R 是 A 到 B 的二元关系，R x, y x A且 y B且 x, y A B则 R 的有序对集合为 ， 22设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，则 v，e和r满足的关系式 v-e+r=2 23.设G= 是有6个结点，8
9、条边的连通图，则从 G中删去 3 条边，可以确定图 G的一棵生成树.24无向图G存在欧拉回路，当且仅当 G连通且 _所有结点的度数全为偶数 25设个体域D = 1,2，则谓词公式 xA(x)消去量词后的等值式为 _A(1) A(2) 26设集合A = a，b，那么集合 A的幂集是 ,a,b, a, b 27.如果R1和R2是A上的自反关系，则 R1U R2，Rm R2，R1- R2中自反关系有 2 个.28设图G是有6个结点的连通图，结点的总度数为 18,则可从G中删去 4 条边后使之变成树.29设连通平面图 G的结点数为5，边数为6，则面数为 3 .30.设个体域D = a, b，则谓词公式
10、(x)A(x) A( x) B ( x)消去量词后的等值式为 _(A (a)A A (b)A (B ( a) V B ( b) ) .31.设集合 A=0，1 ，2 ，B=l ，2，3， 剖，R 是 A 到 B 的二元关系，R= |x A 且 y B 且 x， y 匕 A n B则 R 的有序对集合为 ,_32.设G是连通平面图，v， e， r分别表示G的结点数， 边数和面数， 则v， e和r满足的关系式 v-e+r=233.G=是有20个结点，25条边的连通图，则从G中删去 6条边，可以确定图 G的一棵生成树.34.无向图G存在欧拉回路， 当且仅当G所有结点的度数全为偶数且 连通 35.设个
11、体域D= 1,2 ，则谓词公式 xA(x)消去量词后的等值式为 A(1) A A(2)三、化简解答题11设集合 A=1，2，3，4，A 上的二元关系 R，R= 1，1， 1，4， 2，2， 2，3， 3，2， 3，3， 4，1，4，4，说明R是A上的等价关系。解 从R的表达式知， X A, (x, x) R,即R具有自反性；三、逻辑公式翻译1将语句 今天上课.”翻译成命题公式.设P:今天上课， 则命题公式为：P.2将语句 他去操场锻炼，仅当他有时间. ”翻译成命题公式.设P:他去操场锻炼，Q:他有时间， 则命题公式为：P Q.3将语句“他是学生.”翻译成命题公式.设P:他是学生， 则命题公式为
12、： P.4将语句“如果明天不下雨，我们就去郊游. ”翻译成命题公式.设P:明天下雨，Q:我们就去郊游， 则命题公式为： P Q .5将语句“他不去学校.”翻译成命题公式.设P:他去学校， P.6将语句“他去旅游，仅当他有时间.”翻译成命题公式.设P :他去旅游，Q:他有时间， P Q.7.将语句“所有的人都学习努力.”翻译成命题公式.设 P(x): x 是人，Q(x) : X 学习努力， (x) (P(x) Q(x).8.将语句“如果你去了，那么他就不去.”翻译成命题公式.设P:你去，Q:他去， P Q.9.将语句“小王去旅游，小李也去旅游.”翻译成命题公式.设P:小王去旅游，Q:小李去旅游，
13、 P Q.10将语句“所有人都去工作.”翻译成谓词公式.设 P(x)： x 是人，Q(x): x去工作， (x)(P(x) Q(x).11将语句“如果所有人今天都去参加活动，则明天的会议取消. ”翻译成命题公式.设P:所有人今天都去参加活动， Q:明天的会议取消， P Q .12将语句“今天没有人来.”翻译成命题公式.设P :今天有人来， P.13将语句“有人去上课.”翻译成谓词公式.设 P(x): x 是人，Q(x): x 去上课，(x)(P(x) Q(x).1 1.将语句如果小李学习努力，那么他就会取得好成绩 .翻译成命题公式.设P：小李学习努力，Q：小李会取得好成绩，PTQ12.将语句小
14、张学习努力，小王取得好成绩.翻译成命题公式.设P:小张学习努力，Q：小王取得好成绩，PA Q四、判断说明题1.设集合A=1，2，B=3，4，从A到B的关系为f= ,_则f是A到B的函数.错误. 因为A中元素2没有B中元素与之对应，故f不是A到B的函数.2设G是一个有4个结点10条边的连通图，则 G为平面图.错误. 不满足“设G是一个有v个结点e条边的连通简单平面图，若 v 3,则e3,则e 3v-6.”7.如果R1和R2是A上的自反关系，则 R1U R2是自反的.正确. R1和R2是自反的， x A， R1， R2,则 R1 R2,所以R1U R2是自反的.8如图二所示的图 G存在一条欧拉回路
15、.第4正确. 因为图G为连通的，且其中每个顶点的度数为偶数.9. n PA( Q)V P 为永真式.正确.n PA( Q )V P是由PA( Q )与P组成的析取式，如果P的值为真，则n PA( P-n Q)V P为真，如果P的值为假，则n P与P-n Q为真，即n PA( P-n Q)为真，也即n P A( P-n Q )V P为真，所以n P A( P-n Q )V P是永真式.另种说明：n PA( P-n Q)V P是由n PA( P-n Q)与P组成的析取式， 只要其中一项为真，则整个公式为真.可以看到，不论P的值为真或为假，n PA( P-n Q)与P总有一个为真， 所以n PA(
16、P-n Q)V P是永真式.或用等价演算n PA( P-n Q)V P T10若偏序集A, R的哈斯图如图一所示，则集合 A的最大元为a，最小元不存在.图一正确.对于集合A的任意元素x,均有x, a R (或xRa)，所以a是集合A中的最大元按照最小元的定义，在集合 A中不存在最小元.11.如果R1和R2是A上的自反关系， 则Ri n R2是自反的。正确，R1和R2，是自反的， x匕A,x,x匕R1,x,x R2, _则x,x匕R1 n R2，所以R1 n R2是自反的.12.如图二所示的图中存在一条欧拉回路 .图二 入正确，因为图G为连通的，且其中每个顶点的度数为偶数。五计算题(每小题12分
17、，本题共36分)1.试求出(PV Q)-( RV Q)的析取范式.(PV Q)-( RV Q) n (PV Q) V( RV Q)(n PAn Q) V( RV Q)(n PAn Q)V RV Q (析取范式)2 设 A=1, 1,2 ，B= 1, 2，试计算(1) (A n B) ( 2) (AU B) ( 3) A (An B).(1)( An B) =1(2)( A UB) =1,2, 1, 2(3)A (An B) =1, 1,23图 G=，其中 V= a, b, c, d ，E= (a, b), (a, c) , (a, d), (b, c), (b, d), (c, d)，对应边的
18、权值依次为 1、2、3、1、4及 5,试(1)画出G的图形；(2)写岀G的邻接矩阵；(3)求出G权最小的生成树及其权值.(1) G的图形表示如图一所示:图一(3 )最小的生成树如图二中的粗线所示:权为：1+1+3=5图01111011(2)邻接矩阵：110111104 .画一棵带权为1,2, 2, 3, 4的最优二叉树，计算它们的权. 最优二叉树如图三所示权为 1 3+2 3+2 2+3 2+4 2=275.求(PV Q)t R的析取范式与合取范式.(PV Q) R ( PV Q)V R(PA Q)V R (析取范式)(PV R)A ( Q V R)(合取范式)6.设 A=0 , 1, 2,
19、3, R=|x A, y A 且 x+y0 , S=|x A, y A 且 x+y 2，试求 R, S, R?S, S -1, r(R).R= , S=v0,0,v0,1,v0,2,v1,0,v1,1,R?S=,S -1= S,r(R)=|A=v0,0,v1,1,v2,2,v3,3.7.试求出(PV Q) R的析取范式，合取范式，主合取范式.(P V Q) R n (PV Q)V R (n PAn Q)V R (析取范式)(n PV R) A (n Q V R)(合取范式)(n PV R)V (Q An Q)A (n Q V R)V (P An P)(n PV RV Q) A (n PV RV
20、n Q) A (n QV RV P)A (n Q V RVn P)(n PV QV R) A (n PVn QV R) A (P Vn QV R)8设 A= a, b, 1,2 , B= a, b, 1, 1,试计算(1)( A B) (2)( AU B) (3)( AU B) (A Q B).(1)( A B) =a, b, 2(2)( A U B) = a, b, 1,2, a, b, 1(3) ( A U B) (AQ B) = a, b, 2, a, b, 19图 G=,其中 V= a, b, c, d, e , E= (a, b), (a, c), (a, e), (b, d), (
21、b, e), (c, e), (c, d), (d, e) ，对应边的权值依次为 2、1、2、3、6、1、4 及 5，试(1)画出G的图形；(2)写岀G的邻接矩阵；(3)求出G权最小的生成树及其权值.(1) G的图形表示为：(2)邻接矩阵：0110110011100110110111110(3)粗线表示最小的【生成树，权为7 :10设谓词公式 x(P(x, y) zQ(y,x, z) yR(y,z) F(y)，试(1)写出量词的辖域； (2)指出该公式的自由变元和约束变元.(1) x量词的辖域为(P(x, y) zQ(y,x,z),z量词的辖域为Q(y, x, z),y量词的辖域为R(y, z
22、).(2)自由变元为(P(x, y) zQ(y,x,z)与F(y)中的y,以及R(y,z)中的z约束变元为x与Q( y, X, z)中的Z,以及R( y, z)中的y.11.设 A=1,2,1,2 , B=1,2,1,2，试计算(1)( A B)； ( 2)( AH B)； (3) AX B.(1) A B =1,2(2) AH B =1,2(3) AXB=v1,1 , , , , ,v2,1,2 , , , , , ,12 .设 G=vV , E , V= V1 , V2 , V3 , V4 , V5 , E=(V1,V3), (V2, V3) ,(V2,V4),(V3,V4),(V3,V5
23、),(V4,V5)，试(1)给岀G的图形表示； (2)写岀其邻接矩阵；(3)求出每个结点的度数； (4)画出其补图的图形.(1)G的图形表示为:(2)邻接矩阵：0010000110110110110100110(3)V1 , V2 , V3 , V4 , V5 结点的度数依次为 1 , 2 , 4 , 3 , 2(4)补图如下：13.设集合 A=1 , 2 , 3 , 4, R=|x, y A; |x y|=1 或 x y=0，试(1)写岀R的有序对表示；(2)画出R的关系图；(3)说明R满足自反性，不满足传递性.(1) R=v1,1,v2,2,v3,3,v4,4,v1,2,v2,1,v2,3
24、,v3,2,v3,4,(2 )关系图为R中，故R在A上是自反的3)因为1,1,2,2,3,3,4,4均属于R，即A的每个元素构成的有序对均在因有2,3与3,4属于R,但2,4不属于R,所以R在A上不是传递的14.求P Q R的析取范式，合取范式、主析取范式，主合取范式.Pt( RV Q)n PV (RV Q)n PV QV R (析取、合取、主合取范式)(n PAn Q An R) V (n PAn Q A R) V( n PA Q A R) V(PAn Q An R)V (PAn Q A R) V (P A Q An R) V (PA Q A R)(主析取范式)15.设图 G=V，E，V=
25、VI，v2，v3，v4，v5，E= ( v1, v2)，(v1, v3)，(v2, v3)，(v2, V4)，(v3, v4)，(v3, v5)，(v4, v5) ，试(1)画出G的图形表示；(2)写岀其邻接矩阵；(3)求出每个结点的度数；(4)画出图G的补图的图形.(1)关系图0 110 0(2 )邻接矩阵10110110110110100110(3)deg(V1)=2 deg(V2)=3 deg(V3)=4 deg(v4)=3 deg(v5)=2(4)补图16.设谓词公式 x(A(x,y) A zB(x,y, z) A yC(y,z)试(1)写岀量词的辖域x 量词的辖域为(A(x,y) A
26、 zB(x,y, z),(2)指出该公式的自由变元和约束变元 .z量词的辖域为B(x,y,z), y量词的辖域为C(y,z)自由变元为(A(x,y) A zB(x,y, z)中的y,以及C(y,z)中的z.约束变元为(A(x,y) A zB(x,y, z)中的x与B(x,y,z)中的乙以及C(y,z)中的y。六、证明题1.试证明：若 R与S是集合A上的自反关系，则 RQS也是集合A上的自反关系.证明：设 x A,因为R自反，所以x R x，即 x, x R;又因为S自反，所以x R x，即 x, x S.即 x, x Rn S故Rn 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 或 xC . 也即x A B且x A C，即x
