离散数学答案屈婉玲版

第二版高等教育出版社课后答案

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

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) ?320m m m ∨∨

?∑(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) ? M 1 ?∏(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)在两个个体域中都解释为)

?，在（a）中为假命题，在(b)中为真命题。

xF

(x

(2)在两个个体域中都解释为)

?，在（a）(b)中均为真命题。

(x

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

x

G

y

?

y

∧

x→

?

))

(

,

(

)

x

((y

(

H

(2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快

命题符号化为: )))

y

x

F

G

y→

??

∧

?

x

(

)

(

,

(

)

x

H

(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

∈.

说明下列公式在I下的含义,并指出各公式的真值:

(1)))

y

G

x?

→

?

?

x

y

,

)

(

(

(y

F

x

,

(2)))

x

y

a

f

F

?

x→

G

?

y

)

(

,

x

),

(y

,

(

(

答:(1) 对于任意两个实数x,y,如果x

(2) 对于任意两个实数x,y,如果x-y=0, 那么x

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)因为1

q

→

p

p

p为永真式；

q

?

→p

)

?

)

(?

(

∨

?

∨

所以为永真式；

(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))(x f 为3)4(,4)3(==f f

(c)1)3,4()4,3(,0)4,4()3,3(),(====F F F F y x F 为. 试求下列公式在Ｉ下的真值. (1)),(y x yF x ??

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

? ))4,4()3,4(())4,3()3,3((F F F F ∨∧∨ ?1)01()10(?∨∧∨

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

))))4(),(()4,(()))3(),(()3,(((f x f F x F f x f F x F x →∧→??

)))3),(()4,(())4),(()3,(((x f F x F x f F x F x →∧→??

)))3),3(()4,3(())4),3(()3,3(((f F F f F F →∧→?

)))3),4(()4,4(())4),4(()3,4(((f F F f F F →∧→∧

)))3,4()4,3(())4,4(0((F F F →∧→?)))3,3(0())4,3(1((F F →∧→∧

)11()00(→∧→?)00()11(→∧→∧1?

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

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

(5))),()((),(2121211x x G x x H x x F x ??→→? (本题课本上有错误) 解:(1) ),()(y x yG x xF ?→?),()(y t yG x xF ?→??)),()((y t G x F y x →??? (5) )),()((),(2121211x x G x x H x x F x ??→→?

)),()((),(2323211x x G x x H x x F x ??→→?? )),()((),(2332411x x G x H x x x F x ?→?→?? ))),()((),((2334121x x G x H x x F x x ?→→???

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

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

结论: ?xR(x)

(2) 前提: ?x(F(x)→(G(a)∧R(x))), xF(x) 结论:x(F(x)∧R(x)) 证明(1)

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

③))())()((()(y R y G y F y x xF →∨?→? 前提引入 ④))())()(((y R y G y F 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)) ⑦EG

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

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,全域关系E A,小于或等于关系L A,整除关系D A.

={,,}

解：I

A

={,,,,,,,,}

E

A

={,,,,,}

L

A

={}

D

A

13.设A={,,}

B={,,}

求A?B,A?B, domA, domB, dom(A?B), ranA, ranB, ran(A?B ), fld(A-B).

解：A?B={,,,,}

A?B={}

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={,}，fld(A-B)={1,2,3}

14.设R={,,,,}

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

解：R R={,,}

R -1,={,,,,,}

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

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

1

R ={

},,,,,a a a b b d

{}2,,,,,,,R a d b c b d c b

=

求23

122112,,,R R R R R R 。

解: R 1 R 2={,,} R 2 R 1={}

R 12=R 1 R 1={,,} R 22=R 2 R 2={,,} R 23=R 2 R 22={,,}

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) ∏={{,,,}, {,,}, {,}, {}, {,,}, {,}, {} }

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)∏={{}, {,}, {,,}, {,,,}, {,,}, {,}, {}}

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

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

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

:

2

3

468

1

11

(1) (2)

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

d

g

a

