数理逻辑部分综合练习及答案.doc

个人收集整理 勿做商业用途
数理逻辑部分综合练习及答案
一、单项选择题
1．设P：我将去打球，Q:我有时间．命题“我将去打球，仅当我有时间时"符号化为( )．
A． B． C． D．
因为语句“仅当我有时间时”是“我将去打球”的必要条件,一般地，当语句是由“……，仅当……”组成，它的符号化用条件联结词®．所以选项B是正确的．
正确答案：B
问：如果把“我将去打球”改成“我将去学习”、“我将去旅游"等，怎么符号化呢？
2．命题公式PÚQ的合取范式是 ( ）．
A．PÙQ B．(PÙQ）Ú（PÚQ)
C．PÚQ D．Ø（ØPÙØQ）
复习合取范式的定义:
定义6.6.2 一个命题公式称为合取范式，当且仅当它具有形式：
A1∧A2∧…∧An ， （n1）
其中A1，A2，…，An均是由命题变元或其否定所组成的析取式．
由此可知，选项B和D是错的．又因为PÙQ 与PÚQ不是等价的，选项A是错的．所以,选项C是正确的．
正确答案：C
3．命题公式的析取范式是( ）．
A． B C． D．
复习析取范式的定义：
定义6。6。3 一个命题公式称为析取范式，当且仅当它具有形式：
A1∨A2∨…∨An , （n1)
其中A1，A2，…，An均是有命题变元或其否定所组成的合取式．
由教材第167页中的蕴含等价式知道，公式与是等价的,满足析取范式的定义，所以，选项A是正确的．
正确答案: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
8．表达式中的辖域是( )．
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)
如何判断并说明理由呢？
9．在谓词公式（"x)(A（x）→B(x)ÚC(x，y））中，（ )．
A．x,y都是约束变元 B．x，y都是自由变元
C．x是约束变元，y都是自由变元 D．x是自由变元，y都是约束变元
约束变元就是受相应的量词约束的变元．而自由变元就是不受任何量词约束的变元．所以选项C是正确的．
正确答案：C
注：如果该题改为填写约束变元或自由变元的填空题，大家也应该掌握．
补充题：设个体域为自然数集合，下列公式中是真命题的为 （ ）
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
二、填空题
1．命题公式的真值是　 　．
因为ÛØPÚ(QÚP） Û1，所以应该填写：1．
应该填写：1
问：命题公式、的真值是什么？
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｝,那么谓词公式消去量词后的等值式为 ．
因为在有限个体域下，消除量词的规则为：设D＝{a1， a2， …， an｝,则

所以,应该填写：（A（a)Ú A(b))Ú (B(a)Ù B（b）)
应该填写：(A（a）Ú A(b))Ú (B（a)Ù B(b）)
注：如果个体域是D＝{1， 2},D=｛a, b， c}, 或谓词公式变为，怎么做?
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．命题公式的真值是1．
解 错误．
因为是永假式（教材167页的否定律)．
2．命题公式ØP∧（P®ØQ)∨P为永真式．
解:正确
因为，由真值表
P
Q
ØP
ØQ
P®ØQ
ØP∧(P→ØQ）∨P
0
0
1
1
1
1
0
1
1
0
1
1
1
0
0
1
1
1
1
1
0
0
0
1
可知,该命题公式为永真式．
注：如果题目改为该命题公式为永假式，如何判断并说明理由？
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．设谓词公式．
（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®(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)） P
（2) P（a）ÙR（a） ES(1) (存在指定规则）
（3） P(a) T(2) I （化简)
（4） （$x）P（x) EG(3) (存在推广规则)
(5) R（a） T（2) I (化简）
(6) （$x)R(x) EG（5） （存在推广规则)
（7） （$x）P(x）Ù($x）R(x） T(4）（6)I （合取引入）