离散数学期末试题及答案

离散数学期末考试题及详细答案一、选择题（每题5分，共20分）1. 在离散数学中，下列哪个概念用来描述元素与集合之间的关系？A. 并集B. 交集C. 子集D. 元素答案：D2. 布尔代数中，下列哪个运算符表示逻辑“与”？A. ∨B. ∧C. ¬D. →答案：B3. 下列哪个命题的否定是正确的？A. 如果今天是周一，则明天是周二。

B. 如果今天是周一，则明天不是周二。

答案：B4. 在图论中，一个图的顶点数为n，边数为m，下列哪个条件可以保证该图是连通的？A. m > nB. m ≥ nC. m = nD. m > n-1答案：D二、填空题（每题5分，共20分）1. 在集合论中，一个集合的幂集包含该集合的所有______。

答案：子集2. 如果一个函数f: A → B是单射的，那么对于任意的a1, a2 ∈ A，如果a1 ≠ a2，则f(a1) ≠ f(a2)。

这种性质称为函数的______。

答案：单射性3. 在图论中，一个图的直径是指图中任意两个顶点之间的最短路径的最大值。

如果一个图的直径为1，则该图被称为______。

答案：完全图4. 一个布尔表达式可以表示为一系列逻辑运算符和变量的组合。

布尔表达式(A ∧ B) ∨ (¬ A ∧ C)的真值表中，当A为真，B为假，C为真时，整个表达式的值为______。

答案：真三、简答题（每题10分，共30分）1. 请简述什么是图的哈密顿回路，并给出一个例子。

答案：哈密顿回路是图中的一个回路，它恰好访问每个顶点一次。

例如，在一个完全图中，任意一个顶点出发，依次访问其他顶点，最后回到出发点的路径就是一个哈密顿回路。

2. 请解释什么是二元关系，并给出一个二元关系的例子。

答案：二元关系是定义在两个集合上的一个关系，它关联了第一个集合中的元素和第二个集合中的元素。

例如，小于关系是实数集合上的一个二元关系，它关联了每一对实数，如果第一个数小于第二个数。

