2020年电大离散数学(本)期末考试题库及答案

精选-可编辑修改-中央电大离散数学（本科）考试试题一、单项选择题（每小题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 上是自反的。

一．填空题（每小题2分，共10分）1. 谓词公式)()(x xQ x xP ∃→∀的前束范式是___________。

2. 设全集{}{}{},5,2,3,2,1,5,4,3,2,1===B A E 则A ∩B =____，=A _____，=B A __ _____3. 设{}{}b a B c b a A ,,,,==，则=-)()(B A ρρ__ __________，=-)()(A B ρρ_____ ______。

二．选择题（每小题2分，共10分）1. 与命题公式)(R Q P →→等价的公式是（ ）（A ）R Q P →∨)( （B ）R Q P →∧)( （C ）)(R Q P ∧→ （D ）)(R Q P ∨→ 2. 设集合{}c b a A ,,=,A 上的二元关系{}><><=b b a a R ,,,不具备关系( )性质 （A ） (A)传递性 (B)反对称性 (C)对称性 (D)自反性 三．计算题（共43分）1. 求命题公式r q p ∨∧的主合取范式与主析取范式。

（6分）2. 设集合{}d c b a A ,,,=上的二元关系R 的关系矩阵为⎪⎪⎪⎪⎪⎭⎫⎝⎛=1000000011010001R M ,求)(),(),(R t R s R r 的关系矩阵，并画出R ，)(),(),(R t R s R r 的关系图。

（10分）5. 试判断),(≤z 是否为格？说明理由。

（5分）（注：什么是格？Z 是整数，格：任两个元素，有最小上界和最大下界的偏序）四．证明题（共37分）1. 用推理规则证明D D A C C B B A ⌝⇒∧⌝⌝⌝∧∨⌝→)(,)(,。

（10分）2. 设R 是实数集，b a b a f R R R f +=→⨯),(,:，ab b a g R R R g =→⨯),(,:。

求证：gf 和都是满射，但不是单射。

（10分）一，1, _∃x∃y¬P(x)∨Q(y)2, {2} {4,5} {1,3,4,5}3, {{c},{a,c},{b,c},{a,b,c}} Φ_二，B D三，解：主合取方式：p∧q∨r⇔(p∨q∨r)∧(p∨¬q∨r)∧(¬p∨q∨r)= ∏0.2.4 主析取范式：p∧q∨r⇔(p∧q∧r) ∨(p∧q∧¬r)∨(¬p∧q∧r) ∨(¬p∧¬q∧r) ∨(p∧¬q ∧r)=∑1.3.5.6.7四，1，证明：编号公式依据（1）（¬B∨C）∧¬C前提（2）¬B∨C，¬C（1）（3）¬B（2）（4）A→B （3）（5）¬A（3）（4）（6）¬（¬A∧D）前提（7）A∨¬D（6）（8）¬D（5）（6）2，证明：要证f是满射，即∀y∈R,都存在（x1，x2）∈R×R，使f（x1，x2）=y，而f（x1，x2）=x1+x2，可取x1=0，x2=y，即证得；再证g是满射，即∀y∈R，,都存在（x1，x2）∈R×R，使g（x1，x2）=y，而g（x1，x2）=x1x2，可取x1=1，x2=y，即证得；最后证f不是单射，f（x1，x2）=f（x2，x1）取x1≠x2，即证得，同理：g（x1，x2）=g（x2，x1），取x1≠x2，即证得。

离散数学期末考试题及答案一、选择题（每题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}的幂集含有__个元素。

一、填空2．A ，B ，C4．公式的主合取范式为5 在I 下真值为 1 。

