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

1、离散数学数理逻辑部分期末复习辅导一、单项选择题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

2、解 对于选项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复习：范式：一个命题公式称为析取（合

3、取）范式，当且仅当它具有形式：A1ÚA2ÚÚAn （A1ÙA2ÙÙAn）， （n1）其中A1，A2，An均是由命题变元或其否定所组成的简单合取（析取）式对于给定的命题公式，如果有一个等价公式，它仅仅由小项（大项）的析取（合取）组成，则该等价式称为原式的主析取（主合取）范式求命题公式的主析取（主合取）范式的推演步骤：(1) 首先将公式化为析取（合取）范式 将公式中的联结词化归成Ø，Ù及Ú（利用双条件等价式P«QÛ(P®Q)Ù(Q®P)消去«，利用蕴

4、含等价式P®Q ÛØPÚQ消去®） 利用德·摩根律将否定符号Ø直接移到各个命题变元之前 利用合取对析取（析取对合取）的分配律、结合律将公式归约为析取范式（合取范式）(2) 除去析取（合取）范式中永假（真）的析取（合取）项，并将析取（合取）范式中重复出现的合取（析取）项和相同变元合并(3) 对于不是小项（大项）的合取（析取）式，补入没有出现的命题变元，即通过合取（析取）添加(PÚØP)（(PÙØP)）式，然后应用合取（析取）对析取（合取）的分配律展开公式(4) 合并相同的小项（大项），并

5、将小项（大项）按编码从小到大的顺序排列，可用（）表示之主析取范式与主合取范式的关系：一般地，若命题公式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题复习了合取范式和析取范式的概念，大家一定要记住的。如果

6、题目改为求一个变元（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)Û

7、;Ø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 B

8、P®Ø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

9、Ú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Ú

10、;(Ø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)解 由定理有，AÛB的充分必要条件是A«B为永真式（重言式）

11、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) 如果本题题目改为“下列公式 ( )为永真式”，应

12、该是一样的(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是工人，则命题“有人是工人”可符

13、号化为（ ）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在谓词公式(&q

14、uot;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是

15、不存在的答 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下列

16、等价公式成立的为( )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矛盾

17、式 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的主析取范式是

18、 解 答 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(

19、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：小

20、王去旅游，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

21、 “T2次列车5点或6点钟开”怎么翻译成命题公式？这里的“或”为不可兼或四、判断说明题（判断下列各题，并说明理由）1命题公式的真值是1解 错误是永假式（教材167页的否定律）2命题公式ØPÙ(P®ØQ)ÚP为永真式解 正确（否定律）或 由真值表PQØPØQP®ØQØPÙ(P®ØQ)ØPÙ(P®ØQ)ÚP0011111011011110011011100001可知，该命题公式为永真式注：如果题目改为该命题公式为永假式，

22、如何判断并说明理由？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的析取范式、合取

23、范式、主析取范式、主合取范式解 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

24、7;Ø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

25、17;Ø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Ú

26、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)Ú

27、;(PÙQÙØR)Ú(PÙQÙR) （主析取范式）2求命题公式(PÚQ)®(RÚQ)的主析取范式、主合取范式解 （析取范式） （Ú对Ù的分配律） （主合取范式）（同上题）Û(ØPÙØQÙØR)Ú(ØPÙØQÙR)Ú(ØPÙQÙØR)Ú(ØPÙQÙR)Ú(PÙØ

28、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Ù

29、;QÙR100100ØPÚQÚR101111PÙØQÙR110111PÙQÙØR111111PÙQÙR表中所有小项的析取就是公式的主析取范式，所有大项的合取就是公式的主合取范式，故所求公式的主析取范式为：(ØPÙØQÙØR)Ú(ØPÙØQÙR)Ú(ØPÙQÙØR)Ú(ØPÙQÙR)

30、8;(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）指出该公式的自由变