2007年1月广工离散数学B试题

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

《离散数学》考试试卷（试卷库20卷）及答案第 1 页/共 4 页《离散数学》考试试卷（试卷库20卷）试题总分： 100 分考试时限：120 分钟、选择题（每题2分，共20分）1. 设论域为全总个体域，M(x)：x 是人，Mortal(x)：x 是要死的，则“人总是要死的”谓词公式表示为( )（A ）)()(x Mortal x M → （B ）)()(x Mortal x M ∧（C ）))()((x Mortal x M x →?（D ）))()((x Mortal x M x ∧?2. 判断下列命题哪个正确？( )（A ）若A∪B＝A∪C，则B ＝C （B ）{a,b}={b,a}（C ）P(A∩B)≠P(A)∩P (B)（P(S)表示S 的幂集）（D ）若A 为非空集，则A ≠A∪A 成立3. 集合},2{N n x x A n∈==对( )运算封闭（A ）乘法（B ）减法（C ）加法（D ）y x -4. 设≤><,N 是偏序格，其中N 是自然数集合，“≤”是普通的数间“小于等于”关系，则N b a ∈?,有=∨b a ( )（A ）a（B ）b（C ）min(a ，b)（D ） max(a ，b)5. 有向图D=，则41v v 到长度为2的通路有( )条（A ）0 （B ）1 （C ）2 （D ）36. 设无向图G 有18条边且每个顶点的度数都是3，则图G 有( )个顶点（A ）10 （B ）4 （C ）8 （D ）127. 下面哪一种图不一定是树？（）（A ）无回路的连通图（B ）有n 个结点n-1条边的连通图（C ）每对结点间都有通路的图（D ）连通但删去一条边则不连通的图 8. 设P ：我将去镇上,Q ：我有时间。

命题“我将去镇上,仅当我有时间”符号化为（）（A ）P →Q （B ）Q →P （C ）P Q （D ）Q P ?∨? 9. 下列代数系统中,其中*是加法运算,（）不是群。

离散数学试题及答案讲解学习离散数学试题及答案⼀、填空题1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; ρ(A) - ρ(B)＝__________________________ .2. 设有限集合A, |A| = n, 则|ρ(A×A)| = __________________________.3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是_______________________________________, 其中双射的是__________________________.4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是_________________________________________________________________________________________.5.设G是完全⼆叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________.6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝_________________________; A?B ＝_________________________;A－B＝_____________________ .7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________,________________________, _______________________________.8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有__________________________，_____________________________, __________________________.9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1?R2 =________________________,R2?R1 =____________________________, R12=________________________.10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________.11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B =__________________________ , B-A = __________________________ ,A∩B = __________________________ , .13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为__________________________________________________________________.14. 设⼀阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是_______________________________.15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。

离散数学考试试题(A、B卷及答案)离散数学考试试题(A卷及答案）一、证明题（10分）1) (P∧Q∧A→C)∧(A→P∨Q∨C)⇔ (A∧(P↔Q))→C。

P<->Q=(p->Q)合取（Q->p）证明: (P∧Q∧A→C)∧(A→P∨Q∨C)⇔(⌝P∨⌝Q∨⌝A∨C)∧(⌝A∨P∨Q∨C)⇔((⌝P∨⌝Q∨⌝A)∧(⌝A∨P ∨Q))∨C反用分配律⇔⌝((P∧Q∧A)∨(A∧⌝P∧⌝Q))∨C⇔⌝(A∧((P∧Q)∨(⌝P∧⌝Q)))∨C再反用分配律⇔⌝( A∧(P↔Q))∨C⇔(A∧(P↔Q))→C⇔(⌝P∨Q∨R)∧(((⌝P∨Q)∧(⌝P∨R))∨(⌝Q∧⌝R))分配律⇔(⌝P∨Q∨R)∧(⌝P∨Q∨⌝Q)∧(⌝P∨Q∨⌝R)∧(⌝P∨R∨⌝Q)∧(⌝P∨R ∨⌝R)⇔(⌝P∨Q∨R)∧(⌝P∨Q∨⌝R)∧(⌝P∨⌝Q∨R)⇔4M∧5M∧6M使（非P析取Q析取R）为0所赋真值，即100，二进制为4⇔0m∨1m∨2m∨3m∨7m所以，公式(P→(Q∨R))∧(⌝P∨(Q↔R))为可满足式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。

真值表法：P Q R Q↔R P→(Q∨R)⌝P∨(Q↔R) (P→(Q∨R))∧(⌝P∨(Q↔R))0 0 0 0 0 1 0 1 0 0 1 1 111111111111111 0 0 1 0 1 1 1 0 1 1 1 11111111由真值表可知，公式(P→(Q∨R))∧(⌝P ∨(Q↔R))为可满足式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。

三、推理证明题（10分）1）⌝P∨Q，⌝Q∨R，R→S P→S。

证明：(1)P附加前提(2)⌝P∨Q P(3)Q T(1)(2)，I（析取三段论）(4)⌝Q∨R P(5)R T(3)(4)，I（析取三段论）(6)R→S P(7)S T(5)(6)，I（假言推理）(8)P→S CP2) ∀x(P(x)→Q(y)∧R(x))，∃xP(x)⇒Q(y)∧∃x(P(x)∧R(x))证明（1）∃xP(x)(2)P(a)(3)∀x(P(x)→Q(y)∧R(x))(4)P(a)→Q(y)∧R(a)(5)Q(y)∧R(a)(6)Q(y)(7)R(a)(8)P(a)(9)P(a)∧R(a)(10)∃x(P(x)∧R(x))(11)Q(y)∧∃x(P(x)∧R(x))五、已知A、B、C是三个集合，证明(A∪B)－C＝(A－C)∪(B－C) （10分）证明：因为x∈(A∪B)－C⇔x∈(A∪B)－C⇔x∈(A∪B)∧x∉C⇔(x∈A∨x∈B)∧x∉C⇔(x∈A∧x∉C)∨(x∈B ∧x∉C)⇔x∈(A－C)∨x∈(B－C)⇔x∈(A－C)∪(B－C) 所以，(A∪B)－C＝(A－C)∪(B－C)。

2007-2008学年第2学期期末考试试卷（B卷）参考答案及评分标准一、填空题（4小题，每空2分，共20分）1、2n2、T3、225，220，52，55，5！4、ℵ，ℵ0二、判断题（4小题，每小题2分，共8分。

正确的划√，错误的划×。

）1、√2、×3、√4、√三、计算或简答题（5小题，共36分）1、在命题逻辑中把下列命题符号化（3小题，每题3分，共9分）（1）设P：别人有困难，Q：老王帮助别人，R：困难解决了。

符号化为(P∧⌝R)→Q或⌝R→(P→Q)（2）设P：我今天上街，Q：我有时间。

符号化为Q→P（3）设P：n是整数，Q：n是偶数，R：n能被2整除。

符号化为(P∧Q)⇄R2、在谓词逻辑中把下列命题符号化（3小题，每题3分，共9分）（1）设P(x)：x是无理数，Q(x)：x能表示成分数。

符号化为⌝∃x (P(x)∧Q(x)) 或∀x(P(x)→⌝Q(x))（2）设P(x,y)：x=y，Q(x)：x是实数，符号化为∀x(Q(x)∧⌝P(x,0)→∃y(Q(y)∧P(xy,1)))或者∀x∃y (Q(x)∧⌝P(x,0)→(Q(y)∧P(xy,1)))（3）设P(x)：x是人，Q(x)：x努力，R(x)：x成功。

符号化为∀x(P(x)∧R(x)→Q(x))3、用等价演算法求下面公式的主析取范式.主合取范式：P→(Q→R)⇔⌝P∨(⌝Q∨R) ⇔⌝P∨⌝Q∨R...............[斟酌给0～2分]公式的所有极小项有⌝P∧⌝Q∧⌝R，⌝P∧⌝Q∧R，⌝P∧Q∧⌝R，⌝P∧Q∧R，P∧⌝Q∧⌝R，P∧⌝Q∧R，P∧Q∧⌝R，故主析取范式为...........................[斟酌给0～2分] (⌝P∧⌝Q∧⌝R)∨(⌝P∧⌝Q∧R)∨(⌝P∧Q∧⌝R)∨(⌝P∧Q∧R)∨(P∧⌝Q∧⌝R)∨(P∧⌝Q∧R)∨(P∧Q∧⌝R)........................................................[斟酌给0～1分] 4、求下面公式的前束范式（5分）∀x(∃yF(x,y)→⌝∀y(G(x,y)∧∃zH(x,y,z)))⇔∀x(∃yF(x,y)→∃y(⌝G(x,y)∨∀z⌝H(x,y,z)))........................[斟酌给0～1分]⇔∀x(∃uF(x,u)→∃y(⌝G(x,y)∨∀z⌝H(x,y,z))) ........................[斟酌给0～2分]⇔∀x∀u∃y∀z (F(x,u)→(⌝G(x,y)∨⌝H(x,y,z))) .....................[斟酌给0～2分] 5、解：不满足自反性、反自反性、反对称性和传递性。

离散数学期末考试题b及答案一、选择题（每题2分，共10分）1. 在集合论中，以下哪个符号表示"属于"关系？A. ∈B. ∉C. ⊆D. ⊂答案：A2. 命题逻辑中，以下哪个符号表示"非"？A. ∧B. ∨C. ¬D. →答案：C3. 以下哪个选项是图的邻接矩阵的正确定义？A. 矩阵的元素表示顶点之间的路径数量B. 矩阵的元素表示顶点之间的边的权重C. 矩阵的元素表示顶点之间的距离D. 矩阵的元素表示顶点之间的连接关系答案：D4. 在布尔代数中，以下哪个运算是幂等的？A. 与运算B. 或运算C. 非运算D. 异或运算答案：C5. 以下哪个选项是哈希函数的基本特性？A. 快速计算B. 容易逆向C. 容易碰撞D. 难以预测答案：A二、填空题（每题3分，共15分）1. 有限自动机的三个组成部分是____、____和____。

答案：状态集、输入字母表、转移函数2. 在图论中，一个图的度是指图中一个顶点的____的个数。

答案：边3. 逻辑等价是指两个逻辑表达式在所有可能的变量赋值下都有____的真值。

答案：相同4. 在关系数据库中，____是用于唯一标识关系表中每行数据的属性或属性组。

答案：主键5. 一个算法的时间复杂度是指算法执行时间随输入规模增长的____。

答案：增长趋势三、简答题（每题5分，共20分）1. 请简述什么是图的连通分量。

答案：图的连通分量是指图中最大的连通子图，即图中任意两个顶点之间都存在路径。

2. 解释一下什么是闭包。

答案：闭包是指在关系数据库中，对于一组属性，如果它们之间存在某种函数依赖关系，则称这组属性的闭包包含了所有依赖于它们的属性。

3. 什么是归纳法证明？答案：归纳法证明是一种数学证明方法，它包括两个步骤：基础步骤（证明当n取第一个值时命题成立）和归纳步骤（假设当n=k时命题成立，然后证明当n=k+1时命题也成立）。

4. 请描述一下什么是欧拉路径和欧拉回路。

离散数学试题及答案一、填空题1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝_____{3}______________; ρ(A) - ρ(B)＝____{{3}，{1，3}，{2,3},{1,2,3}}__________ .2. 设有限集合A, |A| = n, 则|ρ(A×A)| = ___2^(n^2)________.3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是____A1 = {(a,1), (b,1)}, A2 = {(a,2), (b,2)}, A3 = {(a,1), (b,2)}, A4 = {(a,2), (b,1)},_________ _____________, 其中双射的是______A3, A4__________.4. 已知命题公式G＝⌝(P→Q)∧R，则G的主析取范式是____P∧⌝Q∧R (m5)____.5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为___12______，分枝点数为_______3_________.6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A⋂B＝______{4}______; A⋃B＝____{1,2,3,4}_________;A－B＝______{1,2}_______ .7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______自反性____________, _________对称性_________, _________传递性_____________.8. 设命题公式G＝⌝(P→(Q∧R))，则使公式G为真的解释有_____（1,0,0）__________，______(1,0,1)________, ________(1,1,0)________.9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1•R2= ___{(1,3),(2,2),(3,1)}____,R2•R1 =_____{(2,4), (3,3), (4,2)}_____, R12=_______{(2,2), (3,3)}_________.10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A⨯B)| = ______2^(m*n)___________.11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = _____{x | -1 ≤x < 0, x ∈R}_______ , B-A = ______{x | 1 < x < 2, x ∈R}_____ ,A∩B = ______{x | 0 ≤x ≤1, x ∈R}__________ , .13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________________{(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)}_________.14. 设一阶逻辑公式G = ∀xP(x)→∃xQ(x)，则G的前束范式是_____∃y∃x(P(y)→Q(x))________ _____.15.设G是具有8个顶点的树，则G中增加__21___条边才能把G变成完全图。

