离散数学数理逻辑部分期末复习题.doc
离散数学数理逻辑部分综合练习辅导一、单项选择题1设P：我将去打球，Q：我有时间命题“我将去打球，仅当我有时间时”符号化为( )A B C D因为语句“仅当我有时间时”是“我将去打球”的必要条件，所以选项B是正确的正确答案：B一般地，当语句是由“，仅当”组成，它的符号化用条件联结词®问：如果把“我将去打球”改成“我将去学习”、“我将去旅游”等，会符号化吗？2设命题公式G：，则使公式G取真值为1的P，Q，R赋值分别是 ( )A0, 0, 0 B0, 0, 1 C0, 1, 0 D1, 0, 0 个人收集整理 勿做商业用途 当P为真值为1时，的真值为0，无论的真值是1还是0，命题公式G的真值为1所以选项D是正确的正确答案：D3命题公式PÚQ的合取范式是 ( )APÙQ B（PÙQ）Ú（PÚQ）CPÚQ DØ（ØPÙØQ）复习合取范式的定义：定义6.6.2 一个命题公式称为合取范式，当且仅当它具有形式： A1A2An， （n1）其中A1，A2，An均是由命题变元或其否定所组成的析取式由此可知，选项B和D是错的又因为PÙQ 与PÚQ不是等价的，选项A是错的所以，选项C是正确的正确答案：C 4命题公式的析取范式是( )ABCD复习析取范式的定义：定义6.6.3 一个命题公式称为析取范式，当且仅当它具有形式： A1A2An ， （n1）其中A1，A2，An均是有命题变元或其否定所组成的合取式 公式与是等价的，满足析取范式的定义，所以，选项A是正确的正确答案：A5下列公式成立的为( )AØPÙØQ ÛPÚQBP®ØQÛØP®QCQ®PÞ P DØPÙ(PÚQ)ÞQ因为：ØPÙ(PÚQ)ÞQ 所以，选项D是正确的正确答案：D 6下列公式 ( )为重言式AØPÙØQ«PÚQB(Q®(PÚQ) «(ØQÙ(PÚQ)C(P®(ØQ®P)«(ØP®(P®Q) D(ØPÚ(PÙQ) «Q(P®(ØQ®P) ÛØPÚ(QÚ P)，(ØP®(P®Q) Û PÚ(ØPÚQ) 所以，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(x)®B(x)表示只要是人，就是学生，而“不是所有”应该用全称量词的否定，即Ø"x，得到公式C个人收集整理 勿做商业用途正确答案：C8设C(x)：x是国家级运动员，G(x)：x是健壮的，则命题“没有一个国家级运动员不是健壮的”可符号化为 ( )个人收集整理 勿做商业用途 A BCD 由题设知道，C(x)ÙØ G(x)表示国家级运动员不是健壮的，而“没有一个”就是“不存在一个”，因此用存在量词的否定，即Ø$x，得到公式D个人收集整理 勿做商业用途正确答案：D9表达式中的辖域是( ) AP(x, y) BP(x, y)ÚQ(z) CR(x, y) DP(x, y)ÙR(x, y)个人收集整理 勿做商业用途所谓辖域是指“紧接于量词之后最小的子公式称为量词的辖域”那么看题中紧接于量词"x之后最小的子公式是什么呢？显然是P(x, y)ÚQ(z)，因此，选项B是正确的个人收集整理 勿做商业用途正确答案：B10在谓词公式("x)(A(x)B(x)ÚC(x，y)中，（ ）Ax，y都是约束变元 Bx，y都是自由变元 Cx是约束变元，y都是自由变元Dx是自由变元，y都是约束变元约束变元就是受相应的量词约束的变元而自由变元就是不受任何量词约束的变元所以选项C是正确的正确答案：C注：如果该题改为填写约束变元或自由变元的填空题，大家也应该掌握二、填空题1命题公式的真值是因为ÛØPÚ(QÚP)Û1，所以应该填写：1应该填写：1问：命题公式、的真值是什么？2设P：他生病了，Q：他出差了R：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为个人收集整理 勿做商业用途一般地，当语句是由“如果，那么”，或“若，则”组成，它的符号化用条件联结词®应该填写：(PÚQ)®R3含有三个命题变项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设个体域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)Û1Ú1Ú0Û1应该填写：16谓词命题公式("x)(A(x)ÙB(x) ÚC(y)中的自由变元为 因为自由变元就是不受任何量词约束的变元，在公式("x)(A(x)ÙB(x) ÚC(y)中，y是不受全称量词"约束的变元所以应该填写：y个人收集整理 勿做商业用途应该填写：y问: 公式中的约束变元是什么?三、公式翻译题1请将语句“今天是天晴”翻译成命题公式解：设P：今天是天晴； 则命题公式为： P 问：“今天不是天晴”的命题公式是什么？2请将语句“小王去旅游，小李也去旅游”翻译成命题公式解：设 P：小王去旅游，Q：小李去旅游， 则命题公式为：PÙQ 注：语句中包含“也”、“且”、“但”等连接词，命题公式要用合取“Ù” 3请将语句“他去旅游，仅当他有时间”翻译成命题公式解：设 P：他去旅游，Q：他有时间， 则命题公式为：P®Q 4请将语句“所有人都努力工作”翻译成谓词公式解：设P(x)：x是人，Q(x)：x努力工作 谓词公式为： ("x)(P(x)® Q(x)四、判断说明题（判断下列各题，并说明理由） 1命题公式的真值是1解 错误因为是永假式（教材167页的否定律）2命题公式ØP(P®ØQ)P为永真式 解：正确 因为，由真值表PQØPØQP®ØQØP(PØQ)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 求P®QÚR的析取范式，合取范式、主析取范式，主合取范式解 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) （主析取范式）个人收集整理 勿做商业用途注：如果题目只是求“析取范式”或“合取范式”，大家一定不要再进一步求“主析取范式”或“主合取范式”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) （化简） (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) （合取引入）