b

f g

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

R ={,,,,,,,,,}A I ?

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

R ={,,,,,,}A I ?

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

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

R ={,,,,,,}?I A . (2)A={a,b,c,d,e}, R ={}?IA. 解:

a

b d

e

a

b

c

d

e

(1) (2)

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

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

1．设f :N →N,且

f (x)=12x x x ??

???

，若为奇数若为偶数，

求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)=x 2+2 不是满射，不是单射

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

(3) f:N →N,f(x)=10x x ???，若为奇数

，若为偶数 不是满射，不是单射

(4) f:N →{0,1},f(x)=01x x ???，若为奇数

，若为偶数 是满射，不是单射

(5) f:N-{0}→R,f(x)=lgx 不是满射，是单射 (6) f:R →R,f(x)=x 2-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） 非零整数集合

普通的除法运算。不封闭

（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关于普通的加法和乘法运算。

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

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

见上题

7．设* 为+Z上的二元运算+

x,，

y

?Z

∈

X * Y = min ( x，y ),即x和y之中较小的数.

(1)求4 * 6，7 * 3。

4, 3

Z上是否适合交换律，结合律，和幂等律？

(2)* 在+

满足交换律，结合律，和幂等律

(3)求*运算的单位元，零元及+

Z中所有可逆元素的逆元。

单位元无，零元1, 所有元素无逆元

8．Q

=Q为有理数集，*为S上的二元运算，,S有

Q

S?

* =

（1）*运算在S上是否可交换，可结合？是否为幂等的？

不可交换：*= ≠*

可结合：(*)*=*=

*(*)=*=

(*)*=*(*)

不是幂等的

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

设是单位元，S ，*= *=

则==，解的=，即为单位。

设是零元，S ，*= *=

则==，无解。即无零元。

S，设是它的逆元*= *=

==

a=1/x,b=-y/x

所以当x ≠0时，x

y x y x -=

>

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) 不满足交换律，满足结合律和幂等律 没有单位元, 没有零元

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

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

问〈S ，〉是否构成群？为什么？

解：(1) ?x,y ∈S, x

y=(xy)mod 4S ∈,

是S 上的代数运算。

(2) ?x,y,z ∈S,设xy=4k+r 30≤≤r

(x

y)

z =((xy)mod 4)

z=r

z=(rz)mod 4

=(4kz+rz)mod 4=((4k+r)z)mod 4 =(xyz)mod 4 同理x

(y

z) =(xyz)mod 4 所以，(x y)

z = x (y

z)，结合律成立。

(3) ?x ∈S, (x

1)=(1

x)=x,，所以1是单位元。

(4),33,1111==-- 0和2没有逆元 所以，〈S ，〉不构成群

9.设Z 为整数集合，在Z 上定义二元运算。如下： " ?x,y ∈Z,xoy= x+y-2 问Z 关于o 运算能否构成群？为什么？

解：(1) ?x,y ∈Z, xoy= x+y-2Z ∈,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, xo e = e ox=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 y x -==-41 所以〈Z ，o 〉构成群

11.设G=?

??

??????? ??--???? ??-???? ??-???? ??1001,1001,

1001,1001，证明G 关于矩阵乘法构成一个群． 解：(1) ?x,y ∈G, 易知xy ∈G,乘法是Z 上的代数运算。

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

(3)设???

?

??1001是单位元，

离散数学答案屈婉玲版 第二版高等教育出版社课后答案 第一章部分课后习题参考答案 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)

