离散数学答案 第三章 谓词逻辑

第三章 谓词逻辑

习题3.1

1．解 ⑴个体：离散数学；谓词：…是一门计算机基础课程。

⑵个体：田亮；谓词：…是一名优秀的跳水运动员。

⑶个体：大学生；谓词：…要好好学习计算机课程；量词：所有。

⑷个体：推理；谓词：…是能够由计算机来完成的；量词：一切。

2． 解 ⑴设F(x)：x是舞蹈演员；a：小芳。命题符号化：F(a)。

⑵设F(x)：x是一位有名的哲学家；a：苏格拉底。命题符号化：F(a)。

⑶设F(x)：x作完了他的作业家；a：张三。命题符号化：F(a)。 ⑷设F(x)：x身体很好；a：我。命题符号化：F(a)。

3．解 ⑴选取个体域为整数集合。设F(x)：x的平方是奇数；G(x)：x是奇数。命题符号化：F(x)G(x)。

⑵选取个体域为所有国家的集合。设F(x)：x在南半球；G(x)：x在北半球。命题符号化：xF(x)xG(x)。

⑶选取个体域为所有人的集合。设F(x)：x在中国居住；G(x)：x是中国人。命题符号化：x(F(x)G(x))

⑷选取个体域为所有人的集合。设M(x)：x是艺术家；F(x)：x是导演；G(x)：x是演员。命题符号化：x(M(x)F(x)G(x))。

⑸选取个体域为所有猫的集合。设M(x)：x是好猫；F(x)：x捉耗子。命题符号化：xM(x)x(F(x)M(x))。

G(x)：xF(x)xG(x)。4．解 ⑴①设F(x)：x喜欢开汽车；x喜欢骑自行车。命题符号化：

②设F(x)：x喜欢开汽车；G(x)：x喜欢骑自行车；M(x)：x是人。命题符号化：

x(M(x)F(x))x(M(x)G(x))。

⑵①设F(x)：x必须学好数学。命题符号化：xF(x)。

②设F(x)：x必须学好数学；M(x)：x是学生。命题符号化：x(M(x)F(x))。

⑶①设F(x)：x的平方是质数；M(x)：x是质数。命题符号化： x(M(x)F(x))。

②同①。

③设F(x)：x的平方是质数。命题符号化：x(F(x))。

习题3.2

1．解 ⑴x的辖域为P(x)Q(x)，个体变元x是约束变元。

⑵x的辖域为P(x)yQ(x,y)，y的辖域为Q(x,y)，个体变元x是约束变元，个体变元y是约束变元。

⑶x的辖域为F(x,y)，其中个体变元x是约束变元，个体变元y是自由变元；的辖域为Q(x,y)，其中个体变元x是自由变元，个体变元y是约束变元。

2．解 ⑴st(P(s,z)Q(t))S(x,y)。

⑵M(x,y)s(P(s,y)zQ(s,z))。

3．解 ⑴(xP(x)yQ(x))F(s,z)；

⑵y(P(s,y)(zQ(s,z)R(s,y,v)))xrS(x,t,r)。

4．解 ⑴S(x),xS(x),S(x)xS(x)的真值分别为：0，1，0。

⑵S(x),xS(x),S(x)xS(x)的真值分别为：0，1，0。

⑶S(x),xS(x),S(x)xS(x)的真值分别为：1，1，1。

⑷S(x),xS(x),S(x)xS(x)的真值分别为：0，0，0。

5．解 ⑴0。 ⑵1。 ⑶0。

6．解 ⑴设I为任意解释，其个体域为D，若xP(x)为真，即xP(x)为假，则xP(x)xP(x)为真；若xP(x)为假，即xP(x)为真，则就是说在个体域中不存在使得

P(x)为真的个体，故xP(x)为假，即xP(x)xP(x)为假。因此xP(x)xP(x)仅为可

满足式。

⑵设I为任意解释，其个体域为D，若xA(x)为假,则xA(x)为真，就是说对于个体域中任意一个个体A(x)均为真，那么A(x)必为假，所以x(A(x))必为假；若xA(x)为真，即xA(x)为假，则就是说对于个体域中至少存在一个体使A(x)均为假，那么对于个体域中至少存在一个个体使A(x)为真，所以x(A(x))必为真，总之xA(x)x(A(x))对于个体域中任意一个个体必为真，即其为逻辑有效式。

