离散数学习题整合

1、CH01复习题§1.2 1. 命题判断（每空1分，共4分）1.11.3 P32-A 小李和小王是同班同学 B 小猪不是鲜花 C 3-2n<0 D 若2+2=4，则太阳从西方升起。上述语句中， 是简单命题， 不是命题， 是符合命题且真值为假， 是符合命题且真值为真。 （参考答案：ACDB）2. 命题符号化（每空2分，共4分）习题1.5(7)(3) P32-p：天下大雨，q：他乘公共汽车去上班，命题“除非天下大雨，否则他不乘公共汽车去上班”可符号化为 。（参考答案：qp 必要条件为后件）r：天很冷，s：老李来了，命题“虽然天很冷，老李还是来了” 可符号化为 。（参考答案rs）3.

2、五个真值表（每空2分，共4分）习题1.6(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）A rs B (r¬s)(¬rs) C rs D (r¬s)或(&

3、#172;rs)§1.2 命题公式及分类已知：A是含三个命题变项的命题公式，且A(001)=0，A(100)=1，则A是 。（D）A 矛盾是 B 可满足式 C 重言式 D 非重言式的可满足式§1.3 等值演算用等值演算法证明等值式：(pq)rp(qr). (演算的每一步都要写依据)§1.4 范式6. （每项1分，共4分）已知命题公式A(p,q)的真值表PqA(p,q)000011100111求A的永主析取范式、主合取范式、成真赋值和成假赋值。（参考答案：m1m3，M0M2，01、11，00、10）7. （2分）命题公式B(p,q,r)=(¬pr¬

4、;q)的主析取范式是 。（参考答案：C） A m2 B M6 C m1 D M5 E 命题公式B(p,q,r)=(¬p¬qr)的主析取范式是 。（参考答案：A） A m0m1m2m3m4m5m7 B M6 C m1 D M1 §1.5 全功能集（2分） 不是联结词全功能集。（参考答案：D） A B ¬, C ¬, D , 是联结词全功能集。（参考答案：A） A , B , C D §1.6 组合电路（习题1.16）有一盏灯由三个开关控制，要求按任何一个开关都能使灯由黒变亮或由亮变黑，试设计这样的一个电路。（解题基本步骤：状态设置、设计

5、真值表、写主析取范式、化简、绘制电路. 答案不唯一）§1.7 推理理论(习题1.19(1)用直接证明法或归谬法证明下面的推理.前提：¬(p¬q)， ¬qr，¬r. 结论：¬p.证明： (习题1.19(3)用直附加前提法证明下面的推理.前提：Pq. 结论：P(pq).证明：（例题1.28）公安人员审查一件盗窃案，已知事实如下：（1） 李或王盗窃了录音机；（2） 若李盗窃了录音机，则作案时间不能发生在午夜前；（3） 若王的证词正确，则午夜时屋里灯光未灭；（4） 若王的证词不正确，则作案时间发生在午夜前；（5） 午夜时屋里灯光灭了.试问盗窃

6、录音机的是李还是王，并证明你的结论。参考答案：王盗窃了录音机.设 p：李盗窃了录音机；q：王盗窃了录音机；r：作案时间发生在午夜前；s：王的证词正确；t：午夜时屋里灯光灭了.前提：pq，p¬r，st，¬sr，¬t. 结论：q.证明：CH02复习题§2.1例2.1（3）1 将命题“若李一的成绩比王二高，王二的成绩比吴三高，那么李一的成绩比吴三高”用0元谓词符号化。解：设H(x,y)：x的成绩比y高，a：李一，b：王二，c: 吴三则命题可符号化为 H(a,b) H(b,c) H(a,c)§2.1例2.4（4）2 在一阶逻辑中将命题“素数不全是奇数”

7、符号化。解：设F(x)：x是素数，G(x)：x是奇数则命题可符号化为 x(F(x)G(x)或 x(F(x)G(x)§2.23 （每空1分，共4分）给定解释I，对一阶逻辑合式公式中每个 出现的 指定 中的一个元素，称作在 下的赋值。 （自由 个体变项 个体域 解释I）§2.24 下面的一阶逻辑合式公式 不是闭式。(D 有自由出现) A x(F(x)G(X) B y(F(x,y)G(x) C xF(x)yG(y) D xF(x,y)yG(y)§2.25 下面各种叙述， 不正确。(C 例2.8（5）) 也可改造成正误判断题 A 在给定的解释和赋值下，任何一阶逻辑合式公式

8、都是命题 P45- B 闭公式的真值与赋值无关，只需要给定解释 C 非闭式的公式的真值只与赋值有关 D 可满足式可能是逻辑有效式§2.36 在四个合式公式"x$y(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）A 2 B 3 C 1 D 0（*参考答案：B）7 已知F(x)=Ø$x(M(x)ÙF(x)，G1(x)="

9、;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)的前束范式。 A 0 B 3 C 2 D 1例2.11（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) (量词扩

10、TH2.2(2)xyF(x)G(y) ) (量词扩TH2.2(2)解法3：xF(x,)G(x)F(y)G(x) )§2.4例2.17设个体域D=a,b，消去公式 x(F(x)yG(y) 中的量词。离散CH03复习题判断（1分/每小题）若集合A=1，1,2，3，则2A （×）若集合B=2，a，b，则a，bB （×）单选（2分/每小题）下面的集合算式 不正确。（A=C）A A-(BC)=A-B)(A-C) B A-B=AB C A=A D ABA-B=已知B= a，b，c ，则|P(A)|= . （P(A)= ，c，a，b，B，A）A |，c，a，b，B| B 2 C

11、 3 D 8填空（2分/每小题）若|P(A)| = 128，则|A|= . (|P(A)|=27,7)设A=1,3,3，则|A|= . (A=1,3，2)计算（8分/每小题）某班有48个学生， 第一次作业优秀7人，第二次作业优秀6人，两次作业都没得优秀的41人，求两次作业都得优秀的人数。（求解过程参见例3.12，参考答案：6）解：用A、B分别表示第一次和第二次作业优秀的人数集合，E为某班全体学生的集合 则：|E|=48，|A|=7，|B|=6，|AB|=41|AB| = |E|-(|A|+|B|)+|AB|AB| = 41-48+(7+6) = 6已知A=a，b，c，d，B=c，d，计算AB、

12、AB、A-B、AB。（P74-3.13(1)）画图画（AB）（C-B）的文氏图。（3.15（3）ABC证明：（AB）（C-B）=（AC）- B证：左式=（AB）（CB ） （3.27 /差交运算转换 ）= (AC) B （3.8/分配律）= (AC)-B （3.27 /差交运算转换 ）离散CH04复习题判断（1分/每小题）§4.11. A是任意集合，则A×A的任何子集称作A上的二元关系。 （）2. 若集合B=2，a，b，则a，bB （×）单选（2分/每小题）§4.13. A是任意集合，<x，x>|xA称作 关系。（恒等关系蕴含其是A上的B）A

13、 空 B恒等 C 全域 D A上的4. 设A=a，b，c， R=<a，a>，<a，b >，< b，b>，<b，c>，<c，a>，<c，b>，则 是R的关系矩阵。（参见P80-，参考答案：（A）A B C D 设S=1,2,3,4，R是S上的关系，其关系矩阵是，R的关系图中有 个环。AA 1 B 3 C 6 D 7填空（2分/每小题）§4.16. A、B是任意两个集合，若|A|=m，|B|=n，则|P(A×B)|= 。 （）7. 设A是任意集合， |A|=n，则A上有 个不同的二元关系。 (,|A

14、5;A|=n2)§4.58. R是集合A上的等价关系，如果有序对<a,b>R，则记作 。（ab）9.若R是集合A上的偏序关系，则可将此偏序关系简记作；有序对<x,y>，可记作 。（ab）计算（8分/每小题）§4.210. 已知关系R=<2,2>，<2,2,2>，求RR、R2、R2. (同例4.7 理解定义4.9)解：RR=<2，2,2>R2 = <2,2> 限制R2 = ran（R2）= ran<2,2> = 2 像集11. 已知A=a，b，c，d，R1和R2是A上的关系，且R1=<a

15、，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关系性质

16、的定义12. 设集合A上的两个关系R1和R2都是对称的，证明R1R2仍是对称的。证明： 参见主教材P87-13. 试证任何集合A的幂集P(A) 上的包含关系R是偏序关系证明：xP(A)，都有xx，<x，x>R R是自反的<x,y>R xyxy xy xy （集合包含关系的定义） yx <y,x>R (包含关系的定义) R是反对称的x、t、yP(A),若<x,t>R<t,y>R 则 xtty (关系R的定义) xy （集合运算律） <x,y>R （关系R的定义）R是传递的14. 已知R的关系图如下图所示，画R的自反闭包r（R

17、）、对称闭包s（R）、传递闭包t(R).1235415. 画<1,2,3,4,5,6,7,8，R整除>的哈斯图。16. 判断函数f：NN， 是否是满射、单射、双射，为什么?012.0123.解：作f的对应关系图如右，由图可知1无原像，故f非满射，也非双射。但f是单射。离散CH05 选择一个最合适的答案       e0e1e2v3v4v5v6e3v0v1v2e4e5e61.下图中的边（和边的交替）序列：e0 e1 e2 e3 e4e5 称为 。（A） A 简单通路 B 初级通路 C 通路 D 复杂通路 v0v1v

18、2v3v4v5v62. 下面有向图中的顶点序列：V0 V1 V2 V3 V4 V2 V5 称为 。（C）A 路径 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，vV，都有 ，则称G是n阶有向完全图。（<u，v>E < v，u >E）5. G（V,E）是n阶有向完全图，通常记为 。(Kn）v1v2v3e4e1e2e36. 在下面的有向图中，从v2到v2的长度为2的初级回路是 。v2e4v1e1v2v0v1v3v2e0e1e3e2

19、7.在下面的无向图中，顶点 是割点，边 是桥。（V2）（e3）8. 设G是有向图或无向图，称p（G）是图G的 。（连通分支个数）简答（6分/每小题）§5.29. 下面三个无向图，它们之间哪些同构，哪些不同构。若不同构，为什么？若同构，请建立顶点之间的双射。 图G1 图G2 图G3答：图G1与图G2不同构，因为图G1与G2存在度不相同的顶点。 2分同理G2G3. 2分G1 G3. 2分因为 2 c b 1 4 3 d a建立顶点之间的如下对应关系f：1a，2b，3c，4d，f是双射，并且两图的边也一一对应。10.无向图的（点）着色：P132-例5.511. 图 强连通，图 单向连通，图

20、 弱连通，图 非连通。D2D3D4D1 参考答案：D2 、D3 、D4 、D1）12.应用题 P133-例5.6离散CH06 选择一个最合适的答案1. 下面三种说法，其中不正确的有 个。(C 还有必要条件) Hall定理是二部图G(V1, V2,E)存在完备匹配的充要条件 无论是有向图还是无向图，都有判断其是否存在欧拉通路和欧拉回路的充要条件 目前只有判断哈密顿图的充分条件A 0 B 3 C 1 D 2 2. 下面四种说法，其中正确的有 个。（A） 存在既是欧拉图又是哈密顿图的无向图 存在是欧拉图不是哈密顿图的无向图存在不是欧拉图却是哈密顿图的无向图 存在既不是欧拉图又不是哈密顿图的无向图A

21、4 B 3 C 2 D 1填空§6.13. 用G(V1 ,V2,E)表示二部图G，| V1|=n，| V2|=m，记号表示图G为 。（完全二部图）§6.44. 若图G画在平面上使得除顶点处外没有 出现，则称G为平面图。（边交叉）5. 下面的平面图共有 个面，其中无限面R0的次数deg（R0）= 。（3，8） 平面图6-1 6. 非连通的平面图6-2的外部面是R0，deg（R0）= 。（9）R1R0R2非连通平面图6-2应用题：7. P151-习题6.5 （二部图的应用）8. P151-习题6.15 （哈密顿图的应用）9. P152-习题6.18 （欧拉通路或欧拉回路的应用）10. *P152-习题6.23 （平面图在作色中的应用）离散CH07复习题§7.11. P165-12设n阶连通无向图G(V,E)有m条边，G的生成树有 条边，余树有 条边。（n-1，m-n+1）2. P167-例7.5（2）画出4个顶点非同构无向树。（2种）3. P173-习题7.16（3）画出4个顶点非同构的根