【浙江工商大学】《离散数学》期末考试题(B)

..一、填空2．A ，B ，C 表示三个会合，文图中暗影部分的会合表达式为 (B⊕C)-AA C4．公式(PR)(SR)P的主合取范式为(PSR) ( PS R)。

5．若解说I 的论域D 仅包括一个元素，则 xP(x) xP(x) 在I 下真值为 1 。

6．设A={1，2，3，4}，A 上关系图以下，则 R^2={(1,1),(1,3),(2,2),(2,4)}。

//备注： 0 1 0 01 0 1 0 0 1 0 1R 1 0 1 0 R 20 0 0 1 0 0 0 00 0 0 00 0 0 07．设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 da abcd b b c d a ccdabd 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}。

;....3、设A={1，2，3}，则A 上的二元关系有（ C ）个。

离散期末考试题一、选择题（每题3分，共30分）1. 在离散数学中，以下哪个概念用于描述两个集合之间的一一对应关系？A. 并集B. 交集C. 映射D. 子集2. 以下哪个命题的否定是正确的？A. 如果今天是周一，那么明天是周二。

B. 如果下雨，那么地面会湿。

C. 如果x > 0，则x² > 0。

D. 所有的鸟都会飞。

3. 在图论中，一个连通图是指图中任意两个顶点之间都存在一条路径。

以下哪个选项描述的不是连通图？A. 完全图B. 树C. 环D. 星形图4. 以下哪个逻辑运算符表示逻辑“或”？A. ∧B. ∨C. ¬D. →5. 在集合论中，以下哪个符号表示集合的差集？A. ∪B. ∩C. -D. ×6. 以下哪个命题是永真命题？A. p ∧ ¬pB. p ∨ ¬pC. p → ¬pD. ¬(p → ¬p)7. 在关系R中，如果对于任意的a, b ∈ A，都有(a, b) ∈ R和(b,a) ∈ R，则称R是对称的。

以下哪个关系不是对称的？A. 等价关系B. 子集关系C. 整除关系D. 朋友关系8. 在命题逻辑中，以下哪个等价于“p且q”？A. ¬p ∨ ¬qB. p ∧ qC. ¬p → ¬qD. ¬(p → ¬q)9. 在图论中，以下哪个术语描述的是一个图中没有环的子图？A. 路径B. 连通图C. 树D. 环10. 在集合论中，以下哪个符号表示集合的笛卡尔积？A. ×B. ∪C. ∩D. -二、填空题（每题2分，共20分）11. 如果集合A有n个元素，那么集合A的子集个数是________。

12. 在逻辑中，一个命题的________是当原命题为真时，它为假；当原命题为假时，它为真的命题。

13. 如果一个图的每个顶点的度数都是偶数，则该图一定存在________。

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

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

第 1 页/共 4 页《离散数学》考试试卷（试卷库14卷）试题总分： 100 分 考试时限：120 分钟一、选择题（每题2分，共20分）1. 下述命题公式中，是重言式的为( )（A ）)()(q p q p ∨→∧ （B ）q p ∨))()((p q q p →∨→⇔（C ）q q p ∧→⌝)(（D ）q q p →⌝∧)(2. 对任意集合A,B,C,下列结论正确的是（ ）（A ）若A ⊆B,B ∈C,则A ⊆C ； （B ）若A ∈B,B⊆C,则A ⊆C ； （C ）若A ⊆B,B ∈C,则A ∈C ； （D ）若A ∈B,B ⊆C,则A ∈C ； 3. 设} 3 ,2 ,1 {=S ，定义S S ⨯上的等价关系,,则由R 产生的S S ⨯上一个划分共有( )个分块。

（A ）4（B ）5（C ）6（D ）94. 下列偏序集( )能构成格5. 连通图G 是一棵树当且仅当G 中( )（A ）有些边是割边 （B ）每条边都是割边（C ）所有边都不是割边 （D ）图中存在一条欧拉路径6. 有n 个结点)3(≥n ，m 条边的连通简单图是平面图的必要条件( )（A ） 63-≤n m（B ）63-≤m n （C ）63-≥n m （D ） 63-≥m n7. 设P,Q 的真值为0,R,S 的真值为1,则下面命题公式中真值为1的是（ ）（A ）R →P （B ）Q ∧S （C ）P S （D ）Q ∨R 8. 在图G=<V,E>中,结点总度数与边数的关系是（ ）（A ）deg()2||i v E =（B ）deg()||i v E =（C ）deg()2||iv Vv E ∈=∑（D ）deg()||iv Vv E ∈=∑9. 设有33盏灯,拟公用一个电源,则至少需有五插头的接线板数（ ）（A ）７ （B ）８ （C ）９ （D ）１４ 10. 设集合A 上有四个元素,则A 上的不同的等价关系的个数为（ ）（A ）11 （B ）14 （C ）17（D ）15二、填空题（每题2分，共20分）1. 设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为则R= 。

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

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

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

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

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

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

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

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

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

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

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

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

一．填空题（每小题2分，共10分）1。

谓词公式的前束范式是__∃x∃y¬P（x)∨Q(y）__________。

2。

设全集则A∩B =__{2｝__，_{4，5｝____，__｛1，3,4，5} _____3. 设，则__ {｛c}，｛a,c}，｛b，c}，{a,b,c}} __________,_____Φ_______。

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

