当前位置：文档之家 › (完整版)洪帆《离散数学基础》(第三版)课后习题答案

(完整版)洪帆《离散数学基础》(第三版)课后习题答案

  • 格式：doc
  • 大小：3.66 MB
  • 文档页数：71

1

第1章 集合

1、列举下列集合的元素

(1) 小于20的素数的集合

(2) 小于5的非负整数的集合

(3) 2{|,10240515}iiIiii且

答：(1) {1,3,5,7,11,13,17,19}

(2) {0,1,2,3,4}

(3) {5,6,7,8,9,10,11}

2、用描述法表示下列集合

(1) 12345{,,,,}aaaaa

答：{|,15}iaiIi

(2) {2,4,8,}L

答：{2|}iiN

(3) {0,2,4,100}L

答：{2|,050}iiZi

3、下面哪些式子是错误的？

(1) {}{{}}aa 答：正确

(2) {}{{}}aa 答：错误

(3) {}{{},}aaa 答：正确

(4) {}{{},}aaa 答：正确

4、已给{2,,{3},4}Sa和{{},3,4,1}Ra，指出下面哪些论断是正确的？哪些是错误的？

(1) {}aS 错误 2

(2) {}aR 正确

(3) {,4,{3}}aS 正确

(4) {{},1,3,4}aR 正确

(5)RS 错误

(6) {}aS 正确

(7) {}aR错误

(8) R正确

(9) {{}}aR 正确

(10) {}S错误

(11) R错误

(12) {{3},4}正确

5、 列举出集合,,ABC的例子，使其满足AB，BC且AC

答：{}Aa，{{}}Ba，显然AB，{{{}}}Ca，显然BC，但是AC。

6、 给出下列集合的幂集

(1) {,{}}ab

