当前位置：文档之家› 离散数学课后习题答案

离散数学课后习题答案

第一章命题逻辑基本概念

课后练习题答案

1.将下列命题符号化，并指出真值：

（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.

2.将下列命题符号化，并指出真值：

（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；

3.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨；

（2）(p∧┐q)∨(┐p∧q),其中，p：刘晓月选学英语，q：刘晓月选学日语；.

4.因为p与q不能同时为真.

5.设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.

第二章命题逻辑等值演算

本章自测答案

5.(1)：∨∨,成真赋值为00、10、11；

(2)：0，矛盾式，无成真赋值；

(3)：∨∨∨∨∨∨∨,重言式，000、001、010、011、100、101、110、111全部为成真赋值；

7.(1)：∨∨∨∨?∧∧；

(2)：∨∨∨?∧∧∧；

8.(1)：1?∨∨∨,重言式；

(2)：∨?∨∨∨∨∨∨；

(3)：∧∧∧∧∧∧∧?0，矛盾式.

11.(1)：∨∨?∧∧∧∧；

(2)：∨∨∨∨∨∨∨?1；

(3)：0?∧∧∧.

12.A?∧∧∧∧?∨∨.

第三章命题逻辑的推理理论

本章自测答案

6.在解本题时，应首先将简单陈述语句符号化，然后写出推理的形式结构*，其次就是判断*是否为重言式，若*是重言式，推理就正确，否则推理就不正确，这里不考虑简单语句之间的内在联系

(1)、(3)、(6)推理正确，其余的均不正确，下面以(1)、(2)为例，证明(1)推理正确，(2)推理不正确

(1)设p:今天是星期一，q:明天是星期三，推理的形式结构为

(p→q)∧p→q(记作*1)

在本推理中，从p与q的内在联系可以知道，p与q的内在联系可以知道，p与q不可能同时为真，但在证明时，不考虑这一点，而只考虑*1是否为重言式.

可以用多种方法（如真值法、等值演算法、主析取式）证明*1为重言式，特别是，不难看出，当取A为p,B为q时，*1为假言推理定律，即(p→q)∧p→q ? q

(2)设p:今天是星期一，q:明天是星期三，推理的形式结构为

(p→q)∧p→q(记作*2)

可以用多种方法证明*2不是重言式，比如，等值演算法、主析取范式（主和取范式法也可以）等

(p→q)∧q→p

?(┐p∨q) ∧q →p

?q →p

?┐p∨┐q

??∨∨

从而可知，*2不是重言式，故推理不正确，注意，虽然这里的p与q同时为真或同时为假，但不考虑内在联系时，*2不是重言式，就认为推理不正确.

9.设p:a是奇数，q:a能被2整除，r:a：是偶数

推理的形式结构为

(p→q┐)∧(r→q)→(r→┐p) (记为*)

可以用多种方法证明*为重言式，下面用等值演算法证明：

(p→┐q)∧(r→q)→(r→┐p)

?(┐p∨┐q) ∨(q∨┐r)→(┐q∨┐r) (使用了交换律)

?(p∨q)∨(┐p∧r)∨┐q∨┐r

?(┐p∨q)∨(┐q∧┐r)

?┐p∨(q∨┐q)∧┐r

10.设p:a,b两数之积为负数，q:a,b两数种恰有一个负数，r：a，b都是负数.

推理的形式结构为

(p→q)∧┐p→(┐q∧┐r)

?(┐p∨q) ∧┐p→(┐q∧┐r)

?┐p→(┐q∧┐r) (使用了吸收律)

?p∨(┐q∧┐r)

?∨∨∨

由于主析取范式中只含有5个W极小项，故推理不正确.

11.略

14.证明的命题序列可不惟一，下面对每一小题各给出一个证明

① p→(q→r)前提引入

② P前提引入

③ q→r①②假言推理

④ q前提引入

⑤ r③④假言推理

⑥ r∨s前提引入

（2）证明：

① ┐(p∧r)前提引入

② ┐q∨┐r①置换

③ r前提引入

④ ┐q ②③析取三段论

⑤ p→q前提引入

⑥ ┐p④⑤拒取式

（3）证明：

① p→q前提引入

② ┐q∨q①置换

③ (┐p∨q)∧(┐p∨p) ②置换

④ ┐p∨(q∧p③置换

⑤ p→(p∨q) ④置换

15.(1)证明：

① S结论否定引入

② S→P前提引入

③ P①②假言推理

④ P→(q→r)前提引入

⑤ q→r③④假言推论

⑥ q前提引入

⑦ r⑤⑥假言推理

（2）证明：

① p附加前提引入

② p∨q①附加

③ (p∨q)→(r∧s)前提引入

④ r∧s②③假言推理

⑤ s④化简

⑥ s∨t⑤附加

⑦ (s∨t)→u前提引入

⑧ u⑥⑦拒取式

16.(1)证明：

① p结论否定引入

② p→ ┐q前提引入

③ ┐q ①②假言推理

④ ┐r∨q前提引入

⑤ ┐r③④析取三段论

⑥ r∧┐s前提引入

⑦ r⑥化简

⑧ ┐r∧r⑤⑦合取

（2）证明：

① ┐(r∨s)结论否定引入

② ┐r∨┐s①置换

③ ┐r②化简

④ ┐s②化简

⑤ p→r前提引入

⑥ ┐p③⑤拒取式

⑦ q→s前提引入

⑧ ┐q④⑦拒取式

⑨ ┐p∧┐q⑥⑧合取

⑩ ┐(p∨q)⑨置换

口p∨q前提引入

⑾①口┐(p∨q) ∧(p∨q) ⑩口合取

17．设p：A到过受害者房间，q: A在11点以前离开，r：A犯谋杀罪，s：看门人看见过A。

前提：(p∧┐q) →r , p ,q →s , ┐s

结论：r

证明：

① q→s 前提引入

② ┐s 前提引入

③ ┐q ①②拒取式

④ p 前提引入

⑤ p∧┐q ③④合取

⑥（p∧┐q）→r 前提引入

⑦ r ⑤⑥假言推理

18．（1）设 p：今天是星期六，q：我们要到颐和园玩，s：颐和园游人太多。

前提：p→(p∨r) , s→┐q , p , s

结论：r

证明：

① s→┐q前提引入

② s前提引入

③ ┐q①②假言推理

④ p前提引入

⑤ p→(q∨r)前提引入

⑥ q∨r④⑤假言推理

⑦r③⑥析取三段论

（2）设p:小王是理科学生，q：小王数学成绩好，r：小王是文科学生。

前提：p→q ,┐r→p ,┐q

结论：r

证明：

① p→q前提引入

② ┐q前提引入

③ ┐p①②拒取式

④ ┐r→p前提引入

⑤ r③④拒取式

第四章 (一阶)谓词逻辑基本概念

本章自测答案

4.(1)┐x(F(x)∧ ┐G(x))?x( F (x) →G (x) ),其中,F(x)：x是有理数,G(x) ：x能表示成分数；

(2)┐x( F (x) →G (x) ) ?x(F(x)∧ ┐G(x)),其中,F (x)：x在北京卖菜,G (x) ：x是外地人；

(3)x( F (x) →G (x) ),其中,F (x)：x是乌鸦,G (x) ：x是黑色的；

(4)xF(x)∧ G(x)),其中,F (x)：x是人,G (x) ：x天天锻炼身体。

