2013-1-17离散数学考试.doc

2012-2013年度离散数学试卷A 设P：天下雪；Q：我进城；R：我有时间 将下列命题的符号化： （1）如果天不下雪且我有时间，我就进城； （2）我进城的必要条件是我有时间； （3）天不在下雪； （4）我进城当且仅当我有时间且天不下雪； 一个命题公式A（P、Q、R）的成真指派为FFF, FFT , FTF , TFF , TTF ,求改公式的主合取范式。 构造下面推理的证明： （1） （2） 设解析I如下： 确定下列公式在I下的真值： 一个体育团共25人，其中14人会踢足球，12人会打乒乓球6人既会踢足球又会打乒乓球，5人既会打篮球又会踢足球，还有2人这三种球都会，而6个会打篮球的人都会打另外一种球，求不会打球的人数。 、 如下给出四个函数，判断哪些是入射？哪些是满射？哪些是双射？ 区间[2,3]的基数是什么？证明你的结论。 设Z是整数集，定义Z上的运算*如下：a*b=a+b-2，（这里的+和-是普通加法和减法 （1）代数系统Z，*是半群吗？为什么？ （2）它有没有幺元？如果有，请给出。 （3）Z中的每个整数都有逆元吗？如果有，请给出。 下图给了一些偏序集的哈斯图 指出哪些不是格？为什么？ 给出每个格的一个子格。 在上述第一个格上计算 给出如图一个无向的简单图 给出上图的一个平面图像的对偶图 给出（1）中平面图像的对偶图 用布尔奇鲍威尔法给出该图的一个正常着色 给出该图的着色数并做适当的解释 已知简单有向图如下： （1）图中长度小于等于四的路（包括回路）有多少条？ （2）给出该图的可达矩阵 （3）给出该图的弱分图，单侧分图，强分图 已知如下一个带杈图 该图有没有欧拉回路、欧拉路？如果有，请给出。 用kruskal 算法求出该图的一个最小生成树。 说明该图没有哈密尔顿回路但存在哈密尔顿路。