离散数学（第五版）清华大学出版社第2章习题解答
2.1 本题没有给出个体域,因而使用全 总个体域. (1) 令F(x):x是鸟 G(x):x会飞翔. 命题符号化为 ?x(F(x)→G(x)). (2)令F(x):x为人. G(x):x爱吃糖 命题符号化为 ??x(F(x)→G(x)) 或者
?x(F(x)∧?G(x)) (3)令F(x):x为人. G(x):x爱看小说. 命题符号化为 ?x(F(x)∧G(x)). (4) F(x):x为人. G(x):x爱看电视. 命题符号化为 ??x(F(x)∧?G(x)).
分析 1°如果没指出要求什么样的个体域，就使用全总个休域，使用全总个体域时，往往要使用特性谓词。（1）-（4）中的F(x)都是特性谓词。 2° 初学者经常犯的错误是，将类似于（1）中的命题符号化为 27
?x(F(x)∧G(x))
即用合取联结词取代蕴含联结词，这是万万不可的。将（1）中命题叙述得更透彻些，是说“对于宇宙间的一切事物百言，如果它是鸟，则它会飞翔。”因而符号化应该使用联结词→而不能使用∧。若使用∧，使（1）中命题变成了“宇宙间的一切事物都是鸟并且都会飞翔。”这显然改变了原命题的意义。
3° （2）与（4）中两种符号化公式是等值的，请读者正确的使用量词否定等值式，证明（2），（4）中两公式各为等值的。 2.2 (1)d (a),(b),(c)中均符号化为 ?xF(x)
其中F(x):(x+1)2=x2+2x+1,此命题在(a),(b),(c)中均为真命题。 （2） 在(a),(b),(c)中均符号化为 ?xG(x)
其中G(x):x+2=0，此命题在（a）中为假命题，在(b)(c)中均为真命题。 （3）在(a),(b),(c)中均符号化为 ?xH(x)
其中H(x):5x=1.此命题在(a),(b)中均为假命题，在(c)中为真命题。 分析 1°命题的真值与个体域有关。
2° 有的命题在不同个体域中，符号化的形式不同，考虑命题 “人都呼吸”。
在个体域为人类集合时，应符号化为 ?xF(x)
这里，F(x):x呼吸，没有引入特性谓词。 在个体域为全总个体域时，应符号化为 ?x(F(x)→G(x))
这里，F(x):x为人，且F(x)为特性谓词。G(x):x呼吸。 28
2．3 因题目中未给出个体域，因而应采用全总个体域。
（1） 令：F(x):x是大学生，G(x):x是文科生，H(x):x是理科生，命题符号化为 ?x(F(x)→(G(x)∨H(x))
（2）令F(x):x是人，G(y):y是化，H(x):x喜欢，命题符 号化为 ?x(F(x)∧?y(G(y)→H(x,y)))
（3）令F(x):x是人，G(x):x犯错误，命题符号化为 ??x(F(x)∧?G(x)), 或另一种等值的形式为 ?x(F(x)→G(x)
（4）令F(x):x在北京工作，G(x):x是北京人，命题符号化为 ??x(F(x)→G(x)), 或
?x(F(x)∧?G(x)),
（5）令F(x):x是金属，G(y):y是液体，H(x,y):x溶解在y中，命题符号化为 ?x(F(x)→?y(G(y)∧H(x,y))).
（6）令F(x):x与y是对顶角，H(x,y):x与y相等，命题符号化为 ?x?y(F(x,y)→H(x,y)).
分析 （2），（5），（6）中要使用2无谓词，用它们来描述事物之间的关系。 2.4 1）对所有的x，存在着y，使得x?y=0，在(a),(b)中为真命题，在(c),(d)中为假命题。
（2）存在着x对所有的y，都有x,?y=0，在(a),(b)中为真命题，在(c),(d)中为假命题。 29
（3）对所有x，存在着y，使得x?y=1，在(a),(b)(c)中均为假命题，而在(d)中为真命题。
（4）存在着x，对所有的y，都有x?y=1，在(a),(b)(c)(d)中都是假命题。 （5）对所有的x，存在着y，使得x?y=x在(a),(b)(c)(d)中都是真命题。 （6）存在x，对所有的y，都有x?y=x，在(a),(b)中为真命题，在(c)(d)中为假命题。
（7）对于所有的x和y，存在着z，使得x?y=z，在(a),(b)中为真命题，在(c)(d)中为假命题。
2.5 1）取解释I1为：个体域D=R（实数集合），F(x):x为有理数，G(x):x能表示成分数，在I1下，?x(F(x)→G(x))的含义为
“对于叙何实数x而言，若x为有理数，则x能表示成分数”，简言之为“有理数都能表示成分数。”在此蕴含式中，当前件F(x)为真时，后件G(x)也为真，不会出现前件为真，后件为假的情况，所以在I1下，?x(F(x)→G(x))为真命题。 在在I1下，?x(F(x)∧G(x))的含义为
“对于任何实数x,x既为有理数，又能表示成分数。”
取x= 2，则F( 2)∧g( 2)显然为假，所以，在I1下，?x(F(x)∧G(x))为假命题. (2) 取解释I2为:个体域 D=N(自然数集合), F(x):x为奇数, G(x):x为偶数,在I2下,?x(F(x)∧G(x))的含义为
“存在自然数x,x发既为奇数，又为偶数。”
取x=2，则F(2)为假，于是F(2)→G(2)为真，这表明?x(F(x)→G(x)为真命题。 分析 本题说明
?x(F(x)→G(x))??x(F(x)∧G(x)), 30
?x(F(x)∧G(x))??x(F(x)→G(x)),
这里，A?B表示A与B不等值，以后遇到?，含义相同。
在一阶逻辑中，将命题符号化时，当引入特性谓词（如题中的F(x))之后，全称量词?后往往使用联结词→而不使用∧，而存在量词?后往往使用∧，而不使用→，如果用错了，会将真命题变成假命题，或者将假命题变成真命题。 2．6 在解释R下各式分别化为 （1）?x(?x<0); （2）?x?y(x?y≥x);
（3）?x?y?z(x 易知，在解释R下，（1），（2）为假；，（3）（4）为真。 2．7 给定解释I为：个体域D=N（自然数集合），F(x):x为奇数，G(x):x为偶数。 （1）在解释I下，公式被解释为 “如果所有的自然数不是奇数就是偶数，则所有自然数全为奇数，或所有自然数全为偶数。”因为蕴含式的前件为真，后件为假，所以真值为假。 （2）在I下，公式解释为 “如果存在着自然数为奇数，并且存在着自然为偶数，则存在着自然数既是奇数，又是偶数。” 由于蕴含式的前件为真，后件为假，后以真值为假。 分析 本题说明全称量词对析取不满足分配律，存在量词对合取不满足分配律。 2.8 令A=?x?y(F(x)∧G(y)→L(x,y)),在A中，无自由出现的个体变项，所以A 为闭式。 给定解释I1：个体域 D=N（整数集合），F(x):x为正数，G(x):x为负数，L(x,y):x>y，在I1下，A的含义为 31 “对于任意的整数x和y，如果x为正整数，y为负整数，则x>y。” 这是真命题。 设解释I2：个体域D=R（R整数集合），F(x):x为有理数，G(y):y为无理数，L(x,y):x≤y，在I2下，A的含义为 “对于任意的实数x和y，如果x为有理数，y为元理数，则x≥y。” 这是假命题。 分析 闭式在任何解释下不是真就是假，不可能给出解释I, 使得闭式在I下真值不确定，这一点是闭式的一个重要特征。而非封闭的公式就没有这个特征。 2.9 取A1=L(f(x,y),g(x,y))和A2=?x(f(x,y),x)，则A1和A2都是非土产的公式，在A1中，x, y都是自由出现的，在A2中，y是自出现的。 取 解 释 I 为 ， 个 体 域 D=N （ N 为 自 然 数 集 合 ），f(x,y,)=x+y,g(x,y)=x?yL(x,y)为x=y。在 I下，A1为x+y=x?y为假，所以在I下，A1真值不确定，即在I下A2的真值也是命题。 在I下，A2为?x(x+y=x),当y=0时，它为真；y≠0时为假，在I下A2的真值也不确定。 分析 非闭式与 闭式的显著区别是，前者可能在某些解释下，真值不确定，而后者对于任何解释真值都确定，即不是真就是假。 当然非闭式也可以是逻辑有效式（如F(x)→F(x)），也可能为矛盾式（如F(x)∧?F(x))，也可能不存在其值不确定的解释。 2．10 （1） ??xA(x)??(A(a)∧A(b)∧A(c)) （消去量词等值式） ??A(a)∨?A(b)∨?A(c) （德·摩根律） ??x?A(x) （消去量词等值式） （2） ??xA(x)??(A(a)∨A(b)∨A(c)) （消去量词等值式） 32
离散数学(第五版)清华大学出版社第2章习题解答
