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

2020-02-28 其他范文下载本文

第2章谓词逻辑习题及答案由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“谓词逻辑练习及答案”。

谓词逻辑习题

1.将下列命题用谓词符号化。（1）小王学过英语和法语。（3）3不是偶数。

（2）2大于3仅当2大于4。（4）2或3是质数。

（5）除非李键是东北人，否则他一定怕冷。解：

(1)令P(x)：x学过英语，Q(x)：x学过法语，c：小王，命题符号化为P(c)Q(c)(2)令P(x,y)：x大于y, 命题符号化为P(2,4)P(2,3)(3)令P(x)：x是偶数，命题符号化为P(3)(4)令P(x)：x是质数，命题符号化为P(2)P(3)

(5)令P(x)：x是北方人；Q(x)：x怕冷；c：李键；命题符号化为Q(c)P(x)

b，c}，消去下列各式的量词。2.设个体域D{a，（1）xy(P(x)Q(y))（3）xP(x)yQ(y)

（2）xy(P(x)Q(y))（4）x(P(x，y)yQ(y))

解：

(1)中A(x)y(P(x)Q(y))，显然A(x)对y是自由的，故可使用UE规则，得到

A(y)y(P(y)Q(y))，因此xy(P(x)Q(y))y(P(y)Q(y))，再用ES规则，y(P(y)Q(y))P(z)Q(z)，zD，所以xy(P(x)Q(y))P(z)Q(z)

（2）中A(x)y(P(x)Q(y))，它对y不是自由的，故不能用UI规则，然而，对

A(x)中约束变元y改名z，得到z(P(x)Q(z))，这时用UI规则，可得：

xy(P(x)Q(y))

xz(P(x)Q(z))

z(P(x)Q(z))（3）略（4）略，2，3}。求下列各式3.设谓词P(x，y)表示“x等于y”，个体变元x和y的个体域都是D{1（1）xP(x，3)的真值。，y)（2）yP(1y)（4）xyP(x，y)（6）yxP(x，y)

