《内蒙古大学计算机学院离散数学作业》由会员分享，可在线阅读，更多相关《内蒙古大学计算机学院离散数学作业（4页珍藏版）》请在金锄头文库上搜索。
1、离 散 作 业命题逻辑：1. 命题符号化：1) 小张不仅能吃苦，而且很能干。2) 吃一堑长一智。3) 除非小明努力学习，否则他就不能取得好成绩。2. 当 P、Q 的值为 0，R 、S 的值为 1 时求下列公式的值。1) （P(Q R)）（RS）2) （PR)(QS ）3. 设 A、B、C 为任意的命题公式，若 AC=BC ，则 A=B 一定为真吗？试说明原因。4. 列出命题公式(P(QR)(PQ) (PR)的真值表5. 证明：(PQ)(Q R)PR6. 求解(PQ) ( P ( Q R) ) ) ( P Q ) ( P R ) 的公式类型？（永真、永假、可满足？）7. 试将 PQ 化成与之等值
2、的并仅含联结词的公式. 8. 试将(PQ)R 化成与之等值的并仅含， 的公式. 9. 试用推理方式求解(PQ)(P R)的主合取范式，并根据其主合取范式写出其对应的主析取范式。10. 列出公式(P(QR) (PQ R)的真值表，根据真值表写出其对应的主合取范式和主析取范式。11. 用演绎法证明前提：P(QS) ，R P， Q结论:：RS12. 运用 CP 规则证明前提：P(QS) ，R P， Q结论:：RS 13. 用归结法证明下面推理：前提：P(QS) ，R P， Q结论:：RS 14. 在形式系统 L 中证明：B (BA).谓词逻辑：1. 谓词符号化：1) 所有的鱼都生活在水中。2) 没有
3、大于 2 的偶素数。3) 并不是每个人都聪明。2. 设个体域 D=a,b，将一阶公式(x)(F(x)(y)G(y)中的量词消除3. 设个体域为整数集，令 P(x,y)：x+y=1；Q(x,y)：xy0，试求解下列命题的真假。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. 所有的整数均为有理数并且为实数，存在是整数又是奇数的数，因而存在是奇数又是实数的数。写
4、出上面推理的证明。(用谓词逻辑，写出用谓词表示的前提、结论和证明过程)集合论：1. AB，AB 能否同时成立，说明原因2. 求集合 Aa，a 的幂集3. 证明：若 BC，则 P(B) P(C)4. 如果 AB=AC，是否有 B=C？如果 AB=AC，是否有 B=C？5. 试求 1 到 10000 之间不能被 4，5 或 6 整除的整数个数.6. 列出所有从 A=a,b,c到 B=s的关系，并指出 A*A 中的恒等关系和全域关系.7. 给出 A 上的关系及其关系图和矩阵表示 .|0x-y3 A=0，1，2，3，48. 已知 S=a,b. R =x,y|x,yA xyA 为集合族 (S).试写出关
5、系 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,yA ，S=|y-x=1,x,yA.试求：RS，RR，(RS)R，R (SR).13. 证明
6、：R 是 A 上的传递关系 RRR.14. A=1,2,3,4,5,R=|x,yAx- y 可被 2 整除，试问 R 是否是 A 上的等价关系？如果是，求出 R 的各等价类.15. A=1,2,3,4,5,A 上的划分 =1,2,3,4,5 ，给出由 所诱导出的 A 上的等价关系 R 的集合表达式.16. 试给出一个单射但非满射的函数.(对某一集合而言)17. 设 f：NNN，f(n)=,则：(1)说明 f 是否为单射和满射，并说明理由 .(2) f 的反函数是否存在？并说明理由.(3)求 ranf.18. 已知如果从无限集合 A 到集合 B 存在单射 f，则 B 也是无限集合。设 X 是无限
7、集合，集合 Y，证明：X 与 Y 的笛卡儿积 XY 是无限集合。代数系统：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) 说明
8、V 是否为半群、独异点和群？ 4. 设 A=a,b,c，构造 A 上的二元运算*，使得 a*b=c,c*b=b，且*运算满足幂等律、交换律.1) 给出关于*运算的一个运算表.2) *运算是否满足结合律，为什么？.5. 设是一个代数系统。*是 R 上的一个二元运算，使得对于 R(实数集合)中的任意元素 a,b 都有 a*b=a+b+ab(和+为数集上的乘法和加法).证明：: 是独异点.6. 如果是半群，且*是可交换的.证明：如果 S 中有元素 a,b,使得 a*a=a 和 b*b=b，则(a*b)*(a*b)=a*b.7. 设是一个群,则a,b,c S。 试证明： 群 G 中具有消去律,即成立:
9、 如果 ab=ac ,ba=ca 那么 b=c.8. 求循环群的所有生成元和子群 . 9. 设 是群， aG .现定义一种新的二元运算：xy=x*a*y，x,y G .证明： 也是群 . 10. 试写出模 6 加法群的每个子群及其相应的左陪集 .11. 试 aH 和 bH 是子群 H 在 G 中的两个左陪集.证明：aH=bH 或 aHbH= .12. 试写出群和环的定义.13. 证明偏序集与格的等价。14. 设 A=1,2,5,10,11,22,55,110.1) A 关于整除关系是否构成偏序集？2) 如果构成偏序集合，画出其对应的哈斯图.3) 如果构成偏序集，该偏序集合构成哪种格？ (分配格
10、、有界格、有补格、布尔格).图论：1. 已知无向图 G 有 12 条边， 6 个 3 度顶点，其余顶点的度数均小于 3，问 G 至少有几个顶点？并画出满足条件的一个图形.2. 是否存在 7 阶无向简单图 G，其度序列为 1、3、3、4、6、6、7.给出相应证明.3. 设 d1、d 2、d n 为 n 个互不相同的正整数. 证明：不存在以 d1、d 2、d n 为度序列的无向简单图.4. 求下图的补图.5.1) 试画一个具有 5 个顶点的自补图2) 是否存在具有 6 个顶点的自补图，试说明理由。6. 设图 G 为 n(n2 且为奇数)阶无向简单图，证明：G 与 G 的补图中奇度顶点个数相等.7.
11、 无向图 G 中只有 2 个奇度顶点 u 和 v，u 与 v 是否一定连通.给出说明或证明。8. 图 G 如下图所示：1) 写出上图的一个生成子图.2) (G)， (G)，(G).说明：(G)=min d(v) | vV ；(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.
