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

个人收集整理 勿做商业用途数理逻辑部分综合练习及答案一、单项选择题1设P：我将去打球，Q:我有时间命题“我将去打球，仅当我有时间时符号化为( )A B C D 因为语句“仅当我有时间时”是“我将去打球”的必要条件,一般地，当语句是由“，仅当”组成，它的符号化用条件联结词所以选项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是正确的正确答案：C 3命题公式的析取范式是( ） A B C D复习析取范式的定义：定义6。6。3 一个命题公式称为析取范式，当且仅当它具有形式： A1A2An , （n1)其中A1，A2，An均是有命题变元或其否定所组成的合取式 由教材第167页中的蕴含等价式知道，公式与是等价的,满足析取范式的定义，所以，选项A是正确的正确答案:A注:第2，3题复习了合取范式和析取范式的概念，大家一定要记住的。如果题目改为求一个变元（P或P）命题公式的合取范式或析取范式，那么答案是什么?4下列公式成立的为（ ）APQ PQ BPQ PQ CQP P DP（PQ）Q 因为： P(PQ)Q(析取三段论，P171公式（10） 所以，选项D是正确的正确答案:D 5下列公式 ( ）为重言式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）表示只要是人，就是学生，而“不是所有”应该用全称量词的否定，即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)）表示“有人是工人”正确答案:A 8表达式中的辖域是( ) AP(x， y） BP(x, y）Q（z） CR(x， y） DP(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）中，（ )Ax,y都是约束变元 Bx，y都是自由变元 Cx是约束变元，y都是自由变元 Dx是自由变元，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(QP） 1，所以应该填写：1应该填写：1问：命题公式、的真值是什么？2设P：他生病了,Q：他出差了R：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习符号化的结果为 一般地,当语句是由“如果，那么,或“若，则组成,它的符号化用条件联结词应该填写：（PQ）R3含有三个命题变项P，Q，R的命题公式PQ的主析取范式是 复习主析取范式的定义：定义6.6。5 对于给定的命题变元，如果有一个等价公式，它仅仅有小项的析取组成，则该等价式称为原式的主析取范式而小项的定义是：定义6.6。4 n个命题变元的合取式，称为布尔合取或小项，其中每个变元与它的否定不能同时存在,但两者必须出现且仅出现一次由小项的定义知道,命题公式PQ中缺少命题变项R与它的否定，因此,应该补上,即PQPQ （RR) (PQ R) （PQR）得到命题公式PQ的主析取范式应该填写：(PQR) （PQR）4设个体域Da， b,那么谓词公式消去量词后的等值式为 因为在有限个体域下，消除量词的规则为：设Da1， a2， ， an,则所以,应该填写：（A（a) A(b) (B(a) B（b）)应该填写：(A（a） A(b) (B（a) B(b）)注：如果个体域是D1， 2,D=a, b， c, 或谓词公式变为，怎么做?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是不受全称量词约束的变元所以应该填写：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（PQ)P为永真式 解:正确 因为，由真值表PQPQPQP(PQ）P001111011011100111110001可知,该命题公式为永真式注：如果题目改为该命题公式为永假式，如何判断并说明理由？ 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）（(PP)(QQ)R)（补齐命题变项)（PQR)（PQR)（PQR)（PQR)（PQR)(PQR）(PQR）（PQR)(PQR)(PQR）（PQR)（PQR） （对的分配律）(PQR)（PQR）（PQR）(PQR）（PQR)(PQR）(PQR） （主析取范式）注：如果题目只是求“析取范式或“合取范式”，大家一定不要再进一步求“主析取范式”或“主合取范式” 例如：求(PQ）R 或(PQ）(RQ）,PQR的合取范式、析取范式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(QR）)PQ与（PQ）等价 证:(P(QR)）PQ(P（QR）PQ （(PQR）P)Q PQ （吸收律） （PQ） （摩根律)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 （合取引入）