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

离散数学数理逻辑部分期末复习辅导一、单项选择题1设P：我将去打球，Q：我有时间命题“我将去打球，仅当我有时间”符号化为( )A B C D复习：PQ表示的逻辑关系是，P是Q的充分条件，或Q是P的必要条件因此“只要P则（就）Q”，“P仅当Q”，“只有Q才P”等，都可用复合命题PQ表示解 因为语句“我有时间”是“我将去打球”的必要条件，所以选项B是正确的记住：“P仅当Q”即表示为PQ答 B问：如果把“我将去打球”改成“我将去市里”、“我将去旅游”等，会符号化吗？2设命题公式G：，则使公式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，必需Ø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,13命题公式(PÚQ)®R的析取范式是 ( )AØ(PÚQ)ÚR B(PÙQ)ÚRC(PÚQ)ÚR D(ØPÙØQ)ÚR复习：范式：一个命题公式称为析取（合取）范式，当且仅当它具有形式：A1ÚA2ÚÚAn （A1ÙA2ÙÙAn）， （n1）其中A1，A2，An均是由命题变元或其否定所组成的简单合取（析取）式对于给定的命题公式，如果有一个等价公式，它仅仅由小项（大项）的析取（合取）组成，则该等价式称为原式的主析取（主合取）范式求命题公式的主析取（主合取）范式的推演步骤：(1) 首先将公式化为析取（合取）范式 将公式中的联结词化归成Ø，Ù及Ú（利用双条件等价式P«QÛ(P®Q)Ù(Q®P)消去«，利用蕴含等价式P®Q ÛØPÚQ消去®） 利用德·摩根律将否定符号Ø直接移到各个命题变元之前 利用合取对析取（析取对合取）的分配律、结合律将公式归约为析取范式（合取范式）(2) 除去析取（合取）范式中永假（真）的析取（合取）项，并将析取（合取）范式中重复出现的合取（析取）项和相同变元合并(3) 对于不是小项（大项）的合取（析取）式，补入没有出现的命题变元，即通过合取（析取）添加(PÚØP)（(PÙØP)）式，然后应用合取（析取）对析取（合取）的分配律展开公式(4) 合并相同的小项（大项），并将小项（大项）按编码从小到大的顺序排列，可用（）表示之主析取范式与主合取范式的关系：一般地，若命题公式A的主析取范式为(i1, i2, , ik)则公式A的主合取范式为(0, 1, , i1-1, i1+1, , ik-1, ik+1, , 2n-1)解 答 D4命题公式 (PÚQ) 的合取范式是 ( )APÙQ B(PÙQ)Ú(PÚQ)CPÚQ DØ(ØPÙØQ)答 C5命题公式的析取范式是( )A B C D解 答 A注意：第3、4、5题复习了合取范式和析取范式的概念，大家一定要记住的。如果题目改为求一个变元（P或ØP）命题公式的合取范式或析取范式，那么答案是什么？6下列等价公式成立的为( )AØPÙØQÛPÚQBP®(ØQ®P) ÛØP®(P®Q)CQ®(PÚQ) ÛØQÙ(PÚQ)DØPÚ(PÙQ) ÛQ解 AØPÙØQÛØ(PÚQ)BP®(ØQ®P)ÛØPÚ(QÚP)Û PÚ(ØPÚQ)ÛØP®(P®Q)CQ®(PÚQ)ÛØQÚ(PÚQ)DØPÚ(PÙQ)Û(ØPÚP)Ù(ØPÚQ)Û1Ù(ØPÚQ)ÛØPÚQ答 B7下列公式成立的为( )AØPÙØQ ÛPÚQ BP®ØQ ÛØP®QCQ®P Þ P DØPÙ(PÚQ)ÞQ解 AØPÙØQÛØ(PÚQ)BP®ØQ ÛØPÚØQC(Q®P)®PÛØ(ØQÚP)ÚPÛ(QÙØP)ÚPÛ(QÚP)Ù(ØPÚP)Û(QÚP)Ù1ÛPÚQ（不是永真式）DØPÙ(PÚQ)ÞQ（析取三段论，P171公式(10)）或者直接推导：ØPÙ(PÚQ)®QÛØ(ØPÙ(PÚQ)ÚQÛ(PÚ(ØPÙØQ)ÚQÛ(PÚØP)Ù(PÚØQ)ÚQÛ(PÚØQ)ÚQÛPÚ(ØQÚQ)ÛPÚ1Û1所以 ØPÙ(PÚQ)ÞQ答 D8下列公式中 ( )为永真式AØAÙØB«ØAÚØB BØAÙØB«Ø(AÚB)CØAÙØB«AÚB DØAÙØB « Ø(AÙB)解 由定理6.5.3有，AÛB的充分必要条件是A«B为永真式（重言式）A，B，C，D，答 B9下列公式 ( )为重言式AØPÙØQ«PÚQB(Q®(PÚQ)«(ØQÙ(PÚQ)C(P®(ØQ®P)«(ØP®(P®Q)D(ØPÚ(PÙQ)«Q解 A，BC所以，(P®(ØQ®P)«(ØP®(P®Q)Û1D答 C说明：(1) 如果本题题目改为“下列公式 ( )为永真式”，应该是一样的(2) 上述两题也可以利用公式A«BÛ(A®B)Ù(B®A)直接验证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设C(x)：x是国家级运动员，G(x)：x是健壮的，则命题“没有一个国家级运动员不是健壮的”可符号化为 ( )A BC D答 D13表达式中的辖域是( )AP(x, y) BP(x, y)ÚQ(z)CR(x, y) DP(x, y)ÙR(x, y)答 B注意：如果该题改为判断题，即表达式中的辖域是P(x, y)如何判断并说明理由呢？14在谓词公式("x)(A(x)B(x)ÚC(x，y)中，（ ）Ax，y都是约束变元Bx，y都是自由变元Cx是约束变元，y是自由变元Dx是自由变元，y是约束变元答 C注：如果该题改为填写约束变元或自由变元的填空题，大家也应该掌握补充题：设个体域为自然数集合，下列公式中是真命题的为 ( )A BC D解 因为选项A表示：对任一自然数x存在自然数y满足xy=1，这样的y是不存在的选项B表示：对任一自然数x存在自然数y满足x+y=0，这样的y也是不存在的选项C表示：存在一自然数x对任意自然数y满足xy=x，取x=0即可，故选项C正确选项D表示：存在一自然数x对任意自然数y满足x+y=2y，这样的x是不存在的答 C15设个体域D=a, b, c，那么谓词公式消去量词后的等值式为 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)ÚB(b)ÚB(c)D(A(a)ÙA(b)ÙA(c)Ú(B(a)ÙB(b)ÙB(c)答 A16命题公式的主合取范式是( )A BC D答 C17下列等价公式成立的为( )AØPÙP ÛØQÙQ BØQ®PÛP®QCPÙQÛPÚQ DØPÚP ÛQ解 AØPÙPÛ0ÛØQÙQBØQ®PÛØP®Ø(ØQ)ÛØP®QP®QCPÙQPÚQDØPÚP Û1Q18命题公式为 ( )A矛盾式 B可满足式 C重言式 D合取范式解 是可满足式答 B19谓词公式xA(x)ØxA(x)是（ ）A不可满足的 B可满足的C有效的 D蕴含式答 A20前提条件的有效结论是( )AP BØP CQ DØQ答 D（假言推理）二、填空题1命题公式的真值是 解 答 1或T问：命题公式、的真值是什么？2设P：他生病了，Q：他出差了，R：我同意他不参加学习则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 答 一般地，当语句是由“如果，那么”，或“若，则”组成，它的符号化用条件联结词®3含有三个命题变项P，Q，R的命题公式PÙQ的主析取范式是 解 答 4设P(x)：x是人，Q(x)：x去上课，则命题“有人去上课”为 答 5设个体域Da, b,那么谓词公式消去量词后的等值式为 答 注：如果个体域是D1, 2，D=a, b, c，或谓词公式变为$x(A(x)ÚB(x)，怎么做？6设个体域D1, 2, 3，A(x)为“x小于3”，则谓词公式($x)A(x) 的真值为 解 ($x)A(x)ÛA(1)ÚA(2)ÚA(3)Û1Ú1Ú0Û1答 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问：公式中的约束变元是什么?判断：谓词命题公式("x)(A(x)ÙB(x)ÚC(y)中的自由变元为x，是否正确？为什么？8谓词命题公式("x)(P(x)Q(x)ÚR(x，y)中的约束变元为 答 x三、公式翻译题1请将语句“今天是天晴”翻译成命题公式解 设P：今天是天晴则命题公式为：P问：“今天不是天晴”的命题公式是什么？2请将语句“小王去旅游，小李也去旅游”翻译成命题公式解 设P：小王去旅游，Q：小李去旅游则命题公式为：PÙQ注：语句中包含“也”、“且”、“但”等连接词，命题公式要用合取“Ù” 3请将语句“如果明天天下雪，那么我就去滑雪”翻译成命题公式解 设P：明天天下雪，Q：我去滑雪则命题公式为：4请将语句“他去旅游，仅当他有时间”翻译成命题公式解 设P：他去旅游，Q：他有时间则语句表示为5请将语句“有人不去工作”翻译成谓词公式解 设P(x)：x是人，Q(x)：x去工作则语句表示为6请将语句“所有人都努力工作”翻译成谓词公式解 设P(x)：x是人，Q(x)：x努力工作则语句表示为注意：命题公式的翻译还要注意“不可兼或”的表示例如，教材第164页的例6 “T2次列车5点或6点钟开”怎么翻译成命题公式？这里的“或”为不可兼或四、判断说明题（判断下列各题，并说明理由）1命题公式的真值是1解 错误是永假式（教材167页的否定律）2命题公式ØPÙ(P®ØQ)ÚP为永真式解 正确（否定律）或 由真值表PQØPØQP®ØQØPÙ(P®ØQ)ØPÙ(P®ØQ)ÚP0011111011011110011011100001可知，该命题公式为永真式注：如果题目改为该命题公式为永假式，如何判断并说明理由？3谓词公式是永真式解 正确4下面的推理是否正确，请给予说明(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求P®QÚR的析取范式、合取范式、主析取范式、主合取范式解 P®QÚRÛØPÚQÚR （析取范式、合取范式、主合取范式）Û(ØPÙ(QÚØQ)Ù(RÚØR)Ú(PÚØP)ÙQÙ(RÚØR)Ú(PÚØP)Ù(QÚØ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)Ú(Ø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 （析取范式、合取范式、主合取范式）ÛM100Ûm000Úm001Úm010Úm011Úm101Úm110Úm111Û(ØPÙØQÙØR)Ú(ØPÙØQÙR)Ú(ØPÙQÙØR)Ú(ØPÙQÙR)Ú(PÙØQÙR)Ú(PÙQÙØR)Ú(PÙQÙR) （主析取范式）2求命题公式(PÚQ)®(RÚQ)的主析取范式、主合取范式解 （析取范式） （Ú对Ù的分配律） （主合取范式）（同上题）Û(ØPÙØQÙØR)Ú(ØPÙØQÙR)Ú(ØPÙQÙØR)Ú(ØPÙQÙR)Ú(PÙØQÙR)Ú(PÙQÙØR)Ú(PÙQÙR)（主析取范式）（根据上题）解二 （利用命题公式的真值表）列出命题公式(PÚQ)®(RÚQ)的真值表如下：PQRPÚQRÚQ(PÚQ)®(RÚQ)小项大项000001ØPÙØQÙØR001011ØPÙØQÙR010111ØPÙQÙØR011111ØPÙQÙR100100ØPÚQÚR101111PÙØQÙR110111PÙQÙØR111111PÙ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ÚQ)，P®QÙR的合取范式、析取范式解 （析取范式） （合取范式） （析取范式） （合取范式） （析取范式） （合取范式）3设谓词公式（1）试写出量词的辖域；（2）指出该公式的自由变元和约束变元解 （1）量词的辖域为，的辖域为，的辖域为（2）自由变元为中的y，中的z约束变元为中的x，中的z，中的y4设个体域为D=a1, a2，求谓词公式"y$xP(x,y)消去量词后的等值式解 六、证明题1试证明 (P®(QÚØR)ÙØPÙQ与Ø(PÚØQ)等价证明 （蕴含等价） （结合律） （吸收律） （德·摩根律）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月审定）和指定的参考教材为依据制定的本课程指定的参考教材是李伟生主编的、中央广播电视大学出版社出版的离散数学考核方式：本课程的考核实行形成性考核和终结性考核相结合的方式其中终结性考核采用半开卷、纸质、笔试方式，试卷满分100分半开卷考试允许考生携带指定的一张专用A4纸（统一印制），考生可以将自己对全课程学习内容的总结归纳写在这张A4纸上带入考场，作为答卷时参考考试时间：90分钟试题类型及结构：单项选择题的分数占15，填空题的分数占15，公式翻译题的分数占12，判断说明题的分数占14，计算题的分数占36；证明题的分数占8单项选择题和填空题主要涉及基本概念、基本理论、重要性质和结论、公式及其简单计算单项选择题给出四个备选答案，其一是正确选项填空题只需填写正确结论，不写计算、推论过程或理由逻辑公式翻译题主要是利用命题逻辑的基本概念及命题联结词，将一个陈述句翻译成命题公式判断说明题是对给定的一个命题或结论作出对与错的判断，并给出简单的说明计算题主要考核学生的基本运算技能和速度，要求写出化简、计算过程证明题主要考查应用概念、性质、定理及重要结论进行逻辑推理的能力，要求写出推理过程