离散数学自学考试复习题

离散数学自学考试复习题课程代码：02324一、单项选择题)B.(pV-|p)fqD-p)B.(pV-|p)fqD-p「q)B.1+1=1.0D.凡石头都可练成金A.pf(pVq)qA-|q.下列语句中不举命题的只有(A.这个语句是假的。C.飞碟来自地球外的星球。.下列等价式正确的是( )-|(3x)A<^>(3x)-|A(V%)(Vy)Ao0x)(Vy)A-|(Vx)Ao(3x)-|AD.(Vx)(A(x)aB(x))o(Vx)A(x)v(Vx)B(x).在公式0%)(Vy)(尸(羽y)aQ(z))-0y)?(y,z)中变元y是( )A.自由变元B.约束变元C.既是自由变元，又是约束变元D.既不是自由变元，又不是约束变元.设八={1,2,3},A上二元关系S={<1,1>,<1,2>,<3,2>,<3,3>},则$是( )A.自反关系 B.反自反关系C.对称关系 D.传递关系.设集合X为人的全体，在X上定义关系R、$为!?={<@,b|a,b£X/\a是b的父亲},S={<a,b>[a,b£X/\a是b的母亲}，那么关系{<a,b>[a,b£x/\a是b的祖母}的表达式为( )A.RoS B.R-i°SC.S°R D.RoSi.设A是正整数集，R={(x,y)|x,yGAAx+3y=12},则RA({2,3,4,6}X{2,3,4,6})=A.0B.{<3,3>}C.{<3, 3>,<6,2>}D.{<3,3>,<6,2>,<9,A.0B.{<3,3>}C.{<3, 3>,<6,2>}D.{<3,3>,<6,2>,<9,1>}.下列命题正确的是（{1,2}与{{1, 2},{1, 2, 3},1}{1,2}屋{1, {1,2}, {1, 2,3}, 2}{1,2}口{1},{2},{1,2}}{1,2}G{1,2,{2},{1,2,3}}.在下列代数系统中，不是环的只有( )<Z,+,*）,其中Z为整数集，+,*分别为整数加法和乘法。（Q,+,*）,其中Q为有理数集，+,*分别为有理数加法和乘法。C.<R,+,*>，其中R为实数集，+为实数加法，a*b=a+2b。<Mn（R）,+,*>，其中Mn（R）为实数集nXn阶矩阵结合，+,*是矩阵加法和乘法。TOC\o"1-5"\h\z.下列整数集对于整除关系都构成偏序集，而能构成格的是（ ）A. {1, 2,3, 4,5} B. {1, 2,3,6, 12}C. {2, 3,7} D. {1, 2,3,7}.结点数为奇数且所有结点的度数也为奇数的连通图必定是（ ）A.欧拉图BA.欧拉图D.不存在的CD.不存在的.无向图G是欧拉图当且仅当G是连通的且（ ）G中各顶点的度数均相等G中各顶点的度数之和为偶数G中各顶点的度数均为偶数G中各顶点的度数均为奇数.平面图（如下）的三个面的次数分别是（ ）B.11,3,5D.B.11,3,5D.10,4,3C.12,3,6.下列语句中不是命题的只有（ ）.A.鸡毛也能飞上天？CA.鸡毛也能飞上天？C.不经一事，不长一智。D.牙好，胃口就好。.从真值角度看，命题公式的全部类型是（ ）A.永真式B.永假式A.永真式B.永假式C.永真式，永假式D.永真式，永假式，可满足式.下列公式是前束范式的是（(V(Vx)(Vy)(「F(z,x)vG(y))(「0x)F(x)v(Vy)G(y))△H(z)(3(3x)F(x,y)T(Vy)G(y)(Vx)(F(x,y)T(Vy)G(x,y)).下列是谓词演算中的合式公式的是( )A.A.(Vx)(p(x)T3y)C.(Vx)P(x,y)Q(y,z)18.下列式子正确的是( )(A-B)-C=A-(BUC)C.~(A-B)=~(B-A)(3x)F(x)△G(x,y)D.(Vx)「x△P(x,y)B.A-(BUC)=(A-B)UCD.~(AAB)与A19.下列集合对所给的运算是封闭的只有( )A.非零整数集合Z*上的除法运算B.全体nXn实可逆矩阵集合Mn(R)上的矩阵加法和乘法运算C.全体nXn实矩阵集合Mn(R)上的矩阵加法和乘法运算D.A={1,2,…，10},x*y=LCM(x,y),即x,y最小公倍数.设＜A,㊉，*＞是环，则下列说法不正确的是( ).＜A,㊉＜A,㊉＞是交换群C.*对㊉是可分配的＜A,*＞是半群D.㊉对*是可分配的.下列各图是无向完全图的是( )23.设连通平面图G,共有n个结点，e条边，r个面，则欧拉证明成立的公式是( )A.e-n+r=2 B.n+r-e=2C.n-r+e=2 D.n-e-r=2二、填空题.所谓—是指不能再分解的命题，而复合命题是由一些—经过联结词复合而成的命题。.在命题演算中，两个的合取、析取、条件、双条件均为。.使公式(3x)(3y)(A(x)△B(y))o(3x)A(x)△(3y)B(y)成立的条件是中不含y,中不含X。.设A={1,2,3,4},R是A上的二元关系，R={<x,y>lx/y是素数}，则domR=;RanR=。.设X={1,3,5,9,15,45},R是X上的整除关系，则R是X上的偏序，其最大元是,极小元是一。.设<L',^,0,1>是有界格，a,bwL,若avb=0,则a=b=；若aab=1,则a=b=。.设e是群G上的幺元，若awG且a2=e，则a-1=—,a-2=。.代数系统<A,。>，其中A为命题公式集合，。为析取运算v，则<A,。>中零元素是—，幺元是。.树是不包含的图。.在命题演算中，五个联结词的含义是由其 表唯一确定的，而不是由其类似的语言的含义确定。.设A={0,1,2,3,6},R={〈x,y〉|xWyA(x,y£A)Ay三x(mod3)},则UdomR=,ranR=。.称集合S是给定非空集合A的覆盖：若S={S1,S2,…，Sn},其中Si旦A,SiW0,i=1,2,…，n,且 ；进一步若，则S是集合A的划分。.对实数的普通加法和乘法，是加法的幕等元，是乘法的幕等元。.设〈A,W〉是偏序集，若A中都有最小上界和则称A关于偏序W构成格。.若一条路中，所有边均不相同，则此路称作；若一条路中所有的结点均不相同，则称此路为。.求一个公式的主析取或主合取范式的方法，有法和法。.给定谓词合式公式A,其中一部分公式形式为(Vx汨仪)或(3x)B(x),则量词V,3后面所跟的x称为，而称B为相应量词的。.设X, U, V, Y都是实数集，耳 X-U,且fl(x)=ex； f2： U-V,且f2(u)=u(1+u)； f3： V一Y,且f3(v)=cosv。那么f3。f2。f1的定义域是，而复合函数(f3。f2。f1)(x)=.集合X={a,b,c,d}上二元关系R={<a,b>,<a,c>,<a,d>,<b,c>,<b,d>,<c,d>},则R的自反闭包r(R)=，对称闭包s(R)=。.已知G=<{l,-1,i,-i},•>(其中i=i匚i，是数的乘法)是群，则-l的阶是；i的阶是。.对代数系统<S,*>,其中*是S上的二元运算，若a,bGS,且对任意的xGS,都有a*x=x*a=x,b*x=x*b=b,则称a为运算“*”的，称b为运算“*”的。.设＜S,*＞是群，则＜S,*＞满足结合律和；若1 Y]SI＞l,S中不可能有。 /\\.写出如右有向图的一条初级回路：，其长度是 O.一个 且 的无向图称为树。.在简单无向图G=＜V,E＞中，如果V中的每个结点都与其余的所有结点邻接，则该图称为，如果V有n个结点，那么它还是度正则图。三、计算题.构造命题公式(p-(qAr))—[p的真值表。.求图G=＜V,E＞的可达矩阵，其中V={VI,v2,v3,v4},E={(v1,v2),(v2,v3),(v2,v4),(v3,v2),(v3,v4),(v3,v1),(v4,v1)}.设A={2,3,4,6,8,12,24},R为A上整除关系，试画＜A,R＞的哈斯图，并求A中的最大元，最小元，极大元，极小元。.如果论域是集合{a,b,c},试消去下面公式中的量词：(Vx)(3y)(x+y=0).已知集合A和B且|A|=n,|B|=m,求A到B的二元关系数是多少？A到B的函数数是多少？.个体域为{1,2},求x3y(x+y=4)的真值。四、证明题.设R是集合X上的二元关系，证明R是X上传递关系当且仅当RR旦Ro.用推理方法证明：PTQ,「QvR,「R,」(「P△S)1-「So.已知R和S是非空集合A上的等价关系，试证：1)RAS是A上的等价关系；2)对a£A,[a]Rns=[a]RP[a]So.叙述并证明苏格拉底三段论。五、应用题.设I是整数集，＜,＞,=,W,〉，W是I上的二元关系，分别表示小于，大于、等于、小于等于，大于等于，不等于，那么这些关系会满足什么性质？试填写下表自反反自反对称反对称传递<>=W^