发布时间 : 星期二 文章离散数学习题解答（耿素云屈婉玲）北京大学出版社更新完毕开始阅读
去找 QQ头像 http://www.7zhao.net
其中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)). (3)?x?y?zF(f(x,y),z).
文章来源：http://www.7zhao.net
去找 QQ头像 http://www.7zhao.net
(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； （4）?x(2x?x2)，即存在的自然数x，使2x?x。 其中（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)) (2)?x(F(x)?G(x)?H(x))
2文章来源：http://www.7zhao.net
去找 QQ头像 http://www.7zhao.net
(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?y。则对任意一个正数x（比如3），不一定存在不等于x的整数，整除x。
(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的代换实例。 （2）?(F(x)?F(x))，它是矛盾式?(A?A)的代换实例。
文章来源：http://www.7zhao.net
去找 QQ头像 http://www.7zhao.net
（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是素数 4．给定公式A??xF(x)??xF(x)
文章来源：http://www.7zhao.net