koorio.com
海量文库 文档专家
赞助商链接
当前位置:首页 >> 数学 >>

离散数学2014春学期数理逻辑综合练习辅导-6.26 (1)


离散数学 2014 春数理逻辑部分综合练习辅导
一、单项选择题 单项选择题主要是第 6 次形考作业的部分题目. 第 6 次作业还是由 10 个单项选择题组成,每小题 10 分,满分 100 分.在每 次作业在关闭之前,允许大家反复多次练习,系统将保留您的最好成绩,希望大 家要多练几次, 争取好成绩. 需要提醒大家的是每次练习的作业题目可能不一样, 请大家一定要认真阅读题目. 1.设 P:我将去打球,Q:我有时间.命题“我将去打球,仅当我有时间时” 符号化为( A.Q ? P ). B.P ? Q C.P ? Q D.?P ? ?Q

因为语句“仅当我有时间时”是“我将去打球”的必要条件,一般地,当语 句是由“??,仅当??”组成,它的符号化用条件联结词?.所以选项 B 是 正确的. 正确答案:B 问:如果把“我将去打球”改成“我将去学习”、“我将去旅游”等,怎么符号 化呢? 2.命题公式 P?Q 的合取范式是 ( A.P?Q C.P?Q 复习合取范式的定义: 定义 6.6.2 一个命题公式称为合取范式,当且仅当它具有形式: A1∧A2∧?∧An , (n ? 1) 其中 A1,A2,?,An 均是由命题变元或其否定所组成的析取式. 由此可知,选项 B 和 D 是错的.又因为 P?Q 与 P?Q 不是等价的,选项 A 是错的.所以,选项 C 是正确的. 正确答案:C 3.命题公式 ?( P ? Q) 的析取范式是( A. P ? ?Q B ?P ? Q 复习析取范式的定义: 定义 6.6.3 一个命题公式称为析取范式,当且仅当它具有形式: A1∨A2∨?∨An , (n ? 1) 其中 A1,A2,?,An 均是有命题变元或其否定所组成的合取式. 由教材第 167 页中的蕴含等价式知道,公式 ?( P ? Q) 与 P ? ?Q 是等价的,
P ? ?Q 满足析取范式的定义,所以,选项 A 是正确的.

). B.(P?Q)?(P?Q) D.?(?P??Q)

). C. ?P ? Q D. P ? ?Q

1

正确答案:A 注意:第 2,3 题复习了合取范式和析取范式的概念,大家一定要记住的。如果 题目改为求一个变元(P 或?P)命题公式的合取范式或析取范式,那么答案是 什么? 4.下列公式成立的为( A.?P??Q ? P?Q C.Q?P ? P 所以,选项 D 是正确的. 正确答案:D 5.下列公式 ( A.?P??Q?P?Q C.(P?(?Q?P))?(?P?(P?Q)) 由教材第 167 页中的蕴含等价式,得 (P?(?Q?P)) ??P?(Q? P),(?P?(P?Q)) ? P? (?P?Q) 所以,C 是重言式,也就是永真式. 正确答案:C 说明:如果题目改为“下列公式 ( 可符号化为( ). B.?( ? x)(A(x)?B(x)) D.?( ? x)(A(x)??B(x)) )为永真式”,应该是一样的. 6.设 A(x):x 是人,B(x):x 是学生,则命题“不是所有人都是学生” A.( ? x)(A(x)?B(x)) C.?(?x)(A(x)?B(x)) 全称量词的否定,即??x,得到公式 C. 正确答案:C 7.设 A(x):x 是人,B(x):x 是工人,则命题“有人是工人”可符号化 为( ). A.(?x)(A(x)?B(x)) C.?(?x)(A(x)?B(x)) B.(?x)(A(x)?B(x)) D.?(?x)(A(x)??B(x)) )为重言式. B.(Q?(P?Q)) ?(?Q?(P?Q)) D.(?P?(P?Q)) ?Q ). B.P??Q ? ?P?Q D.?P?(P?Q)?Q

因为: ?P?(P?Q)?Q(析取三段论,P171 公式(10))

由题设知道,A(x)?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)的解释可为( ).

2

