湘潭大学 刘任任版 离散数学课后习题答案 习题15

第一篇：湘潭大学 刘任任版 离散数学课后习题答案 习题15

习题十五

1、设下面所有谓词的论域D={a、b、c}。试将下面命题中的量词消除，写成与之等值的命题公式。分析：本题主要是考察对全称量词、存在量词的理解，然后通过合取词、析取词把全称量词和存在量词消去。（1）xRxSx

解：R(a)R(b)R(c)S(a)S(b)S(c)（2）xPxQ(x)

解：P(a)Q(a))P(b)Q(b)P(c)Q(c)（3）x7P(x)xP(x)

解：7P(a)7P(b)7P(c))P(a)P(b)P(c)

2、指出下列命题的真值：

分析：本题主要是考察合式公式的解释的定义，已经判定给定解释下合式公式的真值。（1）xPQ(x))R(e)

其中，P:“3＞2”,Q(x):“x3”,R(x):“x＞5”,e:5，论域D={-2，3，6} 解：假。

（x为-2时不成立）（2）xP(x)Q(x)

其中，P(x):“x＞3”,Q(x):“x4”，论域D={2}。解：真。

3、在一阶逻辑中，将下列命题符号化：

分析：本题主要是考察存在量词、全称量词已经基本的连接词的运用。（1）凡有理数均可表示为分数。

解：令：P(x)： x是有理数；Q（x）:x可表示为分数。

x(P(x)Q(x))

（2）有些实数是有理数。解：P（x）：:x是实数，Q(x)：x是有理数。

xPxQ(x)

（3）并非所有实数都是有理数。解：P（x）：:x是实数，Q(x)：x是有理数。

x(P(x)Q(x))

（4）如果明天天气好，有一些学生将去公园。

解：P（x）: x去公园

S（x）: x是学生

W：明天天气好

Wx(P(x)S(x))

（5）对任意的正实数，都存在大于该实数的实数。解：P（x）: x是实数；

G（x, y）：:x大于y。

x(P(x)y(P(y)G(y,x)))（6）对任意给＞0，x0a,b，都在存在N，使当n＞N时，有

fx0fnx解：G（x，y）: x＞y, Sx:xa,b

＜

x0G,0Sx0Nn(Gn,NG(,f(x0)fn(x))))

4、指出下列公式中的自由变元和约束变元，并指出各量词的作用域。

分析：本题主要是考察自由边缘、约束变元的定义，以及量词的作用域的概念。（1）xPxQxxRxQz

解；自由变元z, 约束变元x, 第一个x的作用域是PxQx，第二个是R(x)。

