离散数学自学考试复习题

离散数学自学考试复习题课程代码：02324一、单项选择题1．下列命题公式为重言式的是（）A．p→(p∨q)B．(p∨┐p)→qC．q∧┐qD．p→┐q2．下列语句中不是命题的只有（）．．A．这个语句是假的。B．1+1=1.0C．飞碟来自地球外的星球。D．凡石头都可练成金。3．下列等价式正确的是（）A．┐(x)A(x)┐AxyAB．()()xyA()()C．┐(x)A(x)┐AD．()(()xAxB(x))(x)A(x)(x)B(x)4．在公式(x)(y)(P(x,y)Q(z))(y)P(y,z)中变元y是（）A．自由变元B．约束变元C．既是自由变元，又是约束变元D．既不是自由变元，又不是约束变元5．设A={1，2，3}，A上二元关系S={<1，1>，<1，2>，<3，2>，<3，3>}，则S是（）A．自反关系B．反自反关系C．对称关系D．传递关系6．设集合X为人的全体，在X上定义关系R、S为R={<a，b|a，b∈X∧a是b的父亲}，S={<a，b>|a，b∈X∧a是b的母亲}，那么关系{<a，b>|a，b∈x∧a是b的祖母}的表达式为（）A．RSB．R-1SC．SRD．RS-17．设A是正整数集，R={(x，y)|x，y∈A∧x+3y=12}，则R∩({2，3，4，6}×{2，3，4，6})=（）A．O/B．{<3，3>}C．{<3，3>，<6，2>}D．{<3，3>，<6，2>，<9，1>}

