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

2022年离散数学习题答案 篇一：离散数学习题答案-2022 离散数学习题答案 习题一 1、利用逻辑联结词把下列命题翻译成符号逻辑形式 （1） 他既是本片的编剧，又是导演 - P Q （2） 银行利率一降低，股价随之上扬- P Q （3） 尽管银行利率降低，股价却没有上扬 - P Q （4） 占据空间的、有质量而且不断改变的对象称为物质- M ? （5） 他今日不是乘火车去北京，就是随旅行团去了九寨沟 - P Q （6） 小张身体单薄，但是极少生病，并且头脑好使- P Q R （7） 不识庐山真面目，只缘身在此山中 - P Q （说明：因为身在此山中，所以不识庐山真面目） （8） 两个三角形相像，当且仅当他们的对应角相等或者对应边成比例 - S ? （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）到2022年，中国的国民生产总值将赶上和超过美国 - 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） 证明：左式 ? ) ) （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 - R为永真式，及有P - R为永真式，所以P ? R. 8、把下列各式用等价表示出来 （1） P 解：原式 ? ) ? ) ) ) 9、证明： 是最小功能完备集合 证明: 因为, 是最小功能完备集合,所以,假如 能表示出,则其是功能完备集合。由于 P Q ? Q ,所以 是功能完备集合。因为 不能相互表示，所以 是最小功能完备集合；同理可证：非，条件非也能将或表示出来： P Q ? 8、分别利用真值表法和等价变换法求下列公式的主合取范式及主析取范式: P) 解：真值表法 主合取范式为 = = M4M6 主析取范式为 = = m0m1m2m3m5m7 等价变换法（略） ) ) 解：真值表法 主合取范式为 = = M1M2M3M4M5M6 主析取范式为 = = 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 ? P Q ? T ? ? P ? P 所以，这是个等价式，因此也是个蕴含式 （2） Q= 证明： Q ? Q ? Q ? ? T ? 所以，这是个等价式，因此也是个蕴含式 （3）PPR=S 证明：PPR ? F = S （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） , , , ? P 证明：运用反证方法，将结论的非纳入前提，证明步骤如下 P p PRp R T I p QST I p EBT I p F T E （5）P,Q ? P 证明：运用cp法，将结论条件式的前件作为前提，证明步骤如下 P p P p QRT I Q p R T E QST I P CP 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 将下列命题符号化,并给出各命题的真值: 2+24当且仅当3+36.2+2 4的充要条件是3+3?6.2+2?4与 3+36互为充要条件.若2+2?4, 则 3+3?6,反之亦然. p?q,其中,p: 2+24,q: 3+36, 真值为 1.p?q,其中,p:2+24,q:3+36,真值为0. ?p?q,其中,p:2+24,q:3+36,真值为 0.?p?q,其中,p:2+24,q:3+36,真值为1. 1.13 将下列命题符号化, 并给出各命题的真 值:若今日是星期一,则明天是星期二.只有 今日是星期一,明天才是星期二.今日是星期 一当且仅当明天是星期二. 若今日是星期一, 则明天是星期三. 令p: 今日是星期一;q:明天是星期二;r:明天是星期三. p?q ?1. q?p ?1. p?q?1. p?r当p ?0时为真; p ?1时为假. 1.14 将下列命题符号化. 刘晓月跑得快,跳得高. 老王是山东人或河北人. 因为天气冷, 所以我穿了羽绒服. 王欢与李乐组成一个小 组. 李辛与李末是兄弟. 王强与刘威都学过法语. 他一面吃 饭, 一面听音乐. 假如天下大雨,他就乘 班车上班.只有天下大雨,他才乘班车上 班.除非天下大雨,他才乘班车上班. 下雪路滑, 他迟到了. 2与4都是素数,这是不对的. “2或4是素数,这是不对的”是不对的. p?q,其中, p:刘晓月跑得快, q: 刘晓月跳得 高.p?q,其中, p:老王是山东人, q: 老王是河北 人.p?q, 其中,p:天气冷, q:我穿了羽绒服. p, 其中,p:王欢与李乐组成一个小组,是简洁命题.p, 其中,p:李辛与李末是兄弟. p?q,其中, p:王强学过法语, q: 刘威学过法语.p?q, 其中, p:他吃饭,q:他听音乐. p?q, 其中,p:天下大雨, q:他乘班车上班. p?q, 其中,p:他乘班车上班, q: 天下大雨.p?q, 其中,p: 他乘班车上班,q:天下大雨.p?q, 其中,p: 下雪路滑, q:他迟到了. 12)?或?p?q,其中,p:2是素数,q:4是素 数.?或p?q,其中,p:2 是素数,q:4是素数. 1.15 设p:2+3=5. q: 大熊猫产在中 国.r: 复旦高校在广州. 求下列复合命题的真值: ?r)?p?r? ?r) 真值为0. 真值为0. 真值为0. 真值为1. 留意:p, q是真命题,r是假命题. 1.16 1.17 1.18 1.19 略 略 略 用真值表推断下列公式的类 型:p? ?q ?r ? ? ?)? ? , ,为重言式. 为冲突式. , ,为可满意式. 1.20 1.21 1.22 1.23 1.24 1.25 1.26 1.27 1.28 1.29 1.30 1.31 略 略 略 略 略 略 略 略 略 略 略 将下列命题符号化,并给出各命题的真 值:若3+4,则地球是静止不动的. 若3+24,则地球是运动不止的. 若地球 上没有树木,则人类不能生存. 若地球上没有水,则3是无理数. p?q,其中, p: 2+24,q:地球静止不动,真值为0.p?q, 其中, p: 2+24,q:地球运动不止,真值为1. ?p?q,其中,p:地球上有树木,q:人类能生存,真值为 1.?p?q,其中,p:地球上有水,q: 3 是无理数,真值为1. 2.1.设公式A=p?q,B=p?q,用真值表验证公式A和B适合德摩根律: ?A?B. 因为?和?A?B的真值表相同,所以它们等值. 2.2. 略 2.3. 用等值演算法推断下列公式的类型, 对不是重言式的可满意式,再用真值表法求出成真赋 值.? )? ? ?q)?p?q?q?p?0?0?0.冲突式.重言式. ?p?q?p?r易见,是可满意式,但不是重言式.成真赋值为:000,001, 101, 111 2.4.用等值演算法证明下面等值 式:p? ? ? ?p?p?1?p.? ?) ?) ? ? ? ? ? ? ? ? 2.5.求下列公式的主析取范式,并求成真赋 值:? ?q?r ) ? ? ? ? ?p?q?q?p?p?q?q?p?q?p? ?p?q?p?q?p?q?p?q ?m10?m00?m11?m10 ?m0?m2?m3 ?. 成真赋值为00,10, 11. 主析取范式为0, 无成真赋值,为冲突式.m0?m1?m2?m3?m4?m5?m6?m7,为重言式. 2.6.求下列公式的主合取范式, 并求成假赋 值:?p ? )?r ?p ?p ?q?p?p ?q?0 ?0 ?M0?M1?M2?M3 这是冲突式.成假赋值为00, 01,10,11. M4,成假赋值为100. 主合取范式为1, 为重言式. 篇三：离散数学习题答案 离散数学习题答案 习题一及答案：（P14-15） 14、将下列命题符号化： （5）李辛与李末是兄弟 解：设p：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语 解：设p：王强学过法语；q：刘威学过法语；则命题符号化的结果是（9）只有天下大雨，他才乘班车上班 解：设p：天下大雨；q：他乘班车上班；则命题符号化的结果是q?p （11）下雪路滑，他迟到了 解：设p：下雪；q：路滑；r：他迟到了；则命题符号化的结果是?r 15、设p：2+3=5. q：大熊猫产在中国. r：太阳从西方升起. 求下列复合命题的真值： （4）?r) 解：p=1，q=1，r=0， p?q ?1， ?r)?0)?1 ?r)?1?1?1 19、用真值表推断下列公式的类型： （2）?q 解：列出公式的真值表，如下所示： 20、求下列公式的成真赋值： （4）?q 解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是： ?1?p?0 ? q?0q?0? 所以公式的成真赋值有：01，10，11。 习题二及答案：（P38） 5、求下列公式的主析取范式，并求成真赋值： （2）? 解：原式?q?r?q?r?q?r ?m3?m7，此即公式的主析取范式， 所以成真赋值为011，111。 *6、求下列公式的主合取范式，并求成假赋值： （2）? 解：原式?M4，此即公式的主合取范式， 所以成假赋值为100。 7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）?r 解：原式?p?q?r) ?r ? ?rr?rr?r?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）前提：?,?u结论：p?u 证明：用附加前提证明法。 p附加前提引入 p?q 附加 ? 前提引入 r?s 假言推理 s 化简 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。 则前提：?r，p，q?s，?s结论：r 证明： q?s 前提引入 ?s 前提引入 ?q 拒取式 p 前提引入 p?q 合取引入 ?r 前提引入 r假言推理 习题四及答案：（P65-67） 5、在一阶逻辑中将下列命题符号化： （2）有的火车比有的汽车快。 解：设F：x是火车，G：y是汽车，H：x比y快；则命题符号化的结果是： ?x?y?G?H) （3）不存在比全部火车都快的汽车。 解：方法一： 设F：x是汽车，G：y是火车，H：x比y快；则命题符号化的结果是： ?x?y?H)或?x?y?H) 方法二： 设F：x是火车，G：y是汽车，H：x比y快；则命题符号化的结果是： ?x?y?H)或?x?y?H) 9、给定说明I如下： 个体域为实数集合R。 特定元素a ? ? ?0。 函数 f?x?y,x,y?R。 ? 谓词F:x?y,G:x?y,x,y?R。 ? 给出以下公式在I下的说明，并指出它们的真值： （2）?x?y,a)?G) 解：说明是：?x?y，含义是：对于随意的实数x，y，若x-y=0则xy。 该公式在I说明下的真值为假。 14、证明下面公式既不是永真式也不是冲突式： （1）?x?y?H) 解：取说明I如下：个体域为全总个体域， F：x是兔子，G：y是乌龟，H：x比y跑得快，则该公式在说明I下真值是1； 取说明I如下：H：x比y跑得慢，其它同上，则该公式在说明I下真值是0； 第20页 共20页第 20 页 共 20 页第 20 页 共 20 页第 20 页 共 20 页第 20 页 共 20 页第 20 页 共 20 页第 20 页 共 20 页第 20 页 共 20 页第 20 页 共 20 页第 20 页 共 20 页第 20 页 共 20 页