（3）xyP(x，y)（5）xyP(x，解：

(2)当x3时可使式子成立，所以为Ture。

(3)当y1时就不成立，所以为False。

(4)任意的x,y使得xy，显然有xy的情况出现，所以为False。

(4)存在x,y使得xy，显然当x1,y1时是一种情况，所以为Ture。

(5)存在x，任意的y使得xy成立，显然不成立，所以为False。

(6)任意的y，存在x，使得xy成立，显然不成立，所以为False。

4.令谓词P(x)表示“x说德语”，Q(x)表示“x了解计算机语言C++”，个体域为杭电全体学生的集合。用P(x)、Q(x)、量词和逻辑联接词符号化下列语句。

（1）杭电有个学生既会说德语又了解C++。（2）杭电有个学生会说德语，但不了解C++。（3）杭电所有学生或会说德语，或了解C++。（4）杭电没有学生会说德语或了解C++。

假设个体域为全总个体域，谓词M(x)表示“x是杭电学生”。用P(x)、Q(x)、M(x)、量词和逻辑联接词再次符号化上面的4条语句。解：（ⅰ）个体域为杭电全体学生的集合时：

（1）x(P(x)Q(x))（2）x(P(x)Q(x))（3）x(P(x)Q(x))（4）x(P(x)Q(x))

（ⅱ）假设个体域为全总个体域，谓词M(x)表示“x是杭电学生”时：

（1）x(M(x)P(x)Q(x))（2）x(M(x)P(x)Q(x))（3）x(M(x)(P(x)Q(x)))（4）x(M(x)(P(x)Q(x)))

5.令谓词P(x，y)表示“x爱y”，其中x和y的个体域都是全世界所有人的集合。用P(x，y)、量词和逻辑联接词符号化下列语句。

（1）每个人都爱王平。

（2）每个人都爱某个人。（4）没有人爱所有的人。（6）有个人人都不爱的人。（8）成龙爱的人恰有两个。

（3）有个人人都爱的人。

（5）有个张键不爱的人。

（7）恰有一个人人都爱的人。

（9）每个人都爱自己。

（10）有人除自己以外谁都不爱。

解：a：王平 b：张键

c：张龙

(1)xP(x,a）

(2)xyP(x,y)(3)yxP(x,y)

(4)xyP(x,y)(5)xP(b，x)

(6)xyP(x,y)(7)x(yP(y,x)z((P(,z))zx))

(8)xy(xyP(c,x)P(c)z(P(c，z)(zxzy)))(9)xP(x,x)

(10)xy(P(x,y)xy)§2.2 谓词公式及其解释

习题2.2 1.指出下列谓词公式的指导变元、量词辖域、约束变元和自由变元。

（1）x(P(x)Q(x，y))（2）xP(x，y)yQ(x，y)

（3）xy(P(x，y)Q(y，z))xR(x，y，z)

解：（1）x是指导变元，x的辖域是P(x)Q(x,y)，对于x的辖域而言，x是约束变元，y是自由变元。

（2）x,y都为指导变元，x的辖域是P(x，y)yQ(x，y)，y的辖域是Q(x，y)；对于x的辖域而言，x,y都为约束变元，对于y的辖域而言，x是自由变元，y是约束变元。

（3）x,y为指导变元，x的辖域是y(P(x，y)Q(y，z))xR(x，y，z)，y的辖域是(P(x，y)Q(y，z))xR(x，y，z)，x的辖域是R(x，y，z)；对于x的辖域而言，x,y为约束变元，z为自由变元，对于y的辖域而言，z为自由变元，y为约束变元，x即为约束变元也为自由变元，对于x的辖域而言，x为约束变元，y,z是自由变元。在整个公式中，x,y即为约束变元又为自由变元，z为自由变元。

2.判断下列谓词公式哪些是永真式，哪些是永假式，哪些是可满足式，并说明理由。（1）x(P(x)Q(x))(xP(x)yQ(y))（2）x(P(x)Q(x))(xP(x)yQ(y))（3）(xP(x)yQ(y))yQ(y)（4）x(P(y)Q(x))(P(y)xQ(x))（5）x(P(x)Q(x))(P(x)xQ(x))（6）(P(x)(yQ(x，y)P(x)))（7）P(x，y)(Q(x，y)P(x，y))

解：（1）易知公式是(pq)(pq)的代换实例，而

(pq)(pq)(pq)(pq)1 是永真式，所以公式是永真式。

（2）易知公式是(pq)(pq)的代换实例，而

(pq)(pq)(pq)(pq)1 是永真式，所以公式是永真式。

（3）易知公式是(pq)q的代换实例，而

(pq)q(pq)qpqq0 是永假式，所以公式是永假式。

（4）易知公式是(pq)(pq)的代换实例，而

(pq)(pq)(pq)(pq)1 是永真式，所以公式是永真式。

（5）易知公式是(pq)(pq)的代换实例，而

(pq)(pq)(pq)(pq)1 是永真式，所以公式是永真式。

（6）易知公式是(p(qp))的代换实例，而

(p(qp))(p(qp))pqp0 是永假式，所以公式是永假式。

（7）易知公式是pqp的代换实例，而

pqp(pq)p(pq)p 是可满足式，所以公式是可满足式。§2.3 谓词公式的等价演算与范式

习题2.3 1.将下列命题符号化，要求用两种不同的等价形式。（1）没有小于负数的正数。

（2）相等的两个角未必都是对顶角。

解：（1）P(x)：x为负数，Q(x)：x是正数，R(x,y)：x小于y，命题可符号化为：xy(R(P(x),Q(y)))或xy(R(P(x),Q(y)))

（2）略

2.设P(x)、Q(x)和R(x，y)都是谓词，证明下列各等价式（1）x(P(x)Q(x))x(P(x)Q(x))（2）x(P(x)Q(x))x(P(x)Q(x))

（3）xy(P(x)Q(y)R(x，y))xy(P(x)Q(y)R(x，y))（4）xy(P(x)Q(y)R(x，y))xy(P(x)Q(y)R(x，y))证明：（1）左边＝x(P(x)Q(x))

＝x(P(x)Q(x))＝x(P(x)Q(x))＝右边

（2）左边＝x(P(x)Q(x))

＝x(P(x)Q(x))

＝x(P(x)Q(x))＝右边

（3）左边＝xy(P(x)Q(y)R(x,y))

＝xy((P(x)Q(y))R(x,y))

＝xy(P(x)Q(y)R(x，y))＝右边

（4）左边＝xy(P(x)Q(y)R(x,y)

＝xy(P(x)Q(y))R(x,y)

＝xy(P(x)Q(y)R(x，y))＝右边

3.求下列谓词公式的前束析取范式和前束合取范式。（1）xP(x)yQ(x，y)

（2）x(P(x，y)yQ(x，y，z))（3）xyP(x，y)(zQ(z)R(x))

（4）x(P(x)Q(x，y))(y(R(y)zS(y，z))

解：（1）原式xyP(x)Q(z,y)xy(P(x)Q(z,y))

前束析取范式

xy(P(x)Q(z,y))

前束合取范式

（2）原式xt(P(x,y)Q(x,t,z)xt(P(x,y)Q(x,t,z)前束析取范式

xt(P(x,y)Q(x,t,z)

前束合取范式（3）原式xyz(P(x,y)(Q(z)R(t))

xyz(P(x,y)Q(z)R(t))

前束析取范式

xyz(P(x,y)Q(z)R(t))

前束合取范式（4）原式x(P(x)Q(x，y))(t(R(t)zS(t，z))

xtz((P(x)Q(x,y))(R(t)S(t,z)))

xtz((P(x)Q(x,y))(R(t)S(t,z)))

xtz((P(x)Q(x,y)R(t))(P(x)Q(x,y)S(t,z)))

xtz((P(x)(R(t)S(t,z))(Q(x,y)R(t)S(t,z)

§2.4 谓词公式的推理演算

习题2.4 1.证明：x(A(x)B(x))x(A(x)B(x))

证明：（1）左边x(A(x)B(x))x(A(x)B(x))

x(A(x)B(x))＝x(A(x)B(x))2.指出下面演绎推理中的错误，并给出正确的推导过程。（1）①xP(x)Q(x)

②P(y)Q(y)

P规则 US规则：① P规则 US规则：① P规则 ES规则：① P规则 UG规则：① P规则 EG规则：① P规则 EG规则：①（2）①x(P(x)Q(x))

②P(a)Q(b)

（3）①P(x)xQ(x)

②P(a)Q(a)（4）①P(a)G(a)

②x(P(x)G(x))

（5）①P(a)G(b)

②x(P(x)G(x))

（6）①P(y)Q(y)

②x(P(c)Q(x))

解：（1）②错，使用US,UG,ES,EG规则应对前束范式，而①中公式不是前束范式，所以不能用US规则。

A(x)P(x)Q(x)，(2)②错，①中公式为xA(x)，这时，因而使用US规则时，应得A(a)(或A(y)),故应有P(a)Q(a)，而不能为P(a)Q(b)。

3.用演绎法证明下列推理式

xP(x)y((P(y)Q(y))R(y))，xP(x)xR(x)

证明：① xP(x)前提引入

② P(a)ES①

③ xP(x)y((P(y)Q(y))R(y))

前提引入

④ y((P(y)Q(y))R(y))T①③

⑤(P(a)Q(a))R(a)US④

⑥ P(a)Q(a)

T②

⑦ R(a)T⑤⑥

⑧ xR(x)EG⑦

4.将下列命题符号化，并用演绎推理法证明其结论是有效的。（1）有理数、无理数都是实数；虚数不是实数。因此，虚数既不是有理数，也不是无理数。（个体域取全总个体域）（2）所有的舞蹈者都很有风度；万英是个学生并且是个舞蹈者。因此，有些学生很有风度。（个体域取人类全体组成的集合）（3）每个喜欢步行的人都不喜欢骑自行车；每个人或者喜欢骑自行车或者喜欢乘汽车；有的人不喜欢乘汽车。所以有的人不喜欢步行。（个体域取人类全体组成的集合）（4）每个旅客或者坐头等舱或者坐经济舱；每个旅客当且仅当他富裕时坐头等舱；有些旅客富裕但并非所有的旅客都富裕。因此有些旅客坐经济舱。（个体域取全体旅客组成的集合）

解：(2)证明：设P(x)：x 是个舞蹈者； Q(x)：x很有风度； S(x)：x是个学生； a：王华

上述句子符号化为：

前提：x(P(x)Q(x))、S(a)P(a)结论：x(S(x)Q(x))

（1）S(a)P(a)P（2）x(P(x)Q(x))P（3）P(a)Q(a)（4）P(a)（5）Q(a).（6）S(a)（7）S(a)Q(a)（8）x(S(x)Q(x)

]（3）命题符号化为：F(x)：x喜欢步行,G(x)：x喜欢骑自行车，H(x)：x喜欢坐汽车。

US（2）T（1）I T（3）（4）I T（1）I T（5）（6）I EG（7）

前提：x(F(x)G(x))，x(G(x)H(x))，x(H(x))

结论：x(F(x)).证明：(1)x(H(x))P(2)H(c)ES(1)(3)x(G(x)H(x))

P(4)G(c)H(c)US(3)(5)G(c)T(2)(4)I(6)x(F(x)G(x))

P(7)F(c)G(c)US(6)(8)F(c)T(5)(7)I(9)x(F(x))

EG(8)

（4）命题符号化为：F(x)：x坐头等舱, G(x)：x坐经济舱，H(x)：x富裕。