离散数学期末试卷(B)

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

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

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

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

这种性质称为函数的______。

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

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

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

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

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

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

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

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

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

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

安徽大学《离散数学》期末考试试卷（B 卷）（时间120分钟）开课院（系、部） 姓名 学号 .一、选择题（每小题2分，共20分）1．设522:=⨯P ，:Q 雪是黑的，842:=⨯R ，:S 太阳从东方升起，下列命题中真值为T 的是（ ） A 、R Q P ∧→； B 、S P R ∧→；C 、R Q S ∧→；D 、)()(S Q R P ∧∨∧。

2．下列命题公式中，为重言式的是（ ）A 、)(R Q P ∨→；B 、)()(Q P R P →∧∨；C 、)()(R Q Q P ∨↔∨；D 、))()(())((R P Q P R Q P →→→→→→。

3．设x x L :)(是演员，x x J :)(是老师，x y x A :),(钦佩y ，命题“所有演员都钦佩某些老师”符号化为（ ）A 、)),()((y x A x L x →∀；B 、))),()(()((y x A y J y x L x ∧∃→∀；C 、)),()()((y x A y J x L y x ∧∧∃∀；D 、)),()()((y x A y J x L y x →∧∃∀。

4．设}{φ=A ， ))((A B ρρ=，以下各小题中不正确的有（ ）A 、B ∈}}{{φ； B 、B ∈}}}{{,{φφ ；C 、B ⊆}}}{{,{φφ；D 、B ⊆}}}{,{},{{φφφ。

5．设φ=A ， }}{,{φφ=B ，则A B -是（ ）。

A 、 }}{{φ； B 、}{φ ； C 、 }}{,{φφ； D 、 φ。

6．设},,{c b a A =，R ,S ,T 是集合)(A ρ上的二元关系。

其中，}|,{y x y x R ⊂><=，}|,{φ=><=y x y x S ，}|,{A y x y x T =><= 。

下列哪些命题为真？（ ） I.R 是反自反、反对称和传递的 II.S 是反自反和对称的 III.T 是反自反和对称的A 、仅I ；B 、仅II ；C 、I 和II ；D 、全真。

离散数学期末试题及答案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 .。

A. B. C. D.
参考答案： B
6、 设 A. 代数系统 B. 半群 C. 群
,*为普通乘法,则<S,*>是( )
D. 都不是
参考答案： A
7、 设S={0,1},*为普通乘法,则< S , * >是( ) A. 半群,但不是独异点 B. 只是独异点,但不是群 C. 群 D. 环,但不是群
参考答案： B
A. B. C. D.
参考答案： B
3、 命题“有的人喜欢所有的花”的逻辑符号化为( ) 设D:全总个体域,F(x):x是花,M(x) :x是人,H(x,y):x喜欢y
A. B. C. D.
参考答案： D
4、 下列等价式成立的有( )
A. B. C. D.
参考答案： D
5、 下列公式是重言式的有( )
5、 ( )设S={1,2},则S在普通加法和乘法运算下都不封闭。 参考答案： 正确
8、 谓词公式
中的x是( )
A. 自由变元
B. 约束变元
C. 既是自由变元又是约束变元
D. 既不是自由变元又不是约束变元
参考答案： C
9、 设
是一个有界格,如果它也是有补格,只要满足( )
A. 每个元素都至少有一个补元
B. 每个元素都有多个补元
C. 每个元素都无补元
D. 每个元素都有一个补元
参考答案： A
10、 一棵无向树T有4度、3度、2度的分枝点各1个,其余顶点均为树叶,则T中有( )片树叶
A. 3 B. 4 C. 5 D. 6
参考答案： C
11、 设
A. {{1,2}} B. {1,2 } C. {1} D. {2}
参考答案： A
,则有( )

离散数学复习题一、单项选择题1.下列命题公式为重言式的是【 A 】。

A．p→(p∨q) B．(p∨┐p)→qC．q∧┐q D．p→┐q2．下列语句中不是．．命题的是【 A 】。

A．这个语句是假的。

B．1+1=1.0C．飞碟来自地球外的星球。

D．凡石头都可练成金。

3．设A={Φ，{1}，{1，3}，{1，2，3}}，则A上包含关系“⊆”的哈斯图为【 C 】4．在公式)QyzPyxP∧∀→x∃y∃中变元y是【 B 】。

(z()))y,(()())((,A．自由变元B．约束变元C．既是自由变元，又是约束变元D．既不是自由变元，又不是约束变元5．设A={1，2，3}，A上二元关系S={<1，1>，<1，2>，<3，2>，<3，3>}，则S是【 D 】。

A．自反关系B．反自反关系C．对称关系D．传递关系6．图中从v1到v3长度为3 的通路有【 D 】条。

离散数学试卷（B）第1页（共6页）离散数学试卷（B ）第2页（共6页）A ．0；B ．1；C ．2；D ．3。

7．在下列代数系统中，不是环的只有【 C 】。

A ．<Z ，+，*)，其中Z 为整数集，+，*分别为整数加法和乘法。

B ．(Q ，+，*)，其中Q 为有理数集，+，*分别为有理数加法和乘法。

C ．<R ，+，*>，其中R 为实数集，+为实数加法，a*b=a+2b 。

D ．<M n (R)，+，*>，其中M n (R)为实数集n×n 阶矩阵结合，+，*是矩阵加法和乘法。

8．下列整数集对于整除关系都构成偏序集，而能构成格的是【 B 】。

A ．{l ，2，3，4，5} B ．{1，2，3，6，12} C ．{2，3，7}D ．{l ，2，3，7}9．结点数为奇数且所有结点的度数也为奇数的连通图必定是【 D 】。

A ．欧拉图 B ．汉密尔顿图 C ．非平面图D ．不存在的10．无向图G 是欧拉图当且仅当G 是连通的且【 C 】。

《离散数学》期末考试试卷附答案一、填空题(每小题3分，共15小题，共45分)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变成完全图。

天津师范大学考试试卷2009 —2010学年第一 学期期末考试试卷（B 卷）科目： 离散数学学院： 管理学院专业：08信管、物流一、 单项选择题:在每小题的备选答案中选出一个正确答案，并将正确答案的代（每小题 分，本大题共 分）1.谓词公式(∀x)(P(x) ( ∃y)R(y)) → Q(x)中量词(∀x)的辖域是（ ）。

A. (∀x) (P(x) ( ∃y)R(y))B. P(x)C. P(x) ( ∃y)R(y)D. P(x),Q(x)2. 下列公式中哪些公式不是前束范式（ ）。

A. x ∀∃y(P(x) q(y))B. ∀x ∀y(P(x) Q(y) ( ∃z)S(z))C.Q(a,b)D. P3. 给定解释N 如下：个体域为自然数D N ；D N 上特定元素a = 0；D N 上特定函数f(x,y) = x+y , g(x,y) = x ∙y ； D N 上特定谓词E(x,y)为x=y ,下列公式为真的是（ ）。

A. ∀xE(g(x,a),x) B. ∀x ∀y ∀zE(f(x,y),z) C. ∀x ∀yE(f(x,y),g(x,y)) D. ∃x ∃yE(f(x,y),g(x,y))4. 设集合X≠∅，则空关系∅不具备的性质是（）。

xA.反自反性B.自反性C.对称性D.传递性5. 下列各式中，哪个不成立（）。

A.(∀x) (P(x) Q(x))⇔(∀x) (P(x) (∀x)Q(x))B.(∃x)(P(x) Q(x))⇔(∃x) (P(x) (∃x)Q(x)C.(∀x) (P(x) Q(x))⇔(∀x) (P(x) (∀x)Q(x)D.(∀x) (P(x) Q)⇔(∀x) (P(x) Q)6. 设个体域A={a,b},则∃x(F(x) G(x))消去量词为（）。

A. F(a) G(a)B. F(b) G(b)C. ( F(a) G(a) (F(b) G(b)))D. F(a) G(b)7. 给定A={1,2,3,4}，A上的关系R={<1,3>,<1,4>,<2,3>,<2,4>,<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. 在命题逻辑中，_________ 表示一个命题是真的，而 _________ 表示一个命题是假的。

东 华 大 学 试 卷2021-2022学年第 1 学期 课号课程名称 离散数学 （期末; 闭卷） 适用班级（或年级、专业）1、对任意两个集合B A 和，证明 ()()A B A B A =⋂⋃-2、构造下面命题推理的证明如果我学习，那么我数学不会不及格；如果我不热衷于玩游戏机，那么我将学习；但我数学不及格，因此我热衷与玩游戏机。

二 、计算（本大题共4小题，第1小题5分，第2、3、4小题各10分，总计35分） 1、画一个有一条欧拉回路和一条汉密顿回路的图。

2、设()(){}212,，，个体域为为，整除为<x x Q y x y x P ，求公式： ()()()()()x Q y x P y x →∃∀,的真值。

3、一棵树有2n 个结点度数为2 ，3n 个结点度数为3，… ，k n 个结点度数为k ，问它有几个度数为1的结点。

4、设集合{}A d c b a A ,,,,=上的关系 {}d c c b a b b a R ,,,,,,,=，求出它的自反闭包，对称闭包和传递闭包。

三、设{}15,9,5,3=A 上的整除关系{}212121,,,a a A a a a a R 整除∈=，R 是否为A 上的偏序关系？若是，则：1、画出R 的哈斯图；2、求A 的极大值和A 的极小值。

（本大题10分）四、用推导法求公式()()R Q P →→的主析取范式和主合取范式。

（本大题10分） 五、设自然数集N 上的关系R 定义为：{}I m n n N n n n n R m ∈=∈=,2/,,,212121，证明：R 是N 上的等价关系。

（本大题10分）六、设+R R 和分别是实数集和正实数集，＋和×分别是普通加法和乘法，定义函数+→R R f :为r r f 10)(=，证明 ),(),(⨯++R R f 到是从的同构映射。

（本大题10分）七、设I 是整数集合，＋是普通加法，试证明>+<,I 是一个群。

华东理工大学离散数学模拟期末试卷B 答案(2004)1一. 是非题（每小题2分，共40分）:2.( T )()()A B B C A C ∈∧⊆⇒∈.3.( F )()()()()A B C D A C B D ⊂∧⊂⇒⊂ .(这里P Q ⊂表示P 是Q 的真子集)4.( T )(()())()A B B A B A T →∧→↔↔⇔(T 表示重言式).6.( F )任意两个不同的布尔大项的合取式必为永真假式.7.( F )若{}112,,,k A A A π=⋅⋅⋅和{}212,,,s B B B π=⋅⋅⋅都是集合A 的划分, 则12ππ-也一定是集合A 的一个划分.9.( F )设1R 和2R 是集合A 上的两个没有对称性的关系,那么12R R 也是没有对称性的关系.10.( F )一个偏序集如果没有最大元,则必不可能有极大元.11.( F )每个全序集必为良序集.14.( F )非素数阶群不可能是循环群.15.( T )4阶群必为可换群.16.( F )24阶群一定不可能是Abel 群.17.( F )有向图的邻接矩阵必为对称阵.18.( T )如果一个连通图有两个奇结点,那么它一定不是Euler 图.19.( F )如果一个有n 个结点的图的任意一对结点的度数之和都小于n ,那么它必不是Hamilton 图.20.( F )完全图n K 都不是平面图.二. 填空题（每小题2分，共20分）:1. 设p 与q 的真值为F ,,r s 的真值为T ,则(())(()())p q r p q r s ∧∨∧⌝∧⌝∨⌝∨⌝的真值是 F .2. 有甲乙丙三个人猜测ABC 三个球队中的冠军.各人的猜测如下:甲: 冠军不是乙,也不是丙.乙: 冠军不是乙,而是甲.丙: 冠军不是甲,而是乙.已知其中有一个人说的完全正确.一个人说的都不对,而另外一人恰有一半说对了.据此推算,冠军应该 是 乙 .3. 取个体域为全体整数的集合,给出下列各公式：(1)()()()()x y z x y z ∀∀∃-=(2)()()x xy x ∀=(3)()()(2)x y x y y ∃∀+=其中公式 (1) 的真值为T ，公式 (3) 的真值为F .4.下列4个推理中，错误的推理是 （1）（3） .（1）前提：()(()())x F x G x ∃∧结论：()()y F y ∀（2）前提：()(()()),()x F x H x H y ∀→⌝结论：()(())x F x ∀⌝（3）前提：()(),()()x F x x G x ∃∃结论：()(()())y F y G y ∃∧（4）前提：()()F c H c ∧结论：()(()())x F x H x ∃∧5. 设R 是在正整数集合Z +上如下定义的二元关系 {},(,)(318)R x y x y Z x y +=<>∈∧+=，则它一共有 5 个二元序偶，且有自反性、对称性、传递性、反自反性和反对称性诸性质中的 反自反性 性质。

第1页 共6页第2页 共 6页一、填空题（每小题3分，共15分）1.设F (x )：x 是苹果，H (x ，y )：x 与y 完全相同，L (x ，y )：x =y ，则命题“没有完全相同的苹果”的符号化（利用全称量词）为∀x ∀y (F (x )∧F (y )∧⌝L (x ，y )→⌝H (x ，y ))．2.命题“设L 是有补格，在L 中求补元运算‘′’是L 中的一元运算”的真值是　0　．3.设G ={e ，a ，b ，c }是Klein 四元群，H =〈a 〉是G 的子群，则商群G /H ={〈a 〉，{b ，c }}={{e ，a }，{b ，c }}．4.设群G =〈P ({a ，b ，c })，⊕〉，其中⊕为集合的对称差运算，则由集合{a ，b }生成的子群〈{a ，b }〉 ={∅，{a ，b }}．5.已知n 阶无向简单图G 有m 条边，则G 的补图有n (n -1)/2-m 条边．二、选择题（每小题3分，共15分）1.命题“只要别人有困难(p )，小王就会帮助他(q )，除非困难已经解决了(r )”的符号化为 【B 】A ．⌝(p ∧r )→q ．B ．(⌝r ∧p )→q ．C ．⌝r →(p ∧q )．D ．⌝r →(q → p )．2.设N 为自然数集合，“≤”为通常意义上的小于等于关系，则偏序集〈N ，≤〉是 【C 】A ．有界格．B ．有补格．C ．分配格．D ．布尔代数．3.设n (n ≥3) 阶无向图G =〈V ，E 〉是哈密尔顿图，则下列结论中不成立的是 【D 】A ．∀V 1⊂V ，p (G -V 1)≤|V 1|．B ．|E |≥n ．C ．无1度顶点．D ．δ(G )≥n /2．4.设A ={a ，b ，c }，在A 上可以定义 个二元运算，其中有 个是可交换的，有 个是幂等的． 【A 】A ．39，36，36．B ．39，36，33．C ．36，36，33．D ．39，36，39．5.下列图中是欧拉图的有【C 】A ．K 4，3．B ．K 6．C ．K 5．D ．K 3，3．三、计算与简答题（每小题10分，共50分）1.利用等值演算方法求命题公式(p ∨q ) → (q →p )的主合取范式；利用该主合取范式求公式的主析取范式，并指出该公式的成真赋值和成假赋值．(p ∨q ) → (q →p ) ⇔⌝(p ∨q )∨(⌝q ∨p ) ⇔(⌝p ∧⌝q )∨(⌝q ∨p )⇔(⌝p ∨⌝q ∨p )∧(⌝q ∨⌝q ∨p ) ⇔⌝q ∨p ⇔p ∨⌝q哈尔滨工程大学试卷考试科目：离散数学（061121，061131）考试时间：　2008.07.09 9:00-11:00题号一二三四五总分分数评卷人第5页 共6页第6页 共 6页=(a ∧b )∨((a ∨c )∧(b’ ∨c’ ∨c ))=(a ∧b )∨(a ∨c )=(a ∨(a ∨c ))∧(b ∨a ∨c )=(a ∨c )∧(a ∨c ∨b )=a ∨c四、证明题（共20分）1.在自然推理系统中，构造推理证明：前提：∀x (F (x )∨G (x ))结论：⌝∀xF (x )→ ∃xG (x )证明：(1) ⌝∀xF (x ) 附加前提引入(2) ∃x ⌝F (x ) (1)置换(3) ⌝F (c )(2)EI 规则(4) ∀x (F (x )∨G (x )) 前提引入(5) F (c )∨G (c ) (4)UI 规则(6) G (c )) (3)(5)析取三段论(7) ∃xG (x )(6)EG 规则2.设代数系统〈A ，*〉是独异点，e 是其单位元．若∀a ∈A ，有a *a =e ，证明：〈A ，*〉是Abel 群．证明：由于对∀a ∈A ，有a *a =e ，因此，A 中任意元素a 都有逆元，且a=a -1．又〈A ，*〉是有单位元的独异点，从而〈A ，*〉是群．∀a ，b ∈A ，有a *b ∈A ，且a=a -1，b=b -1，(a *b )-1=a *b ．又(a *b )-1=b -1*a -1=b *a ，因此　a *b =b *a ，即〈A ，*〉是Abel 群．3.证明：若无向图G 为欧拉图，则G 无桥．证明：（1）假设G 中有桥，不妨设e =(u ，v ) 为其一座桥．这样，从中删去边e =(u ，v )后，所得图G ’一定不连通（G ’至少含有两个连通分支）．由于G 为欧拉图，因此它是连通图，且有经过每条边一次且仅一次的回路，这条回路必经过G 的所有顶点．从而存在顶点v 1，v 2，…，v s ，使得uv 1v 2…v s vu 是G 的一条回路．从G 中删去边e =(u ，v )后，所得图G ’仍有从u 到v 的通路uv 1v 2…v s v ，这样G ’仍是连通图．矛盾．因此，G 中一定无桥．（2）由于G 为欧拉图，其每个顶点的度数均为偶数．假设G 中有桥，不妨设e =(u ，v ) 为其一座桥．这样，从中删去边e =(u ，v )后，所得图G ’至少有两个连通分支．而且，顶点u ，v 的度数都是奇数，这与每个连通分支为图矛盾（与握手定理矛盾），因此，G 中一定无桥．。

离散数学-期末复习题及答案课程名称:《离散数学》一、单项选择题1、 (D)。

下列句子是命题的为。

A 、这朵花多好看呀！B 、明天下午有会吗？C 、5y x >+D 、地球外的星球上也有人。

2、 (A)。

李平不是不聪明，而是不用功。

p:李平聪明q:李平用功。

符号化为。

A 、 q )p (??∧ B 、q p ??∧ C 、q )p (∧?? D 、q )p (?∨ 3、 (A)。

与)q p (∨?命题公式等值的是。

A 、q p ??∧ B 、q p ??∨ C 、q p ∧ D 、q)(p ∧?4、 (D)。

含有3个命题变项的简单和取式中一定可形成种不同的极小项。

A 、2 B 、4 C 、6 D 、85、 (C)。

q )q p (∧→?此公式的类型为。

A 、重言式B 、永真式C 、矛盾式D 、可满足式 6、 (C)。

q )q )q p ((→∧→此公式的类型为。

A 、矛盾式B 、可满足式C 、重言式D 、永假式7、 (A)。

设A 是含有3个命题变项的公式,若它的主析取范式中含有8个极小项,则它是。

A 、重言式B 、矛盾式C 、可满足式D 、永假式8、 (B)。

只有天下大雨,他才乘公共汽车上班.p:天下大雨q:他乘车上班,符号化为。

A 、q p → B 、p q → C 、q p →?D 、p q →?9、 (B)。

不经一事,不长一智p:经一事q:长一智,符号化为。

A 、p q →B 、q p ??→C 、p q ??→ D 、q p → 10、 (B)。

R Q P →∧?)(成真赋值为。

A 、 000,001,110B 、 001,011,101,110,111C 、全体赋值D 、无11、 (B)。

公式Q P→的主析取范式为)3,1,0(∑，则公式的主合取范式为。

A 、)2(TB 、)2(∏C 、)3,1,0(∏D 、)3,2,1,0(∏12、 (A)。

R Q P →∧?成假赋值为。

A 、 100，B 、 001,011,101,110,111C 、全体赋值D 、无13、 (B)。

而用长为3的等长码字传输需要30000个二进制数字。
解答：用Huffman算法求频率（乘以100）为权的最优2元树，其中w1=5，w2=5，w3=10，w4=10，w5=15，w6=20，w7=35；最优2元树如图所示：
故，可采取如下编码：A---11 B---01 C---101 D---100 E---001
F---0001 G---0000
传输100个按比例出现的7个字母所需二进制数字的个数为w(T)=255个，故传输10000个所用二进制数字的个数为25500个。
1.求命题公式：(PQ)(QP)的主析取范式和主合取范式。
答案：用等值演算法、真值表法均可，根据解题过程及答案正确与否酌情给分。
主吸取范式为：(PQ)(PQ)(PQ)=(0,2,3)
主合取范式为：PQ
2.设A={a,b,c,d}，1、2、3是A上的划分，1={{a,b},{c,d}}，2={{a},{b},{c},{d}}，3={{a,b,c,d}}，试求：
⑩x(F(x)R(x)G(x)) T，⑨，EG
(2)设7个字母在通信中出现的频率如下：
A：35% B：20% C：15% D：10%
E：10% F：5% G：5%
采用2元前缀码，求传输数字最少的2元码（即最小前缀码），并求传输10000个按上述比例出现的八进制数字需要多少个二进制数字？若用长为3的等长码字传输需要多少个二进制数字？
答案：QP
2.对命题公式：P（QR）PQ化为仅含和的等价表达式。
答案：（PQ）
3.设S(x)：x是火车，L(x)：x是卡车，F(x,y)：x比y快。在谓词逻辑中符号化命题“所有火车都比所有卡车快”。
答案： x(S(x)→y(L(y) ∧F（x , y）)

离散数学试题(B卷答案1）一、证明题（10分）1)(⌝P∧(⌝Q∧R))∨(Q∧R)∨(P∧R)⇔R证明: 左端⇔(⌝P∧⌝Q∧R)∨((Q∨P)∧R)⇔((⌝P∧⌝Q)∧R))∨((Q∨P)∧R)⇔(⌝(P∨Q)∧R)∨((Q∨P)∧R)⇔(⌝(P∨Q)∨(Q∨P))∧R⇔(⌝(P∨Q)∨(P∨Q))∧R⇔T∧R(置换)⇔R2) ∃x (A(x)→B(x))⇔∀xA(x)→∃xB(x)证明：∃x(A(x)→B(x))⇔∃x(⌝A(x)∨B(x))⇔∃x⌝A(x)∨∃xB(x)⇔⌝∀xA(x)∨∃xB(x)⇔∀xA(x)→∃xB(x)二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分）。

证明：(P∨(Q∧R))→(P∧Q∧R)⇔⌝(P∨(Q∧R))∨(P∧Q∧R))⇔（⌝P∧(⌝Q∨⌝R)）∨(P∧Q∧R)⇔(⌝P∧⌝Q)∨(⌝P∧⌝R))∨(P∧Q∧R)⇔(⌝P∧⌝Q∧R)∨(⌝P∧⌝Q∧⌝R)∨(⌝P∧Q∧⌝R))∨(⌝P∧⌝Q∧⌝R))∨(P∧Q∧R)⇔m0∨m1∨m2∨m7⇔M3∨M4∨M5∨M6三、推理证明题（10分）1）C∨D， (C∨D)→⌝E，⌝E→(A∧⌝B)， (A∧⌝B)→(R∨S)⇒R∨S 证明：(1) (C∨D)→⌝E P(2) ⌝E→(A∧⌝B) P(3) (C∨D)→(A∧⌝B) T(1)(2)，I(4) (A∧⌝B)→(R∨S) P(5) (C∨D)→(R∨S) T(3)(4)， I(6) C∨D P(7) R∨S T(5)，I2) ∀x(P(x)→Q(y)∧R(x))，∃xP(x)⇒Q(y)∧∃x(P(x)∧R(x))证明(1)∃xP(x) P(2)P(a) T(1)，ES(3)∀x(P(x)→Q(y)∧R(x)) P(4)P(a)→Q(y)∧R(a) T(3)，US(5)Q(y)∧R(a) T(2)(4)，I(6)Q(y) T(5)，I(7)R(a) T(5)，I(8)P(a)∧R(a) T(2)(7)，I(9)∃x(P(x)∧R(x)) T(8)，EG(10)Q(y)∧∃x(P(x)∧R(x)) T(6)(9)，I四、某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。