5．如果连通平面图G有个顶点，条边，则G有___e+2—n____个面.二．选择题（每小题2分，共10分)1. 与命题公式等价的公式是（)（A) （B）（C）（D)2. 设集合,A上的二元关系不具备关系( ）性质（A）(A)传递性（B)反对称性（C）对称性(D)自反性3。

在图中，结点总度数与边数的关系是（)（A) (B) （C)(D)4。

设D是有n个结点的有向完全图，则图D的边数为（）(A) (B）(C）(D)5. 无向图G是欧拉图,当且仅当（)(A)G的所有结点的度数都是偶数（B)G的所有结点的度数都是奇数（C）G连通且所有结点的度数都是偶数（D) G连通且G的所有结点度数都是奇数.三．计算题（共43分）1. 求命题公式的主合取范式与主析取范式.（6分）解：主合取方式：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.72. 设集合上的二元关系R的关系矩阵为,求的关系矩阵，并画出R,的关系图。

（10分）3 无向图G有12条边,G中有6个3度结点，其余结点的度数均小于3，问G中至少有多少个结点？（10分）解：∵G(V，E）,｜E |=V，d（Vi)〈3，设至少有x个节点，由握手定理得:2×12=∑d(Vi）〈6×3+（x—6)×32<（x-6) =＞x〉8故G中至少有9个节点。

浙江工业大学期终考试命题稿2010 /2011 学年第 1 学期命题注意事项：一、命题稿请用A4纸电脑打印，或用教务处印刷的命题纸，并用黑墨水书写，保持字迹清晰，页码完整。

二、两份试题必须同等要求，卷面上不要注明A、B字样，由教务处抽定A、B卷。

三、命题稿必须经学院审核，并在考试前两周交教务处。

浙江工业大学2012/2013 学年第1学期试卷课程＿＿＿＿＿＿＿＿姓名＿＿＿＿＿＿＿＿班级＿＿＿＿＿＿＿＿学号＿＿＿＿＿＿＿＿一、选择 15分（每小题 3分）1．下列语句是命题的是（ A ）。

A、离散数学是重要的一门必修课。

B、1+101=110？C、我正在说谎。

D、全体起立！2．图的邻接矩阵为( C )。

A、 B、 C、 D、3．下列排列能构成图的顶点度序列的是（ A ）。

A、1,2,2,3,4B、2,3,4,5,6,7C、2,1,1,1,2D、3,3,5,6,04．设，则IA =（ D ）。

A、 A ；B、A×IA；C、IA×A；D、。

5．下述命题公式中，是重言式的为（ C ）。

A、；B、；C、；D、。

二、填空题15分（每小题 3分）1已知一棵无向树T有三个3度顶点,一个2度顶点,其余的都是1度顶点, 则T中有 5 个1度顶点。

2．设A={1，2，3，4}，A上二元关系R={<2,2>,< 2,3>, < 3,2>, <3,1>}，则S(R)={<2,2>,<2,3>,<3,2>,<3,1>,<1,3>}。

3．A={1，2，3，4，5，6}，A上二元关系，则用列举法给出T={<2,1>,<3,1>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<4,2>,<6,3>,<5,1>, <6,2>}。

