《离散数学》模拟试卷A及答案

PAGEPAGE2《离散数学》模拟试卷A及答案一、选择dbeac设集合A={a，b，c，d，e}，偏序关系R的哈斯图下图所示，假设A的子集B={c，ddbeacA．下界B．最大下界C．最小上界D．以上答案都不对已知│A│=15，│B│=10，│A∪B│=20，则│A∩B│=（）A．10B．5C．20D．13下图中哪个是欧拉图（）ABCD下列式子中正确的是（）A．Æ=0B．ÆÎÆC．ÆÎ{a，b}D．ÆÎ{Æ}在下图所示的哈斯图中的偏序集不是格的是（）下图中是一个从X到Y的映射f，其中X={a，b，c，d，e}，Y={1，2，3，4}，则映射f是（）acacbd1243e已知集合A={Æ，1，2}，则A的幂集合r(A)=________设K6是有6个点的完全图，则K6共有____________条边。设A，B是两集合，其中A={a，b，c}，B={a，b}，则A-B=_______________，AÇB=_______________________________________设A={a，b}，B＝｛1，2，3｝，则AB=二、计算或证明题利用推理规则证明：┒（P∧┒Q），┒Q∨R，┒R┒P（10分）利用推理规则证明：（x）（┒A（x）→B（x）），（x）┒B（x）（x）A（x）（10分）如果关系R和S为X上的等价关系，证明：RS也是X上的等价关系。（10分）设集合A={a，b，c，d}，A上的关系R={<a，a>，<a，b>，<b，a>，<c，d>，<b，c>}（10分）求：1）画出R的关系图，并用作图法分别求出R的自反闭包和对称闭包。2）用Warshall算法求出R的传递闭包设<R，*>是一个代数系统，*是R上的一个二元运算，使得对于R中的任意元素x，y都有x*y=x+y+xy，证明0是幺元而且<R，*>是独异点（其中，R为实数集，+为普通加法，为普通乘法）（10分）设f1，f2都是一从代数系统<A，*>到代数系统<B，>的同态。设g是从A到B的一个映射，使得对任意aA，都有g(a)=f1(a)f2(a)；证明：如果<B，>为一个可交换半群，那么g是一个由<A，*>到<B，>的同态。（10分）假设给定了正整数的序偶集合A，在A上定义二元关系R如下：<<x，y>，<u，v>>R，当且仅当xv=yu，证明：R为等价关系。（10分）答题纸姓名：学号：成绩选择填空题选择题答案：题号123456答案CBCDBB填空题答案：7）Æ，{1}，{2}，{Æ}，{1，2}，{Æ，1}，{Æ，2}，{Æ，1，2}8）159）{c}，{a,b}10）{<a，1>，<a，2>，<a，3>，<b，1>，<b，2>，<b，3>}计算证明题证明：┒（P∧┒Q）P┒P∨QT（1）EP→QT（2）E┒Q∨RPQ→RT（4）EP→RT（3）（5）I┒R→┒PT（6）E┒RP┒PT（7）（8）I证明：（x）（┒A（x）→B（x））P（x）┒B（x）P┒B（a）US（2）┒A（a）→B（a）US（1）┒B（a）→A（a）T（4）EA（a）T（3）（5）I（x）A（x）EG（6）如果关系R和S为X上的等价关系，证明：RS也是X上的等价关系。证明：1）设任意xX，∵R和S为等价关系，满足自反性质∴有<x，x>R，<x，x>S∴<x，x>RS，∴RS在X上自反。2）设任意<x，y>RS，则，<x，y>R且<x，y>S∵R和S为等价关系，满足对称性质，∴必有<y，x>R且<y，x>S∴<y，x>RS∴RS满足对称性质3）设任意<x，y>，<y，z>RS则<x，y>，<y，z>R，∵R传递，∴<x，z>R同理，由<x，y>，<y，z>S，∵S传递，∴<x，z>S∴<x，z>RS∴RS传递综上，RS满足自反、对称和可传递的性质，为X上的等价关系。设集合A={a，b，c，d}，A上的关系R={<a，a>，<a，b>，<b，a>，<c，d>，<d，c>}求：1）画出R的关系图，并用作图法分别求出R的自反闭包和对称闭包。2）用Warshall算法求出R的传递闭包略。参考书上例题。5、设<R，*>是一个代数系统，*是R上的一个二元运算，使得对于R中的任意元素x，y都有x*y=x+y+xy，证明0是幺元而且<R，*>是独异点（其中，R为实数集，+为普通加法，为普通乘法）（10分）证明：对于任意x，yR，x*y=x+y+xy，因为+和在实数集合上封闭，所以x*yR；对于任意x，y，zR，x*（y*z）=x+（y+z+yz）+x（y+z+yz）=x+y+z+xy+xz+yz+xyz（x*y）*z=（x+y+xy）+z+（x+y+xy）z=x+y+z+xy+xz+yz+xyz所以x*（y*z）=（x*y）*z，所以*在R上可结合。对于任意xR，因为x*0=x+0+x0=x，0*x=0+x+0x=x，所以x*0=0*x=x，所以0为幺元。综上，<R，*>是独异点。6、设f1，f2都是一从代数系统<A，*>到代数系统<B，>的同态。设g是从A到B的一个映射，使得对任意aA，都有g(a)=f1(a)f2(a)；证明：如果<B，>为一个可交换半群，那么g是一个由<A，*>到<B，>的同态。证明：设任意x，y∈A，因为f1，f2为<A，*>到<B，>的同态，所以f1（x*y）=f1（x）f1（y），f2（x*y）=f2（x）f2（y）g（x*y）=f1（x*y）f2(x*y)=（f1（x）f1（y））（f2（x）f2（y））因为运算可结合，可交换，所以（f1（x）f1（y））（f2（x）f2（y））=f1（x）f2（x）f1（y）f2（y）=（f1（x）f2（x））（f1（y）f2（y））=g（x）g（y）所以g（x*y）=g（x）g（y）所以g为<A，*>到<B，>的同态。7、证明：设A上定义的二元关系R为：＜＜x,y＞,＜u,v＞＞∈Rx/y=u/v对任意＜x,y＞∈A,因为x/y=x/y,所以＜＜x,y＞,＜x,y＞＞∈R即R是自反的。设＜x,y＞∈A，＜u,v＞∈A,若＜＜x,y＞,＜u,v＞＞∈R=>x/y=u/v=>u/v=x/y＜＜u,v＞,＜x,y＞＞∈R即R是对称的。设任意＜x,y＞∈A，＜u,v＞∈A,＜w,s＞∈A,对＜＜x,y＞,＜u,v＞＞∈R∧＜＜u,v＞,＜w,s＞＞∈R=>(x/y=u/v)∧(u/v=w/s)=>x/y=w/s=>＜＜x,y＞,＜w,s＞＞∈R故R是传递的，于是R是A上的等价关系。《离散数学》模拟试卷B喻琇瑛一、选择下面不是命题的句子是（）。虽然李明很累，他还是去上课。请不要抽烟！北京是中国的首都。李明不是老师。已知│A│=15，│B│=10，│A∪B│=20，则│A∩B│=（）A．10B．5C．20D．13设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．以上都不对设集合S={1，2，3}，S上的关系R={<1，1>，<1，2>，<2，1>，<3，3>}，如果1）自反性2）反自反性3）对称性4）反对称性5）传递性则R具有性质：（）A．1）3）5）B．1）2）C．2）4）D．3）下列式子中正确的是（）A．Æ=0B．ÆÎÆC．ÆÎ{a，b}D．ÆÎ{Æ}下面的有向图G为（）A．弱连通B．单向连通C．强连通D．以上都不是下图中是一个从X到Y的映射f，其中X={a，b，c，d}，Y={1，2，3}，则映射f是（）A双射B满射C入射D以上都不是aacbd123一个代数系统<S，*>，其中S是非空集合，*是S上的一个二元运算，如果运算*是封闭的，可结合的，则代数系统<S，*>为（）A半群B群C独异点D以上都不是一个代数系统<S，*>，其中S是非空集合，*是S上的一个二元运算，如果运算*是封闭的，可结合的，则代数系统<S，*>为（）A半群B群C独异点D以上都不是已知集合A={1，2，3}，则A的幂集合r(A)=____________________________________。设集合A={a，b，c，d}，A上的关系R={<a，a><a，c>，<b，d>}，S={<a，b>，<d，c>，<a，d>}则关系R2=________________________________。逆关系RC=________________________________________________________。复合关系R○S=____________________________________________________。设集合A={1，2，3，4，5}，A上偏序关系R的哈斯图如下图所示，则A的极大元是________，极小元是________________。445213二、计算或证明题利用推理规则证明：P∨Q，P→R，Q→SR∨S（10分）利用推理规则证明：∀x(A(x)→B(x)),∀x(C(x)→┓B(x))⇒∀x(C(x)→┓A(x))下列均为集合A={1，2，3，4}上的偏序关系，分别画出它们的哈斯图，找出集合A相应的最大、最小元，极大、极小元。（10分）1212341243A={0，1，2，3，4}，式子{<x，y>2<x∧y<3}，写出该式所给出的A上的二元关系，并画出关系图。（10分）证明：设*是定义在集合A上的一个二元运算，且在A中有关于运算*的左零元θl和右零元θr，那么θl=θr=θ，且A中的零元是唯一的。（10分）设A={a，b，c，d，e}，A上有一个划分H={{a，b}，{c，d}，{e}}，求由划分H所确定的A上的一个等价关系。（10分）证明：集合X上的二元关系S是传递的，当且仅当SSS（10分）求出下图的邻接矩阵，并求出可达性矩阵。V4V4V3V2V1答题纸姓名：学号：成绩选择填空题选择题答案：题号123456789答案BBBDDBBAA填空题答案：10）Æ，{1}，{2}，{3}，{1，2}，{1，3}，{2，3}，{1，2，3}11）R2={<a，a><a，c>}，RC={<a，a><c，a>，<d，b>}，R○S={<a，b><a，d>，<b，c>}12）极大元是_4，5_______，极小元是_1，2，3___________计算证明题1、利用推理规则证明：P∨Q，P→R，Q→SR∨S1）P∨QP2）┒P→QT（1）E3）P→RP4）┒R→┒PT（3）E5）┒R→QT（1）（4）I6）Q→SP7）┒R→ST（5）（6）I8）R∨ST（7）E2、∀x(A(x)→B(x)),∀x(C(x)→┓B(x))⇒∀x(C(x)→┓A(x))证明：(1)∀x(A(x)→B(x))P(2)┓B(a)→┓A(a)US（1）(3)∀x(C(x)→┓B(x))P(4)C(a)→┓B(a)US（3）(5)┓B(a)→┓A(a)T（2）E(6)C(a)→┓A(a)T(5),(4),I(7)∀x(C(x)→┓A(x))UG(6)3、３４３４１２图1：极大元：2，3极小元：4最大元：无最小元：4图2：极大元：4极小元：3最大元：4最小元：3A={0，1，2，3，4}，式子{<x，y>2<x∧y<3}，写出该式所给出的A上的二元关系，并画出关系图。（10分）R={<3，0>，<3，1>，<3，2>，<3，0>，<3，1>，<3，2>，<4，0>，<4，1>，<4，2>}关系图略5、证明：设*是定义在集合A上的一个二元运算，且在A中有关于运算*的左零元θl和右零元θr，那么θl=θr=θ，且A中的零元是唯一的。证明：因为θl=θl*θr=θr，所以θl=θr=θ。又设另有一零元θ’，则θ’=θ’*θ=θ所以θ’=θ。所以零元唯一。6、设A={a，b，c，d，e}，A上有一个划分H={{a，b}，{c，d}，{e}}，求由划分H所确定的A上的一个等价关系。R1={a，b}{a，b}={<a，a>，<a，b>，<b，a>，<b，b>}R2={c，d}{c，d}={<c，c>，<c，d>，<d，c>，<d，d>}R3={e}{e}={<e，e>}所以R=R1∪R2∪R3={<a，a>，<a，b>，<b，a>，<b，b>，<c，c>，<c，d>，<d，c>，<d，d>，<e，e>}证明：集合X上的二元关系S是传递的，当且仅当SSS（10分）证明：1）设S是传递的，设任意＜x,z＞∈S°S,由复合定义，则存在某个y∈X，使得＜x,y＞∈S，且＜y,z＞∈S。因为S是传递的，所以＜x,z＞∈S，所以S°SS。2）反之，设S°SS，假定＜x,y＞∈S且＜y,z＞∈S，则＜x,z＞∈S°S。因为S°SS，故＜x,z＞∈S，得到S是传递的。综上，S是传递的，当且仅当SSS。求出下图的邻接矩阵，并求出可达性矩阵。V4V4V3V2V101100110000101001010AR=