国家开放大学电大本科《离散数学》2024-2025期末试题及答案(试卷号：1009)

精选-可编辑修改-中央电大离散数学（本科）考试试题一、单项选择题（每小题3分，本题共15分）1．若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( a )．A ．A ⊂B ，且A ∈B B ．B ⊂A ，且A ∈BC ．A ⊂B ，且A ∉BD ．A ⊄B ，且A ∈B2．设有向图（a ）、（b ）、（c ）与（d ）如图一所示，则下列结论成立的是 ( d )．图一A ．（a ）是强连通的B ．（b ）是强连通的C ．（c ）是强连通的D ．（d ）是强连通的3．设图G 的邻接矩阵为 ⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡010*******000011100100110则G 的边数为( b )．A ．6B ．5C ．4D ．34．无向简单图G 是棵树，当且仅当( a )．A ．G 连通且边数比结点数少1B ．G 连通且结点数比边数少1C ．G 的边数比结点数少1D ．G 中没有回路．5．下列公式 ( c )为重言式．A ．⌝P ∧⌝Q ↔P ∨QB ．(Q →(P ∨Q)) ↔(⌝Q ∧(P ∨Q))C ．(P →(⌝Q →P))↔(⌝P →(P →Q))D ．(⌝P ∨(P ∧Q)) ↔Q1．若集合A ={a ，b }，B ={ a ，b ，{ a ，b }}，则（ a ）．A ．A ⊂B ，且A ∈B B ．A ∈B ，但A ⊄BC ．A ⊂B ，但A ∉BD ．A ⊄B ，且A ∉B2．集合A ={1, 2, 3, 4, 5, 6, 7, 8}上的关系R ={<x ，y >|x +y =10且x , y ∈A }，则R 的性质为（ b ）．A ．自反的B ．对称的C ．传递且对称的D ．反自反且传递的3．如果R 1和R 2是A 上的自反关系，则R 1∪R 2，R 1∩R 2，R 1-R 2中自反关系有（ b ）个．A ．0B ．2C ．1D ．34．如图一所示，以下说法正确的是 ( d ) ．A ．{(a, e )}是割边B ．{(a, e )}是边割集C ．{(a, e ) ,(b, c )}是边割集D ．{(d , e )}是边割集图一5．设A （x ）：x 是人，B （x ）：x 是学生，则命题“不是所有人都是学生”可符号化为（ c ）．A ．(∀x)(A(x)∧B(x))B ．┐(∃x)(A(x)∧B(x))C ．┐(∀x)(A(x) →B(x))D ．┐(∃x)(A(x)∧┐B(x))1．设A ={a , b }，B ={1, 2}，R 1，R 2，R 3是A 到B 的二元关系，且R 1={<a ，2>, <b ，2>}，R 2={<a ，1>, <a ，2>, <b ，1>}，R 3={<a ，1>, <b ，2>}，则（ b ）不是从A 到B 的函数．A ．R 1和R 2B ．R 2C ．R 3D ．R 1和R 32．设A ={1, 2, 3, 4, 5, 6, 7, 8}，R 是A 上的整除关系，B ={2, 4, 6}，则集合B 的最大元、最小元、上界、下界依次为 ( b )．A ．8、2、8、2B ．无、2、无、2C ．6、2、6、2D ．8、1、6、13．若集合A 的元素个数为10，则其幂集的元素个数为（ a ）．A ．1024B ．10C ．100D ．14．设完全图K n 有n 个结点(n ≥2)，m 条边，当（ c ）时，K n 中存在欧拉回路．精选-可编辑修改- A ．m 为奇数 B ．n 为偶数 C ．n 为奇数 D ．m 为偶数5．已知图G 的邻接矩阵为，则G 有（ d ）．A ．5点，8边B ．6点，7边C ．6点，8边D ．5点，7边1．若集合A ＝{ a ，{a}，{1，2}}，则下列表述正确的是( c )．A ．{a ，{a}}∈AB ．{2}⊆AC ．{a}⊆AD ．∅∈A2．设图G ＝<V, E>，v∈V ，则下列结论成立的是 ( c ) ． A ．deg(v)=2∣E ∣ B ． deg(v)=∣E ∣ C ．E v V v 2)deg(=∑∈ D ．E v V v =∑∈)deg(3．命题公式（P ∨Q ）→R 的析取范式是 ( d )A ．⌝（P ∨Q ）∨RB ．（P ∧Q ）∨RC ．（P ∨Q ）∨RD ．（⌝P ∧⌝Q ）∨R4．如图一所示，以下说法正确的是 ( a )．A ．e 是割点B ．{a, e}是点割集C ．{b, e}是点割集D ．{d}是点割集5．下列等价公式成立的为( b )．A ．⌝P ∧⌝Q ⇔P ∨QB ．P →(⌝Q →P) ⇔⌝P →(P →Q)C ．Q →(P ∨Q) ⇔⌝Q ∧(P ∨Q)D ．⌝P ∨(P ∧Q) ⇔Q1．若G 是一个汉密尔顿图，则G 一定是( d )．A ．平面图B ．对偶图C ．欧拉图D ．连通图2．集合A={1, 2, 3, 4}上的关系R={<x ，y>|x=y 且x, y ∈A}，则R 的性质为（ c ）．A ．不是自反的B ．不是对称的C ．传递的D ．反自反3．设集合A={1，2，3，4，5}，偏序关系≤是A 上的整除关系，则偏序集<A ，≤>上的元素5是集合A 的（b ）．A ．最大元B ．极大元C ．最小元D ．极小元4．图G 如图一所示，以下说法正确的是 ( c ) ．A ．{(a, d)}是割边B ．{(a, d)}是边割集C ．{(a, d) ,(b, d)}是边割集D ．{(b, d)}是边割集图一5．设A （x ）：x 是人，B （x ）：x 是工人，则命题“有人是工人”可符号化为（ a ）．A ．(∃x)(A(x)∧B(x))B ．(∀x)(A(x)∧B(x))C ．┐(∀x)(A(x) →B(x))D ．┐(∃x)(A(x)∧┐B(x))1．若集合A ＝{ a ，{a}}，则下列表述正确的是( a )．A ．{a}⊆AB ．{{{a}}}⊆AC ．{a ，{a}}∈AD ．∅∈A2．命题公式（P ∨Q ）的合取范式是 ( c )A ．（P ∧Q ）B ．（P ∧Q ）∨（P ∨Q ）C ．（P ∨Q ）D ．⌝（⌝P ∧⌝Q ）3．无向树T 有8个结点，则T 的边数为( b )．A ．6B ．7C ．8D ．94．图G 如图一所示，以下说法正确的是 ( b )．A ．a 是割点B ．{b, c}是点割集C ．{b, d}是点割集D ．{c}是点割集图一5．下列公式成立的为( d )．A ．⌝P ∧⌝Q ⇔ P ∨QB ．P →⌝Q ⇔ ⌝P →Q精选-可编辑修改- C ．Q →P ⇒ P D ．⌝P ∧(P ∨Q)⇒Q1．“小于5的非负整数集合”采用描述法表示为___a___．A ．{x ∣x ∈N, x<5 }B ．{x ∣x ∈R, x<5 }C ．{x ∣x ∈Z, x<5 }D ．{x ∣x ∈Q, x<5 }2．设R1，R2是集合A={a,b,c,d}上的两个关系，其中R1={(a,a),(b,b),(b,c), (d,d)}，R2={(a,a),(b,b),(b,c),(c,b),(d,d)}，则R2是R1的__b____闭包．A ．自反B ．对称C ．传递D ．以上答案都不对3．设函数f ：R →R ，f(a)=2a+1；g ：R →R ，g(a)=a2，则___c___有反函数．A ．f gB ．g fC ．fD ．g4．已知图G 的邻接矩阵为⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛0111110101110001000111010，则图G 有___d___．A ．5点，8边B ．6点，7边C ．6点，8边D ．5点7边5．无向完全图K4是___a___．A ．汉密尔顿图B ．欧拉图C ．非平面图D ．树6．在5个结点的完全二叉树中，若有4条边，则有___b___片树叶．A ．2B ．3C ．4D ．57．无向树T 有7片树叶，3个3度结点，其余的都是4度结点，则T 有__c___个4度结点．A ．3B ．2C ．1D ．08．与命题公式P →（Q →R ）等值的公式是___a___．A ．(P ∧Q)→RB ．(P ∨Q)→RC ．(P →Q)→RD ．P →(Q ∨R) 9．谓词公式)())()((x Q y yR x P x →∃∨∀中量词∀x 的辖域是___b___． A ．))()((y yR x P x ∃∨∀ B ．)()(y yR x P ∃∨ C ．P(x) D ．)(x Q 10．谓词公式))()(()(x xQ x Q x x xP ⌝∃→⌝∀→∀的类型是___c___． A ．蕴涵式 B ．永假式C ．永真式D ．非永真的可满足式1．设A={1,2,3,4}，B={1,3}，C={-1,0,1,2}，则___a___．A ．AB ⊆ B ．C B ⊆C ．A B ∈D ．C B ∈2．若集合A 的元素个数为10，则其幂集的元素个数为___b___．A ．1000B ．1024C ．1D ．10 3．设集合A={1,2}，B={a,b}，C={α}，则=⨯⨯C B A )(__c____． A ．{<1,a,α>,<1,b,α>,<2,a,α>,<2,b,α>}B ．{<1,<a,α>>,<1,<b,α>>,<2,<a,α>>,<2,<b,α>>}C ．{<<1,a>,α>,<<1,b>,α>,<<2,a>,α>,<<2,b>,α>}D ．{{1,2},{a,b},{α}}4．设A={1, 2, 3, 4, 5, 6, 7, 8}，R 是A 上的整除关系，B={2, 4, 6}，则集合B 的最大元、最小元、上界、下界依次为___d___．A ．8、1、6、1B ． 8、2、8、2C ．6、2、6、2D ．无、2、无、25．有5个结点的无向完全图K5的边数为___a___．A ．10B ．20C ．5D ．256．设完全图K n 有n 个结点(n ≥2)，m 条边，当___b___时，K n 中存在欧拉回路．A ．n 为偶数B ．n 为奇数C ．m 为偶数D ．m 为奇数7．一棵无向树T 有5片树叶，3个2度分支点，其余的分支点都是3度顶点，则T 有__c___个顶点．A ．3B ．8C ．11D ．138．命题公式（P ∨Q ）→R 的析取范式是___b___．A ．（⌝P ∧⌝Q ）∨RB ． ⌝（P ∨Q ）∨RC ．（P ∧Q ）∨RD ．（P ∨Q ）∨R9．下列等价公式成立的是___b___．A ．⌝P ∧⌝Q ⇔P ∨QB ． P →(⌝Q →P) ⇔⌝P →(P →Q)C ．⌝P ∨(P ∧Q) ⇔QD ．Q →(P ∨Q) ⇔⌝Q ∧(P ∨Q) 10．谓词公式))()(()(x xQ x Q x x xP ⌝∃→⌝∀→∀的类型是__c____． A ．蕴涵式 B ．永假式C ．永真式D ．非永真的可满足式二、填空题（每小题3分，本题共15分）6．命题公式)(P Q P ∨→的真值是 T （或1） ．7．若图G=<V , E>中具有一条汉密尔顿回路，则对于结点集V 的每个非空子集S ，在G 中删除S 中的所有结点得到的连通分支数为W ，则S 中结点数|S|与W 满足的关系式为 W ≤|S| ．精选-可编辑修改-8．给定一个序列集合{000，001，01，10，0}，若去掉其中的元素 0 ，则该序列集合构成前缀码．9．已知一棵无向树T 中有8个结点，4度，3度，2度的分支点各一个，T 的树叶数为 5 ．10．(∀x )(P (x )→Q (x )∨R (x ，y ))中的自由变元为R (x ，y )中的y6．若集合A 的元素个数为10，则其幂集的元素个数为 1024 ．7．设A ={a ，b ，c }，B ={1，2}，作f ：A →B ，则不同的函数个数为 8 ． 8．若A ={1,2}，R ={<x , y >|x ∈A , y ∈A , x +y =10}，则R 的自反闭包为{<1,1>,<2,2>}．9．结点数v 与边数e 满足 e=v -1 关系的无向连通图就是树．6．设集合A ＝{a ，b }，那么集合A 的幂集是{∅,{a ,b },{a },{b }}．7．如果R 1和R 2是A 上的自反关系，则R 1∪R 2，R 1∩R 2，R 1-R 2中自反关系有 2 个．8．设图G 是有6个结点的连通图，结点的总度数为18，则可从G 中删去 4 条边后使之变成树．9．设连通平面图G 的结点数为5，边数为6，则面数为 3 ．10．设个体域D ＝{a , b }，则谓词公式(∀x )A (x )∧（∃x ）B （x ）消去量词后的等值式为(A (a )∧A (b ))∧(B （a ）∨B （b ）) ．6．设集合A ={0, 1, 2, 3}，B ={2, 3, 4, 5}，R 是A 到B 的二元关系， },,{B A y x B y A x y x R ⋂∈∈∈><=且且则R 的有序对集合为{<2, 2>，<2, 3>，<3, 2>}，<3, 3>．7．设G 是连通平面图，v , e , r 分别表示G 的结点数，边数和面数，则v ，e 和r 满足的关系式v -e +r =2 ．8．设G ＝<V , E >是有6个结点，8条边的连通图，则从G 中删去 3 条边，可以确定图G 的一棵生成树．9．无向图G 存在欧拉回路，当且仅当G 连通且所有结点的度数全为偶数10．设个体域D ＝{1,2}，则谓词公式)(x xA ∃消去量词后的等值式为A (1)∨A (2)6．命题公式)(P Q P ∨→的真值是 T （或1） ．7．若图G=<V , E>中具有一条汉密尔顿回路，则对于结点集V 的每个非空子集S ，在G 中删除S 中的所有结点得到的连通分支数为W ，则S 中结点数|S|与W 满足的关系式为 W ≤|S| ．8．给定一个序列集合{000，001，01，10，0}，若去掉其中的元素 0 ，则该序列集合构成前缀码．9．已知一棵无向树T 中有8个结点，4度，3度，2度的分支点各一个，T 的树叶数为 5 ．10．(∀x )(P (x )→Q (x )∨R (x ，y ))中的自由变元为R (x ，y )中的y6．若集合A 的元素个数为10，则其幂集的元素个数为 1024 ．7．设A ={a ，b ，c }，B ={1，2}，作f ：A →B ，则不同的函数个数为 8 ． 8．若A ={1,2}，R ={<x , y >|x ∈A , y ∈A , x +y =10}，则R 的自反闭包为{<1,1>,<2,2>}．9．结点数v 与边数e 满足 e=v -1 关系的无向连通图就是树．10．设个体域D ＝{a , b , c }，则谓词公式(∀x )A (x )消去量词后的等值式为A (a ) ∧A (b )∧A （c ）6．若集合A={1，3，5，7}，B ={2，4，6，8}，则A ∩B =空集（或∅） ．7．设集合A ={1，2，3}上的函数分别为：f ={<1,2>,<2,1>,<3,3>,}，g ={<1,3>,<2,2>,<3,2>,}，则复合函数g ︒f ={<1, 2>, <2, 3>, <3, 2>,}8．设G 是一个图，结点集合为V ，边集合为E ，则G 的结点度数之和为2|E |（或“边数的两倍”）9．无向连通图G 的结点数为v ，边数为e ，则G 当v 与e 满足 e=v -1 关系时是树．10．设个体域D ＝{1, 2, 3}， P (x )为“x 小于2”，则谓词公式(∀x )P (x ) 的真值为假（或F ，或0） ．6．设集合A ={2, 3, 4}，B ={1, 2, 3, 4}，R 是A 到B 的二元关系，},{y x B y A x y x R ≤∈∈><=且且则R 的有序对集合为{<2, 2>，<2, 3>，<2, 4>，<3, 3>}，<3, 4>，<4, 4>}7．如果R 是非空集合A 上的等价关系，a ∈A ，b ∈A ，则可推知R 中至少包含<a , a >，< b , b >等元素．8．设G ＝<V , E >是有4个结点，8条边的无向连通图，则从G 中删去 5 条边，可以确定图G 的一棵生成树．9．设G 是具有n 个结点m 条边k 个面的连通平面图，则m 等于n +k -210．设个体域D ＝{1, 2}，A (x )为“x 大于1”，则谓词公式()()x A x ∃的真值为真（或T ，或1）11．设集合A ={1,2,3}，用列举法写出A 上的恒等关系I A ，全关系E A ：I A = __ I A ={<1,1>,<2,2>,<3,3>}；E A ={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}12．设集合A ＝{a ，b }，那么集合A 的幂集是{∅,{a },{b },{a ,b }}13．设集合A ={1,2,3}，B ={a ,b }，从A 到B 的两个二元关系R ={<1,a >,<2,b >,<3,a >}，S={<1,a >,<2,a >,<3,a >}，则R -S =_ R -S ={<2,b >}．14．设G 是连通平面图，v , e , r 分别表示G 的结点数，边数和面数，则v ，e 和r 满足的关系式v -e +r =2．15．无向连通图G 是欧拉图的充分必要条件是结点度数均为偶数．16．设G ＝<V , E >是有6个结点，8条边的连通图，则从G 中删去 3 条边，可以确定图G 的一棵生成树．17．设G 是完全二叉树，G 有15个结点，其中有8个是树叶，则G 有____14___条边，G 的总度数是___28_____，G 的分支点数是____7____．18．设P ，Q 的真值为1，R ，S 的真值为0，则命题公式Q S R Q P ∧∨∧∨)(的真值为___0_____．19．命题公式)(R Q P →∧的合取范式为)(R Q P ∨⌝∧析取范式为)()(R P Q P ∧∨⌝∨20．设个体域为整数集，公式)0(=+∃∀y x y x 真值为___1_____．11．设集合A ={1,2,3,4}，B ={3,4,5,6}，则：=B A ___{3,4}_____，=B A _____{1,2,3,4,5,6}_____．12．设集合A 有n 个元素，那么A 的幂集合P (A )的元素个数为 ．13．设集合A ={a ,b ,c ,d }，B ={x ,y ,z }，R ={<a ,x >,<a ,z >,<b ,y >,<c ,z >,<d ,y >}则关系矩阵M R ＝⎪⎪⎪⎪⎪⎭⎫⎝⎛010100010101．精选-可编辑修改-14．设集合A ={a ,b ,c ,d ,e }，A 上的二元关系R ={<a ,b >,<c ,d >,<b ,b >}，S ={<d ,b >,<b ,e >,<c ,a >}，则R ·S ={<a ,e >,<c ,b >,<b ,e >}15．无向图G 存在欧拉回路，当且仅当G 连通且__所有结点的度数全为偶数16．设连通平面图G 的结点数为5，边数为6，则面数为 3 ．17．设正则二叉树有n 个分支点，且内部通路长度总和为I ，外部通路长度总和为E ，则有E =___ I +2n18．设P ，Q 的真值为0，R ，S 的真值为1，则命题公式)()(S Q R P ∨→∨的真值为_____1___．19．已知命题公式为G ＝(⌝P ∨Q )→R ，则命题公式G 的析取范式是(P ∧⌝Q )∨R20．谓词命题公式(∀x )(P (x )→Q (x )∨R (x ，y ))中的约束变元为___x___．三、逻辑公式翻译（每小题4分，本题共12分）11．将语句“如果所有人今天都去参加活动，则明天的会议取消．”翻译成命题公式．设P ：所有人今天都去参加活动，Q ：明天的会议取消， （1分）P → Q ． （4分）12．将语句“今天没有人来．” 翻译成命题公式．设 P ：今天有人来， （1分）⌝ P ． （4分）13．将语句“有人去上课．” 翻译成谓词公式．设P(x)：x 是人，Q(x)：x 去上课， （1分）(∃x)(P(x) ∧Q(x))． （4分）11．将语句“如果你去了，那么他就不去．”翻译成命题公式．设P ：你去，Q ：他去， （1分）P →⌝Q ． （4分）12．将语句“小王去旅游，小李也去旅游．”翻译成命题公式．设P ：小王去旅游，Q ：小李去旅游， （1分）P ∧Q ． （4分）13．将语句“所有人都去工作．”翻译成谓词公式．设P(x)：x 是人，Q(x)：x 去工作， （1分）(∀x)(P(x)→Q(x))． （4分）11．将语句“他不去学校．”翻译成命题公式．设P ：他去学校， （1分）⌝ P ． （4分）12．将语句“他去旅游，仅当他有时间．”翻译成命题公式．设 P ：他去旅游，Q ：他有时间， （1分）P →Q ． （4分）13．将语句“所有的人都学习努力．”翻译成命题公式．设P(x)：x 是人，Q(x)：x 学习努力， （1分）（∀x ）(P(x)→Q(x))． （3分）11．将语句“尽管他接受了这个任务，但他没有完成好．”翻译成命题公式．设P ：他接受了这个任务，Q ：他完成好了这个任务， （2分）P ∧⌝ Q ． （6分）12．将语句“今天没有下雨．”翻译成命题公式．设P ：今天下雨， （2分）⌝ P ． （6分）11．将语句“他是学生．”翻译成命题公式．设P ：他是学生， （2分）则命题公式为： P ． （6分）12．将语句“如果明天不下雨，我们就去郊游．”翻译成命题公式．设P ：明天下雨，Q ：我们就去郊游， （2分）则命题公式为：⌝ P → Q ． （6分）11．将语句“今天考试，明天放假．”翻译成命题公式．设P ：今天考试，Q ：明天放假． （2分）则命题公式为：P ∧Q ． （6分）12．将语句“我去旅游，仅当我有时间．”翻译成命题公式．设P ：我去旅游，Q ：我有时间， （2分）则命题公式为：P →Q ． （6分）⑴ 将语句“如果明天不下雨，我们就去春游．”翻译成命题公式．⑵ 将语句“有人去上课．” 翻译成谓词公式．⑴设命题P 表示“明天下雨”，命题Q 表示“我们就去春游”.则原语句可以表示成命题公式 ⌝P →Q. （5分）⑵设P(x)：x 是人，Q(x)：x 去上课则原语句可以表示成谓词公式 (∃x)(P(x) ∧Q(x))．四、判断说明题（每小题7分，本题共14分）14．┐P ∧（P →┐Q ）∨P 为永真式．正确． （3分）┐P ∧（P →┐Q ）∨P 是由┐P ∧（P →┐Q ）与P 组成的析取式，如果P 的值为真，则┐P ∧（P →┐Q ）∨P 为真， （5分）精选-可编辑修改-如果P 的值为假，则┐P 与P →┐Q 为真，即┐P ∧（P →┐Q ）为真，也即┐P ∧（P →┐Q ）∨P 为真，所以┐P ∧（P →┐Q ）∨P 是永真式． （7分）15．若偏序集<A ，R>的哈斯图如图一所示，则集合A 的最大元为a ，最小元不存在．正确． （3分）对于集合A 的任意元素x ，均有<x, a>∈R （或xRa ），所以a 是集合A 中的最大元．（5分）14．如果R1和R2是A 上的自反关系，则R1∪R2是自反的．正确． （3分）R1和R2是自反的，∀x ∈A ，<x, x> ∈ R1，<x, x> ∈R2，则<x, x> ∈ R1⋃R2，所以R1∪R2是自反的． （7分）15．如图二所示的图G 存在一条欧拉回路．正确． （3分）因为图G 为连通的，且其中每个顶点的度数为偶数． （7分）14．设N 、R 分别为自然数集与实数集，f ：N →R ，f (x)=x+6，则f 是单射．正确． （3分）设x1，x2为自然数且x1≠x2，则有f(x1)= x1+6≠ x2+6= f(x2)，故f 为单射． （7分）15．设G 是一个有6个结点14条边的连通图，则G 为平面图．错误． （3分）不满足“设G 是一个有v 个结点e 条边的连通简单平面图，若v ≥3，则e ≤3v-6．”13．下面的推理是否正确，试予以说明．(1) （∀x ）F （x ）→G （x ） 前提引入(2) F （y ）→G （y ） US （1）．错误． （3分）（2）应为F （y ）→G （x ），换名时，约束变元与自由变元不能混淆． （7分）14．若偏序集<A ，R>的哈斯图如图二所示，则集合A 的最大元为a ，最小元不存在．错误． （3分）集合A 的最大元不存在，a 是极大元． （7分）13．下面的推理是否正确，试予以说明．(1) （∀x ）F （x ）→G （x ） 前提引入(2) F （y ）→G （y ） US （1）．错误． （3分）（2）应为F （y ）→G （x ），换名时，约束变元与自由变元不能混淆． （7分）14．如图二所示的图G 存在一条欧拉回路．v 1v 图二精选-可编辑修改-错误． （3分）因为图G 为中包含度数为奇数的结点． （7分）13．如果图G 是无向图，且其结点度数均为偶数，则图G 是欧拉图．错误． （3分）当图G 不连通时图G 不为欧拉图． （7分）14．若偏序集<A ，R>的哈斯图如图二所示，则集合A 的最大元为a ，最小元是f ．图二错误． （3分）集合A 的最大元与最小元不存在，a 是极大元，f 是极小元，．五．计算题（每小题12分，本题共36分）16．设集合A={1，2，3，4}，R={<x, y>|x, y ∈A ；|x -y|=1或x -y=0}，试（1）写出R 的有序对表示；（2）画出R 的关系图；（3）说明R 满足自反性，不满足传递性．（1）R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>} （3分）（2）关系图为（6分）（3）因为<1,1>,<2,2>,<3,3>,<4,4>均属于R ，即A 的每个元素构成的有序对均在R 中，故R 在A 上是自反的。

