下载文档原格式
《离散数学》试题及答案一、选择题（每题5分，共25分）1. 下列关系中，哪个是等价关系？（）A. 小于等于（≤）B. 大于等于（≥）C. 整除（|）D. 模2同余（≡）答案：D2. 下列哪个图是完全图？（）A. 无向图B. 有向图C. 简单图D. n阶完全图答案：D3. 设A和B为集合，若A∪B=A，则下列哪个结论成立？（）A. A⊆BB. B⊆AC. A=BD. A∩B=∅答案：B4. 下列哪个命题是永真命题？（）A. (p→q)∧(q→p)B. (p∧q)→(p∨q)C. (p→q)∧(p→¬q)D. (p∧¬q)→(p→q)答案：B5. 设G=(V,E)是一个连通图，其中V={v1,v2,v3,v4,v5}，E={e1,e2,e3,e4,e5,e6}，若G的最小生成树的边数是（）。
A. 4B. 5C. 6D. 7答案：B二、填空题（每题5分，共25分）6. 设A={1,2,3,4,5}，B={3,4,5,6,7}，则A∩B=_________。
答案：{3,4,5}7. 设图G的顶点集V={a,b,c,d}，边集E={e1,e2,e3,e4,e5}，其中e1=(a,b)，e2=(a,c)，e3=(b,d)，e4=(c,d)，e5=(d,a)，则G的邻接矩阵为_________。
答案：[0 1 1 0 0; 1 0 0 1 0; 1 0 0 1 0; 0 1 1 0 1;0 0 0 1 0]8. 设p为真命题，q为假命题，则(p∧q)∨(¬p∧¬q)的值为_________。
答案：真9. 设G=(V,E)是一个连通图，其中V={v1,v2,v3,v4,v5}，E={e1,e2,e3,e4,e5,e6}，若G的度数序列为（3,3,3,3,3,3），则G的边数是_________。
答案：1510. 下列命题中，与“若p，则q”互为逆否命题的是_________。
离散数学试题及答案一、选择题1. 在集合论中，下列哪个选项表示两个集合A和B的并集？A. A ∩ BB. A ∪ BC. A - BD. A × B答案：B2. 命题逻辑中，下列哪个符号表示逻辑非？A. ∧B. ∨C. ¬D. →答案：C3. 在有向图中，如果存在一条从顶点u到顶点v的路径，那么称顶点v为顶点u的：A. 祖先B. 后代C. 邻居D. 连接点答案：B二、填空题1. 一个命题函数P(x)表示为“x是偶数”，那么其否定形式为________。
答案：x是奇数2. 在关系R上，如果对于所有的a和b，如果(a, b)∈R且(b, a)∈R，则称R为________。
答案：自反的三、简答题1. 简述什么是等价关系，并给出其三个基本性质。
答案：等价关系是一种特殊的二元关系，它满足自反性、对称性和传递性。
自反性指每个元素都与自身相关；对称性指如果a与b相关，则b也与a相关；传递性指如果a与b相关，b与c相关，则a与c也相关。
2. 解释什么是图的连通分量，并给出如何判断一个图是否是连通图。
答案：连通分量是指图中最大的连通子图，即图中任意两个顶点之间都存在路径。
判断一个图是否是连通图，可以通过深度优先搜索或广度优先搜索算法遍历整个图，如果所有顶点都被访问，则图是连通的。
四、计算题1. 给定命题公式P：((p → q) ∧ (r → ¬p)) → (q ∨ ¬r)，证明P是一个重言式。
答案：通过使用命题逻辑的等价规则和真值表，可以证明P在所有可能的p, q, r的真值组合下都为真，因此P是一个重言式。
2. 给定一个有向图G，顶点集合V(G)={1, 2, 3, 4}，边集合E(G)={(1, 2), (2, 3), (3, 4), (4, 1), (2, 4)}。
找出所有强连通分量。
答案：通过Kosaraju算法或Tarjan算法，可以找到图G的强连通分量，结果为{1, 4}和{2, 3}。
习题参考解答习题1.11、（3）P：银行利率降低Q：股价没有上升P∧Q（5）P：他今天乘火车去了北京Q：他随旅行团去了九寨沟PQ（7）P：不识庐山真面目Q：身在此山中Q→P，或～P→～Q（9）P：一个整数能被6整除Q：一个整数能被3整除R：一个整数能被2整除T：一个整数的各位数字之和能被3整除P→Q∧R ，Q→T2、（1）T （2）F （3）F （4）T （5）F（6）T （7）F （8）悖论习题 1.31（3）)()()()()()(R P Q P R P Q P R Q P R Q P →∨→⇔∨⌝∨∨⌝⇔∨∨⌝⇔∨→（4）()()()(())()(()())(())()()()()P Q Q R R P P R Q R P P R R P Q R P P R P R Q R Q P ∧∨∧∨∧=∨∧∨∧=∨∨∧∧∨∧=∨∧∨∧∨∧∨=右2、不， 不， 能习题 1.41(3) (())~((~))(~)()~(~(~))(~~)(~)P R Q P P R Q P P R T P R P R Q Q P R Q P R Q →∧→=∨∧∨=∨∧=∨=∨∨∧=∨∨∧∨∨、主合取范式)()()()()()()()()()()()()()())(())(()()(())()())(()((Q P R P Q R P Q R R Q P R Q P R Q P Q P R Q P R P Q R P Q R R Q P R Q P R Q P R Q P Q Q P R P P Q R R R Q Q P P R Q R P P Q R P P Q R P ∧∧∨∧⌝∧∨⌝∧⌝∧∨∧⌝∧⌝∨⌝∧∧⌝∨⌝∧⌝∧⌝=∧∧∨⌝∧∧∨∧⌝∧∨⌝∧⌝∧∨∧⌝∧⌝∨∧⌝∧⌝∨⌝∧∧⌝∨⌝∧⌝∧⌝=∨⌝∧∧∨∨⌝∧⌝∧∨∨⌝∧∨⌝∧⌝=∧∨⌝∧∨⌝=∨⌝∧∨⌝=→∧→ ————主析取范式(2) ()()(~)(~)(~(~))(~(~))(~~)(~)(~~)P Q P R P Q P R P Q R R P R Q Q P Q R P Q R P R Q →∧→=∨∧∨=∨∨∧∧∨∨∧=∨∨∧∨∨∧∨∨ 2、()~()(~)(~)(~~)(~)(~~)P Q R P Q R P Q P R P Q R P Q R P R Q →∧=∨∧=∨∧∧=∨∨∧∨∨∧∨∨∴等价3、解：根据给定的条件有下述命题公式：（A →（C ∇D ））∧～（B ∧C ）∧～（C ∧D ）⇔（～A ∨（C ∧～D ）∨（～C ∧D ））∧（～B ∨～C ）∧（～C ∨～D ）⇔（（～A ∧～B ）∨（C ∧～D ∧～B ）∨（～C ∧D ∧～B ）∨（～A ∧～C ）∨（C ∧～D ∧～C ）∨（～C ∧D ∧～C ））∧（～C ∨～D ）⇔（（～A ∧～B ）∨（C ∧～D ∧～B ）∨（～C ∧D ∧～B ）∨（～A ∧～C ）∨（～C ∧D ∧～C ）） ∧（～C ∨～D ）⇔（～A ∧～B ∧～C ）∨（C ∧～D ∧～B ∧～C ）∨（～C ∧D ∧～B ∧～C ）∨ （～A ∧～C ∧～C ）∨（～C ∧D ∧～C ∧～C ）∨（～A ∧～B ∧～D ）∨（C ∧～D ∧～B ∧～D ）∨（～C ∧D ∧～B ∧～D ）∨（～A ∧～C ∧～D ）∨ （～C ∧D ∧～C ∧～D ）（由题意和矛盾律）⇔（～C ∧D ∧～B ）∨（～A ∧～C ）∨（～C ∧D ）∨（C ∧～D ∧～B ）⇔（～C ∧D ∧～B ∧A ）∨ （～C ∧D ∧～B ∧～A ）∨ （～A ∧～C ∧B ）∨ （～A ∧～C ∧～B ）∨ （～C ∧D ∧A ）∨ （～C ∧D ∧～A ）∨（C ∧～D ∧～B ∧A ）∨（C ∧～D ∧～B ∧～A ）⇔（～C ∧D ∧～B ∧A ）∨ （～A ∧～C ∧B ∧D ）∨ （～A ∧～C ∧B ∧～D ）∨（～A ∧～C ∧～B ∧D ）∨ （～A ∧～C ∧～B ∧～D ）∨（～C ∧D ∧A ∧B ）∨ （～C ∧D ∧A ∧～B ）∨ （～C ∧D ∧～A ∧B ）∨ （～C ∧D ∧～A ∧～B ）∨（C ∧～D ∧～B ∧A ）∨（C ∧～D ∧～B ∧～A ） ⇔（～C ∧D ∧～B ∧A ）∨ （～A ∧～C ∧B ∧D ）∨ （～C ∧D ∧A ∧～B ）∨ （～C ∧D ∧～A ∧B ） ∨（C ∧～D ∧～B ∧A ）⇔（～C ∧D ∧～B ∧A ）∨ （～A ∧～C ∧B ∧D ）∨（C ∧～D ∧～B ∧A ） 三种方案：A 和D 、 B 和D 、 A 和C习题 1.51、 （1）需证()(())P Q P P Q →→→∧为永真式()(())~(~)(~())~~(~)(()(~))~(~)(~)()P Q P P Q P Q P P Q P P P Q P Q TP Q P Q T P Q P P Q →→→∧=∨∨∨∧∨=∨∨∧∨=∨∨∨=∴→⇒→∧（3）需证S R P P →∧⌝∧为永真式SR P P T S F S R F S R P P ⇒∧⌝∧∴⇔→⇔→∧⇔→∧⌝∧3A B A B ⇒∴→ 、为永真式。
.离散1一、选择题（每题2分，共20分） CABBB DACDA二、填空题（每题2分，共20分）1.n222.a∨b=1，a∧b=03.x*(xΔy)=x xΔ(x*y)=x4. 无回路5. 大项的合取所组成6. (∃x)⌝ P(x) (∀x)⌝ P(x)7.68.对任意的a,b G∈,有(a*b)*(a*b)=(a*a)*(b*b)9.βγ10. {<1，2>，<3，3>,<1，3>，<4，2>}，{<1,4>,<2,2>}三、判断题（每题1分，共10分）×√√×××××√√四、解答题（5小题，共30分）1.(5分）给定无孤立点图G，若存在一条路，经过图中每边一次且仅一次，该条路称为欧拉路；如果一个图有欧拉路，则这个图能一笔画出。
2.（8分）各4分，步骤对，结果错，适当扣分，如果求出其一个，另一个直接写出，也不扣分。
只有结果，且结果对，给一半分，只有结果，且结果错，不给分。
解：主析取范式:(┐P∧┐Q∧R)∨(┐P∧┐Q∧┐R)∨(P∧Q∧R)∨(P∧┐Q∧R)∨(┐P∧Q∧R)主合取范式:（┐P∨Q∨R）∧（┐P∨┐Q∨R）∧（P∨┐Q∨R）3.（5分）由无向树的性质可知，无向树的顶点数是边数加1，又知无向图所有顶点的度之和为边数的2倍。
（1分）令1度顶点个数为x,则顶点数为2+1+3+x，所有顶点的度之和为x+2*2+3+3*4，（2分）从而有x+2*2+3+3*4=2*(2+1+3+x-1)，解之得x=9,即有9个1度的点。
（2分）4.（7分）解：5. （5分）⎪⎪⎪⎪⎪⎭⎫⎝⎛=1100110100100101R M （2分）,（2分）,具有自反，对称性质（1分）五、证明（3小题，共20分）1. （10分）每步约1分，没有P,T 标识扣3分,没有序号扣3分。
《离散数学》题库与答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式( )(1)⌝Q=>Q→P (2)⌝Q=>P→Q (3)P=>P→Q (4)⌝P∧(P∨Q)=>⌝P答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别）2、下列公式中哪些是永真式( )(1)(┐P∧Q)→(Q→⌝R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q)答：（2），（3），（4）可用蕴含等值式证明3、设有下列公式，请问哪几个是永真蕴涵式( )(1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q(4)P∧(P→Q)=>Q (5) ⌝(P→Q)=>P (6) ⌝P∧(P∨Q)=>⌝P答：（2）是第三章的化简律，（3）类似附加律，（4）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式4、公式x((A(x)B(y，x))z C(y，z))D(x)中，自由变元是( )，约束变元是( )。
答：x,y, x,z（考察定义在公式x A和x A中，称x为指导变元，A为量词的辖域。
在x A和x A的辖域中，x的所有出现都称为约束出现，即称x 为约束变元，A中不是约束出现的其他变项则称为自由变元。
于是A(x)、B(y，x)和z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x 为自由变元）5、判断下列语句是不是命题。
若是，给出命题的真值。
( )(1)北京是中华人民共和国的首都。
(2) 陕西师大是一座工厂。
(3) 你喜欢唱歌吗 (4) 若7+8＞18，则三角形有4条边。
(5) 前进！ (6) 给我一杯水吧！答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6）不是（命题必须满足是陈述句，不能是疑问句或者祈使句。
）6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。
精品文档离散数学习题答案习题一及答案：（ P14-15 ）14、将下列命题符号化：（ 5）李辛与李末是兄弟解：设 p：李辛与李末是兄弟，则命题符号化的结果是p（ 6）王强与刘威都学过法语解：设 p：王强学过法语； q：刘威学过法语；则命题符号化的结果是p q （ 9）只有天下大雨，他才乘班车上班解：设 p：天下大雨； q：他乘班车上班；则命题符号化的结果是q p（ 11）下雪路滑，他迟到了解：设 p：下雪； q：路滑； r ：他迟到了；则命题符号化的结果是( p q)r15、设 p： 2+3=5.q：大熊猫产在中国 .r：太阳从西方升起 .求下列复合命题的真值：（ 4）(p q r )(( p q)r )解： p=1， q=1，r=0 ，(p q r )(110)1，((p q)r )((11)0)(00)1(p q r )(( p q)r ) 1 1119、用真值表判断下列公式的类型：（ 2）( p p)q解：列出公式的真值表，如下所示：p q p qp) ( p p)q( p001111011010100101110001由真值表可以看出公式有 3 个成真赋值，故公式是非重言式的可满足式。
20、求下列公式的成真赋值：精品文档（ 4）( p q)q解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：( p q)1p0q0q0所以公式的成真赋值有： 01，10， 11。
习题二及答案：（ P38）5、求下列公式的主析取范式，并求成真赋值：（ 2）(p q) (q r )解：原式( p q) q r q r( p p) q r( p q r ) ( p q r )m3m7，此即公式的主析取范式，所以成真赋值为011， 111。
6、求下列公式的主合取范式，并求成假赋值：（ 2）( p q) ( p r )解：原式( pp r ) ( p q r )( p q r )M 4，此即公式的主合取范式，所以成假赋值为 100。
离散数学试题与答案试卷一一、填空 20% （每小题2分）1．设 }7|{)},5()(|{<∈=<∈=+x E x x B x N x x A 且且（N ：自然数集，E + 正偶数） 则 =⋃B A 。
2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为 。
3．设P ，Q 的真值为0，R ，S 的真值为1，则)()))(((S R P R Q P ⌝∨→⌝∧→∨⌝的真值= 。
4．公式P R S R P ⌝∨∧∨∧)()(的主合取范式为。
5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ∀→∃ 在I 下真值为。
6．设A={1，2，3，4}，A 上关系图为则 R 2 = 。
A B7．设A={a，b，c，d}，其上偏序关系R的哈斯图为则 R= 。
8．图的补图为。
9．设A={a，b，c，d} ，A上二元运算如下：* a b cda bcda b cdb c dac d abd a bc那么代数系统<A，*>的幺元是，有逆元的元素为，它们的逆元分别为。
10．下图所示的偏序集中，是格的为。
二、选择 20% （每小题 2分）1、下列是真命题的有（）A ． }}{{}{a a ⊆；B ．}}{,{}}{{ΦΦ∈Φ；C ． }},{{ΦΦ∈Φ；D ． }}{{}{Φ∈Φ。
2、下列集合中相等的有（ ）A ．{4，3}Φ⋃；B ．{Φ，3，4}；C ．{4，Φ，3，3}；D ． {3，4}。
3、设A={1，2，3}，则A 上的二元关系有（ ）个。
A ． 23 ；B ． 32 ；C ． 332⨯；D ． 223⨯。
4、设R ，S 是集合A 上的关系，则下列说法正确的是（ ）A ．若R ，S 是自反的， 则S R 是自反的；B ．若R ，S 是反自反的， 则S R 是反自反的；C ．若R ，S 是对称的， 则S R 是对称的；D ．若R ，S 是传递的， 则S R 是传递的。
离散考试题与答案一、选择题1. 下列哪个不是离散数学的基本概念？A. 集合B. 二进制C. 图论D. 函数答案：C2. 设A = {1, 2, 3, 4}，B = {3, 4, 5, 6}，则A ∩ B = ?A. {1, 2}B. {3, 4}C. {5, 6}D. {3, 4, 5, 6}答案：B3. 在一个完全图中，有多少条边？A. nB. n(n-1)/2C. n(n+1)/2D. 2n答案：B4. 若f(x) = x^2 + 3x，则f(-2)的值为？A. -4B. -2C. 0D. 2答案：C5. 若A = {a, b, c}，B = {b, c, d}，则A - B = ?A. {a, b, c}B. {b, c, d}C. {a, d}D. {}答案：A二、填空题1. 设f(x) = x^2 + 5，求f(-3)的值。
答案：162. 设A = {1, 2, 3}，B = {3, 4, 5}，则A ∪ B = ？答案：{1, 2, 3, 4, 5}3. 在一个有向图中，若存在一条从顶点A到顶点B的路径，并且从B到A也存在一条路径，则该图称为_____图。
答案：强连通图4. 二进制数11111111转换为十进制的结果为______。
答案：2555. 若给定集合A = {1, 2, 3, 4}，则集合A的所有子集的个数为______。
答案：16三、简答题1. 解释集合的并、交和差的运算。
答案：集合的并运算指的是将两个集合中的所有元素合并成一个新的集合，新集合中的元素包括原来两个集合中的所有元素，但不重复。
集合的交运算指的是求出两个集合中共有的元素，构成一个新的集合。
集合的差运算指的是在一个集合中去除另一个集合中的元素，得到一个新的集合。
2. 什么是图论？答案：图论是研究图及其在各个领域中的应用问题的一门学科。
图由若干个顶点及连接这些顶点的边构成，图论主要研究图的性质、结构和算法问题。
3. 什么是函数？答案：函数是一种将每个输入值唯一对应到输出值的关系。
离散数学试题及答案一、选择题（每题2分，共20分）1. 在集合论中，下列哪个选项不是集合的运算？A. 并集B. 交集C. 差集D. 乘法2. 命题逻辑中，下列哪个命题是真命题？A. (P ∧ ¬P) → QB. (P ∨ Q) ∧ ¬(P ∧ Q)C. P → (Q → P)D. (P → Q) ∧ (Q → R) → (P → R)3. 函数f: A → B，如果f是单射，那么下列哪个选项是正确的？A. A中不同的元素在B中可能有相同的像B. B中每个元素都有原像C. A中不同的元素在B中有不同的像D. B中不同的元素在A中有不同的原像4. 在图论中，下列哪个选项不是图的基本术语？A. 顶点B. 边C. 邻接D. 矩阵5. 组合数学中，从n个不同元素中取出k个元素的组合数记作C(n, k)，下列哪个选项是错误的？A. C(n, k) = C(n, n-k)B. C(n, 0) = 1C. C(n, 1) = nD. C(n, k) = C(k, n)6. 关系R是A×B上的二元关系，下列哪个选项不是关系R的性质？A. 自反性B. 对称性C. 传递性D. 可数性7. 在命题逻辑中，下列哪个命题等价于P ∨ (Q ∧ R)？A. (P ∨ Q) ∧ (P ∨ R)B. (P ∧ Q) ∨ (P ∧ R)C. (P ∨ Q) ∨ RD. (P ∨ Q) ∧ R8. 集合{1, 2, 3}的幂集含有多少个元素？A. 3B. 6C. 8D. 99. 在图论中，下列哪个选项不是树的性质？A. 无环B. 至少有两个顶点C. 任意两个顶点都由唯一路径连接D. 至少有一个环10. 在集合论中，下列哪个选项是正确的？A. 空集是任何集合的子集B. 任何集合都是其自身的超集C. 空集是任何非空集合的真子集D. 空集是其自身的并集二、简答题（每题10分，共30分）11. 简述命题逻辑中的德摩根定律，并给出一个例子。
离散数学习题集十五套答案LELE was finally revised on the morning of December 16, 2020离散数学试题与答案试卷一一、填空 20% （每小题2分）1．设}7|{)},5()(|{<∈=<∈=+x E x x B x N x x A 且且（N ：自然数集，E + 正偶数） 则 =⋃B A 。
2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为 。
3．设P ，Q 的真值为0，R ，S 的真值为1，则)()))(((S R P R Q P ⌝∨→⌝∧→∨⌝的真值= 。
4．公式P R S R P ⌝∨∧∨∧)()(的主合取范式为。
5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ∀→∃ 在I 下真值为 。
6．设A={1，2，3，4}，A 上关系图为则 R 2 = 。
7．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为则 R= 。
8．图的补图为 。
9．设A={a ，b ，c ，d} ，A 上二元运算如下：A BC*a b c d abcd a b c d b c d a c d a b d a b c那么代数系统<A ，*>的幺元是 ，有逆元的元素为 ，它们的逆元分别为 。
10．下图所示的偏序集中，是格的为 。
二、选择 20% （每小题 2分）1、下列是真命题的有（ ）A ． }}{{}{a a ⊆；B ．}}{,{}}{{ΦΦ∈Φ；C ． }},{{ΦΦ∈Φ；D ． }}{{}{Φ∈Φ。
2、下列集合中相等的有（ ）A ．{4，3}Φ⋃；B ．{Φ，3，4}；C ．{4，Φ，3，3}；D ． {3，4}。
3、设A={1，2，3}，则A 上的二元关系有（ ）个。
A ． 23 ；B ． 32 ；C ． 332⨯；D ． 223⨯。
4、设R ，S 是集合A 上的关系，则下列说法正确的是（ ）A ．若R ，S 是自反的， 则S R 是自反的；B ．若R ，S 是反自反的， 则S R 是反自反的；C ．若R ，S 是对称的， 则S R 是对称的；D ．若R ，S 是传递的， 则S R 是传递的。
5、设A={1，2，3，4}，P （A ）（A 的幂集）上规定二元系如下R=t st sp∧∈=则P（A）/ R=（）|}>A<)(|||s(,,{t|A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}}6、设A={Φ，{1}，{1，3}，{1，2，3}}则A上包含关系“⊆”的哈斯图为（）7、下列函数是双射的为（）A．f : I→E , f (x) = 2x ； B．f : N→N⨯N, f (n) = <n , n+1> ；C．f : R→I , f (x) = [x] ； D．f :I→N, f (x) = | x | 。
（注：I—整数集，E—偶数集， N—自然数集，R—实数集）8、图中从v1到v3长度为3 的通路有（）条。
A． 0；B． 1；C． 2；D． 3。
9、下图中既不是Eular图，也不是Hamilton图的图是（）10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（）个4度结点。
A ．1；B ．2；C ．3；D ．4 。
三、证明 26%１、 R 是集合X 上的一个自反关系，求证：R 是对称和传递的，当且仅当< a, b> 和<a , c>在R 中有<.b , c>在R 中。
（8分）２、 f 和g 都是群<G 1 ,★>到< G 2, *>的同态映射，证明<C , ★>是<G 1,★>的一个子群。
其中C=)}()(|{1x g x f G x x =∈且 (8分)３、 G=<V, E> (|V| = v ，|E|=e ) 是每一个面至少由k （k ≥3）条边围成的连通平面图，则2)2(--≤k v k e ， 由此证明彼得森图（Peterson ）图是非平面图。
（11分）四、逻辑推演 16%用CP 规则证明下题（每小题 8分）1、F A F E D D C B A →⇒→∨∧→∨,2、)()())()((x xQ x xP x Q x P x ∀→∀⇒→∀五、计算 18%1、设集合A={a ，b ，c ，d}上的关系R={<a , b > ,< b , a > ,< b, c > , < c , d >}用矩阵运算求出R 的传递闭包t (R)。
（9分）2、如下图所示的赋权图表示某七个城市721,,,v v v 及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。
（９分）试卷二试题与答案一、填空 20% （每小题2分）1、P ：你努力，Q ：你失败。
“除非你努力，否则你将失败”的翻译为；“虽然你努力了，但还是失败了”的翻译为。
2、论域D={1，2}，指定谓词P P (1,1)P (1,2) P (2,1) P (2,2) T T F F则公式x ∀真值为 。
2、设S={a 1 ，a 2 ，…，a 8}，B i 是S 的子集，则由B 31所表达的子集是 。
3、设A={2，3，4，5，6}上的二元关系}|,{是质数x y x y x R ∨<><=，则R=（列举法）。
R 的关系矩阵M R =。
5、设A={1，2，3}，则A 上既不是对称的又不是反对称的关系R= ；A 上既是对称的又是反对称的关系R= 。
* a b c6、设代数系统<A ，*>，其中A={a ，b ，c},则幺元是 ；是否有幂等 性；是否有对称性 。
7、4阶群必是 群或 群。
8、下面偏序格是分配格的是 。
9、n 个结点的无向完全图K n 的边数为 ，欧拉图的充要条件是 。
10、公式R Q P Q P P ⌝∧∨⌝∧∧⌝∨)(())((的根树表示为。
二、选择 20% （每小题2分）1、在下述公式中是重言式为（ ）A ．)()(Q P Q P ∨→∧；B ．))()(()(P Q Q P Q P →∧→↔↔；C ．Q Q P ∧→⌝)(；D ．)(Q P P ∨→。
2、命题公式 )()(P Q Q P ∨⌝→→⌝ 中极小项的个数为（ ），成真赋值的个数为（ ）。
A ．0；B ．1；C ．2；D ．3 。
3、设}}2,1{},1{,{Φ=S ，则 S 2 有（ ）个元素。
A ．3；B ．6；C ．7；D ．8 。
abca b c b b c c c b4、设} 3 ,2 ,1 {=S ，定义S S ⨯上的等价关系},,,, | ,,,{c b d a S S d c S S b a d c b a R +=+⨯>∈<⨯>∈<><><<=则由 R 产 生的S S ⨯上一个划分共有（ ）个分块。
A ．4；B ．5；C ．6；D ．9 。
5、设} 3 ,2 ,1 {=S ，S 上关系R 的关系图为则R 具有（ ）性质。
A ．自反性、对称性、传递性；B ．反自反性、反对称性；C ．反自反性、反对称性、传递性；D ．自反性 。
6、设 ,+ 为普通加法和乘法，则（ ）>+< ,,S 是域。
A ．},,3|{Q b a b a x x S ∈+==B ．},,2|{Z b a n x x S ∈==C ．},12|{Z n n x x S ∈+==D ．}0|{≥∧∈=x Z x x S = N 。
7、下面偏序集（ ）能构成格。
8、在如下的有向图中，从V 1到V 4长度为3 的道路有（ ）条。
A ．1；B ．2；C ．3；D ．4 。
9、在如下各图中（ ）欧拉图。
10、设R 是实数集合，“⨯”为普通乘法，则代数系统<R ，×> 是（ ）。
A ．群；B ．独异点；C ．半群 。
三、证明 46%1、设R 是A 上一个二元关系，)},,,(),(|,{R b c R c a A c A b a b a S >∈<>∈<∈∧∈><=且有对于某一个试证明若R 是A 上一个等价关系，则S 也是A 上的一个等价关系。
（9分）2、用逻辑推理证明：所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。
因此有些学生很有风度。
（11分）3、若B A f →:是从A 到B 的函数，定义一个函数A B g 2:→对任意Bb ∈有)})(()(|{)(b x f A x x b g =∧∈=，证明：若f 是A 到B 的满射，则g 是从B 到 A2 的单射。
（10分）4、若无向图G 中只有两个奇数度结点，则这两个结点一定连通。
（8分）5、设G 是具有n 个结点的无向简单图，其边数2)2)(1(21+--=n n m ，则G 是Hamilton 图（8分）四、计算 14%1、设<Z 6,+6>是一个群，这里+6是模6加法，Z 6={[0 ]，[1]，[2]，[3]，[4]，[5]}，试求出<Z 6,+6>的所有子群及其相应左陪集。
（7分）2、权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。
（7分）试卷二答案：试卷三试题与答案一、 填空 20% （每空 2分）1、设 f ，g 是自然数集N 上的函数x x g x x f N x 2)(,1)(,=+=∈∀，则=)(x g f 。
2、设A={a ，b ，c}，A 上二元关系R={< a, a > , < a, b >,< a, c >, < c, c>} ,则s （R ）= 。
3、A={1，2，3，4，5，6}，A 上二元关系}|,{是素数y x y x T ÷><=，则用列举法T= ；T 的关系图为；T 具有 性质。
4、集合}}2{},2,{{Φ=A 的幂集A 2= 。
5、P ，Q 真值为0 ；R ，S 真值为1。
则))()(())((S R Q P S R P wff ∧∧∨→∨∧的真值为 。
6、R R Q P wff →∨∧⌝))((的主合取范式为 。
7、设 P （x ）：x 是素数， E(x)：x 是偶数，O(x)：x 是奇数 N (x,y)：x 可以整数y 。
则谓词))),()(()((x y N y O y x P x wff ∧∃→∀的自然语言是 。