A.存在一整数 x 有整数 y 满足 x+y=0 B.对任一整数 x 存在整数 y 满足 x+y=0 C.存在一整数 x 对任意整数 y 满足 x+y=0 D.任一整数 x 对任意整数 y 满足 x+y=0 正确答案:B 8.表达式 ?x( P( x, y) ? Q( z )) ? ?y( R( x, y) ? ?zQ( z )) 中 ?x 的辖域是( A.P(x, y) B.P(x, y)?Q(z) C.R(x, y) ). D.P(x, y)?R(x, y)

所谓辖域是指“紧接于量词之后最小的子公式称为量词的辖域”.那么看题 中紧接于量词?x 之后最小的子公式是什么呢?显然是 P(x, y)?Q(z),因此,选项 B 是正确的. 正确答案:B 注意:如果该题改为判断题,即 表达式 ?x( P( x, y) ? Q( z )) ? ?y( R( x, y) ? ?zQ( z )) 中 ?x 的辖域是 P(x, y) 如何判断并说明理由呢? 9.在谓词公式(?x)(A(x)→B(x)?C(x,y))中, ( A.x,y 都是约束变元 C.x 是约束变元,y 都是自由变元 的变元.所以选项 C 是正确的. 正确答案:C 注:如果该题改为填写约束变元或自由变元的填空题,大家也应该掌握. 补充题:设个体域为自然数集合,下列公式中是真命题的为 ( A. ?x?y( x ? y ? 1) C. ?x?y( x ? y ? x) B. ?x?y( x ? y ? 0) D. ?x?y( x ? y ? 2 y) ) ) . B.x,y 都是自由变元 D.x 是自由变元,y 都是约束变元

约束变元就是受相应的量词约束的变元. 而自由变元就是不受任何量词约束

因为选项 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 ? (Q ? P) 的真值是 . 因为 P ? (Q ? P) ??P?(Q?P) ?1,所以应该填写:1.

3

应该填写:1 问:命题公式 Q ? Q 、 Q ? ?Q 的真值是什么? 2.设 P:他生病了,Q:他出差了.R:我同意他不参加学习. 则命题“如 果他生病或出差了, 我就同意他不参加学习” 符号化的结果为 它的符号化用条件联结词?. 应该填写:(P?Q)?R 3. 含有三个命题变项 P, Q, R 的命题公式 P?Q 的主析取范式是 复习主析取范式的定义: 定义 6.6.5 对于给定的命题变元,如果有一个等价公式,它仅仅有小项的析 取组成,则该等价式称为原式的主析取范式. 而小项的定义是: 定义 6.6.4 n 个命题变元的合取式,称为布尔合取或小项,其中每个变元与 它的否定不能同时存在,但两者必须出现且仅出现一次. 由小项的定义知道,命题公式 P?Q 中缺少命题变项 R 与它的否定,因此, 应该补上,即 P?Q?P?Q? (R??R) ?(P?Q? R) ?(P?Q??R) 得到命题公式 P?Q 的主析取范式. 应该填写:(P?Q?R)? (P?Q??R) 4.设个体域 D= {a, b}, 那么谓词公式 ?xA( x) ? ?yB ( y ) 消去量词后的等值式 为 . 因为在有限个体域下,消除量词的规则为:设 D={a1, a2, ?, an},则 . . 一般地,当语句是由“如果??,那么??”,或“若??,则??”组成,

?xA( x) ? A(a1 ) ? A(a2 ) ? ... ? A(an ) ?xA( x) ? A(a1 ) ? A(a2 ) ? ...? A(an )
所以,应该填写:(A(a)? A(b))? (B(a)? B(b)) 应该填写:(A(a)? A(b))? (B(a)? B(b)) 注:如果个体域是 D={1, 2},D={a, b, c}, 或谓词公式变为 ?x( A( x) ? B( x)) ,怎 么做? 5.设个体域 D={1, 2, 3},A(x)为“x 小于 3”,则谓词公式(?x)A(x) 的真值 为 应该填写:1 注:若个体域 D={1, 2},A(x)为“x 小于 3”,则谓词公式(?x)A(x) 的真值是什 么? 或:设个体域 D={1, 2, 3},A(x)为“x 是奇数”,则谓词公式(?x)A(x) 的真值是 . 因为 (?x)A(x)?A(1)?A(2)?A(3)?1?1?0?1

4

