离散数学课后习题合集(6)

（2）?x(A(x)?B(x,t))??y(A(y)?B(x,y)) 解

A(x)?B(x,t)中的x受?约束，A(y)?B(x,y)中的y受?约束； A(x)?B(x,t)中的x和A(y)?B(x,y)中的y为约束变元； A(x)?B(x,t)中的t和A(y)?B(x,y)中的x为自由变元。

3.5 已知公式?xA(x)??y(B(x,y)?P(y))

（1）试对公式中的自由变元x代以y3?2。 解

先对公式改名，以防止代入后改变变元的约束关系

原式=?xA(x)??u(B(x,u)?P(u)) 公式中的自由变元x代以y3?2后得： ?xA(x)??u(B(y3?2,u)?P(u))

（2）试对公式中的谓词变元B(e1,e2)代以式子?xC(e1,e2,x,y)。 解

先对公式和代入进行改名，以防止代入后改变变元的约束关系 原式改名为：

?xA(x)??u(B(x,u)?P(u)) 代入式改名为： ?vC(e1,e2,v,y) 代入后的式子为：

?xA(x)??u(?vC(x,u,v,y)?P(u))

3.6 试讨论公式?x?yX(x,y)在个体域{1,2}上的成真解释和成假解释。

解

个体域{1,2}上的二元谓词共有16类谓词，见下表：

26

12 31516e1 e2 X X X ??X X

1 1 T F T ? ? F F 1 2 T T F ? ? F F 2 1 T T T ? ? F F 2 2 T T T ? ? T F

所以，公式的成假解释为({1,2};Xi)其中i?2..16；成真解释为({1,2};X1)。 3.7 利用量词的等价公式判断下列两组公式是否等价，其中?中不含自由的x。

（1）r??x?(x)和?x(r??(x)) 解

因为 r??x?(x)=????x?(x)=?x(????(x))=?x(???(x)) 所以，两公式等价。

（2）??x??(x)????x(?(x)??) 解

因为 ??x??(x)????x??(x)????x(??(x)??)

??x(?(x)??)??x(?(x)?r) 所以，两公式不等价。

3.8 试讨论公式?x(X(x)?Y(x))?(?xX(x)??x(Y(x))的永真性和可满足性。

解

（1）讨论公式在1域{1}上的情况 原式=(X(1)?Y(1))?(X(1)?Y(1))?T 公式在1域上永真。

（2）讨论公式在2域{1,2}上的情况

2域上的一元谓词共有四类，见下表：

e X1 X2 X3 X4

1 T F T F

2 T T F F因为公式在解释(I;X,Y)?({1,2);X2,X3)下

原式=?x(X2(x)?X3(x))?(?xX2(x)??xX3(x))

27

=T?(F?F)

=T?F =F

所以，公式在2域上存在成假解释。

又因为公式在1域上永真，所以由定理知，公式在2域上可满足。 综上，公式在2域上可满足，但非永真。 （3）讨论公式在k(k?3)域上的情况

因为公式在2域上可满足，所以由定理知，公式在k域上可满足。

假设公式在k域上永真，由定理大永真可推出小永真知，公式在2域上永真，矛盾，因此公式在k域上非永真。

3.9 试讨论公式?x(X(x)?Y(x))?(?xX(x)??xY(x))的永真性和可满足性。

解

公式在k域{1,2,3,??,k}上永真。

因为?x(X(x)?Y(x))?(X(1)?Y(1))?(X(2)?Y(2))???(X(k)?Y(k)) ?(X(1)?X(2)???X(k))?(Y(1)?Y(2)???Y(k)) ?(?xX(x)??xY(x)) 所以，公式在k域{1,2,3,??,k}上永真。 3.10 试求出下列公式的前束范式和SKOLEM标准形。

（1）??x(?(?yX(x,y))?(??zY(z)?Z(x))) 解

原式=??x(?yX(x,y)?(??zY(z)?Z(x))) =?x(?y?X(x,y)?(?zY(z)??Z(x)))

=?x?y?z(?X(x,y)?(Y(z)??Z(x)))（前束范式）

) ??x?z(?X(x,f(x))?(Y(z)??Z(x))

??x(?X(x,f(x))?(Y(g(x))??Z(x)))（SKOLEM标准形） （2）?x?y?z(X(x,y,z)?(?uY(u,x)??xW(y,x))) 解

原式=?x?y?z(X(x,y,z)?(?u?Y(u,x)??xW(y,x)))

28

=?x?y?z(X(x,y,z)?(?u?Y(u,x)??vW(y,v)))

=?x?y?z?u?v(X(x,y,z)?(?Y(u,x)?W(y,v)))（前束范式） ??y?z?u?v(X(a,y,z)?(?Y(u,a)?W(y,v)))

??y?z?u(X(a,y,z)?(?Y(u,a)?W(y,f(x,y,z))))（SKOLEM标准形）

3.11 试用唯一性量词或摹状词符号化下列语句：

（1）只有一个人去过南极。 解

令P(e)表示e为人； A(e1,e2)表示e1去过e2； a表示南极； 则原句译为：

?!x(P(x)?A(x,a))

（2）最后一个离开办公室的人关门窗关电源。 解

令P(e)表示e为人；

A(e1,e2)表示e1 比e2晚离开办公室； B(e1,e2)表示e1关e2； b表示门窗； c表示电源；

又令t??yx(P(x)??z(P(z)?A(x,z)))

则原句译为： B(t,b)?B(t,c)。 （3）并非年龄最大的人最有知识。 解

令P(e)表示e为人；

A(e1,e2)表示e1 比e2年龄大； B(e1,e2)表示e1比e2有知识；

又令t??yx(P(x)??z(P(z)?A(x,z)))

29

则原句译为：

??x(P(x)?B(t,x))。

（4）每个数均有唯一的一个数是它的后继。 解

令P(e)表示e为数；

A(e1,e2)表示e1 是e2的后继； 则原句译为：

?x(P(x)??!y(P(y)?A(y,x)))。30