《离散数学》练习
福建农林大学东方学院
2009 ——2010 学年第一学期
第一篇 数理逻辑
一、填空题及单项选择题：
1、设解释I为：客体城D?{2,3}，
a2b,3f(2)3f(3),2P(2,2)1P(2,3)1P(3,2)0P(3,3) 0则P(a,f(a))?P(b,f(b))? ，?x?yP(x,y) 。
2、公式G?(P?(?Q?R))?Q的主析取范式为 。 3、下列命题等值式正确的是 【 】 （A）P?Q?(P?Q)?(Q?P)；
P?Q?(P?Q)?(P??Q)；（B）
（C）P?Q??Q??P； （D）P?Q?P??Q.
4、设命题公式G?(Q?P)?(?P?Q)，则G是 【 】 （A）可满足的； （B）永真的； （C）永假的； （D）析取范式
5、前提?xP(x)与?x(P(x)?Q(x))的有效结论是 【 】 （A）?xQ(x)； （B）?xQ(x)；
（C）?xP(x)； （D）?x(P(x)?Q(x))。. 二、解答题：
1、 将下列命题符号化：
（1） 明天不下雨又有空的话，我就会去打球。
（2） 只要她生病了，我都会去看她（只有她生病了，我才会去看她）。 （3） 每个旅客或坐头等舱或坐二等舱。
（4） 有些汽车比任何火车都慢，但并非所有的汽车都比火车慢。
2、 求公式G?(P?(Q?R))??Q的主合取范式和主析取范式，并求使G取值为 真的所有指派。
练习第1页（共6页）
三、逻辑推理题
1、用演绎法证明：P→（?Q→R），?S?P，?Q, ?R├?S. （应注明每一步推理所采用的推理规则）。
2、找出下列推导过程中的错误，并问结论是否有效？如果是，写出正确的推导过程。 （1）?x(P(x)?Q(x)) （2）P(y)?Q(y) （3）?xP(x) （4）P(y) （5）Q(y) （6）?xQ(x)
规则P（前提引入） (1) ??
规则P（前提引入） (3) ??
(2),(4)假言推理 (5) ??
3、有红、黄、绿、白四队参加足球联赛，如果红队第三，则当黄队不是第二时，绿队第四。或者白队不是第一，或者红队第三。已知绿队不是第四。试证明：如果白队第一，那么黄队第二。
（要求：设P：白队第一；Q：黄队第二；R：红队第三；S：绿队第四。并写出前提和结论的符号化及推理过程。）
第二篇 集合论
一、填空题及单项选择题：
1、 设R是集合A?{a,b,c}上的二元关系，且R?{(a,b),(a,c)}，则
s(R)? ，ts(R)? 。
2、 设R是A?{a,b,c,d}上的二元关系，且
R?{(a,b),(a,d),(c,c),(d,a)}，则R的关系矩阵AR?3、偏序关系应具有的性质为 。
4．设N、Z、Q、R和C分别为自然数、整数、有理数、实数和复数集合，（0，1）为实数区间，则下列式子正确的是 【 】
（A）N?R； （B）Q?C； （C）N?Q； （D）(0,1)?Z.
5．设N、R分别为自然数和实数集合，则下列基数关系式正确的是 【 】 （A）cardR??； （B）???0； （C）card2??； （D）card2N??0
练习第2页（共6页）
N6．按照阶从低到高的次序排列，则下列排列次序正确的是 【 】 （A）n,logn,n2,2n； （B）lgn,n,n,n2??(2n)； （C）logn,n,2n,n2； （D）logn??(lgn),n,n,2n 二、解答题
1、设集合A?{1,2,?,12}，R为A上的整除关系 ，试求： （1）画出偏序集(A,R)的Hasse图；
（2）写出A中的最大元、最小元、极大元、极小元；
（3）写出A的子集B?{1,3,6,9}的上界、下界及上、下确界。
2、（自然映射问题）习题八（P162）第16题。 （屈婉玲《离散数学》，下同） 设A?{a,b,c}，R为A上的等价关系，且
R?{?a,b?,?b,a?}?IA
求自然映射g:A?A/R。
3、（计数问题）习题六（P99）第21，23题。
（1）某班有25个学生，其中14人会打篮球，12人会打排球， 6人会打篮球和排球， 5人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人都会打蓝球或排球。求不会打球的人数。
（2）使用包含排斥原理求不超过120的素数个数。 三、证明题
?也是A上的等价关系。 1、设R是非空集合A上的等价关系，试证R的逆关系R?也是A上的偏序关系。 2、设R是非空集合A上的偏序关系，试证R的逆关系R3、设（0，1）和[0，1]为实数区间，证明：(0,1)?[0,1]
*第三篇 代数系统
一、填空题及单项选择题：
?123456?1、设?,?,??S6，且??(1)，????546213??，???则??= ，??的阶= 。
?123456????521436??， ??,10,11}，运算?是按位加，则群(G,?)的子群有 个，非平2、设G?{00,01凡子群有 个，2阶子群有 个。
3、整数集Z对于普通减法来说作成一个代数系统(Z,?)，则(Z,?) 【 】
（A）是半群但没有单位元； （B）含有单位元；
（C）有右单位元，但没有左单位元； （D）有左单位元，但没有右单位元。
练习第3页（共6页）
4、设S?{0,1,2}，?为模3乘法，即 ?x,y?S,x?y?(x)ymo，d 3则代数系统?S,?? 【 】
（A）是可换群； （B）是群但不是可换群； （C）是半群但不是独异点； （D）是独异点。
*5、设(B,?,?,,0,1)是布尔代数，若a?b，则下面不成立的公式是 【 】 a,b?B，（A）a?b?1； （B）a?b?1； （C）a?b?0； （D）a?b?a。 *6．设I是整数集，?,?分别是普通加法和减法；A是非空集合，则 【 】 （A）(I,?,?)是格； （B）(2A,?)不是格；
（C）(2A,?,?)不是格； （D）(2A,?)和(2A,?,?)是同一个格。 二、解答题
1、设A?{0,1}，S?A，试列出S中的所有函数，并给出S上合成运算的运算表。 2、设在实数集R上有运算*如下：a?b?a?b?ab,?a,b?R。 （1）求代数系统(R,?)的单位元e和零元?；
（2）求出元a(a??1)的逆元a。(R,?)中每一个元都有逆元吗？为什么？ （3）(R,?)是群吗？若R?R???1?，则(R,?)是否为群？为什么？
**?1A?21(,{)3(,)2})3、已知3次对称群 S3?{(1),(12),(13),(23),(123),(132)}，若H?1（1）试验证H是S3的一个正规子群；
（2）求出子群K??(12)?的所有左陪集及K在S3的指数[S3:K]； （3）求出S3的子群格，并画出它的偏序图。 三、证明题
1、设（G，*）是群，a∈G，定义映射
f：G →G，使 f(x)?a?x?a,?x? G证明f是（G，*）的自同构。
2、设G是群，若?x?G有x?e，证明G为阿贝尔群。
练习第4页（共6页）
2。
?1
第四篇 图论
一、填空题及单项选择题：
?102???0011、邻接矩阵为??的有向图中，长度为2的非回路的路有 条， ?110???长度为2的回路有 条。
2、树叶权为1，2，3，4，5的最优树为
。
3、 具有5个结点的所有不同构的树为
4、在下列的各种顶点度序列中可图解但不可简单图解的是 【 】 （A）(3,1,1,1); （B）d?(5,3,2,1,1); （C）d?(1,1,1,1);
（D）d?(3,2,2,1,1)
5、二分图K3,3也是 【 】 （A）欧拉图; （B）哈密尔顿图; （C）平面图;
（D）完全图。
6、下图是 【 】 （A）Bipartite Graph; (B)Planar Graph; （C）Eller Graph; (D)Hamilton Graph
二、计算题
1、设图G为平面图，它的边数是区域数的2倍，并且有一个6次顶点，四个3次顶点， 三个2次顶点，其余顶点都是1次的。试求图G的顶点数、边数和区域数。
2、一棵树有2个2次分枝点，1个3次分枝点，3个4次分枝点，其余顶点都是树叶， 问这棵树有几片树叶？
3、 设有无向图G?(V,E)，其中V(G)?{a1,a2,?,a5}，而G的邻接矩阵
练习第5页（共6页）
?0?1?A??0??1??110110011?110??001?，
?001?110??且当(ai,aj)?E(G)时，边(ai,aj)的权数为i?j(i,j?1,2,?,5)。试画出图G，并求图
G的一个最小生成树及最小生成树的权数。
三、应用及证明题：
1、（哈米尔顿回路问题）习题十五（P306）第15题。
某工厂生产由6种颜色的纱织成的双色布。已知在一批双色布中，每种颜色至少与其他3种颜色相搭配。证明可以从这批双色布中挑出3种，它们由不同颜色的纱织成。
2、（最短路问题）习题十五（P307）第22题。
某工厂使用一台设备，每年年初要决定是继续使用，还是购买新的。预计该设备第一年的价格为11万元，以后每年涨1万元。使用的第1年，第2年，…，第5年的维修费分别为5，6，8，11，18万元。使用1年后的残值为4万元，以后每使用1年残值减少1万元。试制定购买维修该设备的5年计划，使总支出最小。
3、试证，在完全二叉树中，边的总条数应该等于2(nt?1),其中的nt是树叶的总片数。
练习第6页（共6页）