6．设A=｛1，2，3，4｝,A 上关系图如下,则 R^2= ｛(1,1），（1，3）,(2，2）,(2,4)｝ 。

//备注:7．设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 ，＊>的幺元是 a ,有逆元的元素为 a ，b,c ，d ，它们的逆元分别为 a ，b ，c ，d . //备注：二元运算为x*y=max{x,y}，x,y A 。

10．下图所示的偏序集中，是格的为 c .//（注：什么是格？即任意两个元素有最小上界 和最大下界的偏序）二、选择题1、下列是真命题的有（ C 、D ）A ． ；B ．；C ． ；D ．。

2、下列集合中相等的有（ B 、C ）A ．｛4，3｝；B ．｛，3,4｝；C ．｛4,，3，3｝;D ． {3,4｝.3、设A={1，2,3},则A 上的二元关系有（ C ）个.A ． 23 ；B ． 32 ；C ． ；D ． 。

//备注：A 的二元关系个数为:个。

4、设R ，S 是集合A 上的关系，则下列说法正确的是（ A )A ．若R ，S 是自反的， 则是自反的；B ．若R ，S 是反自反的， 则是反自反的； XC ．若R ，S 是对称的， 则是对称的； XD ．若R ，S 是传递的， 则是传递的。

X//备注：设R=｛<3，3>,<6，2〉}，S={<2，3〉}, 则={<6，3>} , ={<2,3〉｝5、设A=｛1，2，3，4}，P （A)（A 的幂集）上规定二元系如下，则P （A)/ R=( D ）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 上包含关系“”的哈斯图为（ C )//例题:画出下列各关系的哈斯图1）P=｛1,2，3，4},〈P,≤〉的哈斯图。

A一、单项选择题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．在公式（）F （x ，y ）→（ y ）G （x ，y ）中变元x 是（ B ）x ∀∃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}，与公式等价的是( A ))()(x A x ∃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．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分，共20分）1. 以下哪个选项是图的边数与顶点数的关系？A. 边数小于顶点数B. 边数等于顶点数C. 边数大于顶点数D. 边数与顶点数无固定关系答案：D2. 有限自动机的英文缩写是什么？A. FAB. PDAC. TMAD. NFA答案：A3. 布尔代数中，德摩根定律是指什么？A. ¬(A ∧ B) 等于¬ A ∨ ¬ BB. ¬(A ∨ B) 等于¬ A ∧ ¬ BC. A ∧ B 等于¬(A ∨ B)D. A ∨ B 等于¬(¬ A ∧ ¬B)答案：B4. 在命题逻辑中，以下哪个符号表示蕴含？A. ∧B. ∨C. →D. ↔答案：C5. 集合A = {1, 2, 3}，B = {2, 3, 4}，则A ∪ B等于：A. {1, 2, 3, 4}B. {1, 2, 3}C. {2, 3, 4}D. {1, 3, 4}答案：A6. 以下哪个选项是正确的递归定义？A. 一个数是偶数当且仅当它是2的倍数B. 一个数是偶数当且仅当它不是2的倍数C. 一个数是偶数当且仅当它是另一个偶数加1D. 以上都是正确的递归定义答案：A7. 有向图和无向图的主要区别是什么？A. 有向图的边有方向，无向图的边没有方向B. 有向图的顶点有方向，无向图的顶点没有方向C. 有向图的边可以相交，无向图的边不可以相交D. 有向图可以有环，无向图不可以有环答案：A8. 在命题逻辑中，以下哪个公式是矛盾的？A. A ∧ ¬ AB. A ∨ ¬ AC. A → BD. A ∧ B ∧ ¬ A答案：A9. 以下哪个是图的同义术语？A. 网络B. 矩阵C. 树D. 以上全部答案：A10. 以下哪个命题逻辑公式是有效的？A. (A → B) ∧ (B → A)B. (A ∧ B) → AC. (A ∨ B) → AD. (A ∧ B) → B答案：B二、填空题（每题2分，共20分）11. 在命题逻辑中，_________ 表示一个命题是真的，而 _________ 表示一个命题是假的。

大学离散数学期末考试题库和答案一、单项选择题（每题2分，共20分）1. 在集合论中，以下哪个符号表示“属于”？A. ∈B. ∉C. ⊆D. ⊂答案：A2. 如果A和B是两个集合，那么A∪B表示什么？A. A和B的交集B. A和B的并集C. A和B的差集D. A和B的补集答案：B3. 以下哪个命题是真命题？A. ∀x∈N, x^2 > xB. ∃x∈N, x^2 = x + 1C. ∀x∈N, x^2 ≥ xD. ∃x∈N, x^2 < x答案：C4. 在图论中，一个无向图的边数为E，顶点数为V，那么这个图的生成树的边数是多少？A. EB. V-1C. VD. E-1答案：B5. 以下哪个算法是用于解决旅行商问题（TSP）的？A. 动态规划B. 贪心算法C. 分支限界法D. 回溯法答案：D6. 在逻辑中，以下哪个符号表示“蕴含”？A. ∧B. ∨C. →D. ↔答案：C7. 以下哪个是二进制数？A. 1010B. 2A3C. 12BD. ZYX答案：A8. 在关系数据库中，以下哪个操作用于删除表中的行？A. SELECTB. INSERTC. UPDATED. DELETE答案：D9. 以下哪个是布尔代数的基本运算？A. 并集B. 交集C. 差集D. 所有以上答案：D10. 在离散数学中，以下哪个概念用于描述两个集合之间的关系？A. 函数B. 映射C. 序列D. 所有以上答案：D二、多项选择题（每题3分，共15分）11. 以下哪些是集合的基本运算？A. 并集B. 交集C. 差集D. 补集答案：ABCD12. 在图论中，以下哪些是图的基本类型？A. 无向图B. 有向图C. 完全图D. 二分图答案：ABCD13. 在逻辑中，以下哪些是命题逻辑的基本连接词？A. 与（∧）B. 或（∨）C. 非（¬）D. 蕴含（→）答案：ABCD14. 在关系数据库中，以下哪些是SQL的基本操作？A. SELECTB. INSERTC. UPDATED. DELETE答案：ABCD15. 在离散数学中，以下哪些是组合数学的基本概念？A. 排列B. 组合C. 二项式系数D. 图论答案：ABC三、填空题（每题3分，共30分）16. 如果集合A={1, 2, 3}，集合B={2, 3, 4}，那么A∩B=______。

离散数学（本科）考试试题一、单项选择题（每小题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∉B D．A⊄B，且A∈B2．设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是( d )．图一A．（a）是强连通的B．（b）是强连通的C．（c）是强连通的D．（d）是强连通的3．设图G的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡1111111111则G的边数为( b )．A．6 B．5 C．4 D．34．无向简单图G是棵树，当且仅当( a )．A．G连通且边数比结点数少1 B．G连通且结点数比边数少1C．G的边数比结点数少1 D．G中没有回路．5．下列公式( c )为重言式．A．⌝P∧⌝Q↔P∨Q B．(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∉B D．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．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（b ）个．A．0 B．2 C．1 D．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}，R1，R2，R3是A到B的二元关系，且R1={<a，2>, <b，2>}，R2={<a，1>, <a，2>, <b，1>}，R3={<a，1>, <b，2>}，则（ b ）不是从A到B的函数．A．R1和R2B．R2C．R3D．R1和R32．设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最大元、最小元、上界、下界依次为( b )．A．8、2、8、2 B．无、2、无、2C．6、2、6、2 D．8、1、6、13．若集合A的元素个数为10，则其幂集的元素个数为（ a ）．A．1024 B．10 C．100 D．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 →QC ．Q →P ⇒ PD ．⌝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） ．。

一．填空题1. 谓词公式)()(x xQ x xP ∃→∀的前束范式是 ∃x ∃y¬P(x)∨Q(y)2。

设全集 E=｛1，2，3，4，5},A={1,2，3｝,B={2,5}, 则A ∩B = {2} ，=A {4，5} ，=B A {1，3，4，5｝ 。

3。

设{}{}b a B c b a A ,,,,==，则=-)()(B A ρρ__｛{c ｝，｛a ，c}，｛b,c},{a,b,c}}_，=-)()(A B ρρ__Φ__。

4。

在代数系统（N,+）中，其单位元是0,仅有 单位元0 有逆元。

//x+y=0，x 的逆元= -x ，即x=05．如果连通平面图G 有n 个顶点，e 条边，则G 有__e+2-n __个面。

//点＋面-边=23 无向图G 有12条边,G 中有6个3度结点，其余结点的度数均小于3,问G 中至少有 9 个结点？//因为至少，所以 6×3+2n=12×2 解得n=3 总结点m=6+3=9二．选择题1。

与命题公式)(R Q P →→等价的公式是（ ）（A ）R Q P →∨)( (B ）R Q P →∧)( (C))(R Q P ∧→ （D ）)(R Q P ∨→3。

在图>=<E V G ,中，结点总度数与边数的关系是( C ）(A ）E v i 2)deg(= (B ） E v i =)deg(（C)∑∈=V v i E v 2)deg((D) ∑∈=V v iE v )deg(4. 设D 是有n 个结点的有向完全图,则图D 的边数为（ A ）(A ）)1(-n n (B))1(+n n (C)2/)1(+n n （D)2/)1(-n n5。

无向图G 是欧拉图，当且仅当（ C ）(A) G 的所有结点的度数都是偶数 (B ）G 的所有结点的度数都是奇数(C)G 连通且所有结点的度数都是偶数 （D) G 连通且G 的所有结点度数都是奇数。

国家开放大学电大本科《离散数学》2024-2025期末试题及答案(试卷号：1009)一、单项选择题(每小题3分，本题共16分)若集合A = {1,2,3,4},则下列表述不正确的是( ).A.{2,3)€AB.AU{1,2,3,4}C. <1,2,3,4)QAD. 16A2.若无向图G的结点度数之和为20,则G的边数为( ).A.10B. 20C. 30D. 53.无向图G是棵树，结点数为10,则G的边数为( ).A. 5B. 10C.9D. 114.设A(x)：x是人,B(x)：x是学生，则命题“有的人是学生”可符号化为( )•A.Vx)(A(x)-*B(x»B.(3x)(A(x)AB(x))C.(Vx)(A(x)AB(x»D.-«(3x)(A(x)A -B(x»5.下面的推理正确的是( ).A.(l)(Vx)F(x)->G(x) 前提引入(2)F(>-)-*G(y) US(1).B.(1)( 3 x)F(x)-*G(x) 前提引入(2)F(y)-*G(y) US(1),C.(l)(3x)(F(x)->G(x»前提引入(2)F(y)-*G(x) ES(1).D.(l)(3x)(F(x)-*G(x)) 前提引入(2)F(y)-*G(y) ESQ).二、填空题(每小题3分，本题共15分)6.设A = {1,2),H = {1,2,3},则A到B上不同的函数个数为________________ .7.有&个结点的无向完全图的边数为 ____________ .8.若无向图G中存在欧拉路但不存在欧拉回路，则G的奇数度数的结点有________ 个.9.设G是有10个结点的无向连通图，结点的度数之和为30,则从G中删去条边后使之变成树.10.设个体域£> = {1,2,3,4},则谓词公式(*)人(了)消去量词后的等值式为三、逻辑公式翻译(每小题6分，本息共12分)11.将语句“昨天下甬“翻译成命题公式.12.将语句“小王今天上午或者去看电彩或者去打球”翻译成命JS公式.四、判断说明题(判断各题正误，并说明理由.每小题7分，本黑共14分)13.存在集合A与B,使得A6B与AUB同时成立.14.完全图K<是平面图.五、计算题(每小题12分，本题共36分)15.设偏序集VA,R>的哈斯图如下,B为A的子集，其中B = 试(1)写出R的关系表达式；(2)画出关系R的关系图；(3)求出B的最大元、极大元、上界.16.设图G — <V,E>,V={vj f v it v t,Vi»v s)»(v2, v3)»(v3»vs)}»试(1)画出G的图形表示；(2)写出其邻接矩阵；(3)求出每个结点的度数；(4)画出图G的补图的图形，17.求P TQ代R)的合取范式与主合取范式.六、证明题(本题共8分)18.设A.B是任意集合，试证明：若AXA=BXB,^ A = B.M答杖松标准(仅辩者)一、单项选择题(每小题3分，本题共15分)1. A2. A3. C4.B5. D二、填空题(每小题3分，本题共］5分)6.97.”3 — 1)/2(或庆)8.210. A(l) VA(2) V A(3) V A(4)三、 逻辑公式翻译（每小题6分，本题共】2分）H,设P ：昨天下雨. 则命题公式为:P ，12. 设P ：小王今天上午去看电影 Q ：小王今天上午去打球 则命题公式为：r （PiQ ）. 或者（rPAQ ）V 〈PA rQ ）四、 判断说明题（每小题7分，本题共14分）13. 正确.例：设 A = {a} t H — {a,{a}） 则有且ACI3.说明：举出符合条件的例均给分. 14. 正确.完全图K 〈是平面图， 如K,可以如下图示嵌入平面.（7分）五、计算题（每小题12分，本题共36分）15. （l ）R = {Va ，a>,Vb,Q>,Vc,c>,Vd,d>・Va0>・Va ・c>，V&，d>，VQ,d >}. （4 分）（2）关系图(8分)（3）集合B 无最大元，极大元为6与c.无上界. 16, 解: （1）关系图（2分） （6分）（2分）（6分）（3分） （517. P TQAR) 5PV(QAR) 0(rPVQ 〉A(rPVR)合取范式<=>(-PVQ)V(K A rR)A(rPVR) 0("VQ)V(& A rR)A(" VR)V(QA -Q)D(rPVQVR)A(rPVQVA("VR VQ) A(-、PVR V -Q) c=>(-PVQV7?)A(-'PVQV-R)A(-PV-QVR) 主合取范式 六、证明题（本意共8分）18. 证明：V2（2）邻接矩阵bioir 101001001 1 00 0（6分）(3) deg(vi)=,3deg(v t )—2 <ieg(v 3)~2 deg顷)=1 deg(v s )=2 (4) 补图（9分）（】2分）（2分） （5分）（7分〉设x€A,则Vx,x>€AXA,（1 分）因AXA = BXB,故V X,X>€BXB,则有xGB, （3 分）因此AGB. （5分）设xQB,则Vx,x>€BXB,（6 分）因AXA-BXB,故Vx,x>eAXA,则有因此BWA. （7 分）故得A=B. （8分）。

离散数学期末考试题及答案1. 题目描述：以下是离散数学期末考试的题目。

请仔细阅读每个问题，并在题后给出相应的答案。

请注意，答案应尽量详细和准确，以确保得分。

1.1 命题与谓词逻辑（20分）1.1.1 什么是命题逻辑？它可以用于解决哪些问题？1.1.2 简要解释谓词逻辑的概念和其在离散数学中的应用。

1.2 集合和图论（30分）1.2.1 定义两个集合的并、交和差的概念。

1.2.2 解释有向图和无向图的区别，并给出一个实际应用中的例子。

1.3 关系和函数（40分）1.3.1 什么是关系？请给出一个实际应用中关系的例子。

1.3.2 定义函数的概念，并解释函数与关系的区别。

1.4 计数原理（20分）1.4.1 简要阐述乘法原理和加法原理的概念，并给出一个应用实例。

1.4.2 什么是排列和组合？请说明它们的应用场景，并给出一个例子。

2. 答案解析：2.1 命题与谓词逻辑1.1.1 命题逻辑是一种数学分支，用于研究命题之间的关系和推理规则。

其应用范围广泛，包括数学、计算机科学、哲学等领域。

1.1.2 谓词逻辑是一种扩展了命题逻辑的逻辑体系，它考虑了命题中的变量、谓词和量词等元素。

在离散数学中，谓词逻辑常用于描述集合、函数和关系等概念。

2.2 集合和图论1.2.1 集合的并（∪）是指将两个或多个集合中的所有元素取出形成一个新的集合；交（∩）指仅包含两个或多个集合中共有的元素；差（-）是指从一个集合中去除另一个集合中的元素。

1.2.2 有向图中，边是具有方向性的；而在无向图中，边是没有方向性的。

例如，在社交网络中，有向图可以表示人与人之间的关注关系，而无向图可以表示人与人之间的好友关系。

2.3 关系和函数1.3.1 关系是集合之间的一种特殊的子集，它描述了元素之间的某种联系。

例如，家族中的血亲关系可以看作是一个关系。

关系可以用图、矩阵等方式表示。

1.3.2 函数是一种特殊的关系，它将一个集合中的每个元素映射到另一个集合中的唯一元素。

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 具有的性质是（ ）。

离散数学期末考试试题及答案一、选择题（每题4分，共40分）1.下列哪一个不是集合操作？ A. 并 B. 交 C. 补 D. 叉积正确答案：D2.下列哪一个不是真命题？ A. 1 + 1 = 2 B. 所有的猫都会飞 C. 所有的数都是整数 D. 狗是哺乳动物正确答案：B3.设A = {1, 2, 3}，B = {3, 4, 5}，则A ∩ B的结果是：A. {1, 2}B. {3}C. {1, 3}D. {4, 5}正确答案：B4.设A = {1, 2, 3}，B = {3, 4, 5}，则A × B的结果是：A. {(1, 3), (2, 4), (3, 5)}B. {(1, 1), (2, 2), (3, 3)}C. {(3, 3), (3,4), (3, 5)} D. {(3, 1), (3, 2), (3, 3)}正确答案：A5.若n为正整数，则n是偶数的充要条件是： A. n可以被2整除 B. n除以2的余数为1 C. n大于2 D. n的绝对值是偶数正确答案：A6.若A = {1, 2, 3, 4}，B = {3, 4, 5}，则A - B的结果是：A. {1, 2}B. {3}C. {1, 3, 4}D. {4, 5}正确答案：A7.已知命题P和命题Q，下列哪个是它们的逻辑等价式？A. P ∧ (P ∨ Q) = P B. P ∧ (P ∨ Q) = Q C. P ∨ (P ∨ Q) = P D. P ∨ (P ∨ Q) = Q正确答案：A8.设n为奇数，则n + n的结果是： A. 2n B. n^2 C.n(n+1) D. n(n-1)正确答案：C9.已知集合A = {1, 2, 3, 4}，B = {4, 5, 6}，C = {6, 7, 8}，则(A ∩ B)∩ C的结果是： A. {1, 2, 3} B. {4} C. {6} D. 空集正确答案：D10.若命题P为真，则下列哪个推理是正确的？ A. 如果P为真，则Q为真（反证法） B. P与Q都为真（析取引理）C. P蕴含Q（推理法则） D. P等价于Q（假设法）正确答案：A二、解答题（每题10分，共60分）1.证明：任取集合A和B，有(A ∪ B) - B = A - B解答：运用集合的基本运算性质：对任意元素x，x∈ (A ∪ B) - B，即x ∈ (A ∪ B)且x ∉ B。

2020年电大离散数学（本）期末考试题库及答案一、单项选择题1．设P ：a 是偶数，Q ：b 是偶数。

R ：a + b 是偶数，则命题“若a 是偶数，b 是偶数，则a + b 也是偶数”符号化为（D ． P Q →R ）。

2．表达式∀x （P （x ，y ）∨Q （z ））∧∃y （Q （x ，y ）→∀zQ （z ））中∀x 的辖域是（P （x ，y ） Q （z ））。

3．设)(}),({},{,4321∅=∅=∅=∅=P S P S S S 则命题为假的是（42S S ∈）。

4．设G 是有n 个结点的无向完全图，则G 的边数（ 1/2 n （n-1））。

5．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r=（ e-v+2）。

6．若集合A ={1，{2}，{1，2}}，则下列表述正确的是( {1}⊂A )．7．已知一棵无向树T 中有8个顶点，4度、3度、2度的分支点各一个，T 的树叶数为( 5 )．8．设无向图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡010*******000011100111110则G 的边数为( 7 )． 9．设集合A ={a }，则A 的幂集为({∅，{a }} )．10．下列公式中 (⌝A ∧⌝B ↔ ⌝(A ∨B ) )为永真式．11．若G 是一个汉密尔顿图，则G 一定是( 连通图 )．12．集合A ={1, 2, 3, 4}上的关系R ={<x ，y >|x =y 且x , y ∈A }，则R 的性质为（传递的 ）．13．设集合A ={1，2，3，4，5}，偏序关系≤是A 上的整除关系，则偏序集<A ，≤>上的元素5是集合A 的（极大元 ）．14．图G 如图一所示，以下说法正确的是 ( {(a, d ) ,(b, d )}是边割集 ) ．图一 15．设A （x ）：x 是人，B （x ）：x 是工人，则命题“有人是工人”可符号化为（(∃x )(A (x )∧B (x )) ）．16．若集合A ={1，2}，B ={1，2，{1，2}}，则下列表述正确的是(A ⊂B ，且A ∈B )． 17．设有向图（a ）、（b ）、（c ）与（d ）如图一所示，则下列结论成立的是 ( （d ）是强连通的 )．18．设图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡010*******000011100100110则G 的边数为( 5 )． 19．无向简单图G 是棵树，当且仅当(G 连通且边数比结点数少1 )．20．下列公式 ((P →(⌝Q →P ))↔(⌝P →(P →Q )) )为重言式．21．若集合A ＝{ a ，{a }，{1，2}}，则下列表述正确的是({a }⊆A )．22．设图G ＝<V , E >，v ∈V ，则下列结论成立的是 (E v Vv 2)deg(=∑∈ ) ．23．命题公式（P ∨Q ）→R 的析取范式是 (（⌝P ∧⌝Q ）∨R )24．下列等价公式成立的为(P →(⌝Q →P ) ⇔⌝P →(P →Q ) )．25．设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>}，则（ R 2 ）不是从A 到B 的函数．26．设A ={1, 2, 3, 4, 5, 6, 7, 8}，R 是A 上的整除关系，B ={2, 4, 6}，则集合B 的最大元、最小元、上界、下界依次为 (无、2、无、2)．27．若集合A 的元素个数为10，则其幂集的元素个数为（1024）．28．如图一所示，以下说法正确的是 (e 是割点)．图一29．设完全图K n 有n 个结点(n ≥2)，m 条边，当（ n 为奇数）时，K n 中存在欧拉回路．30．已知图G 的邻接矩阵为，则G 有（ 5点，7边 ）．二、填空题（每小题3分，共15分） 1．设A ，B 为任意命题公式，C 为重言式，若A ∧C ⇔B ∧C ，那么A ↔B 是 重言 式（重言式、矛盾式或可满足式）。