离散数学2019年4月考试真题(02324)

某开发区有新建的5个工厂,相互之间的距离由下列矩阵表示(单位为千米),

现要架设供电线路。请找出最短的供电线路铺设方案,并算出该方案的线路长度。

对任意集合A、B、C,推导出下列集合等式成立的充要条件(1)(A-B)∪(A-C)=A(2)(A-B)∪(A-C)=?

设在实数集R上有运算*，定义为a、b∈R，a*b=a+b+2ab，证明是群，并求出其单位元和R中任意元素a的逆元。

证明下列谓词公式为永真式(xF(x)yG(y))→(yG(y)→xF(x))

如题30图所示有向图D，求其长度为4的通路总数,并指出其中国路有几条?

R为实数集，x、y∈R，证明x+y=max(x，y)+min(x，y)

N为自然数集合,设f：N×N→N，f()=x+y+1。

 (1)说明f是否为单射、满射、双射;

 (2)令A={|x，y∈N且f()=3}，求A。

求命题公式(P∨(￢P→Q))∧(Q→R)的主析取范式。

根据关系的性质，填写下表(具备该项性质填写“√”，不具备该项性质填写”x”)

用列真值表的方法说明下列逻辑等价式成立(P∨Q→R)(P→R)∧(Q→R)

谓词公式的辖域是_______，自由变元是_______。

对7阶无向简单图G，其最多有_______条边。

下图给出了一个格L,那么e的补元是_______，全上界是_______。

对集合A上的恒等关系I_A和全域关系E_A，如果|A|=n,那么|I_A|=_______，|E_A|=_______。

一颗7阶树,其分支结点最多有_______个,最多有_______片树叶。

设集合={1，2，3，4，5，6，7，8，9，10}，二元关系R={|x，y∈A，x是y的因子，x<5}，则dom R=_______，ran R=_______。

谓词公式的前束范式为_______。

设集合A={1，2，3，4，5，6}，集合B={x|x=n²+1，n∈N，x<20}，则A∪B_______。

在实数域中，命题公式的真值为_______，命题公式的真值为_______。

下面的9阶无向图，需要添加边使其成为欧拉图，至少需要添加_______和_______。

下列5阶图中为哈密顿图的是

• A.
• B.
• C.
• D.

一个n阶图不一定是树的为

• A.无回路的连通图
• B.无回路且有n-1条边
• C.n阶连通图
• D.有n-1条边的连通图

集合A上有两个二元关系R1与R2,r、s、t分别代表自反、对称和传递闭包，下列不成立的恒等式为

• A.r( R1∪R2) =r( R1)∪r( R2) )
• B.s(R1∪R2) =s(R1)∪s(R2)
• C.r( R1∩R2) =r( R1)∩r(R2)
• D.t(R1∪R2)=t(R1)∪t(R2)

集合A上的二元关系R和S都是自反关系,下列不是自反关系的为

• A.R-1
• B.R∩S
• C.R∪S
• D.R-S

下列关于图的命题正确的是

• A.欧拉图都是哈密顿图
• B.哈密顿图都是欧拉图
• C.4阶以上完全图都是欧拉图
• D.4阶以上完全图都是哈密顿图

设（L，≤）是一个有界格，下列叙述中，正确的是

• A.每个元素都有补元
• B.每个元素都没有补元
• C.至少有两个元素有补元
• D.最多有一个元素有补元

集合A和B，其幂集分别为P(A)和P(B)，下列关系不成立的是

• A.|P(A)|=2^|A|
• B.|P(B)|=2^|B|
• C.P(A∩B)=P(A)∩P(B)
• D.P(A∪B)=P(A)∪P(B)

包含n个命题变项的重言式包括有小项的个数为

• A.2ⁿ
• B.2n
• C.1
• D.0

设G为7阶无向简单图，下列命题中可成立的是

• A.G的每个结点的度数均为3
• B.G的每个结点的度数均为5
• C.G的每个结点的度数均为6
• D.G的每个结点的度数均为7

下列关于二元关系R的逆关系R^-1的性质，不成立的是

• A.(R^-1)^-1=R
• B.dom R^-1= ran R
• C.ran R^-1=dom R
• D.(R1UR2)^-1=Rl∩R2

下列可以作为4阶无向简单图的结点度数序列是

• A.1，2，3，4
• B.O，2，2，3
• C.1，1，2，2
• D.1，3，3，3

设G是有n个结点，m条边的连通图，要确定G的一棵生成树，必须删去C的多少条边

• A.m-n+1
• B.m-n
• C.m+n+1
• D.n-m+l

-个7阶无向简单图，其结点的最大度数为

• A.5
• B.6
• C.7
• D.8

令F(x)：x是火车，G(y)：y是汽车，H(x，y)：x比y快，则命题“说火车都比汽车快是不对的”的符号化形式为

• A.
• B.
• C.
• D.

令p：下午下雨，q：我去公园，r：家里来客人，则命题“若下午不下雨，我就去公园，除非家里来客人”的符号化形式为

• A.￢p∧q∧r
• B.￢p∧q∧￢r
• C.(￢p∧￢r)→q
• D.(￢p∧r)→q