⑶设I为任意解释，其个体域为D，若x(P(x)Q(x))为真，即是说在个体域中至少存在一个个体使得P(x)和Q(x)同时为真，此时x(P(x)Q(x))可真可假，所以，x(P(x)Q(x))

x(P(x)Q(x))可真可假。因此，(x(P(x)Q(x)))(xP(x)Q(x))仅为可满足式。

习题3.3

1．解 ⑴(xA(x)xB(x))(xA(x)xB(x))

xA(x)xB(x))xA(x)xB(x))

⑵(xA(x)B(x)xC(x))xA(x)B(x)xC(x)

xA(x)B(x)xC(x)

⑶((xA(x)xB(x))xC(x))

((xA(x)xB(x))(xA(x)xB(x)))xC(x)

(xA(x)xB(x))(xA(x)xB(x))xC(x)。

2．证明 ⑴x(P(x)Q(x))(xP(x)xQ(x))

x(P(x)Q(x))(xP(x)xQ(x))x(P(x)Q(x))xP(x)xQ(x)

((P(1)Q(1))((P(2)Q(2))((P(3)Q(3)))(P(1)P(2)P(3))

Q(1)Q(2)Q(3)

((P(1)Q(1))((P(2)Q(2))((P(3)Q(3)))(P(1)P(2)P(3))

(P(1)P(2)P(3))(Q(1)Q(2)Q(3))(P(1)P(2)P(3))

1。

故x(P(x)Q(x))(xP(x)xQ(x))为逻辑有效式。

⑵(xP(x)xQ(x))x(P(x)Q(x))(xP(x)xQ(x))x(P(x)Q(x))

(xP(x)xQ(x))x(P(x)Q(x))

((P(1)P(2)P(3))(Q(1)Q(2)Q(3))

((P(1)Q(1))P(2)Q(2))P(2)Q(2)))

[(P(1)Q(1))(P(2)Q(2))(P(3)Q(3))(P(1)Q(2))]

((P(1)Q(1))(P(2)Q(2))(P(1)Q(1)))

((P(1)Q(1))(P(1)Q(1))(P(2)Q(2))(P(3)Q(3))(P(1)Q(2)))

((P(2)Q(2))(P(1)Q(1))(P(2)Q(2))(P(3)Q(3))(P(1)Q(2)))

((P(1)Q(1))(P(1)Q(1))(P(2)Q(2))(P(3)Q(3))(P(1)Q(2)))

111。

⑶x(A(x)B(x))(xA(x)xB(x))

((A(1)B(1))(A(2)B(2))(A(3)B(3)))

((A(1)A(2)A(3))(B(1)B(2)B(3)))

1

习题3.4

1．解 ⑴④错。在一个逻辑推理过程中，若同时用到ES和US，并且选用代替的个体变元相同时应先用ES，再用US。

⑵②错，在用UG规则时，引入的个体变元在原来的公式中不能自由出现过。③错。

⑶④错，在用两次ES规则时，引入的个体常元不能是一样的。

2．⑴证明

①xQ(x) P

②Q(y) T①US

③x(P(x)Q(x)) P

④P(y)Q(y) T③US

⑤P(y) T②④拒取式

⑥xP(x) T⑤EG

⑵证明

①xP(x) P附加前提引入

②P(c) T①US

③x(P(x)Q(x)) P

④P(c)Q(c) T③US

⑤Q(c) T②④假言推理

⑥xQ(x) ⑦xP(x)xQ(x) ⑶证明

①x(P(x)Q(x)) ②x(P(x)Q(x)) ③P(c)Q(c) ④xQ(x) ⑤Q(c) ⑥Q(c) ⑦Q(c)Q(c) T⑤UG

T①⑥CP

P

T①量词否定，德摩根律

T②ES

P否定结论引入

T④US

T③化简

T⑤⑥合取

由⑦得到矛盾，由间接证明原理，原命题得证明。

3． 解 ⑴设M(x)：x是鸟；N(x)：x是猴子，F(x)：x会飞。

前提：x(M(x)F(x))，x(N(x)F(x))

结论：x(N(x)M(x))

证明

①x(N(x)F(x)) P

②N(y)F(y) T①US

③x(M(x)F(x)) P

④M(y)F(y) T③US

⑤F(y)M(y) T④假言易位

⑥N(y)M(y) T②⑤假言三段论

⑦x(N(x)M(x)) T⑥UG

⑵设M(x)：x是学生；N(x)：x是教师；F(x)：x是骗子；R(x, y)：x相信y。

前提：x(M(x)y(N(y)R(x, y)))，x(M(x)y(F(y)R(x, y)))

结论：x(N(x)F(x))

证明

①x(M(x)y(N(y)R(x, y))) ②M(c)y(N(y)R(c, y)) ③M(c) ④x(M(x)y(F(y)R(x, y))) ⑤M(c)y(F(y)R(c, y)) ⑥y(F(y)R(c, y)) ⑦F(d)R(c, d) ⑧y(N(y)R(c, y)) ⑨N(d)R(c, d) ⑩R(c, d)F(d) P

T①ES

T②化简

P

T④US

T③⑤假言推理

T⑥US

T②化简

T⑧US

T⑦假言易位

⑾N(d)F(d) T⑨⑩假言三段论

⑿x(N(x)F(x)) T⑾UG

⑶设M(x)：x是学术会成员；N(x)：x是工人；R(x)：x是专家；Q(x)：x是青年人。

前提：x(M(x)(N(x)R(x)))，x(M(x)Q(x))

结论：x(M(x)Q(x)R(x))

证明

①x(M(x)Q(x)) ②M(c)Q(c) ③x(M(x)(N(x)R(x))) ④M(c)(N(c)R(c)) ⑤M(c) ⑥N(c)R(c) ⑦R(c) P

T①ES

P

T③US

T②化简

T④⑤假言推理

T⑥化简

⑧M(c)Q(c)R(c) T②⑦合取

⑨x(M(x)Q(x)R(x)) T⑧EG

复习题3

1．解 ⑴设个体域是整数集合I，F(x)：x是最大的整数，命题符号化为xF(x)。

⑵设M(x)：x是学生，F(x)：x要好好学习。命题符号化x(M(x)F(x))。

⑶设M(x)：x是液体，F(x)：x能溶于水。命题符号化x(M(x)F(x))。

⑷设M(x)：x是人，F(x, y)：x与y一样高。命题符号化x((M(x)M(y))F(x, y))。

⑸设M(x)：x是数，F(x)：x是实数，G(x)：x是复数。命题符号化x(M(x)(F(x)G(x)))。

⑹设M(x)：x是数，F(x)：x是奇数，G(x)：x是偶数，H(x)：x是2。命题符号化

x(M(x)((F(x)G(x))H(x)))。

⑺设M(x)：x不是地球，F(x)：x上有人，c：金星。命题符号化

x(M(x)F(x))F(c)。

2．解 ⑴x(A(x)B(x))

(A(1)B(1))(A(2)B(2))(A(3)B(3))

0000。

⑵x(A(x)(x2))

(A(1)(12))(A(2)(22))(A(3)(32))

1010。

3．解 ⑴x的辖域P(x)Q(y)，其中x是约束变元，y是自由变元；y的辖域M(x,y)，其中x是自由变元，y是约束变元。

⑵x的辖域P(x)，x的辖域M(x)，其中x在两个量词的不同辖域中都是约束变元，

y是自由变元。

⑶x的辖域P(x,y)，其中x是约束变元，y是自由变元；y的辖域Q(y)，其中y是约束变元。

⑷x的辖域yP(x,y)，y的辖域P(x,y)，整个公式中x是约束变元，y约束变元1次，自由变元1次。

4．解 !xP(x)x(P(x)y(P(y)(y=x)))。

5．解 ⑴xP(x)xQ(x)

P(a)P(b)P(c)Q(a)Q(b)Q(c)

⑵x(P(x)xQ(x))

(P(a)(Q(a)Q(b)Q(c)))(P(b)(Q(a)Q(b)Q(c)))(P(c)(Q(a)Q(b)Q(c)))

⑶xyR(x,y)yR(a,y)yR(b,y)yR(c,y)

(R(a,a)R(a,b)R(a,c))(R(b,a)R(b,b)R(b,c))(R(c,a)R(c,b)R(c,c))

6．解 ⑴设个体域为D={a，b}，令P(a)=1；P(b)=0；Q(a)=0；Q(b)=1。则xP(x)为假，xQ(x)为假，从而xP(x)xQ(x)为真。由于P(a)Q(a)为假，所以x(P(x) Q(x))也为假，此时公式为假。因此，公式不是逻辑有效式。

⑵ 设D={a}，若R(a)=1，P(a)=0，Q(a)=1，则x(P(x)Q(x))为假，而x((P(x)R(x))(Q(x)R(x)))为真，因此原公式为假。因此，公式不是逻辑有效式。

⑶设个体域D={a，b}，Q(a)=Q(b)=0，取P(a)=1，P(b)=0。则x(P(x)Q(y))为真，而(xP(x)Q(y))为假。因此，原公式不是逻辑有效式。

⑷xy(P(x)Q(y))xy(P(x)Q(y))x(P(x)yQ(y))

xP(x)y Q(y)xP(x)yQ(y)xP(x)yQ(y)

因此，原公式为逻辑有效式。

7．⑴证明 z(A(x)B(x))

x(A(x)B(x))

xA(x)x B(x))

xA(x)x B(x))

xA(x) x B(x))