因为本题中没有指明个体域,因而使用全总个体域。

5.(1)x y (F(x) ∧ G( y) → H(x,y)),其中,F(x)：x是火车,G(y) ：y是轮船,H(x,y)：x比y快；

(2)x y (F(x) ∧ G( y ) → H(x,y)),其中,F(x)：x是火车,G(y) ：y是汽车,

H(x,y)：x比y快；

(3)┐x(F(x)∧y(G (y) → H (x,y)))?x(F(x) → y(G(y) ∧ ┐H(x,y))),其中,F(x)：x是汽车,G (y) ：y是火车,H(x,y)：x比y快；

(4)┐x(F(x)→y(G(y) → H(x,y)))?x y(F(x)∧G(y)∧┐H(x,y))),其中,F(x)：x是汽车,G(y) ：y是火车,H(x,y)：x比y慢。

6.各命题符号化形式如下：

(1)x y (x ．y = 0)；

(2)x y (x ．y = 0)；

(3)x y (y =x+1)

(4)x y(x ．y = y．x)

(5)x y(x ．y =x+ y)

(6)x y (x + y ＜0 )

9.(1)对任意数的实数x和y,若x ＜y,则x ≠ y；

(2)对任意数的实数x和y,若x–y = 0,则x＜y；

(3)对任意数的实数x和y,若x＜y,则x–y≠0；

(4)对任意数的实数x和y,若x–y ＜0,则x=y.

其中,(1)(3)真值为1(2)与(4)真值为0.

11.(1)、(4)为永真式,(2)、(6)为永假式,(3)、(5)为可满足式。

这里仅对(3)、(4)、(5)给出证明。

(3)取解释I 为：个体域为自然数集合N,F(x,y)：x ≤ y,在下,x y F(x,y)为真,而x y F(x,y)也为真(只需取x =0即可),于是(3)中公式为真,取解释为：个体域仍为自然数集合N,而F(x,y)：x = y。此时,x yF(x,y)为真(取y为x即可),可是x yF(x,y)为假,于是(3)中公式在下为假,这说明(3)中公式为可满足式。

(4)设I为任意一个解释,若在I下,蕴涵式前件xy F(x,y)为假,则

x yF(x,y)→y xF(x,y)为真,若前件x yF(x,y)为真,必存在I的个体域D1中的个体常项x0,使yF(x0,y)为真,并且对于任意

y∈,F(x0,y)为真,由于有x0∈,F(x0,y)为真,所以xF(x,y)为真,又其中y是任意个体变项,所以y xF(x,y )为真,由于I的任意性,所以(4)中公式为永真式(其实,次永真式可用第五章的构造证明法证明之)。

(5)取解释为：个体域为自然数集合,F(x,y)：x = y在下,(5)中公式为真,而将F(x,y)改为F(x,y)：x ＜ y,(5)中公式就为假了,所以它为可满足式。

13．（1）取解释为：个体域为自然数集合N，F（x）：x为奇数，G（x）：x为偶数，在下， x（F（x）∨G（x））为真命题。

取解释为：个体域为整数集合Z，F（x）：x为正整数，G（x）：x为为负整数，在下， x（F（x）∨G（x））为假命题。

（2）与（3）可类似解答。

14．提示：对每个公式分别找个成真的解释，一个成假的解释。

第五章谓词逻辑等值演算与推理

本章自测答案

2.(1) (F(a)∧ F(b)∧ F (c)) ∧ (G (a )∨G (b)∨G (c))

(2) (F(a)∧ F(b)∧ F (c)) ∨ (G (a)∧G (b)∧G (c))

(3) (F(a)∧ F(b)∧ F (c)) → (G (a)∧G (b)∧G (c))

(4) (F(a ,y) ∨ F(b,y)∨ F (c,y)) → (G (a)∨G (b)∨G (c))

5.提示：先消去量词，后求真值，注意，本题3个小题消去量词时，量词的辖域均不能缩小，经过演算真值分别为：1,0,1 .

(1) 的演算如下：

x yF(x,y)

?x (F(x,3)∨F(x,4))

?(F(3,3)∨F(3,4))∧(F(4,3)∨F(4 ,4))

?1∧1?1

6.乙说得对，甲错了。本题中，全称量词的指导变元为x ，辖域为(F (x)→G(x,y)),其中F(x )与G(x,y)中的x都是约束变元，因而不能将量词的辖域缩小。

7.演算的第一步，应用量词辖域收缩与扩张算值式时丢掉了否定联结词“ ┐”。演算的第二步，在原错的基础上又用错了等值式，即

(F(x)∧(G(y)→ H(x,y))) ≠(F(x) ∧G(y)→H (x,y))

12.公式的前束范式不唯一，下面每题各给出一个答案。

(1) x y (F(x)→ G(z,y));

(2) x t (x,y) → G(x,t,z));

(3) x4 ((F(,y) →G(,y))∧(G(,y) →F(x4,y)));

(4) ((F()→G(,)) → (H () → L(,)));

(5) (F(,)→(F() → ┐G (,))).

