2020年电大离散数学(本科)考试试题及答案参考资料重要知识点

精选

如果P的值为假，则┐P与P→┐Q为真，即┐P∧（P→┐Q）为真， 也即┐P∧（P→┐Q）∨P为真，

所以┐P∧（P→┐Q）∨P是永真式． （7分）

15．若偏序集的哈斯图如图一所示，则集合A的最大元为a，最小元不存在．

正确． （3分） 对于集合A的任意元素x，均有?R（或xRa），所以a是集合A中的最大元．（5分） 14．如果R1和R2是A上的自反关系，则R1∪R2是自反的．

正确． （3分） R1和R2是自反的，?x ?A， ? R1， ?R2， 则 ? R1?R2，

所以R1∪R2是自反的． （7分） 15．如图二所示的图G存在一条欧拉回路．

v1

e a v5 f v2 h d g v4 n c

b 图二

v3 正确． （3分） 因为图G为连通的，且其中每个顶点的度数为偶数． （7分） 14．设N、R分别为自然数集与实数集，f：N→R，f (x)=x+6，则f是单射．

正确． （3分）

设x1，x2为自然数且x1?x2，则有f(x1)= x1+6? x2+6= f(x2)，故f为单射． （7分） 15．设G是一个有6个结点14条边的连通图，则G为平面图．

错误． （3分） 不满足“设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．” 13．下面的推理是否正确，试予以说明．

(1) （?x）F（x）→G（x） 前提引入 (2) F（y）→G（y） US（1）．

错误． （3分） （2）应为F（y）→G（x），换名时，约束变元与自由变元不能混淆． （7分） 14．若偏序集的哈斯图如图二所示，则集合A的最大元为a，最小元不存在．

错误． （3分） 集合A的最大元不存在，a是极大元． （7分） 13．下面的推理是否正确，试予以说明．

(1) （?x）F（x）→G（x） 前提引入 (2) F（y）→G（y） US（1）．

错误． （3分） （2）应为F（y）→G（x），换名时，约束变元与自由变元不能混淆． （7分） 14．如图二所示的图G存在一条欧拉回路．

-可编辑修改-

精选

错误． （3分）

因为图G为中包含度数为奇数的结点． （7分） 13．如果图G是无向图，且其结点度数均为偶数，则图G是欧拉图．

错误． （3分） 当图G不连通时图G不为欧拉图． （7分） 14．若偏序集的哈斯图如图二所示，则集合A的最大元为a，最小元是f．

图二

错误． （3分） 集合A的最大元与最小元不存在， a是极大元，f是极小元，．

五．计算题（每小题12分，本题共36分）

16．设集合A={1，2，3，4}，R={|x, y?A；|x?y|=1或x?y=0}，试 （1）写出R的有序对表示； （2）画出R的关系图；

（3）说明R满足自反性，不满足传递性．

（1）R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>} （3分） （2）关系图为

? 2 1 ? 4 3 ? ? （6分）

（3）因为<1,1>,<2,2>,<3,3>,<4,4>均属于R，即A的每个元素构成的有序对均在R中，故R在A上是自反的。 （9分）

因有<2,3>与<3,4>属于R，但<2,4>不属于R，所以R在A上不是传递的。 17．求P?Q?R的析取范式，合取范式、主析取范式，主合取范式． P→（R∨Q） ?┐P∨(R∨Q)

? ┐P∨Q∨R （析取、合取、主合取范式） （9分） ?(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R) ∨(┐P∧Q∧R) ∨(P∧┐Q∧┐R)

∨(P∧┐Q∧R) ∨(P∧Q∧┐R) ∨(P∧Q∧R) （主析取范式） （12分）

18．设图G=，V={ v1，v2，v3，v4，v5}，E={ (v1, v2)，(v1, v3)，(v2, v3)，(v2, v4)，(v3, v4)，(v3, v5)，(v4, v5) }，试 画出G的图形表示； 写出其邻接矩阵； (3) 求出每个结点的度数； (4) 画出图G的补图的图形．

（1）关系图 v

?1

v2 ?

v3

? ? ? v5

v4

（3分） （2）邻接矩阵

-可编辑修改-

精选

?0?1??1??0??01011011011011010?0??1??1?0?? （6分）

（3）deg(v1)=2

deg(v2)=3 deg(v3)=4 deg(v4)=3

v?1 vv2 ? ? 5

deg(v5)=2 （9分）

? ?

v4 v3 （4）补图

16．设谓词公式?x(P(x,y)??zQ(y,x,z))??yR(y,z)?F(y)，试

（1）写出量词的辖域； （2）指出该公式的自由变元和约束变元．

（1）?x量词的辖域为(P(x,y)??zQ(y,x,z))， （2分）

?z量词的辖域为Q(y,x,z), （4分） ?y量词的辖域为R(y,z)． （6分） （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． （12分） 17．设A={{1},{2},1,2}，B={1,2,{1,2}}，试计算

（1）（A?B）； （2）（A∩B）； （3）A×B．

（1）A?B ={{1},{2}} （4分） （2）A∩B ={1,2} （8分） （3）A×B={<{1},1>，<{1},2>，<{1},{1,2}>，<{2},1>，<{2},2>， <{2},{1,2}>，<1,1>，<1,2>，<1, {1,2}>，<2,1>，<2,2>, <2, {1,2}>}

18．设G=，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，试 （1）给出G的图形表示； （2）写出其邻接矩阵； （3）求出每个结点的度数； （4）画出其补图的图形． 1）G的图形表示为：

（3分）

（2）邻接矩阵：

?0?0??1??0??00011011011011010?0??1??1?0?? （6分）

（3）v1，v2，v3，v4，v5结点的度数依次为1，2，4，3，2 （9分）

（4）补图如下：

16．试求出（P∨Q）→R的析取范式，合取范式，主合取范式．

（P∨Q）→R?┐(P∨Q)∨R? (┐P∧┐Q)∨R（析取范式） （3分）

? (┐P∨R)∧ (┐Q∨R)（合取范式） （6分） ? ((┐P∨R)∨(Q∧┐Q))∧ ((┐Q∨R)∨(P∧┐P)) ? (┐P∨R∨Q)∧(┐P∨R∨┐Q)∧ (┐Q∨R∨P) ∧(┐Q∨R∨┐P)

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

-可编辑修改-