离散数学试题小集

《离散数学试题小集》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、填空题(共20分)1．若A-B=A,则AÇB=.2．若关系R具有自反性，当且仅当在关系矩阵中，主对角线上元素；若关系只具有对称性，当且仅当关系矩阵是.3．设f:N→N,且令A={0,1},B={2},那么有f(A)=；f(B)=.4．A={1,2},则EA={<1,1>,<1,2>,<2,1>,<2,2>}IA={<1,1>,<2,2>}5．已知图G有10条边,4个3度顶点,其余顶点的度数均小于等于2,问G至少有多少个顶点. 二、单项选择题(选择一个正确答案的代号，填入括号中。共14分)1．下面关于集合的表示中，正确的是()．A．φ＝0B．φ∈{φ}C．φ∈φD．φ∈{

2、a，b}2．设R1，R2是集合A＝{1，2，3，4}上的两个关系，其中R1＝{(1，1)，(2，2)，(2，3)，(4，4)}，R2＝{(1，1)，(2，2)，(2，3)，(3，2)，(4，4)}，则R2是R1的()闭包．A．自反B．反对称C．对称D．以上都不是3．设半序集(A，≤)上关系只的哈斯图如下图所示，若A的子集B＝{2，3，4，5}，则元素6为B的()．A．下界B．上界C．最小上界D.最大下界4．函数f:R→R,f(x)=-x2+2x-1是()A．单射的B．双射的C．满射的D．以上都不对5.非平凡的无向树至少有()片树叶．A．1B.2C．3D．4三、计算题(共50分)

3、1．求下列公式的前束范式：1）$xF(x)®"xG(x)2）"xF(x)$ØÙyG(y)2．求Ø(p®q)ØÚr的主析取范式与主合取范式3．设偏序集如下图所示，求A的极小元、最小元、极大元、最大元.设B＝{b,c,d},求B的下界、上界、下确界、上确界.4．设f:R→R,g:R→R求f∘g,g∘f.如果f和g存在反函数,求出它们的反函数 四、证明题1)证明AÅB=AÈB-AÇB.2)证明下列等值式:Ø$x(M(x)ÙF(x))Û"x(M(x)®ØF(x))  答案一、填空题1．φ2．全为1对称矩阵3．f(A)=f({0,1})={f(0),f(1)}={0,2}f(

4、B)={f(2)}={1}4．EA={<1,1>,<1,2>,<2,1>,<2,2>}IA={<1,1>,<2,2>}5．8 二、单项选择题1．B2．C3．B4．D5．B 三、计算题1．解：1)ÛØ$xF(x)∨"xG(x)Û"xØF(x)∨"xG(x)Û"xØF(x)∨"yG(y)Û"x(ØF(x)∨"yG(y))Û"x"y(ØF(x)∨G(y))2)"xF(x)$ØÙyG(y)Û"xF(x)Ù"yØG(y)Û"x(F(x)Ù"yØG(y))Û"x"y(F(x)ØÙG(y))2．解：解(1)Ø(p®q)ØÚrÛ(pØÙq)ØÚrpØÙqÛ(pØÙq)Ù1Û(pØÙq)Ù(

5、ØrÚr)Û(pØÙqØÙr)Ú(pØÙqÙr)Ûm4Úm5ØrÛ(ØpÚp)Ù(ØqÚq)ØÙrÛ(ØpØÙqØÙr)Ú(ØpÙqØÙr)Ú(pØÙqØÙr)Ú(pÙqØÙr)Ûm0Úm2Úm4Úm6得Ø(p®q)ØÚrÛm0Úm2Úm4Úm5Úm6可记作ÛS(0,2,4,5,6)(2)Ø(p®q)ØÚrÛ(pØÚr)Ù(ØqØÚr)pØÚrÛpÚ0ØÚrÛpÚ(qØÙq)ØÚrÛ(pÚqØÚr)Ù(pØÚqØÚr)ÛM1ÙM3ØqØÚrÛ(pØÙp)ØÚqØÚrÛ(pØÚqØÚr)Ù(ØpØÚqØÚr)ÛM3ÙM7得Ø(p®q)ØÚrÛM1ÙM3ÙM7可记作ÛP(1,3,7

6、)3．解：极小元：a,b,c,g；极大元：a,f,h；没有最小元与最大元.B的下界和最大下界都不存在,上界有d和f,最小上界为d.4．解：f:R→R不存在反函数；g:R→R的反函数是g-1:R→R,g-1(x)=x-2 四、证明题1)证AÅB=(AÇ~B)È(~AÇB)=(AÈ~A)Ç(AÈB)Ç(~BÈ~A)Ç(~BÈB)=(AÈB)Ç(~BÈ~A)=(AÈB)Ç~(AÇB)=AÈB-AÇB2）证左边Û"xØ(M(x)ÙF(x))Û"x(ØM(x)ÚØF(x))Û"x(M(x)®ØF(x))离散数学试卷一．选择题1.命题公式为()(A)矛盾式(B)可满足式(C)重言式(D)合

7、取范式2.设集合A={{1,2,3},{4,5},{6,7,8}}，则下式为真的是()(A)1ÎA(B){1,2,3}ÍA(C){{4,5}}ÌA(D)ÆÎA3．设R1，R2是集合A＝{1，2，3，4}上的两个关系，其中R1＝{(1，1)，(2，2)，(2，3)，(4，4)}，R2＝{(1，1)，(2，2)，(2，3)，(3，2)，(4，4)}，则R2是R1的()闭包．A．自反B．反对称C．对称D．以上都不是4．设S1={1,2，…，8,9},S2={2,4,6,8},S3={1,3,5,7