第四章部分课后习题参考答案 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 xF ?，在（a ）中为假命题，在(b)中为真命题。 (2)在两个个体域中都解释为)(x xG ?，在（a ）(b)中均为真命题。 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x 能表示成分数 H(x): x 是有理数 命题符号化为: ))()((x H x F x ∧??? (2)F(x): x 是北京卖菜的人 H(x): x 是外地人 命题符号化为: ))()((x H x F x →?? 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x 是火车; G(x): x 是轮船; H(x,y): x 比y 快

命题符号化为: )) F x G x→ ∧ ? ? y y ( )) ( ) , x ((y ( H (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 命题符号化为: ))) x x F y y→ ?? ∧ ? G (y H ( , ( ) ( ( x ) 9.给定解释I如下: (a) 个体域D为实数集合R. (b) D中特定元素错误！未找到引用源。=0. (c) 特定函数错误！未找到引用源。(x,y)=x错误！未找到引用源。y,x,y D ∈错误！未找到引用源。. (d) 特定谓词错误！未找到引用源。(x,y):x=y,错误！未找到引用源。(x,y):x离散数学课后习题答案

习题参考解答 习题 1、（3）P：银行利率降低 Q：股价没有上升 P∧Q （5）P：他今天乘火车去了北京 Q：他随旅行团去了九寨沟 Q P? （7）P：不识庐山真面目 Q：身在此山中 Q→P，或～P→～Q （9）P：一个整数能被6整除 Q：一个整数能被3整除 R：一个整数能被2整除 T：一个整数的各位数字之和能被3整除 P→Q∧R ，Q→T 2、（1）T （2）F （3）F （4）T （5）F （6）T （7）F （8）悖论 习题 1（3） ) ( ) ( ) ( ) ( ) ( ) ( R P Q P R P Q P R Q P R Q P → ∨ → ? ∨ ? ∨ ∨ ? ? ∨ ∨ ? ? ∨ →

（4） ()()()(())()(()())(())()()()()P Q Q R R P P R Q R P P R R P Q R P P R P R Q R Q P ∧∨∧∨∧=∨∧∨∧=∨∨∧∧∨∧=∨∧∨∧∨∧∨=右 2、不， 不， 能 习题 1(3) (())~((~)) (~)()~(~(~))(~~)(~) P R Q P P R Q P P R T P R P R Q Q P R Q P R Q →∧→=∨∧∨=∨∧=∨=∨∨∧=∨∨∧∨∨、 主合取范式 ) ()()()()()()()()()()()()()())(())(()()(()) ()())(()((Q P R P Q R P Q R R Q P R Q P R Q P Q P R Q P R P Q R P Q R R Q P R Q P R Q P R Q P Q Q P R P P Q R R R Q Q P P R Q R P P Q R P P Q R P ∧∧∨∧?∧∨?∧?∧∨∧?∧?∨?∧∧?∨?∧?∧?=∧∧∨?∧∧∨∧?∧∨?∧?∧∨∧?∧?∨∧?∧?∨?∧∧?∨?∧?∧?=∨?∧∧∨∨?∧?∧∨∨?∧∨?∧?=∧∨?∧∨?=∨?∧∨?=→∧→ ————主析取范式 (2) ()()(~)(~) (~(~))(~(~))(~~)(~)(~~) P Q P R P Q P R P Q R R P R Q Q P Q R P Q R P R Q →∧→=∨∧∨=∨∨∧∧∨∨∧=∨∨∧∨∨∧∨∨Q 2、 ()~() (~)(~) (~~)(~)(~~)P Q R P Q R P Q P R P Q R P Q R P R Q →∧=∨∧=∨∧∧=∨∨∧∨∨∧∨∨∴等价 3、解：根据给定的条件有下述命题公式： （A →（CD ））∧～（B ∧C ）∧～（C ∧D ） （～A ∨（C ∧～D ）∨（～C ∧D ））∧（～B ∨～C ）∧（～C ∨～D ） （（～A ∧～B ）∨（C ∧～D ∧～B ）∨（～C ∧D ∧～B ）∨ （～A ∧～C ）∨（C ∧～D ∧～C ）∨（～C ∧D ∧～C ））∧（～C ∨～D ）

第一章部分课后习题参考答案 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 所以公式类型为永真式//最后一列全为1 （5）公式类型为可满足式（方法如上例）//最后一列至少有一个1 （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)

离散数学课后习题答案(左孝凌版) 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）解：

离散数学第四版课后答案 第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的真值是确定的（客观存在的），只是现在不知道而已。（9）p：太阳系外的星球上的生物。它的真值情况而定，是确定的。 1 （10）p：小李在宿舍里. p的真值则具体情况而定，是确定的。 （12）p∨q，其中，p:4是偶数，q:4是奇数。由于q是假命题，所以，q 为假命题，p∨q为真命题。 （13）p∨q，其中，p:4是偶数，q:4是奇数，由于q是假命题，所以，p∨q 为假命题。 （14）p：李明与王华是同学，真值由具体情况而定（是确定的）。 （15）p：蓝色和黄色可以调配成绿色。这是真命题。 分析命题的真值是唯一确定的，有些命题的真值我们立即可知，有些则不能马上知道，但它们的真值不会变化，是客观存在的。 1．3 令p:2+2=4,q:3+3=6,则以下命题分别符号化为 （1）p→q （2）p→?q （3）?p→q （4）?p→?q

1.1．略 1.2．略 1.3．略 1.4．略 1.5．略 1.6．略 1.7．略 1.8．略 1.9．略 1.10．略 1.11．略 1.12．将下列, 并给出各命题的: (1)2+2＝4 当且仅 当3+3＝6. (2)2+2＝4 的充要 条件是3+3 6. (3)2+2 4 与3+3 ＝6 互为充要条件. (4)若2+24, 则 3+36, 反之亦然. (1)p q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为1. (2)p q,

其中, p: 2+2＝4, q: 3+3＝6, 真值为0. (3) p q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为0. (4) p q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为1. 1.13．将下列命题符号化, 并给出各命题的真值:(1)若今天是星期一, 则明天是星期二. (2)只有今天是星期一, 明天才是星期二. (3)今天是星期一当且仅当明天是星期二. (4)若今天是星期一, 则明天是星期三. 令p: 今天是星期一; q: 明天是星期二; r: 明天是星期三. (1) p q 1. (2) q p 1. (3) p q 1.

(4) p r 当p 0 时为真; p 1 时为假. 1.14．将下 列 . (1) 刘 晓月跑得快, 跳得高. (2) 老王是山东 人或河北人. (3)因为天气冷, 所以我穿了羽 绒服. (4)王欢与李乐组成一个 小组. (5)李辛与李末是兄弟. (6)王强与刘威都学 过法语. (7)他一面 吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他 迟到了. (12)2 与4 都是素数, 这是不对的. (13)“2或4 是素数, 这是不对的”是不对的.

离散数学习题详细答案

————————————————————————————————作者：————————————————————————————————日期：

离散数学习题答案 习题一及答案：（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、求下列公式的成真赋值：

离散数学课后答案 习题一 6.将下列命题符号化。 （1）小丽只能从框里那一个苹果或一个梨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答： （1）（p Λ?q ）ν（?pΛq）其中p:小丽拿一个苹果，q:小丽拿一个梨（2）（p Λ?q ）ν（?pΛq）其中p:刘晓月选学英语，q:刘晓月选学日语 14.将下列命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2与4都是素数, 这是不对的. (13)“2或4是素数, 这是不对的”是不对的. 答： (1)p∧q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高. (2)p∨q, 其中, p: 老王是山东人, q: 老王是河北人. (3)p→q, 其中, p: 天气冷, q: 我穿了羽绒服. (4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题. (5)p, 其中, p: 李辛与李末是兄弟. (6)p∧q, 其中, p: 王强学过法语, q: 刘威学过法语. (7)p∧q, 其中, p: 他吃饭, q: 他听音乐. (8)p→q, 其中, p: 天下大雨, q: 他乘班车上班. (9)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (10)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (11)p→q, 其中, p: 下雪路滑, q: 他迟到了. (12) ? (p∧q)或?p∨?q, 其中, p: 2是素数, q: 4是素数. (13) ? ? (p∨q)或p∨q, 其中, p: 2是素数, q: 4是素数. 16. 19.用真值表判断下列公式的类型: (1)p→ (p∨q∨r) (2)(p→?q) →?q

离散数学第二版邓辉文编著第一章第二节习题答案 1.2 映射的有关概念 习题1.2 1. 分别计算?1. 5?，?-1?，?-1. 5?，? 1. 5?，?-1?，?-1. 5?. 解?1. 5?=2，?-1?=-1，?-1. 5?=-1，?1. 5?=1，?-1?=-1，?-1. 5?=-2. 2. 下列映射中，那些是双射? 说明理由. (1)f :Z →Z , f (x ) =3x . (2)f :Z →N , f (x ) =|x |+1. (3)f :R →R , f (x ) =x 3+1. (4)f :N ?N →N , f (x 1, x 2) =x 1+x 2+1. (5)f :N →N ?N , f (x ) =(x , x +1). 解 (1)对于任意对x 1, x 2∈Z ，若f (x 1) =f (x 2) ，则3x 1=3x 2，于是x 1=x 2，所以f 是单射. 由于对任意x ∈Z ，f (x ) ≠2∈Z ，因此f 不是满射，进而f 不是双射. (2)由于2, -2∈Z 且f (2) =f (-2) =3，因此f 不是单射. 又由于0∈N ，而任意x ∈Z 均有f (x ) =|x |+1≠0，于是f 不是满射. 显然，f 不是双射. (3)对于任意对x 1, x 2∈R ，若f (x 1) =f (x 2) ，则x 1+1=x 2+1，于是x 1=x 2，所以f 是单射. 对于任意y ∈R ，取x =(y -1) ，这时 1??3f (x ) =x +1=?(y -1) 3?+1=(y -1) +1=y ， ??33313 所以f 是满射. 进而f 是双射.

习题3.7 1. 列出关系}6|{=???∈>离散数学课后习题答案

1-1，1-2 （1）解： 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）解： a)不是合式公式，没有规定运算符次序（若 规定运算符次序后亦可作为合式公式） b)是合式公式 c)不是合式公式（括弧不配对） d)不是合式公式（R和S之间缺少联结词） e)是合式公式。 （2）解：

习题 1-5 （1）证明： a)(P∧(P→Q))→Q (P∧(┐P∨Q))→Q (P∧┐P)∨(P∧Q)→Q (P∧Q)→Q ┐(P∧Q)∨Q ┐P∨┐Q∨Q ┐P∨T T b)┐P→(P→Q) P∨(┐P∨Q) (P∨┐P)∨Q T∨Q T c)((P→Q)∧(Q→R))→(P→R) 因为(P→Q)∧(Q→R)(P→R) 所以(P→Q)∧(Q→R)为重言式。 d)((a∧b)∨(b∧c) ∨(c∧a))(a∨b)∧(b∨c)∧(c∨a) 因为((a∧b)∨(b∧c)∨(c∧a)) ((a∨c)∧b)∨(c∧a) ((a∨c)∨(c∧a))∧(b∨(c∧a)) (a∨c)∧(b∨c)∧(b∨a) 所以((a∧b)∨(b∧c) ∨(c∧a))(a∨b)∧(b∨c)∧(c∨a)为重言式。 （2）证明： a)(P→Q)P→(P∧Q) 解法1： 设P→Q为T （1）若P为T，则Q为T，所以P∧Q为T，故P→(P∧Q)为T （2）若P为F，则Q为F，所以P∧Q为F，P→(P∧Q)为T 命题得证 解法2： 设P→(P∧Q)为F ，则P为T，(P∧Q)为F ，故必有P为T，Q为F ，所以P→Q为F。 解法3： (P→Q) →(P→(P∧Q)) ┐(┐P∨Q)∨(┐P∨(P∧Q)) ┐(┐P∨Q)∨((┐P∨P)∧(┐P∨Q)) T 所以(P→Q)P→(P∧Q) b)(P→Q)→Q P∨Q

