离散数学第五版清华大学出版社第2章习题解答.docx

离散数学（第五版）清华大学出版社第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）中的命题符号化为27x(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呼吸。2823 因题目中未给出个体域，因而应采用全总个体域。（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相等，命题符号化为xy(F(x,y)H(x,y).分析 （2），（5），（6）中要使用2无谓词，用它们来描述事物之间的关系。2.4 1）对所有的x，存在着y，使得xy=0，在(a),(b)中为真命题，在(c),(d)中为假命题。（2）存在着x对所有的y，都有x,y=0，在(a),(b)中为真命题，在(c),(d)中为假命题。29（3）对所有x，存在着y，使得xy=1，在(a),(b)(c)中均为假命题，而在(d)中为真命题。（4）存在着x，对所有的y，都有xy=1，在(a),(b)(c)(d)中都是假命题。（5）对所有的x，存在着y，使得xy=x在(a),(b)(c)(d)中都是真命题。（6）存在x，对所有的y，都有xy=x，在(a),(b)中为真命题，在(c)(d)中为假命题。（7）对于所有的x和y，存在着z，使得xy=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),30x(F(x)G(x)x(F(x)G(x),这里，AB表示A与B不等值，以后遇到，含义相同。在一阶逻辑中，将命题符号化时，当引入特性谓词（如题中的F(x)之后，全称量词后往往使用联结词而不使用，而存在量词后往往使用，而不使用，如果用错了，会将真命题变成假命题，或者将假命题变成真命题。26 在解释R下各式分别化为（1）x(x0);（2）xy(xyx);（3）xyz(xy)(xzyz);（4）xy(xy，在I1下，A的含义为31“对于任意的整数x和y，如果x为正整数，y为负整数，则xy。”这是真命题。设解释I2：个体域D=R（R整数集合），F(x):x为有理数，G(y):y为无理数，L(x,y):xy，在I2下，A的含义为“对于任意的实数x和y，如果x为有理数，y为元理数，则xy。”这是假命题。分析 闭式在任何解释下不是真就是假，不可能给出解释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)=xyL(x,y)为x=y。在 I下，A1为x+y=xy为假，所以在I下，A1真值不确定，即在I下A2的真值也是命题。在I下，A2为x(x+y=x),当y=0时，它为真；y0时为假，在I下A2的真值也不确定。分析 非闭式与 闭式的显著区别是，前者可能在某些解释下，真值不确定，而后者对于任何解释真值都确定，即不是真就是假。当然非闭式也可以是逻辑有效式（如F(x)F(x)），也可能为矛盾式（如F(x)F(x)，也可能不存在其值不确定的解释。210 （1）xA(x)(A(a)A(b)A(c) （消去量词等值式）A(a)A(b)A(c) （德摩根律）xA(x) （消去量词等值式）（2）xA(x)(A(a)A(b)A(c) （消去量词等值式）32A(a)A(b)A(c) （德摩根律）xA(x) （消去量词等值式）211 （1） 令F(x):x为人。G(x):x长着绿色头发。本命题直接符号化验为x(F(x)G(x)而 x(F(x)G(x)x(F(x)G(x) （量词否定等值式）x(F(x)G(x) （德摩根律）x(F(x)G(x) （蕴含等值式）最后一步得到的公式满足要求（使用全称量词），将它翻译成自然语言，即为“所有的人都不长绿色头发”。可见得“没有人长着绿色头发。”与“所有人都不长绿色头发。”是同一命题的两种不同的叙述方法。（2）令F(x):x是北京人G(x):x去过香山。命题直接符号化为x(F(x)G(x)而 x(F(x)G(x)x(F(x)G(x) （双重否定律）x(F(x)G(x) （理词否定等值式）x(F(x)G(x) （德摩根律）x(F(x)G(x)（蕴含等值式）33最后得到的公式满足要求（只含全称量词），将它翻译成自然语言，即为“并不是北京人都去过香山。”可见，“有的北京人没过过香山。”与“并不是北京人都去过香山。”是同一命题不同的叙述方法。2.12 （1） xF(x)yG(y)(F(a)F(b)F(c)(G(b)G(c).（2） xF(x)yG(y)xF(x)yG(y) （量词辖域收缩扩张等值式）(F(a)F(b)F(c)(G(a)G(b)(c).（3） xyH(x,y)x(H(x,a)H(x,b)H(x,c)(H(a,a)H(a,b)H(x,c)(H(b,a)H(b,b)H(b,c)(H(c,a)H(c,b)H(c,c)分析 在有穷个体域内消去量词时，应将量词的辖域尽量缩小，例如，在（2）中，首先将量词辖域缩小了（因为yG(y)中不含x，所以，可以缩小）。否则，演算是相当麻烦的。见下面的演算：x(F(x)yG(y)(F(a)yG(y)(F(b)yG(y)F(c)yG(y)(F(a)(G(a)G(b)G(c)(F(b)(G(a)G(c)(F(c)(G(a)G(b)G(c)(F(a)(F(b)(G(a)G(b)(c).显然这个演算比原来的喾算麻烦多了。342.13 在I下（1）x(F(x)G(x)(F(2)G(2)(F(3)G(3)F(6)G(6)(10)(10)(01)0,所以，x(F(x)G(x)在I下为假。（2）x(R(x)F(x)G(5)(R(2)F(2)(R(3)F(3)(R(6)F(6)0(11)(11)0,所以，此公式在I下也是假命题。（3）x(F(x)G(x)xF(x)xG(x) （量词分配等值式）(F( 2)F(3)F(6)(G( 2)G(3)G(3)(110)(001)1,所以，此公式在I下为真214 （1）xF(x)yG(x,y)xF(x)yG(x,y) （量词否定等值式）zF(z)yG(x,y) （约束变项换名规则）zy(F(z)G(x,y)（量词辖域收缩扩张等值式）zy(F(z)G(x,y)（2）(xF(x,y)yG(x,y)xF(x,y)yG(x,y)35z1F(z1,y)z2G(x,z2)z1z2(F(z1,y)G(x,z2)在以上演算中分别使用了德摩根律、量词否定等值式、约束变项换名规则等。分析 公式的前束范式是不唯一的。（1）中最后两步都是前束范式，其实yz(F(z)G(x,y)也是（1）中公式的前束范式。215 （1）xF(x)yG(x,y)xF(x)yG(z,y)xy(F(x)G(z,y)（2）x(F(x)yG(x,y,z)zH(x,y,z)x(F(x)yG(x,y,u)zH(v,z)xy(F(x)G(x,y,u)zH(v, ,z)xy(F(x)G(x,y,u)H(v, ,z)在以上演算中分别使用了自由变项换名规则和量词辖域收缩扩张等值式。2.16 （1）错。使用UI，UG，EI，EG规则应对前束范式，而中公式下不是前束范式，所以，不能使用UI规则。（2）。中公式为xA(x)，这时，A(x)=F(x)G(x)，因而使用UI规则时，应得A(a)（或A(y)），故应有F(a)G(a),而不可能为F(a)G(b).（3）错。应对A(c)=F(c)G(c)使用EG规则，其中c为特定的使A为真的个体常项，而不能为个体变项。（4）错。中公式含个体变项x，不能使用EG规则。（5）错。公式含两个个体常项，不能使用EG规则。36（6）错。对使用EI规则得F(c)G(c)，此c应使F(c)G(c)为真，此c不一定使H(c)R(c)为真。分析 由于的错误，可能由真前提，推出假结论。反例如下：设个体域为自然数集合N.F(x):x为偶数，G(x):x为素数，H(x):x能被 3整除，R(x):x能被4整数，显然此时，x(F(x)G(x)与x(H(x)R(x)均为真，但x(F(x)G(x)为假。其实在（6）中，应为F(2)G(2)，它是真命题，而H(2)R(2)为假命题。对x(H(x)R(x)使用 EI 规则，得H(12)R(12)才为真。所以，对两个公式使用EI规则使用同一个个体常项是会犯错误的。2.17（1）证明xF(x)y(F(y)G(y)R(y)前提引入 xF(x) 前提引入y(F(y)G(y)R(y) 假言推理F(c) EIF(c)G(c) 附加F(c)G(c)R(c) UIR(c) 假言推理xR(x) EG（2）证明：xF(x) 前提引入 F(c)EI37x(F(x)(G(y)R(x)前提引入F(c)(G(y)R(c) UIG(y)R(c) 假言推理R(c)化简F(c)R(c) 合取x(F(x)R(x) EG218 令F(x):x是大熊猎。G(x):x产在中国。a:欢欢前提：x(F(x)(G(x),F(a)结论：G(a)证明：x(F(x)G(x)前提引入 F(a) 前提引入F(a)G(a) UIG(a)假言推理219令F(x):x为有理数。G(x):x为实数。H(x):x为整数。前提：x(F(x)G(x),xF(x)H(x).结论：x(G(x)H(x).证明：xF(x)y(F(y)G(y)R(y)前提引入38 xF(x) 前提引入y(F(y)G(y)R(y) 假言推理F(c) EIF(c)G(c) 附加F(c)G(c)R(c) UIR(c) 假言推理xR(x) EG（2）证明：xF(x)H(x)前提引入 F(c)H(c) EIx(F(x)G(x)前提引入F(c)G(c)UIF(c) 化简G(c)假言推理H(c) 化简G(c)H(c)与合取 x(G(x)H(x) EG分析 在以上证明中，不能如下进行。x(F(x)H(x) 前提引入 x(F(x)G(x)前提引入F(c)G(c)UIF(c)H(c)EI至此，可能犯了错误，在中取c= 2,则F( 2)G( 2)为真，但39E( 2)H( 2)为假，就是说，由UI规则得到的c不一定满足EI规则，但反之为真，这一点务必注意。2.20