离散数学(一)练习题与答案

1一、判断题（正确√，错误×）1-5题：××××√6-10题：××√√√11-15题：××√×√16-17题：√×二、单项选择题1AC2C3C4.B5A6B7B8C9B10B11D12A13C14C三、填空题1┐Q→P或┐P→Q，Q→P2AB｛{a,b},{a},{b},{c}｝，AB｛｛c｝｝，AB｛{a,b}｝，AB｛{a,b},{a},{b}｝。3．{}Φ，{,{}}{Φ,{Φ}}，{,{}}{}{{Φ}}，{}{Φ}。4．A={1,2,3,……,12}，R是A上的整除关系，子集B={2,4,6}。则B的最大元是：无，最小元是：2，极大元是：4，6，极小元是：2，上界是：12，下界是：2，上确界是：12，下确界是：2。5.ggg6R,T7.略8．极大元：{a,b},{b,c}，最大元：无，上界：{a,b,c}，下确界：Φ。2一、判断题（正确√，错误×）()1．设A，B，C为任意的命题公式，若ACBC,则AB。()2．公式PQ是合取范式，不是析取范式。()3．公式()()PQPQ与公式()PQR等价。()4．()(()())()()()()xAxBxxAxxBx。()5．谓词公式()()((,)(,))xyPxyQyz中，x,y是约束变元，z是自由变元。()6．对谓词公式()(()(,))(,)xPyQxyRxy中的自由变元进行代入后得到公式()(()(,))(,)xPzQxzRxy。()7．对谓词公式()(()(,))(,)xPxQxyRxy中的约束变元进行换名后得到公式()(()(,))(,)yPyQyyRxy。()8．{}{,{}}，且{}{,{}}。()9．对任意的集合A,B,C,D.若,ACBD，则ABCD。()10．设A,B,C是任意的集合，则()()()ABCABAC。()11．集合A={a,b,c}上的任何二元关系R都不可能既是对称的，又是反对称的。()12．若R和S是集合A上的任意的两个反自发的关系，则R○S也是反自反的。()13．设P,≤是一个偏序集合，若最大成员存在，则该最大成员必然是极大成员。()14．R是等价关系一定是相容关系，反之亦然。()15．当X和Y都是有限集合时，若f:X→Y是单射函数，则|X|≤|Y|。()16．设N是自然数集合，f:N→N,且f(j)=j2+2,则f是单射函数。()17．设X={1,2,3,4},f是X上的关系且f={1,4,2,1,2,3,3,2,4,4}，则f是函数。二、单项选择题1．给定命题公式()PQR，则它的成真指派为()，成假指派为()。A．111,011,100,101,110B.111,011C.000,010,001D.0002．给定命题公式：()()PQPR与之等价的是()。A．()PQRB.()PQR3C.()PQRD.()PQR3．命题：“所有马都比某些牛跑得快”的符号化公式为()。假设：H(x)：x是马；C(x)：x是牛；F(x,y)：x跑得比y快。A.()(()()(()(,)))xHxyCyFxyB.()(()()(()(,)))xHxyCyFxyC.()(()()(()(,)))xHxyCyFxyD.()()(()(()(,)))yxHxCyFxy4．给定命题公式：()(())xAxB与之等价的公式是()。A．()()xAxBB.()()xAxBC.()()BxAxD.()()BxAx5．对任意的集合A,B,C,下述论断正确的是（）。A．若,ABBC，则AC.B.若,ABBC，则AC.C.若,ABBC，则AC.D.若,ABBC，则AC.6．下列选项错误的是（）。A.B.C.{}D.{}7．设A={1,{1}},P(A)为A的幂集，下列选项错误的是（）。A．{1}()PAB.{1}()PAC.{{1}}()PAD.{{1}}()PA8．集合A={1,2,3,6},A上的整除关系具有的性质是（）A．自反的，对称的，可传递的B.反自反的，对称的，可传递的C.自反的，反对称的，可传递的D.反自反的，反对称的，可传递的9．关系R的关系矩阵1010010100100001RM,则关系R具有的性质是()。A．自反的，对称的，可传递的B．自反的，反对称的，可传递的C．自反的，对称的4D．都不是10．函数的复合运算满足（）。A．交换律B.结合律C.等幂律D.分配律11．若g○f是双射函数，则（）。A．f，g必是满射B.f，g必是单射C．f必是满射,g必是单射D.f必是单射,g必是满射12．设N是自然数集合，R是实数集合，f:N→R，且给定10()logfjj，则（）。A．f是单射B.f是满射C．f是双射D.都不是13．设AB，则有（）。A．BB.BC．ABD.BA14．给定公式()(,)()()xFyxyGy，它的前束范式是（）。A．()()((,)())xyFyxGyB.()()((,)())xyFzxGyC．()()((,)())xyFzxGyD.()()((,)())xyFzxGy三、填空题1．给定命题1：“除非你努力，否则你将失败”（假设Q：你努力，P：你将失败）；命题2：“只有睡觉才能恢复疲劳”（假设P：睡觉，Q：恢复疲劳）。则命题1符号化为_________________，命题2符号化为___________________。2．集合A={{a,b},{c}}，B={{a},{b},{c}},试写出：AB___________________，AB___________________，AB___________________，AB___________________。3．确定以下各式：{}____________，{,{}}____________，{,{}}{}________________，{}________________。4．A={1,2,3,……,12}，R是A上的整除关系，子集B={2,4,6}。则B的最大元是____________，最小元是____________，极大元是____________，极小元是____________，上界是______________，下界是______________，上确界是____________，下确界是____________。5．设A={1,2,3}，f,g,h均为A到A的函数，即f,g,h：A→A，其中5f={1,1,2,1,3,1},g={1,1,2,3,3,2},h={1,3,2,1,3,1}，则__________是单射，__________是满射，__________是双射。6．设A={a,b,c},B={x,y,z}，R，S，T：A→B的关系，且R={a,x,b,y,c,y}，S={a,x,a,y}，T={a,x,b,x,c,x}，则________可定义为A到B的函数。7．关系R是自反的，当且仅当在关系矩阵中___________________________，在关系图中____________________________________________________；关系R是反自反的，当且仅当在关系矩阵中_________________________，在关系图中___________________________________________________；关系R是对称的，当且仅当在关系矩阵中__________________________，在关系图中__________________________________________________。8．设A={a,b,c}上偏序集(),PA，其中P(A)是A的幂集，则幂集P(A)的子集{,{},{},{,},{,}}Bababbc的极大元是______________，最大元是_______________，上界是______________，下确界是______________。四、简答题1.将下列命题符号化(1)不存在两片完全相同的叶子。(2)发光的不都是金子。(3)尽管有人聪明，但未必一切人都聪明。2.利用两种方法证明下列蕴涵式：()QPQP.3.利用求主合取范式证明下列公式等价性：()()()PQPRPQR4．设A,B和C是集合，则回答下列问题：若ABAC,是否必须B=C?五、综合题1应用CP规则证明：R→S可以从前提P→(Q→S),┐R∨P和Q推出。2.符号化下列命题，并给出构造推理证明每位资深名士或是中科院院士或是国务院参事。所有的资深名士是政协委员。张大为是资深名士，但他不是中科院院士，因此有的政协委员是国务院参事。6六R是整数集合Z上的二元关系，对任意m,n∈Z,m,n∈R当且仅当m2=n2.(1)证明R是等价关系。(2)求R的等价类。七.设S为X上的偏序关系，T为Y上的偏序关系，若x1,y1,x2,y2∈P当且仅当x1,x2∈S且y1,y2∈T,证明P是X×Y上的一个偏序关系。7