安徽大学《离散数学》（上）试卷（A卷）及参考答案

安徽大学《离散数学》（上）试卷（A卷）及参考答案安徽大学《离散数学》（上）试卷（A卷）考试时间：120分钟满分：100分考试方式：闭卷院系：__________专业：__________姓名：__________学号：__________得分：__________一、单项选择题（每小题2分，共20分）1.下列语句中，属于真命题的是（）A.请勿吸烟！B.明天会下雨吗？C.若2是偶数，则3是奇数D.x+5>32.下列命题公式中，为永真式的是（）A.P∧¬PB.P∨¬PC.P→(Q∧¬Q)D.(P→Q)∧(Q→P)3.设论域为实数集R，谓词P(x)：x是正数，Q(x)：x是偶数，则命题“所有正数都不是偶数”可符号化为（）A.∀x(P(x)→¬Q(x))B.∃x(P(x)∧¬Q(x))C.∀x¬(P(x)∧Q(x))D.∃x¬(P(x)→Q(x))4.对任意集合A、B、C，下列结论正确的是（）A.若A⊆B且B⊆C，则A⊂CB.若A∈B且B⊆C，则A∈CC.若A⊆B且B∈C，则A∈CD.若A∈B且B∈C，则A∈C5.设集合A={1,2,3}，B={a,b}，则从A到B的函数个数为（）A.5B.6C.8D.96.设集合A={1,2,3,4}，关系R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>}，则R具有（）A.自反性、对称性、传递性B.自反性、对称性、非传递性C.自反性、反对称性、传递性D.反自反性、对称性、传递性7.下列关系中，不是偏序关系的是（）A.实数集上的“≤”关系B.集合A的幂集P(A)上的“⊆”关系C.整数集上的“整除”关系D.整数集上的“<”关系8.设f:A→B，g:B→C，若f和g均为单射，则g∘f（复合函数）是（）A.单射B.满射C.双射D.非单非满射9.设集合A={a,b,c}，其划分π={{a},{b,c}}，则由π诱导的等价关系R的元素个数为（）A.3B.4C.5D.610.下列集合中，基数与其他集合不同的是（）A.自然数集NB.整数集ZC.实数集RD.有理数集Q二、判断题（每小题2分，共10分，对的打“√”，错的打“×”）1.命题公式“P→Q”与“¬P∨Q”是逻辑等价的。（）2.空集是任何集合的真子集。（）3.若关系R是对称的，则其逆关系R⁻¹也一定是对称的。（）4.满射函数的复合函数一定是满射函数。（）5.有限集的幂集的基数一定是2的正整数次幂。（）三、填空题（每小空2分，共20分）1.设P：明天放假，Q：我去旅游，则命题“明天不放假，我也不去旅游”可符号化为__________；命题“如果明天放假，我就去旅游”的逆否命题可符号化为__________。2.设集合A={1,2,3,4}，B={2,4,6}，则A∩B=__________，A∪B=__________，A-B=__________。3.设集合A={1,2}，则A的幂集P(A)=__________，P(A)的基数为__________。4.设R是集合A={1,2,3}上的关系，R={<1,2>,<2,3>}，则R的传递闭包t(R)=__________。5.设f:Z→Z，f(x)=2x+1，则f是__________（填“单射”“满射”或“双射”）函数。四、解答题（每小题10分，共20分）1.用等值演算法求命题公式(P∨Q)→(P∧R)的主析取范式和主合取范式。2.设集合A={1,2,3,4}，R是A上的二元关系，R={<1,1>,<1,3>,<2,2>,<3,1>,<3,3>,<4,4>}。（1）证明R是A上的等价关系；（2）求A关于R的等价类。五、证明题（每小题10分，共30分）1.用推理规则证明：前提：P→(Q∨R)，¬Q，P；结论：R。2.证明：对任意集合A、B、C，有(A∩B)∪C=(A∪C)∩(B∪C)。3.设f:A→B，g:B→C是两个函数，若g∘f是双射，证明f是单射，g是满射。安徽大学《离散数学》（上）试卷（A卷）参考答案一、单项选择题（每小题2分，共20分）1.C2.B3.A4.B5.C6.B7.D8.A9.C10.C解析：1.命题需满足可判断真假，A、B为非命题，D为开语句，C为真命题；2.永真式（重言式）是恒为真的命题公式，P∨¬P恒为真；3.“所有正数都不是偶数”即对任意x，若x是正数，则x不是偶数，对应符号化∀x(P(x)→¬Q(x))；4.由集合包含关系的传递性，A∈B且B⊆C，则A∈C；5.从A到B的函数个数为|B|=2=8；6.R满足自反性（每个元素自身相关）、对称性（<1,2>与<2,1>同时存在），但非传递性（无<1,1>以外的传递链）；7.偏序关系需满足自反性、反对称性、传递性，“<”关系无自反性，不是偏序；8.单射函数的复合仍为单射；9.划分诱导的等价关系包含每个子集内元素的自反、对称、传递关系，共1+3=4个自反元素，2个对称元素，合计5个；10.自然数集、整数集、有理数集均为可数集，基数相同，实数集为不可数集，基数不同。二、判断题（每小题2分，共10分）1.√2.×3.√4.×5.√解析：1.由等值演算，P→Q⇔¬P∨Q，正确；2.空集是任何非空集合的真子集，不是自身的真子集，错误；3.对称关系的逆关系与原关系相同，仍为对称，正确；4.满射复合不一定是满射，例如f:{1,2}→{1,2}（f(1)=1,f(2)=2），g:{1,2}→{1}（g(1)=g(2)=1），g∘f是满射，但f是双射，g是满射，若f为满射、g为非满射，复合后非满射；5.若|A|=n，则|P(A)|=2，正确。三、填空题（每小空2分，共20分）1.¬P∧¬Q；¬Q→¬P（或等价形式）2.{2,4}；{1,2,3,4,6}；{1,3}3.{∅,{1},{2},{1,2}}；44.{<1,2>,<2,3>,<1,3>}5.单射四、解答题（每小题10分，共20分）1.解：等值演算过程如下：(P∨Q)→(P∧R)⇔¬(P∨Q)∨(P∧R)（蕴含等值式）（2分）⇔(¬P∧¬Q)∨(P∧R)（德摩根定律）（4分）⇔(¬P∧¬Q∧R)∨(¬P∧¬Q∧¬R)∨(P∧Q∧R)∨(P∧¬Q∧R)（补全最小项）（7分）主析取范式：m₀∨m₁∨m₇∨m₅（或写成∑(0,1,5,7)）（8分）主合取范式：M₂∧M₃∧M₄∧M₆（或写成∏(2,3,4,6)）（10分）2.（1）证明：①自反性：对任意x∈A，<x,x>∈R（R中包含<1,1>,<2,2>,<3,3>,<4,4>），故R自反；（3分）②对称性：对任意x,y∈A，若<x,y>∈R，则<y,x>∈R（如<1,3>∈R，<3,1>∈R），故R对称；（6分）③传递性：对任意x,y,z∈A，若<x,y>∈R且<y,z>∈R，则<x,z>∈R（如<1,3>∈R，<3,1>∈R，可得<1,1>∈R），故R传递；（9分）综上，R是A上的等价关系。（2）等价类：[1]ₐ={1,3}，[2]ₐ={2}，[4]ₐ={4}（10分）五、证明题（每小题10分，共30分）1.证明：（1）P（前提引入）（2分）（2）P→(Q∨R)（前提引入）（4分）（3）Q∨R（(1)(2)假言推理）（6分）（4）¬Q（前提引入）（8分）（5）R（(3)(4)析取三段论）（10分）故结论成立。2.证明：任取x∈(A∩B)∪C，则x∈A∩B或x∈C（2分）若x∈A∩B，则x∈A且x∈B，故x∈A∪C且x∈B∪C，即x∈(A∪C)∩(B∪C)；（5分）若x∈C，则x∈A∪C且x∈B∪C，即x∈(A∪C)∩(B∪C)；（7分）故(A∩B)∪C⊆(A∪C)∩(B∪C)。反之，任取x∈(A∪C)∩(B∪C)，则x∈A∪C且x∈B∪C（8分）若x∈C，则x∈(A∩B)∪C；若x∉C，则x∈A且x∈B，即x∈A∩B，故x∈(A∩B)∪C；（9分）故(A∪C)∩(B∪C)⊆(A∩B)∪C。综上，(A∩B)∪C=(A∪C)∩(B∪C)。（10分）3.证明：①证明f是单射：假设存在a₁,a₂∈A，a₁≠a₂，使得f(a₁)=f(a₂)（2分）则g(f(a