(本科)中央电大离散数学考试试题

最新国家开放大学电大《离散数学》形考任务1试题及答案最新国家开放大学电大《离散数学》形考任务1试题及答.形考任务1（集合论部分概念及性质）单项选择.题目.若集合A＝.a, {a}, {1, 2}}, 则下列表述正确的是（）.选择一项:A.{a, {a}}.B..C.{1, 2..D.{a..题目.设函数f: N→N, f(n)=n+1, 下列表述正确的是.）.选择一项: A.f是满射.B.f存在反函.C.f是单射函.D.f是双射.题目.设集合A={1, 2, 3, 4, 5}, 偏序关系是A上的整除关系, 则偏序集<A, >上的元素5是集合A的.）.选择一项:A.极小.B.极大.C.最大.D.最小.题目.设A={a, b}, B={1, 2}, C={4, 5}, 从A到B的函数f={<a,1>.<b, 2>}, 从B到C的函数g={<1, 5>.<2, 4>}, 则下列表述正确的是.）.选择一项:A.g..={<a, 5>.<b, 4>.B.g..={<5, .>.<4, .>.C.f°.={<5, .>.<4, .>.D.f°.={<a, 5>.<b, 4>.题目.集合A={1.2.3.4}上的关系R={<x, y>|x=y且x.yA}, 则R的性质为.）.选择一项:A.传递.B.不是对称.C.反自.D.不是自反.题目.设集合..{1..}, 则P(A...).选择一项:A.{{1}.{a}.{1..}.B.{{1}.{a}.C.{,{1}.{a}.D.{,{1}.{a}.{1..}.题目.若集合A={1, 2}, B={1, 2, {1, 2}},则下列表述正确的是.).选择一项:A.AB, 且A.B.AB, 且A.C.BA, 且A.D.AB, 且A.题目.设集合A={1.2.3}, B={3.4.5}, C={5.6.7},则A∪B–.=.).选择一项:A.{1.2.3.4.B.{4.5.6.7.C.{2.3.4.5.D.{1.2.3.5.题目.设集合..{1.2.3.4.5}上的偏序关系的哈斯图如右图所示, 若A的子集..{3.4.5}, 则元素3为B的.）.选择一项:A.最小上.B.下.C.最大下.D.最小.题目1.如果R1和R2是A上的自反关系, 则R1∪R2, R1∩R2, R1-R2中自反关系有.）个.选择一项:A..B..C..D..以下资料为赠送资料:《滴水之中见精神》主题班会教案活动目的: 教育学生懂得“水”这一宝贵资源对于我们来说是极为珍贵的, 每个人都要保护它, 做到节约每一滴水, 造福子孙万代。

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

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

国开(中央电大)本科《离散数学(本)》网上形考(任务一至三)试题及答案国开(中央电大)本科《离散数学(本)》网上形考(任务一至三)试题及答案说明：适用于计算机科学与技术本科国开平台网上形考。

形考任务一试题及答案题目为随机，用查找功能(Ctrl＋F)搜索题目[题目]若集合A＝{a，{a}，{1，2}}，则下列表述正确的是（）．[答案]{a}A[题目]若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是()．[答案]AB，且AB[题目]若集合A＝{2，a，{a}，4}，则下列表述正确的是()．[答案]{a}A[题目]设集合A={1,2,3}，B={3,4,5}，C={5,6,7}，则A∪B–C=()．[答案]{1,2,3,4}[题目]设集合A={a}，则A的幂集为()．[答案]{，{a}}[题目]设集合A={1,a}，则P(A)=()．[答案]{,{1},{a},{1,a}}[题目]若集合A的元素个数为10，则其幂集的元素个数为（）．[答案]1024[题目]设A、B是两个任意集合，则A-B=()．[答案]AB[题目]设集合A={2,4,6,8}，B={1,3,5,7｝，A到B 的关系R={<x,y>|y=x+1｝，则R=()．[答案]{<2,3>,<4,5>,<6,7>}[题目]集合A={1,2,3,4,5,6,7,8}上的关系R={<x，y>|x+y=10且x,yA}，则R 的性质为（）．[答案]对称的[题目]集合A={1,2,3,4}上的关系R={<x，y>|x=y且x,yA}，则R的性质为（）．[答案]传递的[题目]如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个．[答案]2[题目]设集合A={1,2,3,4}上的二元关系R={<1,1>，<2,2>，<2,3>，<4,4>}，S={<1,1>，<2,2>，<2,3>，<3,2>，<4,4>}，则S是R的（）闭包．[答案]对称[题目]设A={1,2,3,4,5,6,7,8}，R是A上的整除关系，B={2,4,6}，则集合B的最大元、最小元、上界、下界依次为()．[答案]无、2、无、2[题目]设集合A={1，2，3，4，5}，偏序关系是A上的整除关系，则偏序集<A，>上的元素5是集合A的（）．[答案]极大元[题目]设集合A={1,2,3,4,5}上的偏序关系的哈斯图如图所示，若A的子集B={3,4,5}，则元素3为B的（）．[答案]最小上界[题目]设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数为（）．[答案]8[题目]设A={a，b}，B={1，2}，C={4，5}，从A到B的函数f={<a，1>,<b，2>}，从B到C的函数g={<1，5>,<2，4>}，则下列表述正确的是（）．[答案]g°f={<a，5>,<b，4>}[题目]设集合A={1,2,3}上的函数分别为：f={<1,2>，<2,1>，<3,3>}，g={<1,3>，<2,2>，<3,2>}，h={<1,3>，<2,1>，<3,1>}，则h=（）．[答案]f◦g[题目]设函数f：N→N，f(n)=n+1，下列表述正确的是（）．[答案]f是单射函数判断题[题目]设集合A={1,2,3}，B={2,3,4}，C={3,4,5}，则A∩(C-B)={1,2,3,5}．（）[答案]错[题目]设集合A={1,2,3}，B={1,2}，则P(A)-P(B)={{3},{1,3},{2,3},{1,2,3}}．（）[答案]对[题目]空集的幂集是空集．（）[答案]错[题目]设集合A={1,2,3}，B={1,2}，则A×B={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>}．（）[答案]对[题目]设A={1，2}，B={a,b,c}，则A×B的元素个数为8．（）[答案]错[题目]设集合A={0,1,2,3}，B={2,3,4,5}，R是A到B的二元关系，则R的有序对集合为{<2,2>，<2,3>，<3,2>，<3,3>}．（）[答案]对[题目]设集合A={1,2,3,4}，B={6,8,12}，A到B的二元关系R＝那么R－1＝{<6,3>，<8,4>}．（）[答案]对[题目]设集合A=｛a,b,c,d｝，A上的二元关系R={<a,b>,<b,a>,<b,c>,<c,d>}，则R具有反自反性质．（）[答案]对[题目]设集合A=｛a,b,c,d｝，A上的二元关系R={<a,a>,<b,b>,<b,c>,<c,d>}，若在R中再增加两个元素<c,b>，<d,c>，则新得到的关系就具有反自反性质．（）[答案]错[题目]若集合A={1，2，3}上的二元关系R={<1,1>，<1,2>，<3,3>}，则R是对称的关系．（）[答案]错[题目]若集合A={1，2，3}上的二元关系R={<1,1>，<2,2>，<1,2>}，则R是自反的关系．（）[答案]错[题目]设A={1,2}上的二元关系为R={<x,y>|xA，yA,x+y=10}，则R的自反闭包为{<1,1>,<2,2>}．（）[答案]对[题目]设R是集合A上的等价关系，且1,2,3是A中的元素，则R中至少包含<1,1>，<2,2>，<3,3>等元素．（）[答案]对[题目]设A={1，2，3}，R={<1，1>,<1，2>，<2，1>,<3，3>}，则R是等价关系．（）[答案]错[题目]如果R1和R2是A上的自反关系，则、R1∪R2、R1∩R2是自反的．（）[答案]对[题目]若偏序集<A，R>的哈斯图如图二所示，则集合A的最大元为a，极小元不存在．（）[答案]错[题目]设集合A={1,2,3,4}，B={2,4,6,8}，下列关系f={<1,4>,<2,2,>,<4,6>,<1,8>}可以构成函数f：．（）[答案]错[题目]设集合A={1,2,3,4}，B={2,4,6,8}，下列关系f={<1,8>,<2,6>,<3,4>,<4,2,>}可以构成函数f：．（）[答案]对[题目]设A={a,b}，B={1,2}，C={a,b}，从A到B的函数f={<a,1>,<b,2>}，从B到C的函数g={<1,b>,<2,a>}，则g°f={<1，2>,<2，1>}．（）[答案]错[题目]设A={2,3}，B={1,2}，C={3,4}，从A到B的函数f={<2,2>,<3,1>}，从B到C的函数g={<1，3>,<2，4>}，则Dom(g°f)={2，3}．（）[答案]对形考任务二试题及答案题目为随机，用查找功能(Ctrl＋F)搜索题目单选题[题目]设图G＝<V,E>，v∈V，则下列结论成立的是()．[答案][题目]设无向图G的邻接矩阵为，则G的边数为()．[答案]5[题目]设无向图G的邻接矩阵为，则G的边数为()．[答案]7[题目]已知无向图G的邻接矩阵为，则G有（）．[答案]5点，7边[题目]如图一所示，以下说法正确的是()．[答案]{(d,e)}是边割集[题目]如图二所示，以下说法正确的是()．[答案]e是割点[题目]图G如图三所示，以下说法正确的是()．[答案]{b,c}是点割集[题目]图G如图四所示，以下说法正确的是()．[答案]{(a,d),(b,d)}是边割集[题目]设有向图（a）、（b）、（c）与（d）如图五所示，则下列结论成立的是()．[答案]（a）是强连通的[题目]设有向图（a）、（b）、（c）与（d）如图六所示，则下列结论成立的是()．[答案]（d）只是弱连通的[题目]无向图G存在欧拉回路，当且仅当（）．[答案]G连通且所有结点的度数全为偶数[题目]无向完全图K4是（）．[答案]汉密尔顿图[题目]若G是一个汉密尔顿图，则G一定是()．[答案]连通图[题目]若G是一个欧拉图，则G一定是()．[答案]连通图[题目]G是连通平面图，有v个结点，e条边，r个面，则r=()．[答案]e－v＋2[题目]无向树T有8个结点，则T的边数为()．[答案]7[题目]无向简单图G是棵树，当且仅当()．[答案]G连通且边数比结点数少1[题目]已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为()．[答案]5[题目]设G是有n个结点，m条边的连通图，必须删去G的()条边，才能确定G的一棵生成树．[答案]m-n+1[题目]以下结论正确的是()．[答案]树的每条边都是割边判断题[题目]已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是15．()[答案]对[题目]设G是一个图，结点集合为V，边集合为E，则．()[答案]对[题目]设图G如图七所示，则图G的点割集是{f}．()[答案]错[题目]若图G=<V,E>，其中V={a,b,c,d}，E={(a,b),(a,d),(b,c),(b,d)}，则该图中的割边为(b,c)．()[答案]对[题目]无向图G存在欧拉回路，当且仅当G连通且结点度数都是偶数．()[答案]对[题目]如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路．()[答案]错[题目]如图八所示的图G存在一条欧拉回路．()[答案]错[题目]设完全图K有n个结点(n2)，m条边，当n为奇数时，Kn中存在欧拉回路．()[答案]对[题目]汉密尔顿图一定是欧拉图．()[答案]错[题目]设G=<V，E>是具有n个结点的简单图，若在G中每一对结点度数之和小于n-1，则在G中存在一条汉密尔顿路．()[答案]错[题目]若图G=<V,E>中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为W|S|．()[答案]对[题目]如图九所示的图G不是欧拉图而是汉密尔顿图．()[答案]对[题目]设G是一个有7个结点16条边的连通图，则G为平面图．()[答案]错[题目]设G是一个连通平面图，且有6个结点11条边，则G有7个面．()[答案]对[题目]设连通平面图G的结点数为5，边数为6，则面数为4．()[答案]错[题目]结点数v与边数e满足e=v的无向连通图就是树．()[答案]错[题目]设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去4条边后使之变成树．()[答案]对[题目]无向图G的结点数比边数多1，则G是树．()[答案]错[题目]设图G是有5个结点的连通图，结点度数总和为10，则可从G中删去6条边后使之变成树．()[答案]错[题目]两个图同构的必要条件是结点数相等；边数相等；度数相同的结点数相等．()[答案]对形考任务三试题及答案题目为随机，用查找功能(Ctrl＋F)搜索题目选择题[题目]设P：我将去打球，Q：我有时间．命题“我将去打球，仅当我有时间时”符号化为()．[答案]P→Q[题目]设命题公式G：G:┐p→(Q∧R)，则使公式G取真值为1的P，Q，R赋值分别是()．[答案]1,0,0[题目]命题公式(P∨Q)→R的析取范式是()．[答案](┐P∧┐Q)∨R[题目]命题公式(P∨Q)的合取范式是()．[答案](P∨Q)[题目]命题公式┐(p→Q)的主析取范式是()．[答案]P∧┐Q[题目]命题公式P→Q的主合取范式是()．[答案]┐P∨Q[题目]下列等价公式成立的为()．[答案]P→(┐Q→P)＜＝＞┐P→(P→Q)[题目]下列等价公式成立的为()．[答案]┐P∧P＜＝＞┐Q∧Q[题目]下列公式成立的为()．[答案]┐P∧(P∨Q)＝＞Q[题目]下列公式中()为永真式．[答案]┐A∧┐B↔┐(A∨B)[题目]下列公式()为重言式．[答案]Q→(P∨(P∧Q))↔Q→P[题目]命题公式(P∨Q)→Q为()[答案]可满足式[题目]设A（x）：x是书，B（x）：x是数学书，则命题“不是所有书都是数学书”可符号化为（）．[答案][题目]设A（x）：x是人，B（x）：x是教师，则命题“有人是教师”可符号化为（）．[答案][题目]设个体域为整数集，则公式的解释可为()．[答案]对任一整数x存在整数y满足x+y=0[题目]表达式中的辖域是()．[答案][题目]谓词公式(∀x)(A(x)→B(x)∨C(x，y))中的（）。

电大离散数学本科试题及答案一、选择题（每题3分，共30分）1. 在离散数学中，下列哪个概念是用来描述两个集合之间元素的一一对应关系？A. 并集B. 交集C. 笛卡尔积D. 子集答案：D2. 命题逻辑中，德摩根定律描述的是哪种命题的否定形式？A. 合取命题B. 析取命题C. 条件命题D. 生成命题答案：B3. 在图论中，一个没有自环且任意两个顶点之间至多只有一条边的图被称为：A. 有向图B. 无向图C. 完全图D. 树答案：B4. 以下哪个算法用于判断一个命题逻辑表达式的真值表是否存在矛盾？A. 归并排序B. 快速排序C. 归约子句法D. 拓扑排序答案：C5. 集合{1, 2, 3}的幂集含有多少个元素？A. 4B. 6C. 8D. 16答案：C6. 在关系数据库中，一个关系模式的候选键是：A. 能唯一标识元组的属性集合B. 可以为空的属性C. 必须包含所有属性的超键D. 必须包含所有属性的候选键答案：A7. 以下哪个是离散数学中归纳证明的步骤？A. 基础步骤B. 归纳假设C. 归纳步骤D. 所有以上答案：D8. 在命题逻辑中，一个命题函数是：A. 仅包含逻辑运算符的表达式B. 可以取真假值的表达式C. 包含变量和逻辑运算符的表达式D. 仅包含逻辑运算符和变量的表达式答案：C9. 一个布尔代数中的幺元是指：A. 恒等元B. 恒真元C. 恒假元D. 单位元答案：D10. 在有限自动机中，状态的转移是由：A. 输入符号决定B. 当前状态和输入符号决定C. 输出符号决定D. 状态本身决定答案：B二、填空题（每题2分，共20分）11. 在离散数学中，一个集合的子集的总数是2的该集合元素数量的______次方。

答案：对数12. 如果一个命题逻辑表达式中只包含两个命题变量，那么它的真值表有______行。

答案：413. 在图论中，一个图的度序列是指该图所有顶点的______之和的非增序列。

答案：度数14. 一个关系R在域D上的闭包是指R通过______和______运算后得到的关系。

离散数学考试题及答案一、选择题（每题5分，共20分）1. 下列哪个选项不是离散数学的研究对象？A. 图论B. 组合数学C. 微积分D. 逻辑学答案：C2. 在逻辑学中，下列哪个命题是真命题？A. 如果今天是周一，那么明天是周二。

B. 如果今天是周一，那么明天是周三。

C. 如果今天是周一，那么明天是周四。

D. 如果今天是周一，那么明天是周五。

答案：A3. 在集合论中，下列哪个符号表示集合的并集？A. ∩B. ∪C. ⊆D. ⊂答案：B4. 在图论中，下列哪个术语描述的是图中的顶点集合？A. 边B. 路径C. 子图D. 顶点答案：D二、填空题（每题5分，共20分）1. 如果一个集合A包含5个元素，那么它的子集个数是______。

答案：322. 在逻辑学中，如果命题P和命题Q都是真命题，那么复合命题“P且Q”的真值是______。

答案：真3. 在图论中，如果一个图的顶点数为n，那么它的最大边数是______。

答案：n(n-1)/24. 如果一个二叉树的深度为3，那么它最多包含______个节点。

答案：7三、简答题（每题10分，共30分）1. 请简述什么是图的连通性，并给出一个例子。

答案：图的连通性是指在图中任意两个顶点之间都存在一条路径。

例如，在一个完全图K3中，任意两个顶点之间都可以通过一条边直接连接，因此它是连通的。

2. 解释什么是逻辑蕴含，并给出一个例子。

答案：逻辑蕴含是指如果一个命题P为真，则另一个命题Q也必须为真。

例如，命题P：“如果今天是周一”，命题Q：“明天是周二”。

如果今天是周一，那么根据逻辑蕴含，明天必须是周二。

3. 请描述什么是二叉搜索树，并给出它的一个性质。

答案：二叉搜索树是一种特殊的二叉树，其中每个节点的左子树只包含小于当前节点的数，右子树只包含大于当前节点的数。

它的一个性质是中序遍历可以得到一个有序序列。

四、计算题（每题15分，共30分）1. 给定一个集合A={1, 2, 3, 4, 5}，请计算它的幂集，并列出所有元素。

(本科)中央电大离散数学考试试题中央电大离散数学（本科)考试试题一、单项选择题（每小题3分，本题共15分）1。

若集合A1，2，B1,2，1，2,则下列表述正确的是 a。

A.AB,且AB B。

BA，且ABC。

AB，且AB D。

AB，且AB2。

设有向图(a）、（b)、(c）与（d）如图一所示，则下列结论成立的是d .图一A。

(a)是强连通的B。

（b)是强连通的C。

（c)是强连通的D。

（d)是强连通的3。

设图G的邻接矩阵为则G的边数为 b 。

A。

6 B。

5C。

4 D.34。

无向简单图G是棵树，当且仅当 a .A。

G连通且边数比结点数少1B.G连通且结点数比边数少1C。

G的边数比结点数少1 D。

G中没有回路.5。

下列公式 c 为重言式.A。

PQPQ B.QPQ QPQC.PQPPPQD。

PPQ Q1。

若集合Aa,b，B a，b， a，b ，则（ a ）。

A。

AB，且AB B。

AB，但AB C。

AB，但AB D。

AB，且AB2。

集合A1, 2， 3， 4， 5， 6， 7， 8上的关系Rx,y｜x+y10且x, yA，则R的性质为( b ）。

A.自反的B。

对称的 C。

传递且对称的D。

反自反且传递的3。

如果R1和R2是A上的自反关系,则R1∪R2，R1∩R2，R1-R2中自反关系有（ b ）个。

A.0 B。

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.xAx∧Bx B。

┐xAx∧BxC。

┐xAx →Bx D。

┐xAx∧┐Bx1。

设Aa, b，B1， 2，R1，R2，R3是A到B的二元关系,且R1a，2, b，2，R2a，1， a，2, b，1，R3a，1， b,2，则（ b ）不是从A到B的函数。

中央电大离散数学（本科）考试试题一、单项选择题（每小题3分，本题共15分）1．若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( a )．A ．AB ，且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 ．AB ，且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)=2E B ． deg(v)=EC ．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） ．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 )中的y 6．若集合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 I ___{3,4}_____，=B A Y _____{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 ＝⎪⎪⎪⎪⎪⎭⎫ ⎝⎛010*********． 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> ∈ R1R2，所以R1∪R2是自反的． （7分）15．如图二所示的图G 存在一条欧拉回路．正确． （3分）因为图G 为连通的，且其中每个顶点的度数为偶数． （7分）14．设N 、R 分别为自然数集与实数集，f ：N →R ，f (x)=x+6，则f 是单射．正确． （3分）设x1，x2为自然数且x1x2，则有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 存在一条欧拉回路．错误． （3分）因为图G 为中包含度数为奇数的结点． （7分）13．如果图G 是无向图，且其结点度数均为偶数，则图G 是欧拉图．错误． （3分）当图G 不连通时图G 不为欧拉图． （7分）14．若偏序集<A ，R>的哈斯图如图二所示，则集合A 的最大元为a ，最小元是f ．图二错误． （3分）集合A 的最大元与最小元不存在，a 是极大元，f 是极小元，．v 1 v vv 4 d b a e f g h n 图二五．计算题（每小题12分，本题共36分）16．设集合A={1，2，3，4}，R={<x, y>|x, y ∈A ；|xy|=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 上是自反的。

国家开放大学电大本科《离散数学》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分）。

离散数学（本科）考试试题一、单项选择题（每小题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） ．。

最新国家开放大学电大《离散数学(本)》期末题库及答案考试说明：本人针对该科精心汇总了历年题库及答案，形成一个完整的题库，并且每年都在更新。

该题库对考生的复习、作业和考试起着非常重要的作用，会给您节省大量的时间。

做考题时，利用本文档中的查找工具，把考题中的关键字输到查找工具的查找内容框内，就可迅速查找到该题答案。

本文库还有其他网核及教学考一体化答案，敬请查看。

《离散数学》题库及答案一一、单项选择题（每小题3分，本题共15分）1．若集合A={a，b}，B={ a，b，{ a，b }}，则（）．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的性质为（）．A．自反的B．对称的C．传递且对称的D．反自反且传递的3．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个．A．0 B．2 C．1 D．34．如图一所示，以下说法正确的是( ) ．A．{(a, e)}是割边B．{(a, e)}是边割集C．{(a, e) ,(b, c)}是边割集D．{(d, e)}是边割集图一5．设A（x）：x是人，B（x）：x是学生，则命题“不是所有人都是学生”可符号化为（）．A．(∀x)(A(x)∧B(x)) B．┐(∃x)(A(x)∧B(x))C．┐(∀x)(A(x) →B(x)) D．┐(∃x)(A(x)∧┐B(x))二、填空题（每小题3分，本题共15分）6．若集合A的元素个数为10，则其幂集的元素个数为．7．设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数为．8．若A={1,2}，R={<x, y>|x∈A, y∈A, x+y=10}，则R的自反闭包为．9．结点数v与边数e满足关系的无向连通图就是树．10．设个体域D＝{a, b, c}，则谓词公式(∀x)A(x)消去量词后的等值式为．三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“尽管他接受了这个任务，但他没有完成好．”翻译成命题公式．12．将语句“今天没有下雨．”翻译成命题公式．四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．13．下面的推理是否正确，试予以说明．(1) （∀x）F（x）→G（x）前提引入(2) F（y）→G（y）US（1）．14．若偏序集<A，R>的哈斯图如图二所示，则集合A的最大元为a，最小元不存在．图二五．计算题（每小题12分，本题共36分）15．求（P∨Q）→（R∨Q）的合取范式．16．设A={0，1，2，3，4}，R={<x，y>|x∈A，y∈A且x+y<0}，S={<x，y>|x∈A，y∈A且x+y≤3}，试求R，S，R•S，R-1，S-1，r(R)．17．画一棵带权为1, 2, 2, 3, 4的最优二叉树,计算它们的权．六、证明题（本题共8分）18．设G是一个n阶无向简单图，n是大于等于2的奇数．证明G与G中的奇数度顶点个数相等(G 是G的补图)．试题解答一、单项选择题（每小题3分，本题共15分） 1．A 2．B 3．B 4．D 5．C 二、填空题（每小题3分，本题共15分） 6．1024 7．88．{<1,1>,<2,2>} 9．e=v -110．A (a ) ∧A (b )∧A （c ）三、逻辑公式翻译（每小题6分，本题共12分）11．设P ：他接受了这个任务，Q ：他完成好了这个任务， （2分）P ∧⌝ Q ． （6分）12．设P ：今天下雨， （2分）⌝ P ． （6分）四、判断说明题（每小题7分，本题共14分）13．错误． （3分） （2）应为F （y ）→G （x ），换名时，约束变元与自由变元不能混淆． （7分） 14．错误． （3分） 集合A 的最大元不存在，a 是极大元． （7分） 五．计算题（每小题12分，本题共36分）15．（P ∨Q ）→（R ∨Q ）⇔⌝（P ∨Q ）∨（R ∨Q ） （4分） ⇔(⌝P ∧⌝Q )∨（R ∨Q ）⇔(⌝P ∨R ∨Q )∧(⌝Q ∨R ∨Q )⇔(⌝P ∨R ∨Q ) ∧R 合取范式 （12分） 16．R =∅, （2分） S ={<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0>} （4分） R •S =∅， （6分）R -1=∅， （8分） S -1= S ， （10分） r (R )=I A ． （12分） 17．（10分）权为1⨯3+2⨯3+2⨯2+3⨯2+4⨯2=27 （12分）六、证明题（本题共8分）18．证明：因为n 是奇数，所以n 阶完全图每个顶点度数为偶数， （3分） 因此，若G 中顶点v 的度数为奇数，则在G 中v 的度数一定也是奇数， （6分）ο οο ο ο ο ο ο ο 1 2 23 34 75 12所以G 与G 中的奇数度顶点个数相等． （8分）《离散数学》题库及答案二一、单项选择题（每小题3分，本题共15分）1．若集合A ={1，{2}，{1，2}}，则下列表述正确的是( )． A ．2⊂A B ．{1}⊂AC ．1∉AD ．2 ∈ A2．已知一棵无向树T 中有8个顶点，4度、3度、2度的分支点各一个，T 的树叶数为( )． A ．6 B ．4 C ．3 D ．53．设无向图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0101110011000011100111110 则G 的边数为( )． A ．1 B ．7 C ．6 D ．144．设集合A ={a }，则A 的幂集为( )．A ．{{a }}B ．{a ，{a }}C ．{∅，{a }}D ．{∅，a }5．下列公式中 ( )为永真式．A ．⌝A ∧⌝B ↔ ⌝A ∨⌝B B ．⌝A ∧⌝B ↔ ⌝(A ∨B )C ．⌝A ∧⌝B ↔ A ∨BD ．⌝A ∧⌝B ↔ ⌝(A ∧B )二、填空题（每小题3分，本题共15分）6．命题公式P P ⌝∧的真值是 ． 7．若无向树T 有5个结点，则T 的边数为 ．8．设正则m 叉树的树叶数为t ，分支数为i ，则(m -1)i = ．9．设集合A ={1，2}上的关系R ＝{<1, 1>,<1, 2>}，则在R 中仅需加一个元素 ，就可使新得到的关系为对称的．10．(∀x )(A (x )→B (x ，z )∨C (y ))中的自由变元有 ．三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“今天上课．”翻译成命题公式．12．将语句“他去操场锻炼，仅当他有时间．”翻译成命题公式．四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．13．设集合A={1，2}，B={3，4}，从A到B的关系为f={<1, 3>}，则f是A到B的函数．14．设G是一个有4个结点10条边的连通图，则G为平面图．五．计算题（每小题12分，本题共36分）15．试求出（P∨Q）→（R∨Q）的析取范式．16．设A={{1}, 1, 2}，B={1, {2}}，试计算（1）（A∩B）（2）（A∪B）（3）A （A∩B）．17．图G=<V, E>，其中V={ a, b, c, d }，E={ (a, b), (a, c) , (a, d), (b, c), (b, d), (c, d)}，对应边的权值依次为1、2、3、1、4及5，试（1）画出G的图形；（2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值．六、证明题（本题共8分）18．试证明：若R与S是集合A上的自反关系，则R∩S也是集合A上的自反关系．试题解答一、单项选择题（每小题3分，本题共15分）1．B 2．D 3．B 4．C 5．B二、填空题（每小题3分，本题共15分）6．假（或F，或0）7．48．t-19．<2, 1>10．z，y三、逻辑公式翻译（每小题6分，本题共12分）11．设P ：今天上课， （2分） 则命题公式为：P ． （6分） 12．设 P ：他去操场锻炼，Q ：他有时间， （2分） 则命题公式为：P →Q ． （6分） 四、判断说明题（每小题7分，本题共14分）13．错误． （3分） 因为A 中元素2没有B 中元素与之对应，故f 不是A 到B 的函数． （7分） 14．错误． （3分） 不满足“设G 是一个有v 个结点e 条边的连通简单平面图，若v ≥3，则e ≤3v -6．” （7分）五．计算题（每小题12分，本题共36分）15．（P ∨Q ）→（R ∨Q ）⇔ ┐(P ∨Q )∨（R ∨Q ） （4分）⇔ (┐P ∧┐Q )∨（R ∨Q ） （8分）⇔ (┐P ∧┐Q )∨R ∨Q （析取范式） （12分）16．（1）（A ∩B ）={1} （4分）（2）（A ∪B ）={1, 2, {1}, {2}} （8分） （3） A -（A ∩B ）={{1}, 1, 2} （12分）17．（1）G 的图形表示如图一所示：（3分）（2）邻接矩阵：⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0111101111011110 （6分） （3）最小的生成树如图二中的粗线所示：图一 ο ο ο ο a b c d1 124 53 图二ο ο ο ο a b cd1 1 2453（10分）权为：1+1+3=5 （12分）六、证明题（本题共8分）18．证明：设∀x∈A，因为R自反，所以x R x，即< x, x>∈R；又因为S自反，所以x R x，即< x, x >∈S．（4分）即< x, x>∈R∩S （6分）故R∩S自反．（8分）《离散数学》题库及答案三一、单项选择题（每小题3分，本题共15分）1．若集合A＝{ a，{a}}，则下列表述正确的是( )．A．{a}⊆A B．{{{a}}}⊆AC．{a，{a}}∈A D．∅∈A2．命题公式（P∨Q）的合取范式是( )A．（P∧Q）B．（P∧Q）∨（P∨Q）C．（P∨Q）D．⌝（⌝P∧⌝Q）3．无向树T有8个结点，则T的边数为( )．A．6 B．7 C．8 D．9 4．图G如图一所示，以下说法正确的是( )．A．a是割点B．{b,c}是点割集C．{b, d}是点割集D．{c}是点割集图一5．下列公式成立的为( )．A．⌝P∧⌝Q ⇔P∨Q B．P→⌝Q⇔⌝P→QC．Q→P⇒ P D．⌝P∧(P∨Q)⇒Q二、填空题（每小题3分，本题共15分）6．设集合A ={2, 3, 4}，B ={1, 2, 3, 4}，R 是A 到B 的二元关系，},{y x B y A x y x R ≤∈∈><=且且则R 的有序对集合为 ．7．如果R 是非空集合A 上的等价关系，a ∈A ，b ∈A ，则可推知R 中至少包含 等元素． 8．设G ＝<V , E >是有4个结点，8条边的无向连通图，则从G 中删去 条边，可以确定图G 的一棵生成树．9．设G 是具有n 个结点m 条边k 个面的连通平面图，则m 等于 10．设个体域D ＝{1, 2}，A (x )为“x 大于1”，则谓词公式()()x A x ∃的真值为 三、逻辑公式翻译（每小题6分，本题共12分） 11．将语句“今天考试，明天放假．”翻译成命题公式． 12．将语句“我去旅游，仅当我有时间．”翻译成命题公式． 四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．13．如果图G 是无向图，且其结点度数均为偶数，则图G 是欧拉图．14．若偏序集<A ，R >的哈斯图如图二所示，则集合A 的最大元为a ，最小元是f ．图二五．计算题（每小题12分，本题共36分）15．设谓词公式)),,()(),()((z x y B z y x A x ∀→∃，试（1）写出量词的辖域； （2）指出该公式的自由变元和约束变元． 16．设集合A ={{1},1,2}，B ={1,{1,2}}，试计算（1）（A -B ）； （2）（A ∩B ）； （3）A ×B ．17．设G =<V ，E >，V ={ v 1，v 2，v 3，v 4 }，E ={ (v 1,v 3)，(v 2,v 3)，(v 2,v 4)，(v 3,v 4) }，试 （1）给出G 的图形表示； （2）写出其邻接矩阵；（3）求出每个结点的度数； （4）画出其补图的图形． 六、证明题（本题共8分）18．设A ，B 是任意集合，试证明：若A ⨯A=B ⨯B ，则A=B ．试题解答(供参考)一、单项选择题（每小题3分，本题共15分） 1．A 2．C 3．B 4．B 5．D 二、填空题（每小题3分，本题共15分）6．{<2, 2>，<2, 3>，<2, 4>，<3, 3>}，<3, 4>，<4, 4>} 7．<a , a >，< b , b > 8．5 9．n +k -210．真（或T ，或1）三、逻辑公式翻译（每小题4分，本题共12分）11．设P ：今天考试，Q ：明天放假． （2分） 则命题公式为：P ∧Q ． （6分）12．设P ：我去旅游，Q ：我有时间， （2分）则命题公式为：P →Q ． （6分） 四、判断说明题（每小题7分，本题共14分）13．错误． （3分）当图G 不连通时图G 不为欧拉图． （7分） 14．错误． （3分） 集合A 的最大元与最小元不存在，a 是极大元，f 是极小元，． （7分） 五．计算题（每小题12分，本题共36分）15．（1）∃x 量词的辖域为)),,()(),((z x y B z y x A ∀→， （3分）∀z 量词的辖域为),,(z x y B , （6分） （2）自由变元为)),,()(),((z x y B z y x A ∀→中的y ， （9分）约束变元为x 与z ． （12分）16．（1）A -B ={{1},2} （4分）（2）A ∩B ={1} （8分） （3）A ×B={<{1},1>，<{1},{1,2}>，<1,1>，<1, {1,2}>，<2,1>，<2, {1,2}>} （12分） 17．（1）G 的图形表示为(如图三)：（3分）图三 （2）邻接矩阵：⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0110101111000100（6分） （3）v 1，v 2，v 3，v 4结点的度数依次为1，2，3，2 （9分） （4）补图如图四所示：（12分）图四六、证明题（本题共8分）18．证明：设x ∈A ，则<x ，x >∈A ⨯A ， （1分） 因为A ⨯A=B ⨯B ，故<x ，x >∈B ⨯B ，则有x ∈B ， （3分） 所以A ⊆B ． （5分） 设x ∈B ，则<x ，x >∈B ⨯B ， （6分） 因为A ⨯A=B ⨯B ，故<x ，x >∈A ⨯A ，则有x ∈A ，所以B ⊆A ． （7分） 故得A=B ． （8分）《离散数学》题库及答案四一、单项选择题（每小题3分，本题共15分）二、填空题（每小题3分，本题共15分）三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“如果他掌握了计算机的用法，那么他就能完成这项工作．”翻译成命题公式．12．将语句“前天下雨，昨天还是下雨．”翻译成命题公式．四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）五、计算题（每小题12分，本题共36分）六、证明题（本题共8分）试题答案《离散数学》题库及答案五一、单项选择题（每小题3分，本题共15分）试题及答案《离散数学》题库及答案六一、单项选择题（每小题3分，本题共15分）二、填空题（每小题3分，本题共15分）三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“昨天下雨”翻译成命题公式．12．将语句“小王今天上午或者去看电影或者去打球”翻译成命题公式．四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）五、计算题（每小题12分，本题共36分）六、证明题（本题共8分）试题答案及评分标准（供参考）。

国家开放大学电大本科《离散数学》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分）。

最新国家开放大学电大《离散数学》期末题库及答案
考试说明：本人针对该科精心汇总了历年题库及答案，形成一个完整的题库，并且每年都在更新。

该题库对考生的复习、作业和考试起着非常重要的作用，会给您节省大量的时间。

做考题时，利用本文档中的查找工具，把考题中的关键字输到查找工具的查找内容框内，就可迅速查找到该题答案。

本文库还有其他网核及教学考一体化答案，敬请查看。

《离散数学》题库及答案一
一、单项选择题（每小题3分，本题共15分）
试题答案及评分标准
仅供参考
《离散数学》题库及答案二一、单项选择题（每小题3分，本题共15分）
试题及答案
《离散数学》题库及答案三一、单项选择题（每小题3分，本题共15分）
二、填空题（每小题3分，本题共15分）
三、逻辑公式翻译（每小题6分，本题共12分）
11．将语句“如果他掌握了计算机的用法，那么他就能完成这项工作．”翻译成命题公式．12．将语句“前天下雨，昨天还是下雨．”翻译成命题公式．
四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）
五、计算题（每小题12分，本题共36分）
六、证明题（本题共8分）
试题答案
《离散数学》题库及答案四一、单项选择题（每小题3分，本题共15分）
二、填空题（每小题3分，本题共15分）
三、逻辑公式翻译（每小题6分，本题共12分）
11．将语句“昨天下雨”翻译成命题公式．
12．将语句“小王今天上午或者去看电影或者去打球”翻译成命题公式．四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）
五、计算题（每小题12分，本题共36分）
六、证明题（本题共8分）
试题答案及评分标准
（供参考）。

离散数学本科试题及答案一、选择题（每题5分，共20分）1. 在集合论中，空集的定义是：A. 包含所有集合的集合B. 不包含任何元素的集合C. 包含所有非空集合的集合D. 包含所有有限集合的集合答案：B2. 在逻辑运算中，非运算的符号是：A. ∧B. ∨C. ¬D. →答案：C3. 以下哪个选项是图的邻接矩阵表示法？A. 邻接表B. 顶点列表C. 边列表D. 所有选项都是答案：A4. 以下哪个命题是真命题？A. 所有的偶数都是整数B. 所有的整数都是偶数C. 所有的奇数都是整数D. 所有的整数都是奇数答案：A二、填空题（每题5分，共20分）1. 在布尔代数中，逻辑与运算的符号是________。

答案：∧2. 如果一个图是无向图且任意两个顶点都相连，则称这个图是________。

答案：完全图3. 在关系数据库中，关系模式的属性名集合称为________。

答案：关系模式4. 一个命题的逆否命题与其原命题的________是相同的。

答案：真假性三、简答题（每题10分，共30分）1. 描述什么是二元关系，并举例说明。

答案：二元关系是定义在两个集合上的一个关系，它由有序对组成，每个有序对的第一个元素来自第一个集合，第二个元素来自第二个集合。

例如，小于关系是实数集上的一个二元关系，因为对于任意两个实数a和b，如果a小于b，那么有序对(a, b)属于这个关系。

2. 解释什么是图的哈密顿回路，并给出一个例子。

答案：图的哈密顿回路是一条通过图中每个顶点恰好一次的闭合路径。

例如，在一个五边形的顶点上，可以画出一条哈密顿回路，即从任一顶点出发，依次经过其他顶点，最后回到起始顶点。

3. 什么是正规文法？请给出一个例子。

答案：正规文法是一种形式文法，它能够生成正规集合，即可以被有限自动机接受的字符串集合。

例如，正规文法可以定义为：S -> aSb| ε，其中S是开始符号，a和b是字母，ε表示空字符串。

这个文法生成的字符串集合是所有长度为偶数的字符串，其中a和b交替出现。