什么? 6.谓词命题公式(?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 ?Q. 注:语句中包含“也”、“且”、“但”等连接词,命题公式要用合取“?” . 3.请将语句“他去旅游,仅当他有时间.”翻译成命题公式. 解:设 P:他去旅游,Q:他有时间, 则命题公式为:P ?Q. 注意:命题公式的翻译还要注意“不可兼或”的表示. 例如,教材第 164 页的例 6 “T2 次列车 5 点或 6 点钟开.”怎么翻译成命 题公式?这里的“或”为不可兼或. 4.请将语句“所有人都努力工作.”翻译成谓词公式. 解:设 P(x):x 是人,Q(x):x 努力工作. 谓词公式为: (?x)(P(x)? Q(x)). 四、判断说明题(判断下列各题,并说明理由.) 1.命题公式 ?P ? P 的真值是 1. 解 错误. 因为 ?P ? P 是永假式(教材 167 页的否定律). 2.命题公式?P∧(P??Q)∨P 为永真式. 解:正确 因为,由真值表 P 0 Q 0 ?P 1 ?Q 1 P??Q 1 ?P∧(P→?Q)∨P 1 . 因为自由变元就是不受任何量词约束的变元,在公式(?x)((A(x)?B(x)) ?C(y))

5

0 1 1

1 0 1

1 0 0

0 1 0

1 1 0

1 1 1

可知,该命题公式为永真式. 注:如果题目改为该命题公式为永假式,如何判断并说明理由? 3.下面的推理是否正确,请给予说明. (1) (?x)A(x) ? B(x) (2) A(y) ?B(y) 解:错 第 2 步应为:A(y) ? B(x) 因为 A(x)中的 x 是约束变元,而 B(x)中的 x 是自由变元,换名时,约束变元 与自由变元不能混淆. 五.计算题 1.求 P?Q?R 的析取范式,合取范式、主析取范式,主合取范式. 分析: 定义 6.6.7 对于给定的命题变元,如果有一个等价公式,它仅仅有 大项的合取组成,则该等价式称为原式的主合取范式. 定义 6.6.6 解 n 个命题变元的析取式,称为布尔析取或大项,其中每个变元与 它的否定不能同时存在,但两者必须出现且仅出现一次. 析取范式,合取范式、主析取范式的定义前面复习过了,由教材 167 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) “主析取范式”或“主合取范式”. 例如:求(P?Q)→R [或(P?Q)?(R?Q),P?Q?R]的合取范式、析取范式. 2.设谓词公式 (?x)( P( x, y) ? (?z)Q( y, x, z)) ? (?y) R( y, z) . (1)试写出量词的辖域; (2)指出该公式的自由变元和约束变元. 解 (1)量词 ?x 的辖域为 P( x, y) ? ?zQ( y, x, z ) , (主析取范式) 注意:如果题目只是求“析取范式”或“合取范式”,大家一定不要再进一步求 (?对?的分配律) 的蕴含等价式 ?(?P?(Q??Q)?(R??R))?((P??P)?Q?(R??R))?((P??P)?(Q??Q)?R) 前提引入 US (1)

6

? z 的辖域为 Q( y, x, z ) ,

?y 的辖域为 R( y, z ) .

(2)自由变元为 P( x, y) ? ?zQ( y, x, z ) 中的 y, R( y, z ) 中的 z. 约束变元为 P( x, y) ? ?zQ( y, x, z ) 中的 x, Q( y, x, z ) 中的 z, R( y, 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?(Q??R))??P?Q 与?(P??Q)等价. 证:(P?(Q??R))??P?Q?(?P?(Q??R))??P?Q ?((?P?Q??R)??P)?Q ??P?Q ??(P??Q) 2.试证明(?x)(P(x)?R(x))?(?x)P(x)?(?x)R(x). 分析:前提:(?x)(P(x)?R(x)), 结论:(?x)P(x)?(?x)R(x) . 证明 (1) (?x)(P(x)?R(x)) (2) P(a)?R(a) (3) P(a) (4) (?x)P(x) (5) R(a) (6) (?x)R(x) (7) (?x)P(x)?(?x)R(x) P ES(1) T(2) EG(3) T(2) EG(5) (存在指定规则) (化简) (存在推广规则) (化简) (存在推广规则) (吸收律) (摩根律)

注意, 教材第 6 章的学习指导中的例题要认真学习, 尤其是例 5 大家一定要重视。

T(4)(6) (合取引入)

7


赞助商链接
推荐相关:
网站首页 | 网站地图
All rights reserved Powered by 酷我资料网 koorio.com
copyright ©right 2014-2019。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com