8．下列命题正确的是（）C．{1，2}{{1}，{2}，{1，2}}D．{1，2}∈{1，2，{2}，{l，2，3}}9．在下列代数系统中，不是环的只有（）A．<Z，+，*)，其中Z为整数集，+，*分别为整数加法和乘法。B．(Q，+，*)，其中Q为有理数集，+，*分别为有理数加法和乘法。C．<R，+，*>，其中R为实数集，+为实数加法，a*b=a+2b。D．<M(R)，+，*>，其中M(R)为实数集n×n阶矩阵结合，+，*是矩阵加法和乘法。nn10．下列整数集对于整除关系都构成偏序集，而能构成格的是（）B．{1，2，3，6，12}D．{l，2，3，7}A．{l，2，3，4，5}C．{2，3，7}11．结点数为奇数且所有结点的度数也为奇数的连通图必定是（）A．欧拉图B．汉密尔顿图C．非平面图D．不存在的12．无向图G是欧拉图当且仅当G是连通的且（）A．G中各顶点的度数均相等B．G中各顶点的度数之和为偶数C．G中各顶点的度数均为偶数D．G中各顶点的度数均为奇数13．平面图(如下)的三个面的次数分别是（）A．11，3，4C．12，3，6B．11，3，5D．10，4，314．下列语句中不是命题的只有（）．A．鸡毛也能飞上天？C．不经一事，不B．或重于泰山，或轻于鸿毛。D．牙好，胃口就好。长一智。15．从真值角度看，命题公式的全部类型是（）A．永真式B．永假式C．永真式，永假式D．永真式，永假式，可满足式16．下列公式是前束范式的是（）A．(x)(y)(F(z,x)G(y))B．((x)F(x)(y)G(y))H(z)C．(x)F(x,y)(y)G(y)D．(x)(F(x,y)(y)G(x,y))C．(x)P(x,y)Q(y,z)B．A－（B∪C）=（A－B）∪D．~（A∩B）AC．~（A－B）=~（B－A）19．下列集合对所给的运算是封闭的只有（）A．非零整数集合Z上的除法运算*B．全体n×n实可逆矩阵集合M（R）上的矩阵加法和乘法运算nC．全体n×n实矩阵集合M（R）上的矩阵加法和乘法运算nA．<A，○+>是交换群B．<A，*>是半群D．○+对*是可分配的23．设连通平面图Ｇ，共有n个结点，e条边，r个面，则欧拉证明成立的公式是（）A．e-n+r=2B．n+r-e=2D．n-e-r=2C．n-r+e=21．所谓____是指不能再分解的命题，而复合命题是由一些____经过联结词复合而成的命题。(x)(y)(A(x)B(y))(x)A(x)(y)B(y)3．使公式成立的条件是____中不含y，____中不含x。4．设A={1，2，3，4}，R是A上的二元关系，R={<x,y>|x/y是素数}，则domR=_____;RanR=____。5．设X={1，3，5，9，15，45}，R是X上的整除关系，则R是X上的偏序，其最大元是___，极小元是____。L,,,0,16．设<>是有界格，a,bL,若ab=0,则a=b=_____；若ab=1,则a=b=____。7．设G上的幺元，若aG且a2=e,则a-1=____,a-2=__________。8．代数系统<A,。>，其中A为命题公式集合，。为析取运算，则元是____。e是群<A，。>中零元素是____，幺9．树是不包含_____的___图。10．在命题演算中，五个联结词的含义是由其____________表唯一确定的，而不是由其类似的____________语言的含义确定。11．设A={0，1，2，3，6}，R={〈x,y〉|x≠y∧(x,y∈A)∧y≡x(mod3)}，则domR=____________，ranR=____________。12．称集合S是给定非空集合A的覆盖：若S={S1，S2，…，S}，其中SA，Si≠Ø，i=1，ni2，…，n，且____________；进一13．对实数的____________是加法的步若____________，则S是集合A的划分。普通加法和乘法，幂等元，____________是乘法的幂等元。14．设〈A，≤〉是偏序集，若A中____________都有最小上界和____________则称A关于偏序≤构成格。15．若一条路中，所有边均不相同，则此路称作____________；若一条路中所有的结点均不相同，则称此路为____________。16.求一个公式的主析取或主合取范式的方法，有______________法和______________法。17．给定A，其中一的x称为______________，而称B为相应量词的18．设X，U，V，Y都是f：X→U，且f(x)=ex；后面所跟x谓词合式公式部分公式形式为()B(x)或(x)B(x)，则量词，______________。实数集，f：U→V，且f(u)＝u(1+u)；f3：V1l222→Y，且f(v)=cosv。那么f3ff1的定义域是______________，而复合函数(f3ff1)(x)=32______________。19．集合X={a，b，c，d}上二元关系R={<a，b>，<a，c>，<a，d>，<b，c>，<b，d>，<c，d>}，则R的自反闭包r(R)=______________，对称闭包s(R)=______________。1，是数的乘法)是群，则20．已知G=<{l，-1，i，-i}，·>(其中-l的阶是______________；i的阶是______________。i=21．对代数系统<S，*>，其中a，b∈S，且对任意的x∈S，都有a*x=x*a=x，*是S上的二元运算，若b*x=x*b=b，则称a为运算“*”的______________，称b为运算“*”的______________。23．写出如右有向图的一条初级回路：______________，其长度是______________。1．构造命题公式(p→(q∧r))→┐p的真值表。(v3,v1),(v4,v1)｝3．设A＝｛2，3，4，6，8，12，24｝，R为A上整除关系，试画<A，R>的哈斯图，并求A中4．如果论域是集合{a,b,c}，试消去下面公式中的量词：(x)(y)(xy0)6.个体域为{1，2}，求xy（x+y=4）的真值。四、证明题1.设R是集合X上的二元关系，证明R是X上传递关系当且仅当RRR。PQQRR,,,(PS)S。2.理方法证明：.3已知R和S是非空集合A上的等价关系，试证：1）R∩S是A上的等价关系；2）对a∈A，[a]R=[a]∩[a]。S∩SR4.叙述并证明苏格拉底三段论。五、应用题1．设I是整数集，<，>，＝，≤，≥，≠是Ｉ上的二元关系，分别表示小于，大于、等于、小于等于，大于等于，不等于，那么这些关系会满足什么性质？试填写下表自反反自反对称反对称传递<>=≤≥≠≤∩≥≤∪≥2.75个儿