13.(1)x y(F(x) ∧G(y) ∧H(x ,y)),其中，F(x):x是汽车，G(y)：y是火车，H(x，y)：x比y跑的快；

(2)x y(F(x) ∧G(y)→H(x ,y)),其中，F(x):x是火车，G(y)：y是汽车，H(x，y)：x比y跑的快；

(3)x y(F(x) ∧G(y) ∧┐H(x ,y)),其中，F(x):x是火车，G(y)：y是汽车，H(x，y)：x比y跑的快；

(4)x y(F(x) ∧G(y) → ┐H(x ,y)),其中，F(x):x是飞机，G(y)：y是汽车，H(x，y)：x比y慢；

14.(1)对F(x) → xG(x)不能使用EI规则，它不是前束范式，首先化成前束范式。

F(x) → xG(x) <=> x(F(y)→G(x))

因为量词辖域(F(y)→G(x))中，除x外还有自由出现的y，所以不能使用EI规则。

(2)对x F(x) → y G(y)也应先化成前束范式才能消去量词，其前束范式为x y(F(x) →G(y)),要消去量词，既要使用UI规则，又要使用EI 规则。

(3)在自然推理系统F中EG规则为

A(c)/∴x(x)

其中c为特定的个体常项，这里A(y) = F(y) →G(y)不满足要求。

(4)这里，使F(a)为真的a不一定使G(a)为真，同样地使G(b)为真的b不一定使F(b)为真，如，F(x):x为奇数，G(x):x为偶数，显然F(3)∧G(4)为真，但不存在使F(x)∧G(x)为真的个体。

(5)这里c为个体常项，不能对F(c)→G(c)引入全称量词。

15.(1)证明：①xF(x) 前提引入

②xF(x)→ y((F(y)∨G(y)) →R(y)) 前提引入

