离散数学试题1

《离散数学》模拟试卷1一、选择1．设集合A={a，b，c，d，e}，偏序关系R的哈斯图下图所示，假设A的子集B={c，d，e}，则元素c为B的（）A．下界

B．最大下界

C．最小上界

D．以上答案都不对2．已知│A│=15，│B│=10，│A∪B│=20，则│A∩B│=

（）A．10

B．5

C．20

D．133．下图中哪个是欧拉图（）A

B

C

D4．下列式子中正确的是（）A．=0

B．

C．{a，b}

D．{}5．在下图所示的哈斯图中的偏序集不是格的是（）6．下图中是一个从X到Y的映射f，其中X={a，b，c，d，e}，Y={1，2，3，4}，则映射f是（）

A双射

B满射

C入射

D以上都不是7．下面不是命题的句子是

（

）。A．虽然李明很累，他还是去上课。B．请不要抽烟！C．北京是中国的首都。D．李明不是老师。8．设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．以上都不对9．设集合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）10．下列式子中正确的是（）A．=0

B．

C．{a，b}

D．{}11．下面的有向图G为（）A．弱连通

B．单向连通

C．强连通

D．以上都不是12．下图中是一个从X到Y的映射f，其中X={a，b，c，d}，Y={1，2，3}，则映射f是（）A双射

B满射

C入射

D以上都不是13．下面不是命题的句子是

（

）。A．虽然李明很累，他还是去上课。B．请不要抽烟！C．北京是中国的首都。D．李明不是老师。14．已知│A│=15，│B│=10，│A∪B│=20，则│A∩B│=

（）A．10

B．5

C．20

D．1315．设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．以上都不对16．设集合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）17．下列式子中正确的是（）A．=0

B．

C．{a，b}

D．{}18．下面的有向图G为（）A．弱连通

B．单向连通

C．强连通

D．以上都不是19．下图中是一个从X到Y的映射f，其中X={a，b，c，d}，Y={1，2，3}，则映射f是（）A双射

B满射

C入射

D以上都不是20．一个代数系统<S，*>，其中S是非空集合，*是S上的一个二元运算，如果运算*是封闭的，可结合的，则代数系统<S，*>为（）A

半群

B

群

C

独异点

D

以上都不是21．一个代数系统<S，*>，其中S是非空集合，*是S上的一个二元运算，如果运算*是封闭的，可结合的，则代数系统<S，*>为（）A

半群

B

群

C

独异点

D

以上都不是22．一个代数系统<S，*>，其中S是非空集合，*是S上的一个二元运算，如果运算*是封闭的，可结合的，则代数系统<S，*>为（）A

半群

B

群

C

独异点

D

以上都不是23．一个代数系统<S，*>，其中S是非空集合，*是S上的一个二元运算，如果运算*是封闭的，可结合的，则代数系统<S，*>为（）A

半群

B

群

C

独异点

D

以上都不是24．已知集合A={1，2，3}，则A的幂集合(A)=____________________________________。25．设集合A={a，b，c，d}，A上的关系R={<a，a><a，c>，<b，d>}，S={<a，b>，<d，c>，<a，d>}则关系R2=________________________________。逆关系RC=________________________________________________________。复合关系R○S=____________________________________________________。26．设集合A={1，2，3，4，5}，A上偏序关系R的哈斯图如下图所示，则A的极大元是________，极小元是________________。27．已知集合A={，1，2}，则A的幂集合(A)=________28．设K6是有6个点的完全图，则K6共有____________条边。29．设A，B是两集合，其中A={a，b，c}，B={a，b}，则A-B=_______________，AB=_______________________________________30．设A={a，b}，B＝｛1，2，3｝，则AB=31．已知集合A={1，2，3}，则A的幂集合(A)=____________________________________。32．设集合A={a，b，c，d}，A上的关系R={<a，a><a，c>，<b，d>}，S={<a，b>，<d，c>，<a，d>}则关系R2=________________________________。逆关系RC=________________________________________________________。复合关系R○S=____________________________________________________。33．设集合A={1，2，3，4，5}，A上偏序关系R的哈斯图如下图所示，则A的极大元是________，极小元是________________。二、计算或证明题1．利用推理规则证明：┒（P∧┒Q），┒Q∨R，┒R┒P（10分）2．利用推理规则证明：（x）（┒A（x）→B（x）），（x）┒B（x）（x）A（x）（10分）3．如果关系R和S为X上的等价关系，证明：RS也是X上的等价关系。（10分）4．设集合A={a，b，c，d}，A上的关系R={<a，a>，<a，b>，<b，a>，<c，d>，<b，c>}

（10分）求：1）画出R的关系图，并用作图法分别求出R的自反闭包和对称闭包。2）用Warshall算法求出R的传递闭包5．设<R，*>是一个代数系统，*是R上的一个二元运算，使得对于R中的任意元素x，y都有x*y=xyxy，证明0是幺元而且<R，*>是独异点（其中，R为实数集，为普通加法，为普通乘法）（10分）6．设f1，f2都是一从代数系统<A，*>到代数系统<B，>的同态。设g是从A到B的一个映射，使得对任意aA，都有g(a)=f1(a)f2(a)；证明：如果<B，>为一个可交换半群，那么g是一个由<A，*>到<B，>的同态。（10分）7．假设给定了正整数的序偶集合A，在A上定义二元关系R如下：<<x，y>，<u，v>>R，当且仅当xv=yu，证明：R为等价关系。（10分）8．利用推理规则证明：P∨Q，P→R，Q→SR∨S

（10分）9．利用推理规则证明：∀x(A(x)→B(x)),∀x(C(x)→┓B(x))⇒∀x(C(x)→┓A(x))

10．下列均为集合A={1，2，3，4}上的偏序关系，分别画出它们的哈斯图，找出集合A相应的最大、最小元，极大、极小元。

（10分）11．A={0，1，2，3，4}，式子{<x，y>2<x∧y<3}，写出该式所给出的A上的二元关系，并画出关系图。

（10分）12．证明：设*是定义在集合A上的一个二元运算，且在A中有