离散数学期末试题及答案HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】326《离散数学》期末考试题(B )一、填空题(每小题3分，共15分)1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )，)(A P 中的元素个数=|)(|A P ( ).2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数.3.谓词公式))()(())()((y P y Q y x Q x P x ⌝∧∃∧→∀中量词x ∀的辖域为( ), 量词y ∃的辖域为( ).4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元.5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=⨯||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个.2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射.3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧⌝)(； (5)q q p →→)(.4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ).5. 设G 是(7, 15)简单平面图，则G 一定是( )图，且其每个面恰由( )条边围成，G 的面数为( ).三．1.设}}{},,{{c b a A =，}}{},,{},{{c c b a B =，则)(=⋃B A ，)(=⋂B A ，)()(=A P .2.集合},,{c b a A =，其上可定义( )个封闭的1元运算，( )个封闭的2元运算，( )个封闭的3元运算.3.命题公式1)(↑∧q p 的对偶式为( ).4.所有6的因数组成的集合为( ).5.不同构的5阶根树有( )棵.四、(10分)设B A f →:且C B g →:，若g f 是单射，证明f 是单射，并举例说明g 不一定是单射.五、(15分)设},,,{d c b a A =,A 上的关系)},(),,(),,(),,(),,(),,(),,(),,(),,{(c d b d a d c c b c a c c a b a a a R =,1.画出R 的关系图R G .2.判断R 所具有的性质.3.求出R 的关系矩阵R M .六、(10分)利用真值表求命题公式))(())((p q r r q p A →→↔→→=的主析取范式和主合取范式.七、(10分) 边数30<m 的简单平面图G ，必存在节点v 使得4)deg(≤v . 八、(10分) 有六个数字，其中三个1，两个2，一个3，求能组成四位数的个数.《离散数学》期末考试题(B)参考答案一、1. {{a , b }, a , b , ?}， {{a , b }, a , b }，16.2.92, 27.3.)()(x Q x P →, )()(y P y Q ⌝∧.4. 2, 4, 6, 12.5.4≤，奇数.二、1.22,2,m mn mn ., g , g . ,2,4.，不存在，不存在. 5.连通，3，10.三、1. }}{},,{},,{},{{c c b b a a B A =⋃，}}{{c B A =⋂，{)(=A P ?, {{a , b }}, {{c }}, {{a , b }, {c }}}.2.27933,3,3. 3.0)(↓∨q p .4.{-1，-2，-3，-6，1，2，3，6}. .四、证 对于任意A y x ∈,，若)()(y f x f =，则))(())((y f g x f g =，即))(())((y g f x g f =. 由于g f 是单射，因此y x =，于是f 是单射.例如取},,{},3,2,1(},,{γβα===C B b a A ，令)}2,(),1,{(b a f =，)},3(),,2(),,1{(ββα=g ，这时)},(),,{(βαb a g f = 是单射，而g 不是单射.五、解 1. R 的关系图R G 如下：2.(1)由于R b b ∉),(，所以R 不是自反的. (2)由于R a a ∈),(，所以R 不是反自反的.(3)因为R b d ∈),(，而R d b ∉),(，因此R 不是对称的. (4)因R a c c a ∈),(),,(，于是R 不是反对称的.(5)经计算知R c d a d c c b c a c c a b a a a R R ⊆=)},(),,(),,(),,(),,(),,(),,(),,{( ，进而R 是传递的.综上所述，所给R 是传递的.3.R 的关系矩阵⎪⎪⎪⎪⎪⎭⎫⎝⎛=0111011100000111R M .六、解 命题公式))(())((p q r r q p A →→↔→→=的真值表如下:由表可知，))(())((p q r r q p A →→↔→→=的主析取范式为A 的主合取范式为)()(r q p r q p A ⌝∨⌝∨∧∨⌝∨⌝=.七、证 不妨设G 的阶数3≥n ，否则结论是显然的. 根据推论1知，63-≤n m . 若G 的任意节点v 的度数均有5)deg(≥v ，由握手定理知n v m v5)deg(2≥=∑.于是m n 52≤，进而652363-⋅≤-≤m n m . 因此30≥m ，与已知矛盾. 所以必存在节点v 使得4)deg(≤v .八、解 设满足要求的r 位数的个数有a r 种，r = 0，1，2，…，则排列计数生成函数65432121211219619431x x x x x x ++++++=,因而38!412194=⋅=a .。

离散数学期末考试试题及答案一、选择题（每题3分，共30分）1. 设集合A={1, 2, 3, 4, 5}，B={2, 4, 6, 8}，则A∩B是（）A. {1, 2, 3, 4, 5}B. {2, 4}C. {1, 3, 5}D. {2, 4, 6, 8}2. 下列关系中，哪个是等价关系？（）A. 小于关系B. 大于等于关系C. 模2同余关系D. 整除关系3. 设P(x)是谓词逻辑公式，下列哪个命题与∀xP(x)等价？（）A. ∃x¬P(x)B. ¬∀xP(x)C. ¬∃xP(x)D. ∃x¬P(x)4. 一个图的欧拉回路是指（）A. 经过每一条边的路径B. 经过每一个顶点的路径C. 经过每一条边的环D. 经过每一个顶点的环5. 设G是一个无向图，下列哪个说法是正确的？（）A. G的每个顶点的度数都相等B. G的每个顶点的度数都不相等C. G的任意两个顶点之间都有一条边D. G的任意两个顶点之间都不一定有边6. 下列哪个图是哈密顿图？（）A. K3,3B. K5C. K4,4D. K67. 设G是一个具有n个顶点的连通图，则G的最小生成树至少包含（）A. n个顶点B. n-1条边C. n+1条边D. 2n条边8. 下列哪个算法可以用来求解最短路径问题？（）A. Dijkstra算法B. Kruskal算法C. Prim算法D. Floyd算法9. 设P和Q是两个命题，下列哪个命题与(P→Q)∧(Q→P)等价？（）A. P∧QB. P∨QC. P↔QD. ¬P∨¬Q10. 设A是一个有限集合，A的幂集是指（）A. A的所有子集B. A的所有真子集C. A的所有非空子集D. A的所有非空真子集二、填空题（每题3分，共30分）11. 设集合A={1, 2, 3, 4, 5}，B={2, 4, 6, 8}，则A-B=______。

12. 设P(x)是谓词逻辑公式，∃xP(x)表示“存在一个x使得P(x)成立”，那么∀x¬P(x)表示“______”。

离散数学期末考试题及答案1.选择题（每题3分，共30分）1. 下列命题中，属于复合命题的是：A. 3是一个奇数，且2是一个偶数B. 如果2是一个素数，那么4也是一个素数C. 不是所有奇数都是素数D. 存在一个整数x，使得x>5且x是一个偶数答案：D2. 已知命题p：草地是绿的，命题q：天空是蓝的。

下列表述可以表示p ∧ ¬q 的是：A. 草地是绿的，天空是蓝的B. 草地不是绿的，天空是蓝的C. 草地是绿的，天空不是蓝的D. 草地不是绿的，天空不是蓝的答案：B3. 设命题p表示“这个数是偶数”，q表示“这个数大于10”。

那么“这个数既是偶数又大于10”可以表示为：A. p ∧ qB. p ∨ qC. ¬p ∧ qD. ¬p ∨ q答案：A4. 下列以下列集合的方式描述，其中哪个是空集∅：A. {x | 0 ≤ x ≤ 1}B. {x | x是一个自然数，x > 10}C. {x | x是一个正偶数，x < 2}D. {x | x是一个负整数，x < -1}答案：C5. 设A = {a, b, c}，B = {c, d, e}，C = {a, c, e}。

则(A ∪ B) ∩ C等于：A. {a, b, c, d, e}B. {a, c, e}C. {c}D. 空集∅答案：B6. 假设U是全集，A、B、C是U的子集。

则(A ∪ B) ∩ C 的补集是：A. A ∩ B ∩ C的补集B. (A ∪ B) ∩ C的补集C. A ∪ (B ∩ C)的补集D. (A ∩ C) ∩ (B ∩ C)的补集答案：D7. 若关系R为集合A到集合B的一种映射，且|A| = 7，|B| = 4，则R包含的有序对数目为：A. 4B. 7C. 11D. 28答案：D8. 设A={1,2,3}，B={4,5,6}，则从A到B的映射总数为：A. 3B. 9C. 6D. 18答案：C9. 设A={a,b,c,d,e}，则集合A的幂集的元素个数是：A. 2B. 5C. 10D. 32答案：D10. 若f：A→B为满射且g：B→C为单射，则(g ∘ f)：A→C为：A. 双射B. 满射C. 单射D. 非单射且非满射答案：A2.简答题（每题10分，共20分）1. 请简要解释什么是关系R的自反性、对称性和传递性。

离散数学期末考试题及答案一、选择题（每题2分，共20分）1. 在集合论中，空集表示为：A. {0}B. {1}C. {}D. Ø答案：D2. 命题逻辑中，下列哪个是合取命题的真值表？A. P | Q | P ∧ QB. P | Q | P ∨ QC. P ∧ Q | P ∨ QD. P ∧ Q | ¬(P ∨ Q)答案：A3. 函数f: A → B是单射的，那么f的逆函数：A. 一定存在B. 一定不存在C. 可能存在D. 以上都不对答案：C4. 关系R是自反的，那么对于所有a∈A，以下哪个命题一定为真？A. (a, a) ∈ RB. (a, a) ∉ RC. (a, a) ∈ R或(a, a) ∉ RD. (a, a) ∈ R且(a, a) ∉ R答案：A5. 在图论中，下列哪个不是图的基本术语？A. 顶点B. 边C. 子集D. 路径答案：C6. 命题p: “如果x是偶数，则x能被4整除”的否定是：A. 如果x是偶数，则x不能被4整除B. 如果x不是偶数，则x不能被4整除C. 如果x不是偶数，则x能被4整除D. 如果x是偶数，则x不能被4整除或x不是偶数答案：A7. 有向图G中，如果存在从顶点u到顶点v的有向路径，则称v是u 的：A. 祖先B. 后代C. 邻居D. 连接点答案：B8. 在命题逻辑中，下列哪个命题是永真命题？A. (P ∧ ¬P) ∨ (P ∨ ¬P)B. (P ∧ ¬P) ∧ (P ∨ ¬P)C. (P ∨ ¬P) ∧ (¬P ∨ P)D. (P ∧ ¬P) ∧ (¬P ∧ P)答案：C9. 以下哪个选项是等价命题？A. P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)B. P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)C. P ∨ ¬P ≡ ¬P ∧ PD. P ∧ ¬P ≡ ¬P ∨ P答案：A10. 树是无环连通图，以下哪个是树的属性？A. 至少有一个环B. 至少有两个顶点C. 至少有一个顶点D. 至少有一个边答案：B二、填空题（每空2分，共20分）11. 集合{1, 2, 3}的幂集含有__个元素。

