离散数学习题

《离散数学》习题

命题逻辑： 1. 命题符号化：

1) 小张不仅能吃苦，而且很能干。 2) 吃一堑长一智。

3) 除非小明努力学习，否则他就不能取得好成绩。 2. 当P、Q的值为0，R、S的值为1时求下列公式的值。 1) （P∨(Q∧ R)）→（R∨S） 2) （P?R)∧(?Q∨S）

3. 列出命题公式(P→(Q→R))→((P→Q)→(P→R))的真值表 4. 证明：(P?Q)∧(Q?R)?P?R

5. 求解((P∨Q)∧ ?(? P∧ (? Q ∨? R) ) ) ∨ (? P ∧ ? Q ) ∨ (? P ∧ ?R ) 的公式类型？ （永真、永假、可满足？）

6. 试将P→Q化成与之等值的并仅含联结词?的公式. 7. 试将(P→Q)→R化成与之等值的并仅含{?，∧}的公式.

8. 试用推理方式求解(P∧Q)∨(?P∧R)的主合取范式，并根据其主合取范式写出其对应的主析取范式。 9. 列出公式(P∧(Q?R))∨?(P∨Q∨R)的真值表，根据真值表写出其对应的主合取范式和主析取范式。 10. 用演绎法证明

前提：P→(Q→S) ，R?P，Q 结论:：R→S 11. 运用CP规则证明

前提：P→(Q→S) ，R?P，Q 结论:：R→S

12. 用归结法证明下面推理： 前提：P→(Q→S) ，R?P，Q 结论:：R→S

13. 在形式系统L中证明：?B→(B→A). 谓词逻辑： 1. 谓词符号化：

1) 所有的鱼都生活在水中。 2) 没有大于2的偶素数。 3) 并不是每个人都聪明。

2. 设个体域D={a,b}，将一阶公式(?x)(F(x)→(?y)G(y))中的量词消除

3. 设个体域为整数集，令P(x,y)：x+y=1；Q(x,y)：xy>0，试求解下列命题的真假。

1) (?x) (?y)P(x,y). 2) (?x) (?y)Q(x,y). 4. 求前束范式：

1) (?x)F(x)?(?x)R(x).

2) ((?x)P(x)∨(?y)Q(y))?(?x)R(x). 5. 证明：

前提：(?x)(A(x) ?B(x)∧C(x))，(?x)(A(x)∧D(x)) 结论：(?x)(C(x)∧D(x))

6. 所有的整数均为有理数并且为实数，存在是整数又是奇数的数，因而存在是奇数又是实数的数。

写出上面推理的证明。(用谓词逻辑，写出用谓词表示的前提、结论和证明过程)

集合论：

1. A?B，A∈B能否同时成立，说明原因 2. 求集合A＝{a，{a}}的幂集 3. 证明：若B?C，则P(B)? P(C) 4. 如果A∪B=A∪C，是否有B=C？ 如果A⊕B=A⊕C，是否有B=C？

5. 试求1到10000之间不能被4，5或6整除的整数个数.

6. 列出所有从A={a,b,c}到B={s}的关系，并指出恒等关系和全域关系.

7. 给出A上的关系及其关系图和矩阵表示.{|0≤x-y＜3} A={0，1，2，3，4} 8. 已知S={a,b}. R? ={〈x,y〉|x,y∈A∧x?y∧A为集合族ρ(S)}.试写出关系R?. 9. 已知： A={a,b,c}, R={〈a,b〉,〈a,c〉,〈b,c〉}该关系具有什么性质？ (自反，反自反，对称，反对称，传递性)

10. 设A={a,b,c},R={〈a,b〉,〈a,c〉} 计算：r(R)，sr(R)，tr(R)，str(R). 11. 设A是含有4个元素的集合，试求： (1)在A上可以定义多少种对称关系？

(2)在A上可以定义多少种既是自反的，又是对称的关系？

(3)在A上可以定义多少种既不是自反的，也不是反自反的二元关系？

12. 设集合A={0，1，2，3，4}. R={|x+y=4,x,y∈A} ，R={|y-x=1,x,y∈A}. 试求：R?S，R?R，(R?S)?R，R?(S?R). 13. 证明：R是A上的传递关系?R?R?R.

