《2022年电大离散数学数理逻辑部分期末复习辅导 .docx》由会员分享，可在线阅读，更多相关《2022年电大离散数学数理逻辑部分期末复习辅导 .docx（30页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选学习资料 - - - - - - - - - 离散数学数理规律部分期末复习辅导一、单项挑选题1设 P：我将去打球,Q：我有时间命题“ 我将去打球,仅当我有时间” 符号化为 AQ P BP Q CP Q DP Q复习： PQ 表示的规律关系是, P 是 Q 的充分条件,或 Q是 P 的必要条件因此“ 只要 P 就（就） Q” ,“P 仅当 Q” ,“ 只有 Q 才 P” 等,都可用复合命题 PQ 表示解 由于语句“ 我有时间” 是“ 我将去打球” 的必要条件,所以选项 B 是正确的 记住： “ P 仅当 Q” 即表示为 PQ答 B 问： 假如把“ 我将去打球” 改成“ 我将去市里” 、“ 我
2、将去旅行” 等,会符号化吗？2设命题公式G：PQR ,就使公式G 取真值为1的 P,Q,R赋值分别是 A0, 0, 0 B0, 0, 1 C0, 1, 0 D1, 0, 0 解 对于选项 A、B、C、D 中,Q R 的真值为 0,要使公式G 取真值为 1,必需 项 D 是正确的答 D 如题目改为：P 的真值为 0,从而 P 的真值为 1,所以选设命题公式PQ R取真值为1,就P,Q,R 的赋值是答 1,0,0；1,0,1；1,1,0；1,1,1；0,1,1 3命题公式 P QR 的析取范式是 1 / 18 名师归纳总结 - - - - - - -第 1 页,共 18 页精选学习资料 - - -
3、 - - - - - - AP Q R BP Q RCP Q R D P Q R复习：范式：式：一个命题公式称为 析取 （合取） 范式 ,当且仅当它具有形A1 A2 An （A1 A2 An）,（n 1）其中 A1, A2, , An 均是由命题变元或其否定所组成的简单合取 （析取） 式对于给定的命题公式,假如有一个等价公式,它仅仅由 小项（大项） 的析取 （合取） 组成,就该等价式称为原式的 主析取（主合取） 范式 求命题公式的主析取 （主合取） 范式的推演步骤：1 第一将公式化为析取 （合取） 范式将公式中的联结词化归成, 及 P消去,利用（利用双条件等价式PQPQ Q包蕴等价式 PQ P
4、 Q 消去）前利用德 摩根律将否定符号 直接移到各个命题变元之利用合取对析取 （析取对合取） 的安排律、结合律将公式归约为析取范式 （合取范式） 2 除去析取 （合取） 范式中永假 （真） 的析取 （合取）项,并将析取 （合取） 范式中重复显现的合取 （析取） 项和相同 变元合并3 对于不是小项 （大项） 的合取 （析取） 式,补入没有出现的命题变元,即通过合取（析取） 添加 PP（ PP ）2 / 18 名师归纳总结 - - - - - - -第 2 页,共 18 页精选学习资料 - - - - - - - - - 式,然后应用合取 （析取） 对析取 （合取） 的安排律绽开公式4 合并相同的
5、小项 （大项） ,并将小项 （大项） 按编码从 小到大的次序排列,可用（）表示之主析取范式与主合取范式的关系：一般地,如命题公式 A 的主析取范式为i1, i2, , ik 就公式 A 的主合取范式为解P0, 1, i1 1, i1+1, , ik 1, ik+1, , 2n 1 QRPQRPQR答 D 4命题公式 P Q 的合取范式是 AP Q BP Q P Q CP Q D P Q 答 C 5命题公式QPPQ的析取范式是 QAPBQCPQDP解PQPQPQ答 A 留意：第 3、4、5 题复习了合取范式和析取范式的概念,大家肯定要记住的；假如题目改为求一个变元（P 或P）命题公式的合取范式或
6、析取范式,那么答案是什么？3 / 18 名师归纳总结 - - - - - - -第 3 页,共 18 页精选学习资料 - - - - - - - - - 6以下等价公式成立的为 APQP QP QPPQ BPQP PPQ CQP Q Q P Q DP P Q Q解 APQP Q BPQPP Q PP CQP QQ P Q 1 P QP QDP P Q P P P Q答 B 7以下公式成立的为 AP Q P QBP Q P QCQ P P DP P Q Q解 AP Q P QBP Q P QCQ P P Q P P Q P P Q P P P Q P 1 P Q（不是永真式）DP P Q Q（析
7、取三段论, P171公式 10）或者直接推导：P P Q Q P P Q QP P Q QP P P Q QP Q Q4 / 18 名师归纳总结 - - - - - - -第 4 页,共 18 页精选学习资料 - - - - - - - - - P Q Q P 1 1 所以P P QQ答 D 8以下公式中 为永真式AA B A BBA B A B CA B A B DA B A B 解 由定理 6.5.3 有, A B 的充分必要条件是 A B 为永真式（重言式）AABAAB ,ABBAAB1BABAB ,ABAB1CABB ,AABB11DABAB ,AB答 B 9以下公式 为重言式APQP
8、 QPPQ11BQP Q Q P Q CP QP PPQ DP P QQ解 APQPQ ,PQQB QPQQPQ1QPQQPQQQPQQPQ1CPQPP QP5 / 18 名师归纳总结 - - - - - - -第 5 页,共 18 页精选学习资料 - - - - - - - - - PPQPPQ所以, PQP PPQ1 PQQDPPQPPPQPPQQ1答 C说明： 1 假如此题题目改为“ 以下公式 应当是一样的 为永真式 ” ,2 上述两题也可以利用公式ABAB BA直接验证10设 Ax：x 是人, Bx：x 是同学,就命题“ 不是全部人都是同学” 可符号化为（）xAx Bx AxAx Bx
9、 BCxAxBxDxAxBx解 xAx 为公式 C答 CBx表示“ 全部人都是同学” ,它的否定即11设 Ax：x 是人, Bx：x 是工人,就命题“ 有人是工人” 可符号化为（）A xAx Bx B xAx Bx C xAx BxD xAx Bx答 A12设 Cx：x 是国家级运动员, Gx：x 是健壮的,就命题“ 没有一个国家级运动员不是健壮的” 可符号化为 AxCxGx BxCxGxCxCxGxDxCxGx 6 / 18 名师归纳总结 - - - - - - -第 6 页,共 18 页精选学习资料 - - - - - - - - - 答 D 13表达式xPx ,yQz yR x ,yzQ
10、 z 中x的辖域是 APx, y BPx, y Qz CRx, y DPx, y Rx, y 答 B 留意：假如该题改为判定题,即表达式xP x ,yQz yR x,yzQz 中x 的辖域是 Px, y如何判定并说明理由呢？14在谓词公式 xAx Bx Cx,y中,（）Ax,y 都是约束变元Bx,y 都是自由变元Cx 是约束变元, y 是自由变元Dx 是自由变元, y 是约束变元 答 C注： 假如该题改为填写约束变元或自由变元的填空题,大家也应当把握补充题： 设个体域为自然数集合,以下公式中是真命题的为 Axy xy1 Bxyxy0y 满意Cxyxyx Dxyxy2y解 由于选项A 表示：对任
11、一自然数x 存在自然数xy=1,这样的 y 是不存在的7 / 18 名师归纳总结 - - - - - - -第 7 页,共 18 页精选学习资料 - - - - - - - - - 选项 B 表示：对任一自然数 样的 y 也是不存在的x 存在自然数 y 满意 x+y=0,这选项 C 表示：存在一自然数x 对任意自然数y 满意 xy=x,取 x=0即可,应选项 C 正确 选 项 D 表 示 ： 存 在一 自 然 数 x 对 任 意 自 然 数 y 满 足 x+y=2y,这样的 x 是不存在的 答 C 15设个体域D= a, b, c ,那么谓词公式xA x yBy 消去量词后的等值式为AAa A
12、b Ac Ba Bb Bc BAa Ab Ac Ba Bb Bc CAa Ab Ac Ba Bb Bc DAa Ab Ac Ba Bb Bc 答 A 16命题公式PPQ的主合取范式是 PQAPQQPQ BCPQ DPQ答 C 17以下等价公式成立的为 AP PQ QBQPPQQCP QP Q DP PQQP解 AP P0Q QPBQPPQCP QP Q8 / 18 名师归纳总结 - - - - - - -第 8 页,共 18 页精选学习资料 - - - - - - - - - DP P1Q18命题公式PQQ为 A冲突式 B可满意式 C重言式 D合取范式解PQQPQQPQQQPQ是可满意式答 B
13、19谓词公式xAxxAx是（）A不行满意的 B可满意的C有效的 D包蕴式答 A 20前提条件 P Q , P 的有效结论是 APBPCQDQ答 D（假言推理）二、填空题1命题公式PQPP 的真值是解PQPQP1答 1 或 T 问：命题公式QQ、QQ的真值是什么？2设 P：他生病了, Q：他出差了, R：我同意他不参与学习就命题“ 假如他生病或出差了,我就同意他不参与学习” 符号化的结果为答 PQR如 果 , 那 么 ”, 或一 般 地 , 当 语 句 是 由 “9 / 18 名师归纳总结 - - - - - - -第 9 页,共 18 页精选学习资料 - - - - - - - - - “ 如
14、 ,就 ” 组成,它的符号化用条件联结词3含有三个命题变项P,Q,R 的命题公式P Q 的主析取范式是解PQPQRRPQRPQR答 PQR PQR4设 Px：x 是人, Qx：x 去上课,就命题“ 有人去上课” 为答x P x Q x xA xyBy 消去量5设个体域D a,b, 那么谓词公式词后的等值式为答 A b B a B b 注： 假如个体域是D1, 2 ,D=a, b, c ,或谓词公式变为 xAx Bx,怎么做？6设个体域D1, 2, 3 ,Ax为“ x 小于 3” ,就谓词公式 xAx 的真值为解 xAxA1 A2 A31 1 01 答 1 注： 如个体域 D1, 2,Ax为“
15、xAx的真值是什么？x 小于 3” ,就谓词公式或： 设个体域 D1, 2, 3 ,Ax为“ x 是奇数” ,就谓词公 式 xAx的真值是什么？7谓词命题公式 xAx Bx Cy中的自由变元为答 y10 / 18 名师归纳总结 - - - - - - -第 10 页,共 18 页精选学习资料 - - - - - - - - - 问： 公式中的约束变元是什么 .判定： 谓词命题公式 xAx Bx Cy中的自由变元为x,是否正确？为什么？为8谓词命题公式 xPxQx Rx, y 中的约束变元答 x三、公式翻译题1请将语句“ 今日是天晴” 翻译成命题公式解 设 P：今日是天晴就命题公式为：P问： “
16、 今日不是天晴” 的命题公式是什么？2请将语句“ 小王去旅行,小李也去旅行” 翻译成命题公式 解 设 P：小王去旅行, Q：小李去旅行就命题公式为：P Q注： 语句中包含“ 也” 、“ 且” 、“ 但” 等连接词,命题公式要用合取“”3请将语句“ 假如明每天下雪,那么我就去滑雪” 翻译成 命题公式 P解 设 P：明每天下雪,Q：我去滑雪就命题公式为：Q 4请将语句“ 他去旅行,仅当他有时间” 翻译成命题公11 / 18 名师归纳总结 - - - - - - -第 11 页,共 18 页精选学习资料 - - - - - - - - - 式解 设 P：他去旅行, Q：他有时间就语句表示为PQ 5请
17、将语句“ 有人不去工作” 翻译成谓词公式解 设 Px ： x 是 人 , Qx ： x 去 工 作 就 语 句 表 示 为x P x Q x 6请将语句“ 全部人都努力工作” 翻译成谓词公式解 设 Px： x 是人, Qx： x 努力工作就语句表示为x P x Q x 留意： 命题公式的翻译仍要留意“ 不行兼或” 的表示例如,教材第 164页的 例 6“ T2 次列车 5 点或 6点钟开”怎么翻译成命题公式？这里的“ 或” 为不行兼或四、判定说明题（ 判定以下各题,并说明理由）1命题公式 P P 的真值是 1解 错误P P 是永假式（教材 167 页的否定律）2命题公式 P P Q P 为永真
18、式解 正确PPQPPPQPPPQPPP1（否定律）或由真值表P Q P QP1 QP PQ P P1 Q P0 0 1 1 1 0 1 1 0 1 1 1 1 0 0 1 1 0 1 12 / 18 名师归纳总结 - - - - - - -第 12 页,共 18 页精选学习资料 - - - - - - - - - 1 1 0 0 0 0 1 可知,该命题公式为永真式注：假如题目改为该命题公式为永假式,如何判定并说明理由？3谓词公式xPxyGx,y xPx是永真式解 正确xPxyGx,yxPxxP x yG x y , xP x xP x xP x yG x y1yG x y , 14下面的推理
19、是否正确,请赐予说明1 xAx Bx 前提引入2 Ay By US 1 解 错由于 Ax中的 x 是约束变元,而 束变元与自由变元不能混淆应为：Bx中的 x 是自由变元,约1 xAx Bx 前提引入2 uAu BxT1换名规章3 uAuBx T2量词辖域扩张4 Ay BxES3 五、运算题1求 P Q R 的析取范式、合取范式、主析取范式、主合取范式13 / 18 名师归纳总结 - - - - - - -第 13 页,共 18 页精选学习资料 - - - - - - - - - 解 P Q RP Q R（析取范式、合取范式、主合取范式） P Q Q R R P P Q R R P P Q Q
20、R（补齐命题变项） P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R （对 的 分 配律）PQR PQ R P QR P Q R PQ R P QR P Q R （主析取范式）解二 （利用主析取范式与主合取范式的关系）PQ R（析取范式、合取范式、主合取范式）P Q RM100 m000 m001 m010 m011 m101 m110 m111PQR PQ R P QR P Q R PQ R P QR P Q R （主析取范式）2求命题公式 P Q解 PPQRQQRQR Q的主析取范式、主合取范式P
21、QQQR （析取范式）PR QQR （ 对 的安排律）PQR QQR PQR 114 / 18 名师归纳总结 - - - - - - -第 14 页,共 18 页精选学习资料 - - - - - - - - - PQR （主合取范式）（同上题）PQR PQ R P QR P Q R PQ R P QR P Q R （ 主 析 取 范 式 ） （ 根 据 上题）解二 （利用命题公式的真值表）列出命题公式 P QR Q的真值表如下：P Q R P Q R Q P QR Q 小项大项0 0 0 0 0 1 PQRP Q R0 0 1 0 1 1 PQ R0 1 0 1 1 1 P QR0 1 1 1
22、 1 1 P Q R1 0 0 1 0 0 1 0 1 1 1 1 PQ R1 1 0 1 1 1 P QR1 1 1 1 1 1 P Q R表中全部小项的析取就是公式的主析取范式,全部大项的合 取就是公式的主合取范式,故所求公式的主析取范式为： PQR PQ R P QR P Q R PQ R P QR P Q R,主合取范式为：P Q R注： 假如题目只是求“ 析取范式” 或“ 合取范式” ,大家就 不必再进一步求“ 主析取范式” 或“ 主合取范式” 例如：求P QR 或 P QR Q,PQ R 的合取范式、析取范式解 PPQRQR15 / 18 名师归纳总结 - - - - - - -第
23、 15 页,共 18 页精选学习资料 - - - - - - - - - PQR （析取范式） P R Q R （合取范式） P Q R Q P Q R Q P Q Q R （析取范式） P Q R Q Q R P Q R（合取范式）P Q RP Q R （析取范式） P Q P R （合取范式）3设谓词公式 x P x y zQ y x z , , yR y z （1）试写出量词的辖域；（2）指出该公式的自由变元和约束变元解 （1）量词 x 的辖域为 P x y , zQ y x z ,z 的辖域为 Q y x z ,y 的辖域为 R y z （2）自由变元为 P x y , zQ y x
24、z 中的 y,R y z 中的z约束变元为P x y , zQ y x z 中的 x,Q y x z 中的 z,R y z 中的 y4设个体域为D= a1, a2 ,求谓词公式y xPx,y消去量词后的等值式解y xP x y , xP x a 1xP x a 216 / 18 名师归纳总结 - - - - - - -第 16 页,共 18 页精选学习资料 - - - - - - - - - P a a 1P a a 1 P a a 2P a a 2六、证明 题1试证明 PQRP Q 与PQ等价证明 PQRPQPQRPQ（包蕴等价）PQRPQ（结合律）PQ（吸取律）（德 摩根律）PQ2试证明
25、xPx Rx 证明 1 xPx RxP 2 Pa RaES1 xPx xRx3 PaT2（化简）4 xPxEG3 5RaT2（化简）6 xRxEG5 7 xPx xRxT46（合取引入）下面对本课程的考核做一些说明考核对象：本课程考核的是中心广播电视高校开放训练本科电气信息类运算机科学与技术专业的同学考核依据：以本课程的教案大纲（2007 年 6 月审定）和指定的参考教材为依据制定的本课程指定的参考教材是李伟生主 编的、中心广播电视高校出版社出版的离散数学考核方式：本课程的考核实行形成性考核和终结性考核相结17 / 18 名师归纳总结 - - - - - - -第 17 页,共 18 页精选学
26、习资料 - - - - - - - - - 合的方式其中终结性考核采纳半开卷、纸质、笔试方式,试卷满分 100分半开卷考试答应考生携带指定的一张专用A4 纸（统一印制）,考生可以将自己对全课程学习内容的总结归纳写在这张 A4 纸上带入考场,作为答卷时参考考试时间： 90 分钟试卷类型及结构：单项挑选题的分数占15,填空题的分数占 15,公式翻译题的分数占 12,判定说明题的分数占 14,运算题的分数占 36；证明题的分数占 8单项挑选题 和填空题主要涉及基本概念、基本理论、重要性质和结论、公式 及其简洁运算单项挑选题给出四个备选答案,其一是正确选 项填空题只需填写正确结论,不写运算、推论过程或理由逻 辑公式翻译题主要是利用命题规律的基本概念及命题联结词,将 一个陈述句翻译成命题公式判定说明题是对给定的一个命题或 结论作出对与错的判定,并给出简洁的说明运算题主要考核学 生的基本运算技能和速度,要求写出化简、运算过程证明题主 要考查应用概念、性质、定理及重要结论进行规律推理的才能,要求写出推理过程18 / 18 名师归纳总结 - - - - - - -第 18 页,共 18 页