2022年离散数学习题答案.doc

离散数学习题答案 篇一：离散数学习题答案-2015 离散数学习题答案 习题一 1、利用逻辑结合词把以下命题翻译成符号逻辑方式 （1） 他既是本片的编剧，又是导演 - P Q （2） 银行利率一降低，股价随之上扬- P Q （3） 尽管银行利率降低，股价却没有上扬 - P Q （4） 占据空间的、有质量而且不断变化的对象称为物质- M ?(SPT) （5） 他今天不是乘火车去北京，确实是随旅行团去了九寨沟 - P Q （6） 小张身体薄弱，但是极少生病，同时头脑好使- P Q R （7） 不识庐山真面目，只缘身在此山中 - P Q （解释：由于身在此山中，因而不识庐山真面目） （8） 两个三角形类似，当且仅当他们的对应角相等或者对应边成比例 - S ?(ET) （9） 假设一个整数能被6整除，那么它就能被2和3整除。假设一个整数能被3整除， 那么它的各位数字之和也能被3整除 解：设 P 一个整数能被6整除 Q 一个整数能被2整除 R 一个整数能被3整除 S 一个整数各位数字之和能被3整除 翻译为：（P （Q R） （R S） 2、判别下面各语句是否命题，假设是命题，说出它的真值 （1）BASIC语言是最完满的程序语言 - Y，T/F （2）这件事大概是小王干的 - N （3）x2 = 64- N （4）可导的实函数都是连续函数 - Y，T/F （5）我们要发扬连续作战的作风，再接再厉，争取更大的成功 - N （6）客观规律是不以人们意志为转移的- Y，T （7）到2020年，中国的国民消费总值将赶上和超过美国 - Y，N/A （8）凡事都有例外 - Y，F 3、构造以下公式的真值表，并由此判别哪些公式是永真式、矛盾式或可满足式 （1）（P （P Q） Q 解： 4、利用真值表方法验证以下各式为永真式 （1）（8）略 5、证明以下各等价式 （3）P（Q R）? （P Q）（P R） 证明：左式 ? PQ R ? PQP R ? （PQ）（P R） ? （P Q）（P R）? 右式 （4）（P Q）（R Q）（R P）? （P Q）（R Q）（R P） 证明：左式 ? (（PR） Q）（R P） ? (（PR）R) ) (（PR）P) ) （QR）（QP） ? （P Q）（R Q）（R P）? 右式 6、假设P Q ? QR,能否断定 P ? R ？ 假设P Q ? QR，能否断定 P ? R？假设P ? R，能否断定 P ? R？ 解： （1）假设P Q ? QR，不能推断P ? R，由于假设 Q = P R, 那么P Q? PP R ? QR，但P能够不等价于R. （2）假设P Q ? QR，不能推断P ? R，由于假设 Q = P R, 那么P Q? PP R ? QR，但P能够不等价于R. （3）假设P ? R，那么有P ? R，由于P ? R，那么P lt;- R为永真式，及有P lt;- R为永真式，因而P ? R. 8、把以下各式用等价表示出来 （1）(PQ) P 解：原式 ? (PQ) (PQ) (PP) ? (PQ) (PQ) (PQ) (PQ) (PP) (PP) 9、证明： 是最小功能完备集合 证明: 由于, 是最小功能完备集合,因而,假设 能表示出,那么其是功能完备集合。由于 P Q ? (P) Q ,因而 是功能完备集合。由于 不能互相表示，因而 是最小功能完备集合；同理可证：非，条件非也能将或表示出来： P Q ? (P ! Q) 8、分别利用真值表法和等价变换法求以下公式的主合取范式及主析取范式: (3) P(R(QP) 解：真值表法 主合取范式为 = (PQR) (PQR) = M4M6 主析取范式为 = (PQR)(PQR)(PQR)(PQR)(PQR)(PQR) = m0m1m2m3m5m7 等价变换法（略） (4) (P(QR) (P(QR) 解：真值表法主合取范式为 = (PQR) ( PQR) ( PQR) (PQR) ( PQR) ( PQR) = M1M2M3M4M5M6 主析取范式为 = (PQR)(PQR) = m0m7 等价变换法（略） 14、从A,B,C,D 4个人中派2人出差，要求满足以下条件：假设A去，那么必须在C或D中选一人同去；B和C不能同时去；C和D不能同时去。用构造范式的方法决定选派方案。 解：由题设 A：A去，B：B去，C：C去，D：D去那么满足条件的选派应满足如下范式： （A（C?D）（BC）（CD） 构造和以上范式等价的主析取范式 （A（C?D）（BC）（CD） ?（AB C D ）（ABCD）（ABCD）（ABCD）（ABCD）（ABCD）（ABCD）（ABCD）共有八个极小项，但按照题意，需派两人出差，因而，只有其中三项满足要求：（ABCD），（ABCD），（ABCD） 即有三种方案：A和C去或者A和D去或者B和D去。 15、证明以下包含试： （1）PQ=P (PQ) 证明：PQ ? P Q ? T(P Q) ? (PP) (P Q) ? P (PQ) ? P (PQ) 因而，这是个等价式，因而也是个包含式 （2）(PQ) Q= (PQ) 证明：(PQ) Q ? (PQ) Q ? (PQ) Q ? (PQ) (QQ) ? (PQ) T ? (PQ) 因而，这是个等价式，因而也是个包含式 （3）PPR=S 证明：PPR ? F = S (F可包含任何命题公式) （4）P=QRR 证明：P=T ? QRR （任何公式可包含永真式） 18、一个有钱人生前留下了一笔珍宝，藏在一个隐秘处。在他留下的遗言中指出寻找珍宝的线索如下： （1） 假设藏宝的房子靠近池塘，那么珍宝不会藏在东厢房。 （2） 假设房子的前院栽有大柏树，那么珍宝就藏在东厢房。 （3） 藏宝房子靠近池塘。 （4） 要么前院栽有大柏树，要么珍宝埋在花园正中地下。 （5） 假设后院栽有香樟树，珍宝藏在附近。 请利用包含关系找出藏宝处 解：按照给定的条件有下述命题： P：珍宝藏在东厢房 Q：藏宝的房子靠近池塘 R：房子的前院栽有大柏树 S：珍宝藏在花园正中地下 T：后院栽有香樟树 M：珍宝藏在附近 按照题意，得出： （QP）（RP）Q（RS）（TM） ?？ （QP）（RP）Q（RS）（TM） ?P（RP）（RS）（TM） ?R（RS）（TM） ?S（TM） ?S 即珍宝藏在花园正中地下 20、演绎证明下面各包含式： （4）(RQ) (RS),(QE) (SB), (EB),(PR) ? P 证明：运用反证方法，将结论的非纳入前提，证明步骤如下 1 P p(附加前提) 2 PRp 3 R T 1,2 I 4 (RQ) (RS) p 5 QST 3,4 I 6 (QE) (SB) p 7 EBT 5,6 I 8 (EB) p 9 F(矛盾式) T 7,8 E （5）P(QR),Q(RS) ? P(QS) 证明：运用cp法，将结论条件式的前件作为前提，证明步骤如下 1 P p(附加前提) 2 P(QR) p 3 QRT 1,2 I 4 Q(RS) p 5 R(QS) T 4 E 6 QST 3,5 I 7 P(QS) CP 1,6 21、把以下句子演绎成逻辑方式，并给出证明 （2）某公司发生了一起盗窃案，经细心侦察，掌握了如下一些事实： ? 被盗现场没有留下任何痕迹 ? 失盗时，小花或那么小英正在卡拉ok厅 ? 假设失窃时小胖正在附近，他就会适应性地破门而入偷走东西后扬长而去 ? 假设失盗时小花正在卡拉ok厅唱歌，那么金刚是最大的嫌疑者 ? 假设失盗时小胖不在附近，那么他的女友小英会和他一起外出旅游 ? 假设失盗时小英正在卡拉ok厅唱歌，那么瘦子是最大的嫌疑者 按照以上事实，请通过演绎推理找出偷窃者 解：按照给定的条件有下述命题： P：现场无任何痕迹 Q：失窃时，小花在OK厅 R：失窃时，小英在OK厅 S：失窃时，小胖在附近 T：金刚是偷窃者 M：瘦子是偷窃者 那么按照案情有如下命题公式： P，QR，S P，Q T， S R，R M P P SPP篇二：离散数学最全课后(屈婉玲版) 1.1略 1.2略 1.3略 1.4略 1.5略 1.6略 1.7略 1.8略 1.9略 1.10 略 1.11 略 1.12 将以下命题符号化,并给出各命题的真值: (1)2+24当且仅当3+36.(2)2+2 4的充要条件是3+3?6.(3)2+2?4与 3+36互为充要条件.(4)假设2+2?4, 那么 3+3?6,反之亦然. (1)p?q,其中,p: 2+24,q: 3+36, 真值为 1.(2)p?q,其中,p:2+24,q:3+36,真值为0. (3)?p?q,其中,p:2+24,q:3+36,真值为 0.(4)?p?q,其中,p:2+24,q:3+36,真值为1. 1.13 将以下命题符号化, 并给出各命题的真 值:(1)假设今天是星期一,那么明天是星期二.(2)只有 今天是星期一,明天才是星期二.(3)今天是星期 一当且仅当明天是星期二. (4)假设今天是星期一, 那么明天是星期三. 令p: 今天是星期一;q:明天是星期二;r:明天是星期三.(1) p?q ?1. (2) q?p ?1. (3) p?q?1. (4)p?r当p ?0时为真; p ?1时为假. 1.14 将以下命题符号化. (1) 刘晓月跑得快,跳得高.(2) 老王是山东人或河北人. (3)由于天气冷, 因而我穿了羽绒服. (4)王欢与李乐组成一个小 组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃 饭, 一面听音乐. (8)假设天下大雨,他就乘 班车内班.(9)只有天下大雨,他才乘班车内 班.(10)除非天下大雨,他才乘班车内班.(11) 下雪路滑, 他迟到了. (12)2与4都是素数,这是不对的. (13)“2或4是素数,这是不对的”是不对的.(1)p?q,其中, p:刘晓月跑得快, q: 刘晓月跳得 高.(2)p?q,其中, p:老王是山东人, q: 老王是河北 人.(3)p?q, 其中,p:天气冷, q:我穿了羽绒服. (4)p, 其中,p:王欢与李乐组成一个小组,是简单命题.(5)p, 其中,p:李辛与李末是兄弟. (6)p?q,其中, p:王强学过法语, q: 刘威学过法语.(7)p?q, 其中, p:他吃饭,q:他听音乐. (8)p?q, 其中,p:天下大雨, q:他乘班车内班. (9)p?q, 其中,p:他乘班车内班, q: 天下大雨.(10)p?q, 其中,p: 他乘班车内班,q:天下大雨.(11)p?q, 其中,p: 下雪路滑, q:他迟到了. 12)?(p?q)或?p?q,其中,p:2是素数,q:4是素 数.(13)?(p?q)或p?q,其中,p:2 是素数,q:4是素数. 1.15 设p:2+3=5. q: 大熊猫产在中 国.r: 复旦大学在广州. 求以下复合命题的真值: (1)(p?q)?r(2)(r?( p?q)?p(3)?r?( ?p?q?r) (4)(p?q?r)?(?p?q)?r) (1)真值为0. (2)真值为0. (3)真值为0. (4)真值为1. 留意:p, q是真命题,r是假命题. 1.16 1.17 1.18 1.19 略 略 略 用真值表推断以下公式的类 型:(1)p?(p?q?r) (2)(p?q)?q (3)?(q?r)?r (4)(p?q)?(?q?p) (5)(p?r)?(?p?q)(6)(p?q) ?(q?r)?(p?r)(7)(p?q) ?(r?s)(1), (4),(6)为重言式. (3)为矛盾式. (2), (5),(7)为可满足式. 1.20 1.21 1.22 1.23 1.24 1.25 1.26 1.27 1.28 1.29 1.30 1.31 略 略 略 略 略 略 略 略 略 略 略 将以下命题符号化,并给出各命题的真 值:(1)假设3+4,那么地球是静止不动的. (2)假设3+24,那么地球是运动不止的. (3)假设地球 上没有树木,那么人类不能生存. (4)假设地球上没有水,那么3是无理数. (1)p?q,其中, p: 2+24,q:地球静止不动,真值为0.(2)p?q, 其中, p: 2+24,q:地球运动不止,真值为1. (3)?p?q,其中,p:地球上有树木,q:人类能生存,真值为 1.(4)?p?q,其中,p:地球上有水,q: 3 是无理数,真值为1. 2.1.设公式A=p?q,B=p?q,用真值表验证公式A和B适宜德摩根律: ?(A?B)?A?B. 由于?(A?B)和?A?B的真值表一样,因而它们等值. 2.2. 略 2.3. 用等值演算法推断以下公式的类型, 对不是重言式的可满足式,再用真值表法求出成真赋 值.(1)?(p?q?q) (2)(p?(p?q)?(p?r) (3)(p?q)?(p?r) (1)?(p?q?q)?(?(p?q)?q)?(?p?q?q)?p?q?q?p?0?0?0.矛盾式.(2)重言式. (3) (p?q)?(p?r)?(p?q)?(p?r)?p?q?p?r易见,是可满足式,但不是重言式.成真赋值为:000,001, 101, 111 式:(1)p?(p?q)?(p?q) (3)?(p?q)?(p?q)?(p?q) (4)(p?q)?(?p?q)?(p?q)?(p?q) (1) (p?q)?(p?q)?p?(q?q)?p?1?p.(3)?(p ?q)?(p?q)?(q?p) ?(?p?q)?(?q?p) ?(p?q)?(q?p) ?(p?q)?(p?p)?(?q?q)?(?p?q) ?(p?q) ?(p?q) (4)(p?q)?(?p?q) ?(p?p)?(p?q)?(?q?p)?(?q?q) ?(p?q) ?(p?q) 2.5.求以下公式的主析取范式,并求成真赋 值:(1)(?p?q)?(?q?p) (2)?(p?q)?q?r (3)(p?(q?r) ?(p?q?r) (1)(?p?q)?(?q?p) ?(p?q) ?(?q?p) ?p?q?q?p?p?q?q?p(吸收律)?(p?p)?q?p?(q?q) ?p?q?p?q?p?q?p?q ?m10?m00?m11?m10 ?m0?m2?m3 ?(0, 2,3). 成真赋值为00,10, 11. (2)主析取范式为0, 无成真赋值,为矛盾式.(3)m0?m1?m2?m3?m4?m5?m6?m7,为重言式. 2.6.求以下公式的主合取范式, 并求成假赋 值:(1)?(q?p)?p (2)(p?q)?(?p?r) (3)(p?(p?q)?r (1) ?(q?p)?p ?(?q?p)?p ?q?p?p ?q?0 ?0 ?M0?M1?M2?M3 这是矛盾式.成假赋值为00, 01,10,11. (2)M4,成假赋值为100. (3)主合取范式为1, 为重言式.篇三：离散数学习题答案 离散数学习题答案 习题一及答案：（P14-15） 14、将以下命题符号化： （5）李辛与李末是兄弟 解：设p：李辛与李末是兄弟，那么命题符号化的结果是p （6）王强与刘威都学过法语 解：设p：王强学过法语；q：刘威学过法语；那么命题符号化的结果是（9）只有天下大雨，他才乘班车内班 解：设p：天下大雨；q：他乘班车内班；那么命题符号化的结果是q?p （11）下雪路滑，他迟到了 解：设p：下雪；q：路滑；r：他迟到了；那么命题符号化的结果是(p?q)?r 15、设p：2+3=5. q：大熊猫产在中国. r：太阳从西方升起. 求以下复合命题的真值： （4）(p?q?r)?(?p?q)?r) 解：p=1，q=1，r=0， p?q (p?q?r)?(1?1?0)?1， (?p?q)?r)?(?1?1)?0)?(0?0)?1 ?(p?q?r)?(?p?q)?r)?1?1?1 19、用真值表推断以下公式的类型： （2）(p?p)?q 解：列出公式的真值表，如下所示：20、求以下公式的成真赋值：（4）?(p?q)?q 解：由于该公式是一个包含式，因而首先分析它的成假赋值，成假赋值的条件是： ?(p?q)?1?p?0 ? q?0q?0? 因而公式的成真赋值有：01，10，11。 习题二及答案：（P38） 5、求以下公式的主析取范式，并求成真赋值： （2）(?p?q)?(q?r) 解：原式?(p?q)?q?r?q?r?(?p?p)?q?r ?(?p?q?r)?(p?q?r)?m3?m7，此即公式的主析取范式， 因而成真赋值为011，111。 *6、求以下公式的主合取范式，并求成假赋值： （2）(p?q)?(?p?r) 解：原式?(p?p?r)?(?p?q?r)?(?p?q?r)?M4，此即公式的主合取范式， 因而成假赋值为100。 7、求以下公式的主析取范式，再用主析取范式求主合取范式： （1）(p?q)?r 解：原式?p?q?(?r?r)?(?p?p)?(?q?q)?r) ?(p?q?r)?(p?q?)r ?(?p?q?r) ?(p?q ?(?p?q?)?r(?p?q?)r?(?p)?r(?p ?q?)r?(?p q? )?r?( ?q?)r?(?p q?r? ?pq?r? ?m1?m3?m5?m6?m，此即主析取范式。 7 主析取范式中没出现的极小项为m0，m2，m4，因而主合取范式中含有三个极大项M0，M2， M4，故原式的主合取范式?M0?M2?M4。 9、用真值表法求下面公式的主析取范式：（1）(p?q)?(?p?r) 解：公式的真值表如下：由真值表能够看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式?m1?m2?m3?m4?m5?m6?m7 习题三及答案：（P52-54） 11、填充下面推理证明中没有写出的推理规那么。 前提：?p?q,?q?r,r?s,p 结论：s 证明： p 前提引入 ?p?q前提引入 q 析取三段论 ?q?r前提引入 r 析取三段论 r?s前提引入 s 假言推理 15、在自然推理系统P中用附加前提法证明下面推理： （2）前提：(p?q)?(r?s),(s?t)?u结论：p?u 证明：用附加前提证明法。 p附加前提引入 p?q 附加 (p?q)?(r?s) 前提引入 r?s 假言推理 s 化简 s?t 附加 (s?t)?u前提引入 u 假言推理 故推理正确。 16、在自然推理系统P中用归谬法证明下面推理： （1）前提：p?q，?r?q，r?s结论：?p 证明：用归谬法 p结论的否认引入 p?q前提引入 ?q 假言推理 ?r?q 前提引入 ?r析取三段论 r?s 前提引入 r 化简 r?r 合取 由于r?r?0，因而推理正确。 17、在自然推理系统P中构造下面推理的证明： 只要A曾到过受害者房间同时11点往常没离开，A确实是谋杀嫌犯。A曾到过受害者房间。假设A在11点往常离开，看门人会看见他。看门人没有看见他。因而，A是谋杀嫌犯。 解：设p：A到过受害者房间，q：A在11点往常离开，r：A是谋杀嫌犯，s：看门人看见过A。 那么前提：(p?q)?r，p，q?s，?s结论：r 证明： q?s 前提引入 ?s 前提引入 ?q 拒取式 p 前提引入 p?q 合取引入 (p?q)?r 前提引入 r假言推理 习题四及答案：（P65-67） 5、在一阶逻辑中将以下命题符号化： （2）有的火车比有的汽车快。 解：设F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快；那么命题符号化的结果是： ?x?y(F(x)?G(y)?H(x,y) （3）不存在比所有火车都快的汽车。 解：方法一： 设F(x)：x是汽车，G(y)：y是火车，H(x,y)：x比y快；那么命题符号化的结果是： ?x(F(x)?y(G(y)?H(x,y)或?x(F(x)?y(G(y)?H(x,y) 方法二： 设F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快；那么命题符号化的结果是： ?x(G(x)?y(F(y)?H(x,y)或?x?y(G(x)?(F(y)?H(x,y) 9、给定解释I如下： (a) 个体域为实数集合R。 (b) 特定元素a ? ? ?0。 (c) 函数 f(x,y)?x?y,x,y?R。 ? (d) 谓词F(x,y):x?y,G(x,y):x?y,x,y?R。 ? 给出以下公式在I下的解释，并指出它们的真值： （2）?x?y(F(f(x,y),a)?G(x,y) 解：解释是：?x?y(x? y?0?x?y)，含义是：关于任意的实数x，y，假设x-y=0那么xlt;y。 该公式在I解释下的真值为假。 14、证明下面公式既不是永真式也不是矛盾式： （1）?x(F(x)?y(G(y)?H(x,y) 解：取解释I如下：个体域为全总个体域， F(x)：x是兔子，G(y)：y是乌龟，H(x,y)：x比y跑得快，那么该公式在解释I下真值是1； 取解释I如下：H(x,y)：x比y跑得慢，其它同上，那么该公式在解释I下真值是0；