离散数学(修订版)课后习题答案

离散数学的课后习题答案 修订版的,作者 耿素云 屈婉玲 的那版

第一章部分课后习题参考答案

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∧1 0.

（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是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。”

答：p: 是无理数 1 q: 3是无理数 0 r:

2是无理数 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∨r 1

所以公式类型为永真式

(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)

m0 m2 m3

∑(0,2,3)

主合取范式：

( p→q)→( q p)

(p q) ( q p)

( p q) ( q p)

( p ( q p)) ( q ( q p)) 1 (p q) (p q) M1 ∏(1) (2) 主合取范式为：

(p→q) q r ( p q) q r (p q) q r 0 所以该式为矛盾式.

主合取范式为∏(0,1,2,3,4,5,6,7)

矛盾式的主析取范式为 0 (3)主合取范式为：

(p (q r))→(p q r)

(p (q r))→(p q r)

( p ( q r)) (p q r)

( p (p q r)) (( q r)) (p q r))

1 1 1

所以该式为永真式.

永真式的主合取范式为 1

主析取范式为∑(0,1,2,3,4,5,6,7)

离散数学的课后习题答案 修订版的,作者 耿素云 屈婉玲 的那版

第三章部分课后习题参考答案

14. 在自然推理系统P中构造下面推理的证明： (2)前提：p q, (q r),r

结论： p

(4)前提：q p,q s,s t,t r 结论：p q

证明：（2）

① (q r) 前提引入 ② q r ①置换 ③q r ②蕴含等值式 ④r 前提引入 ⑤ q ③④拒取式 ⑥p q 前提引入 ⑦￢p（3） ⑤⑥拒取式

证明（4）：

①t r 前提引入 ②t ①化简律 ③q s 前提引入 ④s t 前提引入

⑤q t ③④等价三段论 ⑥（q t） (t q) ⑤ 置换 ⑦（q t） ⑥化简 ⑧q ②⑥ 假言推理 ⑨q p 前提引入 ⑩p ⑧⑨假言推理 (11)p q ⑧⑩合取

15在自然推理系统P中用附加前提法证明下面各推理：

离散数学的课后习题答案 修订版的,作者 耿素云 屈婉玲 的那版

(1)前提：p (q r),s p,q

结论：s r 证明

①s 附加前提引入 ②s p 前提引入 ③p ①②假言推理 ④p (q r) 前提引入 ⑤q r ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理

16在自然推理系统P中用归谬法证明下面各推理：

(1)前提：p q, r q,r s

结论： p 证明：

①p 结论的否定引入 ②p ﹁q 前提引入 ③﹁q ①②假言推理 ④￢r q 前提引入 ⑤￢r ④化简律 ⑥r ￢s 前提引入 ⑦r ⑥化简律 ⑧r ﹁r ⑤⑦ 合取

由于最后一步r ﹁r 是矛盾式,所以推理正确.

第四章部分课后习题参考答案

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)在两个个体域中都解释为 xF(x)，在（a）中为假命题，在(b)中为真命题。 (2)在两个个体域中都解释为 xG(x)，在（a）(b)中均为真命题。

4. 在一阶逻辑中将下列命题符号化:

