离散数学春学期数理逻辑综合练习辅导

1、离散数学2014春数理逻辑部分综合练习辅导一、单项选择题单项选择题主要是第6次形考作业的部分题目第6次作业还是由10个单项选择题组成，每小题10分，满分100分在每次作业在关闭之前，允许大家反复多次练习，系统将保留您的最好成绩，希望大家要多练几次，争取好成绩需要提醒大家的是每次练习的作业题目可能不一样，请大家一定要认真阅读题目1设P：我将去打球，Q：我有时间命题“我将去打球，仅当我有时间时”符号化为( )A B C D 因为语句“仅当我有时间时”是“我将去打球”的必要条件，一般地，当语句是由“，仅当”组成，它的符号化用条件联结词所以选项B是正确的正确答案：B问：如果把“我将去打球”改成“我将去

2、学习”、“我将去旅游”等，怎么符号化呢？2命题公式PQ的合取范式是 ( )APQ B（PQ）（PQ）CPQ D（PQ）复习合取范式的定义：定义 一个命题公式称为合取范式，当且仅当它具有形式： A1A2An ， （n1）其中A1，A2，An均是由命题变元或其否定所组成的析取式由此可知，选项B和D是错的又因为PQ 与PQ不是等价的，选项A是错的所以，选项C是正确的正确答案：C 3命题公式的析取范式是( ) A B C D复习析取范式的定义：定义 一个命题公式称为析取范式，当且仅当它具有形式： A1A2An ， （n1）其中A1，A2，An均是有命题变元或其否定所组成的合取式 由教材第167页中的蕴

