第2章谓词逻辑习题及答案

谓词逻辑习题1.将下列命题用谓词符号化。（1）小王学过英语和法语。（2）2大于3仅当2大于4。（3）3不是偶数。（4）2或3是质数。（5）除非李键是东北人，否则他一定怕冷。解：(1)令)(xP：x学过英语，Q(x)：x学过法语，c：小王，命题符号化为)()(cQcP(2)令),(yxP：x大于y,命题符号化为)3,2()4,2(PP(3)令)(xP：x是偶数，命题符号化为)3(P(4)令)(xP：x是质数，命题符号化为)3()2(PP(5)令)(xP：x是北方人；)(xQ：x怕冷；c：李键；命题符号化为)()(xPcQ2.设个体域}{cbaD，，，消去下列各式的量词。（1）))()((yQxPyx（2）))()((yQxPyx（3）)()(yyQxxP（4）))()((yyQyxPx，解：(1)中))()(()(yQxPyxA，显然)(xA对y是自由的，故可使用UE规则，得到))()(()(yQyPyyA，因此))()(())()((yQyPyyQxPyx，再用ES规则，)()())()((zQzPyQyPy，Dz，所以)()())()((zQzPyQxPyx（2）中))()(()(yQxPyxA，它对y不是自由的，故不能用UI规则，然而，对)(xA中约束变元y改名z，得到))()((zQxPz，这时用UI规则，可得：))()((yQxPyx))()((zQxPzx))()((zQxPz（3）略（4）略3.设谓词)(yxP，表示“x等于y”，个体变元x和y的个体域都是}321{，，D。求下列各式的真值。（1）)3(，xxP（2）)1(yyP，（3）)(yxyPx，（4）)(yxyPx，（5）)(yxyPx，（6）)(yxxPy，解：(2)当3x时可使式子成立，所以为Ture。(3)当1y时就不成立，所以为False。(4)任意的x,y使得yx，显然有yx的情况出现，所以为False。(4)存在x,y使得yx，显然当1,1yx时是一种情况，所以为Ture。(5)存在x，任意的y使得yx成立，显然不成立，所以为False。(6)任意的y，存在x，使得yx成立，显然不成立，所以为False。4.令谓词)(xP表示“x说德语”，)(xQ表示“x了解计算机语言C++”，个体域为杭电全体学生的集合。用)(xP、)(xQ、量词和逻辑联接词符号化下列语句。（1）杭电有个学生既会说德语又了解C++。（2）杭电有个学生会说德语，但不了解C++。（3）杭电所有学生或会说德语，或了解C++。（4）杭电没有学生会说德语或了解C++。假设个体域为全总个体域，谓词)(xM表示“x是杭电学生”。用)(xP、)(xQ、)(xM、量词和逻辑联接词再次符号化上面的4条语句。解：（ⅰ）个体域为杭电全体学生的集合时：（1）))()((xQxPx（2）))()((xQxPx（3）))()((xQxPx（4）))()((xQxPx（ⅱ）假设个体域为全总个体域，谓词)(xM表示“x是杭电学生”时：（1）))()()((xQxPxMx（2）))()()((xQxPxMx（3）)))()(()((xQxPxMx（4）)))()(()((xQxPxMx5.令谓词)(yxP，表示“x爱y”，其中x和y的个体域都是全世界所有人的集合。用)(yxP，、量词和逻辑联接词符号化下列语句。（1）每个人都爱王平。（2）每个人都爱某个人。（3）有个人人都爱的人。（4）没有人爱所有的人。（5）有个张键不爱的人。（6）有个人人都不爱的人。（7）恰有一个人人都爱的人。（8）成龙爱的人恰有两个。（9）每个人都爱自己。（10）有人除自己以外谁都不爱。解：a：王平b：张键c：张龙(1)）axxP,((2)),(yxyPx(3)),(yxxPy(4)),(yxPyx(5))(xbPx，(6)),(yxPyx(7))))),(((),((xzzPzxyyPx(8))))()(()(),((yzxzzcPzcPxcPyxyx，(9)),(xxxP(10))),((yxyxPyx§2.2谓词公式及其解释习题2.21.指出下列谓词公式的指导变元、量词辖域、约束变元和自由变元。（1）))()((yxQxPx，（2）)()(yxyQyxxP，，（3）)())()((zyxxRzyQyxPyx，，，，解：（1）x是指导变元，x的辖域是),()(yxQxP，对于x的辖域而言，x是约束变元，y是自由变元。（2）x,y都为指导变元，x的辖域是)()(yxyQyxP，，，y的辖域是)(yxQ，；对于x的辖域而言，x,y都为约束变元，对于y的辖域而言，x是自由变元，y是约束变元。（3）x,y为指导变元，x的辖域是)())()((zyxxRzyQyxPy，，，，，y的辖域是)())()((zyxxRzyQyxP，，，，，x的辖域是)(zyxR，，；对于x的辖域而言，x,y为约束变元，z为自由变元，对于y的辖域而言，z为自由变元，y为约束变元，x即为约束变元也为自由变元，对于x的辖域而言，x为约束变元，y,z是自由变元。在整个公式中，x,y即为约束变元又为自由变元，z为自由变元。2.判断下列谓词公式哪些是永真式，哪些是永假式，哪些是可满足式，并说明理由。（1）))()(())()((yyQxxPxQxPx（2）))()(())()((yyQxxPxQxPx（3）)())()((yyQyyQxxP（4）))()(())()((xxQyPxQyPx（5）))()(())()((xxQxPxQxPx（6）)))()(()((xPyxyQxP，（7）))()(()(yxPyxQyxP，，，解：（1）易知公式是)()(qpqp的代换实例，而1)()()()(qpqpqpqp是永真式，所以公式是永真式。（2）易知公式是)()(qpqp的代换实例，而1)()()()(qpqpqpqp是永真式，所以公式是永真式。（3）易知公式是qqp)(的代换实例，而0)()(qqpqqpqqp是永假式，所以公式是永假式。（4）易知公式是)()(qpqp的代换实例，而1)()()()(qpqpqpqp是永真式，所以公式是永真式。（5）易知公式是)()(qpqp的代换实例，而1)()()()(qpqpqpqp是永真式，所以公式是永真式。（6）易知公式是))((pqp的代换实例，而0))(())((pqppqppqp是永假式，所以公式是永假式。（7）易知公式是pqp的代换实例，而pqppqppqp)()(是可满足式，所以公式是可满足式。§2.3谓词公式的等价演算与范式习题2.31.将下列命题符号化，要求用两种不同的等价形式。（1）没有小于负数的正数。（2）相等的两个角未必都是对顶角。解：（1）)(xP：x为负数，)(xQ：x是正数，),(yxR：x小于y，命题可符号化为：)))(),(((yQxPRyx或)))(),(((yQxPRyx（2）略2.设)(xP、)(xQ和)(yxR，都是谓词，证明下列各等价式（1）))()(())()((xQxPxxQxPx（2）))()(())()((xQxPxxQxPx（3）))()()(())()()((yxRyQxPyxyxRyQxPyx，，（4）))()()(())()()((yxRyQxPyxyxRyQxPyx，，证明：（1）左边＝))()((xQxPx＝))()((xQxPx＝))()((xQxPx＝右边（2）左边＝))()((xQxPx＝))()((xQxPx＝))()((xQxPx＝右边（3）左边＝)),()()((yxRyQxPyx＝)),())()(((yxRyQxPyx＝))()()((yxRyQxPyx，＝右边（4）左边＝),()()((yxRyQxPyx＝),())()((yxRyQxPyx＝))()()((yxRyQxPyx，＝右边3.求下列谓词公式的前束析取范式和前束合取范式。（1）)()(yxyQxxP，（2）))()((zyxyQyxPx，，，（3）))()(()(xRzzQyxyPx，（4）))()((())()((zyzSyRyyxQxPx，，解：（1）)),()((),()(yzQxPyxyzQxyPx原式前束析取范式)),()((yzQxPyx前束合取范式（2）原式),,(),((ztxQyxPtx),,(),((ztxQyxPtx前束析取范式),,(),((ztxQyxPtx前束合取范式（3）原式))()((),((tRzQyxPzyx))()(),((tRzQyxPzyx前束析取范式))()(),((tRzQyxPzyx前束合取范式（4）原式))()((())()((ztzStRtyxQxPx，，))),()(()),()(((ztStRyxQxPztx))),()(()),()(((ztStRyxQxPztx))),(),()(())(),()(((ztSyxQxPtRyxQxPztx),()(),(()),()(()(((ztStRyxQztStRxPztx§2.4谓词公式的推理演算习题2.41.证明：))()(())()((xBxAxxBxAx证明：（1）左边))()(())()((xBxAxxBxAx))()((xBxAx＝))()((xBxAx2.指出下面演绎推理中的错误，并给出正确的推导过程。（1）①)()(xQxxPP规则②)()(yQyPUS规则：①（2）①))()((xQxPxP规则②)()(bQaPUS规则：①（3）①)()(xxQxPP规则②)()(aQaPES规则：①（4）①)()(aGaPP规则②))()((xGxPxUG规则：①（5）①)()(bGaPP规则②))()((xGxPxEG规则：①（6）①)()(yQyPP规则②))()((xQcPxEG规则：①解：（1）②错，使用US,UG,ES,EG规则应对前束范式，而①中公式不是前束范式，所以不能用US规则。(2)②错，①中公式为)(xxA，这时，)()()(xQxPxA，因而使用US规则时，应得A(a)(或A(y)),故应有)()(aQaP，而不能为)()(bQaP。3.用演绎法证明下列推理式)()())())()((()(xxRxxPyRyQyPyxxP，证明：①)(xxP前提引入②)(aPES①③))())()((()(yRyQyPyxxP前提引入④))())()(((yRyQyPyT①③⑤)())()((aRaQaPUS④⑥)()(aQaPT②⑦)(aRT⑤⑥⑧)(xxREG⑦4.将下列命题符号化，并用演绎推理法证明其结论是有效的。（1）有理数、无理数都是实数；虚数不是实数。因此，虚数既不是有理数，也不是无理数。（个体域取全总个体域）（2）所有的舞蹈者都很有风度；