第2章谓词逻辑习题及答案.解析.docx

    第2章谓词逻辑习题及答案.解析    谓词逻辑习题1. 将下列命题用谓词符号化 （1）小王学过英语和法语 （2）2大于3仅当2大于43）3不是偶数4）2或3是质数5）除非李键是东北人，否则他一定怕冷 解：(1) 令)(x P ：x 学过英语，Q(x)：x 学过法语，c ：小王，命题符号化为)()(c Q c P ∧ (2) 令),(y x P ：x 大于y, 命题符号化为)3,2()4,2(P P → (3) 令)(x P ：x 是偶数，命题符号化为)3(P ? (4) 令)(x P ：x 是质数，命题符号化为)3()2(P P ∨(5) 令)(x P ：x 是北方人；)(x Q ：x 怕冷；c ：李键；命题符号化为)()(x P c Q ?→ 2. 设个体域}{c b a D ，，=，消去下列各式的量词 （1）))()((y Q x P y x ∧?? （2）))()((y Q x P y x ∨??（3）)()(y yQ x xP ?→?（4）))()((y yQ y x P x ?→?，解：(1) 中))()(()(y Q x P y x A ∧?=，显然)(x A 对y 是自由的，故可使用UE 规则，得到 ))()(()(y Q y P y y A ∧?=，因此))()(())()((y Q y P y y Q x P y x ∧?∧??α，再用ES 规则， )()())()((z Q z P y Q y P y ∧∧?α，D z ∈，所以)()())()((z Q z P y Q x P y x ∧∧??α（2）中))()(()(y Q x P y x A ∨?=，它对y 不是自由的，故不能用UI 规则，然而，对)(x A 中约束变元y 改名z ，得到))()((z Q x P z ∨?，这时用UI 规则，可得：))()((y Q x P y x ∨?? ))()((z Q x P z x ∨??? ))()((z Q x P z ∨?α （3）略 （4）略3. 设谓词)(y x P ，表示“x 等于y ”，个体变元x 和y 的个体域都是}321{，，=D 。

求下列各式的真值 （1）)3(，x xP ?（2）)1(y yP ，? （3）)(y x yP x ，??（4）)(y x yP x ，??（5）)(y x yP x ，??（6）)(y x xP y ，??解：(2) 当3=x 时可使式子成立，所以为Ture 3) 当1≠y 时就不成立，所以为False (4) 任意的x,y 使得y x =，显然有y x ≠的情况出现，所以为False 4)存在x,y 使得y x =，显然当1,1==y x 时是一种情况，所以为Ture (5)存在x ，任意的y 使得y x =成立，显然不成立，所以为False (6)任意的y ，存在x ，使得y x =成立，显然不成立，所以为False 4. 令谓词)(x P 表示“x 说德语”，)(x Q 表示“x 了解计算机语言C++”，个体域为杭电全体学生的集合用)(x P 、)(x Q 、量词和逻辑联接词符号化下列语句 （1）杭电有个学生既会说德语又了解C++ （2）杭电有个学生会说德语，但不了解C++ （3）杭电所有学生或会说德语，或了解C++ （4）杭电没有学生会说德语或了解C++假设个体域为全总个体域，谓词)(x M 表示“x 是杭电学生”。

用)(x P 、)(x Q 、)(x M 、量词和逻辑联接词再次符号化上面的4条语句 解：（ⅰ）个体域为杭电全体学生的集合时：（1）))()((x Q x P x ∧? （2）))()((x Q x P x ?∧? （3）))()((x Q x P x ∨? （4）))()((x Q x P x ∨??（ⅱ）假设个体域为全总个体域，谓词)(x M 表示“x 是杭电学生”时：（1）))()()((x Q x P x M x ∧∧? （2）))()()((x Q x P x M x ?∧∧? （3）)))()(()((x Q x P x M x ∨∧? （4）)))()(()((x Q x P x M x ∨?∧?5. 令谓词)(y x P ，表示“x 爱y ”，其中x 和y 的个体域都是全世界所有人的集合用)(y x P ，、量词和逻辑联接词符号化下列语句 （1）每个人都爱王平2）每个人都爱某个人 （3）有个人人都爱的人 （4）没有人爱所有的人 （5）有个张键不爱的人6）有个人人都不爱的人7）恰有一个人人都爱的人8）成龙爱的人恰有两个9）每个人都爱自己10）有人除自己以外谁都不爱解：a ：王平 b ：张键 c ：张龙(1) ）a x xP ,(? (2)),(y x yP x ?? (3)),(y x xP y ?? (4)),(y x P y x ??? (5))(x b P x ，?? (6)),(y x P y x ??? (7))))),(((),((x z z P z x y yP x =→??∧??ωω(8))))()(()(),((y z x z z c P z c P x c P y x y x =∨=→?∧∧∧≠??， (9)),(x x xP ? (10))),((y x y x P y x =??? §2.2 谓词公式及其解释习题2.21. 指出下列谓词公式的指导变元、量词辖域、约束变元和自由变元。

（1）))()((y x Q x P x ，→? （2）)()(y x yQ y x xP ，，?→?（3）)())()((z y x xR z y Q y x P y x ，，，，?∨∧??解： （1）x 是指导变元，x ?的辖域是),()(y x Q x P →，对于x ?的辖域而言，x 是约束变元，y 是自由变元2）x,y 都为指导变元，x ?的辖域是)()(y x yQ y x P ，，?→，y ?的辖域是)(y x Q ，；对于x ?的辖域而言，x,y 都为约束变元，对于y ?的辖域而言，x 是自由变元，y 是约束变元3）x,y 为指导变元，x ?的辖域是)())()((z y x xR z y Q y x P y ，，，，?∨∧?，y ?的辖域是)())()((z y x xR z y Q y x P ，，，，?∨∧，x ?的辖域是)(z y x R ，，；对于x ?的辖域而言，x,y 为约束变元，z 为自由变元，对于y ?的辖域而言，z 为自由变元，y 为约束变元，x 即为约束变元也为自由变元，对于x ?的辖域而言，x 为约束变元，y,z 是自由变元在整个公式中，x,y 即为约束变元又为自由变元，z 为自由变元。

2. 判断下列谓词公式哪些是永真式，哪些是永假式，哪些是可满足式，并说明理由1）))()(())()((y yQ x xP x Q x P x ?∧?→∧? （2）))()(())()((y yQ x xP x Q x P x ?∨?→∨? （3）)())()((y yQ y yQ x xP ?∧?→?? （4）))()(())()((x xQ y P x Q y P x ?→→→? （5）))()(())()((x xQ x P x Q x P x ?→→→? （6）)))()(()((x P y x yQ x P →?→?， （7）))()(()(y x P y x Q y x P ，，，→→解：（1）易知公式是)()(q p q p ∧→∧的代换实例，而 1)()()()(=∧∨∧?=∧→∧q p q p q p q p 是永真式，所以公式是永真式2）易知公式是)()(q p q p ∨→∨的代换实例，而 1)()()()(=∨∨∨?=∨→∨q p q p q p q p 是永真式，所以公式是永真式3）易知公式是q q p ∧→?)(的代换实例，而0)()(=∧?∧=∧∨??=∧→?q q p q q p q q p 是永假式，所以公式是永假式。

4）易知公式是)()(q p q p →→→的代换实例，而 1)()()()(=→∨→?=→→→q p q p q p q p 是永真式，所以公式是永真式5）易知公式是)()(q p q p →→→的代换实例，而 1)()()()(=→∨→?=→→→q p q p q p q p 是永真式，所以公式是永真式6）易知公式是))((p q p →→?的代换实例，而0))(())((=?∧∧=∨?∨??=→→?p q p p q p p q p 是永假式，所以公式是永假式7）易知公式是p q p →→的代换实例，而p q p p q p p q p ∨?∧=∨∨??=→→)()( 是可满足式，所以公式是可满足式 §2.3 谓词公式的等价演算与范式习题2.31. 将下列命题符号化，要求用两种不同的等价形式 （1）没有小于负数的正数2）相等的两个角未必都是对顶角解：（1）)(x P ：x 为负数，)(x Q ：x 是正数，),(y x R ：x 小于y ，命题可符号化为：)))(),(((y Q x P R y x ??或)))(),(((y Q x P R y x ????（2）略2.设)(x P 、)(x Q 和)(y x R ，都是谓词，证明下列各等价式 （1）))()(())()((x Q x P x x Q x P x ?→?=∧?? （2）))()(())()((x Q x P x x Q x P x ?∧?=→??（3）))()()(())()()((y x R y Q x P y x y x R y Q x P y x ，，?∧∧??=→∧??? （4）))()()(())()()((y x R y Q x P y x y x R y Q x P y x ，，?→∧??=∧∧??? 证明：（1）左边＝))()((x Q x P x ∧??＝))()((x Q x P x ?∨?? ＝))()((x Q x P x ?→?＝右边（2）左边 ＝))()((x Q x P x →??＝))()((x Q x P x ∨???＝))()((x Q x P x ?∧?＝右边 （3）左边＝)),()()((y x R y Q x P y x →∧??? ＝)),())()(((y x R y Q x P y x ∨∧???? ＝))()()((y x R y Q x P y x ，?∧∧??＝右边 （4）左边＝),()()((y x R y Q x P y x ∧∧??? ＝),())()((y x R y Q x P y x ?∨∧??? ＝))()()((y x R y Q x P y x ，?→∧??＝右边3. 求下列谓词公式的前束析取范式和前束合取范式。

（1）)()(y x yQ x xP ，?→?（2）))()((z y x yQ y x P x ，，，?→? （3）))()(()(x R z zQ y x yP x →?→???，（4）))()((())()((z y zS y R y y x Q x P x ，，?→?→→?解：（1）)),()((),()(y z Q x P y x y z Q x yP x ∨????→???原式 前束析取范式)),()((y z Q x P y x ?∧???? 前束合取范式（2）原式),,(),((z t x Q y x P t x →???),,(),((z t x Q y x P t x ∨????前束。