(1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解:

(1)F(x): x能表示成分数 H(x): x是有理数

命题符号化为: x( F(x) H(x)) (2)F(x): x是北京卖菜的人 H(x): x是外地人

命题符号化为: x(F(x) H(x)) 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快.

(3) 不存在比所有火车都快的汽车. 解:

(1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快 命题符号化为: x y((F(x) G(y)) H(x,y))

(2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 命题符号化为: y(G(y) x(F(x) H(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<y,x,y D.

说明下列公式在I下的含义,并指出各公式的真值: (1) x y(G(x,y) F(x,y)) (2) x y(F(f(x,y),a) G(x,y))

答:(1) 对于任意两个实数x,y,如果x<y, 那么x y. 真值1.

(2) 对于任意两个实数x,y,如果x-y=0, 那么x<y. 真值0. 10. 给定解释I如下：

（a） 个体域D=N(N为自然数集合).

（b） D中特定元素错误！未找到引用源。=2.

（c） D上函数错误！未找到引用源。=x+y,错误！未找到引用源。(x,y)=xy. （d） D上谓词错误！未找到引用源。(x,y):x=y.

说明下列各式在I下的含义，并讨论其真值. (1) 错误！未找到引用源。xF(g(x,a),x)

(2) 错误！未找到引用源。x错误！未找到引用源。y(F(f(x,a),y)→F(f(y,a),x) 答:(1) 对于任意自然数x, 都有2x=x, 真值0.

(2) 对于任意两个自然数x,y,使得如果x+2=y, 那么y+2=x. 真值0.

11. 判断下列各式的类型:

(1) 错误！未找到引用源。

(3) 错误！未找到引用源。yF(x,y).

解:(1)因为 p (q p) p ( q p) 1 为永真式； 所以 错误！未找到引用源。为永真式；

(3)取解释I个体域为全体实数 F(x,y)：x+y=5

所以,前件为任意实数x存在实数y使x+y=5，前件真； 后件为存在实数x对任意实数y都有x+y=5，后件假，] 此时为假命题

离散数学的课后习题答案 修订版的,作者 耿素云 屈婉玲 的那版

再取解释I个体域为自然数N， F(x,y)：:x+y=5

所以,前件为任意自然数x存在自然数y使x+y=5，前件假。此时为假命题。

此公式为非永真式的可满足式。 13. 给定下列各公式一个成真的解释，一个成假的解释。

(1) 错误！未找到引用源。(F(x)错误！未找到引用源。

(2) 错误！未找到引用源。x(F(x)错误！未找到引用源。G(x)错误！未找到引用源。H(x))

解:(1)个体域:本班同学

F(x)：x会吃饭, G(x)：x会睡觉.成真解释

F(x)：x是泰安人,G(x)：x是济南人.（2）成假解释 (2)个体域:泰山学院的学生

F(x)：x出生在山东,G(x):x出生在北京,H(x):x出生在江苏,成假解释. F(x)：x会吃饭,G(x)：x会睡觉,H(x)：x会呼吸. 成真解释.

第五章部分课后习题参考答案

5.给定解释Ｉ如下:

(a)个体域D={3,4};

(b)f(x)错误！未找到引用源。为f(3) 4,f(4) 3错误！未找到引用源。 (c)F(x,y)为F(3,3) F(4,4) 0,F(3,4) F(4,3) 1错误！未找到引用源。. 试求下列公式在Ｉ下的真值. (1) x yF(x,y)

(3) x y(F(x,y) F(f(x),f(y))) 解:(1) x yF(x,y) x(F(x,3) F(x,4))

(F(3,3) F(3,4)) (F(4,3) F(4,4))

(0 1) (1 0) 1

(2) x y(F(x,y) F(f(x),f(y)))

x((F(x,3) F(f(x),f(3))) (F(x,4) F(f(x),f(4))))

离散数学的课后习题答案 修订版的,作者 耿素云 屈婉玲 的那版

x((F(x,3) F(f(x),4)) (F(x,4) F(f(x),3))) ((F(3,3) F(f(3),4)) (F(3,4) F(f(3),3)))

((F(4,3)

F(f(4),4)) (F(4,4) F(f(4),3)))

((0 F(4,4)) (F(3,4) F(4,3))) ((1 F(3,4)) (0 F(3,3)))

(0 0) (1 1) (1 1) (0 0) 1

12.求下列各式的前束范式。

(1) xF(x) yG(x,y)

(5) x1F(x1,x2) (H(x1) x2G(x1,x2)) (本题课本上有错误) 解:(1) xF(x) yG(x,y) xF(x) yG(t,y) x y(F(x) G(t,y)) (5) x1F(x1,x2) (H(x1) x2G(x1,x2))

x1F(x1,x2) (H(x3) x2 G(x3,x2)) x1F(x1,x4) x2(H(x3) G(x3,x2)) x1 x2(F(x1,x4) (H(x3) G(x3,x2)))

15.在自然数推理系统F中,构造下面推理的证明:

(1) 前提: xF(x) y((F(y) G(y)) R(y)), xF(x)

结论: xR(x)

(2) 前提: x(F(x)→(G(a)∧R(x))), 错误！未找到引用源。xF(x) 结论:错误！未找到引用源。x(F(x)∧R(x)) 证明(1)

① xF(x) 前提引入 ②F(c) ①EI

③ xF(x) y((F(y) G(y)) R(y)) 前提引入 ④ y((F(y) G(y)) R(y)) ①③假言推理 ⑤(F(c)∨G(c))→R(c)) ④UI ⑥F(c)∨G(c) ②附加 ⑦R(c) ⑤⑥假言推理 ⑧ xR(x) ⑦EG

离散数学的课后习题答案 修订版的,作者 耿素云 屈婉玲 的那版

(2)

① xF(x) 前提引入 ②F(c) ①EI

③ x(F(x)→(G(a)∧R(x))) 前提引入 ④F(c)→(G(a)∧R(c)) ③UI

⑤G(a)∧R(c) ②④假言推理 ⑥R(c) ⑤化简 ⑦F(c)∧R(c) ②⑥合取引入 ⑧ x(F(x)∧R(x))

第六章部分课后习题参考答案

5.确定下列命题是否为真：

（1） 真 （2） 假 （3） { }

真

（4） { } 真 （5）｛a,b｝ ｛a,b,c,｛a,b,c｝｝ 真 （6）｛a,b｝ ｛a,b,c,｛a,b｝｝ 真 （7）｛a,b｝ ｛a,b,｛｛a,b｝｝｝ 真 （8）｛a,b｝ ｛a,b,｛｛a,b｝｝｝ 假

6．设a,b,c各不相同，判断下述等式中哪个等式为真: （1）｛｛a,b｝，c,

｝ =｛｛a,b｝,c｝ 假

（2）｛a ,b,a｝=｛a,b｝ 真 （3）｛｛a｝，{b}｝=｛｛a,b｝｝ 假 （4）｛ ，｛ ｝，a,b｝=｛｛ ,｛ ｝｝,a,b｝ 假 8．求下列集合的幂集：

（1）｛a,b,c｝ P(A)={ ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} （2）｛1，｛2，3｝｝ P(A)={ , {1}, {{2,3}}, {1，{2，3}} } （3）｛ ｝ P(A)={ , ｛ ｝ }

离散数学的课后习题答案 修订版的,作者 耿素云 屈婉玲 的那版

（4）｛ ，｛ ｝｝ P(A)={ , {1}, {{2,3}}, {1，{2，3}} } 14．化简下列集合表达式： （1）（A B） B ）-（A B） （2）（（A B C）-（B C）） A 解:

(1)（A B） B ）-（A B）=（A B） B ） ～（A B）

=（A B） ～（A B）) B= B=

（2）（（A B C）-（B C）） A=（（A B C） ～（B C）） A =（A ～（B C）） （（B C ） ～（B C）） A =（A ～（B C）） A=（A ～（B C）） A=A

18．某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人都会打篮球或排球。求不会打球的人数。

解: 阿A={会打篮球的人}，B={会打排球的人}，C={会打的人}

|A|=14, |B|=12, |A B|=6,|A C|=5,| A B C|=2, |C|=6,C A B 如图所示。

25-(5+4+2+3)-5-1=25-14-5-1=5

不会打球的人共5人

21.设集合A＝{{1，2}，{2，3}，{1，3},{ }},计算下列表达式： （1） A （2） A （3） A （4） A 解:

（1） A={1，2} {2，3} {1，3} { }={1，2，3, }

（2） A={1，2} {2，3} {1，3} { }=

（3） A=1 2 3 =

（4） A=

网球

离散数学的课后习题答案 修订版的,作者 耿素云 屈婉玲 的那版

27、设A,B,C是任意集合，证明 (1)(A-B)-C=A- B C (2)(A-B)-C=(A-C)-(B-C) 证明

(1) (A-B)-C=(A ～B) ～C= A ( ～B ～C)= A ～(B C) =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 由（1）得证。

第七章部分课后习题参考答案

7.列出集合A={2,3,4}上的恒等关系I A,全域关系EA,小于或等于关系LA,整除关系DA. 解：IA ={<2，2>,<3,3>,<4,4>}

EA={<2,2>,<2,3>,<2,4>,<3,4>,<4,4>,<3,2>,<3,3>,<4,2>,<4,3>}

LA={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>} DA={<2,4>}

13.设A={<1,2>,<2,4>,<3,3>} B={<1,3>,<2,4>,<4,2>}

求A B,A B, domA, domB, dom(A B), ranA, ranB, ran(A B ), fld(A-B). 解：A B={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>} A B={<2,4>}

domA={1,2,3} domB={1,2,4} dom(A∨B)={1,2,3,4}

ranA={2,3,4} ranB={2,3,4} ran(A B)={4}

A-B={<1,2>,<3,3>}，fld(A-B)={1,2,3} 14.设R={<0,1><0,2>,<0,3>,<1,2>,<1,3>,<2,3>}

求R R, R-1, R {0,1,}, R[{1,2}]

离散数学的课后习题答案 修订版的,作者 耿素云 屈婉玲 的那版

解：R R={<0,2>,<0,3>,<1,3>}

R-1,={<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>}

R {0,1}={<0,1>,<0,2>,<0,3>,<1,2>,<1,3>} R[{1,2}]=ran(R|{1,2})={2,3}

16．设A={a,b,c,d}，R1，R2为A上的关系，其中

R1

=

a,a,a,b,b,d

R2 a,d,b,c,b,d,c,b

求R1 R2,R2 R1,R12,R23。

解: R1 R2={<a,d>,<a,c>,<a,d>} R2 R1={<c,d>}

R12=R1 R1={<a,a>,<a,b>,<a,d>} R22=R2 R2={<b,b>,<c,c>,<c,d>} R23=R2 R22={<b,c>,<c,b>,<b,d>}

36．设A={1，2，3，4}，在A A上定义二元关系R，

<u,v>,<x,y> A A ，〈u,v> R <x,y> u + y = x + v. (1)证明R 是A A上的等价关系. (2)确定由R 引起的对A A的划分. （1）证明：∵<u,v>R<x,y> u+y=x-y

∴<u,v>R<x,y> u-v=x-y

<u,v> A A

∵u-v=u-v ∴<u,v>R<u,v> ∴R是自反的

任意的<u,v>,<x,y>∈A×A 如果<u,v>R<x,y> ，那么u-v=x-y ∴x-y=u-v ∴<x,y>R<u,v>

∴R是对称的

离散数学的课后习题答案 修订版的,作者 耿素云 屈婉玲 的那版

任意的<u,v>,<x,y>,<a,b>∈A×A 若<u,v>R<x,y>,<x,y>R<a,b> 则u-v=x-y,x-y=a-b ∴u-v=a-b ∴<u,v>R<a,b> ∴R是传递的

∴R是A×A上的等价关系

(2) ∏={{<1,1>,<2,2>,<3,3>,<4,4>}, {<2,1>,<3,2>,<4,3>}, {<3,1>,<4,2>}, {<4,1>}, {<1,2>,<2,3>,<3,4>}, {<1,3>,<2,4>}, {<1,4>} }

41.设A={1，2，3，4}，R为A A上的二元关系, 〈a，b〉，〈c，d〉 A A , 〈a，b〉R〈c，d〉 a + b = c + d (1) 证明R为等价关系. (2)求R导出的划分. (1)证明： <a，b〉 A A

a+b=a+b ∴<a,b>R<a,b> ∴R是自反的

任意的<a,b>,<c,d>∈A×A 设<a,b>R<c,d>，则a+b=c+d ∴c+d=a+b ∴<c,d>R<a,b> ∴R是对称的

任意的<a,b>,<c,d>,<x,y>∈A×A 若<a,b>R<c,d>,<c,d>R<x,y> 则a+b=c+d,c+d=x+y ∴a+b=x+y ∴<a,b>R<x,y> ∴R是传递的

∴R是 A×A上的等价关系

(2)∏={{<1,1>}, {<1,2>,<2,1>}, {<1,3>,<2,2>,<3,1>}, {<1,4>,<4,1>,<2,3>,<3,2>}, {<2,4>,<4,2>,<3,3>}, {<3,4>,<4,3>}, {<4,4>}}

离散数学的课后习题答案 修订版的,作者 耿素云 屈婉玲 的那版

43. 对于下列集合与整除关系画出哈斯图:

(1) {1,2,3,4,6,8,12,24}

(2) {1,2,3,4,5,6,7,8,9,10,11,12}

解

:

842

1

63

1

11

7

(1) (2)

45.下图是两个偏序集<A,R >的哈斯图.分别写出集合A和偏序关系R 的集合表达式.

d

g

b

f

g

a

a

(a) (b)

解: (a)A={a,b,c,d,e,f,g}

R ={<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<a,g>,<b,d>,<b,e>,<c,f>,<c,g>} IA

(b) A={a,b,c,d,e,f,g}

R ={<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<d,f>,<e,f>} IA

46.分别画出下列各偏序集<A,R >的哈斯图,并找出A的极大元`极小元`最大元和最小元.

(1)A={a,b,c,d,e}

R ={<a,d>,<a,c>,<a,b>,<a,e>,<b,e>,<c,e>,<d,e>} IA. (2)A={a,b,c,d,e}, R ={<c,d>} IA.

解:

离散数学的课后习题答案 修订版的,作者 耿素云 屈婉玲 的那版

e

d

bd

e

a

b

c

a

(1) (2)

项目 (1) (2) 极大元: e a,b,d,e 极小元: a a,b,c,e 最大元: e 无 最小元: a 无

第八章部分课后习题参考答案

1．设f :N N,且

1，若x为奇数 f (x)= x

若x为偶数 2，

求f (0), f ({0}), f (1), f ({1}), f ({0,2,4,6, })，f ({4,6,8}), f -1({3,5,7}). 解：f (0)=0, f ({0})={0}, f (1)=1, f ({1})={1},

f ({0,2,4,6, })=N，f ({4,6,8})={2,3,4}, f -1 ({3,5,7})={6,10,14}. 4. 判断下列函数中哪些是满射的?哪些是单射的?哪些是双射的? (1) f:N N, f(x)=x2+2 不是满射，不是单射

(2) f:N N,f(x)=(x)mod 3,x除以3的余数 不是满射，不是单射

1，若x为奇数

(3) f:N N,f(x)= 不是满射，不是单射

0，若x为偶数

0，若x为奇数

(4) f:N {0,1},f(x)= 是满射，不是单射

1，若x为偶数

(5) f:N-{0} R,f(x)=lgx 不是满射，是单射 (6) f:R R,f(x)=x2-2x-15 不是满射，不是单射