《离散数学》题库与答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？( )(1)⌝Q=>Q→P (2)⌝Q=>P→Q (3)P=>P→Q (4)⌝P∧(P∨Q)=>⌝P答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别）2、下列公式中哪些是永真式？( )(1)(┐P∧Q)→(Q→⌝R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q)答：（2），（3），（4）可用蕴含等值式证明3、设有下列公式，请问哪几个是永真蕴涵式?( )(1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q(4)P∧(P→Q)=>Q (5) ⌝(P→Q)=>P (6) ⌝P∧(P∨Q)=>⌝P答：（2）是第三章的化简律，（3）类似附加律，（4）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式4、公式∀x((A(x)→B(y，x))∧∃z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。

答：x,y, x,z（考察定义在公式∀x A和∃x A中，称x为指导变元，A为量词的辖域。

在∀x A和∃x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。

于是A(x)、B(y，x)和∃z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元）5、判断下列语句是不是命题。

若是，给出命题的真值。

( )(1)北京是中华人民共和国的首都。

(2) 陕西师大是一座工厂。

(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。

(5) 前进！ (6) 给我一杯水吧！答：（1） 是，T （2） 是，F （3） 不是 （4） 是，T （5） 不是 （6） 不是 （命题必须满足是陈述句，不能是疑问句或者祈使句。

离散数学试题及答案一、选择题1. 下列哪个是由离散数学的基本概念组成的？A. 集合论和函数论B. 图论和逻辑C. 运算符和关系D. 全数论和数论答案：B2. 下列哪个是离散数学的一个应用领域？A. 数据结构和算法分析B. 微积分和线性代数C. 概率论和统计学D. 数值分析和微分方程答案：A3. 集合A={1, 2, 3}，集合B={2, 3, 4}，则A交B的结果是：A. {1, 2, 3, 4}B. {2, 3}C. {2}D. {1}答案：B4. 下列哪个是对于集合的补集运算的正确描述？A. A∪A' = ∅B. A∩A' = ∅C. A - A' = AD. A'∩B' = (A∪B)'答案：B5. 若命题p为真，命题q为假，则命题p→q的真值为：A. 真B. 假C. 不确定D. 无法确定答案：B二、填空题1. 对于命题“如果x是偶数，则x能被2整除”，其逆命题为________________。

答案：如果x不能被2整除，则x不是偶数。

2. 在一个完全图中，如果有12条边，则这个图有__________个顶点。

答案：6个顶点。

3. 设集合A={1, 2, 3, 4}，则A的幂集的元素个数是__________。

答案：2^4=16个元素。

4. 设关系R={(-1, 0), (0, 1), (1, 0)}，则R的逆关系是__________。

答案：R^(-1)={(0, -1), (1, 0), (0, 1)}。

5. 若集合A={1, 2, 3}，集合B={2, 3, 4}，则A的笛卡尔积B是__________。

答案：A×B={(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)}。

三、计算题1. 求集合A={1, 2, 3}和集合B={2, 3, 4}的并集。