（2）x(P(x)y(Q(y))(xP(x)Q(z))

中的Px 解：自由变元z，约束为元：x，y。第一个x的作用域为PxyQy



第二个x的作用域为第二个P(x)； y的作用域为Q(y)。（3）x(P(x)Q(x))yR(y)s(z)

解：自由变元：z，约束变元：x和y；

x的作用域为(P(x)Q(x))，y的作用域为R(y)

（4）x(F(x)yH(x,y))

解：无自由变元

约束变元x，y；

x的作用域：(F(x)yH(x，y))，y的作用域：H(x,y)

（5）xF(x)G(x,y)

解：自由变元：y与G(x，y)中的x，约束变元：F(x)中的x；

x的作用域：F(x)（6）xy(R(x,y)Q(x,z))xH(x,y)

解：自由变元：Z与H(x，y)中的y；

约束变元：x,y, x和y的作用范围：(R(x,y)Q(x,z)，x的作用范围：H(x,y)

5．设谓词公式x(P(x,y)Q(x,z))。判定以下改名是否正确 ：

分析：本题主要是考察改名规则的定义，以及它的适用范围。有兴趣的同学可以顺便了解一下代替规则情形。

（1）u(P(u,y)Q(x,z))

解：错误（2）u(P(u,y)Q(u,z))

解：正确（3）x(P(u,y)Q(u,z))

解：错误（4）u(P(x,y)Q(x,z))

解：错误（5）y(P(y,y)Q(y,z))

解：错误 6．设I是如下一个解释 ：

D:a，b，P(a，a):1，P(a,b):0，P(b,a):0，P(b,b):1。

试确定下列公式在I下的真值：

分析：本题主要考察合式公式在特定解释下的真值。（1）xyP(x,y)

解：真

（2）xyP(x,y)

解：假

（3）xy(P(x,y)P(y,x))解：真（4）xP(x,x)

解：真

7．判断下列公式的恒真性和恒假性

分析：本题主要是根据已知的命题公式、合式公式的基本等值式来进行推导，看该合式公式是与1等值还是与0等值。

（1）xF(x)xF(x)

解：恒真（2）xF(x)(xyG(x,y)xF(x))

解：恒真（3）xF(x)(x(F(x)yG(y))

解：恒真（4）(F(x,y)F(x,y))

解：恒假

8．设G（x）是恰含自由变元x的谓词公式，H是不含变元x的谓词公式，证明：（1）x(G(x)H)xG(x)H（2）x(G(x)H)xG(x)H 分析：本题根据量词作用域的扩张进行证明。证明（1）

x(G(x)H)x(7G(x)H)x7G(x)H7(xG(x))HxG(x)H

证明（2）

x(G(x)H)x(7G(x)H)x7G(x)H7(xG(x))HxG(x)H

9．设G（x，y）是任意一个含x，y自由出现的谓词公式，证明：（1）xyG(x，y)yxG(x，y)

分析：本题主要是根据两个合式公式等值的定义进行证明。证：设D是论域，I是G（x，y）的一个解释。

（a）若xyG(x，y)在I下的为真，则在I下，对任意的x,yD,G(x,y)即yxG(x,y)是真命题，反之亦然。

（b）若xyG(x,y)在I下为假，则在I下必存在x0D或y0D，使得G（x0, y）或G（x, y0）为假，于是，此xo或yo亦弄假yxG(x,y)，反之亦然。

（2）xyG(x，y)yxG(x，y)

分析：本题主要是根据两个合式公式等值的定义进行证明。

证：设D是论域，I是G（x, y）的一个解释。

（a）若xyG(x，y)在I下为真，则在I下存在x0D与y0D,使G（x0,y0）为真命题，于是，yxG(x,y)也是真命题，反之亦然。

（b）若xyG(x，y)在I下为假，则对任意x，yD，G（x, y）均为假，故yxG(x,y)亦为假，反之亦然。

10．将下列公式化成等价的前束范式：

分析：本题主要是根据已知的基本等值式通过消去蕴含连接词、等价连接词，依据改名规则、代替规则进行等值演算化成前束范式。

（1）xF(x)xG(x)

解：xF(x)xG(x)xF(x)xG(x)x(F(x)G(x))（2）xF(x)xG(x)解：

xF(x)xG(x)xF(x)xG(x)x(7F(x))xG(x)x(7F(x)G(x))

（3）(xF(x,y)yG(y))xH(x,y)

解：

(xF(x,y)yG(y))xH(x,y)(7(xF(x,y))yG(y))xH(x,y)(x(7F(x,y))zG(z))xH(x,y)xz(7F(x,y)G(z))xH(x,y)xz(F(x,y)7G(z))uH(u,y)xzu((F(x,y)G(z))H(u,y))

（4）x(P(x)yQ(x,y))

解：x(P(x)yQ(x,y))x(7P(x)yQ(x,y))xy(7P(x)Q(x,y))

11．给出下面公式的skolem范式：

分析：本题主要是根据已知的基本等值式通过消去蕴含连接词、等价连接词，依据改名规则、代替规则进行等值演算化成前束范式，然后根据前束范式写出对应的skolem范式。

（1）7(xP(x)yzQ(y,z))解：

7(xP(x)yzQ(y,z))(xP(x)yzQ(y,z)xyz(P(x)Q(y,z))

∴所求为:xz(P(x)Q(f(x),z))

（2）x(7E(x,o)(y(E(y,g(x))zE(z,g(x))E(y,z)))))解: 原式x(7E(x,o)(yz(E(y),g(x)E(z),g(x)E(y,z))))

x(7E(x,o)7(yz(E(y)g(x))E(y,g(x)E(y,z))))x(7E(x,o)(u7(E(y),g(x))E(,g(x)E(y,z))))

x(7E(x,o)u((7(E(u),g(x)))(7E(1g(x)))E(y,z))

xu(E(x,o)((7E(u,g(x)))(7E(,g(x)))E(y,z))

即为所求

（3）7(xP(x)yP(y))

解：7(xP(x)yP(y))7(7xP(x)yP(y)7(x7P(x)yP(y)

7(xy(7P(x)P(y)))xy(P(x)7P(y))即为所求。

12．假设xyM(x，y)是公式G的前束范式，其中M（x, y）是仅仅包含变量x，y的母式，设f是不出现在M（x, y）中的函数符号。证明：G恒真当且仅当xyM(x,f(x))恒真。

分析：本题主要是用反证法，根据解释的定义来证明结论成立。

证：设GxyM(x，y)恒真。若xM(x,f(x))不真，则存在一个解释I, 使得对任意的x0D（论域），M(x0,f(x0))为假。于是，G在I下也为假。此为矛盾。

反之，设xM(x,f(x))恒真。若xyM(x，y)不是恒真，则存在一个解释I’，使得对任意xiD，存在yiD，使M(xi，yi)为假。由于f是不出现在M(x，y)中的函数符号，故可定义函数f:使得f(xi)yi。于是，xM(x,f(x))在I’下为假。矛盾。

故结论成立。13．证明

DD，(x)(P(x)Q(x))(x)(Q(x)R(x))(x)(P(x)R(x))

分析：本题是根据基本的等值式、蕴含式、以及US、UG、ES、EG规则证明结论成立。证：（1）(x)(P(x)Q(x))(x)(Q(x)R(x))前提引入

(2)(x)(P(x)Q(x))

化简（1）

（3）P(y)Q(y)

US规则，根据（2）（4）(x)(Q(x)R(x))

化简（1）

（5）Q(y)R(y)

US规则，根据（4）

（6）P(y)R(y)

假言三段论，根据（3），（5）（7）(x)(P(x)R(x))

ES规则，根据（6）

14．构造下面推理的证明：

分析：本题是根据基本的等值式、蕴含式、以及US、UG、ES、EG规则证明结论成立。前提：x(F(x)H(x)),x(G(x)H(x))结论：xG(x)7F(x)

证：（1）x(F(x)H(x))

前提引入

（2）x(7F(x)7H(x))

等价式（1）（3）x(H(x)7F(x))

等值式（2）（4）H(y)7F(y)

US规则（3）（5）x(G(x))H(x)

前提引入（6）G(y)H(y)

US规则（5）（7）G(y)F(y)

假言三段论（4），（6）

（8）x(G(x)7F(x))

UG规则（7）

15．指出下面两个推理的错误。

分析：本题主要是考察US、UG、ES、EG规则的适用范围，也就是前提条件。（1）x(F(x)G(x))

前提引入

（2）F(y)G(y)

US规则，根据（1）（3）xF(x)

前提引入

（4）F（y）

ES,(3)（5）G（y）

假言推理，（2），（4）（6）xGx

UG,(5）

解：（4）错误。Fy中的变元y与（2）中的变元重名。

（1）xyx，y

前提引入（2）yF(z,y)

US规则，（1）（3）F(z,c)

ES规则，（2）（4）xFx,c

UG，（3）（5）yxF(x,y)

EG，（4）解：（3）错误。在yF(z,y)中变元并非只有y。

16.每个学术会的成员都是知识分子并且是专家，有些成员是青年人。证明：有的成员是青年专家。分析：本题主要是首先把明天符号化，符号化前提，结论。然后根据US、UG、ES、EG规则证明结论成立。

解：P（x）：x是学术会的成员；

E（x）：x是专家；

G（x）：x是知识分子；

Y（x）：x是青年人。

前提：x(P(x)G(x)E(x)),(x)(P(x)Y(x))结论：x(P(x)Y(x)E(x))

证明：（1）x(P(x)G(x)E(x)))

前提引入

（2）P(c)(G(x)E(c))

US,(1)

（3）x(P(x)Y(x))

前提引入（4）P(c)Y(c)

ES,（3）（5）P（c）

化简（4）

（6）G(c)E(c)

假言推理,（2），（5）（7）E（c）

化简,（6）

（8）Y(c)

化简,（4）

（9）P(c)Y(c)E(c)

合取（5）（7）（8）（10）x(P(x)Y(x)E(x))

EG

第二篇：离散数学课后习题答案

第一章部分课后习题参考答案 设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: 是无理数

q: 3是无理数

0

r: 2是无理数

s: 6能被2整除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

0

0

0

0

0

0

0

0

所以公式类型为永真式

（5）公式类型为可满足式（方法如上例）（6）公式类型为永真式（方法如上例）

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

3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.1(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

0

0

0

0

0

0

0

0 0

0

0 1

0

0

0

0 1

0

1

0

0

0 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中用附加前提法证明下面各推理：

4(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 是矛盾式,所以推理正确.

第三篇：离散数学课后习题答案第三章

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

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, 如图所示。

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）得证。

网球的人} |C|=6,CAB

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

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,b23求R1R2,R2R1,R1,R2。

解: R1R2={,,} R2R1={} R12=R1R1={,,} R22=R2R2={,,} R23=R2R22={,,}

36．设A={1，2，3，4}，在AA上定义二元关系R，,AA，〈u,v> R u + y = x + v.(1)证明R 是AA上的等价关系.(2)确定由R 引起的对AA的划分.（1）证明：∵R u+y=x-y ∴Ru-v=x-y AA ∵u-v=u-v ∴R ∴R是自反的

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

任意的,,∈A×A 若R,R 则u-v=x-y,x-y=a-b ∴u-v=a-b ∴R ∴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+b ∴R ∴R是自反的

任意的,∈A×A 设R，则a+b=c+d ∴c+d=a+b ∴R ∴R是对称的 任意的,,∈A×A 若R,R 则a+b=c+d,c+d=x+y ∴a+b=x+y ∴R ∴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} 解: ***19511

42(1)(2)45.下图是两个偏序集的哈斯图.分别写出集合A和偏序关系R的集合表达式.debafc

gbcfdeag

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

(b)A={a,b,c,d,e,f,g} R={,,,,,,}IA 46.分别画出下列各偏序集的哈斯图,并找出A的极大元`极小元`最大元和最小元.(1)A={a,b,c,d,e} R={,,,,,,}IA.(2)A={a,b,c,d,e}, R={}IA.解:

edbcadeabc

(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

不是满射，不是单射

5.设X={a,b,c,d},Y={1,2,3},f={,,,}判断以下命题的真假:(1)f是从X到Y的二元关系,但不是从X到Y的函数;

对

(2)f是从X到Y的函数,但不是满射,也不是单射的;

错

(3)f是从X到Y的满射,但不是单射;

错

(4)f是从X到Y的双射.错

第四篇：离散数学课后习题答案第四章

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

4．判断下列集合对所给的二元运算是否封闭：（1）整数集合Z和普通的减法运算。

封闭,不满足交换律和结合律，无零元和单位元（2）非零整数集合普通的除法运算。不封闭

（R）和矩阵加法及乘法运算，其中n2。（3）全体nn实矩阵集合封闭 均满足交换律，结合律，乘法对加法满足分配律； 加法单位元是零矩阵，无零元；

乘法单位元是单位矩阵，零元是零矩阵；

（4）全体nn实可逆矩阵集合关于矩阵加法及乘法运算，其中n2。不封闭（5）正实数集合和运算，其中运算定义为：

不封闭

因为 1111111R（6）n关于普通的加法和乘法运算。

封闭，均满足交换律，结合律，乘法对加法满足分配律 加法单位元是0，无零元；

乘法无单位元（n1），零元是0；n1单位元是1（7）A = {a1,a2,,an} n运算定义如下：

封闭 不满足交换律，满足结合律，（8）S = 关于普通的加法和乘法运算。

封闭

均满足交换律，结合律，乘法对加法满足分配律（9）S = {0,1},S是关于普通的加法和乘法运算。

加法不封闭，乘法封闭；乘法满足交换律，结合律（10）S = ,S关于普通的加法和乘法运算。

加法不封闭，乘法封闭，乘法满足交换律，结合律

5．对于上题中封闭的二元运算判断是否适合交换律，结合律，分配律。

见上题

7．设 * 为Z上的二元运算x,yZ，X * Y = min(x，y),即x和y之中较小的数.(1)求4 * 6，7 * 3。

4,(2)* 在Z上是否适合交换律，结合律，和幂等律？ 满足交换律，结合律，和幂等律

(3)求*运算的单位元，零元及Z中所有可逆元素的逆元。单位元无，零元1, 所有元素无逆元

8．SQQ Q为有理数集，*为S上的二元运算，,S有

< a，b >* = （1）*运算在S上是否可交换，可结合？是否为幂等的？ 不可交换：*= < a，b >* 可结合：(*)*=*= *(*)=*=(*)*=*(*)不是幂等的

（2）*运算是否有单位元，零元？ 如果有请指出，并求S中所有可逆元素的逆元。

设是单位元，S，*= *= 则==，解的=<1,0>，即为单位。

设是零元，S，*= *= 则==，无解。即无零元。

S，设是它的逆元*= *=<1,0> ==<1,0> a=1/x,b=-y/x 所以当x0时，x,y11y, xx

10．令S={a，b}，S上有四个运算：*，分别有表10.8确定。

(a)

(b)

(c)

(d)

(1)这4个运算中哪些运算满足交换律，结合律，幂等律？(a)交换律，结合律，幂等律都满足，零元为a,没有单位元；(b)满足交换律和结合律，不满足幂等律，单位元为a,没有零元

a1a,b1b(c)满足交换律,不满足幂等律,不满足结合律

a(bb)aab, a(bb)(ab)b

没有单位元, 没有零元

(d)不满足交换律，满足结合律和幂等律

没有单位元, 没有零元

(2)求每个运算的单位元，零元以及每一个可逆元素的逆元。见上

(ab)baba

16．设V=〈 N，+，〉，其中+，分别代表普通加法与乘法，对下面给定的每个集合确定它是否构成V的子代数，为什么？

（1）S1=（2）S2= 是

不是 加法不封闭

（3）S3 = {-1，0，1} 不是，加法不封闭

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

8.设S={0，1，2，3}，为模4乘法，即

y=(xy)mod 4 “x,y∈S, x问〈S，〉是否构成群？为什么？

y=(xy)mod 4S,是S上的代数运算。解：(1)x,y∈S, x(2)x,y,z∈S,设xy=4k+r 0r3

(xy)z =((xy)mod 4)

z=r

z=(rz)mod 4 =(4kz+rz)mod 4=((4k+r)z)mod 4 =(xyz)mod 4 同理x(yz)=(xyz)mod 4 y)z = x1)=(1(y

z)，结合律成立。所以，(x(3)x∈S,(xx)=x,，所以1是单位元。

(4)111,313, 0和2没有逆元 所以，〈S，9.设Z为整数集合，在Z上定义二元运算。如下： ” x,y∈Z,xoy= x+y-2 问Z关于o运算能否构成群？为什么？ 〉不构成群 解：(1)x,y∈Z, xoy= x+y-2Z,o是Z上的代数运算。(2)x,y,z∈Z,(xoy)oz =(x+y-2)oz=(x+y-2)+z-2=x+y+z-4 同理(xoy)oz= xo(yoz)，结合律成立。

(3)设e是单位元，x∈Z, xoe= eox=x,即x+e-2= e+x-2=x, e=2(4)x∈Z , 设x的逆元是y, xoy= yox=e, 即x+y-2=y+x-2=2, 所以，x1y4x 所以〈Z，o〉构成群

101011.设G=01,01,101001,01，证明G关于矩阵乘法构成一个群． 解：(1)x,y∈G, 易知xy∈G,乘法是Z上的代数运算。

(2)矩阵乘法满足结合律

10(3)设01是单位元，(4)每个矩阵的逆元都是自己。所以G关于矩阵乘法构成一个群．

14.设G为群，且存在a∈G,使得 G={ak∣k∈Z} 证明：G是交换群。

证明:x,y∈G，设xak,yal，则

xyakalaklalkalakyx 所以，G是交换群

17.设G为群，证明e为G中唯一的幂等元。

22证明:设e0G也是幂等元，则e0e0，即e0e0e，由消去律知e0e

18.设G为群，a,b,c∈G,证明

∣abc∣=∣bca∣=∣cab∣ 证明：先证设(abc)ke(bca)ke 设(abc)ke,则(abc)(abc)(abc)(abc)e，即

a(bc)(abc)(abc)a(bc)aa1e 左边同乘a1，右边同乘a得

(bca)(bca)(bca)(bca)(bac)ka1eae

反过来，设(bac)ke,则(abc)ke.由元素阶的定义知，∣abc∣=∣bca∣，同理∣bca∣=∣cab∣

19.证明：偶数阶群G必含2阶元。

证明：设群G不含2阶元，aG，当ae时，a是一阶元，当ae时，a至少是3阶元,因为群G时有限阶的，所以a是有限阶的，设a是k阶的,则a1也是k阶的，所以高于3阶的元成对出现的，G不含2阶元，G含唯一的1阶元e,这与群G是偶数阶的矛盾。所以，偶数阶群G必含2阶元

20.设G为非Abel群，证明G中存在非单位元a和b,a≠b,且ab=ba.证明：先证明G含至少含3阶元。

若G只含1阶元,则G={e},G为Abel群矛盾；

若G除了1阶元e外,其余元a均为2阶元，则a2e，a1a

a,bG,a1a,b1b,(ab)1ab,所以aba1b1(ba)1ba，与G为Abel群矛盾；

所以，G含至少含一个3阶元，设为a，则aa2，且a2aaa2。令ba2的证。

21.设G是Mn(R)上的加法群，n≥2，判断下述子集是否构成子群。（1）全体对称矩阵 是子群（2）全体对角矩阵 是子群

（3）全体行列式大于等于0的矩阵.不是子群（4）全体上（下）三角矩阵。是子群

22.设G为群，a是G中给定元素，a的正规化子N（a）表示G中与a可交换的元素构成的集合，即 N（a）={x∣x∈G∧xa=ax} 证明N（a）构成G的子群。证明：ea=ae,eN(a)

x,yN(a),则axxa,ayya

a(xy)(ax)y(xa)yx(ay)x(ya)(xy)a,所以xyN(a)

由axxa，得x1axx1x1xax1,x1aeeax1，即x1aax1，所以x1N(a)所以N（a）构成G的子群

31.设1是群G1到G2的同态，2是G2到G3的同态，证明12是G1到G3的同态。证明：有已知1是G1到G2的函数，2是G2到G3的函数，则1·2是G1到G3的函数。

a,bG1,(12)(ab)2(1(ab))2(1(a)1(b))

(2(1(a)))(2(1(b)))(12)(a)(12)(b)所以:1·2是G1到G3的同态。

33.证明循环群一定是阿贝尔群，说明阿贝尔群是否一定为循环群，并证明你的结论。

证明：设G是循环群,令G=,x,yG,令xak,yal,那么

xyakalaklalkalakyx,G是阿贝尔群

克莱因四元群,G{e,a,b,c}

eeabceabcaaecb bbceaccbae是交换群,但不是循环群,因为e是一阶元，a,b,c是二阶元。36.设,是5元置换，且

123451234521453，34512

(1)计算,,1,1,1；(2)将,1,1表成不交的轮换之积。

(3)将（2）中的置换表示成对换之积，并说明哪些为奇置换，哪些为偶置换。

1234512345112345解：(1) 4532143125 45123

11234512345121534 54132 )1(14253(2)(1425)(25))1(143(3)(14)(12)(15)奇置换，1(14)(12)(15)(13)偶置换

1(14)(13)(25)奇置换

第五篇：离散数学习题及答案

离散数学考试试题（A卷及答案）

一、（10分）某项工作需要派A、B、C和D 4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？

(1)若A去，则C和D中要去1个人；

(2)B和C不能都去；

(3)若C去，则D留下。

解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：ACD，(B∧C)，CD必须同时成立。因此

(ACD)∧(B∧C)∧(CD)

(A∨(C∧ D)∨(C∧D))∧(B∨C)∧(C∨D)

(A∨(C∧ D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D))

(A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D)

∨(C∧ D∧B∧C)∨(C∧ D∧B∧D)∨(C∧ D∧C)∨(C∧ D∧C∧D)∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D∧C∧D)

F∨F∨(A∧C)∨F∨F∨(C∧ D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F (A∧C)∨(B∧C∧ D)∨(C∧D∧B)∨(C∧D)

(A∧C)∨(B∧C∧ D)∨(C∧D)

T

故有三种派法：B∧D，A∧C，A∧D。

二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。

解：论域：所有人的集合。S(x)：x是专家；W(x)：x是工人；Y(x)：x是青年人；则推理化形式为：

x(S(x)∧W(x))，xY(x)x(S(x)∧Y(x))

下面给出证明：

(1)xY(x)P

(2)Y(c)T(1)，ES

(3)x(S(x)∧W(x))P

(4)S(c)∧W(c)T(3)，US

(5)S(c)T(4)，I

(6)S(c)∧Y(c)T(2)(5)，I

(7)x(S(x)∧Y(x))T(6)，EG

三、（10分）设A、B和C是三个集合，则AB(BA)。

证明：ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA)

x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB)

(x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A))

(BA)。

四、（15分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。

解r(R)＝R∪IA＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>}

s(R)＝R∪R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>} R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}

R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>}

R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R

t(R)＝Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，i14232－

15>}。

