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

1、个人收集整理 勿做商业用途 数理逻辑部分综合练习及答案一、单项选择题1. 设P:我将去打球，Q:我有时间.命题"我将去打球，A QP B P QC P因为语句“仅当我有时间时”是“我将去打球”的必要条件它的符号化用条件联结词 .所以选项 B 是正确的. 正确答案: B 问:如果把“我将去打球”改成“我将去学习”、2. 命题公式 P Q 的合取范式是 (A . P QB.C . P QD .复习合取范式的定义 : 定义 6.6.2 一个命题公式称为合取范式，当且仅当它具有形式:Ai A A2人人A 其中Ai, A2,，An均是由命题变元或其否定所组成的析取式.P Q 与 P Q 不是等

2、价的，选项 A 是错的.仅当我有时间时Q“我将去旅游)(P Q) ( P Q) ( P Q )n，"符号化为 ().PQ，一般地，当语句是由“，仅当”组成,D"等，怎么符号化呢？n 1)由此可知,选项 B 和 D 是错的.又因为 正确答案: C3.命题公式 (P Q) 的析取范式是 (A. P QB P Q复习析取范式的定义:定义 6。 6。 3 一个命题公式称为析取范式,)C P QD P Q所以 ,选项 C 是正确的当且仅当它具有形式:Ai V A2V-V An , 其中Ai, A2,，An均是有命题变元或其否定所组成的合取式.由教材第167页中的蕴含等价式知道，公式(

3、P Q)与P所以,选项 A 是正确的.正确答案 :A注:第 2, 3题复习了合取范式和析取范式的概念,大家一定要记住的。公式的合取范式或析取范式,那么答案是什么4. 下列公式成立的为().A. P Q P Q C . Q P P 因为： P (P Q) Q(析取三段论， 所以,选项 D 是正确的.正确答案 :D5. 下列公式 (A. PC.( P 由教材第(P 所以, C 是重言式,也就是正确答案 :C 说明：如果题目改为“下列公式6 .设 A(x): x 是人,B (x):A. ( x)( A(x) C .( x)( A由题设知道, A 得到公式 C.正确答案: CB P Q P D P (

4、P Q) P171 公式( 10)n 1)Q 是等价的 ,P如果题目改为求一个变元Q 满足析取范式的定义，P 或 P )命题)为重言式QP) ( P (PQP(Q167 页中的蕴含等价式 ,得 ( Q P) P (Q P )， 永真式 B(x)x) B(x) x)B)(PQ (P Q ) D ( P(P Q) P( Q ( P Q) P Q )Q()为永真式” ,应该是一样的.x 是学生,则命题“不是所有人都是学生 "可符号化为(B .( x)( A(x) B(x)D.( x)(A(x) B( x)B (x)表示只要是人，就是学生，而“不是所有”应该用全称量词的否定，即x，7 .设A

5、(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个人收集整理勿做商业用途& 表达式 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 (

6、x, y)所谓辖域是指“紧接于量词之后最小的子公式称为量词的辖域” 那么看题中紧接于量词 公式是什么呢？显然是 P (x, y) Q (z),因此，选项B是正确的.正确答案：B 注：如果该题改为判断题，即表达式 x(P(x, y) Q(z) y(R(x, y) 如何判断并说明理由呢？9.在谓词公式( x)(A (x) t B(x) C(x, A . x,y都是约束变元B.zQ( z)中x的辖域是P(x, y)y)中，( ). x, y都是自由变元C.x是约束变元，y都是自由变元D . x是自由变元，y都是约束变元约束变元就是受相应的量词约束的变元.而自由变元就是不受任何量词约束的变元.所以选项

7、 正确答案：C 注：如果该题改为填写约束变元或自由变元的填空题，大家也应该掌握. 补充题：设个体域为自然数集合，下列公式中是真命题的为A .C .因为选项选项 选项 正确答案：x y(x y 1)x y(x y x)A表示:对任一自然数B表示：C表示： C对任一自然数 存在一自然数二、填空题1 .命题公式因为P应该填写：1问：命题公式Q Q、2. 设P:他生病了P (Q (Q P)x之后最小的子C是正确的.(0)2y)B.x y(x yD.x y(x yx存在自然数y满足xy=1，这样的y是不存在的x存在自然数y满足x+y=0,这样的y也是不存在的x自然数对任意自然数 y满足xy=x，取 x=

8、0即可，故选项 C正确P)的真值是.P (Q P)1,所以应该填写：1.Q,Q：他出差了.Q的真值是什么？R：我同意他不参加学习则命题“如果他生病或出差了，我就同意他不参加学习"符号化的结果为 _一般地，当语句是由“如果 ，那么"，或“若，则应该填写：(P Q) R3. 含有三个命题变项P, Q, R的命题公式P Q的主析取范式是 复习主析取范式的定义：定义6.6。5对于给定的命题变元，如果有一个等价公式，它仅仅有小项的析取组成，则该等价式称为原式 的主析取范式.而小项的定义是：定义6.6。4 n个命题变元的合取式，称为布尔合取或小项，其中每个变元与它的否定不能同时存在，但

9、两者必须出现且仅出现一次.由小项的定义知道，命题公式P Q中缺少命题变项P Q P Q (R R)得到命题公式P Q的主析取范式.应该填写：(P Q R) (P QR)4. 设个体域D = a, b,那么谓词公式因为在有限个体域下，消除量词的规则为：设xA(x)xA(x)所以，应该填写：(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 ,"组成,它的符号化用条件联结词R与它的否定，因此，应该补上，即(P Q R) (P QR)xA(x)yB(y)

10、消去量词后的等值式为D= ai, a2,，an贝UA(ai) A(a2).A(an)A(ai) A). A(an)或谓词公式变为x(A(x)3, A (x)为“ x小于3”，则谓词公式(B(x)，怎么做? x)A(x)的真值为因为(x)A (x) A(1) A (2) A(3)1101应该填写：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)中的自由变元为 .因为

11、自由变元就是不受任何量词约束的变元，在公式(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.注:语句中包含“也”、“且”、“但”等连接词，命题公式要用合取

12、“”.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. 命题公式 PA( P Q)V P为永真式.

13、 解:正确因为，由真值表PQPQP QP A (P Q )V P0 101111011011 :100111110001可知,该命题公式为永真式.注：如果题目改为该命题公式为永假式，如何判断并说明理由？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对于给定的命题变元，如果有一个等价公式，它仅

14、仅有大项的合取组成，则该等价式 称为原式的主合取范式.定义6.6.6 n个命题变元的析取式， 称为布尔析取或大项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次.解 析取范式，合取范式、主析取范式的定义前面复习过了，由教材167的蕴含等价式P Q R P Q R(析取范式、合取范式、主合取范式)个人收集整理 勿做商业用途(P(Q Q)(RR) (PP) Q (RR)( (PP) (Q Q) R)(补齐命题变项 )(PQ R) (PQ R) (PQ R) (PQ R)(PQ R) (PQR)( PQR)( PQR)(P QR) (PQR)( PQR) ( PQR)( 对 的分配律

15、)(PQ R) (P Q R)(P QR)(P Q R)(PQ R) (P Q R) (PQR)(主析取范式)注：如果题目只是求“析取范式 " 或“合取范式”，大家一定不要再进一步求“主析取范式”或“主合取范式”例如：求(P Q) tR咸(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)中的乙R( y, z)中的y.2.试证明 ( x)(P(x)R(x)分析 :前提： ( x)( P(x)R(x)结论 :( x) P(x)( x) R证明 (1)( x)( P(x) R(x)(2) P( a)R(a)(3) P(a)( 4) ( x) P(x)3.设个体域为D= ai, a2,求谓词公式 y xP(x,y)消去量词后的等值式.解：y xP(x， y)xP(x, a1)(xP(x, a2)P(a1,a1)P(a2，a1)(P (