《离散数学》期末考试题(G)参考答案一、1.自反性、对称性和传递性.2. 2, 1.3. 6.4. 封闭性和结合性.5. 不含圈的连通.二、1(A); 2(C); 3(B); 4(D); 5(C); 6(B); 7(C); 8(A); 9(B); 10(A).三、1(×); 2(√); 3(√); 4(√); 5(√).四、证 对于任意A b a ∈,，假定)()(b f a f =. 由于≤是偏序，于是a a ≤，所以)(a f a ∈，进而)(b f a ∈，根据定义知b a ≤. 同理可证，a b ≤. 根据偏序的反对称性有b a =，因此f 是单射.当b a ≤时，对于任意)(a f x ∈，于是a x ≤. 根据偏序的传递性有b x ≤，即)(b f x ∈，故)()(b f a f ⊆.五、证 (1) 与非联结词“↑”的运算表如下：(2)p p p p p ↑=∧⌝=⌝)(. )()()())((q p q p q p q p q p ↑↑↑=↑⌝=∧⌝⌝=∧.)()()()()(q q p p q p q p q p ↑↑↑=⌝↑⌝=⌝∧⌝⌝=∨.六、解 ))),(),((),,((v y vQ u x uQ z y x zP y x ∃→∃∧∃∀∀=))),(),((),,((v y vQ u x uQ z y x zP y x ∃∨⌝∃∧∃∀∀=))),(),((),,((v y vQ u x Q u z y x zP y x ∃∨⌝∀∧∃∀∀=))),(),((),,((v y Q u x Q v u z y x zP y x ∨⌝∃∀∧∃∀∀=))),(),((),,((v y Q u x Q z y x P v u z y x ∨⌝∧∃∀∃∀∀七、证 首先，x 和x -1的阶数相同. 其次，当|x | >2时，1-≠x x .令G G f →:，1)(-=x x f ，容易验证f 是双射. 于是阶数大于2的元素成对出现，故其个数为偶数.八、证 (1)根据Euler 公式，有2+-=n m r . (2) 31052)2(5-≤⇒≤+-n m m n m . (3) 若Petersen 图是平面图，由于其每个面至少5条边围成，于是由(2)知3105-≤n m . 因为在Petersen 图中，m = 15, n = 10, 于是31010515-⋅≤，矛盾.。

一、填空题(每小题3分，共15分)1. 在实数集R 上定义运算“*”如下：xy y x y x ++=*, ∈∀y x ,R , 则R 关于“*”的单位元为________, 零元为________, 元素2关于“*”的逆元为________.2. 设A ={l, 2, 3, 4}, A 上的二元关系R ={(1, 2), (3, 4), (4, 3)}, S = {(l, 3), (3, 4), (4, 1)}, 则S R ⋂=________, 1)(-⋃S R =________, S R =________.3. 用联结词⌝，∧表示联结词∨, →和联结词↔：B A ∨= ________,B A →=________, B A ↔=________.4. 设),,(⋅+R 是整环, 则),(+R 是________, ),(⋅R 是运算可交换的含幺________且_____零因子.5. 当________时, 完全图K n 是非平面图. 对于二部图K m , n , 当________时, K m , n 是平面图，当________时，K m , n 是非平面图.二、单选题(每小题3分，共15分)1. 设N +是非零自然数集，f ：N + × N + → N +，y x y x f =),(, ∈y x , N +, 则f ( )(A) 仅是入射 (B) 仅是满射(C) 是双射 (D) 不是函数.2. 在整数集Z 上，下面哪个运算不是．．二元运算( ) (A) 加法 (B) 减法(C) 乘法 (D) 除法.3. 设A 是奇数集合，×为乘法运算，则(A ，×)是( )(A) 半群 (B) 群(C) 循环群 (D) 交换群.4. 下面既是汉密尔顿图又是欧拉图的图形是( )5. 一棵树有3个5度点、1个4度点、3个2度点，其它的都是1度，那么它的边数是（ ）(A) 17 (B) 18(C) 19 (D) 20.三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”.1. 设x 和y 是实数集中的变量, 则x + y > 0是命题函数. ( )2. 关系矩阵⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡001111101对应的关系具有自反性.( )3. 设R 和S 是集合A 上的等价关系，则S R 是A 上的等价关系.( )4. 在公式),()(),(),())((y x P x z x Q y x P y x ∃→∨∃∀中x ∀的辖域为P (x , y ).( )5. 在同构意义下，有限布尔代数只有,,,),((⋂⋃X P ∅, X ). ( )四、(15分) 设p , q , r 为命题变元，分别用等值演算法和真值表法计算(p →q )→r 的主合取范式.五、(10分) 设A ={a , b , c , d }，R ={(a , b ), (a , d ), (b , c ), (c , a ), (d , a )}，求用关系图计算R的传递闭包t (R ).六、(10分) 设A ={2, 3, 6, 12, 24, 36}, 请画出A 上整除关系“|”的哈斯图，并给出子集{6, 12, 24, 36}的极大元、极小元、最大元、最小元、上界、下界、上确界和下确界.七、(10分) 符号化下面命题，并构造推理证明：人是要死的，苏格拉底是人，所以苏格拉底是要死的.八、(10分) 证明：一个图是强连通的，当且仅当图中有一个回路，它至少包含每个结点一次.。

离散数学试题(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人会打这三种球。

离散数学期末考试题及答案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 函数是一种特殊的关系，它将一个集合中的每个元素映射到另一个集合中的唯一元素。

离散数学考试试题及答案一、单项选择题（每题5分，共20分）1. 在离散数学中，以下哪个概念不是布尔代数的基本元素？A. 逻辑与B. 逻辑或C. 逻辑非D. 逻辑异或答案：D2. 下列哪个命题不是命题逻辑中的命题？A. 所有学生都是勤奋的B. 有些学生是勤奋的C. 学生是勤奋的D. 勤奋的学生答案：D3. 在集合论中，以下哪个符号表示集合的并集？A. ∩B. ∪C. ⊆D. ⊂答案：B4. 以下哪个图不是无向图？A. 简单图B. 完全图C. 有向图D. 多重图答案：C二、填空题（每题5分，共20分）1. 如果一个命题的逆否命题为真，则原命题的________为真。

答案：逆命题2. 在图论中，如果一个图的任意两个顶点都由一条边连接，则称这个图为________图。

答案：完全3. 一个集合的幂集是指包含该集合的所有________的集合。

答案：子集4. 如果一个函数的定义域和值域都是有限集合，那么这个函数被称为________函数。

答案：有限三、简答题（每题10分，共30分）1. 请简述什么是图的欧拉路径。

答案：欧拉路径是一条通过图中每条边恰好一次的路径。

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

答案：二元关系是指定义在两个集合之间的关系，它将第一个集合中的元素与第二个集合中的元素联系起来。

例如，小于关系就是一个二元关系。

3. 请说明什么是递归函数，并给出一个简单的例子。

答案：递归函数是一种通过自身定义来计算函数值的函数。

例如，阶乘函数就是一个递归函数，定义为：n! = n * (n-1)!，其中n! = 1当n=0时。

四、计算题（每题10分，共30分）1. 计算以下逻辑表达式：(P ∧ Q) ∨ ¬R答案：首先计算P ∧ Q，然后计算¬R，最后计算两者的逻辑或。

2. 给定集合A = {1, 2, 3}，B = {2, 3, 4}，求A ∪ B。

答案：A ∪ B = {1, 2, 3, 4}3. 已知函数f(x) = 2x + 3，求f(5)。

离散试卷及答案离散数学试题(A 卷及答案）一、证明题（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))∧RT ∧R(置换)R2)x(A(x)B(x))xA(x)xB(x) 证明 ：x(A(x)B(x))x(A(x)∨B(x))xA(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(2) E (A ∧B) (3) (C ∨D)(A ∧B)(4) (A ∧B)(R ∨S)(5) (C ∨D)(R ∨S)(6) C ∨D (7) R ∨S 2) 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))四、设m 是一个取定的正整数，证明：在任取m ＋1个整数中，至少有两个整数，它们的差是m 的整数倍证明 设1a ，2a ，…，1+m a 为任取的m ＋1个整数，用m 去除它们所得余数只能是0，1，…，m －1，由抽屉原理可知，1a ，2a ，…，1+m a 这m ＋1个整数中至少存在两个数s a 和t a ，它们被m 除所得余数相同，因此s a 和t a 的差是m 的整数倍。