设P∨Q为F，则P为F，且Q为F， 故P→Q为T，(P→Q)→Q为F， 所以(P→Q)→Q P∨Q。 c)(Q→(P∧┐P))→(R→(R→(P∧┐P)))R→Q 设R→Q为F，则R为T，且Q为F，又P∧┐P为F 所以Q→(P∧┐P)为T，R→(P∧┐P)为F 所以R→(R→(P∧┐P))为F，所以(Q→(P∧┐P))→(R→(R→(P∧┐P)))为F 即(Q→(P∧┐P))→(R→(R→(P∧┐P)))R→Q成立。 （3）解： a) P→Q表示命题“如果8是偶数，那么糖果是甜的”。 b)a)的逆换式Q→P表示命题“如果糖果是甜的，那么8是偶数”。 c)a)的反换式┐P→┐Q表示命题“如果8不是偶数，那么糖果不是甜的”。 d)a)的逆反式┐Q→┐P表示命题“如果糖果不是甜的，那么8不是偶数”。（4）解： a)如果天下雨，我不去。 设P：天下雨。Q：我不去。P→Q 逆换式Q→P表示命题:如果我不去，则天下雨。 逆反式┐Q→┐P表示命题:如果我去，则天不下雨 b)仅当你走我将留下。 设S：你走了。R：我将留下。R→S 逆换式S→R表示命题：如果你走了则我将留下。 逆反式┐S→┐R表示命题：如果你不走，则我不留下。 c)如果我不能获得更多帮助，我不能完成个任务。 设E：我不能获得更多帮助。H：我不能完成这个任务。E→H 逆换式H→E表示命题：我不能完成这个任务，则我不能获得更多帮助。 逆反式┐H→┐E表示命题：我完成这个任务，则我能获得更多帮助（5）试证明P Q，Q逻辑蕴含P。 证明：解法1： 本题要求证明(P Q) ∧Q P, 设(P Q) ∧Q为T，则(P Q)为T，Q为T ，故由的定义，必有P为T。 所以(P Q) ∧Q P 解法2： 由体题可知，即证((P Q)∧Q)→P是永真式。 ((P Q)∧Q)→P (((P∧Q) ∨(┐P∧┐Q)) ∧Q)→P (┐((P∧Q) ∨(┐P∧┐Q)) ∨┐Q) ∨P (((┐P∨┐Q) ∧(P∨Q)) ∨┐Q) ∨P ((┐Q∨┐P∨┐Q) ∧(┐Q∨P∨Q)) ∨P ((┐Q∨┐P) ∧T) ∨P ┐Q∨┐P∨P

