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

（12）B(y,a)?P(y),A(y,x) （13）P(c)? （14）F(b)? （15）A(c,b)? （16）C(c,z)?A(z,b) （17）M(x1,y1)?M(y1,x1) （18）G(Jones)? （19）G(Mary)?

（20）D(x2,EC)?B(x2,SD),E(x2) 问Mary是否在SD公司任职？翻译为子句：（21）?B(Mary,SD)

（22）□ 所以Mary在SD公司任职。 问她结婚了吗？翻译为子句： （23）?E(Mary)

（24）□ 所以MARY已婚。

问丈夫是谁？翻译为子句： （25）?M(x3,Mary)

（26）□ 所以Mary的丈夫是Jones。 她是否享有保险？翻译为子句： （27）?D(Mary,EC)

（28）?B(Mary,SD),E(Mary) （29）?E(Mary) （30）□ 所以她享有保险。

（21）（6）归结（23）（9）归结{Jones/x3}（25）（8）归结{Mary/x2}（27）（20）归结 （28）（（6）归结（29）（9）归结 41

第五章 递归函数论

5.1 写出下列语句的特征函数

（1）x大于等于y。

解

N2(y ? x)

（2）a为b,c的公倍数。 解

N2(N2rs(a,b)?N2rs(a,c)) （3）x为质数。 解

N2(?Nrs(x,t) ? 2)

t?x（4）x为y的倍数且x为平方数。 解

x为y的倍数的特征函数为： N2rs(x,y)

x为平方数的特征函数为：

N2(x ? [x]2)

故原句的特征函数为：

N2(N2rs(x,y)?N2(x ? [x]2))

（5）x为非负数或x为平方数。 解

x为非负数的特征函数为： Nx

x为平方数的特征函数为：

N2(x ? [x]2)

故原句的特征函数为：

Nx?N2(x ? [x]2)

（6）在a，b间的一切x均使得A(x)成立。 解

N2(ctA(a)?ctA(a?1)???ctA(b))

42

（7）在a，b间有一个x使得A(x)成立。 解

ctA(a)?ctA(a?1)???ctA(b) 5.2 试把下列公式化为标准迭置

（1）h(x1,x2,x3)?f(x2,5,g1(x1,x3),g2(x2)) 解

h(x1,x2,x3)?f(h1,h2,h3,h4)(x1,x2,x3) 其中

h1(x1,x2,x3)?I3,2(x1,x2,x3) h52(x1,x2,x3)?SOI3,1(x1,x2,x3) h3(x1,x2,x3)?g1(I3,1,I3,3)(x1,x2,x3) h4(x1,x2,x3)?g2(I3,2)(x1,x2,x3) （2）h(x1,x2,x4)?f(3,x4,g1(x1,x2)) 解

h(x1,x2,x4)?f(h1,h2,h3)(x1,x2,x4) 其中

h31(x1,x2,x4)?SOI3,1(x1,x2,x4) h2(x1,x2,x4)?I3,3(x1,x2,x4) h3(x1,x2,x4)?g1(I3,1,I3,2)(x1,x2,x3) 5.3 用凑合定义法定义函数dv(x,3)，并把它化为迭置。解

dv(x,3)???3 x为3 的倍数?1 x不为3 的倍数

dv(x,3)?3N3rs(x,3)?N2rs(x,3) ?3Nrs(x,3)?N2rs(x,3) ?1?2Nrs(x,3)

43

5.4 试证明下列函数为原始递归函数

（1）D(x) 证明 因为??D(0)?0

D(x?1)?x?B(x,D(x))?其中B为I2,1，也就是说D(x)可用原始递归式表示。 所以D(x)为原始递归函数。 （2）a 证明

0??a?1因为?

x?1xx??a?a?a?B(x,a)x其中B为?(I2,2,SOI2,1)，也就是说a可用原始递归式表示。 所以a为原始递归函数。

（3）Im,n(x1,x2,?,xn,?xm?1,xm) 证明

因为Im,n(x1,x2,?,xn,?xm?1,xm)为本原函数，而本原函数为原始递归函数。 所以Im,n(x1,x2,?,xn,?xm?1,xm)为原始递归函数。 （4）max(x,y) 证明

因为max(x,y)?x?(y ? x)，且x?y和x ? y为原始递归函数，所以max(x,y)是由原始递归函数x?y和x ? y利用迭置而得。根据原始递归函数的定义知，max(x,y)为原始递归函数。

（5）x ?? y 证明

因为x ?? y?(x ? y)?(y ? x)，且x?y和x ? y为原始递归函数，所以x ?? y是由原始递归函数x?y和x ? y利用迭置而得。根据原始递归函数的定义知，x ?? y为原始递归函数。

xax 44

（6）?f(x)

x?n证明

??f因为?(x)?f(0)?x?0??f(x)?f(n?1)??1?f(x)?B(x,n,

?x?nx?n?f(x))t?n其中B为?(f(SI3,2),I3,3)，也不是说?f(x)可用原始递归式表示。

x?n所以?f(x)为原始递归函数。

x?n

45