离散数学习题整合

离散数学习题整合离散数学习题整合离散数学习题整合资料仅供参考文件编号：2022年4月离散数学习题整合版本号：A修改号：1页次：1.0审核：批准:发布日期：CH01复习题§1.命题判断（每空1分，共4分）~P32-A小李和小王是同班同学B小猪不是鲜花C3-2n<0D若2+2=4，则太阳从西方升起。上述语句中，是简单命题，不是命题，是符合命题且真值为假，是符合命题且真值为真。（参考答案：ACDB）2.命题符号化（每空2分，共4分）习题(7)(3)P32- p：天下大雨，q：他乘公共汽车去上班，命题“除非天下大雨，否则他不乘公共汽车去上班”可符号化为。（参考答案：q→p必要条件为后件） r：天很冷，s：老李来了，命题“虽然天很冷，老李还是来了”可符号化为。（参考答案r∧s）3.五个真值表（每空2分，共4分）习题(2)(4)P32- 设p的真值为0，r的真值为1，q、s都是命题，则命题公式（的真值为，命题公式的真值为。（参考答案：0,1）4.用符号p、q填空。（每空1分，共4分）基本概念设p：x>0（其中x是整数），q：太阳从西方升起，则是命题，是命题变项，是命题常项，不是命题。（参考答案：q，p，q，p）5.命题符号化，相容或与排斥或设r：现在小李在图书馆，s：现在小李在学生宿舍，则“现在小李在图书馆或学生宿舍”可符号化为。（参考答案：B）Ar∨sB(r∧¬s)∨(¬r∧s)Cr∧sD(r∧¬s)或(¬r∧s)§命题公式及分类已知：A是含三个命题变项的命题公式，且A(001)=0，A(100)=1，则A是。（D）A矛盾是B可满足式C重言式D非重言式的可满足式§等值演算用等值演算法证明等值式：(p∧q)→rp→(q→r).(演算的每一步都要写依据)§范式6.（每项1分，共4分）已知命题公式A(p,q)的真值表PqA(p,q)000011100111求A的永主析取范式、主合取范式、成真赋值和成假赋值。（参考答案：m1∨m3，M0∧M2，01、11，00、10）7.（2分）命题公式B(p,q,r)=(¬p∧r∧¬q)的主析取范式是。（参考答案：C）Am2BM6Cm1DM5E命题公式B(p,q,r)=(¬p∨¬q∨r)的主析取范式是。（参考答案：A）Am0∨m1∨m2∨m3∨m4∨m5∨m7BM6Cm1DM1§全功能集（2分）不是联结词全功能集。（参考答案：D）A{↑}B{¬,→}C{¬,∨}D{∧,∨}是联结词全功能集。（参考答案：A）A{↓,}B{∨,∧}C{∨}D{∧}§组合电路（习题）有一盏灯由三个开关控制，要求按任何一个开关都能使灯由黒变亮或由亮变黑，试设计这样的一个电路。（解题基本步骤：状态设置、设计真值表、写主析取范式、化简、绘制电路.答案不唯一）§推理理论(习题(1))用直接证明法或归谬法证明下面的推理.前提：¬(p∧¬q)，¬q∨r，¬r.结论：¬p.证明：…(习题(3))用直附加前提法证明下面的推理.前提：P→q.结论：P→(p∧q).证明：…（例题）公安人员审查一件盗窃案，已知事实如下：李或王盗窃了录音机；若李盗窃了录音机，则作案时间不能发生在午夜前；若王的证词正确，则午夜时屋里灯光未灭；若王的证词不正确，则作案时间发生在午夜前；午夜时屋里灯光灭了.试问盗窃录音机的是李还是王，并证明你的结论。参考答案：王盗窃了录音机.设p：李盗窃了录音机；q：王盗窃了录音机；r：作案时间发生在午夜前；s：王的证词正确；t：午夜时屋里灯光灭了.前提：p∨q，p→¬r，s→t，¬s→r，¬t.结论：q.证明：…CH02复习题§例（3）1将命题“若李一的成绩比王二高，王二的成绩比吴三高，那么李一的成绩比吴三高”用0元谓词符号化。解：设H(x,y)：x的成绩比y高，a：李一，b：王二，c:吴三则命题可符号化为H(a,b)∧H(b,c)H(a,c)§例（4）2在一阶逻辑中将命题“素数不全是奇数”符号化。解：设F(x)：x是素数，G(x)：x是奇数则命题可符号化为x(F(x)∧G(x)) 或x(F(x)G(x))§3（每空1分，共4分）给定解释I，对一阶逻辑合式公式中每个出现的指定中的一个元素，称作在下的赋值。（自由个体变项个体域解释I）§4下面的一阶逻辑合式公式不是闭式。(D有自由出现)Ax(F(x)G(X))By(F(x,y)G(x))CxF(x)yG(y)DxF(x,y)yG(y)§5下面各种叙述，不正确。(C例（5）)也可改造成正误判断题A在给定的解释和赋值下，任何一阶逻辑合式公式都是命题√P45-B闭公式的真值与赋值无关，只需要给定解释C非闭式的公式的真值只与赋值有关D可满足式可能是逻辑有效式§6在四个合式公式xy(F(x)(G(y)H(x,y)))、x(F(x)y(G(y)H(x,y)))、x(F(x)G(x))、x(F(x)G(x))中共有个是前束范式。（参考答案：A）A2B3C1D0（*参考答案：B）7已知F(x)=x(M(x)F(x))，G1(x)=x(M(x)F(x))，G2(x)=x(M(x)F(x))，G3(x)=x(M(x)F(x))，则在G1(x)、G2(x)和G3(x)中，有个是F(x)的前束范式。A0B3C2D1例（3）8求公式xF(x)G(x)的前束范式。解：xF(x)G(x)xF(x)xG(x)(蕴涵等值式)xF(x)xG(x)(量词否定等值式)xF(x)G(x))(量词分配等值式)解法2：xF(x)G(x)xF(x)yG(y)(换名规则)x(F(x)yG(y))(量词扩(2)=3\*GB3③)xyF(x)G(y))(量词扩(2)=4\*GB3④)解法3：xF(x,)G(x)F(y)G(x))§例设个体域D={a,b}，消去公式x(F(x)∧yG(y))中的量词。离散CH03复习题判断（1分/每小题）若集合A={1，{1,2}，3}，则2A（×）若集合B={2，{a，b}}，则{a，b}B（×）单选（2分/每小题）下面的集合算式不正确。（∵A=∴C）AA-(B∪C)=A-B)∪(A-C)BA-B=A∩～BCA=ADABA-B=已知B={{a，b}，c}，则|P(A)|=.（∵P(A)={，{c}，{{a，b}}，B}，∴A）A|{，{c}，{{a，b}}，B}|B2C3D8填空（2分/每小题）若|P(A)|=128，则|A|=.(∵|P(A)|=27,∴7)设A={1,3,3}，则|A|=.(∵A={1,3}，∴2)计算（8分/每小题）某班有48个学生，第一次作业优秀7人，第二次作业优秀6人，两次作业都没得优秀的41人，求两次作业都得优秀的人数。（求解过程参见[例]，参考答案：6）解：用A、B分别表示第一次和第二次作业优秀的人数集合，E为某班全体学生的集合则：|E|=48，|A|=7，|B|=6，|～A∩～B|=41 |～A∩～B|=|E|-(|A|+|B|)+|A∩B| |A∩B|=41-48+(7+6) =6已知A={{a，b}，c，d}，B={c，d}，计算A∩B、A∪B、A-B、AB。（(1)）画图画（A∩～B）∪（C-B）的文氏图。（（3））AABC证明：（A∩～B）∪（C-B）=（A∪C）-B证：左式=（A∩～B）∪（C∩～B）（/差交运算转换）=(A∪C)∩～B（分配律）=(A∪C)-B（/差交运算转换）离散CH04复习题判断（1分/每小题）§1.A是任意集合，则A×A的任何子集称作A上的二元关系。（√）2.若集合B={2，{a，b}}，则{a，b}B（×）单选（2分/每小题）§3.A是任意集合，{<x，x>|xA}称作关系。（∵恒等关系蕴含其是A上的∴B）A空B恒等C全域DA上的4.设A={a，b，c}，R={<a，a>，<a，b>，<b，b>，<b，c>，<c，a>，<c，b>}，则是R的关系矩阵。（参见P80-，参考答案：（A）ABCD设S={1,2,3,4}，R是S上的关系，其关系矩阵是，R的关系图中有个环。AA1B3C6D7填空（2分/每小题）§6.A、B是任意两个集合，若|A|=m，|B|=n，则|P(A×B)|=。（）7.设A是任意集合，|A|=n，则A上有个不同的二元关系。(,|A×A|=n2)§8.R是集合A上的等价关系，如果有序对<a,b>R，则记作。（a～b）9.若R是集合A上的偏序关系，则可将此偏序关系简记作；有序对<x,y>，可记作。（ab）计算（8分/每小题）§10.已知关系R={<2,{2}>，<{2},{2,{2}}>}，求RR、R{2}、R[{2}].(同例理解定义解：RR={<2，{2,{2}}>} R{2}={<2,{2}>}限制 R[{2}]=ran（R{2}）=ran{<2,{2}>}={{2}}像集11.已知A={a，b，c，d}，R1和R2是A上的关系，且R1={<a，a>，<a，b>，<b，d>}，R2={<a，d>，<b，c>，<b，d>，<c，b>}。求R2R1。解：∵<a，a>R1<a，d>R2，∴<a，d>R2R1 <a，b>R1<b，c>R2，∴<a，c>R2R1 <a，b>R1<b，d>R2，∴<a，d>R2R1故R2R1={<a，d>，<a，c>}证明题综合：§1等值公式和等值运算+§3集合运算+§4关系性质的定义12.设集合A上的两个关系R1和R2都是对称的，证明R1∩R2仍是对称的。证明：参见主教材P87-13.试证任何集合A的幂集P(A)上的包含关系R是偏序关系证明：xP(A)，都有xx，，<x，x>R∴R是自反的<x,y>R∧x≠yxy∧x≠yxy（集合包含关系的定义）yx<y,x>R(包含关系的定义)∴R是反对称的x、t、yP(A),若<x,t>R∧<t,y>R则xt∧ty(关系R的定义)xy（集合运算律）<x,y>R（关系R的定义）∴R是传递的14.已知R的关系图如下图所示，画R的自反闭包r（R）、对称闭包s（R）、传递闭包t(R).11235415.画<{1,2,3,4,5,6,7,8}，R整除>的哈斯图。16.判断函数f：N→N，是否是满射、单射、双射，为什么?

01012...0123..1无原像，故f非满射，也非双射。但f是单射。离散CH05选择一个最合适的答案

e0e1e2v3v4v5v6

e0e1e2v3v4v5v6e3v0v1v2e4e5e6A简单通路B初级通路C通路D复杂通路v0v1v2v3v4v5v62.下面有向图中的顶点序列Γ：V0V1Vv0v1v2v3v4v5v6A路径B初级通路C简单通路D复杂通路3.能构成图的度数序列。（C）A（3，3，2，1）B（2，3，2）C（1）D（3，3，3）填空：4.设G（V,E）是n阶有向简单图，若u，v∈V，都有，则称G是n阶有向完全图。（<u，v>∈E∧<v，u>∈E）5.G（V,E）是n阶有向完全图，通常记为。(Kn）v1v2v3e4v1v2v3e4e1e2e3v2e4v1e1v2v0v1v3v2e0e1e3v0v1v3v2e0e1e3e28.设G是有向图或无向图，称p（G）是图G的。（连通分支个数）简答（6分/每小题）§9.下面三个无向图，它们之间哪些同构，哪些不同构。若不同构，为什么？若同构，请建立顶点之间的双射。图G1图G2图G3答：图G1与图G2不同构，因为图G1与G2存在度不相同的顶点。…2分同理G2G3.…2分G1G3.…2分因为2cb143da建立顶点之间的如下对应关系f：1→a，2→b，3→c，4→d，f是双射，并且两图的边也一一对应。10.无向图的（点）着色：P132-例11.图强连通，图单向连通，图弱连通，图非连通。D2D2D3D4D1参考答案：D2、D3、D4、D1）12.应用题P133-[例]离散CH06选择一个最合适的答案1.下面三种说法，其中不正确的有个。(C还有必要条件)=1\*GB3①Hall定理是二部图G(V1,V2,E)存在完备匹配的充要条件=2\*GB3②无论是有向图还是无向图，都有判断其是否存在欧拉通路和欧拉回路的充要条件=3\*GB3③目前只有判断哈密顿图的充分条件A0B3C1D22.下面四种说法，其中正确的有个。（A）=1\*GB3①存在既是欧拉图又是哈密顿图的无向图=2\*GB3②存在是欧拉图不是哈密顿图的无向图=3\*GB3③存在不是欧拉图却是哈密顿图的无向图=4\*GB3④存在既不是欧拉图又不是哈密顿图的无向图A4B3C2D1填空§3.用G(V1,V2,E)表示二部图G，|V1|=n，|V2|=m，记号表示图G为。（完全二部图）§4.若图G画在平面上使得除顶点处外没有出现，则称G为平面图。（边交叉）5.下面的平面图共有个面，其中无限面R0的次数deg（R0）=。（3，8）平面图6-16.非连通的平面图6-2的外部面是R0，deg（R0）=。（9）RR1R0R2非连通平面图6-2应用题：7.P151-习题（二部图的应用）8.P151-习题（哈密顿图的应用）9.P152-习题（欧拉通路或欧拉回路的应用）10.*P152-习题（平面图在作色中的应用）离散CH07复习题§1.P165-↓12设n阶连通无向图G(V,E)有m条边，G的生成树有条边，余树有条边。（n-1，m-n+1）2.P167-例（2）画出4个顶点非同构无向树。（2种）3.P173-习题（3）画出4个顶点非同构的根树（4种）4.下面三条叙述中有条正确。（B）①一阶零图是一棵树②只有一片树叶的树在同构意义下只