答：幂集{,{},{{}},{,{}}abab

(2) {,,{}}aa

答：幂集{,{},{},{{}},{,},{,{}},{,{}},{,,{}}}aaaaaaaa

7、设{}Aa，给出A和2A的幂集

答：2{,{}}Aa 22{,{{}},{{}},{,{}}}Aaa

8、 设128{,,,}AaaaL由17B和31B所表示的A的子集各是什么？应如何表示子集2,67{,}aaa和13{,}aa

答：170001000148{,}BBaa 3

310001111145678{,,,,}BBaaaaa

2,670100011070{,}aaaBB，1310100000160{,}aaBB

9、 设{1,2,3,4,5}U，{1,4}A，{1,2,5}B，{2,4}C，确定集合：

(1) AB (2) ()ABC (3) ()ABC (4)()()ABAC

(5) ()AB (6) AB (7) ()BC (8)BC (9) 22AC (10)22AC

答：(1) {3,4}B，{4}AB

(2) {1}AB，{1,3,5}C，(){1,3,5}ABC

(3) {2}BC，(){1,2,4}ABC

(4) {1,2,4,5}AB，{1,2,4}AC，()(){1,2,4}ABAC

(5) (){2,3,4,5}AB (6) {2,3,5}A，{2,3,4,5}AB

(7) {1,2,4,5}BC，(){3}BC

(8) {3,4}B，{1,3,5}C，{3}BC

(9) 2{,{1},{4},{1,4}}A，2{,{2},{4}{24}}C，，，22{{1},{1,4}}AC

(10) 22{,{4}}AC

10、 给定自然数集N的下列子集：

{1,2,7,8}A，2{|50}Bii，{|330}Ciii可被整数，0

{|2,,06}kDiikZk

求下列集合：

(1) (())ABCD

答：{1,2,3,4,5,6,7}B，

{0,3,6,9,12,15,18,21,24,27,30}C，{1,2,4,8,16,32,64}D

(()){0,1,2,3,4,5,6,7,8,9,12,15,16,18,21,24,27,30,32,64}ABCD

(2) (())ABCD 4

(3) ()BAC

解：{0,1,2,3,6,7,8,9,12,15,18,21,24,27,30}AC，(){4,5}BAC

(4) ()ABD

解：{3,4,5,6}ABBA，(){1,2,3,4,5,6,8,16,32,64}ABD

11、 给定自然数集N的下列子集

{|12}Ann，{|8}Bnn，{|2,}CnnkkN，{|3,}DnnkkN

{|21,}EnnkkN

将下列集合表示为由,,,,ABCDE产生的集合：

(1) {2,4,6,8} (2){3,6,9} (3){10} (4){|369}nnnn或或

(5) {|109}nnnnn是偶数且或是奇数且

(6) {|6}nn是的倍数

答：{1,2,3,4,5,6,7,8,9,10,11}A，{1,2,3,4,5,6,7,8}B

{2,4,6,8,}CL，{3,6,9,12,}DL，{1,3,5,7,}EL

{2,4,6,8}BC

{3,6,9}=AD

{10}=(())ABDE

(4){|369}nnnn或或{3}{6}{9,10,11,12,}L

{3,6,9,10,11,12,}()ADBL

(5) {2,4,6,8,10,11,13,15,}(()())(())AEEBADBL

(6) {|6}{6,12,18,24,30}nnL是的倍数CD

12、 判断以下哪些论断是正确的，哪些论断是错误的，并说明理由。

(1) 若aA，则aAB 5

答：正确，根据集合并的定义

(2) 若aA，则aAB

答：显然不正确，因为根据集合交运算的定义，必须a同时属于A和B

(3) 若aAB，则aB

答：正确

(4) 若AB，则ABB

答：错误

(5) 若AB，则ABA

答：正确

(6) 若aA，则aAB

答：错误

(7) 若aA，则aAB

答：正确

13、 设,,ABC是任意的集合，下述论断哪些是正确的？哪些是错误的？说明理由

(1) 若ABAC，则BC

答：不正确，反例，设A，则不论,BC是什么集合，都有ABAC，但显然,BC不一定相等。

(2) 当且仅当ABB，有AB；

答：正确，证明如下：若ABB，则对aA，有aABB，则有aB，因此有AB。反之，若AB，则ABB显然成立。

(3) 当且仅当ABA，有AB

答：正确，证明如下：若ABA，则对aA，因此aAB，则aB，则有AB。若AB，则aA，有aB，因此由aA，可以得出aAB，因此AAB，又ABA，有ABA。

6

(4) 当且仅当AC，有()ABC

答：不正确，因为()ABCABC，因此不一定需要满足AC，而若AB也可以满足。例如：{,,}Aabc，{,}Bde，{,}Cab，()ABC成立，而AC不成立。

(5) 当且仅当BC，有()ABCA

答：不正确，因为若BC，有()ABCA成立，但是反之不成立，反例如下:{1,2,3,4,5}A，{1,6}B，{1,2}C，而{2,3,4,5}AB，(){1,2,3,4,5}ABC，但是BC不成立。

14、 设,,,ABCD是集合，下述哪些论断是正确的？哪些是错误的？说明理由。

(1) 若,ABCD，则()ACBD

答：正确，证明：对aAC，则aA或aC，因为,ABCD，因此aB或aD，因此aBD，即()ACBD成立。

(2) 若,ABCD，则()ACBD

答：正确

(3)若AB，CD，则()ACBD

答：正确

(4) 若,ABCD，则()ACBD

答：不正确。例如若,ABCD，但是AC，BD，则()ACBD。

15、 设,AB是两个集合，问：

(1)如果ABB，那么A和B有什么关系？

答：因为ABB，而ABABB，即对aB有,aAaB，因此7

AB。

(2) 如果ABBA，那么A和B有什么关系？

答：充要条件是AB。证明：因为ABBA的()()ABABAA，从而有AAB，即AB，同理可证明BA，因此AB。

16、 设,AB是任意集合，下述论断哪些是正确的？哪些是错误的？说明理由。

(1) 222ABAB

答：不正确。例如{,}Aab，{,}Bbc，则{,,}ABabc

2{,{},{},{},{,},{,},{,},{,,}}ABabcabacbcabc

2{,{},{},{,}}Aabab，2{,{},{},{,}}Bbcbc

显然222ABAB不成立。

(2) 222ABAB

答：成立。证明：对22ABC，则2AC且2BC，则,CACB，则CAB，因此2ABC。反之，若2ABC，则CAB，则CA且CB，因此2AC，且2BC，因此22ABC，即222ABAB。

(3) 2(2)AA

答：显然不成立，因为左边集合肯定含有，而右边不含有。

17、 在一个班级的50个学生中，有26人在离散数学的考试中取得了优秀的成绩；21人在程序设计的考试中取得了优秀的成绩。假如有17人在两次考试中都没有取得优秀成绩，问有多少人在两次考试中都取得了优秀成绩?

答：分别用,AB表示在离散和程序设计的考试中取得优秀成绩的学生集合，U表示全体学生集合：则#()26A，#()21B，#()501733AB，则两次考试中都取得了优秀成绩的学生人数为26+21-33=14人。

18、 设,,ABC是任意集合，运用成员表证明：

(1) ()()()()ABACACAB

证明：

合集下载

离散数学课后习题答案(最新)

离散数学课后习题答案(最新)

最新精品推荐

最新精品推荐 习题参考解答

习题1.1

1、（3）P：银行利率降低

Q：股价没有上升

P∧Q

（5） P：他今天乘火车去了北京

Q：他随旅行团去了九寨沟

QP

（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

1（3）

)()()()()()(RPQPRPQPRQPRQP

（4）

()()()(())()(()())(())()()()()PQQRRPPRQRPPRRPQRPPRPRQRQP右

2、不， 不， 能

习题 1.4

1(3) (())~((~))(~)()~(~(~))(~~)(~)PRQPPRQPPRTPRPRQQPRQPRQ、

主合取范式

)()()()()()()()()()()()()()())(())(()()(())()())(()((QPRPQRPQRRQPRQPRQPQPRQPRPQRPQRRQPRQPRQPRQPQQPRPPQRRRQQPPRQRPPQRPPQRP

离散数学第8,9章课后习题答案

离散数学第8,9章课后习题答案

第8章 习题参考答案

1. 在一次10周年同学聚会上，想统计所有人握手的次数之和，应该如何建立该问题的图论模型？

解：将每个同学分别作为一个节点，如果两个人握过一次手就在相应的两个节点之间画一条无向边，于是得到一个无向图。一个人握手的次数就是这个节点与其他节点所连接的边的条数，进而可得出所有人握手的次数之和。

2. 在一个地方有3户人家，并且有3口井供他们使用。由于土质和气候的关系，有些井中的水常常干枯，因此各户人家要到有水的井去打水。不久，这3户人家成了冤家，于是决定各自修一条路通往水井，打算使得他们在去水井的路上不会相遇。试建立解决此问题的图论模型。

解：将3户人家分别看做3个节点且将3口井分别看做另外3个节点，若1户人家与1口井之间有一条路，则在该户人家与该口井对应的节点之间连一条无向边，这样就得到一个无向图。

3. 某人挑一担菜并带一条狼和一只羊要从河的一岸到对岸去。由于船太小，只能带狼、菜、羊中的一种过河。由于明显的原因，当人不在场时，狼要吃羊，羊要吃菜。通过建立图论模型给出问题答案。

解：不妨认为从北岸到南岸，则在北岸可能出现的状态为24=16种，其中安全状态有下面10种：（人，狼，羊，菜），（人，狼，羊），（人，狼，菜），（人，羊，菜），（Φ），（人，羊），（菜），（羊），（狼），（狼，菜）；不安全的状态有下面6种：（人）（人，菜）（人，狼）（狼，羊，菜）（狼，羊）（羊，菜）。

线将北岸的10种安全状态看做10个节点，而渡河的过程则是状态之间的转移，这样就得到一个无向图，如图8-1所示。

图8-1

从上述无向图可以得出安全的渡河方案有两种：

第1种：（人，狼，羊，菜）→（狼，菜）→（人，狼，菜）→（狼）→（人，狼，羊）→（羊）→（人，羊）→（Φ）。 (人，狼，羊，菜)

(人，狼，羊)

(人，狼，菜)

(人，羊，菜)

(人，羊) (狼，菜)

(羊)

(狼)

(菜)

(Φ) 第2中：（人，狼，羊，菜）→（狼，菜）→（人，狼，菜）→（菜）→（人，羊，菜）→（羊）→（人，羊）→（Φ）。

离散数学习题与参考答案

离散数学习题与参考答案

习题二 谓词逻辑

一、 选择题

1、 下列哪个式子不是谓词演算的合式公式( )

A. (x)(A(x,2)∧B(y)) B. (x)(A(x)∧B(x,y))

C. ((x)∧(y))→(A(x,y)∧B(x,y)) D. (x)(A(x)→B(y))

2、设个体域是整数集，则下列命题的真值为真的是（ ）

A.xy (xy=1) B. xy(x+y=y)

C.xy(x+y=x) D. xy(y=2x)

3、设B是不含变元x的公式，谓词公式(x)(A(x)→B)等价于( )

A.(x)A(x)→B B. (x)A(x)→B C. A(x)→B D.(x)A(x)→(x)B

4、谓词公式(x)(P(x)∨(y)R(y))→Q(x)中的x( ).

A.只是约束变元

B.只是自由变元

C.既非约束变元又非自由变元

D.既是约束变元又是自由变元

5、谓词公式(x)P(x,y)∧(x)(Q(x,z)→(x)(y)R(x,y,z))中量词x的辖域是（ ）.

A．(x)Q(x,z)→(x)(y)R(x,y,z))

B．Q(x,z)→(y)R(x,y,z)

C．Q(x,z)→(x)(y)R(x,y,z)

D．Q(x,z)

6、在论域D={a,b}中与公式（）A（x）等价的不含存在量词的公式是（ ）

A. B.

C. D.

7、设M（x）：x是人；F（x）：x要吃饭.用谓词公式表达下述命题：所有的人都要吃饭，其中错误的表达式是（ ）.

A． B．

C． D．

8、设个体域A={a,b}，公式xP(x)∧xS(x)在A中消去量词后应为（ ）.

A．P(x)∧S(x) B．P(a)∧P(b)∧(S(a)∨S(b))

C．P(a)∧S(b) D．P(a)∧P(b)∧S(a)∨S(b)

离散数学第10章习题答案

离散数学第10章习题答案

第10章 图

1 第10章习题答案

1.解 (1)设G有m条边，由握手定理得2m＝Vvvd)(＝2＋2＋3＋3＋4＝14，所以G的边数7条。

(2)由于这两个序列中有奇数个是奇数，由握手定理的推论知，它们都不能成为图的度数列。

(3) 由握手定理得Vvvd)(＝2m＝24，度数为3的结点有6个占去18度，还有6度由其它结点占有，其余结点的度数可为0、1、2，当均为2时所用结点数最少，所以应由3个结点占有这6度，即图G中至多有9个结点。

2.证明 设1v、2v、…、nv表示任给的n个人，以1v、2v、…、nv为结点，当且仅当两人为朋友时其对应的结点之间连一条边，这样得到一个简单图G。由握手定理知nkkvd1)(＝3n必为偶数，从而n必为偶数。

3. 解 由于非负整数列d＝(d1，d2，…，dn)是可图化的当且仅当niid1≡0(mod 2)，所以(1)、(2)、(3)、(5)能构成无向图的度数列。

(1)、(2)、(3)是可简单图化的。其对应的无向简单图如图所示。

(5)是不可简单图化的。若不然，存在无向图G以为1，3，3，3度数列，不妨设G中结点为1v、2v、3v、4v，且d(1v)＝1，d(2v)＝d(3v)＝d(4v)＝3。而1v只能与2v、3v、4v之一相邻，设1v与2v相邻，于是d(3v)＝d(4v)＝3不成立，矛盾。

4.证明 因为两图中都有4个3度结点，左图中每个3度结点均与2个2度结点邻接，而右图中每个3度结点均只与1个2度结点邻接，所以这两个无向图是不同构的。

5. 解 具有三个结点的所有非同构的简单有向图共16个，如图所示，其中(8)(16)为其生成子图。

6. 解 (1)G的所有子图如图所示。 (1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)(15)(16)第10章 图

2 (2)图(8)(18)是G的所有生成子图。