2020-2021《离散数学》期末课程考试试卷A一、填空题（每空3分，共15分）1．命题公式)(r q p p ∨∨→的类型是 。

2．设p ：我将去镇上。

q ：我有时间。

则命题“我将去镇上，仅当我有时间。

”的符号化形式为 。

3．化简下面集合表达式：)())((C B A C A B -= 。

4．已知一有向图的D 的度序列为（2,3,2,3），出度序列为（1,2,1,1），则D 的入度序列为 。

5．5个顶点的非同构的无向树共有 棵。

二、选择题（单项选择题，每题3分，共30分）1．设命题公式)(p q p ⌝→∧，记作A ，则使A 的真值指派为1的p ，q 的取值是（ ）。

A 、00B 、 01C 、10D 、112．设p ：你努力。

q ：你将失败。

则命题“除非你努力，否则你将失败。

”符号化为（ ）。

A 、p →q B 、q →p C 、┐p →q D 、┐q →p 3．下列公式中不与)(q p ↔⌝等值的是（ ）。

A 、)()(q p q p ∨⌝∧⌝∨B 、)()(q p q p ∧⌝∨⌝∧C 、q p ↔⌝D 、q p ⌝↔4．下面公式正确的是（ ）。

A 、)()())()((x xB x xA x B x A x ∀∨∀⇔∨∀ B 、)()())()((x xB x xA x B x A x ∃∨∃⇔∨∃C 、)())((x xB A x B A x ∃→⇔→∀D 、)()(x A x x xA ⌝∃⇔⌝∃5．下列命题错误的是（ ）。

A 、}},,{,,,{},{c b a c b a b a ⊆ B 、}},{,,,{},{b a c b a b a ∈ C 、}}},{{,,{},{b a b a b a ⊆D 、}}},{{,,{},{b a b a b a ∈6．设R={<x,y>|x,y ∈R ，x-y+2>0且x-y-2<0}，则R 具有的性质是（ ）。

离散数学期末考试试题及答案离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。

下面是小编整理的离散数学期末考试试题及答案，欢迎阅读参考！一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。

1、在由3个元素组成的集合上，可以有 ( ) 种不同的关系。

[A] 3 [B] 8 [C]9 [D]272、设A1,2,3,5,8,B1,2,5,7,则AB( )。

[A] 3,8 [B]3 [C]8 [D]3,83、若X是Y的子集，则一定有( )。

[A]X不属于Y [B]X∈Y[C]X真包含于Y [D]X∩Y=X4、下列关系中是等价关系的'是( )。

[A]不等关系 [B]空关系[C]全关系 [D]偏序关系5、对于一个从集合A到集合B的映射，下列表述中错误的是( )。

[A]对A的每个元素都要有象 [B] 对A的每个元素都只有一个象[C]对B的每个元素都有原象 [D] 对B的元素可以有不止一个原象6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为( )。

[A]p→q [B]q→p [C]┐q→┐p [D]┐p→q7、设A={a,b,c},则A到A的双射共有( )。

[A]3个 [B]6个 [C]8个 [D]9个8、一个连通G具有以下何种条件时，能一笔画出：即从某结点出发，经过中每边仅一次回到该结点( )。

[A] G没有奇数度结点 [B] G有1个奇数度结点[C] G有2个奇数度结点 [D] G没有或有2个奇数度结点9、设〈G,*〉是群，且|G|>1，则下列命题不成立的是( )。

[A] G中有幺元 [B] G中么元是唯一的[C] G中任一元素有逆元 [D] G中除了幺元外无其他幂等元10、令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为( )[A] p→┐q [B] p∨┐q[C] p∧q [D] p∧┐q11、设G=的结点集为V={v1,v2,v3},边集为E={,}.则G的割(点)集是( )。

国家开放大学电大本科《离散数学> 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)可以用真值表验证.采用反证法可参照给分.。