第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

(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.2 1. 指出下列谓词公式的指导变元、量词辖域、约束变元和自由变元。 （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 4

是永真式，所以公式是永真式。 （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.3 1. 将下列命题符号化，要求用两种不同的等价形式。 （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.4 1.证明：))()(())()((xBxAxxBxAx