五、（10分）R是非空集合A上的二元关系，若R是对称的，则r(R)和t(R)是对称的。

证明对任意的x、y∈A，若xr(R)y，则由r(R)＝R∪IA得，xRy或xIAy。因R与IA对称，所以有yRx或yIAx，于是yr(R)x。所以r(R)是对称的。

下证对任意正整数n，R对称。

因R对称，则有xRyz(xRz∧zRy)z(zRx∧yRz)yRx，所以R对称。若Rn对称，则xRn1yz(xRnz∧zRy)z(zRnx∧yRz)yRn1x，所以Rn1对称。因此，对任意正整数n，Rn对称。对任意的x、y∈A，若xt(R)y，则存在m使得xRy，于是有yRx，即有yt(R)x。因此，t(R)是对称的。

六、（10分）若f：A→B是双射，则f：B→A是双射。

证明因为f：A→B是双射，则f是B到A的函数。下证f是双射。

对任意x∈A，必存在y∈B使f(x)＝y，从而f(y)＝x，所以f是满射。

对任意的y1、y2∈B，若f(y1)＝f(y2)＝x，则f(x)＝y1，f(x)＝y2。因为f：A→B是函数，则y1＝y2。所以f是单射。

综上可得，f：B→A是双射。

七、（10分）设是一个半群，如果S是有限集，则必存在a∈S，使得a*a＝a。