精品文档. B 卷1． Show that ((p ∨q)∧⌝p) → q are tautologies. (10 scores)2. Suppose that f(x),g(x) and h(x) are functions such that f(x ) is Ω(g(x)) and g(x) is Ω (h(x)).Show that f(x) is Ω (h(x)).(10 scores)3. Let ⎥⎦⎤⎢⎣⎡=0312A and ⎥⎦⎤⎢⎣⎡=3221B .Find B t A t . (10 scores) 4. Find a compatible total ordering for the poset ({2,4,6,9,12,18,27,36,48,60,72},|).(10 scores) 5 . Let R be the relation on the set of ordered pairs of positive integers such that ((a,b),(c,d)) ∈ R if and only if a+d = b + c. Show that R is an equivalence relation. (15 scores)6. Use adjacency matrix to find the numbers paths between U 1 and U 5 in the graph in Figure1 of length 3, determine whether it is planar and if it is planar ,into how many regions does this graph split the plane? (10 scores)7. Suppose there are 7 finals to be scheduled so that no student has two exams at the same time. Suppose the courses are numbered 1 through 7. Suppose that the following pairs of courses have common students : 1 and 2, 1 and 3, 1 and 4, 1 and 5, 2 and 3, 3 and 4 ,4 and 5.Please schedule the final exams for this. (10 scores)8 . Use Prim ’s algorithm to find a minimum spannig tree in the followinggraph,then use Kruskal ‘s algorithm to find a minimum spannig tree in the same graph. (10 scores)9. Suppose T is an ordered rooted tree.And the inorder listing of T is h,d,b,i,e,j,a,f,c,k,gThe preorder listing of T is a,b,d,h,e,I,j,c,f,g,kPlease draw T and find the postorder listing of T. (15 scores)。