2022年电大离散数学数理逻辑部分期末复习辅导.docx

《2022年电大离散数学数理逻辑部分期末复习辅导.docx》由会员分享，可在线阅读，更多相关《2022年电大离散数学数理逻辑部分期末复习辅导.docx（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品学习资源离散数学数理规律部分期末复习辅导一、单项挑选题1. 设 P：我将去打球， Q：我有时间命题“我将去打球，仅当我有时间”符号化为 欢迎下载精品学习资源A. QP B PQ C PQDPQ欢迎下载精品学习资源复习： PQ 表示的规律关系是， P 是 Q 的充分条件，或 Q 是 P 的必要条件因此“只要 P 就（就） Q”，“ P 仅当 Q”， “只有 Q 才 P”等，都可用复合命题 P Q 表示解 由于语句“我有时间”是“我将去打球”的必要条件，所以选项 B 是正确的 记住： “P 仅当 Q”即表示为 P Q 答 B问： 假如把“我将去打球”改成“我将去市里”、“我将去旅行”等，会符号

2、化吗？2. 设命题公式 G： PQR ，就使公式 G 取真值为 1的 P，Q，R赋值分别是 A0, 0, 0B 0, 0, 1C 0, 1, 0D1, 0, 0解 对于选项 A、B、C、D 中， Q R 的真值为 0，要使公式G 取真值为 1，必需 P 的真值为 0，从而 P 的真值为 1，所以选项 D 是正确的答 D如题目改为：设命题公式PQ R取真值为 1，就 P， Q， R 的赋值是答 1,0,0；1,0,1；1,1,0；1,1,1；0,1,13. 命题公式 P QR 的析取范式是 欢迎下载精品学习资源A. P QRBP Q RCP QRD PQ R复习： 范式：一个命题公式称为 析取

3、（合取） 范式 ，当且仅当它具有形式：A1A2 An （A1A2 An），（ n1）其中 A1， A2， An 均是由命题变元或其否定所组成的简单合取（析取） 式对于给定的命题公式，假如有一个等价公式，它仅仅由小项（大项） 的析取 （合取） 组成，就该等价式称为原式的主析取（主合取） 范式求命题公式的主析取 （主合取） 范式的推演步骤：(1) 第一将公式化为析取 （合取） 范式将公式中的联结词化归成， 及 （利用双条件等价式PQPQ QP 消去，利用包蕴等价式 PQP Q 消去 ）利用德摩根律将否定符号直接移到各个命题变元之前利用合取对析取 （析取对合取） 的安排律、结合律将公式归约为析取范式

4、 （合取范式） (2) 除去析取 （合取） 范式中永假 （真） 的析取 （合取） 项，并将析取 （合取） 范式中重复显现的合取 （析取） 项和相同变元合并(3) 对于不是小项 （大项） 的合取 （析取） 式，补入没有显现的命题变元，即通过合取 （析取） 添加 P P （ P P ）欢迎下载精品学习资源式，然后应用合取 （析取） 对析取（合取） 的安排律绽开公式(4) 合并相同的小项 （大项） ，并将小项 （大项） 按编码从小到大的次序排列，可用 （）表示之主析取范式与主合取范式的关系：一般地，如命题公式 A 的主析取范式为i1, i 2,i,k就公式 A 的主合取范式为欢迎下载精品学习资源 0

5、, 1,i1 ,1, i 1+1,i,k 1, i k+ 1, n2 1欢迎下载精品学习资源欢迎下载精品学习资源解 PQRPQRPQR欢迎下载精品学习资源答 D4. 命题公式 P Q 的合取范式是 AP QBP Q P QCP QD PQ答 C5. 命题公式 PQ 的析取范式是 欢迎下载精品学习资源A. PQ BPQ C PQ D PQ欢迎下载精品学习资源欢迎下载精品学习资源解 PQPQ欢迎下载精品学习资源PQ答 A留意：第 3、4、5 题复习了合取范式和析取范式的概念，大家肯定要记住的；假如题目改为求一个变元（P 或 P）命题公式的合取范式或析取范式，那么答案是什么？欢迎下载精品学习资源6.

6、 以下等价公式成立的为 ABP CQ D解 APQP QQPPPQP QQ P QP P QQPQP QBPCQD P答 BQPP Q PP P QPPQP QQ P QP QP P P Q1 PQP Q7以下公式成立的为 ACQ 解 A BPCQPQP QBPQPQPP D P P QQPQP QQPQPPQ PPQPPQ P PQ P 1PD P P QQ（不是永真式）Q（析取三段论， P171公式10）或者直接推导：P P QQP P QP PQPPPQQQ QPQ QP欢迎下载精品学习资源P Q Q P 11所以 P P QQ答 D8. 以下公式中 为永真式A. ABABB ABA B