一、单项选择题（每小题3分，共30分）1．下列为两个命题变元ｐ，ｑ的最小项的是（ ） A ．ｐ∧ｑ∧⎤ ｐB ．⎤ ｐ∨ｑC ．⎤ ｐ∧ｑD ．⎤ ｐ∨ｐ∨ｑ 2．下列句子不是命题的是（ ） A ．中华人民共和国的首都是北京 B ．张三是学生 C ．雪是黑色的D ．太好了！3．对于公式(∀x ) (∃y )(P (x )∧Q (y ))→(∃x )R (x ,y )，下列说法正确的是（ ） A ．y 是自由变元 B ．y 是约束变元C ．(∃x )的辖域是R(x , y )D ．(∀x )的辖域是(∃y )(P (x )∧Q (y ))→(∃x )R (x ,y )4．7．集合A={1，2，…，10}上的关系R={（x ，y ）|x +y =10，x ∈A ，y ∈A}，则R 的性质是（ ）A ．自反的B ．对称的C ．传递的、对称的D ．反自反的、传递的 5．设论域为{l ，2}，与公式)(x xA ∃等价的是( ) A.A (1)∨A (2)B. A (1)→A (2)C.A (1)D. A (2)→A (1)6. 下列关系矩阵所对应的关系具有反自反性的是（ ） A ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡001110101B ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡101100001 C ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡001100100D ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡0010101017. 下列运算不满足．．．交换律的是（ ） A ．a *b =a+2bB ．a *b =min(a ,b )C ．a *b =|a -b |D ．a *b =2ab8．.设A 是奇数集合，下列构成独异点的是( ) A.<A ，+> B.<A ，-> C.<A ，×> D.<A ，÷> 9. 右图的最大入度是( ) A ．0 B ．1 C ．2D ．3第9题图拟题学院（系）： 高密校区 适用专业： 学年 2学期 离散数学 （Ｂ卷） 试题标准答案10. 设有向图D 的节点数大于1，D=（V ,E ）是强连通图，当且仅当（ ） A. D 中至少有一条通路 B. D 中至少有一条回路C. D 中有通过每个结点至少一次的通路D. D 中有通过每个结点至少一次的回路 二、填空题(每空3分，共30分)1．设A ={1，2，3，4}，B ={2，4，6}，则A -B =________，A ⊕B =________。

一、填空2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为 (B ⊕C)-A4．公式P R S R P ⌝∨∧∨∧)()(的主合取范式为 )()(R S P R S P ∨⌝∨⌝∧∨∨⌝ 。

5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ∀→∃ 在I 下真值为 1 。

6．设A={1，2，3，4}，A 上关系图如下，则 R^2= {(1,1),(1,3),(2,2),(2,4)} 。

//备注：⎪⎪⎪⎪⎪⎭⎫⎝⎛=0000100001010010R⎪⎪⎪⎪⎪⎭⎫⎝⎛=00000000101001012R7．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图如下，则R= {(a,b),(a,c), (a,d), (b,d), (c,d)} U {(a,a),(b,b)(c,c)(d,d)} 。

//备注：偏序满足自反性，反对称性，传递性8．图的补图为 。

//补图:给定一个图G ,又G 中所有结点和所有能使G 成为完全图的添加边组成的图,成为补图. 自补图:一个图如果同构于它的补图,则是自补图 9．设A={a ，b ，c ，d} ，A 上二元运算如下：* a b c d a b c da b c d b c d a c d a b d a b c那么代数系统<A ，*>的幺元是 a ，有逆元的元素为 a,b,c,d ，它们的逆元分别为 a,b,c,d 。

//备注：二元运算为x*y=max{x,y}，x,y ∈A 。

10．下图所示的偏序集中，是格的为 c 。

//（注：什么是格？即任意两个元素有最小上界 和最大下界的偏序）二、选择题1、下列是真命题的有（ C 、D ）A ． }}{{}{a a ⊆；B ．}}{,{}}{{ΦΦ∈Φ；C ．}},{{ΦΦ∈Φ； D ．}}{{}{Φ∈Φ。

2、下列集合中相等的有（ B 、C ）A ．{4，3}Φ⋃；B ．{Φ，3，4}；C ．{4，Φ，3，3}；D ． {3，4}。

一、单项选择题2.设集合A={1，2，3}，下列关系R 中不．是等价关系的是（ D ） A.R={<1,1>,<2,2>,<3,3>}； B.R={<1,1>,<2,2>,<3,3>,<3,2>,<2,3>}；C. R={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>}；D. R={<1,1>,<2,2>,<3,3>,<1,2 >}.3．在公式（x ∀）F （x ，y ）→（∃ y ）G （x ，y ）中变元x 是（ B ）A ．自由变元；(前面无∀或∃量词)B ．既是自由变元，又是约束变元；C ．约束变元；(前面有∀或∃量词)D ．既不是自由变元，又不是约束变元.4．设A={{1，2，3}，{4，5}，{6，7，8}}，下列选项正确的是（ C ）A ．1∈A ；B ．{1，2，3}⊆A ；C ．{{4，5}}⊆A ；D ．∈A. 5.设论域为{l ，2}，及公式)()(x A x ∃等价的是( A )A.A (1)∨A (2)；B. A (1)→A (2)；C.A (1)∧A (2)；D. A (2)→A (1).6.一棵树有5个3度结点，2个2度结点，其它的都是l 度结点，那么这棵树的结点数是( B )A.13 ；B.14 ；C.16 ；D.17 .//设一度结点数为n,则有：5×3+2×2+n=2[(5+2+n)-1]解得：n=7, 所以这棵树的结点数为：m=5+2+7=14.7．设A 是偶数集合，下列说法正确的是（ A ）A ．<A ,+>是群；B ．<A ,×>是群；C ．<A ,÷>是群；D ．<A ,+>, <A ,×>,<A ,÷>都不是群。

离散期末考试题及答案离散数学期末考试题及答案一、选择题（每题2分，共20分）1. 在集合论中，以下哪个符号表示属于关系？A. ∈B. ∉C. ⊆D. ⊂答案：A2. 有限集合A和B的并集，其元素个数最多是A和B元素个数之和，这个性质称为：A. 德摩根定律B. 幂集C. 并集原理D. 子集原理答案：C3. 命题逻辑中，以下哪个命题是真命题？A. (p ∧ ¬p) ∨ qB. (p ∨ ¬p) ∧ qC. (p ∨ q) ∧ ¬pD. (p ∧ q) ∨ ¬p答案：B4. 在图论中，一个无向图的边数至少是顶点数的多少倍才能保证图中至少存在一个环？A. 1B. 2C. 3D. 4答案：B5. 以下哪个算法用于生成一个集合的所有子集？A. 欧拉回路B. 哈密顿回路C. 深度优先搜索D. 子集生成算法答案：D6. 在关系数据库中，以下哪个操作用于删除表中的行？A. SELECTB. INSERTC. UPDATED. DELETE答案：D7. 以下哪个是有限自动机的状态？A. 初始状态B. 终止状态C. 转移状态D. 所有选项答案：D8. 以下哪个是图论中的一个基本定理？A. 欧拉定理B. 哈密顿定理C. 狄拉克定理D. 所有选项答案：D9. 在命题逻辑中，以下哪个是德摩根定律的逆命题？A. ¬(p ∨ q) ≡ ¬p ∧ ¬qB. ¬(p ∧ q) ≡ ¬p ∨ ¬qC. ¬(p ∨ q) ≡ ¬p ∨ ¬qD. ¬(p ∧ q) ≡ ¬p ∧ ¬q答案：B10. 在集合论中，以下哪个操作表示集合的差集？A. ∩B. ∪C. -D. ×答案：C二、填空题（每空3分，共30分）11. 集合{1, 2, 3}的幂集包含________个元素。

国家开放大学电大本科《离散数学> 2022-2023期末试题及答案（试卷号：1009）一、单项选择题(每小题3分，本息共16分)1, 若集合A = <1,2,3},则下列表述正确的是〈 )•A. {1,2,3}€AB. AC(1,2}C. U,2,3}gAD. {1,2}£A2. 设 A = {1,2,3},B = (1,2,3,4},人到 B 的关系 R = {O ,>> |工 £ A ,了 £ B },则 R =().A. {<1,2>,V2,3>}B. {V1,1>,V1,2>,V1,3>,V1,4>，V1,5>}C. «1,1>,<2,1>)D. {<2,】>,V3,】>,V3,2>}3. 无向图G 的边数是10,则图G 的结点度数之和为(A. 10B. 20C. 30D. 54. 如图一所示，以下说法正确的是〈 )•A. e 是割点B. {a,e}是点割集C. (b.e}是点割集D. {d}是点割集5-设个体域为整数集，则公式Vx3y （x+y = 2）的解释可为（）.A. 任意整数工，对任意整数y 满足工+了 = 2B. 对任意整数工，存在整数y 满足工+了 = 2C. 存在一整数z,对任意整数y 满足工+了 = 2D. 存在一整数工，有整数了满足x+jr = 2则人 CHBUC ）等于 _____ .7. 设 A = {1,2},B = <2,3},C=（3,4},从 A 到 B 的函数/= （VI,2>,V2,3>},从 B到 C 的函数 g = （V2,3>,V3,4>},则 Ran （g 0/）等于 ______ .8. 设G 是汉密尔顿图，S 是其结点集的一个子集，若S 的元素个数为6,则在G-S 中的连通分支数不超过 ________ .二、填空霆（每小题3分，本题共15分）9.设G是有8个结点的连通图，结点的度数之和为24,则可从G中删去 ________ 条边后使之变成树.10.设个体域D = {1,2, 3, 4},则谓词公式（VQ A S）消去量词后的等值式为H.将语句“昨夭下雨，今天仍然下雨.”翻译成命题公式.12. 将i 吾句“我们下午2点或者去礼堂看电彩或者去教室看书.”翻译成命飓公式. 得分评卷人13. 不存在集合A 与B,使得AEB 与AQB 同时成立.14. 如图二所示的图G 存在一条欧拉回路.15. 设 A = ｛l,2,3｝,R = （<x,y>l=£A<yCA 且 1+»=4｝击=｛〈工，3>0£人，36人且 工=）｝，试求 R,S,R" ,r （S ）.16. 设图 G = <VtE>»V=（v! 试（1） 画出G 的图形表示； （2） 写出其邻接矩阵； （3） 求出每个结点的度数； （4）画出图G 的补图的图形•17. 求-I （PVQ ）VR 的析取范式与主合取范式•18. 试证明门 PVQ»P -*(i (n PVn Q)〉.（仅 一、单项选择题（每小题3分，本题共15分）1.C2. D3. B二、填空题（每小题3分，本题共15分）6. {b t c)7. {3,4）（或 C ） 8.6 9.5评卷人三、逻辑公式翻译（每小题6分，本题共12分）四、判断说明题（判断各题正误，并说明理由.每小题7分，本题共14 分）评卷人五、计算题（每小题12分，本题共36分）评卷人六、证明题（本题共8分）10.A（1）AA（2） AA（3） AA（4）三、逻辑公式翻译（每小题6分，本题共12分）11.设P：昨天下雨,Q：今天下雨. （2分）则命题公式为:PAQ. （6分）12.设P：我们下午2点去礼堂看电影，Q：我们下午2点去教室看书. （2分）则命题公式为门（P-Q）. （6分）注:或者（1 PAQ）V（PAi Q）四、判断说明题（每小题7分，本题共14分）13.错误•（3分）例:设A = {a},B^{a,{a}}（5 分）则有AEB且AWB. （7分）说明:举出符合条件的反例均给分.14.正确. （3分）因为图G为连通的，且其中每个顶点的度数均为偶数. （7分）如果具体指出一条欧拉回路也同样给分.五、计算题（每小题12分，本题共36分）15.解：R = {V1,3>,V2,2>,V3,1>} （3分）S = {<1,1>,<2,2>,<3,3>} （6分）7?~* = （<3,1>,<2,2>,<1,3>} （9分）r（S） = （<l,l>,<2,2>,<3,3>} （12分）说明：对于每一个求解项，如果部分正确，可以给对应1分・16.解：（1）（2）邻接矩阵10 0.(3)deg(pi) = 2deg(v2)=2deg(v3)=Odcg(vj = 2 (9 分)(4)补图(12 分)17.解门(PVQ)VR«=>(-, PA-i Q)VR 析取范式(5分)PVR)A(n QVR) (7分)«((n PVK)V(QA-i Q))A(-| QVR) (9分) E((I P VK) V(QA-i Q))A((n QV^>V(P An P)) (10分)«(-i PVR VQ) A(" VR Vi Q) A(i QVk VP)A(i QVRV") ⑴分) «(PV-i QVR)A(i PVQVR)A(rPVi QVR) 主合取范式(12 分)六、证明题(本题共8分)18.证明：(Di PVQ P(1 分)<2)P P(附加前提) (3分)(3)Q T(l)(2)/ (5 分)(4)PAQ T(2)(3)/ (6 分)(5)n(i PV-i Q) T(4)E (7 分)(6)P^n (n PV-i Q) CP 规则(8 分)说明：(D因证明过程中，公式引用的次序可以不同，一般引用前提正确得1分，利用两个公式得出有效结论得1或2分，最后得出结论得2或1分.(2)可以用真值表验证.采用反证法可参照给分.。