3、含等价式知道，公式与是等价的，满足析取范式的定义，所以，选项A是正确的正确答案：A注意：第2，3题复习了合取范式和析取范式的概念，大家一定要记住的。如果题目改为求一个变元（P或P）命题公式的合取范式或析取范式，那么答案是什么？4下列公式成立的为( )APQ PQ BPQ PQ CQP P DP(PQ)Q 因为： P(PQ)Q（析取三段论，P171公式(10)） 所以，选项D是正确的正确答案：D 5下列公式 ( )为重言式APQPQ B(Q(PQ) (Q(PQ) C(P(QP)(P(PQ) D(P(PQ) Q由教材第167页中的蕴含等价式，得 (P(QP) P(Q P)，(P(PQ) P (PQ

4、) 所以，C是重言式，也就是永真式正确答案：C说明：如果题目改为“下列公式 ( )为永真式”，应该是一样的6设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) 由题设知道，A(x)B(x)表示只要是人，就是学生，而“不是所有”应该用全称量词的否定，即x，得到公式C正确答案：C7设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

5、)B(x) 选项A中的A(x)B(x)表示x是人，而且是工人，$x 表示存在一个人，有一个人，因此($x)(A(x)B(x)表示“有人是工人”正确答案：A注意：通过第6，7两题大家基本掌握了谓词公式的翻译，但大家还要掌握谓词公式的解释，譬如2013年7月份试题中的第5题：5设个体域为整数集，则公式x$y(x+y=0)的解释可为( )A存在一整数x有整数y满足x+y=0 B对任一整数x存在整数y满足x+y=0C存在一整数x对任意整数y满足x+y=0 D任一整数x对任意整数y满足x+y=0正确答案：B 8表达式中的辖域是( ) AP(x, y) BP(x, y)Q(z) CR(x, y) DP(x

6、, y)R(x, y) 所谓辖域是指“紧接于量词之后最小的子公式称为量词的辖域”那么看题中紧接于量词x之后最小的子公式是什么呢？显然是P(x, y)Q(z)，因此，选项B是正确的正确答案：B注意：如果该题改为判断题，即 表达式中的辖域是P(x, y)如何判断并说明理由呢？9在谓词公式(x)(A(x)B(x)C(x，y)中，（ ）Ax，y都是约束变元 Bx，y都是自由变元 Cx是约束变元，y都是自由变元 Dx是自由变元，y都是约束变元 约束变元就是受相应的量词约束的变元而自由变元就是不受任何量词约束的变元所以选项C是正确的正确答案：C注：如果该题改为填写约束变元或自由变元的填空题，大家也应该掌握

7、补充题：设个体域为自然数集合，下列公式中是真命题的为 ( )A B C D因为选项A表示：对任一自然数x存在自然数y满足xy=1，这样的y是不存在的 选项B表示：对任一自然数x存在自然数y满足x+y=0，这样的y也是不存在的 选项C表示：存在一自然数x自然数对任意自然数y满足xy=x，取x=0即可，故选项C正确正确答案：C 下面的内容主要是第7次形考作业的部分题目 二、填空题1命题公式的真值是 因为P(QP) 1，所以应该填写：1应该填写：1问：命题公式、的真值是什么？2设P：他生病了，Q：他出差了R：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 一般

8、地，当语句是由“如果，那么”，或“若，则”组成，它的符号化用条件联结词应该填写：(PQ)R3含有三个命题变项P，Q，R的命题公式PQ的主析取范式是 复习主析取范式的定义：定义 对于给定的命题变元，如果有一个等价公式，它仅仅有小项的析取组成，则该等价式称为原式的主析取范式而小项的定义是：定义 n个命题变元的合取式，称为布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次由小项的定义知道，命题公式PQ中缺少命题变项R与它的否定，因此，应该补上，即PQPQ (RR) (PQ R) (PQR)得到命题公式PQ的主析取范式应该填写：(PQR) (PQR)4设个体域Da, b,那

9、么谓词公式消去量词后的等值式为 因为在有限个体域下，消除量词的规则为：设Da1, a2, , an，则所以，应该填写：(A(a) A(b) (B(a) B(b)应该填写：(A(a) A(b) (B(a) B(b)注：如果个体域是D1, 2，D=a, b, c, 或谓词公式变为，怎么做?5设个体域D1, 2, 3，A(x)为“x小于3”，则谓词公式($x)A(x) 的真值为 因为 ($x)A(x)A(1)A(2)A(3)1101应该填写：1注：若个体域D1, 2，A(x)为“x小于3”，则谓词公式($x)A(x) 的真值是什么？或：设个体域D1, 2, 3，A(x)为“x是奇数”，则谓词公式($

10、x)A(x) 的真值是什么？6谓词命题公式(x)(A(x)B(x) C(y)中的自由变元为 因为自由变元就是不受任何量词约束的变元，在公式(x)(A(x)B(x) C(y)中，y是不受全称量词约束的变元所以应该填写：y应该填写：y问: 公式中的约束变元是什么?判断：谓词命题公式(x)(A(x)B(x) C(y)中的自由变元为x，是否正确?为什么?三、公式翻译题 1请将语句“今天是天晴”翻译成命题公式解：设P：今天是天晴； 则命题公式为： P 问：“今天不是天晴”的命题公式是什么？ 2请将语句“小王去旅游，小李也去旅游”翻译成命题公式 解：设 P：小王去旅游，Q：小李去旅游， 则命题公式为：P

11、Q 注：语句中包含“也”、“且”、“但”等连接词，命题公式要用合取“” 3请将语句“他去旅游，仅当他有时间”翻译成命题公式解：设 P：他去旅游，Q：他有时间， 则命题公式为：P Q 注意：命题公式的翻译还要注意“不可兼或”的表示 例如，教材第164页的例6 “T2次列车5点或6点钟开”怎么翻译成命题公式？这里的“或”为不可兼或 4请将语句“所有人都努力工作”翻译成谓词公式 解：设P(x)：x是人，Q(x)：x努力工作 谓词公式为： (x)(P(x) Q(x)四、判断说明题（判断下列各题，并说明理由） 1命题公式的真值是1解 错误因为是永假式（教材167页的否定律）2命题公式P(PQ)P为永真式

12、 解：正确 因为，由真值表PQPQPQP(PQ)P001111011011100111110001可知，该命题公式为永真式注：如果题目改为该命题公式为永假式，如何判断并说明理由？ 3下面的推理是否正确，请给予说明 (1) (x)A(x) B(x) 前提引入(2) A(y) B(y) US (1) 解：错第2步应为：A(y) B(x)因为A(x)中的x是约束变元，而B(x)中的x是自由变元，换名时，约束变元与自由变元不能混淆五计算题1求PQR的析取范式，合取范式、主析取范式，主合取范式分析： 定义 对于给定的命题变元，如果有一个等价公式，它仅仅有大项的合取组成，则该等价式称为原式的主合取范式 定

13、义 n个命题变元的析取式，称为布尔析取或大项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次解 析取范式，合取范式、主析取范式的定义前面复习过了，由教材167的蕴含等价式PQR PQR （析取范式、合取范式、主合取范式）(P(QQ)(RR)(PP)Q(RR)(PP)(QQ)R)（补齐命题变项）(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR) （对的分配律）(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR) （主析取范式）注意：如果题目只是求“析取范式”或“合取范式”，大家一定不要再进一步

14、求“主析取范式”或“主合取范式” 例如：求（PQ）R 或(PQ)(RQ)，PQR的合取范式、析取范式2设谓词公式（1）试写出量词的辖域；（2）指出该公式的自由变元和约束变元解 （1）量词的辖域为，的辖域为，的辖域为（2）自由变元为中的y，中的z约束变元为中的x，中的z，中的y 3设个体域为D=a1, a2，求谓词公式y$xP(x,y)消去量词后的等值式解：y$xP(x, y) ($xP(x, a1)($xP(x, a2) (P(a1, a1)P(a2, a1)(P(a1, a2)P(a2, a2) 六、证明题 1试证明命题公式 (P(QR)PQ与（PQ）等价 证：(P(QR)PQ(P(QR)PQ (PQR)P)Q PQ （吸收律） (PQ) （摩根律）注意，教材第6章的学习指导中的例题要认真学习，尤其是例5大家一定要重视。2试证明($x)(P(x)R(x)($x)P(x