离散数学习题解答(耿素云屈婉玲)北京大学出版社 下载本文

WORD格式.整理版

和y约束出现的,而z是自由出现的。在?zH(x,y,z)中,指导变元为z,辖域为H(x,y,z),其中z约束出现的,而x,y是自由出现的。 9.给定解释I如下:

(a)个体域DI为实数集合R. (b)DI中特定元素a?0

(c)特定函数f(x,y)?x?y,x,y?DI

(d)特定谓词F(x,y):x?y,G(x,y):x?y,x,y?DI. 说明下列公式在I下的含义,并指出各公式的真值: (1).?x?y(G(x,y)??F(x,y)) (2)?x?y(F(f(x,y),a)?G(x,y)) (3)?x?y(G(x,y)??F(f(x,y),a)) (4)?x?y(G(f(x,y),a)?F(x,y)) 解:

(1)?x?y((x?y)?(x?y)),即对任意的实数x和y,若x?y,则x?y。

(2)?x?y((x?y?0)?(x?y)),即对任意的实数x和y,若x?y?0,则x?y。 (3)?x?y((x?y)?(x?y?0)),即对任意的实数x和y,若x?y,则x?y?0。 (4)?x?y((x?y?0)?(x?y)),即对任意的实数x和y,若x?y?0,则x?y。 其中(1)(3)真值为1,(2)(4)真值为0。 10.给定解释I如下:

(a)个体域D?N(N为自然数集合) (b)D中特定元素a=2.

(c)D上函数f(x,y)?x?y,g(x,y)?x*y. (d)D上谓词F(x,y):x?y.

说明下列各式在I的含义,并讨论其真值: (1).?xF(g(x,a),x)

(2)?x?y(F(f(x,a),y)?F(f(y,a),x)).

优质.参考.资料

WORD格式.整理版

(3)?x?y?zF(f(x,y),z). (4)?xF(f(x,x),g(x,x)). 解:各式在I下的解释为:

(1)?x(x?2x),即对任意的自然数x,有x?2x;

(2)?x?y((x?2?y)?(y?2?x)),即对任意的自然数x和y,如果有x?2?y,则有y?2?x。

(3)?x?y?z(x?y?z),即对任意的自然数x和y,存在z,使x?y?z;

2(4)?x(2x?x),即存在的自然数x,使2x?x。

2其中(1)(2)真值为0,(3)(4)真值为1。 11.判断下列各式的类型:

(1).F(x,y)?(G(x,y)?F(x,y))

(2)?x(F(x)?F(x))??y(G(y)??G(y)). (3)?x?yF(x,y)??x?yF(x,y). (4)?x?yF(x,y)??x?yF(x,y). (5)?x?y(F(x,y)?F(y,z)). (6)?(?xF(x)??yG(y))??yG(y).

解:

其中(1)(4)为永真式,(2)(6)为矛盾式,(3)(5)为可满足式,但不是永真式。 12.设I为一个任意的解释,在解释I下,下面哪些公式一定是命题? (1).?xF(x,y)??yG(x,y).

(2)?x(F(x)?G(x))??y(F(y)?H(y)).. (3)?x(?yF(x,y)??yG(x,y)). (4)?x(F(x)?G(x)?H(y))

(2)(3)一定是命题,因为他们是闭式。

13.给出下列各公式一个成真的解释,一个成假的解释。 (1).?x(F(x)?G(x))

优质.参考.资料

WORD格式.整理版

(2)?x(F(x)?G(x)?H(x)) (3)?x(F(x)??y(G(y)?H(x,y))) 解:(1).令x是全体正整数。

成真的情况是:F(x):x是偶数,G(x):x是奇数。 成假的情况是:F(x):x是偶数,G(x):x是素数。 (2).令x是全体正整数,。

成真的情况是:F(x):x能被2整除,G(x):x能被3整除,H(x):x能被5整除。则存在30能被,2,3,5整除。

成假的情况是:F(x):x是偶数,G(x):x是素数,H(x):x能被5整除。不存在一个数既是偶数又是素数同时还能被5整除。 (1).令x是全体正整数,y是全体偶数。

成真的情况是:F(x):x是奇数,G(y):y能被2整除,H(x,y):x比y大。则对任意偶数y,都存在一个大于y的奇数。

成假的情况是:F(x):x是偶数,G(y):y能被2整除,H(x,y):x比y小。则对偶数2,不存在一个小于2的偶数。

14.证明下面的公式既不是永真式也不是矛盾式: (1).?x(F(x)??y(G(y)?H(x,y))) (2)?x?y(F(x)?G(y)?H(x,y)))

解:(1),成真的情况是:F(x):x是正偶数,G(y):y是非1的正整数,H(x,y):x能被y整除且x?y。则对任意一个正偶数x,都存在2,整除x。

矛盾的情况:F(x):x是偶数,G(y):y是非1的正整数,H(x,y):x能被y整除且,不一定存在不等于x的整数,整除x。 x?y。则对任意一个正数x(比如3)

(2).成真的情况:F(x):x能被2整除,G(y):y能被3整除,H(x,y):x*y能被6整除.成假的情况是:F(x):x能被2整除,G(y):y能被4整除,H(x,y):x*y能被6整除. 15.(1)给出一个非闭式的永真式。

(2)给出一个非闭式的永假式。

(3)给出一个非闭式的可满足式,但不是永真式。 解:

(1)(F(x)?G(x))?F(x)?G(x),它是重言式(A?B)?A?B的代换实例。

优质.参考.资料

WORD格式.整理版

(2)?(F(x)?F(x)),它是矛盾式?(A?A)的代换实例。 (3)?x(F(x,y)?F(y,x))

习题五

1. 设个体域D={a,b,c},在D中消去公式?x(F(x)??yG(y))的量词。甲、乙用了不同

的演算过程:

甲的演算过程如下:

?x(F(x)??yG(y))??x(F(x)?(G(a)?G(b)?G(c)))?(F(a)?(G(a)?G(b)?G(c)))?(F(b)?(G(a)?G(b)?G(c)))?(F(c)?(G(a)?G(b)?G(c)))?(F(a)?F(b)?F(c))?(G(a)?G(b)?G(c))乙的演算过程如下:

?x(F(x)??yG(y))

??xF(x)??yG(y)?(F(a)?F(b)?F(c))?(G(a)?G(b)?G(c))

显然,乙的演算过程简单,试指出乙在推演过程中的关键步骤。

答:乙在演算中的关键步骤是,开始利用量词辖域收缩与扩张等值式,将量词的辖域缩小,从而简化了演算。

2. 设个体域D={a,b,c},消去下列各式的量词:

(1)?x?y(F(x)?G(y)) (2)?x?y(F(x)?G(y)) (3)?xF(x)??yG(y) (4)?x(F(x,y)??yG(y)) 答:1) (F(a)?F(b)?F(c))?(G(a)?G(b)?G(c))

2) (F(a)?F(b)?F(c))?(G(a)?G(b)G?(c)) 3) (F(a)?F(b)?F(c))?(G(a)?G(b)?G(c)) 4) (F(a,y)?F(b,y)?F(c,y))?(G(a)?G(b)?G(c))

3.设个体域D={1,2},请给出两种不同的解释I1和I2,使得下面公式在I1下都是真命题,而在I2下都是假命题。 (1)?x(F(x)?G(x)) (2)?x(F(x)?G(x)) 答:解释为I1:F(x),x是偶数,G(x) x是素数 解释为I2:F(x),x是奇数,G(x) x是素数

优质.参考.资料