大学离散数学试题集(非常完整试题)

第1章一.填空题1.2.公式P→(Q→R)在联结词全功能集{﹁,∨}中等值形式为___________________。3.4.5.6.7.全体小项的析取式必为____________________式。8.P,Q为两个命题，则德摩根律可表示为7.全体小项的析取式必为_________式。9.P,Q为两个命题，则吸收律可表示为____________________。10.设P：我有钱，Q：我去看电影。命题“虽然我有钱，但是我不去看电影”符号化为____________________。11.设P：我生病，Q：我去学校。命题“如果我生病，那么我不去学校”符号化为____________________。12.13.14.15.设P、Q为两个命题，交换律可表示为____________________。16.17.命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号化为____________________。18.19.20.21.P：你努力，Q：你失败。命题“除非你努力，否则你将失败”的翻译为____________________。22.23.24.一个重言式和一个矛盾式的合取是____________________。25.全体小项的析取式为____________________。26.命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号化为____________________。27.28.设P：它占据空间，Q：它有质量，R：它不断运动，S：它叫做物质。命题“占据空间的，有质量的而且不断运动的叫做物质”的符号化为____________________。29.30.二.选择题1.2.3.在除﹁之外的四大联结词中，满足结合律的有几个()。A.2B.3C.4D.14.判断下列语句哪个是命题()。A.你喜欢唱歌吗？B.若7+8＞18，则三角形有4条边。　C.前进！D.给我一杯水吧！5.6.7.8.永真式的否定是（）A.永真式　B.永假式　C.可满足式　D.A--D均有可能9.下面哪一个是假命题（）。A.如果2是偶数，那么一个公式的析取范式唯一。B.如果2是偶数，那么一个公式的析取范式不唯一。C.如果2是奇数，那么一个公式的析取范式唯一。D.如果2是奇数，那么一个公式的析取范式不唯一。10.设p:天下大雨，q:小王乘公共汽车上班，命题“只有天下大雨，小王才乘公共汽车上班”的符号化形式为()。A.p→qB.q→p　　C.p→┐qD.┐p→q11.设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为()。A.p→qB.q→pC.┐q→pD.┐p→q12.下面4个推理定律中，不正确的为()。A.A=>(A∨B)(附加律)B.(A∨B)∧┐A=>B(析取三段论)C.(A→B)∧A=>B(假言推理)D.(A→B)∧┐B=>A(拒取式)13.使命题公式p→(p∧q)为假的赋值是()。A.10B.01C.00D.1114.令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）。A.p∧┐qB．p∨┐qC.p∧qD．p→┐q15.一个公式在等价意义下，下面哪个写法是唯一的（　　）。Ａ．析取范式　　　　　　　　　　　B．合取范式Ｃ．主析取范式　　　　　　　　　　D．以上答案都不对16.令p：今天下雨了，q：我上学，则命题“因为今天下雨了，所以我不上学了”可符号化为（）。A．p→┐qB．p∨┐qC．p∧qD．p∧┐q17.下列各组公式中哪组互为对偶（）。(P为原子命题，A为复合命题)A.P,PB.P,┐PC.A,(A*)*D.A,A18.19.20.21.22.23.24.25.下列语句哪个是命题（）。A.9+5≤12B.x+3=5C.我用的计算机CPU主频是1G吗？D我正在说谎。26.27.28.n个命题变元可产生（）个互不等价的大项。A.nB.n2C.2nD.2n29.下列各命题中真值为真的命题有（）。A.2+2=4当且仅当3是奇数B.2+2=4当且仅当3不是奇数C.2+2≠4当且仅当3是奇数D.2+2≠5当且仅当3不是奇数30.下列语句哪个不是命题（）。A.雪是黑的。B.天气多好啊！C.今天下雨。D我学英语，或者我学日语。三.判断题1.“我正在说谎。”是一个命题。（）2.一个命题标识符如表示确定的命题，就称为命题常量。（）3.“她昨天做了一顿或两顿饭。”是个原子命题。（）4.命题公式是没有真假值的，仅当在一个公式中命题变元用确定的命题代入时，才得到一个命题。（）5.如果A和B是合式公式，那么(A→B)是合式公式。（）6.原子谓词公式是合式公式。（）7.一般来说，n个命题变元组成的命题公式共有2n中真值情况。（）8.任何两个重言式的合取或析取，仍然是一个重言式。（）9.重言式和矛盾式的析取是重言式。（）10.在真值表中，一个公式的真值为F的指派所对应的大项的析取，即为此公式的主析取范式。（）11.从假的命题出发，能证明任何命题。（）12.全体小项的析取式永为假。（）13.连接词↑和↓是可交换的，也是可结合的。（）14.P→Q=〉P→P∧Q。（）15.由n个命题变元组成不等值的命题公式的个数为2n。（）四.计算题1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.五.证明题1.2.3.第2章一.填空题1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.二.选择题1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.三.判断题1.“如果1+2=3，则4+5=9。”是真命题。（）2.约束变元换名时，一定要更改为作用域中没有出现的变元名称。（）3.4.简单命题函数由一个谓词和一些客体变元组成。（）5.单独一个谓词，不是完整的命题。（）6.任意一个谓词公式均和一个前束范式等价。（）7.8.9.10.11.12.13.14.15.四.计算题1.2.3.4.5.6.7.8.9.10.五.证明题1.2.3.4.第3章一.填空题1.设A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>},则A∪B=_________________。2.A，B，C表示三个集合，图中阴影部分的集合表达式为____________________。3.设A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>},则A°B=_______________。4.设A={1，2，3，4}，A上二元关系R={<1，2>，<2，1>，<2，3>，<3，4>}画出R的关系图_________________。5.设A={a，b，c，d}，其上偏序关系R的哈斯图为则R=_______________________。6.设A={1，2，3}，则A上既不是对称的又不是反对称的关系为R=____________________。7.设A={1，2，3}，则A上既是对称的又是反对称的关系为R=_____________________。8.设|A|=3，则A上有________________个二元关系。9.偏序集〈Ρ（{a,b}），⊆〉的哈斯图为________________。10.集合A={2，3，6，12，24，36}上偏序关系R的Hass图为则集合B={2，3，6，12}的上界是_________________。11.对集合X和Y，设|X|=m，|Y|=n，则从X到Y的函数有__________________个。12.关系R的自反闭包r(R)＝________________。13.关系R的对称闭包s(R)＝_________________。14.关系R的传递闭包t(R)＝_____________________。15.若R是集合A上的偏序关系，则R满足___________________。16.若R是集合A上的等价关系，则R满足____________________。17.若R是集合A上的相容关系，则R满足__________________。18.集合A={2，3，6，12，24，36}上偏序关系R的Hass图为则集合B={2，3，6，12}的上确界是_____________。19.设A，B是两集合，其中A={a，b，c}，B={a，b}，则A-B=_______________。20.设R={,,}，则ran(R)=______________。21.设R={,,}，则dom(R)=________________。22.设R={,,}，则FLD(R)=_________________。23.设A={a，b}，B＝｛1，2，3｝，则A×B=__________________。24.设R是A={1，2，3，4}上的二元关系,R={<1,1>,<1,2>,<2,3>,<3,4>},则R的对称闭包是_________________。25.设R是A={1，2，3，4}上的二元关系,R={<1,1>,<1,2>,<2,3>,<3,4>},则R的自反闭包是__________________。26.设R是A={1，2，3，4}上的二元关系,R={<1,1>,<1,2>,<2,3>,<3,4>},则R的传递闭包是____________________。27.集合A={2，3，6，12，24，36}上偏序关系R的Hass图为则集合B={2，3，6，12}的下确界是__________________。28.设A,B是集合，|A|=3，|B|=4，|A∩B|=2，那么|A∪B|=_____________。29.集合A有n个元素，则A的幂集有___________个元素。30.一个集合的非平凡子集包括___________和全集。31.集合A={2，3，6，12，24，36}上偏序关系R的Hass图为则集合B={2，3，6，12}的下界是_______________。32.集合A={∅,a}，则A的幂集P(A)=____________。33.设A,B为集合，则命题A-B=∅<=>A=B的真值为（填“真”或“假”或“不可判别”）________。34.设A={a,b,c,d}，A上的等价关系R=IA∪{(b,c),(c,b),(a,d),(d,a)}，则对应于R的A的划分是_______________。35.给定集合A＝{1,2,3,4,5},R是A上的等价关系，且此关系R能产生划分{{1,2},{3,4,5}},则R=_________________。二.选择题1.设A={1,2,3}，则A上有（）个二元关系。A.23B.32C.2^{2^3}D.2^{3^2}2.设X，Y，Z是集合，下列结论不正确的是（）。A．若X⊆Y,则X∩Y=XB．(X-Y)-Z=X-(Y∩Z)C．X⊕X=∅D．X-Y=X∩(~Y)3.设S={1,2,3,4}，R={<1,1>,<2,2>,<3,3>}，则R的性质是（）。A.自反、对称、传递的B.自反、对称、反对称的C.对称、反对称、传递的D.只有对称性4.设R和S是P上的关系，P是所有人的集合，R={|x,y∈P∧x是y的父亲}，S={|x,y∈P∧x是y的母亲}则S-1°R表示关系（）。A、{|x,y∈P∧x是y的丈夫}B、{|x,y∈P∧x是y的孙子或孙女}C、∅D、{|x,y∈P∧x是y的祖父或祖母}5.若X是Y的子集，则一定有（）。A.X不属于YB.X∈YC.X真包含于YD.X∩Y=X6.下列式子中正确的是（）。A．∅=0B．∅∈∅C．∅∈{a，b}D．∅∈{∅}7.下面那条不是偏序关系的性质：（）A.自反性B.相容性C.传递性D.反对称性8.关于闭包运算，下面那条性质不对（）A.rs(R)=sr(R)B.rt(R)=tr(R)C.st(R)=ts(R)D.rtr(R)=tr(R)9.划分必然诱导一个（）A.等价关系B.偏序关系C.同余关系D.同态关系10.设某集合有m个元素，则可以构成（）个子集。A.mB.m!C.2mD.2m-111.A,B为两个集合，如果A⊆B，则下面那个是错误的。（）A)A∩B≠∅B)~B⊆~AC)(B-A)∪A=BD)(B-A)∪A=A12.设S={1,2,3}，S上关系R的关系图为则R具有（）性质。A．自反性、对称性、传递性；B．反自反性、反对称性；C．反自反性、反对称性、传递性；D．自反性。13.设A={∅，{1}，{1，3}，{1，2，3}}则A上包含关系“⊆”的哈斯图为（）14.集合A={1，2，3，4}上的偏序关系图为则它的哈斯图为（）。15.集合A={1，2，3，4}上的偏序关系为，则它的Hass图为（）。16.设R，S是集合A上的关系，则下列（）断言是正确的。A、R,S自反的，则R°S是自反的；B、若R,S对称的，则R°S是对称的；C、若R,S传递的，则R°S是传递的；D、若R,S反对称的，则R°S是反对称的17.设X为集合，|X|=n，在X上有（）种不同的关系。A、n2；B、2n；C、2^{2^n}；D、2^{n^2}。18.下图描述的偏序集中，子集{b,e,f}的上界为（）。A、b,c；B、a,b；C、b；D、a,b,c。19.设R，S是集合A上的关系，则下列说法正确的是（）。A．若R，S是自反的，则R°S是自反的；B．若R，S是反自反的，则R°S是反自反的；C．若R，S是对称的，则R°S是对称的；D．若R，S是传递的，则R°S是传递的。20.设R是集合A上的二元关系，IA是A上的恒等关系，IA⊆R下面四个命题为真的是()。A.R是自反的B.R是传递的C.R是对称的D.R是反对称的21.已知A,B是集合│A│=15，│B│=10，│A∪B│=20，则│A∩B│=（）A．10B．5C．20D．1322.设X，Y，Z是集合，下列结论不正确的是（）。A．若X⊆Y,则X∩Y=XB．(X-Y)-Z=X-(Y∩Z)C．X⊕X=∅D．X-Y=X∩(~Y)23.设A={a,b,c,d}，A上的等价关系R={,,,}∪IA，则对应于R的A的划分是（）。A．{{a},{b,c},{d}}　　B．{{a,b},{c},{d}}C．{{a},{b},{c},{d}}　　D．{{a,b},{c,d}}24.设R是集合A上的二元关系，IA是A上的恒等关系，IA⊆R下面四个命题为真的是()A.R是自反的B.R是传递的C.R是对称的D.R是反对称的25.集合A={1，2，3，4}，则对A的元素进行划分正确的是（）A.{,{1,2},{3,4}}B.{{1,2,3},{3,4}}C.{{1},{3,4}}D.{{1,2,3,4}}26.设集合A={2,{a},3,4}，B={{a},3,4,1}，E为全集，则下列命题正确的是()。(A){2}∈A(B){a}⊆A(C)∅⊆{{a}}⊆B⊆E(D){{a},1,3,4}⊂B27.设集合A={1,2,3},A上的关系R＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，则R不具备().(A)自反性(B)传递性(C)对称性(D)反对称性28.设A,B为集合，当()时A－B＝B.(A)A＝B(B)A⊆B(C)B⊆A(D)A＝B＝∅.29.设集合A={1,2,3,4},A上的关系R＝{(1,1),(2,3),(2,4),(3,4)},则R具有()。(A)自反性(B)传递性(C)对称性(D)以上答案都不对30.下列关于集合的表示中正确的为()。(A){a}∈{a,b,c}(B){a}⊆{a,b,c}(C)∅∈{a,b,c}(D){a,b}∈{a,b,c}31.设R和S是集合A上的关系，若R和S是传递的，则（）(A)R∩S是传递的；(B)R∪S是传递的；(C)R°S是传递的；(D)以上都不对。32.设集合X为人的全体，在X上定义关系R、S为R={|a，b∈X∧a是b的父亲}，S={|a，b∈X∧a是b的母亲|，那么关系{|a，b∈X∧a是b的祖母}的表达式为()(A)R°S(B)R-1°S(C)S°R(D)R°S-133.下列命题正确的是()(A){1,2}⊆{{1,2},{1,2,3},1}(B){1,2}⊆{1,{1,2},{1,2,3},2}(C){1,2}⊆{{1},{2},{1,2}}(D){1,2}∈{1,2,{2},{1,2,3}}34.下列关系矩阵所对应的关系具有反自反性的是（）35.设R1和R2是集合A上的相容关系，下列关于R1⊕R2的说法正确的是（）(A)一定是相容关系；(B)一定不是相容关系；(C)可能是也可能不是相容关系；(D)一定是等价关系。三.判断题1.设集合A={a,b,c,d,e,f}，那么S1={∅,{a,b},{c,d},{f}}是集合A的一个覆盖。()2.恒等关系既是等价关系又是偏序关系。()3.设F,R都是二元关系,则(F°R)-1=F-1°R-1。()4.设A,B,C是三集合，已知A∪B＝A∪C，则一定有B＝C。()5.设集合A={a,b,c,d,e,f}，那么S1={{a,b},{c,d,e},{e,f}}是集合A的划分。()6.集合A上的等价关系确定了A的一个划分。()7.集合A上的偏序关系的三个性质是反自反性、对称性和传递性。()8.三种重要的二元关系是等价关系、偏序关系和函数关系，它们的共同特点是都具有自反性。()9.R的自反传递闭包也一定满足自反关系，传递关系。()10.偏序集合中，链上的任何两个元素都是有关系的。()11.设R是实数集，R上的关系f={||x-y|<2,x,y∈R}，R是相容关系。()12.空集是任何集合的真子集。()13.设集合A、B、C为任意集合，若A×B=A×C，则B=C。()14.若集合A上的关系R是对称的，则R-1也是对称的。15.空集是唯一的。()16.全集不是唯一的。()17.对于一个给定的集合，其划分是唯一的。（）18.设R为X上的二元关系，则R是对称的<=>R=Rc。（）19.设R为X上的二元关系，则R是反对称的<=>R∩Rc⊆IX。（）20.设R为X上的二元关系，则R是传递的<=>(R°R)⊆R。（）四.计算题1.设S={1,2,3,4,6,8,12,24}，“≤”为S上整除关系，问：（1）偏序集的Hass图如何？（2）偏序集的极小元、最小元、极大元、最大元是什么?2.A={a，b，c，d}，R={,,},R是集合A上的二元关系。（1）画出的R的关系图；（2）求R的自反闭包和对称闭包。3.在实数平面上，画出关系R={|x-y+2>0∧x-y-2<0}，并判定关系的特殊性质。4.R1={<1,2>,<1,3>,<2,3>,<3,3>},R2={<2,2>,<2,3>,<3,4>},(1)求R1-1(2)求R2°R15.设集合A＝{a,b,c,d}上的关系R＝{,,,}，写出它的关系矩阵和关系图，并用矩阵运算方法求出R的传递闭包。6.设R是自然数集合N上的关系，且xRy<=>x+2y=10。(1)求domR；(2)说明R具有的性质(自反、反自反、对称、反对称、传递)。7.设为一个偏序集，其中A={1，2，3，4，6，9，24，54},R是A上的整除关系。（1）画出R的哈斯图；（2）求A的极大元和极小元；（3）求B={4,6}的上确界和下确界8.集合S={1，2，3，4，5}，找出S上的等价关系，此关系能产生划分{{1，2}，{3}，{4，5}}，并画出关系图。9.集合上的关系R={<1,1>,<1,3>,<2,2>,<3,3>,<3,1>,<3,4>,<4,3>,<4,4>},写出关系矩阵，画出关系图并讨论R的性质。10.下图是偏序集的哈斯图，（1）写出集合A,R;（2）求A的极大元和极小元；（3）求B={e,f}的上确界和下确界。11.设A={1,3,5,7}，定义A上的二元关系R:∈R<=>a,,,},R2={,,},求：(1)R1-1(2)R2°R113.R1={<1,2>,<1,3>,<2,3>,<3,3>},R2={<2,2>,<2,3>,<3,4>}求：(1)R1-1(2)R1·R2(3)R1214.设A是正整数m=20的因子的集合，并设≤为整除关系。画出A上的偏序集合图(哈斯图)，并指出A中的极大元和极小元，最大元和最小元。五.证明题1.令I是整数集合，I上关系R定义为：R＝{|x-y可被3整除}，求证R是自反、对称和传递的。2.设A、B、C是任意集合，证明：A-(B∪C)=(A-B)∩(A-C)3.如果集合A上的关系R和S是反自反的、对称的和传递的，证明：是A上的等价关系。4.集合A的任一划分S诱导了A的一个等价关系R。5.A,B为两个任意集合，求证：A－(A∩B)=(A∪B)－B.6.试证明实数集R上的小于等于关系“≤”是偏序关系。7.设R,S为二元关系,试证明(R°S)c=Sc°Rc.8.设A、B、C为任意三个集合，证明A×(B∪C)=(A×B)∪(A×C)。第4章一.填空题1.设f是集合X到集合Y的一个关系，如果对∀x∈X，有唯一的y∈Y使得∈f，则称关系f为X到Y的__________。2.设X，U，V，Y都是实数集，f1:X->U，且f1(x)=ex；f2:U->V，且f2(u)=u(1+u)；f3:V->Y，且f3(v)=cosv。那么f3°f2°f1的定义域是______________。3.设X，U，V，Y都是实数集，f1:X->U，且f1(x)=ex；f2:U->V，且f2(u)=u(1+u)；f3:V->Y，且f3(v)=cosv。那么f3°f2°f1(x)=______________。4.F={,,}______（“是”或者“不是”）函数。5.F={,}_______（“是”或者“不是”）函数。6.设f，g是自然数集N上的函数，∀x∈N，f(x)=x+1，g(x)=2x，则f°g(x)＝_______。7.设函数f:X→Y,如果对X中的任意两个不同的x1和x2，它们的象y1和y2也不同，我们说f是______函数。8.设函数f:A→B,则f的逆关系是函数当且仅当f是________（“入射”或“满射”或“双射”）。9.若函数f:A→B存在逆函数f-1,则f-1°f=_________。10.若函数f:A→B存在逆函数f-1,则f°f-1=_________。11.如果IA=_______，则称IA：A→A为集合X上的恒等函数。12.函数f:I->I,f(j)=j(mod3)______（“是”或者“不是”）入射函数。13.函数_____（“是”或者“不是”）满射函数。14.函数f:I->I,f(j)=j(mod3)_______(“是”或者“不是”)双射函数。15.函数f:I->N,f(i)=|2i|+1_______（“是”或者“不是”）入射函数。16.函数________（“是”或者“不是”）满射函数。17.函数f:I->I,f(j)=j(mod3)______（“是”或者“不是”）双射函数。18.函数f:R->R,f(r)=2r-15_____（“是”或者“不是”）入射函数。19.函数f:I->I,f(j)=j(mod3)_______（“是”或者“不是”）满射函数。20.函数f:I->I,f(j)=j(mod3)_______（“是”或者“不是”）双射函数。二.选择题1.设集合A，B是有穷集合，且|A|=m，|B|=n，则从A到B有（）个不同的双射函数。A、n；B、m；C、n!；D、m!。2.下列命题正确的有（）。A、若g,f是满射，则g°f是满射；B、若g°f是满射，则g,f都是满射；C、若g°f是单射，则g,f都是单射；D、若g°f是双射，则f是双射。3.设f，g是函数，当（）时，f=g。A、∀x∈domf都有f(x)=g(x)；B、domg⊆domf且f⊆g；C、f与g的表达式相同；D、domg=domf,rangef=rangef4.N是自然数集，定义f:N->N,f(x)=(x)mod3（即x除以3的余数），则f是（）。A、满射不是单射；B、单射不是满射；C、双射；D、不是单射也不是满射。5.下列关系中能构成函数的是（）。A、{|(x,y∈N)∧(x+y<10)}；B、{|(x,y∈R)∧(y=x2)}；C、{|(x,y∈R)∧(y2=x)}；D、{|(x,y∈I)∧(x≡ymod3)}6.下面函数（）是单射而非满射。A、f：R->R，f(x)=-x2+2x-1；B、f:Z+->R，f(x)=lnx；C、f:R->Z，f(x)=[x],[x]表示不大于x的最大整数；D、f:R->R，f(x)=2x+1。7.若函数g和f的复合函数g°f是双射，则（）一定是正确的。A、g是入射；B、f是入射；C、g是双射；D、f是满射。8.X={a，b，c，d，e}，Y={1，2，3，4}，f从X到Y的映射，其中f(a)=2,f(b)=4,f(c)=1,f(d)=3,f(e)=4,则f是（　　）。A双射B满射C单射D以上都不是9.对于下面函数f的描述，那条不对（）A)f(x)的像必然唯一存在B)如果f存在逆函数，则必是满射的C)如果f是入射的，则必存在逆函数D)如果f是双射的，则必是入射的10.设函数f：N→N（N为自然数集），f(n)=n+1，下面四个命题为真的是()。A.f是单射B.f是满射C.f是双射的D.f非单射非满射三.判断题1.若X和Y的元素个数相同，即|X|=|Y|，则f:X->Y是入射的当且仅当它是一个满射。()2.设f:X->Y是满射，即对任意的y∈Y，必存在x∈X，使得f(x)=y成立。()3.一个函数必然是一个关系。()4.一个关系就是一个函数。()5.函数f:X->Y就是从集合X到集合Y的一个映射。()四.计算题1.设R是实数集合，σ,τ,φ是R上的三个映射，σ(x)=x+3,τ(x)=2x,φ(x)＝x/4,试求复合映射σ•τ，σ•σ,σ•φ,φ•τ，σ•φ•τ.2.下面有三个关系图，判断它们是函数否？如果不是，请说明原因。3.设A={1,2,3,4},B={x,y,z,w},决定下列(1)--(5)的每个关系R是不是从A到B的一个函数。如果是一个函数,找出其定义域和值域,并确定它是不是入射的或满射的。(1){<1,x>,<2,x>,<3,z>,<4,y>};(2){<1,z>,<2,x>,<3,y>,<4,z>,<2,w>};(3){<1,z>,<2,w>,<3,x>,<4,y>};(4){<1,w>,<2,w>,<4,x>}(5){<1,y>,<2,y>,<3,y>,<4,y>}。4.设集合A={1,2,3},f、g是集合A到A的函数，f={<1,2>,<2,3>,<3,1>}，g={<1,2>,<2,1>,<3,3>},计算f°g，g°f。5.设集合A={1,2,3},B={a,b},f:A->B,且f={<1,a>,<2,b>,<3,b>}，试判断f是不是一个函数?如果是函数，是否存在逆函数？五.证明题1.令gοf是一个复合函数。若g和f是满射，则gοf是满射的。2.设f°g是复合函数，证明：如果f°g是满射的，那么f是满射的。3.设f°g是复合函数，证明：如果f°g是入射的，那么g是入射的。第5章一.填空题1.群中有唯一的（）。2.如果群运算是可交换的，则群为（）。3.设*是定义在集合A上的二元运算，如果对于A中任意的两个元素x,y，都有x*y∈A，则称二元运算*在A上是（）。4.设*是定义在集合A上的二元运算，如果对于A中任意的两个元素x,y，都有x*y=y*x，则称二元运算*在A上是（）。5.设★是定义在有理数集合Q上的二元运算，如果对于Q中任意的两个元素x,y，都有x★y=x+y-x*y，其中*表示普通乘法元算，则二元运算★在Q上是（）。（填写可交互/不可交换）6.设*是定义在集合A上的二元运算，如果对于A中任意的元素x,y,z，都有(x*y)*z=x*(y*z)，则称二元运算*在A上是（）。7.设★是定义在非空集合A上的二元运算，如果对于A中任意的两个元素x,y，都有x*y=y，则二元运算★在A上是（）。（填写可结合/不可结合）8.设*，★是定义在集合A上的两个二元运算，如果对于A中任意的元素x,y,z，都有(x*y)★z=（x★z）*(y★z)，z★(x*y)=(z★x)*(z★y),则称二元运算★对于*在A上是（）。9.设*，★是定义在集合A上的两个可交换的二元运算，如果对于A中任意的元素x,y，都有x*(x★y)=x,x★(x*y)=x,则称二元运算*对于★在A上满足（）。10.设*是定义在集合A上的二元运算，如果对于A中任意的元素x，都有x*x=x，则称二元运算*是（）。11.设*是定义在集合A上的二元运算，如果在A中存在元素el，对于A中任意的元素x，都有el*x=x，则称el为A中关于运算*的（）。12.设*是定义在集合A上的二元运算，如果在A中存在元素ol，对于A中任意的元素x，都有ol*x=x，则称ol为A中关于运算*的（）。13.设*是定义在集合A上的二元运算，如果在A中存在元素er，对于A中任意的元素x，都有x*erl=x，则称er为A中关于运算*的（）。14.设*是定义在集合A上的二元运算，如果在A中存在元素or，对于A中任意的元素x，都有x*or=x，则称or为A中关于运算*的（）。15.如果对于集合中的二元运算*，存在左零元和右零元，且左零元等于右零元，则零元是（）。16.如果对于集合中的二元运算*，存在左么元和右么元，且左么元等于右么元，则么元是（）。17.设*是定义在集合A上的二元运算，且e是A中关于运算*的么元，如果对于A中的元素x，存在A中的元素y，有y*x=e，则称y为x的（）。18.对于实数域上的乘法元算，每个元素（）逆元。（填写一定有/不一定有）19.对于实数域上的加法运算，（）零元。（填写存在/不存在）20.对于整数域上的加法运算，（）么元。（填写存在/不存在）21.对于非空集合S上二元运算*，是封闭且可结合的，那么叫做（）。22.正整数上的加法运算（）半群。（填写是/不是）23.实数域上的除法运算（）半群。（填写是/不是）24.整数域上的加法运算（）群。（填写是/不是）25..如果群的运算满足交换率，则这个群叫（）。二.选择题1.下面那个性质不是群必有的？（）A)运算的封闭性B)幺元C)零元D)运算的交换性2.设集合A={1,2,…,10},下面定义的那个二元运算*关于A不封闭？（）A)x*y=max(x,y)B)x*y=质数p的个数，使得x<=p<=yC)x*y=min(x,y)D)x*y=((x+y)mod10)+13.是一个半群，如果S是一个有限集，则必有（）A幺元B零元C等幂元D不确定4.下面那个代数系统表示的范围最大？（）A群B半群C阿贝尔群D独异点5.同构关系必然是一个（）A）等价关系B)偏序关系C)同余关系D)同态关系6.在自然数集N上，下列哪种运算是可结合的？（）A)a*b=a-bB)a*b=max{a,b}C)a*b=a+2bD)a*b=|a-b|7.同构关系必然是一个（）A．等价关系B.偏序关系C.同余关系D.相容关系8.设是群，a,b∈G,则下列结论不正确的是（）A．(a*b)-1=b-1*a-1B．a*x=b有唯一解C．a*x=a*y,则x=yD．a*b=b*a9.下面那个运算不满足运算的封闭性？（）A.自然数上的加法B.有理数上的乘法C.1到10之间的模11加法D.0到9之间的模10加法10.下面那个不满足结合律？（）A)自然数上的加法B）有理数上的乘法C）自然数上的max(a,b)D)自然数上的减法11.对于代数系统，Nk={0,1,…,k-1}，+k是定义在Nk上的模k加法，下面说法不对的是：（）A.有零元B.有么元C.每个元素都有逆元D.是半群12.下面关于半群的说法正确的是（）A.必有零元B.必有么元C.必然服从交换律D.必然服从结合律13.若果为半群，且S是有限集合，则以下说法正确的是（）A)必有a∈S,且a*a=aB)必有a∈S,且a*b=bC)必有零元D）必有零元14.关于独异点，下列说法正确的是（）A)必有零元B)必有等幂元C）必有么元D)必然满足交换律15.以下说法不正确的是（）A)群表示范围比半群小B)交换群表示范围比半群小C)阿贝尔群表示范围比群小D）广群表示的范围比半群小16.下面关于群的说法不正确的是（）A）必有零元B）必有么元C）每个必然有逆元D)必然服从结合律17.下面那个是群？（）A)自然数上的乘法B)实数域上的乘法C)0到9之间的模10加法D)0到9之间的模10乘法18.下面关于群的说法不正确的是（）A)对于任a,b∈G,存在唯一的x∈G,使得a*x=bB)对于任a,b,c∈G，若有a*b=a*c,则必有b=cC)任a∈G，必有唯一的x∈G,使得a*x=e,e为么元D)任a∈G，必有唯一的x∈G,使得a*x=x,x为零元19.下面关于群的说法正确的是（）A)没有等幂元B)有1个等幂元C)有2个等幂元D)和群的阶数有关20.设为一个群，下面关于G的子群的说法正确的是（）A)如果S是G的非空子集且*在S上是封闭的，则就是的子群B)如果S是G的非空子集且含有么元，则就是的子群C)如果S是G的非空子集，且对于任意S中的连个元素a,b都有a*b-1∈G,则就是的子群D)如果S是G的非空子集，且是半群,则就是的子群21.下列说法那个是错误的。（）A)循环群必定是阿贝尔群B)循环群必定有等幂元C)阿贝尔群必定是循环群D)循环群必定是交换群22.下列那个说法是正确的？（）A)同态一定是同构的B）同构一定是同态的C)同态一定是同余的D)同态一定是等价的23.如果f：R->R，对于任意的x∈R,f(x)=5x,则f是从到的一个（）A)单一同态B)满同态C)双射同态D)同构24.下列关于环说法不正确的是()A)是阿尔贝尔群B)是半群C)*对★可分配的D)★对*是可分配的。25..设G是非零乘法群，判断下列哪个f不是G到G的同态映射。（）A）f(x)=|x|B)f(x)=-xC)f(x)=x+1D)f(x)=1/x26.下面关于群的说法不正确的是：（）A）有么元B）有零元C）每个元素都有逆元D）满足结合律27..下面那个是群。（）A）整数域上的加法运算B）实数域上的乘法运算C）自然数域上的除法运算D）整数1到5之间的模6加法运算28..如果是一个环，下列关于环的说法错误的是（）。A）是阿贝尔群B）是阿贝尔群C）运算*对于+是可分配的D）运算+对于*是可分配的29.关于独异点说法错误的是（）。A)必有左么元B)必有右零元C)必然满足结合律D)必是含么半群30.关于阿贝尔群说法错误的是（）。A)必有左么元B)必有右零元C)必然满足交换律D)必是半群三.判断题1.半群一定是独异点。()2.代数系统中有可能有很多个左零元和右零元，它们有可能相等，也有可能不等。()4.群中的某些元素可能有多个不同的逆元。（）5.群的运算一定符合交换律。（）6.如果定义在集合A上的*运算既有左零元，又有右零元，那么必有唯一的零元。（）7.循环群必有等幂元。（）8.有等幂元的群一定是有限群。（）9.阿贝尔群运算一定符合交换律。（）10.有限群一定有么元。（）11.含有零元的半群叫独异点。（）12.在群中，出了么元外，可能还还有其他等幂元。（）13.对一个群，它的任意一个非空有限子集B,如果*在B上封闭，则一定也是群。（）14..循环群一定是阿贝尔群。（）15.同构的一定是同态的。（）16.同态可以诱导一个唯一的等价关系。（）17..f是代数系统到代数系统的同态映射，如果半群，则在f作用下，同态象也是半群。（）18.循环群中必有零元。（）19.(*表示乘法)与同构。（）20.定义在自然数集合上的模k加法是一个群。（）四.计算题1.验证二元运算在实数集上是否满足交换律和结合律？3.设G={[1],[2].[3],[4],[5],[6]},G上的二元运算如表所示。问G是循环群吗(写出验证过程)？若是，找出生成元。4.考察代数系统，以下定义在I上的二元关系R是同余关系吗？如不是，找出反例。1)∈R当且仅当（x<0∧y<0）∨(x≥0∧y≥0)2)∈R当且仅当|x-y|<105.考察代数系统，以下定义在I上的二元关系R是同余关系吗？如不是，找出反例。1)∈R当且仅当（x=y=0）∨(x≠0∧y≠0)2)∈R当且仅当x≥y7..设是一代数系统，其中+，*是普通的加法和乘法运算，A为下列集合：1）A={x|x≥0,x∈I}2)A={x|x=a+b*30.5,a,b为有理数}问在上述情况下，是域吗？为什么？8.设是一代数系统，其中+，*是普通的加法和乘法运算，A为下列集合：1）A={x|x=a/b,a,b∈I+，且a≠k*b}2)A={x|x=a+b*50.5,a,b为有理数}问在上述情况下，是域吗？为什么？五.证明题1.设A=｛a，b｝，〈A，*〉为半群，且a*a=b。证明：a*b=b*a。2.定义I+上的两个二元运算为：a*b=aba○b=aba,b∈I+证明：*对○是不可分配的。3.如果是半群，且*是可交换的，称是可交换半群。证明：如果S中有元素a,b，使得a*a=a和b*b=b,则（a*b）*(a*b)=a*b。4.设是群，且|S|=2n，n∈I+。证明：在S中至少存在a≠e，使得a*a=e，其中e为么元。5.证明：如果f是由到的同态映射，g是由到的同态映射，那么，g。f是由到的同态映射。6.设f是从群到的同态映射,则f是入射当且仅当Ker(f)={e}。其中e是G1中的么元。7.设是一个独异点，且对于G中的每一个元素x都有x*x=e，其中e是么元，证明是一个阿贝尔群。8.设是一个代数系统，且对于任意的a∈A,有a★b=a,证明二元运算*对★时可分配的。第7章一.填空题1.把（）的图叫做简单图。2.无向图具有一条欧拉路，当且仅当图是联通的，而且（）。3.把（）的图叫做完全图。4.把（）的图叫做连通图。5.如果一个连通图有m个结点，则它的完全关联矩阵的秩为（）。6.含有平行边的任何一个图叫做（）。7.含有n个节点的图，至少生成（）棵生成树。8.在一个含有n个节点的图中，度数为奇数节点的个数必为（）个。9.在含有n个节点的完全图中，其边数为（）。10.若图G只有一个连通分支，则G叫作（）。11.无回路的连通图又叫做（）。12.给定一个无孤立节点的图G，若存在一条路，经过图中每边一次仅且一次，则这条路叫做（）。13.G是具有n个节点的简单图，如果G中每对节点度数之和大于等于n，则G中存在一条（）。14.设G=是一个无向图，如果能够把G的所有节点和边画在平面上，且使得任何两条边出了端点之外没有其他的交点，就称G为（）。15.还有v个节点，e条边,r个面的连通平面图G,满足欧拉公式（）。二.选择题1.如果一个连通图有m个结点，则它的完全关联矩阵的秩为（）A)mB)m+1C)m-1D)m/22.一个有n个节点连通图至少有（）条边。A)nB)n-1C)n+1D)(n-1)n/23.关联同一节点的两条边叫做（）。A）环B)回路C)圈D）邻接边4.含有平行边的任何一个图叫做（）。A）欧拉图B）汉米尔顿图C）连通图D）多重图5.在一个含有n个节点的图中，度数为奇数节点的个数必为（）个。A）2B）n-1C）偶数D）奇数6.在任何有向图中，所有节点的出度之和等于（）。A)所有节点的入度之和B）所有节点入度之和的2倍C）所有节点入度之和的一半D）没有必然联系7.在含有n个节点的完全图中，其边数为（）。A)nB)n-1C)n+1D)(n-1)n/28.在含有n个节点的图，它有（）个补图。A)1B)nC)(n-1)n/2D)09..如果两个图是同构的，那么下面那条是错误的.()A)节点数相等B)边数相等C)度数相同的节点数相等D)连通的10.在具有n个节点的图中，如果两个节点之间有路，则必有一条路的长度（）。A)至少为nB)至少为n-1C)至多为n-1D)n11.若图G只有一个连通分支，则G叫作（）。A)连通图B)强连通图C）欧拉图D）平面图12.给定图T，如果T是树，在与下面（）是不等价的。A)无回路的连通图B）连通且e=v-1C)每对节点之间有且只有一条边D）连通，但删除任意一条边后便不连通了13.含有n个节点的图，至少生成（）棵生成树。A)1B)nC)(n-1)n/2D)014.连通图必然有（）。A）欧拉路B)汉米尔顿路C)欧拉回路D)通过各节点的路15.如果一个连通图有m个结点，则它的邻接矩阵的秩为（）A)mB)m+1C)m-1D)不确定三.判断题1.在任何图中，度数为偶数的节点必有奇数个。()2.在任何有向图中，所有节点的入度之和等于所有节点的出度之和。（）3.每个图中，边数等于节点度数的两倍。（）4.连通图必有欧拉回路。（）5.有汉米尔顿路的图必有欧拉路。（）四.计算题1.画出下图的完全补图。2.给一个含有5个节点的自补图。3.求下图中1）从A到F所有通路。2）从A到F的所有迹。4.求下图的邻接矩阵，并求出可达性矩阵。5.求下图的关联矩阵和邻接矩阵。6.1）画一个有一条欧拉路和一条汉米尔顿路的图2）画一个有欧拉路但没有汉米尔顿路的图。7.1）画一个有一条欧拉路和一条汉米尔顿路的图2）画一个有汉米尔顿路但没有欧拉路的图。8.利用Kruskal求下图的一棵最小生成树。五.证明题1.证明在任何有向完全图中，所有节点的入度的平方和等于所有节点的出度的平方和。2.若无向图G中恰有两个奇数度的节点，则这两点间必有一条路。3.若图G=具有汉米尔顿回路，则对于节点集V的每个非空子集S均有W(G-S)≤|S|成立。其中W(G-S)是G-S中连通分支数。4.设G=为连通图，且e∈E.证明：当且仅当e是G的割边时，e才在G中的每颗生成树中。（注：文档可能无法思考全面，请浏览后下载，供参考。可复制、编制，期待你的好评与关注！）