离散数学（第五版）清华大学出版社第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 （4）?x?y(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 ??A(a)∧?A(b)∧?A(c) （德·摩根律） ??x?A(x) （消去量词等值式） 2．11 （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）?x?yH(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)). 显然这个演算比原来的喾算麻烦多了。 34 2.13 在I下 （1）?x(F(x)∧G(x)) ?(F(?2)∧G(?2))∧(F(3)∧G(3))∧F(6)∧G(6)) ?(1∧0)∧(1∧0)∧(0∧1)?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?((1→1)∧(1→1)?0, 所以，此公式在I下也是假命题。 （3）?x(F(x)∨G(x)) ??xF(x)∨?xG(x) （量词分配等值式） ?(F?( 2)∨F(3)∨F(6))∨(G?( 2)∨G(3)∨G(3) ?(1∨1∨0)∨(0∨0∨1)?1, 所以，此公式在I下为真 2．14 （1） ??xF(x)→?yG(x,y) ??x?F(x)→?yG(x,y) （量词否定等值式） ??z?F(z)→?yG(x,y) （约束变项换名规则）??z?y(?F(z)→G(x,y)（量词辖域收缩扩张等值式）??z?y(F(z)∨G(x,y) （2） ?(?xF(x,y)∨?yG(x,y)) ??x?F(x,y)∧?y?G(x,y) 35 ??z1?F(z1,y)∧?z2?G(x,z2) ??z1?z2(?F(z1,y)∧?G(x,z2) 在以上演算中分别使用了德·摩根律、量词否定等值式、约束变项换名规则等。分析公式的前束范式是不唯一的。（1）中最后两步都是前束范式，其实?y?z(F(z) ∨G(x,y))也是（1）中公式的前束范式。 2．15 （1） ?xF(x)∨?yG(x,y) ??xF(x)∨?yG(z,y) ??x?y(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) ??x?y(F(x)∧G(x,y,u))→?zH(v?, ,z) ??x?y(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) ②EI ⑤F(c)∨G(c) ④附加 ⑥F(c)∨G(c))→R(c) ③UI ⑦R(c) ⑤⑥假言推理 ⑧?xR(x) ⑦EG （2）证明： ①?xF(x) 前提引入 ②F(c)①EI 37 ③?x(F(x)→(G(y)∧R(x)))前提引入④F(c)→(G(y)∧R(c)) ③UI ⑤G(y)∧R(c) ②④假言推理⑥R(c)⑤化简⑦F(c)∧R(c) ②⑥合取⑧?x(F(x)∧R(x)) ⑦EG 2．18 令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) ①UI ④G(a)②③假言推理2．19令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) ②EI ⑤F(c)∨G(c) ④附加 ⑥F(c)∨G(c))→R(c) ③UI ⑦R(c) ⑤⑥假言推理 ⑧?xR(x) ⑦EG （2）证明： ①?xF(x)∧H(x)前提引入 ②F(c)∧H(c) ①EI ③?x(F(x)→G(x)前提引入 ④F(c)→G(c)③UI ⑤F(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)②UI ④F(c)∧H(c)①EI 至此，可能犯了错误，在③中取c= 2,则F( 2)→G( 2)为真，但 39 E( 2)∧H( 2)为假，就是说，由UI规则得到的c不一定满足EI规则，但反之为真，这一点务必注意。 2.20 答案A：③；B：② 分析（7）式为非闭式，在个体域为整数集Z时，?x(x·y=x)的真值不能确定，当y=1时为真，当y≠1时为假，所以，它不是命题，其余各式都是命题。（5）虽然不是闭式，但它为真。 2．21 答案A：②；B：④，⑤，⑨C：⑦；D：⑧ 分析注意约束变项和自由变项改名规则的使用。供选答案中，（1）的前束范式只有一个，就是②。而②的前束范式有3个，当然它们都是等值的。（3）的前束范式有2 个，就是⑦和⑧。注意，在（3）式中，?x的辖域为(F(x,y)→?yG(x,y))，这就决定了它们的前束范式为 ?x?y(F(x,z)→G(x,y))，（将自由出现的y改名为z） 但由于 ?y?x(F(x,z)→G(x,y)) ??x?y(F(x,z)→G(x,y)) 所以，⑧也是（3）的前束范式。 2．22 答案A：⑤。 分析（1），（4）正确；可以构造证明。 （1）证明： ①?yF(y)前提引入 ②F(c) ①EI ③?x(F(x)→G(x)前提引入 ④F(c)→G(c)③UI ⑤F(c) ②④假言推理 ⑥?yG(y)⑤EG 40 注意应先使用EI规则。 （4）证明： ①?x(F(x)→H(x)) 前提引入 ②F(y)→H(y) ①UI ③?H(y) 前提引入 ④?F(y) ②③拒取式 ⑤?x(?F(x) ④UG (2),(3)推理不正确,只要举出反例即可. 在自然数集合中,令F(x):x是偶数, G(x):x是素数,则?x(F(x)∧G(x))为真命题,而?yF(y)为假命题,所以, ?x(F(x)∧G(x))→ ?yF(y)不是逻辑有效蕴含式,这说明(2)是推理不正确,读者可举反例说明(3)中推理也不正确. 2.23 答案A: ②B:①C: ⑦D:⑤ 离散数学（第五版）清华大学出版社第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) 离散数学习题答案 习题二及答案：（P38） 5、求下列公式的主析取范式，并求成真赋值： （2）()()p q q r ?→∧∧ 解：原式()p q q r ?∨∧∧q r ?∧()p p q r ??∨∧∧ ()()p q r p q r ??∧∧∨∧∧37m m ?∨，此即公式的主析取范式， 所以成真赋值为011，111。 6、求下列公式的主合取范式，并求成假赋值： （2）()()p q p r ∧∨?∨ 解：原式()()p p r p q r ?∨?∨∧?∨∨()p q r ??∨∨4M ?，此即公式的主合取范式， 所以成假赋值为100。 7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）()p q r ∧∨ 解：原式()(()())p q r r p p q q r ?∧∧?∨∨?∨∧?∨∧ ()()()()()()p q r p q r p q r p q r p q r p q r ?∧∧?∨∧∧∨?∧?∧∨?∧∧∨∧?∧∨∧∧ ()()()()()p q r p q r p q r p q r p q r ??∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧ 13567m m m m m ?∨∨∨∨，此即主析取范式。 主析取范式中没出现的极小项为0m ，2m ，4m ，所以主合取范式中含有三个极大项0M ，2M ，4M ，故原式的主合取范式024M M M ?∧∧。 9、用真值表法求下面公式的主析取范式： （1）()()p q p r ∨∨?∧ 解：公式的真值表如下： 由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式 1234567m m m m m m m ?∨∨∨∨∨∨ 习题三及答案：（P52-54） 11、填充下面推理证明中没有写出的推理规则。 前提：,,,p q q r r s p ?∨?∨→ 结论：s 证明： ① p 前提引入 ② p q ?∨ 前提引入 ③ q ①②析取三段论 ④ q r ?∨ 前提引入 ⑤ r ③④析取三段论 ⑥ r s → 前提引入 ⑦ s ⑤⑥假言推理 15、在自然推理系统P 中用附加前提法证明下面推理： （2）前提：()(),()p q r s s t u ∨→∧∨→ 结论： p u → 证明：用附加前提证明法。 ① p 附加前提引入 ② p q ∨ ①附加 ③ ()()p q r s ∨→∧ 前提引入 ④ r s ∧ ②③假言推理 ⑤ s ④化简 ⑥ s t ∨ ⑤附加 ⑦ ()s t u ∨→ 前提引入 ⑧ u ⑥⑦假言推理 故推理正确。 16、在自然推理系统P 中用归谬法证明下面推理： （1）前提： p q →?，r q ?∨，r s ∧? 结论：p ? 第五章函数Function 函数在数学、应用数学等许多领域，尤其计算机科学领域有着极其重要的作用。函数的思想、概念和应用无处不在，无时不在。 它主要是研究变量之间的关系和规律。函数的划分有很多种。有线性与非线性之分、连续与离散之分。例 如， x12345… y357911… 5.1 函数 假定A，B是两个非空集合，f : A→B，称f为A到B上的函数，对每个a∈A, 有唯一的f(a)∈B, 记做b = f(a)。 函数也叫映射mappings或变换transformations（错误） a叫做函数f的自变量argument，b被称为因变量，b=f(a)叫做函数的值value，也叫a的像。 例1. A＝{1,2,3,4}, B={a,b,c,d}, ， 则f是一个函数。 也可以简单记为， f={(1,a), (2,a), (3,d), (4,c)} 另外, g={(1,a), (1,b), (2,a), (4,c)} 因为对于1来说，1∈A, 不是唯一的f(1)∈B与之相对应,f(1)=a,并且f(1)=b, 因此g就不是一个函数。 例2． f：Z→Z， f(a)= f是函数。 例3．恒等函数1A(a)=a是函数。 正如，我们在第四章里表述的，函数f : A→B，b=f(a), 是一个特殊的二元关系，我们知道，由函数f可以确定一个关系，简单地，可以表示为(a,b)∈，或 ab。关系的特征函数为 或者简记为 因此，这样一来，我们以前所讨论的有关集合或关系的运算和性质对于函数来说，就可以完全适用。 例如，f：A→B, g：A→B, 函数的复合 设f：A→B，g：B→C，是函数，则g?f：A→C，是函数。 g?f（a）＝g(f(a)) 《离散数学》模拟试题3 一、填空题（每小题2分，共20分） 1. 已知集合A ={φ，1，2}，则A得幂集合p（A）=_____ _。 2. 设集合E ={a, b, c, d, e}, A= {a, b, c}, B = {a, d, e}, 则A∪B =___ ___， A∩B =____ __，A－B =___ ___，～A∩～B =____ ____。 3. 设A，B是两个集合，其中A= {1, 2, 3}, B= {1, 2}，则A－B =____ ___， ρ（A）－ρ（B）=_____ _ _。 4. 已知命题公式R Q P G→ ∧ ? =) (，则G的析取范式为。 5. 设P：2＋2＝4，Q：3是奇数；将命题“2＋2＝4，当且仅当3是奇数。”符号化 ，其真值为。 二、单项选择题（选择一个正确答案的代号填入括号中，每小题4分，共16分。） 1. 设A、B是两个集合，A＝{1,3,4}，B＝{1,2}，则A－B为（）. A.{1} B. {1, 3} C. {3,4} D. {1,2} 2. 下列式子中正确的有（）。 A. φ＝0 B. φ∈{φ} C. φ∈{a,b} D. φ∈φ 3. 设集合X＝{x, y}，则ρ（X）＝（）。 A. {{x},{y}} B. {φ,{x},{y}} C. {φ,{x},{y},{x, y}} D. {{x},{y},{x, y}} 4. 设集合A＝{1,2,3}，A上的关系R＝{(1,1),(2,2),(2,3),(3,3),(3,2)}， 则R不具备（）. 三、计算题（共50分） 1. （6分）设全集E＝N，有下列子集：A＝{1，2，8，10}，B＝{n|n2<50 ，n∈N}，C＝ {n|n可以被3整除，且n<20 ，n∈N}，D＝{n|2i，i<6且i、n∈N}，求下列集合：（1）A∪(C∩D) （2）A∩(B∪(C∩D)) （3）B－(A∩C) （4）(～A∩B) ∪D 2. （6分）设集合A＝{a, b, c}，A上二元关系R1，R2，R3分别为：R1＝A×A， R2 ＝{(a，a)，(b，b)}，R3 ＝{(a，a)}，试分别用 定义和矩阵运算求R1·R2 ，22R，R1·R2 ·R3 ， (R1·R2 ·R3 )－1 。 3.（6分）化简等价式（﹁P∧（﹁Q∧R））∨（Q∧R）∨（P∧R）. 4.(8分) 设集合A＝{1,2,3}，R为A上的二元关系，且 M R＝ 写出R的关系表达式，画出R的关系图并说明R的性质. 5. （10分）设公式G的真值表如下. 试叙述如何根据真值表求G的 主析取范式和主合取范式，并 写出G的主析取范式和主合取范式. 1 0 0 1 1 0 1 0 0 习题参考答案 1、设无向图G有16条边，有3个4度结点，4个3度结点，其余结点的度数均小于3，问：G中至少有几个结点。 阮允准同学提供答案: 解：设度数小于3的结点有x个，则有 3×4＋4×3＋2x≥2×16 解得：x≥4 所以度数小于3的结点至少有4个 所以G至少有11个结点 2、设无向图G有9个结点，每个结点的度数不是5就是6，证明：G中至少有5个6度结点或至少有6个5度结点。 阮允准同学答案： 证明：由题意可知：度数为5的结点数只能是0,2，4,6，8。 若度数为5的结点数为0,2，4个，则度数为6的结点数为9，7,5个结论成立。 若度数为5的结点数为6,8个，结论显然成立。 由上可知，G中至少有5个6度点或至少有6个5度点。 3、证明：简单图的最大度小于结点数。 阮同学认为题中应指定是无向简单图. 晓津证明如下：设简单图有n个结点，某结点的度为最大度，因为简单图任一结点没有平行边，而任一结点的的边必连有另一结点，则其最多有n-1条边与其他结点相连，因此其度数最多只有n-1条，小于结点数n. 4、设图G有n个结点，n+1条边，证明：G中至少有一个结点度数≥3 。阮同学给出证明如下： 证明：设G中所有结点的度数都小于3，即每个结点度数都小于等于2，则所有结点度数之和小于等于2n，所以G的边数必小于等于n，这和已知G有n+1条边相矛盾。所以结论成立。 5、试证明下图中两个图不同构。 晓津证明：同构的充要条件是两图的结点和边分别存在一一对应且保持关联关系。我们可以看出，(a)图和(b)图中都有一个三度结点，(a)图中三度结点的某条边关联着两个一度结点和一个二度结点，而(b)图中三度结点关联着两个二度结点和一个一度结点，因此可断定二图不是同构的。 6、画出所有5个结点3条边，以及5个结点7条边的简单图。 解：如下图所示：(晓津与阮同学答案一致) 离散数学习题解答 习题五（第五章 格与布尔代数） 1．设〈L ，?〉是半序集，?是L 上的整除关系。问当L 取下列集合时，〈L ，?〉是否是格。 a) L={1，2，3，4，6，12} b) L={1，2，3，4，6，8，12} c) L={1，2，3，4，5，6，8，9，10} [解] a) 〈L ，?〉是格，因为L 中任两个元素都有上、下确界。 b) 〈L ，?〉不是格。因为L 中存在着两个元素没有上确界。 例如：8 12=LUB{8，12}不存在。 c) 〈L ，?〉不是格。因为L 中存在着两个元素没有上确界。 1 6 3 1 2 4 8 63 1 2 4 1 1 倒例如：46=LUB{4，6}不存在。 2．设A ，B 是两个集合，f 是从A 到B 的映射。证明：〈S ，?〉是〈2B ，?〉的子格。其中 S={y|y=f (x)，x ∈2A } [证] 对于任何B 1∈S ，存在着A 1∈2A ，使B 1=f （A 1），由于f(A 1)={y|y ∈B ∧(x)(x ∈A 1∧f (x)=y)}?B 所以B 1∈2B ，故此S ?2B ；又B 0=f (A)∈S (因为A ∈2A )，所以S 非空； 对于任何B 1，B 2∈S ，存在着A 1，A 2∈2A ，使得B 1=f (A 1)，B 2=f (A 2)，从而 L ∪B{B 1，B 2}=B 1∪B 2=f (A 1)f (A 2) =f (A 1∪A 2) （习题三的8的1）） 由于A 1∪A 2?A ，即A 1∪A 2∈2A ，因此f (A 1∪A 2)∈S ，即上确界L ∪B{B 1，B 2}存在。 对于任何B 1，B 2∈S ，定义A 1=f –1 (B 1)={x|x ∈A ∧f (x)∈B 1}，A 2=f -1 (B 2)={x|x ∈A ∧f (x)∈B 2}，则A 1，A 2∈2A ，且显然B 1=f (A 1)，B 2=f (A 2)，于是 GLB{B 1，B 2}=B 1∩B 2=f (A 1)∩f (A 2) ?f (A 1∩A 2) （习题三的8的2）） 又若y ∈B 1∩B 2，则y ∈B ，且y ∈B 2。由于y ∈B 1=f (A 1)={y|y ∈B ∧(x)(x ∈A 1∧f (x)=y)}，于是存在着x ∈A 1，使f (x)=y ，但是f (x)=y ∈B 2。故此x ∈A 2=f -1 (B 2)={x|x ∈A ∧f(x)∈B 2}，因此x ∈A 1∩A 2，从而y=f (x)∈f (A 1∩A 2)，所以 GLB{B 1，B 2}=B 1∩B 2=f (A 1)∩f (A 2) ?f (A 1∩A 2) 9 7 31 第5章作业答案 1. 用枚举法给出下列集合 解(2) {-3，2} (4) {5，6，7，8，9，10，11，12，13，14，15} 2. 用抽象法说明下列集合 解(6) {x|?k (k∈I∧x = 2k + 1)} 6．写出下列集合的幂集 解(2) ρ({1, ?}) = {?, {1}, {?}, {1, ?}} (4) ρ({?, {a}, {?}}) = {?, {?}, {{a}}, {{?}}, {?, {a}}, {?, {?}}, {{a}, {?}}, {?, {a}, {?}}} 9. 证明：如果B?C，则ρ(B) ?ρ(C)。 证明任取x∈ρ(B)，则x?B，又因为B?C，所以x?C，x∈ρ(C)。 10．设U = {1, 2, 3, 4, 5}，A = {1, 4}，B = {1, 2, 5}和C = {2, 4}，试写出下列集合。解(8) ρ(A) -ρ(C) = {?, {1}, {4}, {1, 4}} - {?, {2}, {4}, {2, 4}} = {{1}, {1, 4}} 11．证明下列恒等式 (7) (A-B) -C = (A-C) - (B-C) 证法1 对于任意x， x∈ (A-C) - (B-C) ?x∈A-C ∧x? B-C ?x∈A∧x?C ∧?(x∈ B∧x?C) ? x∈A∧x?C ∧ ( x?B ∨ x∈C) ?( x∈A∧x?C ∧ x?B)∨( x∈A∧x?C ∧ x∈C) ? x∈A∧x?C ∧ x?B ? x∈A∧ x?B∧x?C ? x∈A-B ∧ x?C ? x∈(A-B) -C 证法2 (A-C) - (B-C) = A?~C?~( B?~C) = A?~C? (~ B? C) = ( A?~C?~ B) ?( A?~C? C) =(A?~C?~ B) ?? = A?~B?~ C = (A-B) ?~ C = (A-B) -C 12．设A, B, C是集合，下列等式成立的条件是什么？ (3) (A-B ) ? (A-C) = ? 解因为(A- B) ?( A-C) = (A?~B) ? ( A?~C) = A? (~B?~C) = A?~(B ?C) = A- (B ?C) 所以(A-B)?(A-C) = ?iff A- (B?C) = ?iff A? (B?C) 离散数学（第五版）清华大学出版社第1章习题解答 1．1 除（3），（4），（5），（11）外全是命题，其中，（1），（2），（8），（9），（10），（14），（15）是简单命题，（6），（7），（12），（13）是复合命题。 分析首先应注意到，命题是陈述句，因而不是陈述句的句子都不是命题。 本题中，（3）为疑问句，（5）为感叹句，（11）为祈使句，它们都不是陈述句，所以它们都不是命题。 其次，4）这个句子是陈述句，但它表示的判断结果是不确定。又因为（1），（2），（8），（9），（10），（14），（15）都是简单的陈述句，因而作为命题，它们 都是简单命题。（6）和（7）各为由联结词“当且仅当”联结起来的复合命题，（12）是由联结词“或”联结的复合命题，而（13）是由联结词“且”联结起来 的复合命题。这里的“且”为“合取”联结词。在日常生活中，合取联结词有许 多表述法，例如，“虽然……，但是……”、“不仅……，而且……”、“一面……，一面……”、“……和……”、“……与……”等。但要注意，有时“和”或“与” 联结的是主语，构成简单命题。例如，（14）、（15）中的“与”与“和”是联结 的主语，这两个命题均为简单命题，而不是复合命题，希望读者在遇到“和”或“与”出现的命题时，要根据命题所陈述的含义加以区分。 1．2 （1）p: 2是无理数，p为真命题。 （2）p:5能被2整除，p为假命题。 （6）p→ｑ。其中，p:2是素数，q：三角形有三条边。由于p与q都是真 命题，因而p→ｑ为假命题。 （7）p→ｑ，其中，p：雪是黑色的，q：太阳从东方升起。由于p为假命 题，q为真命题，因而p→ｑ为假命题。 （8）p:2000年10月1日天气晴好，今日（1999年2月13日）我们还不 知道p的真假，但p的真值是确定的（客观存在的），只是现在不知道而已。（9）p：太阳系外的星球上的生物。它的真值情况而定，是确定的。 1 （10）p：小李在宿舍里. p的真值则具体情况而定，是确定的。 （12）p∨q，其中，p:4是偶数，q:4是奇数。由于q是假命题，所以，q 为假命题，p∨q为真命题。 第5章 习题解答 5.1 A:③; B:⑥; C:⑧; D:⑩; E:⑨ 分析 S 为n 元集,那么有个元素.S 上的一个二元运算就是函数 S S ?2n .这样的函数有个.因此上的二元运算有个. S S S f →?:2n n },{b a 162 =n n 下面说明通过运算表判别二元运算性质及求特导元素的方法. 1 °交换律 若运算表中元素关于主对角线成对称分布,则该运算满足交换律. 2 °幂等律 设运算表表头元素的排列顺序为如果主对角线元,,,21n x x x 素的排列也为 则该运算满足幂等律. ,,,21n x x x 其他性质,如结合律或者涉及到两个运算表的分配律和吸收律,在运算表中没有明显的特征,只能针对所有可能的元素等来验证相关的算律是否成立. z y x ,,3 ° 幺元设运算表表头元素的排列顺序为如果元素所在的.e ,,,21n x x x i x 行和列的元素排列顺序也是则为幺元. ,,,21n x x x i x 4 ° 零元如果元素所在的行和列的元素都是,则是零元. .θi x i x i x 5 ° 幂等元.设运算表表头元素的排列顺序为如果主对角线上,,,21n x x x 第个元素恰 为那么是幂等元.易见幺元和零元都是幂等元. i },,2,1{n i x i ∈i x 6 ° 可逆元素及其逆元.设为任意元素,如果所在的行和列都有幺元,并i x i x 且这两个幺元关于主对角线成对称分布,比如说第行第列和第行第列的两i j j i 个位置,那么与互为逆元.如果所在的行和列具有共同的幺元,则幺元一j x i x i x 定在主对角线上,那么的逆元就是自己.如果所在的和地或者所在的列没i x i x i x 有幺元,那么不是可逆元素.不难看出幺元一定是可逆元素,且;而零i x e e e =-1元不是可逆元素. θ以本题为例,的运算表是对称分布的,因此,这三个运算是可交换的, 321,,f f f 离散数学习题解答(第五章)格与布尔代数 仅供学习与交流，如有侵权请联系网站删除 谢谢2 离散数学习题解答 习题五（第五章 格与布尔代数） 1．设〈L ，?〉是半序集，?是L 上的整除关系。问当L 取下列集合时，〈L ，?〉是否是格。 a) L={1，2，3，4，6，12} b) L={1，2，3，4，6，8，12} c) L={1，2，3，4，5，6，8，9，10} [解] a) 〈L ，?〉是格，因为L 中任两个元素都有上、下确界。 b) 〈L ，?〉不是格。因为L 中存在着两个元素没有上确界。 例如：8 12=LUB{8，12}不存在。 6 3 1 6 3 1 1 仅供学习与交流，如有侵权请联系网站删除 谢谢3 c) 〈L ，?〉不是格。因为L 中存在着两个元素没有上确界。 倒例如：4⊕6=LUB{4，6}不存在。 2．设A ，B 是两个集合，f 是从A 到B 的映射。证明：〈S ，?〉是 〈2B ，?〉的子格。其中 S={y|y=f (x)，x ∈2A } [证] 对于任何B 1∈S ，存在着A 1∈2A ，使B 1=f （A 1），由于f(A 1)={y|y ∈ B ∧(?x)(x ∈A 1∧f (x)=y)}?B 所以B 1∈2B ，故此S ?2B ；又B 0=f (A)∈S (因为A ∈2A )，所以S 非空； 对于任何B 1，B 2∈S ，存在着A 1，A 2∈2A ，使得B 1=f (A 1)，B 2=f (A 2)，从而 L ∪B{B 1，B 2}=B 1∪B 2=f (A 1)f (A 2) =f (A 1∪A 2) （习题三的8的1）） 由于A 1∪A 2?A ，即A 1∪A 2∈2A ，因此f (A 1∪A 2)∈S ，即上确界L ∪B{B 1，B 2}存在。 对于任何B 1，B 2∈S ，定义A 1=f –1(B 1)={x|x ∈A ∧f (x)∈B 1}，A 2=f -1 (B 2)={x|x ∈A ∧f (x)∈B 2}，则A 1，A 2∈2A ，且显然B 1=f (A 1)，B 2=f (A 2)，于是 GLB{B 1，B 2}=B 1∩B 2=f (A 1)∩f (A 2) ?f (A 1∩A 2) （习题三的8的2）） 又若y ∈B 1∩B 2，则y ∈B ，且y ∈B 2。由于y ∈B 1=f (A 1)={y|y ∈B ∧(?x)(x ∈A 1∧f (x)=y)}，于是存在着x ∈A 1，使f (x)=y ，但是f 7 1 第四章部分课后习题参考答案 3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值: (1) 对于任意x,均有2=(x+)(x). (2) 存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解： F(x): 2=(x+)(x). G(x): x+5=9. (1)在两个个体域中都解释为)(x ?，在（a）中为假命题，在 xF (b)中为真命题。 (2)在两个个体域中都解释为)(x ?，在（a）(b)中均为真命 xG 题。 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在卖菜的人不全是外地人. 解: (1)F(x): x能表示成分数 H(x): x是有理数 命题符号化为: )) F x∧ x ?? ? ) ( H ( (x (2)F(x): x是卖菜的人 H(x): x是外地人 命题符号化为: )) F ?? x x→ (x ( H ) ( 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快 命题符号化为: )) F y x G ? y ? ∧ x→ ( ( )) ( H ) x ((y , (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 命题符号化为: ))) x F x y G ∧ ? H ?? y→ ) ( , x ( ( ( (y ) 9.给定解释I如下: (a) 个体域D为实数集合R. (b) D中特定元素=0. (c) 特定函数(x,y)=x y,x,y D ∈. (d) 特定谓词(x,y):x=y,(x,y):x 第一章部分课后习题参考答案 16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r)0∨(0∧1) 0 （2）（p?r）∧(﹁q∨s) （0?1）∧(1∨1) 0∧10. （3）（p∧q∧r）?(p∧q∧﹁r) （1∧1∧1）? (0∧0∧0)0 (4)（r∧s）→(p∧q) （0∧1）→(1∧0) 0→0 1 17．判断下面一段论述是否为真：“是无理数。并且，如果3是无理数，则也是无理数。另外6能被2整除，6才能被4整除。” 答：p: 是无理数 1 q: 3是无理数0 r: 是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。 19．用真值表判断下列公式的类型： （4）(p→q) →(q→p) （5）(p∧r) (p∧q) （6）((p→q) ∧(q→r)) →(p→r) 答：（4） p q p→q q p q→p (p→q)→(q→p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式 （5）公式类型为可满足式（方法如上例） （6）公式类型为永真式（方法如上例） 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) (p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)(p∨(p∨q))∨(p∨r)p∨p∨q∨r1 所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)(p→(q∧r)) (4)(p∧q)∨(p∧q)(p∨q) ∧(p∧q) 证明（2）(p→q)∧(p→r) (p∨q)∧(p∨r) p∨(q∧r)) p→(q∧r) （4）(p∧q)∨(p∧q)(p∨(p∧q)) ∧(q∨(p∧q) (p∨p)∧(p∨q)∧(q∨p) ∧(q∨q) 1∧(p∨q)∧(p∧q)∧1 (p∨q)∧(p∧q) 5.求下列公式的主析取范式与主合取范式，并求成真赋值 (1)(p→q)→(q∨p) (2)(p→q)∧q∧r (3)(p∨(q∧r))→(p∨q∨r) 解： （1）主析取范式 (p→q)→(q p) (p q)(q p) (p q)(q p) (p q)(q p)(q p)(p q)(p q) (p q)(p q)(p q) ∑(0,2,3) 主合取范式： (p→q)→(q p) (p q)(q p) 离散数学（第五版）清华大学出版社第1章习题解答1．1除（3），（4），（5），（11）外全是命题，其中，（1），（2），（8），（9），（10），（14），（15）是简单命题，（6），（7），（12），（13）是复合命题。 分析首先应注意到，命题是陈述句，因而不是陈述句的句子都不是命题。 本题中，（3）为疑问句，（5）为感叹句，（11）为祈使句，它们都不是陈述句，所以它们都不是命题。 其次，4）这个句子是陈述句，但它表示的判断结果是不确定。又因为（1），（2），（8），（9），（10），（14），（15）都是简单的陈述句，因而作为命题，它们都是简单命题。（6）和（7）各为由联结词“当且仅当”联结起来的复合命题，（12）是由联结词“或”联结的复合命题，而（13）是由联结词“且”联结起来的复合命题。这里的“且”为“合取”联结词。在日常生活中，合取联结词有许多表述法，例如，“虽然……，但是……”、“不仅……，而且……”、“一面……，一面……”、“……和……”、“……与……”等。但要注意，有时“和”或“与” 联结的是主语，构成简单命题。例如，（14）、（15）中的“与”与“和”是联结的主语，这两个命题均为简单命题，而不是复合命题，希望读者在遇到“和”或“与”出现的命题时，要根据命题所陈述的含义加以区分。 1．2（1）p:2是无理数，p为真命题。 （2）p:5能被2整除，p为假命题。 （6）p→q。其中，p:2是素数，q：三角形有三条边。由于p与q都是真命题，因而p→q为假命题。 （7）p→q，其中，p：雪是黑色的，q：太阳从东方升起。由于p为假命可编辑范本 题，q为真命题，因而p→q为假命题。 （8）p:2000年10月1日天气晴好，今日（1999年2月13日）我们还不知道p的真假，但p的真值是确定的（客观存在的），只是现在不知道而已。 离散数学习题详细答案 ————————————————————————————————作者：————————————————————————————————日期： 离散数学习题答案 习题一及答案：（P14-15） 14、将下列命题符号化： （5）李辛与李末是兄弟 解：设p ：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语 解：设p ：王强学过法语；q ：刘威学过法语；则命题符号化的结果是 p q ∧ （9）只有天下大雨，他才乘班车上班 解：设p ：天下大雨；q ：他乘班车上班；则命题符号化的结果是q p → （11）下雪路滑，他迟到了 解：设p ：下雪；q ：路滑；r ：他迟到了；则命题符号化的结果是()p q r ∧→ 15、设p ：2+3=5. q ：大熊猫产在中国. r ：太阳从西方升起. 求下列复合命题的真值： （4）()(())p q r p q r ∧∧???∨?→ 解：p=1，q=1，r=0， ()(110)1p q r ∧∧??∧∧??， (())((11)0)(00)1p q r ?∨?→??∨?→?→? ()(())111p q r p q r ∴∧∧???∨?→??? 19、用真值表判断下列公式的类型： （2）()p p q →?→? 解：列出公式的真值表，如下所示： p q p ? q ? ()p p →? ()p p q →?→? 0 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 1 由真值表可以看出公式有3个成真赋值，故公式是非重言式的可满足式。 20、求下列公式的成真赋值： 第五章习题 7年昆明理工 1、在自然数集合 N上，下列哪种运算是可结合的。（） A. a*b=a-b B.a*b=max(a,b) C. a*b=a+2b D.a*b=|a-b| 2、设 Z 为整数集合， +为普通加法，则代数系统 其他习题 1、已知集合 A={1 ，2，?,10}, 下面定的哪些运算关于集合 A 是不封的 .() A. x*y=max(x,y) B.x*y=min(x,y) C.x*y=GCD(x,y) , 即 x,y 的最大公数 D.x*y=LCM(x,y), 即 x,y 的最小公倍数 2、 Z* 是正整数集合， +，—， * ，△分是数的普通加法、减法， 乘法和平方运算，下列（）不能构成代数系。 A. 离散数学（第五版）清华大学出版社第6章习题解答 6.1 A:⑨; B:⑨; C:④; D:⑥; E:③ 分析对于给定的集合和运算判别它们是否构成代数系统的关键是检查集合对 给定运算的封闭性,具体方法已在 5.3节做过说明. 下面分别讨论对各种不同代数系纺的判别方法. 1°给定集合S和二元运算°,判定 离散数学课后习题答案(左孝凌版) 1-1，1-2解： a)是命题，真值为T。 b)不是命题。 c)是命题，真值要根据具体情况确定。 d)不是命题。 e)是命题，真值为T。 f)是命题，真值为T。 g)是命题，真值为F。 h)不是命题。 i)不是命题。 （2）解： 原子命题：我爱北京天安门。 复合命题：如果不是练健美操，我就出外旅游拉。 （3）解： a)(┓P ∧R)→Q b)Q→R c)┓P d)P→┓Q （4）解： a)设Q:我将去参加舞会。R:我有时间。P:天下雨。 Q (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。 b)设R:我在看电视。Q:我在吃苹果。 R∧Q:我在看电视边吃苹果。 c) 设Q:一个数是奇数。R:一个数不能被2除。 （Q→R）∧(R→Q):一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。 (5) 解： a)设P：王强身体很好。Q：王强成绩很好。P∧Q b)设P：小李看书。Q：小李听音乐。P∧Q c)设P：气候很好。Q：气候很热。P∨Q d)设P： a和b是偶数。Q：a+b是偶数。P→Q e)设P：四边形ABCD是平行四边形。Q ：四边形ABCD的对边平行。P Q f)设P：语法错误。Q：程序错误。R：停机。（P∨ Q）→ R (6) 解： a)P:天气炎热。Q:正在下雨。 P∧Q b)P:天气炎热。R:湿度较低。 P∧R c)R:天正在下雨。S:湿度很高。 R∨S d)A:刘英上山。B:李进上山。 A∧B e)M:老王是革新者。N:小李是革新者。 M∨N f)L:你看电影。M:我看电影。┓L→┓M g)P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R h)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3 （1）解： 离散数学（第五版）清华大学出版社第7章习题解答 7.1 (1),(2),(3),(5)都能构成无向图的度数列,其中除(5)外又都能构成无向简单图的度数列. 分析1°非负整数列d,d ,L,d 能构成无向图的度数列当且仅当n di为 1 2n∑ i=1偶数,即d1,d2,L,dn中的奇数为偶数个.（1）,(2),(3),(5)中分别有4个,0个,4个,4 个奇数,所以,它们都能构成无向图的度数列,当然,所对应的无向图很可能是非简 单图.而(4)中有 3 个奇数,因而它不能构成无向图度数列.否则就违背了握手定理的推论. 2°(5) 虽然能构成无向图的度数列,但不能构成无向简单度数列.否则,若存在无向简单图G,以1,3,3,3 为度数列,不妨设G 中顶点为v1,v2,v3,v4,且d(vi)=1,于是d(v2)=d(v3)=d(v4)=3.而v1只能与v2,v3,v4之一相邻,设v1与v2相邻,这样一来,除v2能达到3度外, v3,v4都达不到3度,这是矛盾的. 在图7.5所示的4个图中,(1) 以1为度数列,(2)以2为度数列,(3)以3为度数列,(4)以4为度数列(非简单图). 7.2 设有几简单图D以2,2,3,3为度数列,对应的顶点分别为v1,v2,v3,v4,由于d(v)=d+(v)+d_(v),所示,d+(v)-d-(v)=2-0=2,d+(v )=d(v )-d-(v ) 11222=2-0=2,d+(v)=d(v)-d-(v)=3-2=1,d+(v)=d(v)-d-(v)=3-3=0 333444 81 由此可知,D 的出度列为2,2,1,0,且满足d+(v)= d-(v).请读者画出 ∑i∑ｉ 一个有向图.以2,2,3,3为度数列,且以0,0,2,3为入度列,以2,2,1,0为出度列. 7.3 D 的入度列不可能为1,1,1,1.否则,必有出度列为2,2,2,2(因为d(v)=d+(v)+d-(v)),)此时,入度列元素之和为4,不等于出度列元素之和8,这违背握手定理.类似地讨论可知,1,1,1,1也不能为D的出席列. 7.4 不能. N阶无向简单图的最大度Δ≤n-1.而这里的n个正整数彼此不同,因而这n个数不能构成无向简单图的度数列,否则所得图的最大度大于n,这与最大度应该小于等于n-1矛盾. 离散数学课后习题答案第四章 第十章部分课后习题参考答案 4．判断下列集合对所给的二元运算是否封闭： （1） 整数集合Z 和普通的减法运算。 封闭,不满足交换律和结合律，无零元和单位元 （2） 非零整数集合普通的除法运算。不封闭 （3） 全体n n ?实矩阵集合 （R ）和矩阵加法及乘法运算，其中n 2。 封闭 均满足交换律，结合律，乘法对加法满足分配律； 加法单位元是零矩阵，无零元； 乘法单位元是单位矩阵，零元是零矩阵； （4）全体n n ?实可逆矩阵集合关于矩阵加法及乘法运算，其中n 2。不封闭 （5）正实数集合 和 运算，其中 运算定义为： 不封闭 因为 +?-=--?=R 1111111ο （6）n 关于普通的加法和乘法运算。 封闭，均满足交换律，结合律，乘法对加法满足分配律 加法单位元是0，无零元； 乘法无单位元（1>n ），零元是0；1=n 单位元是1 （7）A = {},,,21n a a a Λ n 运算定义如下： 封闭 不满足交换律，满足结合律， （8）S = 关于普通的加法和乘法运算。 封闭 均满足交换律，结合律，乘法对加法满足分配律 （9）S = {0,1},S 是关于普通的加法和乘法运算。 加法不封闭，乘法封闭；乘法满足交换律，结合律 （10）S = ,S 关于普通的加法和乘法运算。 加法不封闭，乘法封闭，乘法满足交换律，结合律 10．令S={a ，b}，S 上有四个运算：*，分别有表10.8确定。 (a) (b) (c) (d) (1)这4个运算中哪些运算满足交换律，结合律，幂等律？ (a) 交换律，结合律，幂等律都满足， 零元为a,没有单位元； (b)满足交换律和结合律，不满足幂等律，单位元为a,没有零元 b b a a ==--11, (c)满足交换律,不满足幂等律,不满足结合律 a b a b b a b a a b b a ====οοοοοο)(,)( b b a b b a οοοο)()(≠ 没有单位元, 没有零元 (d) 不满足交换律，满足结合律和幂等律 没有单位元, 没有零元 (1) 求每个运算的单位元，零元以及每一个可逆元素的逆元。 见上 16．设V=〈 N ，+ ，〉，其中+ ， 分别代表普通加法与乘法，对下面给定的每个集合确定它是否 构成V 的子代数，为什么？ （1）S 1= 是 （2）S 2= 不是 加法不封闭 （3）S 3 = {-1，0，1} 不是，加法不封闭 第十一章部分课后习题参考答案 8.设S={0，1，2，3}， 为模4乘法，即 "?x,y ∈S, x y=(xy)mod 4离散数学(第五版)清华大学出版社第2章习题解答
离散数学习题(耿素云屈婉玲)
离散数学第五章
离散数学第五版 模拟试题 及答案
自考离散数学教材课后题第五章答案
离散数学习题解答(第五章)格与布尔代数
离散数学第5章作业答案
离散数学(第五版)清华大学出版社第1章习题解答
离散数学 第5章 习题解答
离散数学习题解答(第五章)格与布尔代数教学文案
屈婉玲版离散数学课后习题答案
离散数学第一章部分课后习题参考答案
离散数学(第五版)清华大学出版社第
离散数学习题详细答案
离散数学第五章习题.doc
离散数学(第五版)清华大学出版社第6章习题解答
离散数学课后习题答案(左孝凌版)
离散数学(第五版)清华大学出版社第7章习题解答
离散数学课后习题答案第四章
相关主题
文本预览