东北大学考试试卷（B卷）2011—2012 学年第 1 学期课程名称： 离散数学总分 一 二 三 四 五 六 七 八一．将下面命题符号化(8分)1．如果天气好，我将去游乐场，否则我将呆在家中。

(P→Q)∧(¬P→R)2．只有计算机专业的学生和非大一学生才可以访问校园网。

R→(P∨Q)3．并非所有学习好的大学生都想成为科学家。

¬∀x((A(x) ∧B(x)) →C(x))4．尽管有人聪明，但未必一切人都聪明。

∃x(A(x) ∧B(x)) ∧¬∀x((A(x) →B(x))二．(10分) 填空(每空1分)1.（3分）A与B是全集E的子集,给定集合X={P,Q,R,S,T,U,V,W,Y,Z},其中的元素都表示命题，如下所示：P: A－B=A Q:A∩B=B R:A⊆B S: A⊆∼B T: B⊆AU: ∼B⊆∼A V:A∩B=Φ W:A∪B=B Y: ∼A⊆∼B Z: B⊆∼A又令R是X上的命题等价关系,则商集X/R=({{P,S,V,Z},{R,U,W},{Q,T,Y}} )2.(每空1分)令R和S都是人类上的关系，且R={<x,y>|x是y的父亲} S={<x,y>|x是y的母亲} 则S o R表示( 祖母和孙子 )关系； R o S C表示( 夫妻 )关系。

3.(每空1分) 设f是从A到B的函数，g是从B到A的函数，如果f go是双射的，则f是__满___射的，g是__入___射的。

4.(每空1分)A,B是有限集合, P(A)表示A的幂集,已知|A|=3,|P(B)|=64,|P(A∪B)|=256, 则|B|=( 6 ), |A-B|=( 2 ), |A⊕B|=( 7 )。

三．(8分)写出命题公式P→((R→Q)∧(¬R→¬Q)) 的主析取范式。

解：P→((R→Q)∧(¬R→¬Q))⇔¬P∨((¬R∨Q)∧(R∨¬Q))⇔(¬P∨¬R∨Q) ∧(¬P∨ R∨¬Q)即命题公式的主合取范式中的大项为M6和M2所以其主析取范式中的小项有m0,m3,m4,m5,m6,m7即主析取范式为：(P∧R∧Q)∨( P∧¬R∧¬Q) ∨(¬P∧R∧Q) ∨(¬P∧R∧¬Q) ∨(¬P∧¬R∧Q) ∨(¬P∧¬R∧¬Q) 四．(15分)已知R1、R2是集合Ａ上的等价关系，问R1∪R2、R1∩R2、R1-R2、r((A×A)-R1)中哪些是A上的等价关系？如果不是说明理由，或举反例。

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 .2.g , g , g .3.1,2,4.4.8，不存在，不存在.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}.5.9.四、证 对于任意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 →→↔→→=的主析取范式为).()()()()()(r q p r q p r q p r q p r q p 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，…，则排列计数生成函数()x x x x x x x E +⎪⎪⎭⎫ ⎝⎛++⎪⎪⎭⎫ ⎝⎛+++=1!21!3!21)(23265432121211219619431x x x x x x ++++++=, 因而38!412194=⋅=a .。

离散数学期末考试试题及答案一、选择题（每题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。