1.2 映射的有关概念 习题1.2 1. 分别计算??5.1，??1-，??5.1-，??5.1，??1-，??5.1-. 解 ??25.1=，??11-=-，??15.1-=-，??15.1=，??11-=-，??25.1-=-. 2.下列映射中，那些是双射? 说明理由. (1).3)(,Z Z :x x f f =→ (2).1||)(,N Z :+=→x x f f (3).1)(,R R :3+=→x x f f (4).1),(,N N N :2121++=→?x x x x f f (5)).1,()(,N N N :+=?→x x x f f 解 (1)对于任意对∈21,x x Z ，若)()(21x f x f =，则2133x x =，于是21x x =，所以f 是单射. 由于对任意∈x Z ，∈≠2)(x f Z ，因此f 不是满射，进而f 不是双射. (2)由于∈-2,2Z 且3)2()2(=-=f f ，因此f 不是单射. 又由于∈0N ，而任意∈x Z 均有01||)(≠+=x x f ，于是f 不是满射. 显然，f 不是双射. (3)对于任意对∈21,x x R ，若)()(21x f x f =，则113231+=+x x ，于是21x x =，所以f 是单射. 对于任意∈y R ，取3 1)1(-=y x ，这时 y y y x x f =+-=+??????-=+=1)1(1)1(1)(3313， 所以f 是满射. 进而f 是双射. (4)由于∈)1,2(),2,1(N ?N 且)1,2()2,1(≠，而4)1,2()2,1(==f f ，因此f 不是单射. 又由于∈0N ，而任意∈),(21x x N ?N 均有01),(2121≠++=x x x x f ，于是f 不是满射. 显然，f 就不是双射. (5)由于∈21,x x N ，若)()(21x f x f =，则)1,()1,(2211+=+x x x x ，于是21x x =，因此f 是单射. 又由于∈)0,0(N ?N ，而任意∈x N 均有)0,0()1,()(≠+=x x x f ，于是f 不是满射. 因为f 不是满射，所以f 不是双射.

第一章命题逻辑基本概念 4.将下列命题符号化，并指出真值： （1）p∧q,其中，p:2是素数，q:5是素数,真值为1； （2）p∧q,其中，p:是无理数，q:自然对数的底e是无理数,真值为1； （3）p∧┐q,其中，p:2是最小的素数，q:2是最小的自然数,真值为1； （4）p∧q,其中，p:3是素数，q:3是偶数,真值为0； （5）┐p∧┐q,其中，p:4是素数，q:4是偶数,真值为0. 5.将下列命题符号化，并指出真值： （1）p∨q,其中，p:2是偶数，q:3是偶数,真值为1； （2）p∨q,其中，p:2是偶数，q:4是偶数,真值为1； （3）p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0； （4）p∨q,其中，p:3是偶数，q:4是偶数,真值为1； （5）┐p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0； 6.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨； （2）(p∧┐q)∨(┐p∧q),其中，p：刘晓月选学英语，q：刘晓月选学日语；. 7.因为p与q不能同时为真. 8.p:2

《离散数学1-5章》练习题答案第2，3章(数理逻辑) 1.答：（2），（3），（4） 2.答：（2），（3），（4），（5），（6） 3.答：（1）是，T （2）是，F （3）不是 （4）是，T （5）不是（6）不是 4.答：（4） 5.答：?P ，Q→P 6.答：P(x)∨?yR(y) 7.答：??x(R(x)→Q(x)) 8、 c、P→(P∧(Q→P)) 解：P→(P∧(Q→P)) ??P∨(P∧(?Q∨P)) ??P∨P ? 1 (主合取范式) ? m0∨ m1∨m2∨ m3 （主析取范式） d、P∨(?P→(Q∨(?Q→R))) 解：P∨(?P→(Q∨(?Q→R))) ? P∨(P∨(Q∨(Q∨R))) ? P∨Q∨R ? M0 (主合取范式) ? m1∨ m2∨m3∨ m4∨ m5∨m6 ∨m7 (主析取范式) 9、

b、P→(Q→R)，R→(Q→S) => P→(Q→S) 证明： （1） P 附加前提 （2） Q 附加前提 （3） P→(Q→R) 前提 （4） Q→R （1），（3）假言推理 （5） R （2），（4）假言推理 （6） R→(Q→S) 前提 （7） Q→S （5），（6）假言推理 （8） S （2），（7）假言推理 d、P→?Q，Q∨?R，R∧?S??P 证明、 (1) P 附加前提 （2） P→?Q 前提 （3）?Q （1），（2）假言推理 （4） Q∨?R 前提 (5) ?R （3），（4）析取三段论 (6 ) R∧?S 前提 （7） R （6）化简 （8） R∧?R 矛盾（5），（7）合取 所以该推理正确 10.写出?x(F(x)→G(x))→(?xF(x) →?xG(x))的前束范式。 解：原式??x(?F(x)∨G(x))→(?(?x)F(x) ∨ (?x)G(x)) ??(?x)(?F(x)∨G(x)) ∨(?(?x)F(x) ∨ (?x)G(x)) ? (?x)((F(x)∧? G(x)) ∨G(x)) ∨ (?x) ?F(x)

习题一 1.下列句子中,哪些是命题？在是命题的句子中,哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？ （1）中国有四大发明. 答：此命题是简单命题，其真值为 1. （2）5 是无理数. 答：此命题是简单命题，其真值为 1. （3）3 是素数或 4 是素数. 答：是命题，但不是简单命题，其真值为1. （4）2x+

（2）25 不是无理数. 答：否定式：25 是有理数. p：25 不是无理数. q：25 是有理数. 其否定式q 的 真值为1. （3）2.5 是自然数. 答：否定式：2.5 不是自然数. p：2.5 是自然数. q：2.5 不是自然数. 其否定式q 的真值为1. （4）ln1 是整数. 答：否定式：ln1 不是整数. p：ln1 是整数. q：ln1 不是整数. 其否定式q 的真值为1. 4.将下列命题符号化，并指出真值. （1）2 与5 都是素数 答：p：2 是素数，q：5 是素数，符号化为p q∧ ，其真值为 1. （2）不但π是无理数，而且自然对数的底e 也是无理数. 答：p：π 是无理数，q：自然对数的底e 是无理数，符号化为p q∧ ，其真值为1. （3）虽然2 是最小的素数，但2 不是最小的自然数. 答：p：2 是最小的素数，q：2 是最小的自然数，符号化为p q∧? ，其真值为1. （4）3 是偶素数. 答：p：3 是素数，q：3 是偶数，符号化为p q∧ ，其真值为0. （5）4 既不是素数，也不是偶数. 答：p：4 是素数，q：4 是偶数，符号化为? ∧?p q，其真值为0. 5.将下列命题符号化，并指出真值. （1）2 或3 是偶数. （2）2 或4 是偶数. （3）3 或5 是偶数. （4）3 不是偶数或4 不是偶数. （5）3 不是素数或4 不是偶数. 答: p：2 是偶数，q：3 是偶数，r:3 是素数，s:4 是偶数, t:5 是偶数 (1)符号化: p q∨ ，其真值为1. (2)符号化：p r∨ ，其真值为1. (3)符号化：r t∨ ，其真值为0. (4)符号化：? ∨?q s，其真值为1. (5)符号化：? ∨?r s，其真值为0. 6.将下列命题符号化. （1）小丽只能从筐里拿一个苹果或一个梨. 答：p：小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨，符号化为: p q∨ . （2）这学期，刘晓月只能选学英语或日语中的一门外语课.

第一章 命题逻辑基本概念 课后练习题答案 4.将下列命题符号化，并指出真值： （1）p∧q,其中，p:2是素数，q:5是素数,真值为1； （2）p∧q,其中，p:是无理数，q:自然对数的底e 是无理数,真值为1； （3）p∧┐q,其中，p:2是最小的素数，q:2是最小的自然数,真值为1； （4）p∧q,其中，p:3是素数，q:3是偶数,真值为0； （5）┐p∧┐q,其中，p:4是素数，q:4是偶数,真值为0. 5.将下列命题符号化，并指出真值： （1）p∨q,其中，p:2是偶数，q:3是偶数,真值为1； （2）p∨q,其中，p:2是偶数，q:4是偶数,真值为1； （3）p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0； （4）p∨q,其中，p:3是偶数，q:4是偶数,真值为1； （5）┐p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0； 6.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q ：小丽从筐里拿一个梨； （2）(p∧┐q)∨(┐p∧q),其中，p ：刘晓月选学英语，q ：刘晓月选学日语；. 7.因为p 与q 不能同时为真. 13.设p:今天是星期一，q:明天是星期二，r:明天是星期三： （1）p→q，真值为1（不会出现前件为真，后件为假的情况）； （2）q→p，真值为1（也不会出现前件为真，后件为假的情况）； （3）p q ，真值为1； （4）p→r，若p 为真，则p→r 真值为0，否则，p→r 真值为1. 16 设p 、q 的真值为0；r 、s 的真值为1，求下列各命题公式的真值。 （1）p ∨(q ∧r)? 0∨(0∧1) ? （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是无理数 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 所以公式类型为永真式 //最后一列全为1 （5）公式类型为可满足式（方法如上例）//最后一列至少有一个1 （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