③y((F(y)∨G(y)) →R(y) ①②假言推理

④F(c) ①EI

⑤(F(c)∨G(c))→R(c) ③UI

⑥F(c)∨G(c)④附加

⑦R(c) ⑤⑥假言推理

⑧xR(x) ⑦EG

(2)证明①xF(x) 前提引入

②x((F(x)→G(a)∧R(x)))前提引入

③F(c)①EI

④F(c)→G(a)∧R(a)②UI

⑤G(a)∧R(c)③④假言推理

⑥R(c)⑤化简

⑦F(c)∧R(c)③⑥合取

⑧x(F(x)∧R(x))⑦EG

(3)证明：①┐xF(x) 前提引入

②x┐F(x)①置换

③┐F(c)②UI

④x(F(x)∨G(x))前提引入

⑤F(c)∨G(c)④UI

⑥F(c)③⑤析取三段论

⑦xF(x) ⑥EG

(4)证明①x(F(x)∨G(x))前提引入

②F(y)∨G(y)①UI

③x(┐G(x)∨┐R(x))前提引入

④┐G(y)┐R(y)③UI

⑤x R(x) 前提引入

⑥R(y)⑤UI

⑦┐G(y)④⑥析取三段论

⑧F（y）②⑦析取三段论

⑨xF(x) ⑧UG

17．本题不能用附加前提证明法.

20.(1)与(2)均可用附加前提证明法。

22.(1)设F(x)：x为偶数，G(x):x能被2整除。

前提:x(F(x)→G(x))，F(6)

结论：G(6)

(2)设F(x)：x是大学生，G(x):x是勤奋的，a：王晓山。

前提:x(F(x)→G(x))，┐G(a)

结论：┐F(a)

23.(1)设F(x)：x是有理数，G(x):x是实数，H(x)：x是整数。

前提:x( F(x)→G(x))，x(F(x)∧H(x))

结论:x(G(x)∧H(x))

证明提示：先消存在量词。

(2)设F(x)：x是有理数，G(x):x是无理数，H(x)：x是实数，I(x)：x是虚数。

前提:x((F(x)∨G(x)) →H(x))，x( I(x)→┐H(x))

结论:x(I(x)→(┐F(x)∧┐G(x)))

证明①x(I(x)→(┐H(x))前提引入

②I(y)→H(y)①UI

③x((F(x)∨G(x))→H(x))前提引入

④(F(y)∨G(y))→H(y)③UI

⑤┐H(y)→(┐F(y)∧┐G(y))④置换

⑥I(y)→(┐F(y)∧┐G(y))②⑤假言三段论

⑦x(I(x)→(┐F(x)∧┐G(x))⑧UG

24.设F(x)：x喜欢步行，G(x)：x喜欢骑自行车，H(x)：x喜欢乘汽车。

前提:x(┐F(x)→┐G(x))，x(G(x)∨H(x))，x┐H(x)

结论:x┐F(x)

证明①x┐H(x)前提引入

②┐H(c)①UI

③x(G(x)∨H(x))前提引入

④G(c)∨H(c)③UI

⑤G(c)②④析取三段论

⑥x(F(x) →G(x))前提引入

⑦F(c)→┐G(c)⑥UI

⑧┐F(c)⑤⑦拒取式

⑨x┐F(x)⑧UG

25.设F(x)：x是科学工作者，G(x)：x是刻苦钻研的，H(x)：x是聪明的，I(x)：x在事业中获得成功。

前提:x(F(x)→G(x))，x(G(x)∧H(x)→I(x))，a：王大海，F(a)，H(a)

结论：I(a)

证明①F(a)前提引入

②x(F(x)→G(x))前提引入

③F(a)→G(a)②UI

④G(a)①③假言推理

⑤H(a)前提引入

⑥x(G(x)∧H(x)→I(x))前提引入

⑦G(a)∧H(a)→I(a)⑥UI

⑧G(a)∧H(a)④⑤合取

⑨I(a)⑦⑧假言推理

第六章集合代数

本章自测答案

4.(1) ③ (2) ④ (3) ⑤ (4) ⑦ (5) ⑧

6.只有(2)为真，其余为假。

9.(1) {4}；(2) {1,3,5,6}；(3) {2,3,4,5,6}；(4) {, { 1 }}；(5) {{ 4 },{1,4}}.

11.(1)； (2) {1,4,5}.

22.(2)、(3)、(4)、(8)、(10)为真，其余为假。

24.(1)为真，其余为假，因为

(P-Q) = P ? (P-Q)∩Q = P∩Q ?= P∩Q

(2)(3)(4)的反例：P ={1} ，Q ={2}

26.(A–B)∪(B–A) = (A∩B)∪(B∩A)

=(A∪B)∩(B∪B)∩(A∪A)∩(B∪A)

=(A∪B)∩E∩(A∩B)=(A∪B)-(A∩B)

27.(1)(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=(A–B)- C

(3)(A–B-C=A∩B∩ C =A∩C∩B=(A–C)–B

28.(1)A∩(B∪A) = (A∩B)∪(A∩A) =(A∩B)∪

=A∩B=B∩A

(2)((A∪B)∩A) = (A∪B)∪ A

=(A∩B)∪A = A

29.由第26题有(A-B)∪(B-A)=(A∪B)–(A∩B)，故(A-B)∪(B-A)A∪B。假若x∈A∩B，那么x∈A∪B，因此x(A∪B)-(A∩B),与(A-B)∪(B-A) = (A∪B)-(A∩B) = A∪B矛盾.

30.A B?x(x∈A→x∈B)?x(x B→x A)

?x(x∈B→x∈A)?B A

A B ?A∪A A∪B ? E A∪B

而A∪B E，因此A B ?A∪B=E反之，

A∪B = E ? A∩(A∪B)= A ? A∩B = A ? A B

综合上述，A B?A∪B = E

A B ? A-B =? A-B B

反之A-B B ? (A-B)∪B B ? A∪B B ? A∪B = B ? A B

综合上述A B?A-B B

31.任取x ,x∈A ? {x} A=>{x}∈P(A)=>{x}∈P(B)=>{x}B ? x∈B

32.先证C A∧C B ? C A∩B,任取x,x∈C ? x∈C∧x∈C ? x∈A∧x∈B ? x∈A∪B,从而得到C A∪B.再证C A∩B ? C A∧C B，这可以由C A∩B A,C A∩B B得到。

33.P Q ? P-Q=? P-Q P，反之，P-Q P ?P∩(P-Q)P∩P ? P-Q=? P Q

34.令X=，则有∪Y =，即Y = .

35.A B ? A∪A B∪ A ? E B∪A因为E为全集,B∪A E综合上述B∪A=E.

36.由A∩C B∩C,A-C B-C，利用A∪C B∪D有：

(A∩C)∪(A-C) (B∩C)∪(B-C)

? (A∩C)∪(A∩C)(B∩C)∪(B∩C)

? (A∩(C∪C)(B∩(C∪C) ? A∩E B∩E ? A B

37.恒等变形法

B=B∩(B∪A)=B∩(AB)=B∩(AC)

=(B∩A)∪(B∩C)=(A∩C)∪(B∩C)

=(A∪B)∩C=(A∪C)∩C=C

39.任取x，有x∈P(A) ? x A ? x B ? x∈P(B)，因此P(A)P(B).

40.(1)任取x有

x∈P(A)∩P(B)?x∈P(A)∧x∈P(B)?x A∧x B

?x A∩B?x∈P(A∩B)

(2)任取x有

x∈P(A)∪P(B)?x∈P(A)∨x∈P(B)?x A∧x B

? x A∪B?x∈P(A∪B)

注意与(1)的推理不同，上面的推理中有一步是“ ?”符号，而不是“?”符号。

(3)反例如下：A = {1}，B = {2}，则

P(A)∪P(B)= {,{1},{2}}

P(A∪B)={,{1},{2},{1,2}}

第七章二元关系

本章自测答案

3.(1) 任取< x,y >,有

∈(A ∩ B)×(C ∩ D) <=>x∈A ∩ B ∧ y ∈C ∩ D

?x ∈A∧x ∈ B∧y ∈C∧y ∈ D

?(x ∈A∧y ∈C )∧(x∈B∧y∈D)

?∈A×C∧< x,y >∈B×D

?∈(A×C)∩(B×D)

(2)都为假,反例如下:

A ={1},

B ={1,2},

C ={2},

D ={3}

4.(1)为假,反例如下:A ={1}, B =,C = {2};

(2)为真,证明如下:任取有

∈A×(B∩C)×(C∩D)?x∈A∩B∧y∈B∧y∈C

?(x∈A∧y∈B)∧(x∈A∧y∈C)

?∈A×B∧∈A×C?∈(A×B)∩(A×C)

(3)为真,令A = 即可;

(4)为假,反例如下: A =

7.={<2,2>,<3,3 >,<4,4>}

={<2 . 3>,<2,4>,<3,2>,<3,4>,<4,2>,<4,3>}∪I A

L A={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>}

D A={<2,2>,<2,4>,<3,3>,<4,4>}

9.(1){<1,2>,<1,4>,<1,6>,<2,1>,<2,2>,<2,4> <2,6>,<4,1>,<4,2>,<4,4>, <4,6> <6,1>, <6,2>,<6,4> <6,6>}

(2){<1,2>,<2,1>};

(3){<1,1>,<2,1>,<4,1>,<6,1>,<2,2>,<4,2>,<4,4>,<6,6>}

(4){<1,2>,<2,2>,<4,2>,<6,2>}

12.（略）

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

14.R R = {<0,2>,<0,3>,<1,3>}

R= {<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}] = {2,3}

18.(1)F(G∪H) = F G∪F H

任取 ,有

∈F (G∪H)?t(∈F∧∈G∪H)

?t(∈F∧(∈G∨∈H))

?t((∈F∧∈G)∨(∈F∧∈H))

?t(∈F∧∈G)∨t(∈F∧∈H))

?∈F G∨∈F H?∈F G∪F H

(2)和(4)类似可证

19.(2)任取y,有

y∈R[T∪W]?x(x∈T∪W∧∈R)

?x((x∈T∨x∈W)∧∈R

?x((x∈A∧∈R)∨(x∈W∧∈R))

?x(x∈T∧∈R)∨x(x∈W∧∈R)

?y∈R[T]∨y∈R[W]?y∈R[T]∩R[W]

(3)任取,有

∈F(A∩B)?x∈A∩B∈F

?x∈A∧x∈B∧∈F

?(x∈A∧∈F)(x∈B∧∈F)

?∈F A∧∈F B

?∈F A∩F B

20.(1)任取,有

∈(∪) <=>∈∪

?∈∨∈

?∈∪

(2)和(1)类似可证.

21.只有对称性,因为1+1≠10,<1,1>R,R不是自反的,又由于<5,5>∈R,因此R不是反自反的,根据xRy?x+y = 10=>yRx ,可知R是对称的,又由于<1,9>,<9,1>都是属于R,因此R不是反对称的, <1,9>,<9,1>都属于R,如果R是传递的,必有<1,1>属于R.但这是不成立的,因此R也不是传递的.

22.(1)关系图如图7.15所示; (P148)

(2)具有反自反性、反对称性、传递性.

26.(1)R={<3,3>,<3,1>,<3,5>}, = {<3,3>,<3,1>,<3,5>}

(2)r(R)={<1,1>,<1,5>,<2,2>,<2,5>,<3,3>,<3,1>,<4,4>,<4,5>,<5,5>,<6,6>}

s(R)={<1,5>,<5,1>,<2,5>,<5,2>,<3,3>,<3,1>,<1,3>,<4,5>,<5,4>}

T(R)={<1,5>,<2,5>,<3,3>,<3,1>,<3,5>,<4,5>}

31.(1)R = {<2,3>,<3,2>,<2,4>,<4,2>,<3,4>,<4,3>}∪；(2)R； (3)R.

32.(1)不是等价关系，因为<1,1> R，R不是自反的；

(2)不是等价关系，因为R不是传递的，1R3，3R2但是没有1R2；

(3)不是等价关系，因为<2,2> R，R不是自反的；

(4)不是等价关系，因为R不是传递的。

(5)是等价关系。

33．关系图如图7.17说示 (P151)

[a] = [b] ={a,b},[c] = [d] = {c,d}

38.现取x，有x∈A ? ∈R ? ∈R∧∈R

? ∈R∧∈? ∈R∩R

任取,有∈ R∩ ? ∈R∧∈

? ∈∧∈R ? ∈R∩R

任取,,有

∈R∩ ∧∈R∩

? ∈R∧∈∧∈R∧∈

? (∈R∧∈R)∧(∈∧∈

? ∈R∧∈R? ∈R∩R

42.x,x∈A ? ∈R ? ∈R∧∈R ? ∈T,T是自反的。

x,y∈A,∈T?∈R∧∈R

?∈R∧∈R ? ∈T,T是对称的。

x,y,z∈A,∈T∧∈T

?∈R∧∈R∧∈R∧∈R

? ∈R∧∈R∧∈R∧∈R

? ∈R∧∈R ? ∈T

T是传递的。

43．哈斯图如下图所示.

44.(a)偏序集,A={1,2,3,4,5},R={<1,3>,<1,5>,<2,4>,<2,5>,<3,5>,<4,5>}∪

(b)偏序集,A={a,b,c,d,e,f},R={,,}∪

(c)偏序集,A={1,2,3,4,5}, R={<1,2>,<1,4>,<1,5>,<1,3>,<2,4>,<2,5>,<3,4>,<3,5>,<4,5>}∪

45.(a)A={a,b,c,d,e,f,g}, ={,,,,,,, ,,}∪ (b)A = {a,b,c,d,e,f,g},R口 = {,,,,,,}∪

46.哈斯图如图7.19所示（P153）

（1）极大元e,f；极小元a,f；没有最大与最小元。

（2）极大元a,b,d,e；极小元a,b,c,e；没有最大与最小元。

第八章函数

本章自测答案

2. = {,,… }

= {<1,a>,<2,a>}, = {<1,a>,<2,b>}, = {<1,a>,<2,c>}

= {<1,b>,<2,a>}, = {<1,b>,<2,b>}, = {<1,b>,<2,c>}

= {<1,c>,<2,a>}, = {<1,c>,<2,b>}, = {<1,c>,<2,c>}

3.(1)双射，反函数=,f({8}=|8|),({4}={4}；

(2)双射，反函数：R→ R，（x）= logx, ({1}) = {2}, ({1,2}) ={0,1}；

(3)单射，({5}) = {<5,6>}, ({2,3}) = {2}；

(4)单射，({2,3}) = {5,7}, ({1,3}) = {0,1}；

(5)单射，({-1,2}) = {1,2}, ({1}) = {-1,1}；

(6)单射，((0,1)) = (1/4,3/4),([1/4,1/2]) = [0,1/2]；

(8)单射，((0,1)) = (1,+∞),({2,3}) = {1/2,1/3}.

4.(1) 单射 (2) 不单射,也不满射 (3) 不单射,也不满射 (4) 满射 (5) 单射 (6) 不单射，也不满射.

5.(1) 为真，其余都为假.

7.(1) 结果不唯一，={,,,};

(2) 结果不唯一，={,,,}

(3) 不能

(4) 存在单射还书的充要条件是m ≤ n ，存在满射函数的充要条件是m ≥ n,

存在双射函数的充要条件是m = n .

9.双射函数与单射函数都是n!个

10.(1)不是单射，不是满射，也不是双射；

(2){<1,1>,<0,2>,<2,0>};

(3){3,5,7}

17.f g(x)=2x +7, b f(x) =2x +4, f f(x) =x +6, g g(x) =4x +3,

h f(x)=x/2 +3, g h(x) = x +1/2, f h(x) =(x +5)/2 g h f(x) =x +7/2

18.f f(n) =n+2, g f(n)=2n+1, f g(n)=2n+2, g h(n) =0

h g(n)=, h g f(n)=.

19.(1)g f(x)=x+8x +14, f g(x)=x+2

(2)都不是单射，也不是满射和双射。

(3)g和h有反函数，g:R→R,g(x) = x–4; h:R→R,h(x)=

20．

(1)f g:N→N, f g(x)

(2)不是单射，不是满射，也不是双射。

21.(1)单射，假设f() = f()，那么<,+1> = <,+1>。根据有序对相等的条件得=，因此f是单射的，但是f不是满射的，因为<0,0>ran

(2)不存在反函数

(3)ran={｜n∈N}

24.这些函数都是不唯一的，以下只是一个可能的结果。

(1)f = {<1,a>,<2,b>,<3,c>}

(2)f(x) = 2x

(3)f(x) = ｜x｜ - 1

(4)f(x) = e

第九章集合的基数

本章自测答案

1.令:P(A)→2,(T) = Xт, 假如,∈P(A),且≠,那么存在x只属于和之中的一个集合，不妨设x∈∧x,因此∈(),∈()，

于是（）≠（）,从而证明了是单射的，对于任意g∈2,令B={x｜x∈A,g(x) = 1}，则B∈P(A), 且(B)= Xв = g.

2.令:[1,2] →[0,1],(x) = x – 1,则为[1,2]到[0,1]的双射函数.

3.令:A→N,(x) = x/2 , 则为双射函数.

6.提示：根据A ≈ C,B ≈ D，存在双射：A→C,g:B→D,构造函数h：A×B→C×D,h() = <(a),g(b)>容易证明h的双射性。

7.A = {2n｜n∈N},B = {2|k∈N},C=Z

9.(1) 3∪6 = 6, 2∩5 = 2;

(2)4–3 ={3},3⊕1 = {1,2}

(3)∪4 = 3, ∩1 = 0

(4)1×4 = {<0,0>,<0,1>,<0,2>,<0,3>},2= {,,,}，其中:

={<0,0>,<1,0>} = {<0,0>,<1,1>}

={<0,1>,<1,0>} = {<0,1>,<1,1>}

10.(1)3, (2), (3), (4), (5), (6),

第十章代数系统

本章自测答案

3.(1)可以，A = {-1,0,1}.

(2)不可以.

4.(1)封闭 (2)不封闭 (4)加法不封闭，乘法封闭 (5)不封闭 (7)封闭 (9)加法不封闭，乘法封闭

5.(1)没有交换律、结合律，对于一个运算不能考虑分配律；

(3)加法满足交换律、结合律，乘法满足结合律，乘法对加法满足分配律；

(4)乘法满足结合律

(6)加法和乘法都满足交换律、结合律，乘法对加法满足分配律；

6.(1)没有单位元、零元，没有可逆元素。

(3)n阶全0矩阵是加法单位元，也是乘法的零元；n阶单位矩阵是乘法单位元；加法没有零元。任意n阶矩阵M对于加法都是可逆元，起逆元为

– M；只有n阶可逆矩阵(行列式不为0)对乘法是可逆元，其逆元为M .

(4) 乘法单元为n阶单位矩阵，没有零元。每个矩阵M都有逆元M .

(6) 加法单位元0，没有零元，每个元素x都可逆，其逆元是它的相反数– x 。

当n = 1时，乘法有单位元1，只有两个可逆元素：1 = 1, ( - 1) = - 1.

当n＞1时乘法没有单位元和可逆元素。

(7)没有单位元和零元，也没有可逆元素。

(8)乘法单位元为1，只有1是可逆元素，1 = 1

(9)乘法单位元为1，只有1是可逆元素，1 = 1

(10)乘法没有单位元、零元以及可逆元素。

8.(1)不可交换。反例：<0,1> * <1,2> = <0,1>,<1,2> * <0,1> = <0,3>.

可结合，因为 ,,∈Q × Q

( * ) * = *

* ( * ) = *

不是幂等的，因为<1,1> * <1,1> = <1,2>

(2) 容易严整<1,0>为单位元，没有零元，当a≠0 时，的逆元为<1/ a,- b/a>

11.(1)能构成代数系统。满足交换律、结合律、无单位元，零元是1；

(3)能构成代数系统。满足交换律、结合律，单位元是10，零元是1。

15.(1)能 (2)不能 (3)不能 (4)能

第十一章半群与群

本章自测答案

2.(1)构成半群、独异点和群；

(3)构成半群，不构成独异点，也不构成群；

(4)构成半群、独异点和群

5.(1)假设a*b ≠ b*a，那么或者a*b = a , a = b ；或者a*b = b , b*a = a。若为前者，则

(a*b)*a = a*a = b , a*(b*a) = a*b = a

与结合律矛盾，若为后者，有

(a*b)* a = b*a = a ; a*(b*a) = a*a = b

也与结合律矛盾。

(2) 假设b*b = a ，那么或者a*b = b*a = a，或者a*b = b*a = b 。若为前者，则

(b*a)*a = a*a = b ; b*(a*a) = b*b = a

与结合律矛盾，若为后者，有

(b*a)*a = b*a = b ; b*(a*a) = b*b = a

也与结合律矛盾。

7.任取a + bi , c + di∈G , 有

(a + bi)+(c + di)=(a + c)+(b + d)i∈G

任取a + bi , c + di , e + i ∈G ,有

((a + bi)+(c + di))+(e + i)=(a + c)+(b + d)i +(r + i)

= (a + c + e) + (b + d + ) i

同理

(a + bi)+((c + di)+(e + i))=(a + c + e) + (b + d + ) i

单位元是0，a + bi的逆元是– a – bi .

9. 能构成群，运算封闭。x , y , z ∈A , 有

(x y)z = (x + y - 2) z = (x + y - 2) + z – 2 = x + y + z – 4 x (y z) = xо(y + z - 2) = x + (y + z - 2) – 2 = x + y + z – 4 结合律成立，单位元是2，x的逆元是4 – x。

11．设矩阵A=, B=， C=， D=，

(ab)(b a)=a(bb)a=aa=e

(b a)(ab)=b(a a)b=b b=e

因此b a 是ab的逆元，根据逆元唯一性，命题得证.

(4) 当m，n为自然数时任意给顶n，对m进行归纳，a∈G，有

下面对n或m小于0的情况进行验证,不妨设n＜0,m≥0,则n=-t,t＞0

(a)=(a)=((a))=(a)=a=a

其他类似情况可以类似加以验证.

(5)设G为交换群，当n为自然数时对n归纳。

N = 0,(ab)= e = ee = a b

假设(ab)= a b,则

(ab)= (ab)(ab) =(a b)ab = a(b a)b

= a(ab)b = (a a)(b b) = a b 根据归纳法，命题得证.

若n＜0,令n=-m,m＞0 ，那么有

(ab)=(ba)=(ba)=((ba))=(a b)

=(a)(b) =a b=a b

16.若x∈G有x= e,因此x∈G有x= x.x ,y∈G，有

xy = (xy) = y x = yx

17.设a是幕等元，则aa = a,即aa = ae.根据消去律必有a = e.

19.由x=e?|x|=1或2,换句话说。对于G中元素x，如果|x|＞2,必有x≠x，由于|x|=|x|，阶大于2的元素成对出现，共有偶数个，那么剩下的1阶元总共应该是偶数个，1阶元只有1个，就是单位元，从而证明了G中必有的2阶元.

22.a∈N(a),N(a)≠,任取x,y∈N(a),有

ay = ya ? a(ay)a= a(ya)a? ya = a y

(xy)a = x(y a) = x(a y) = x(ya)

= x(ay ) = (xa)y = a(xy )

根据判定定理，N(a)为G的子群。

30.(1)是同态，不是单同态，也不是满同态。() = {-1,1},ker = 2Z;

(2)是同态，不是单同态，也不是满同态。() = {cosx + i·sinx｜x∈Z},ker = {0};

(3)是同态，不是单同态，是满同态，()={cosx + i·sinx｜x∈R}= A,ker ={2kπ｜k∈Z}

31.设：→ ，：→ ，因此:→ ,

x,y∈，有

(xy) =((xy)) =((x)(y))

=((x))((y)) =(x)(x)

因此是到的同态。

32.由于：→ 是双射，因此：→ 也是双射。

x,y∈,a,b∈,使得(a) = x,(b) = y.从而得到

(x)= a,(y) = b

(xy) =((a)(b)) = ((ab)) = ab =(x)(y)

33.设是循环群，a，a∈有

a a=ａ =ａ =ａａ

因此G是Abel群，但是Abel群不一定是循环群，例如KIein四元群是Abel群，但不是循环群。

34.设=,:→ ,y∈(),ａ∈,使得(ａ)=y

y=(ａ)=()=()=((a))

因此(a)是生成元，即()=<(a)>.

35.(1)生成元为a,a,a,a,a,a,a,a

(2)子群为={e},=G,={e,a,a,a,a},={e,a,a},

36.(1)στ=，τσ=，σ=，τ=，στσ=

(2)στ= (1 4 2 3 )，τ = (1 4 2 5 3 )，στσ = (1 5 2 4 3 )

(3)στ = (1 4)(1 2)(1 3)奇置换

τ = (14)(12)(15)(13)偶置换

στσ = (15)(12)(14)(13) 偶置换

（3）是环，不是整环和域，因为乘法没有么元；

（4）不是环，因为正整数关于加法的负元不存在，关于加法不构成群；

（5）不是环，因为关于乘法不封闭。

6.(1) ( - a )( - a) = - - (a a) = 1 , ( - a)( - a ) = - - ( a a ) = 1

因此 - a 是( - a)的逆元，根据逆元的唯一性得( - a) = - a

(2) (b a )(a b) = b (a a) b = 1 , (ab) (b a ) = a (b b ) a = 1

因此b a 是ab的逆元，根据逆元唯一性有(a b) = b a .

离散数学第三版课后习题答案

离散数学辅助教材概念分析结构思想与推理证明第一部分集合论

离散数学习题解答习题一（第一章集合） 1. 列出下述集合的全部元素： 1）A={x | x ∈N∧x是偶数∧x＜15} 2）B={x|x∈N∧4+x=3} 3）C={x|x是十进制的数字} [解] 1）A={2，4，6，8，10，12，14} 2）B= 3）C={0，1，2，3，4，5，6，7，8，9} 2. 用谓词法表示下列集合： 1）{奇整数集合} 2）{小于7的非负整数集合} 3）{3，5，7，11，13，17，19，23，29} [解] 1）{n n∈I∧(?m∈I)(n=2m+1)}； 2）{n n∈I∧n≥0∧n<7}； 3）{p p∈N∧p>2∧p<30∧?(?d∈N)(d≠1∧d≠p∧(?k∈N)(p=k?d))}。 3. 确定下列各命题的真假性： 1） 2）∈ 3）{} 4）∈{} 5）{a，b}{a，b，c，{a，b，c}} 6）{a,b}∈(a，b，c，{a，b，c}) 7）{a，b}{a，b，{{a，b，}}} 8）{a，b}∈{a，b，{{a，b，}}} [解]1）真。因为空集是任意集合的子集； 2）假。因为空集不含任何元素； 3）真。因为空集是任意集合的子集； 4）真。因为是集合{}的元素； 5）真。因为{a，b}是集合{a，b，c，{a，b，c}}的子集； 6）假。因为{a,b}不是集合{a，b，c，{a，b，c}}的元素；

7）真。因为{a，b}是集合{a，b，{{a，b}}}的子集； 8）假。因为{a,b}不是集合{a，b，{{a，b}}}的元素。 4. 对任意集合A，B，C，确定下列命题的真假性： 1）如果A∈B∧B∈C，则A∈C。 2）如果A∈B∧B∈C，则A∈C。 3）如果A B∧B∈C，则A∈C。 [解] 1）假。例如A={a}，B={a，b}，C={{a}，{b}}，从而A∈B∧B∈C但A∈C。 2）假。例如A={a}，B={a，{a}}，C={{a}，{{a}}}，从而A∈B∧B∈C，但、A ∈C。 3）假。例如A={a}，B={a，b}，C={{a}，a，b}，从而ACB∧B∈．C，但A∈C。5．对任意集合A，B，C，确定下列命题的真假性： 1）如果A∈B∧B C，则A∈C。 2）如果A∈B∧B C，则A C。 3）如果A B∧B∈C，则A∈C。 3）如果A B∧B∈C，则A C。 [解] 1）真。因为B C x（x∈B x∈C），因此A∈B A∈C。 2）假。例如A={a}，B={{a}，{b}}，C={{a}，{b}，{c}}从而A∈B∧B C，但A C。 3）假。例如A={a}，B={{a，b}}，C={{a，{a，b}}，从而A B∧B∈C，但A C。 4）假。例如A={a}，B={{a，b}}，C={{a，b}，b}，从而A B∧B∈C，但A C。 6．求下列集合的幂集： 1）{a，b，c} 2）{a，{b，c}} 3）{} 4）{，{}} 5）{{a，b}，{a，a，b}，{a，b，a，b}} [解] 1）{，{a}，{b}，{c}，{a，b}，{a，c}，{b，c}，{a，b，c}} 2）{，{a}，{{b，c}}，{a，{a，b}}} 3）{，{}} 4）{，{}，{{}}，{，{}}}

离散数学课后习题答案

习题参考解答习题 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 ）

离散数学习题解答

（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）这学期，刘晓月只能选学英语或日语中的一门外语课. 答：p ：刘晓月选学英语，q ：刘晓月选学日语，符号化为: ()()p q p q ?∧∨∧?. 7.设p ：王冬生于1971年，q ：王冬生于1972年，说明命题“王冬生于1971年或1972年”既可以化答:列出两种符号化的真值表：

屈婉玲版离散数学课后习题答案【1】

第一章部分课后习题参考答案 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）解：

离散数学课后答案

离散数学课后答案习题一 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章习题解答 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

离散数学答案屈婉玲版第二版高等教育出版社课后答案

离散数学答案屈婉玲版第二版高等教育出版社课后答案第一章部分课后习题参考答案 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.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 是素数, 这是不对的”是不对的.

离散数学习题详细答案

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

离散数学课后习题答案_(左孝

证明设A 上定义的二元关系R 为：＜＜x,y ＞, ＜u,v ＞＞∈R ?x y =u v ① 对任意＜x,y ＞∈A ，因为x y =x y ，所以＜＜x,y ＞, ＜x,y ＞＞∈R 即R 是自反的。 ② 设＜x,y ＞∈A ，＜u,v ＞∈A ，若＜＜x,y ＞, ＜u,v ＞＞∈R ?x y =u v ?u v =x y ?＜＜u,v ＞,＜x,y ＞＞∈R 即R 是对称的。 ③ 设任意＜x,y ＞∈A ，＜u,v ＞∈A ，＜w,s ＞∈A ，对＜＜x,y ＞, ＜u,v ＞＞∈R ∧＜＜u,v ＞, ＜w,s ＞＞∈R ?（x y =u v ）∧（u v =w s ）?x y =w s ?＜＜x,y ＞, ＜w,s ＞＞∈R 故R 是传递的，于是R 是A 上的等价关系。

3-10.6 设R是集合A 上的对称和传递关系，证明如果对于A中的每一个元素a,在A中同时也存在b，使在R之中，则R是一个等价关系。证明对任意a∈A，必存在一个b∈A，使得＜a,b＞∈R. 因为R是传递的和对称的，故有：＜a,b＞∈R∧＜b, c＞∈R?＜a, c＞∈R?＜c,a＞∈R 由＜a,c＞∈R∧＜c, a＞∈R?＜a,a＞∈R 所以R在A上是自反的，即R是A上的等价关系。 3-10.7 设R1和R2是非空集合A上的等价关系，试确定下述各式，哪些是A上的等价关系，对不是的式子，提供反例证明。a）（A×A）-R1； b）R1-R2； c）R12； d) r（R1-R2）（即R1-R2的自反闭包）。解 a）（A×A）-R1不是A上等价关系。例如： A={a,b}，R1={＜a,a＞，＜b,b＞}

离散数学课后习题答案二

习题3.7 1. 列出关系}6|{=???∈><+ d c b a d c b a d c b a 且，，，，，，Z 中所有有序4元组。解 }6|{=???∈><+ d c b a d c b a d c b a 且，，，，，，Z ,2,1,3,1,3,1,2,1,2,3,1,1,3,2,1,1,1,1,1,6,1,1,6,1,1,6,1,1,6,1,1,1{><><><><><><><><= ><><><><><><><><2,1,1,3,3,1,1,2,1,2,1,3,1,3,1,2,1,1,2,3,1,1,3,2,1,2,3,1,1,3,2,1 2. 列出二维表 3.18所表示的多元关系中所有5元组。假设不增加新的5元组，找出二维表3.18所有的主键码。表3.18 航班信息航空公司航班登机口目的地起飞时间 Nadir 112 34 底特律 08:10 Acme 221 22 丹佛 08:17 Acme 122 33 安克雷奇 08:22 Acme 323 34 檀香山 08:30 Nadir 199 13 底特律 08:47 Acme 222 22 丹佛 09:10 Nadir 322 34 底特律 09:44 解略 3. 当施用投影运算5,3,2π到有序5元组>

离散数学课后习题答案

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

屈婉玲版离散数学课后习题答案

第四章部分课后习题参考答案 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→ ((y ( )) ( H ) x , ( (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y 快命题符号化为: ))) x F x y y→ ?? ∧ ? H G ) ( , 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

离散数学(左孝凌)课后习题解答(详细)

离散数学~ 习题1.1 1.下列句子中，哪些是命题？哪些不是命题？如果是命题，指出它的真值。 ⑴中国有四大发明。 ⑵计算机有空吗? ⑶不存在最大素数。 ⑷21+3＜5。 ⑸老王是山东人或河北人。 ⑹2与3都是偶数。 ⑺小李在宿舍里。 ⑻这朵玫瑰花多美丽呀! ⑼请勿随地吐痰! ⑽圆的面积等于半径的平方乘以。 ⑾只有6是偶数，3才能是2的倍数。 ⑿雪是黑色的当且仅当太阳从东方升起。 ⒀如果天下大雨，他就乘班车上班。解：⑴⑶⑷⑸⑹⑺⑽⑾⑿⒀是命题，其中⑴⑶⑽⑾是真命题，⑷⑹⑿是假命题，⑸⑺⒀的真值目前无法确定；⑵⑻⑼不是命题。 2. 将下列复合命题分成若干原子命题。 ⑴李辛与李末是兄弟。 ⑵因为天气冷，所以我穿了羽绒服。 ⑶天正在下雨或湿度很高。 ⑷刘英与李进上山。 ⑸王强与刘威都学过法语。 ⑹如果你不看电影，那么我也不看电影。 ⑺我既不看电视也不外出，我在睡觉。 ⑻除非天下大雨，否则他不乘班车上班。解：⑴本命题为原子命题； ⑵p：天气冷；q：我穿羽绒服； ⑶p：天在下雨；q：湿度很高； ⑷p：刘英上山；q：李进上山； ⑸p：王强学过法语；q：刘威学过法语； ⑹p：你看电影；q：我看电影； ⑺p：我看电视；q：我外出；r：我睡觉； ⑻p：天下大雨；q：他乘班车上班。