7、C. ABA B D ABA B解 由定理 6.5.3 有， AB 的充分必要条件是 AB 为永真式（重言式）AABAB ，ABAB1BAB AB ，AB AB1CABAB ，ABAB1DAB AB ，AB AB1答 B9. 以下公式 为重言式 A PQP QBQP QQ P QCPQPPPQDP PQQ解 APQPQ ，PQPQ1B Q PQ QPQ1QPQ QPQQ PQ1Q PQ Q PQ 1C PQPPQP欢迎下载精品学习资源PPQP PQ所以， PQPPPQ1欢迎下载精品学习资源D. P PQPPP QPQQ欢迎下载精品学习资源PPQQ1答 C说明： 1 假如此题题目改为“以下公式

8、为永真式”， 应当是一样的2 上述两题也可以利用公式ABAB BA直接验证10. 设 Ax：x 是人， Bx：x 是同学，就命题“不是全部人都是同学”可符号化为（）AxAxBxB xAxBxC xAxBxD xAxBx解 xAxBx 表示“全部人都是同学”，它的否定即为公式 C答 C11. 设 Ax：x 是人， Bx： x 是工人，就命题“有人是工人”可符号化为（）AxAx BxBxAxBxC xAxBxD xAxBx答 A12. 设 Cx：x 是国家级运动员， Gx： x 是健壮的，就命题“没有一个国家级运动员不是健壮的”可符号化为欢迎下载精品学习资源A. xC xG xB. xCxG x欢

9、迎下载精品学习资源欢迎下载精品学习资源C. xC xG x DxC xG x欢迎下载精品学习资源答 D 13表达式的辖域是 xP x, yQ zyR x, yzQ z 中 x欢迎下载精品学习资源APx, yBPx, y QzCRx, yDPx, y Rx, y答 B留意：假如该题改为判定题，即欢迎下载精品学习资源表达式 域是 Px, yx P x, yQ zy R x, yzQ z中 x 的辖欢迎下载精品学习资源如何判定并说明理由呢？14在谓词公式 xAx BxCx， y中，（）Ax，y 都是约束变元Bx，y 都是自由变元Cx 是约束变元， y 是自由变元Dx 是自由变元， y 是约束变元答

10、C注： 假如该题改为填写约束变元或自由变元的填空题，大家也应当把握补充题： 设个体域为自然数集合，以下公式中是真命题的为 欢迎下载精品学习资源A. xC xy x y1y xyxB. xD xyxyxy0y2 y欢迎下载精品学习资源解 由于选项 A 表示：对任一自然数x 存在自然数 y 满意xy=1，这样的 y 是不存在的欢迎下载精品学习资源选项 B 表示：对任一自然数x 存在自然数 y 满意 x+y=0，这样的 y 也是不存在的选项 C 表示：存在一自然数 x 对任意自然数 y 满意 xy=x， 取 x=0 即可，应选项 C 正确选项 D 表示： 存在一 自 然数 x 对任意自然 数 y 满

11、 足x+y=2y，这样的 x 是不存在的答 C欢迎下载精品学习资源15. 设个体域 D= a, b, c ，那么谓词公式去量词后的等值式为xA xyB y 消欢迎下载精品学习资源AAaAbAcBaBbB cBAaAbAcBaBbBcCAaAbAcBaBbBcDAaAbAcBaBbB c欢迎下载精品学习资源答 A16. 命题公式 PQ 的主合取范式是 欢迎下载精品学习资源欢迎下载精品学习资源A. PQPQPQBPQ欢迎下载精品学习资源欢迎下载精品学习资源C PQ答 CD PQ欢迎下载精品学习资源17. 以下等价公式成立的为 A. P PQ QB QPPQCP QP Q D P PQ解 A P P

12、0Q QB. QPPQPQPQCP QP Q欢迎下载精品学习资源D P P1Q18. 命题公式 PQQ 为 A. 冲突式 B可满意式 C重言式 D合取范式解欢迎下载精品学习资源 PQQPQQPQQ QPQ欢迎下载精品学习资源是可满意式 答 B19. 谓词公式 xAxxAx是（） A不行满意的B可满意的 C有效的 D包蕴式答 A20. 前提条件 PQ, P 的有效结论是 APB PCQD Q答 D（假言推理）欢迎下载精品学习资源二、填空题1. 命题公式 PQP的真值是欢迎下载精品学习资源欢迎下载精品学习资源解 PQPPQP1欢迎下载精品学习资源欢迎下载精品学习资源答 1 或 T问：命题公式 QQ

