《2012逻辑部分作业辅导》由会员分享，可在线阅读，更多相关《2012逻辑部分作业辅导（8页珍藏版）》请在金锄头文库上搜索。
1、离散数学离散数学 2012 春学期数理逻辑部分形考作业辅导春学期数理逻辑部分形考作业辅导下面是本学期第 6，7 次形考作业中的部分题目一、单项选择题一、单项选择题单项选择题主要是第 6 次形考作业的部分题目第 6 次作业还是由 10 个单项选择题组成，每小题 10 分，满分 100 分在每次作业在关闭之前，允许大家反复多次练习，系统将保留您的最好成绩，希望大家要多练几次，争取好成绩需要提醒大家的是每次练习的作业题目可能不一样，请大家一定要认真阅读题目1设 P：我将去打球，Q：我有时间命题“我将去打球，仅当我有时间时”符号化为( )A B C DPQ QP QP QP因为语句“仅当我有时间时”是
2、“我将去打球”的必要条件，一般地，当语句是由“，仅当”组成，它的符号化用条件联结词所以选项 B是正确的正确答案：B问：如果把“我将去打球”改成“我将去学习”、“我将去旅游”等，怎么符号化呢？2命题公式 PQ 的合取范式是 ( )APQ B（PQ）（PQ）CPQ D（PQ）复习合取范式的定义：定义 6.6.2 一个命题公式称为合取范式，当且仅当它具有形式： A1A2An ， （n1）其中 A1，A2，An均是由命题变元或其否定所组成的析取式由此可知，选项 B 和 D 是错的又因为 PQ 与 PQ 不是等价的，选项A 是错的所以，选项 C 是正确的正确答案：C3命题公式的析取范式是( )(QP A
3、 B C DQPQP QPQP复习析取范式的定义：定义 6.6.3 一个命题公式称为析取范式，当且仅当它具有形式： A1A2An ， （n1）其中 A1，A2，An均是有命题变元或其否定所组成的合取式 由教材第 167 页中的蕴含等价式知道，公式与是等价的，)(QP QP满足析取范式的定义，所以，选项 A 是正确的QP正确答案：A注：第 2，3 题复习了合取范式和析取范式的概念，大家一定要记住的。如果题目改为求一个变元（P 或P）命题公式的合取范式或析取范式，那么答案是什么？4下列公式成立的为( )APQ PQ BPQ PQCQP P DP(PQ)Q因为： P(PQ)Q（析取三段论，P171
4、公式(10)）所以，选项 D 是正确的正确答案：D5下列公式 ( )为重言式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) 所以，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
5、)表示只要是人，就是学生，而“不是所有”应该用全称量词的否定，即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)B(x)选项 A 中的 A(x)B(x)表示 x 是人，而且是工人，x 表示存在一个人，有一个人，因此(x)(A(x)B(x)表示“有人是工人”正确答案：A8表达式中的辖域是( )(),()(),(zzQyxRyzQyxPxxAP(x, y) BP(x, y)Q(z) CR(x, y) DP(x, y)R(x, y)所
6、谓辖域是指“紧接于量词之后最小的子公式称为量词的辖域”那么看题中紧接于量词x 之后最小的子公式是什么呢？显然是 P(x, y)Q(z)，因此，选项 B 是正确的正确答案：B注：如果该题改为判断题，即表达式中的辖域是 P(x, y)(),()(),(zzQyxRyzQyxPxx如何判断并说明理由呢？9在谓词公式(x)(A(x)B(x)C(x，y)中， （ ） Ax，y 都是约束变元 Bx，y 都是自由变元Cx 是约束变元，y 都是自由变元 Dx 是自由变元，y 都是约束变元约束变元就是受相应的量词约束的变元而自由变元就是不受任何量词约束的变元所以选项 C 是正确的正确答案：C注：注：如果该题改为
7、填写约束变元或自由变元的填空题，大家也应该掌握补充题：设个体域为自然数集合，下列公式中是真命题的为 ( )A B ) 1(yxyx)0(yxyxC D)(xyxyx)2(yyxyx因为选项 A 表示：对任一自然数 x 存在自然数 y 满足 xy=1，这样的 y 是不存在 的选项 B 表示：对任一自然数 x 存在自然数 y 满足 x+y=0，这样的 y 也是不 存在的选项 C 表示：存在一自然数 x 自然数对任意自然数 y 满足 xy=x，取 x=0 即 可，故选项 C 正确 正确答案：C 下面的内容主要是第 7 次形考作业的部分题目二、填空题二、填空题1命题公式的真值是 ()PQP因为P(QP
8、) 1，所以应该填写：1()PQP应该填写：1问：命题公式、的真值是什么？QQ QQ2设 P：他生病了，Q：他出差了R：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 一般地，当语句是由“如果，那么”，或“若，则”组成，它的符号化用条件联结词应该填写：(PQ)R3含有三个命题变项 P，Q，R 的命题公式 PQ 的主析取范式是 复习主析取范式的定义：定义 6.6.5 对于给定的命题变元，如果有一个等价公式，它仅仅有小项的析取组成，则该等价式称为原式的主析取范式而小项的定义是：定义 6.6.4 n 个命题变元的合取式，称为布尔合取或小项，其中每个变元与它的否
9、定不能同时存在，但两者必须出现且仅出现一次由小项的定义知道，命题公式 PQ 中缺少命题变项 R 与它的否定，因此，应该补上，即PQPQ (RR) (PQ R) (PQR)得到命题公式 PQ 的主析取范式应该填写：(PQR) (PQR)4设个体域 Da, b,那么谓词公式消去量词后的等值式为 )()(yyBxxA因为在有限个体域下，消除量词的规则为：设 Da1, a2, , an，则)(.)()()(21naAaAaAxxA)(.)()()(21naAaAaAxxA所以，应该填写：(A(a) A(b) (B(a) B(b)应该填写：(A(a) A(b) (B(a) B(b)注：如果个体域是 D1
10、, 2，D=a, b, c, 或谓词公式变为，怎( ( )( )x A xB x么做?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 是奇数”，则谓词公式(x)A(x) 的真值是什么？6谓词命题公式(x)(A(x)B(x) C(y)中的自由变元为 因为自由变元就是不受任何量词约束的变元，在公式(x)(A(x)B(x) C(y)中，y 是不受全称量
11、词约束的变元所以应该填写：y应该填写：y问: 公式中的约束变元是什么?判断：谓词命题公式(x)(A(x)B(x) C(y)中的自由变元为 x，是否正确?为什么?三、公式翻译题1请将语句“今天是天晴”翻译成命题公式解：设 P：今天是天晴； 则命题公式为： P 问：问：“今天不是天晴”的命题公式是什么？2请将语句“小王去旅游，小李也去旅游”翻译成命题公式 解：设 P：小王去旅游，Q：小李去旅游， 则命题公式为：P Q 注：注：语句中包含“也”、“且”、“但”等连接词，命题公式要用合取“” 3请将语句“他去旅游，仅当他有时间”翻译成命题公式解：设 P：他去旅游，Q：他有时间， 则命题公式为：P Q
12、注：注：命题公式的翻译还要注意“不可兼或”的表示例如，教材第 164 页的例 6 “T2 次列车 5 点或 6 点钟开”怎么翻译成命题公式？这里的“或”为不可兼或4请将语句“所有人都努力工作”翻译成谓词公式解解：设 P(x)：x 是人，Q(x)：x 努力工作 谓词公式为： (x)(P(x) Q(x)四、判断说明题（判断下列各题，并说明理由）1命题公式的真值是 1PP解解 错误因为是永假式（教材 167 页的否定律）PP2命题公式P(PQ)P 为永真式 解：正确因为，由真值表PQPQPQP(PQ)P001111 011011 100111 110001可知，该命题公式为永真式注：如果题目改为该命
13、题公式为永假式，如何判断并说明理由？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 的析取范式，合取范式、主析取范式，主合取范式分析： 定义 6.6.7 对于给定的命题变元，如果有一个等价公式，它仅仅有大项的合取组成，则该等价式称为原式的主合取范式 定义 6.6.6 n 个命题变元的析取式，称为布尔析取或大项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次解解 析取范式，合取范式、主析取范式的定义前面复习过了，由教材 167的蕴含等价式PQR PQR （析取范式、合取范式、主合取范式）(P(QQ)(RR)(PP)Q(RR)
