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

（3）?x?y(P(x)??C(x)?A(y)?W(x,y)) 结论翻译为：

?x(P(x)??C(x)?D(x)) 归结原理证明 （1）?A(x1)?B(x1)

（2）?P(x2)??B(y)??W(x2,y)?D(x2) （3）P(a) （4）?C(a) （5）A(b) （6）W(a,b)

（7）?P(x3)?C(x3)??D(x3)

（8）C(a)??D(a) （9）?D(a) （10）?P(a)??B(y)??W(a,y) （11）?B(y)??W(a,y) （12）?B(b) （13）?A(b) （14）□ 假设推理证明

（1）

?x(A(x)?B(x)) （2）?x?y((P(x)?B(y)?W(x,y))?D(x)) （3）?x?y(P(x)??C(x)?A(y)?W(x,y)) （4）P(a)??C(a)?A(b)?W(a,b) （5）(P(a)??C(a)?A(b)?W(a,b))?P(a) {a/x3}（7）（3）归结 （4）（8）归结 {a/x2}（9）（2）归结 （3）（10）归结{b/y} （11）（6）归结a/x1} （12）（1）归结 （13）（5）归结 假设 假设 假设 额外假设 公理 36

{

（6）(P(a)??C(a)?A(b)?W(a,b))??C(a) 公理 （7）(P(a)??C(a)?A(b)?W(a,b))?A(b) 公理 （8）(P(a)??C(a)?A(b)?W(a,b))?W(a,b) 公理 （9）P(a) 分（5）（4） （10）?C(a) 分（6）（4） （11）A(b) 分（7）（4） （12）（8）（4） W(a,b) 分（13）A(b)?B(b) 全称量词消去（1） （14）（13）（11） B(b) 分（15）（2） (P(a)?B(b)?W(a,b))?D(a) 全称量词消去（16）P(a)?B(b)?W(a,b) 合取（9）（14）（12） （17）D(a) 分（15）（16）

P(a)??C(a)?D(a) 合取（18）（9）（10）（17） (P(a)??C(a)?D(a))??x(P(x)??C(x)?D(x)) 公理21 （19）

（20）?x(P(x)??C(x)?D(x)) 分（19）（18） 4.6 用归结方法证明下列公式

（1）?x(P(x)?Q(x))，?x(Q(x)??R(x))，?xR(x)├?xP(x) 证明

（1）P(x1)?Q(x1) （2）?Q(x2)??R(x2) （3）R(x3) （4）?P(a)

（5）Q(a) {a/x1}（4）（1）归结

37

（6）?R(a) {a/x2}（2）（5）归结 （7）□ {a/x3}（6）（3）归结 （2）?x?y((P(f(x))?Q(f(b)))?(P(f(a))?P(x)?Q(y))) 证明

目标公式的否定

??x?y((P(f(x))?Q(f(b)))?(P(f(a))?P(x)?Q(y)))

=?x?y((?(P(f(x))?Q(f(b)))?(P(f(a))?P(x)?Q(y)))) =?x?y(P(f(x))?Q(f(b))?(?P(f(a))??P(x)??Q(y))) 化为子句集： （1）P(f(x1)) （2）Q(f(b))

（3）?P(f(a))??P(x2)??Q(y)

（4）?P(x2)??Q(y) {a/x1}（1）（3）归结 （5）?P(x2) {f(b)/y}（4）（2）归结 （6）□ {f(x1)/x2}（5）（1）归结 4.7 已知知识如下：

（1）每个程序员均写过程序； （2）病毒是一种程序；

（3）有些程序员没写过病毒。 结论：有些程序不是病毒。 试用霍恩子句逻辑程序证明之。

证明 先对知识符号化

令P(e)表示e为程序员；

A(e)表示e为程序； B(e)表示e为病毒； W(e1,e2)表示e1写了e2

则已知知识翻译为：

（1）?x(P(x)??y(A(y)?W(x,y)))

38

（2）?x(B(x)?A(x))

（3）?x(P(x)??y(B(y)??W(x,y))) 结论翻译为：

?x(A(x)??B(x)) （1）A(f(x1))?P(x1) （2）W(x2,f(x2))?P(x2) （3）A(x3)?B(x3) （4）P(a)? （5）?B(y),W(a,y) （6）B(x4)?A(x4)

（7）?A(y),W(a,y) {y/x4}（5）（6）归结 （8）?P(x1),W(a,f(x1)) {f(x1)/y}（7）（1）归结 （9）?W(a,f(a)) {a/x1}（8）（4）归结 （10）?P(a) {a/x2}（9）（2）归结 （11）□ （4）（10）归结 4.8 已知有关公司信息的知识： （1）John是PD公司经理； （2）Smith在PD公司任职； （3）Jones在PD公司任职； （4）Peter在PD公司任职； （5）Hall是SD公司经理； （6）Mary在SD公司任职； （7）Bell在SD公司任职； （8）Jones和Mary已结婚；

（9）在某家公司当经理者必在该公司任职；

（10）在某家公司当经理者必是在该公司任职的人的老板； （11）A和B结婚，则B和A结婚； （12）一对夫妇不在同一公司任职；

（13）所有在SD公司任职的已婚者可享有EC保险的人寿保险。 现在查询：

Mary是否在SD公司任职？她结婚了吗？丈夫是谁？她是否享有保险？

39

试用霍恩子句逻辑程序证明之。 证明

令A(e1,e2)表示e1为e2公司的经理； B(e1,e2)表示e1为e2公司的任职； M(e1,e2)表示e1和e2夫妇； C(e1,e2)表示e1为e2的老板； D(e1,e2)表示e1享有e2的人寿保险； E(e)表示e已婚； P(e)表示e为人； F(e)表示e为公司； G(e)表示e已婚；

化为霍恩子句：

（1）A(John，PD)? （2）B(Smith，PD)? （3）B(Jones，PD)? （4）B(Peter，PD)? （5）A(Hall，SD)? （6）B(Mary，SD)? （7）B(Bell，SD)? （8）M(Jones,Mary)? （9）E(Mary)? （10）E(Jones)? （11）F(a)?

40