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

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

1、1 / 18 离散数学数理逻辑部分期末复习辅导一、单项选择题1设 P：我将去打球，Q：我有时间命题“我将去打球，仅当我有时间”符号化为( )APQ BQP CQP DQP复习： PQ 表示的逻辑关系是， P 是 Q 的充分条件，或Q是 P 的必要条件因此“只要P 则（就） Q”，“ P 仅当 Q”，“只有 Q才 P”等，都可用复合命题PQ 表示解 因为语句“我有时间”是“我将去打球”的必要条件，所以选项 B 是正确的 记住： “P 仅当 Q”即表示为 PQ答 B 问：如果把“我将去打球”改成“我将去市里”、“我将去旅游”等，会符号化吗？2设命题公式G：)(RQP，则使公式G 取真值为1的 P，

2、Q，R赋值分别是 ( )A0, 0, 0 B0, 0, 1 C0, 1, 0 D1, 0, 0 解 对于选项 A、B、C、D 中，Q R 的真值为 0，要使公式G 取真值为 1，必需P 的真值为 0，从而 P 的真值为 1，所以选项 D 是正确的答 D 若题目改为：设命题公式P(Q R)取真值为1，则P，Q，R 的赋值是答 1,0,0；1,0,1；1,1,0；1,1,1；0,1,1 3命题公式 (P Q)R的析取范式是 ( )精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 18 页2 / 18 A(P Q) R B(P Q) RC(P

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

4、取对析取 （析取对合取） 的分配律、结合律将公式归约为析取范式 （合取范式） (2) 除去析取 （合取） 范式中永假 （真） 的析取 （合取）项，并将析取 （合取） 范式中重复出现的合取 （析取） 项和相同变元合并(3) 对于不是小项 （大项） 的合取 （析取） 式，补入没有出现的命题变元，即通过合取（析取） 添加 (PP)（(PP)）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 18 页3 / 18 式，然后应用合取 （析取） 对析取 （合取） 的分配律展开公式(4) 合并相同的小项 （大项） ，并将小项 （大项） 按编码从小到大的

5、顺序排列，可用 （）表示之主析取范式与主合取范式的关系：一般地，若命题公式A的主析取范式为( i1, i2, , ik) 则公式 A的主合取范式为(0, 1, , i11, i1+1, , ik1, ik+1, , 2n1) 解RQPRQPRQP)()()(答 D 4命题公式 (P Q) 的合取范式是 ( )AP Q B(P Q) (P Q) CP Q D ( PQ) 答 C 5命题公式)(QP的析取范式是 ( )AQPBQPCQPDQP解()()PQPQPQ答 A 注意：第 3、4、5 题复习了合取范式和析取范式的概念，大家一定要记住的。如果题目改为求一个变元（P 或P）命题公式的合取范式或

6、析取范式，那么答案是什么？精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 18 页4 / 18 6下列等价公式成立的为 ( )APQP QBP(QP) P(PQ) CQ(P Q) Q (P Q) DP (P Q) Q解 APQ(P Q) BP(QP)P (Q P)P (P Q)P(PQ) CQ(P Q)Q (P Q) DP (P Q)( P P) (P Q)1 ( P Q)P Q答 B 7下列公式成立的为 ( )APQ P QBPQPQCQP P DP (P Q)Q解 APQ(P Q)BPQPQC(QP)P(Q P) P(QP) P(Q

7、 P) ( P P) (Q P) 1P Q（不是永真式）DP (P Q)Q（析取三段论， P171公式(10)）或者直接推导：P (P Q)Q(P (P Q) Q(P (PQ) Q(PP) (PQ) Q(PQ) Q精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 18 页5 / 18 P ( Q Q) P 1 1 所以P (P Q)Q答 D 8下列公式中 ( )为永真式AABABBAB(A B) CABA B DAB (A B) 解 由定理 6.5.3有，AB 的充分必要条件是AB 为永真式（重言式）AABAB，1ABABB()ABAB，

8、()1ABABCABAB，1ABABD()ABAB，()1ABAB答 B 9下列公式 ( )为重言式APQP QB(Q(P Q)( Q (P Q) C(P( QP)( P(PQ) D(P (P Q)Q解 APQPQ，1PQPQB()1QPQQPQ()()()()1QPQQPQQPQ()()1QPQQPQC()()PQPPQP精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 18 页6 / 18 ()()PPQPPQ所以， (P(QP)( P(PQ)1 D()()()PPQPPPQPQQ()1PPQQ答 C说明： (1) 如果本题题目改为“

9、下列公式 ( ) 为永真式 ”，应该是一样的(2) 上述两题也可以利用公式AB(AB) (BA)直接验证10设 A(x)：x是人， B(x)：x 是学生，则命题“不是所有人都是学生”可符号化为（）A(x)(A(x) B(x) B(x)(A(x) B(x) C(x)(A(x)B(x)D(x)(A(x)B(x)解 ( x)(A(x)B(x)表示“所有人都是学生”，它的否定即为公式 C答 C11设 A(x)：x 是人， B(x)：x 是工人，则命题“有人是工人”可符号化为（）A(x)(A(x) B(x) B(x)(A(x) B(x) C(x)(A(x)B(x)D(x)(A(x)B(x)答 A12设

10、C(x)：x 是国家级运动员， G(x)：x 是健壮的，则命题“没有一个国家级运动员不是健壮的”可符号化为 ( )A)()(xGxCx B)()(xGxCxC)()(xGxCxD)()(xGxCx精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 18 页7 / 18 答 D 13表达式)(),()(),(zzQyxRyzQyxPx中x的辖域是 ( )AP(x, y) BP(x, y) Q(z) CR(x, y) DP(x, y) R(x, y) 答 B 注意：如果该题改为判断题，即表达式)(),()(),(zzQyxRyzQyxPx中x的

11、辖域是 P(x, y)如何判断并说明理由呢？14在谓词公式 ( x)(A(x) B(x) C(x，y)中，（）Ax，y 都是约束变元Bx，y 都是自由变元Cx 是约束变元， y是自由变元Dx 是自由变元， y是约束变元答 C注：如果该题改为填写约束变元或自由变元的填空题，大家也应该掌握补充题： 设个体域为自然数集合，下列公式中是真命题的为 ( )A) 1(yxyx B)0(yxyxC)(xyxyx D)2(yyxyx解 因为选项A 表示：对任一自然数x 存在自然数y 满足xy=1，这样的 y 是不存在的精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第

12、 7 页，共 18 页8 / 18 选项 B 表示：对任一自然数x 存在自然数 y 满足 x+y=0，这样的 y也是不存在的选项 C 表示：存在一自然数x 对任意自然数y 满足 xy=x，取 x=0即可，故选项 C 正确选 项 D 表 示： 存在一 自 然数 x 对 任 意 自然 数 y 满 足x+y=2y，这样的 x 是不存在的答 C 15设个体域D= a, b, c，那么谓词公式)()(yyBxxA消去量词后的等值式为A(A(a) A(b) A(c) (B(a) B(b) B(c) B(A(a) A(b) A(c) (B(a) B(b) B(c) C(A(a) A(b) A(c) (B(a

13、) B(b) B(c) D(A(a) A(b) A(c) (B(a) B(b) B(c) 答 A 16命题公式QP的主合取范式是 ( )A)()()(QPQPQP BQPCQP DQP答 C 17下列等价公式成立的为 ( )AP PQ QBQPPQCP QP Q DP PQ解 AP P0Q QBQPP(Q)PQPQCP QP Q精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 18 页9 / 18 DP P1Q18命题公式QQP)(为 ( )A矛盾式 B可满足式 C重言式 D合取范式解()()()()PQQPQQPQQQPQ是可满足式答

14、B19谓词公式xA(x)xA(x)是（）A不可满足的 B可满足的C有效的 D蕴含式答 A 20前提条件PQP,的有效结论是 ( )APBPCQDQ答 D（假言推理）二、填空题1命题公式()PQP的真值是解()1PQPPQP答 1或 T 问：命题公式QQ、QQ的真值是什么？2设 P：他生病了， Q：他出差了， R：我同意他不参加学习则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为答()PQR一 般 地 ， 当 语 句 是 由 “ 如 果 ， 那 么 ” ， 或精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 18 页10 /

15、 18 “若，则”组成，它的符号化用条件联结词3含有三个命题变项P，Q，R 的命题公式P Q 的主析取范式是解()PQPQRR()()PQRPQR答()()PQRPQR4设 P(x)：x 是人， Q(x)：x 去上课，则命题“有人去上课”为答( ( )( )x P xQ x5设个体域D a,b, 那么谓词公式)()(yyBxxA消去量词后的等值式为答( ( )( )( )( )A aA bB aB b注：如果个体域是D1, 2，D=a, b, c ，或谓词公式变为 x(A(x) B(x)，怎么做？6设个体域D1, 2, 3，A(x)为“x 小于 3”，则谓词公式( x)A(x) 的真值为解 (

16、 x)A(x)A(1) A(2) A(3)1 1 01 答 1 注：若个体域 D1, 2，A(x)为“x 小于 3”，则谓词公式( x)A(x)的真值是什么？或：设个体域 D1, 2, 3 ，A(x)为“x 是奇数”，则谓词公式( x)A(x)的真值是什么？7谓词命题公式 ( x)(A(x) B(x) C(y)中的自由变元为答 y精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 18 页11 / 18 问：公式中的约束变元是什么 ?判断： 谓词命题公式 ( x)(A(x) B(x) C(y)中的自由变元为x，是否正确？为什么？8谓词命题

17、公式( x)(P(x)Q(x) R(x， y)中的约束变元为答 x三、公式翻译题1请将语句“今天是天晴”翻译成命题公式解 设 P：今天是天晴则命题公式为：P问：“今天不是天晴”的命题公式是什么？2请将语句“小王去旅游，小李也去旅游”翻译成命题公式解 设 P：小王去旅游， Q：小李去旅游则命题公式为：P Q注：语句中包含“也”、“且”、“但”等连接词，命题公式要用合取“” 3请将语句“如果明天天下雪，那么我就去滑雪”翻译成命题公式 解 设 P：明天天下雪，Q：我去滑雪则命题公式为：PQ4请将语句“他去旅游，仅当他有时间”翻译成命题公精选学习资料 - - - - - - - - - 名师归纳总结

18、- - - - - - -第 11 页，共 18 页12 / 18 式解 设 P：他去旅游， Q：他有时间则语句表示为PQ5请将语句“有人不去工作”翻译成谓词公式解 设 P(x)： x 是 人， Q(x) ：x 去 工作 则 语 句 表 示 为( )( )x P xQ x6请将语句“所有人都努力工作”翻译成谓词公式解 设 P(x)： x 是人， Q(x)：x 努力工作则语句表示为( ( )( )x P xQ x注意： 命题公式的翻译还要注意“不可兼或”的表示例如，教材第 164页的例 6“T2 次列车 5 点或 6点钟开”怎么翻译成命题公式？这里的“或”为不可兼或四、判断说明题（ 判断下列各题

19、，并说明理由）1命题公式PP的真值是 1解 错误PP是永假式（教材 167页的否定律）2命题公式P (PQ) P 为永真式解 正确()()PPQPPPQPPQPP)(1PP（否定律）或由真值表P Q P QPQP (PQ) P (PQ) P0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 1 0 1 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 18 页13 / 18 1 1 0 0 0 0 1 可知，该命题公式为永真式注：如果题目改为该命题公式为永假式，如何判断并说明理由？3谓词公式)(),()(xxPyxy

20、GxxP是永真式解 正确)(),()(xxPyxyGxxP( )( , )( )xP xyG x yxP x( )( )( ,)xP xxP xyG x y1( , )1yG x y4下面的推理是否正确，请给予说明(1) (x)A(x)B(x) 前提引入(2) A(y)B(y) US (1) 解 错因为 A(x)中的 x是约束变元，而B(x)中的 x 是自由变元，约束变元与自由变元不能混淆应为：(1) (x)A(x)B(x) 前提引入(2) ( u)A(u)B(x)T(1)换名规则(3) ( u)(A(u)B(x) T(2)量词辖域扩张(4) A(y)B(x)ES(3) 五、计算题1求 PQ

21、R 的析取范式、合取范式、主析取范式、主合取范式精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 18 页14 / 18 解 PQ RP Q R（析取范式、合取范式、主合取范式）(P (QQ) (RR) (PP) Q (RR) (PP) (QQ) R)（补齐命题变项）(P Q R) ( P QR) ( PQ R) (PQR) (P Q R) (P QR) ( P Q R) (P QR) (P Q R) (PQ R) ( P Q R) (PQ R) （对的 分 配律）(PQR) ( PQ R) (P QR) (P Q R) (PQ R)

22、(P QR) (P Q R) （主析取范式）解二（利用主析取范式与主合取范式的关系）PQ RP Q R（析取范式、合取范式、主合取范式）M100 m000m001m010m011m101m110m111(PQR) ( PQ R) (P QR) (P Q R) (PQ R) (P QR) (P Q R) （主析取范式）2求命题公式 (P Q)(R Q)的主析取范式、主合取范式解()()PQRQ()()PQRQ()PQQR（析取范式）()()PQRQQR（ 对 的分配律）()()PQRQQR()1PQR精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1

23、4 页，共 18 页15 / 18 PQR（主合取范式）（同上题）(PQR) ( PQ R) (P QR) (P Q R) (PQ R) (P QR) (P Q R) （ 主 析 取 范 式 ） （ 根 据 上题）解二（利用命题公式的真值表）列出命题公式 (P Q)(R Q)的真值表如下：P Q R P Q R Q (P Q)(R Q) 小项大项0 0 0 0 0 1 PQR0 0 1 0 1 1 PQ R0 1 0 1 1 1 P QR0 1 1 1 1 1 P Q R1 0 0 1 0 0 P Q R1 0 1 1 1 1 PQ R1 1 0 1 1 1 P QR1 1 1 1 1 1 P

24、 Q R表中所有小项的析取就是公式的主析取范式，所有大项的合取就是公式的主合取范式，故所求公式的主析取范式为：( PQR) (PQ R) ( P QR) ( P Q R) (PQ R) (P QR) (P Q R)，主合取范式为：P Q R注：如果题目只是求“析取范式”或“合取范式”，大家就不必再进一步求“主析取范式”或“主合取范式”例如：求(P Q)R或(P Q)(R Q)，PQ R的合取范式、析取范式解()PQR()PQR精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 18 页16 / 18 ()PQR（析取范式）()()PRQR

25、（合取范式）()()PQRQ()()PQRQ()PQQR（析取范式）()()PQRQQRPQR（合取范式）PQR()PQR（析取范式）()()PQPR（合取范式）3设谓词公式( ,)( , , )( , )x P x yzQ y x zyR y z（1）试写出量词的辖域；（2）指出该公式的自由变元和约束变元解 （1）量词x的辖域为( , )( , , )P x yzQ y x z，z的辖域为( , , )Q y x z，y的辖域为( , )R y z（2）自由变元为( , )( , , )P x yzQ y x z中的 y，( , )R y z中的z约束变元为( , )( , , )P x y

26、zQ y x z中的 x，( , , )Q y x z中的 z，( , )R y z中的 y4设个体域为D=a1, a2 ，求谓词公式y xP(x,y)消去量词后的等值式解12( , )( ,)( ,)y xP x yxP x axP x a精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 18 页17 / 18 11211222( (,)(,)( (,)(,)P a aP a aP a aP a a六、证明 题1试证明 (P(QR)P Q与(PQ)等价证明()PQRPQ()PQRPQ（蕴含等价）()PQRPQ（结合律）PQ（吸收律）(

27、)PQ（德摩根律）2试证明 ( x)(P(x) R(x)( x)P(x) ( x)R(x)证明 (1)( x)(P(x) R(x)P (2) P(a) R(a)ES(1) (3) P(a)T(2)（化简）(4) ( x)P(x)EG(3) (5)R(a)T(2)（化简）(6) ( x)R(x)EG(5) (7) x)P(x) ( x)R(x)T(4)(6)（合取引入）下面对本课程的考核做一些说明考核对象：本课程考核的是中央广播电视大学开放教育本科电气信息类计算机科学与技术专业的学生考核依据：以本课程的教案大纲（2007 年 6 月审定）和指定的参考教材为依据制定的本课程指定的参考教材是李伟生主

28、编的、中央广播电视大学出版社出版的离散数学考核方式：本课程的考核实行形成性考核和终结性考核相结精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 18 页18 / 18 合的方式其中终结性考核采用半开卷、纸质、笔试方式，试卷满分 100分半开卷考试允许考生携带指定的一张专用A4 纸（统一印制），考生可以将自己对全课程学习内容的总结归纳写在这张A4 纸上带入考场，作为答卷时参考考试时间： 90 分钟试卷类型及结构：单项选择题的分数占15，填空题的分数占15，公式翻译题的分数占12，判断说明题的分数占14，计算题的分数占36；证明题的分数占8单项选择题和填空题主要涉及基本概念、基本理论、重要性质和结论、公式及其简单计算单项选择题给出四个备选答案，其一是正确选项填空题只需填写正确结论，不写计算、推论过程或理由逻辑公式翻译题主要是利用命题逻辑的基本概念及命题联结词，将一个陈述句翻译成命题公式判断说明题是对给定的一个命题或结论作出对与错的判断，并给出简单的说明计算题主要考核学生的基本运算技能和速度，要求写出化简、计算过程证明题主要考查应用概念、性质、定理及重要结论进行逻辑推理的能力，要求写出推理过程精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 18 页