证明因为是一个半群，对任意的b∈S，由*的封闭性可知，b＝b*b∈S，b＝b*b∈S，…，bn∈S，…。

因为S是有限集，所以必存在j＞i，使得bi＝bj。令p＝j－i，则bj＝bp*bj。所以对q≥i，有bq＝bp*bq。

因为p≥1，所以总可找到k≥1，使得kp≥i。对于bkp∈S，有bkp＝bp*bkp＝bp*(bp*bkp)＝…＝232－1－1－1－1－1－1－1－1－1mm222nbkp*bkp。

令a＝bkp，则a∈S且a*a＝a。

八、（20分）（1）若G是连通的平面图，且G的每个面的次数至少为l(l≥3)，则G的边数m与结点数n有如下关系：

m≤

rl(n－2)。l2l证明设G有r个面，则2m＝

2)。d(f)≥lr。由欧拉公式得，n－m＋r＝2。于是，m≤l2(n－ii

1（2）设平面图G＝是自对偶图，则| E|＝2(|V|－1)。

证明设G＝是连通平面图G＝的对偶图，则G G，于是|F|＝|V*|＝|V|，将其代入欧拉公式|V|－|E|＋|F|＝2得，|E|＝2(|V|－1)。**

离散数学考试试题（B卷及答案）

一、（10分）证明(P∨Q)∧(PR)∧(QS)S∨R

证明因为S∨RRS，所以，即要证(P∨Q)∧(PR)∧(QS)RS。

(1)R附加前提

(2)PRP

(3)PT(1)(2)，I

(4)P∨QP

(5)QT(3)(4)，I

(6)QSP

(7)ST(5)(6)，I

(8)RSCP

(9)S∨RT(8)，E

二、（15分）根据推理理论证明：每个考生或者勤奋或者聪明，所有勤奋的人都将有所作为，但并非所有考生都将有所作为，所以，一定有些考生是聪明的。

设P(e)：e是考生，Q(e)：e将有所作为，A(e)：e是勤奋的，B(e)：e是聪明的，个体域：人的集合，则命题可符号化为：x(P(x)(A(x)∨B(x)))，x(A(x)Q(x))，x(P(x)Q(x))x(P(x)∧B(x))。

(1)x(P(x)Q(x))P

(2)x(P(x)∨Q(x))T(1)，E

(3)x(P(x)∧Q(x))T(2)，E

(4)P(a)∧Q(a)T(3)，ES

(5)P(a)T(4)，I

(6)Q(a)T(4)，I

(7)x(P(x)(A(x)∨B(x))P

(8)P(a)(A(a)∨B(a))T(7)，US

(9)A(a)∨B(a)T(8)(5)，I

(10)x(A(x)Q(x))P

(11)A(a)Q(a)T(10)，US

(12)A(a)T(11)(6)，I

(13)B(a)T(12)(9)，I

(14)P(a)∧B(a)T(5)(13)，I

(15)x(P(x)∧B(x))T(14)，EG

三、（10分）某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。

解设A、B、C分别表示会打排球、网球和篮球的学生集合。则：

|A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，|B∩C|＝5，|A∩B∩C|＝2，|(A∪C)∩B|＝6。

因为|(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所以|(A∩

B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，|ABC|＝25－20＝5。故，不会打这三种球的共5人。

四、（10分）设A1、A2和A3是全集U的子集，则形如Ai(Ai为Ai或Ai)的集合称为由A1、A2和

i1

3A3产生的小项。试证由A1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。

证明小项共8个，设有r个非空小项s1、s2、…、sr(r≤8)。

对任意的a∈U，则a∈Ai或a∈Ai，两者必有一个成立，取Ai为包含元素a的Ai或Ai，则a∈Ai，i13即有a∈si，于是Usi。又显然有siU，所以U＝si。

i1i1i1i1rrrr

任取两个非空小项sp和sq，若sp≠sq，则必存在某个Ai和Ai分别出现在sp和sq中，于是sp∩sq＝。综上可知，{s1，s2，…，sr}是U的一个划分。

五、（15分）设R是A上的二元关系，则：R是传递的R*RR。

证明(5)若R是传递的，则∈R*Rz(xRz∧zSy)xRc∧cSy，由R是传递的得xRy，即有∈R，所以R*RR。

反之，若R*RR，则对任意的x、y、z∈A，如果xRz且zRy，则∈R*R，于是有∈R，即有xRy，所以R是传递的。

六、（15分）若G为连通平面图，则n－m＋r＝2，其中，n、m、r分别为G的结点数、边数和面数。证明对G的边数m作归纳法。

当m＝0时，由于G是连通图，所以G为平凡图，此时n＝1，r＝1，结论自然成立。

假设对边数小于m的连通平面图结论成立。下面考虑连通平面图G的边数为m的情况。

设e是G的一条边，从G中删去e后得到的图记为G，并设其结点数、边数和面数分别为n、m和r。对e分为下列情况来讨论：

若e为割边，则G有两个连通分支G1和G2。Gi的结点数、边数和面数分别为ni、mi和ri。显然n1＋n2＝n＝n，m1＋m2＝m＝m－1，r1＋r2＝r＋1＝r＋1。由归纳假设有n1－m1＋r1＝2，n2－m2＋r2＝2，从而(n1＋n2)－(m1＋m2)＋(r1＋r2)＝4，n－(m－1)＋(r＋1)＝4，即n－m＋r＝2。

若e不为割边，则n＝n，m＝m－1，r＝r－1，由归纳假设有n－m＋r＝2，从而n－(m－1)＋r－1＝2，即n－m＋r＝2。

由数学归纳法知，结论成立。

七、（10分）设函数g：A→B，f：B→C，则：

(1)fg是A到C的函数；

(2)对任意的x∈A，有fg(x)＝f(g(x))。

证明(1)对任意的x∈A，因为g：A→B是函数，则存在y∈B使∈g。对于y∈B，因f：B→C是函数，则存在z∈C使∈f。根据复合关系的定义，由∈g和∈f得∈g*f，即∈fg。所以Dfg＝A。

对任意的x∈A，若存在y1、y2∈C，使得、∈fg＝g*f，则存在t1使得∈g且∈f，存在t2使得∈g且∈f。因为g：A→B是函数，则t1＝t2。又因f：B→C是函数，则y1＝y2。所以A中的每个元素对应C中惟一的元素。

综上可知，fg是A到C的函数。

(2)对任意的x∈A，由g：A→B是函数，有∈g且g(x)∈B，又由f：B→C是函数，得∈f，于是∈g*f＝fg。又因fg是A到C的函数，则可写为fg(x)＝f(g(x))。

八、（15分）设是的子群，定义R＝{|a、b∈G且a1*b∈H}，则R是G中的－

一个等价关系，且[a]R＝aH。

证明对于任意a∈G，必有a1∈G使得a1*a＝e∈H，所以∈R。－－

若∈R，则a1*b∈H。因为H是G的子群，故(a1*b)1＝b1*a∈H。所以∈R。－－－－

若∈R，∈R，则a1*b∈H，b1*c∈H。因为H是G的子群，所以(a1*b)*(b1*c)＝a－－－－

－1*c∈H，故∈R。

综上可得，R是G中的一个等价关系。

对于任意的b∈[a]R，有∈R，a1*b∈H，则存在h∈H使得a1*b＝h，b＝a*h，于是b∈aH，－－

[a]RaH。对任意的b∈aH，存在h∈H使得b＝a*h，a1*b＝h∈H，∈R，故aH[a]R。所以，[a]R－

＝aH。