离散数学2014春数理逻辑部分综合练习辅导
一、单项选择题
单项选择题主要是第6次形考作业的部分题目．
第6次作业还是由10个单项选择题组成，每小题10分，满分100分．在每次作业在关闭之前，允许大家反复多次练习，系统将保留您的最好成绩，希望大家要多练几次，争取好成绩．需要提醒大家的是每次练习的作业题目可能不一样，请大家一定要认真阅读题目．
1．设P：我将去打球，Q：我有时间．命题“我将去打球，仅当我有时间时”符号化为( )．
A．P
∨
?
P?Q→B．Q
P→C．Q
P?D．Q 因为语句“仅当我有时间时”是“我将去打球”的必要条件，一般地，当语句是由“……，仅当……”组成，它的符号化用条件联结词→．所以选项B是正确的．
正确答案：B
问：如果把“我将去打球”改成“我将去学习”、“我将去旅游”等，怎么符号化呢？
2．命题公式P∨Q的合取范式是( )．
A．P∧Q B．（P∧Q）∨（P∨Q）
C．P∨Q D．?（?P∧?Q）
复习合取范式的定义：
定义6.6.2 一个命题公式称为合取范式，当且仅当它具有形式：
A1∧A2∧…∧A n，（n≥1）
其中A1，A2，…，A n均是由命题变元或其否定所组成的析取式．
由此可知，选项B和D是错的．又因为P∧Q与P∨Q不是等价的，选项A 是错的．所以，选项C是正确的．
正确答案：C
3．命题公式)
?的析取范式是( )．
P→
(Q
A．Q
?D．Q
∨
P∨
P?
?C．Q
∧B Q
P?
P∧
复习析取范式的定义：
定义6.6.3 一个命题公式称为析取范式，当且仅当它具有形式：
A1∨A2∨…∨A n ，（n≥1）
其中A1，A2，…，A n均是有命题变元或其否定所组成的合取式．
由教材第167页中的蕴含等价式知道，公式)
∧是等价的，
(Q
P?
?与Q
P→
∧满足析取范式的定义，所以，选项A是正确的．
Q
P?
正确答案：A
注意：第2，3题复习了合取范式和析取范式的概念，大家一定要记住的。如果题目改为求一个变元（P或?P）命题公式的合取范式或析取范式，那么答案是什么？
4．下列公式成立的为( )．
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
5．下列公式( )为重言式．
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
说明：如果题目改为“下列公式( )为永真式”，应该是一样的．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．
正确答案：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中的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=0
C．存在一整数x对任意整数y满足x+y=0
D．任一整数x对任意整数y满足x+y=0
正确答案：B
8．表达式))
?的辖域是( )．
y
x
Q
x?
y
z
∨
?中x
R
∧
?
→
P
))
(
(
(
)
,
x
)
zQ
y
(
(z
(
,
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
注意：如果该题改为判断题，即
表达式))
?的辖域是P(x, y)
y
x
y
P
z
Q
?
?中x
∨
∧
→
R
x?
(
))
(
,
(
)
(
)
zQ
y
(z
(
,
x
如何判断并说明理由呢？
9．在谓词公式(?x)(A(x)→B(x)∨C(x，y))中，（）．
A．x，y都是约束变元B．x，y都是自由变元
C．x是约束变元，y都是自由变元D．x是自由变元，y都是约束变元约束变元就是受相应的量词约束的变元．而自由变元就是不受任何量词约束的变元．所以选项C是正确的．
正确答案：C
注：如果该题改为填写约束变元或自由变元的填空题，大家也应该掌握．
补充题：设个体域为自然数集合，下列公式中是真命题的为( ) A．)1
?
+
?y
(=
x
y
x
?
(=
?
?y
y
x
x B．)0
C．)
2
y
(y
y
x=
?
+
?
x
?D．)
y
(x
y
x
x=
?
?
因为选项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) ?1，所以应该填写：1．
P Q P
应该填写：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 },那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 ．
因为在有限个体域下，消除量词的规则为：设D ＝{a 1, a 2, …, a n }，则
)(...)()()(21n a A a A a A x xA ∧∧∧??
)(...)()()(21n a A a A a A x xA ∨∨∨??
所以，应该填写：(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 ) 的真值是什么？
或：设个体域D ＝{1, 2, 3}，A (x )为“x 是奇数”，则谓词公式(?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∧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为永真式．
解：正确
因为，由真值表
注：如果题目改为该命题公式为永假式，如何判断并说明理由？
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．求P→Q∨R的析取范式，合取范式、主析取范式，主合取范式．
分析：定义6.6.7 对于给定的命题变元，如果有一个等价公式，它仅仅有大项的合取组成，则该等价式称为原式的主合取范式．
定义6.6.6 n个命题变元的析取式，称为布尔析取或大项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次．
解析取范式，合取范式、主析取范式的定义前面复习过了，由教材167
的蕴含等价式
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∧?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
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 ={a 1, a 2}，求谓词公式?y ?xP (x ,y )消去量词后的等值式．
解：?y ?xP (x , y ) ?(?xP (x , a 1))∧(?xP (x , a 2))
?(P (a 1, a 1)∨P (a 2, a 1))∧(P (a 1, a 2)∨P (a 2, a 2))
六、证明题
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 ) （摩根律）
注意，教材第6章的学习指导中的例题要认真学习，尤其是例5大家一定要重视。
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 )) P
(2) P (a )∧R (a ) ES (1) (存在指定规则)
(3) P (a ) T (2) （化简）
(4) (?x )P (x ) EG (3) (存在推广规则)
(5) R (a ) T (2) （化简）
(6) (?x )R (x ) EG (5) (存在推广规则)
(7) (?x )P (x )∧(?x )R (x ) T (4)(6) （合取引入）