14. A={1,2,3,4,5},R={|x,y∈A∧x-y可被2整除}，试问R是否是A上的等价关系？如果是，求出R的各等价类. 15. A={1,2,3,4,5},A上的划分∏={{1,2},{3,4},{5}}，给出由∏所诱导出的A上的等价关系R的集合表达式. 16. 试给出一个单射但非满射的函数.(对某一集合而言) 17. 设f：N→N×N，f(n)=,则： (1)说明f是否为单射和满射，并说明理由. (2) f的反函数是否存在？并说明理由. (3)求ranf.

18. 已知如果从无限集合A到集合B存在单射f，则B也是无限集合。

设X是无限集合，集合Y≠φ，证明：X与Y的笛卡儿积X×Y是无限集合。 代数系统：

1. 以下集合和运算是否构成代数系统？如果构成，说明该系统是否满足结合律、交换律？求出该运算的幺元、零元和所有可逆元素的逆元.

1) P(B)关于对称差运算⊕，其中P(B)为幂集. 2) A={a,b,c}，*运算如下表所示：

2. 设集合A={a,b}，那么（1）在A上可以定义多少不同的二元运算？（2）在A上可以定义多少不同的具有交换律的二元运算？

3. 设A={1,2},B是A上的等价关系的集合. 1) 列出B的元素.

2) 给出代数系统V=的运算表.

3) 求出V的幺元、零元和所有可逆元素的逆元. 4) 说明V是否为半群、独异点和群？

4. 设A={a,b,c}，构造A上的二元运算*，使得a*b=c,c*b=b，且*运算满足幂等律、交换律. 1) 给出关于*运算的一个运算表. 2) *运算是否满足结合律，为什么？. 5. 设是一个代数系统。

*是R上的一个二元运算，使得对于R(实数集合)中的任意元素a,b都有a*b=a+b+a·b(·和+为数集上的乘法和加法). 证明：: 是独异点. 6. 如果是半群，且*是可交换的.

证明：如果S中有元素a,b,使得a*a=a和b*b=b，则(a*b)*(a*b)=a*b.

7. 设是一个群,则?a,b,c∈S。 试证明： 群G中具有消去律,即成立: 如果a·b=a·c ,b·a=c·a 那么b=c. 8. 求循环群的所有生成元和子群. 9. 设是群，a∈G .

现定义一种新的二元运算⊙：x⊙y=x*a*y，?x,y∈G . 证明：也是群 .

10. 试写出模6加法群的每个子群及其相应的左陪集. 11. 试aH和bH是子群H在G中的两个左陪集. 证明：aH=bH或aH∩bH=?. 12. 试写出群和环的定义. 13. 证明偏序集与格的等价。 14. 设A={1,2,5,10,11,22,55,110}.

1) A关于整除关系是否构成偏序集？ 2) 如果构成偏序集合，画出其对应的哈斯图.

3) 如果构成偏序集，该偏序集合构成哪种格？ (分配格、有界格、有补格、布尔格). 图论：

1. 已知无向图G有12条边，6个3度顶点，其余顶点的度数均小于3，问G至少有几个顶点？并画出满足条件的一个图形. 2. 是否存在7阶无向简单图G，其度序列为1、3、3、4、6、6、7.给出相应证明.

3. 设d1、d2、…、dn为n个互不相同的正整数. 证明：不存在以d1、d2、…、dn为度序列的无向简单图. 4. 求下图的补图.

5.

1) 试画一个具有5个顶点的自补图

2) 是否存在具有6个顶点的自补图，试说明理由。

6. 设图G为n(n>2且为奇数)阶无向简单图，证明：G与G的补图中奇度顶点个数相等. 7. 无向图G中只有2个奇度顶点u和v，u与v是否一定连通.给出说明或证明。 8. 图G如下图所示：

1) 写出上图的一个生成子图. 2) δ(G)，κ(G)，λ(G).

说明：δ(G)=min{ d(v) | v?V } ；κ(G)=min{ |V’| |V’是图G的点割集} ； λ(G)=min{ |E’| |E’是图G的边割集}

9. 在什么条件下无向完全图Kn为欧拉图？ 10. 证明：有桥的图不是欧拉图. 11. 证明：有桥的图不是哈密尔顿图.

12. 树T有2个4度顶点，3个3度顶点，其余顶点全为树叶，问T有几片树叶？ 13. 证明：最大度Δ（T）≥k的树T至少有k片树叶。

14. 已知具有3个连通分支的平面图G有4个面，9条边，求G的阶数. 15. 给出全部互不同构的4阶简单无向图的平面图形。

16. 如果G是平面图, 有n个顶点、m条边、f个面，G有k个连通分支。试利用欧拉公式证明:：n-m+f=k+1.