离散数学数理逻辑部分期末复习题

1、离散数学数理逻辑部分综合练习辅导一、单项选择题1设 P：我将去打球，Q：我有时间命题“我将去打球，仅当我有时间时”符号化为()AQ ® PBP ® QCP « QDØP Ú ØQ因为语句“仅当我有时间时”是“我将去打球”的必要条件，所以选项 B是正确的正确：B一般地，当语句是由“，仅当”组成，它的符号化用条件联结词® 问：如果把“我将去打球”改成“我将去学习”、“我将去旅游”等，会符号化吗？2设命题公式 G： ØP ® (Q Ù R) ，则使公式 G 取真值为 1 的 P，Q，R 赋值分别是 (

2、)A0, 0, 00, 0B0, 0, 1C0, 1, 0D1,当 P 为真值为 1 时，ØP 的真值为 0，无论(Q Ù R) 的真值是 1 还是 0，命题公式 G 的真值为 1所以选项 D 是正确的正确：D3命题公式 PÚQ 的合取范式是APÙQ CPÚQ复习合取范式的定义：() B（PÙQ）Ú（PÚQ）DØ（ØPÙØQ）定义 6.6.2 一个命题公式称为合取范式，当且仅当它具有形式：，（n ³ 1）所组成的析取式A1A2An其中 A1，A2，An 均是由命题变

3、其由此可知，选项 B 和 D 是错的又因为 PÙQ 与 PÚQ 不是等价的，选项 A是错的所以，选项 C 是正确的正确：C4命题公式Ø(P ® Q) 的析取范式是()A P Ù ØQB ØP Ù QC ØP Ú QD P Ú ØQ复习析取范式的定义：定义 6.6.3 一个命题公式称为析取范式，当且仅当它具有形式：（n ³ 1）A1A2An ，其中 A1，A2，An 均是有命题变其所组成的合取式公式Ø(P ® Q) 与 P Ù Ø