13、 、 QQ 的真值是什么？欢迎下载精品学习资源2. 设 P：他生病了， Q：他出差了， R：我同意他不参与学习就命题“假如他生病或出差了，我就同意他不参与学习”符 号化的结果为答 PQR一 般 地 ， 当 语 句 是 由 “ 假如 ， 那 么 ” ， 或欢迎下载精品学习资源“如，就”组成，它的符号化用条件联结词3. 含有三个命题变项 P，Q，R 的命题公式 P Q 的主析取范式是欢迎下载精品学习资源解 PQPQ RR欢迎下载精品学习资源PQR PQR答 PQRPQR4. 设 Px： x 是人， Qx： x 去上课，就命题“有人去上课”为欢迎下载精品学习资源答x P xQ x欢迎下载精品学习资源

14、欢迎下载精品学习资源5. 设个体域 D a,b, 那么谓词公式词后的等值式为xA xyB y 消去量欢迎下载精品学习资源答 A aAb BaBb欢迎下载精品学习资源注： 假如个体域是D1, 2 ，D= a, b, c ，或谓词公式变为 xAx Bx，怎么做？6. 设个体域 D1, 2, 3 ，Ax为“ x 小于 3”，就谓词公式 xAx 的真值为解 xAxA1 A2A31 1 01答 1注： 如个体域 D1, 2 ，Ax为“ x 小于 3”，就谓词公式 xAx的真值是什么？或： 设个体域 D1, 2, 3 ，Ax为“ x 是奇数”，就谓词公式 xAx的真值是什么？7. 谓词命题公式 xAx B

15、xCy中的自由变元为 答 y欢迎下载精品学习资源问： 公式中的约束变元是什么 .判定： 谓词命题公式 xAx B x Cy 中的自由变元为x，是否正确？为什么？8. 谓词命题公式xPx Qx Rx， y 中的约束变元为答 x三、公式翻译题1. 请将语句“今日是天晴”翻译成命题公式解 设 P：今日是天晴就命题公式为：P 问： “今日不是天晴”的命题公式是什么？2. 请将语句“小王去旅行，小李也去旅行”翻译成命题公式解 设 P：小王去旅行， Q：小李去旅行就命题公式为： P Q注： 语句中包含“也”、“且”、“但”等连接词，命题公式要用合取“ ” 3. 请将语句“假如明每天下雪，那么我就去滑雪”翻

16、译成命题公式 解 设 P：明每天下雪， Q：我去滑雪就命题公式为：PQ 4. 请将语句“他去旅行，仅当他有时间”翻译成命题公欢迎下载精品学习资源式解 设 P：他去旅行， Q：他有时间就语句表示为 PQ 5. 请将语句“有人不去工作”翻译成谓词公式解 设 Px ： x 是 人， Qx ： x 去 工作 就语句表示为xP xQ x 6. 请将语句“全部人都努力工作”翻译成谓词公式解 设 Px： x 是人， Qx ： x 努力工作就语句表示为x P xQx 留意： 命题公式的翻译仍要留意“不行兼或”的表示例如，教材第 164 页的例 6“ T2 次列车 5 点或 6 点钟开” 怎么翻译成命题公式？这

17、里的“或”为不行兼或四、判定说明题（ 判定以下各题，并说明理由）1命题公式PP 的真值是 1解 错误 PP 是永假式（教材 167 页的否定律） 2命题公式 P PQ P 为永真式解 正确P PQPPPQPPPQP欢迎下载精品学习资源PP或由真值表1（否定律）欢迎下载精品学习资源PQPQPQPPQPPQ P001111101101111001101欢迎下载精品学习资源1100001可知，该命题公式为永真式注：假如题目改为该命题公式为永假式，如何判定并说明理欢迎下载精品学习资源由？3. 谓词公式解 正确xP x yG x, yxP x 是永真式欢迎下载精品学习资源xP x yG x, yxP x

18、欢迎下载精品学习资源欢迎下载精品学习资源xP xyG x, yxP x欢迎下载精品学习资源欢迎下载精品学习资源xP xxPxyG x, y欢迎下载精品学习资源1yG x, y14. 下面的推理是否正确，请赐予说明1 xAxBx前提引入2 AyByUS 1解 错由于 Ax中的 x 是约束变元，而 Bx中的 x 是自由变元，约束变元与自由变元不能混淆应为：(1) xAxBx前提引入(2) uAuBxT1换名规章(3) uAuBx T2量词辖域扩张4 AyBx ES3五、运算题1求 PQ R 的析取范式、合取范式、主析取范式、主合取范式欢迎下载精品学习资源解 PQ RP Q R（析取范式、合取范式、

