离散数学11秋数理逻辑部分综合练习辅导
一、单项选择题
1．设P：我将去打球，Q：我有时间．命题“我将去打球，仅当我有时间时”符号化为( )．
A．Q?P B．P?Q C．P?Q D．?P??Q 因为语句“仅当我有时间时”是“我将去打球”的必要条件，一般地，当语句是由“??，仅当??”组成，它的符号化用条件联结词?．所以选项B是正确的． 正确答案：B
问：如果把“我将去打球”改成“我将去学习”、“我将去旅游”等，怎么符号化呢？
2．设命题公式G：?P?(Q?R)，则使公式G取真值为1的P，Q，R赋值分别是 ( )．
A．0, 0, 0 B．0, 0, 1 C．0, 1, 0 D．1, 0, 0 当P为真值为1时，?P的真值为0，由教材162页的条件联结词的运算表知道，无论(Q?R)的真值是1还是0，命题公式G的真值为1．所以选项D是正确的． 正确答案：D
3．命题公式P?Q的合取范式是 ( )．
A．P?Q B．（P?Q）?（P?Q） C．P?Q D．?（?P??Q） 复习合取范式的定义：
定义6.6.2 一个命题公式称为合取范式，当且仅当它具有形式：
A1∧A2∧?∧An ， （n?1）
其中A1，A2，?，An均是由命题变元或其否定所组成的析取式．
由此可知，选项B和D是错的．又因为P?Q 与P?Q不是等价的，选项A是错的．所以，选项C是正确的． 正确答案：C
4．命题公式?(P?Q)的析取范式是( )．
A．P??Q B?P?Q C．?P?Q D．P??Q
复习析取范式的定义：
定义6.6.3 一个命题公式称为析取范式，当且仅当它具有形式：
A1∨A2∨?∨An ， （n?1）
其中A1，A2，?，An均是有命题变元或其否定所组成的合取式．
由教材第167页中的蕴含等价式知道，公式?(P?Q)与P??Q是等价的，
P??Q满足析取范式的定义，所以，选项A是正确的．
1
离散数学11秋数理逻辑部分综合练习辅导
正确答案：A
注：第3，4题复习了合取范式和析取范式的概念，大家一定要记住的。如果题目改为求一个变元（P或?P）命题公式的合取范式或析取范式，那么答案是什么？
5．下列公式成立的为( )．
A．?P??Q ? P?Q B．P??Q ? ?P?Q C．Q?P ? P D．?P?(P?Q)?Q 因为： ?P?(P?Q)?Q（析取三段论，P171公式(10)） 所以，选项D是正确的． 正确答案：D
6．下列公式 ( )为重言式．
A．?P??Q?P?Q B．(Q?(P?Q)) ?(?Q?(P?Q)) C．(P?(?Q?P))?(?P?(P?Q)) D．(?P?(P?Q)) ?Q
由教材第167页中的蕴含等价式，得
(P?(?Q?P)) ??P?(Q? P)，(?P?(P?Q)) ? P? (?P?Q)
所以，C是重言式，也就是永真式． 正确答案：C
说明：如果题目改为“下列公式 ( )为永真式”，应该是一样的．
7．设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． 正确答案：C
8．设C(x)：x是国家级运动员，G(x)：x是健壮的，则命题“没有一个国家级运动员不是健壮的”可符号化为 ( )．
A．??x(C(x)??G(x)) B．??x(C(x)??G(x))
C．??x(C(x)??G(x)) D．??x(C(x)??G(x))
由题设知道，C(x)?? G(x)表示国家级运动员不是健壮的，而“没有一个”就是“不存在一个”，因此用存在量词的否定，即??x，得到公式D． 正确答案：D
9．表达式?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) 所谓辖域是指“紧接于量词之后最小的子公式称为量词的辖域”．那么看题可符号化为（ ）．
2
离散数学11秋数理逻辑部分综合练习辅导
中紧接于量词?x之后最小的子公式是什么呢？显然是P(x, y)?Q(z)，因此，选项B是正确的． 正确答案：B
10．在谓词公式(?x)(A(x)→B(x)?C(x，y))中，（ ）． A．x，y都是约束变元 B．x，y都是自由变元
C．x是约束变元，y都是自由变元 D．x是自由变元，y都是约束变元 约束变元就是受相应的量词约束的变元．而自由变元就是不受任何量词约束的变元．所以选项C是正确的． 正确答案：C
注：如果该题改为填写约束变元或自由变元的填空题，大家也应该掌握．
下面的内容主要是第7次形考作业的部分题目． 二、填空题
1．命题公式P?(Q?P)的真值是 ． 因为P?(Q?P)??P?(Q?P) ?1，所以应该填写：1． 应该填写：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)消去量词后的等值式
3
离散数学11秋数理逻辑部分综合练习辅导
为 ．
因为在有限个体域下，消除量词的规则为：设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) 的真值为 ．
因为 (?x)A(x)?A(1)?A(2)?A(3)?1?1?0?1 应该填写：1
注：若个体域D＝{1, 2}，A(x)为“x小于3”，则谓词公式(?x)A(x) 的真值是什么？
6．谓词命题公式(?x)((A(x)?B(x)) ?C(y))中的自由变元为 ． 因为自由变元就是不受任何量词约束的变元，在公式(?x)((A(x)?B(x)) ?C(y))中，y是不受全称量词?约束的变元．所以应该填写：y． 应该填写：y
问: 公式中的约束变元是什么?
三、公式翻译题
1．请将语句“今天是天晴”翻译成命题公式．
解：设P：今天是天晴；
则命题公式为： P．
问：“今天不是天晴”的命题公式是什么？
2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式．
解：设 P：小王去旅游，Q：小李去旅游， 则命题公式为：P ?Q．
注：语句中包含“也”、“且”、“但”等连接词，命题公式要用合取“?” ． 3．请将语句“他去旅游，仅当他有时间．”翻译成命题公式．
解：设 P：他去旅游，Q：他有时间， 则命题公式为：P ?Q．
注：命题公式的翻译还要注意“不可兼或”的表示．
例如，教材第164页的例6 “T2次列车5点或6点钟开．”怎么翻译成命题公式？这里的“或”为不可兼或．
4
相关推荐：
loading