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是素数

优质.参考.资料