4、;Q 是等价的， P Ù ØQ 满足析取范式的定义，所以，1选项 A 是正确的正确：A5下列公式成立的为( AØPÙØQ Û PÚQ CQ®P Þ P因为： ØPÙ(PÚQ)ÞQ所以，选项 D 是正确的)BP®ØQ Û ØP®QDØPÙ(PÚQ)ÞQ正确：D6下列公式 (AØPÙØQ«PÚQ)为重言式B(Q®(P

5、18;Q) «(ØQÙ(PÚQ)D(ØPÚ(PÙQ) «QC(P®(ØQ®P)«(ØP®(P®Q)(P®(ØQ®P) ÛØPÚ(QÚ P)，(ØP®(P®Q) Û PÚ (ØPÚQ)所以，C 是重言式，也就是式：C正确说明：如果题目改为“下列公式 ()为式”，应该是一样的7设 A（x）：x 是人，B（x）：x

6、 是学生，则命题“不是所有人都是学生”可符号化为（）A( " x)(A(x)ÙB(x)CØ("x)(A(x)®B(x)BØ( $ x)(A(x)ÙB(x)DØ( $ x)(A(x)ÙØB(x)由题设知道，A(x)®B(x)表示只要是人，就是学生，而“不是所有”应该用全称量词的，即Ø"x，得到公式 C正确：C8设 C(x)：x 是级运动员，G(x)：x 是健壮的，则命题“没有一个级运动员不是健壮的”可符号化为A Ø"x(C(x) Ù &#

7、216;G(x)C Ø$x(C(x) ® ØG(x)由题设知道，C(x)ÙØ G(x)表示()B Ø"x(C(x) ® ØG(x)D Ø$x(C(x) Ù ØG(x)级运动员不是健壮的，而“没有一个”量词的，即Ø$x，得到公式 D就是“不一个”，因此用正确：D9表达式"x(P(x, y) Ú Q(z) Ù $y(R(x, y) ® "zQ(z) 中"x 的辖域是()BP(x, y)ÚQ(z)AP(

8、x, y)y)ÙR(x, y)CR(x, y)DP(x,所谓辖域是指“紧接于量词之后最小的子公式称为量词的辖域”那么看题中紧接于量词"x 之后最小的子公式是什么呢？显然是 P(x, y)ÚQ(z)，因此，选项 B 是正确的2正确：B10在谓词公式("x)(A(x)B(x)ÚC(x，y)中，（）Ax，y 都是约束变元Cx 是约束变元，y 都是自由变元Bx，y 都是自由变元Dx 是自由变元，y 都是约束变元约束变元就是受相应的量词约束的变元而自由变元就是不受任何量词约束的变元所以选项 C 是正确的正确：C注：如果该题改为填写约束变自由变元的填空题，

9、大家也应该掌握二、填空题1命题公式 P ® (Q Ú P) 的真值是因为 P ® (Q Ú P) ÛØPÚ(QÚP) Û1，所以应该填写：1 应该填写：1问：命题公式、的真值是什么？2设 P：他生病了，Q：他出差了R：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为一般地，当语句是由“如果，那么”，或“若，则”组成， 它的符号化用条件联结词®应该填写：(PÚQ)®R题公式 PÙQ 的主析取范式是3含有三个命题变项 P，Q，R复习

10、主析取范式的定义：定义 6.6.5 对于给定题变元，如果有一个等价公式，它仅仅有小项的析取组成，则该等价式称为原式的主析取范式而小项的定义是：定义 6.6.4n 个命题变元的合取式，称为合取或小项，其中每个变元与它的不能同时，但两者必须出现且仅出现一次由小项的定义知道，命题公式 PÙQ 中缺少命题变项 R 与它的应该补上，即PÙQÛPÙQÙ (RÚØR) Û(PÙQÙ R) Ú(PÙQÙØR)得到命题公式 PÙQ 的主析取范式 应该填写：(P&#

11、217;QÙR)Ú (PÙQÙØR)，因此，域 Da, b,那么谓词公式$xA(x) Ú "yB( y) 消去量词后的等值式4设为因为在有限域下，消除量词的规则为：设 Da1, a2,"xA(x) Û A(a1) Ù A(a2 ) Ù . Ù A(an ),an，则3$xA(x) Û A(a1) Ú A(a2 ) Ú .Ú A(an )所以，应该填写：(A(a)Ú A(b)Ú (B(a)Ù B(b)应该填写

12、：(A(a)Ú A(b)Ú (B(a)Ù B(b)域是 D1, 2，D=a, b, c, 或谓词公式变为$x(A(x) Ú B(x) ，如果怎么做?域 D1, 2, 3，A(x)为“x 小于 3”，则谓词公式($x)A(x)5设的真值为因为 ($x)A(x)ÛA(1)ÚA(2)ÚA(3)Û1Ú1Ú0Û1应该填写：16谓词命题公式("x)(A(x)ÙB(x) ÚC(y)中的自由变元为因为自由变元就是不受任何量词约束的变元，在公式("x)(A(x)&

13、#217;B(x)ÚC(y)中，y 是不受全称量词"约束的变元所以应该填写：y 应该填写：y问: 公式中的约束变元是什么?三、公式翻译题1请将语句“今天是天晴”翻译成命题公式 解：设 P：今天是天晴；则命题公式为： P问：“今天不是天晴”题公式是什么？2. 请将语句“小王去旅游，小李也去旅游”翻译成命题公式 解：设 P：小王去旅游，Q：小李去旅游，则命题公式为：P ÙQ注：语句中包含“也”、“且”、“但”等连接词，命题公式要用合取“Ù”3. 请将语句“他去旅游，仅当他有时间”翻译成命题公式 解：设 P：他去旅游，Q：他有时间，则命题公式为：P ®

14、;Q4. 请将语句“所有人都努力工作”翻译成谓词公式 解：设 P(x)：x 是人，Q(x)：x 努力工作谓词公式为： ("x)(P(x)® Q(x)四、说明题（下列各题，并说明理由）1命题公式ØP Ù P 的真值是 1解 错误4因为ØP Ù P 是永假式（167 页的律）式2命题公式ØP(P®ØQ)P 为解：正确因为，由真值表可知，该命题公式为式注：如果题目改为该命题公式为永假式，如何3下面的推理是否正确，请给予说明(1) ("x)A(x) Ù B(x)(2) A(y) ÙB

15、(y)解：错第 2 步应为：A(y) Ù B(x)并说明理由？前提引入US (1)因为 A(x)中的 x 是约束变元，而 B(x)中的 x 是自由变元，换名时，约束变元与自由变元不能五计算题1 求 P®QÚR 的析取范式，合取范式、主析取范式，主合取范式解P®QÚR ÛØPÚQÚR（析取范式、合取范式、主合取范式）Û(ØPÙ(QÚØQ)Ù(RÚØR)Ú(PÚØP)ÙQÙ(R&#

16、218;Ø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)Ú(

17、Ø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Ù

18、;R)Ú(PÙØQÙR)Ú(PÙQÙØR)Ú(PÙQÙR)式）（主析取范注：如果题目只是求“析取范式”或“合取范式”，大家一定不要再进一步求“主析取范式”或“主合取范式”2设谓词公式($x)(P(x, y) ® ("z)Q( y, x, z) Ù ("y)R( y, z) （1）试写出量词的辖域；5PQØPØQP®ØQØP(PØQ)P001111011011100111110001（2）

19、指出该公式的自由变元和约束变元解 （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) 中的 yD=a1, a2，求谓词公式"y$xP(x,y)消去量词后的等值3设域为式解："y$xP(x, y) Û($xP(x,a1)Ù($xP(x