19、主合取范式）P QQ RRPP Q RRPP QQR（补齐命题变项）P Q R P QRPQ R PQRP Q R P QRP Q R P QRP Q R PQ RP Q R PQ R（对的 分 配律）PQR PQ R P QR P Q RPQ R P QR P Q R（主析取范式） 解二（利用主析取范式与主合取范式的关系）PQ RP Q R（析取范式、合取范式、主合取范式）M100m000m001m010m011 m101m110m111PQR PQ R P QR P Q RPQ R P QR P Q R（主析取范式） 2求命题公式 P QR Q的主析取范式、主合取范式 解 PQRQPQRQ

20、PQQR （析取范式）PQRQQR （ 对 的安排律）PQRQQRPQR1欢迎下载精品学习资源PQR （主合取范式）（同上题）PQR PQ R P QR P Q RPQ R P QR P Q R（ 主 析取范式 ） （ 依据 上题）解二（利用命题公式的真值表）列出命题公式 P QR Q的真值表如下：PQRP QR QPQRQ小项大项000001PQR001011PQR010111P QR011111P QR100100P QR101111PQR110111P QR111111P Q R表中全部小项的析取就是公式的主析取范式，全部大项的合取就是公式的主合取范式，故所求公式的主析取范式为：PQR

21、PQ R P QR P Q RPQ R P QR P Q R，主合取范式为：P Q R注： 假如题目只是求“析取范式”或“合取范式”，大家就不必再进一步求“主析取范式”或“主合取范式”例如：求 P QR 或P QR Q， PQ R 的合取范式、析取范式解 PQRPQR欢迎下载精品学习资源PQPRR （析取范式）QR （合取范式）欢迎下载精品学习资源 PQRQPQRQPQQR （析取范式）PQRQQRPQR（合取范式） PQRPQR （析取范式）PQPR （合取范式）欢迎下载精品学习资源3. 设谓词公式xP x, yzQ y, x, zyR y, z 欢迎下载精品学习资源（1） 试写出量词的辖域

22、；（2） 指出该公式的自由变元和约束变元欢迎下载精品学习资源解 （1）量词 x 的辖域为Px, yzQ y, x, z ，欢迎下载精品学习资源欢迎下载精品学习资源z 的辖域为y 的辖域为Q y, x, z ，R y, z 欢迎下载精品学习资源（ 2）自由变元为zPx, yzQ y, x, z 中的 y， R y, z 中的欢迎下载精品学习资源欢迎下载精品学习资源约束变元为R y, z 中的 yP x, yzQ y, x, z 中的 x， Q y, x, z中的 z，欢迎下载精品学习资源4. 设个体域为 D= a1, a2 ，求谓词公式 y xPx,y消去量词后的等值式欢迎下载精品学习资源解 y

23、 xP x, yxP x, a1xPx, a2 欢迎下载精品学习资源Pa1,a1Pa2, a1 P a1, a2P a2, a2欢迎下载精品学习资源六、证明 题1试证明 PQRP Q 与 PQ等价证明 PQRPQPQRPQ（包蕴等价）欢迎下载精品学习资源PQRPQ（结合律）欢迎下载精品学习资源PQ（吸取律）PQ（德摩根律）2试证明 xPx Rx xPx xRx 证明 1 xPx RxP2 Pa RaES13 PaT2（化简） 4 xPxEG3 5RaT2（化简） 6 xRxEG57xPx xRxT46（合取引入）下面对本课程的考核做一些说明考核对象：本课程考核的是中心广播电视高校开放训练本科电

24、气信息类运算机科学与技术专业的同学考核依据：以本课程的教案大纲（2007 年 6 月审定）和指定的参考教材为依据制定的本课程指定的参考教材是李伟生主编的、中心广播电视高校出版社出版的离散数学考核方式：本课程的考核实行形成性考核和终结性考核相结欢迎下载精品学习资源合的方式其中终结性考核采纳半开卷、纸质、笔试方式，试卷满分 100 分半开卷考试答应考生携带指定的一张专用A4 纸（统一印制），考生可以将自己对全课程学习内容的总结归纳写在这张A4 纸上带入考场，作为答卷时参考 考试时间： 90 分钟试卷类型及结构：单项挑选题的分数占15，填空题的分数占 15，公式翻译题的分数占12，判定说明题的分数占14，运算题的分数占 36；证明题的分数占 8单项挑选题和填空题主要涉及基本概念、基本理论、重要性质和结论、公式 及其简洁运算单项挑选题给出四个备选答案，其一是正确选项填空题只需填写正确结论，不写运算、推论过程或理由规律公式翻译题主要是利用命题规律的基本概念及命题联结词，将一个陈述句翻译成命题公式判定说明题是对给定的一个命题或结论作出对与错的判定，并给出简洁的说明运算题主要考核同学的基本运算技能和速度，要求写出化简、运算过程证明题主要考查应用概念、性质、定理及重要结论进行规律推理的才能， 要求写出推理过程欢迎下载