⑵证明 xP(x)yQ(y)

xP(x)yQ(y)

xP(x)yQ(y)

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

xy(P(x)Q(y))

9．⑴证明

①xF(x) ②F(c) P

T①ES

③xF(x)y((F(y)G(y))R(y)) P

④F(c)y((F(y)G(y))R(y)) T③US

⑤y((F(y)G(y))R(y)) T②④假言推理

⑥(F(c)G(c))R(c) ⑦F(c)G(c) ⑧R(c) ⑨F(c)R(c) ⑩x(F(x)R(x)) ⑵证明

①x(C(x)B(x)) ②C(y)B(y) ③x(A(x)B(x)) ④A(y)B(y) T⑤US

T⑥附加

T⑤⑦假言推理

T⑥⑧合取

T⑨EG

P

T②US

P

T③US

⑤B(y)A(y) T④假言易位

⑥C(y)A(y) T②⑤假言三段论

⑦x(C(x)A(x)) T⑧UG

x(H(x))A(x))xy((H(y)N(x, y))y(A(y)N(x, y))

⑶证明

①xy((H(y)N(x, y)) P附加前提引入

②y((H(y)N(x, y)) T①US

③H(v)N(x, v) T②US

④x(H(x))A(x)) P

⑤H(v)A(v) T④US

⑥H(v) T③化简

⑥A(v) T⑤⑥假言推理

⑦N(x, v) T③化简

⑧A(v)N(x, v) T⑥⑦合取

⑨y(A(y)N(x, y)) T⑧EG

⑩xy((H(y)N(x, y))y(A(y)N(x, y)) T①⑨CP

10．解 ⑴设M(x)：x是航海家，F(x)：x教育自己的孩子成为航海家，G(x)：x教育他的孩子去做飞行家。

前提：x(M(x)F(x))，x(G(x)F(x))，xG(x)

结论：xM(x)

证明

①xG(x) P

②G(c) T①ES

③x(G(x)F(x)) P

④G(c)F(c) T③US

⑤F(c) T②④假言推理

⑥x(M(x)F(x)) P

⑦M(c)F(c) T⑥US

⑧M(c) T⑤⑦拒取式

⑨xM(x) T⑨UG

⑵设M(x)：x是哺乳动物，N(x)：x是脊椎动物，F(x)：x是胎生动物。

前提：x(M(x)N(x))，x(M(x)F(x)).

结论：x(N(x)F(x))

证明

①x(M(x)F(x)) P

②M(c)F(c) T①ES

③x(M(x)N(x)) P

④M(c)N(c) T③US

⑤M(c) T②化简

⑥N(c) T④⑤假言推理

⑦F(c) T②化简

⑧N(c)F(c) T⑥⑦合取

⑨x(N(x)F(x)) T⑧EG

⑶设F(x)：x是有理数，G(x)：x是无理数，M(x)：x是实数，N(x)：x是虚数。

前提：x(F(x)M(x))，x(G(x)M(x))，x(N(x)M(x))

结论：x(N(x)(F(x) G(x)))

证明

①x(N(x)M(x)) P

②N(y)M(y) T①US

③x(F(x)M(x)) P

④F(y)M(y) T③US

⑤M(y)F(y) T②④假言易位

⑥N(y)F(y) T②⑤假言三段论

⑦x(G(x)M(x)) P

⑧G(y)M(y) T⑦US

⑨M(y)G(y) T⑦假言易位

⑩N(y)G(y) ⑾(N(y)F(y))(N(y)G(y)) ⑿N(y)（F(y)G(y)） ⒀x(N(x)(F(x) G(x))) T②⑨假言三段论

T⑥⑩合取

T⑾蕴涵等价式，分配律

T⑿UG