最新-第一学期《离散数学》期中考试资料

华东交大离散数学期中考试试题一、单项选择题1、若一个代数系统是独异点（含幺半群），则以下选项中一定满足的是（）。

A. 封闭性，且有零元;B. 结合律，且有幺元；C. 交换性，且有幺元;D. 结合律，且每个元素有逆元.2、下面代数系统中,中（）不是群A、G为整数集合， *为加法B、G为偶数集合， *为加法C、G为自然数集合，*为加法D、G为实数集合，*为加法3．下列选项中，（）满足交换律。

A．Klein四元群B．半群C．独异点D．群4．三个结点最多可以构成__________个非同构的无向简单图。

A．1 B．2 C．3 D．45. 下列四组数据中，不能成为任何4阶无向简单图的度数序列的为（）A. 1,1,1,3B. 3,2,2,3C. 2,2,2,2D. 1,2,3,46．无向图的关联矩阵中，每行的元素之和为（）。

A．边数的2倍B．2 C．顶点数D．顶点的度数7、二部图（偶图）K2,3是（）。

A．欧拉图 B．哈密顿图 C．非平面图 D．平面图8．3阶无向完全图（K3）不是以下哪种图？（）A．欧拉图B．平面图C．二部图D．哈密顿图二、填空题1．设S ={1, 2, 3}，S上定义的二元运算*如表所示，S中关于*运算的幺元是_____________。

零元是__________。

2、设Z5={0,1,2,3,4,5}，⊕为模6加法，即? x,y∈ Z6 ，x⊕y=（x+y）mod 6，则代数系统中元素2的逆元为_______,代数系统的生成元为__________。

3、一个无向图有4个结点，4条边，其中的3个顶点度数分别为1，2，3，则第4个结点度数一定是_______。

要成为欧拉图至少要添加_____________条边。

4、无向完全图K45．完全二部图K2,3是平面图，它的平面嵌入共有______________个面。

6. 一棵无向树T有4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T中有_____________片树叶。

数理逻辑部分选择、填空及判断✓下列语句不是命题的（ A ）。

(A) 你打算考硕士研究生吗？ (B) 太阳系以外的星球上有生物。

(C) 离散数学是计算机系的一门必修课。

(D) 雪是黑色的。

✓命题公式P→(P∨⌝P)的类型是（ A ）(A) 永真式(B) 矛盾式(C) 非永真式的可满足式(D) 析取范式✓A是重言式，那么A的否定式是( A )A. 矛盾式B. 重言式C. 可满足式D.不能确定✓以下命题公式中，为永假式的是( C )A. p→(p∨q∨r)B. (p→┐p)→┐pC. ┐(q→q)∧pD. ┐(q∨┐p)→(p∧┐p)✓命题公式P→Q的成假赋值是( D )A. 00,11B. 00,01,11C.10,11D. 10✓谓词公式)xxP∧∀中，变元x是 ( B )R(,x)(yA. 自由变元B. 既是自由变元也是约束变元C. 约束变元D. 既不是自由变元也不是约束变元✓命题公式P→(Q∨⌝Q)的类型是( A )。

(A) 永真式 (B) 矛盾式(C) 非永真式的可满足式 (D) 析取范式✓设B不含变元x，)Ax→x∃等值于( A ))((BA. B( D. B∃)xA→x∃)((∃ C. Bx∧Ax( B. )∀)xA→xx∨)A(x(B✓下列语句中是真命题的是( D )。

A．你是杰克吗？ B．凡石头都可练成金。

C．如果2+2=4，那么雪是黑的。

D．如果1+2=4，那么雪是黑的。

✓从集合分类的角度看，命题公式可分为( B )A. 永真式、矛盾式B. 永真式、可满足式、矛盾式C. 可满足式、矛盾式D. 永真式、可满足式✓命题公式﹁p∨﹁q等价于( D )。

A. ﹁p∨qB. ﹁(p∨q)C. ﹁p∧qD. p→﹁q✓一个公式在等价意义下，下面写法唯一的是( D )。

(A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式✓下列含有命题p，q，r的公式中，是主析取范式的是( D )。

《离散数学》期中复习内容：第一章~第三章题型：一、选择题（20%，每题2分）二．填空题（16%，每题2分）三、计算题（15%，每题5分）四、证明题（15%，每题5分）五、判断题（20%，每题2分）六、程序题（14%，每题7分）第1章数学语言与证明方法1.1 常用的数学符号1.计算常用的数学符号式子1.2 集合及其表示法1.用列举法和描述法表示集合2.判断元素与集合的关系(属于和不属于)3.判断集合之间的包含与相等关系，空集(E)，全集(∅)4.计算集合的幂集5.求集合的运算：并、交、相对补、对称差、绝对补6.用文氏图表示集合的运算7.证明集合包含或相等方法一：根据定义, 通过逻辑等值演算证明方法二：利用已知集合等式或包含式, 通过集合演算证明1.3 证明方法概述1、用如下各式方法对命题进行证明。

☐直接证明法：A→B为真☐间接证明法：“A→B为真” ⇔“ ¬B→ ¬A为真”☐归谬法(反证法)：A∧¬B→0为真☐穷举法：A1→B, A2→B,…, A k→B 均为真☐构造证明法：在A为真的条件下, 构造出具有这种性质的客体B ☐空证明法：“A恒为假” ⇒“A→B为真”☐平凡证明法：“B恒为真”⇒“A→B为真”☐数学归纳法：第2章命题逻辑2.1 命题逻辑基本概念1、判断句子是否为命题、将命题符号化、求命题的真值（0或1）。

命题的定义和联结词(¬, ∧, ∨, →, ↔)2、判断命题公式的类型赋值或解释.成真赋值,成假赋值；重言式(永真式)、矛盾式(永假式)、可满足式:。

2.2 命题逻辑等值演算1、用真值表判断两个命题公式是否等值2、用等值演算证明两个命题公式是否等值3、证明联结词集合是否为联结词完备集2.3 范式1、求命题公式的析取范式与合取范式2、求命题公式的主析取范式与主合取范式（两种主范式的转换）3、应用主析取范式分析和解决实际问题2.4 命题逻辑推理理论1、用直接法、附加前提、归谬法、归结证明法等推理规则证明推理有效第3章一阶逻辑3.1 一阶逻辑基本概念1、用谓词公式符号命题（正确使用量词）2、求谓词公式的真值、判断谓词公式的类型3.2 一阶逻辑等值演算1、证明谓词公式的等值式2、求谓词公式的前束范式3、一阶逻辑的演绎推理（补充）程序题：1.编写程序用位串方法，求出它们的交集、相对补集、对称差集、绝对补集。

《离散数学》期中试题姓名：______________ 学号：______________ 一、确定下列各命题的真、假；（1）∅⊆∅（2）∅⊂∅（3）∅∈∅（4）∅⊆｛∅｝（5）∅∈｛∅｝（6）｛a, b｝⊆｛a , b , c,｛a，b，c｝｝（7）｛a, b｝∈｛a，b，c，｛a，b，c｝｝（8）｛a, b｝⊆｛｛a，b｝，｛｛a，b｝｝｝（9）｛a, b｝∈｛｛a，b｝，｛｛a，b｝｝｝（10）{{a, b}}⊂｛｛a，b｝，｛｛a，b｝｝｝（11）对任意集合A，B，C，、若A∈B，B ⊆ C则A∈C。

（12）对任意集合A，B，C，若A∈B，B ⊆C则A ⊆ C。

（13）对任意集合A，B，C，若A ⊆ B，B∈ C则A ∈ C。

（l4）对任意集合A，B，C，若A ⊆ B，B ∈ C则A ⊆ C。

二、对任意集合A，B，C，证明：（1）（A - B）⊕ B = A ⋃ B （2）（A ⊗ B）⋃ C =（A ⋃ C）⊗（B ⋃ C）（3）A ⋃ B = A ⊕（B ⊕（A ⋂ B））证三、归纳定义下列集合：（1）谓词公式。

（2）命题公式（3）十进制非负有穷小数。

（4）全体十进制有理数。

解四、判断下列语句是否是命题，若是命题则请将其形式化：（1）x>0（2）所有的人都是要死的，但有人不怕死。

（3）我明天或后天去苏州的说法是谣传。

（4）如果买不到飞机票，我哪儿也不去。

（5）除非你陪伴我或代我雇辆车子，否则我不去。

（6）如果只有懂得希腊文才能了解柏拉图，那么我不了解柏拉图。

五、用四种不同方法证明下列逻辑等价式：（1）A→(A→B)┝┥A→B（2）A→(B→C)┝┥(A→B)→(A→C)六、用四种不同方法证明下列逻辑蕴涵式：（1）A∧B┝ A↔B（2）(A→B)→A┝ A七、. 设整数集为个体域，判定下列公式的真值(*表示数乘运算)：（1）∀x ∃y(x*y=x)（2）∀x∃y (x*y=1)（3）∀x ∃y(x+y=1)八、. 用谓词公式将下列语句形式化：（1）高斯是数学家，但不是文学家。

《离散数学》期中考试参考答案一、填空题（本题共10个空，每空2分，共20分）1. 设A为任意的公式，B为重言式，则A∨B的公式类型为重言式。

2. 设个体域为非负实数集，A(x,y)表示x+y=y，则∃x∀yA(x,y)的真值为 T ，∀x∃yA(x,y)的真值为 F 。

3. ∀x∃yA(x,y)的否定式是∃x∀y⌝A(x,y) 。

4. 命题公式P→(Q∧⌝R)的成真赋值有 000, 001, 010, 011, 110 ，成假赋值有 100, 101, 111 。

5. {⌝,∧}，或{⌝,∧}，或{↑} 或{↓} 或{⌝,→} 是一个最小联结词组。

6. 由n个命题变元组成不等价的命题公式的个数为22n。

7. 设A是含有n(n≥1)个命题变元的公式，若A为重演式，则A的主析取范式含有2n个小项。

8. 设解释I为：个体域D={a,b},F(x)与G(x)为2个一元谓词，且F(a)=0,G(b)=1,G(a)=1,G(b)=0.在I下，公式∀x(F(x)→G(x))的真值为 F 。

二、简答题（本大题共5个小题，共计60分）1. 在命题逻辑中，把下列命题符号化（每个小题5分，共25分）（1）除非天下大雨，否则小王不会迟到。

P: 天下大雨，Q：小王迟到。

[2分]Q→P [3分]（后面的相同）（2）仅当你走，我将留下。

P: 你走，Q：我留下。

Q→P（3）他一面吃饭，一面听音乐。

P: 他吃饭，Q：他听音乐。

P ∧ Q（4）老王是山东人或河北人。

P: 老王是山东人，Q：老王是河北人。

P∨Q 或 (P∧⌝Q)∨(⌝P∧Q) 或 P∨Q （5）一个数是素数当且仅当它只能被1和它自身整除。

P: 一个数是素数，Q：一个数被1整除，R：一个数被它自身整除。

S：一个数能被除1和它自身以外的数整除P ⇄（Q∧R∧⌝S）2. 在一阶谓词逻辑中，把下列命题符号化（每个小题5分，共10分）（1）尽管有人聪明，但未必一切人都聪明.M(x):x是人，P(x):x聪明。

许昌学院 2019-2020 学年第一学期期中考试试题试题名称：离散数学使用专业：计算机科学与技术、网络工程中俄计算机科学与技术、数字媒体技术一、填空题（根据题意，将各题的正确答案填写在各题的划线处，每空 2 分，共 20 分。

）1. 集合 A={{Ф,0},0}的幂集 P(A)=.2. 设 P ：我生病，Q ：我去学校，则若我不生病，则我一定去学校，命题可符号化为 .3. 公式(( ⌝P ∧ Q) ∨ ( ⌝P ∧ ⌝ Q)) ∧ P 真值=.4. 公式∀x(F(x,y,z)→G(x,y))∧H(x,y,z)中，x 约束出现次.5. 设 A ＝{1,2,3,4,5,6}，B={1,2,3}，从 A 到 B 的关系 R ＝{<x,y>|x=y 2}，R -1= .6. 设 f,h 为实数集上的函数,f(x) = x 2+4x+3,h(x) = x/2,则 h ︒ f = .7. n阶无向完全图 K n 每个结点的度数是 .8. 已知 7 阶连通平面图 G 有 6 个面，则 G 的边数 m 是 11.9. 在一棵树中有 7 片树叶，3 个 3 度结点，其余都是 4 度结点，则该树有个 4 度结点.10. 设 A={2,4,6}，A 上的二元运算*定义为：a*b=max{a,b}，则在群<A,*>中，单位元是.二、单项选择题（从下列各题四个备选答案中选出一个正确答案，并将其代号写在各题的划线处，答案选错或未选者，该题不得分，每小题 2 分，共 20 分。

）1. 下列语句不是命题.A. 北京是中华人民共和国的首都.B. 陕西师大是一座工厂.C. 你喜欢唱歌吗?D. 若 7+8＞18，则三角形有 4 条边.2. 下面符号描述正确的是 .A. 0 = ФB. 0 ⊆ ФC. 0 ∉ ФD. 0 ∈ Ф3. 设函数 f ：N→N（N 为自然数集），f(x)=2x+1，下面函数判断正确的是 .A. f 是单射函数B. f 是满射函数C. f 是双射函数D. f 非单射非满射函数4. 集合 A={1,2,…,10}上的关系 R={<x,y>|x+y=11,x,y ∈A}，则 R 的性质为.A. 自反的B. 对称的C. 传递的，对称的D. 传递的5. 关系 R={<1,< 2,3 >>, <{2},< 2,3 >>, <2,<2,3 >>}，定义域正确的是.A. 1,{2},2B. {1,2,2}C. {1,{2},2}D. {{1,2,2}}6. 下列哪一种图不一定是树 .A . 无回路的连通图.B. 有 n 个顶点 n-1 条边的连通图.C. 连通但删去任一条边便不连通的图.D. 每对顶点间都有路径的图.7. 下图中,不是二部图.0 A. B.C.D. 8 带权 1,3,5,7,8 的最优二叉树，它的权值下列正确的是.A. 32B. 52C. 23D. 249 下面给出的集合中， 是前缀码.A . {x ，xy ，xxy ，xyxxxx} B. {zx ，zzz ，xx ，xy ，xyx}C. {xy ，xxy ，xxx ，y}D. {y ，yy ，yxy ，xxy ，xxyy}10. 设群 G=<Z,+>,则(3)-3= .A. 27B. 1/27C. 9D. -9三、判断题（判断以下论述的正误，认为正确的就在试卷相应位置划“√”，错误的划“x ”，每小题 1 分，共 10 分。

离散数学总复习资料一、鸽笼原理与容斥原理1．求证边长为1的正方形中放9个点，由这些点构成的三角形中，必有一个三角形面积小于18。

证：把该正方形均分成四个相同的小正方形，则由鸽笼原理知，必有一个小正方形内存在三个点，且这三个点构成的三角形面积小于18。

# 2．对一列21n +个不同整数，任意排列，证明一定存在长为1n +的上升子序列或下降子序列。

证：设此序列为：2121,,,,,k n a a a a +，从k a 开始上升子序列最长的长度为k x ，下降子序列最长的长度为k y ，每一个k a 2(1,2,,1)k n =+都对应了(,)k k x y 。

若不存在长为1n +的上升子序列或下降子序列，那么,k k x n y n ≤≤，形如(,)k k x y 的不同点对至多有2n 个，而k a 有21n +个，则由鸽笼原理知，必有,i j a a 2(11)i j n ≤<≤+同时对应(,)i i x y =(,)j j x y ，由于i j a a ≠，若i j a a <，则i x 至少比j x 大1，若i j a a >，则i y 至少比j y 大1，这均与(,)i i x y =(,)j j x y 矛盾。

故原命题成立。

#3．求}100,,2,1{ 中不被3、4、5整除的个数。

解： 设A 表示}100,,2,1{ 中被3整除的数的集合，B 表示}100,,2,1{ 中被4整除的数的集合，C 表示}100,,2,1{ 中被5整除的数的集合，则20,25,33===C B A6,5,8=⋂=⋂=⋂A C C B B A ， 1=⋂⋂C B A ，进而有C B A A C C B B A C B A C B A ⋂⋂+⋂-⋂-⋂-++=⋃⋃601658202533=+---++= 故有4060100=-=⋃⋃-=⋃⋃C B A U C B A即}100,,2,1{ 中不被3、4、5整除的个数为40。

离散数学考试题及答案一、选择题（每题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}，请计算它的幂集，并列出所有元素。

离散期中考试题及答案《离散数学⼀》期中考试题学院：软件学院级：07级专业：通软/计应⼀．填空（共20分）：1. 设集合A={a,b,c,d,e,f,g}，A上的⼀个划分π={{a,b},{c,d,e},{f,g}}，则π所对应的等价关系有_____个⼆元组。

（2分）Let A be {a,b,c,d,e,f,g} and a partition πof A be {{a,b},{c,d,e},{f,g}}.There are____ ordered pairs in the equivalent relation corresponding to π.答：172.某⼀计算机系统的标号标识符是由⼀个英⽂字母后跟3个数字组成，如果允许重复，那么不同的标号标识符可能有多少种？________ （2分）A label identifier, for a computer system, consists of one letter followed by three digits. If repetitions are allowed, how many distinct label identifiers are possible?________答：26×10×10×10即26 000种。

3.从20个⼥⼠和30个男⼠中选出3个⼥⼠和4个男⼠构成7⼈委员会，那么能形成多少种不同的7⼈委员会？________ （2分）How many different seven-person committees can be formed each containing three women from an available set of 20 women and four men from an available set of 30 men?_______答：20C3×30C4或者1140×27405或者31 241 700.4.从10个志愿者中产⽣三⼈委员会。

数学系0801、0802离散数学期中测验题及答案一、填空 15% （每小题3分）1、 设A={2，3，4，5，6}上的二元关系}|,{是质数x y x y x R ∨<><=，则R=⎭⎬⎫⎩⎨⎧)6,5(),5,5(),4,5(),3,5(),2,5(),6,4(),5,4(),6,3(),5,3(),4,3(),3,3(),2,3(),6,2(),5,2(),4,2(),3,2(),2,2( R 的关系矩阵M R =⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛0000011111110001111111111 2、 设A={1，2，3}，则A 上既不是对称的又不是反对称的关系R= {})3,2(),1,2(),2,1( ；A 上既是对称的又是反对称的关系R= A 上空关系 或A 上恒等关系 。

3、表达式 )*()*)*(((f e d c b a ÷+的二元树表示为4、若一棵完全二元（叉）树有2n-1个顶点，则它有 n 片树叶。

5、设G 是有n 个结点m 条边的连通平面图，且有k 个面，则k 等于(m-n+2)二、选择 20% （每小题2分）1、设} 3 ,2 ,1 { S ，S 上关系R 的关系图为则R 具有（ D ）性质。

A ．自反性、对称性、传递性；B ．反自反性、反对称性；C ．反自反性、反对称性、传递性；D ．自反性 。

2、设G 是一棵树，则G 的生成树有( B )棵。

A. 0B. 1C. 2D. 不能确定3、下列哪一种图不一定是树（ C ）。

A.无简单回路的连通图B.有n 个顶点n-1条边的连通图C.每对顶点间都有通路的图D.连通但删去一条边便不连通的图4、下列图中是欧拉图的有( A )。

A.[A]B.[D]C.[A] [C]D.[B] [D]5、N 是自然数集，定义3mod )()( ,:x x f N N f =→（即x 除以3的余数），则f 是（ D ）。

A 、满射不是单射；B 、单射不是满射；C 、双射；D 、不是单射也不是满射三、判断题5%（每小题1分）1、 设A={a,{a}}，则 {a}⊆P(A) （ 错 ）2、 空集只是非空集合的子集 （ 错 ）3、一条回路和任何一棵生成树至少有一条公共边。

《离散数学》题库与答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？( A )(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）不是（命题必须满足是陈述句，不能是疑问句或者祈使句。

）6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。

《离散数学基础》期中考试题（附参考答案）学 期：20XX－20XX 学年第X 学期 学生班级：XX 专业 XXXX-XXXX 班 考试时间：20XX.XX.XX XX:XX-XX:XX am 考试地点：学号：姓名：班级：□必修 □选修一、填空题（共10分，每空1分）1. 我们称 能够表达判断，并且具有确定真值 的陈述句为命题。

2. 在命运题逻辑中，任何命题公式的主合取范式都是存在的，并且是 唯一的 。

3. 把命题公式在其所有解释下所取真值列成一个表，称为G 的 真值表 。

4. 命题公式G=（P ∧Q ）→R ，则G 共有 8 个不同的解释；解释（F ，T ，F ）使G 的真值为 T 。

5. 在推理理论中，前提在推导过程中的任何时候都可以引入使用，这一推理规则叫做（ P 规则 ）。

6. 设集合}}{,{φφ=A ，A 的幂集ρ(A )=φ,{φ},{{φ}},{φ,{φ}}{}。

7. 设R 是集合A 上的二元关系，如果R 是自反的，则它的关系矩阵的主对角线元素（ 全是1 ）。

8. 设R 是集合A 上的二元关系，R -1是R 的逆关系，则R 的关系矩阵与R -1的关系矩阵具有的关系是（ 互为转置矩阵 ）。

9. 设R 是集合A 上的二元关系，如果关系R 同时具有自反性、 反对称性 和传递性，则称R 是A 上的一个偏序关系。

二、选择一个正确答案的代号，填入括号中。

（共20分，每小题2分）1. 下列语句中不能成为命题的是（ D ）。

A ．地球外的星球上也有人；B ．小王是我的同学，也是我的好朋友；C ．11+1=100；D ．我正在说慌。

2. 下列谓词公式中（ C ）不是命题。

A ．(∀x)P(x)； B ．(∃x)P(x)；C ．(∀x)(P(x)∨P(y))；D ．(∃x)(∃y)(P(x) →R(y))3. 个体域为整数集合，下列公式中（ C ）不是命题。

A ．(∀x)(∀y)(x *y=y)；B ．(∀x)(∃y)(x *y=1)；C ．(∀x)(x *y=x)；D ．(∃x)(∃y)(x *y=2)4.下列谓词公式中（A）不正确。

离散数学考试试题及答案离散数学考试试题及答案离散数学是计算机科学和数学中的一门重要学科，它研究的是离散的结构和对象。

离散数学的理论和方法在计算机科学、信息科学、通信工程等领域具有广泛的应用。

下面将为大家提供一些离散数学考试试题及答案，希望对大家的学习和复习有所帮助。

1. 集合论题目(1) 设A={1,2,3,4,5}，B={3,4,5,6,7}，求A∪B的结果。

答案：A∪B={1,2,3,4,5,6,7}(2) 设A={1,2,3,4,5}，B={3,4,5,6,7}，求A∩B的结果。

答案：A∩B={3,4,5}(3) 设A={1,2,3,4,5}，B={3,4,5,6,7}，求A-B的结果。

答案：A-B={1,2}2. 图论题目(1) 给定一个无向图G，顶点集为V={A,B,C,D,E}，边集为E={(A,B),(A,C),(B,D),(C,D),(D,E)}，求该图的邻接矩阵。

答案：邻接矩阵为：A B C D EA 0 1 1 0 0B 1 0 0 1 0C 1 0 0 1 0D 0 1 1 0 1E 0 0 0 1 0(2) 给定一个有向图G，顶点集为V={A,B,C,D,E}，边集为E={(A,B),(B,C),(C,D),(D,E),(E,A)}，求该图的邻接表。

答案：邻接表为：A ->B ->C ->D ->E -> AB -> CC -> DD -> EE -> A3. 命题逻辑题目(1) 判断以下命题是否为永真式：(p∨q)∧(¬p∨r)∧(¬q∨¬r)。

答案：是永真式。

(2) 给定命题p：如果天晴，那么我去游泳；命题q：我没有去游泳。

请判断以下命题的真假：(¬p∨q)∧(p∨¬q)。

答案：是真命题。

4. 关系代数题目(1) 给定关系R(A,B,C)和S(B,C,D)，求R⋈S的结果。

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

《离散数学》期中复习第一章1．Which of the following propositions is false?（ ）(4)(1)．If 2+2≠4，then the sun rises in the east ；(2)．If 2+2≠4，then the sun rises in the west ；(3)．If 2+2=4，then the sun rises in the east ；(4)．If 2+2=4，then the sun rises in the west ．2．Let P, Q denote the propositions “I go to work by bike ．”， and “It is raining ．”，respectively ． Then the proposition “I go to work by bike only if it is not raining ．” can be symbolized as ．P Q →⌝3．Which of the following propositions is the negation of the proposition “2 is even and -3 is negative”?（ 4 ）(1)．2 is even and -3 is not negative ．(2)．2 is odd and -3 is not negative ．(3)．2 is even or -3 is not negative ．(4)．2 is odd or -3 is not negative ．4．Which of the following is false ?（ ）（2）(1)．,P P Q Q ⌝∨⇒； (2)．P Q P ∨⇒；(3)．,Q P Q P ⌝→⇒⌝； (4)．,P P Q Q →⇒．5． Which of the followingequivalences is hold?（ ）(1)（1）．P Q P Q →⇔⌝∨； （2）．P Q Q P →⇔→； （3）．P Q Q P →⇔⌝∨； （4）．P Q Q P →⇔⌝∨⌝． 6．Fill correct logic connectives in the following blanks ．7．Construct the truth table for the following propositional formula ．(())P Q P Q →∧↔8．Show that (),,A B C S A B S C →→→⇒→证：1,23,45,61.(3.()()S P S A P A T A B C P B C T B P C T S C CP →→→→→ 附加前提） 2. （2分）I 4. （2分）5. I6. （2分）7. I 8. （2分）9．Show that D D A C C B B A ⌝⇒∧⌝⌝⌝∧∨⌝→)(,)(, Proof:1． (D P 附加前提) 7． ()B C C ⌝∨∧⌝ P2． ()A D ⌝⌝∧ P 8． ()B C ⌝∨ (7)T I3． D A ⌝∨ (2)T E 9． C (6),(8)T I4． A (1),(3)T I 10． C ⌝ (7)T I5． B A → P 11． C C ∧⌝ (矛盾) (9),(10)T I 6． B (4),(5)T I 由11得出了矛盾,根据归谬法说明原推理正确．9．Show that ．,(),A B C B C S A →⌝⌝∨∧⌝⇒⌝．Pr ：: 1 (A P 附加前提) 2 A B P →⌝3 1,2B T I ⌝4 C B P ⌝∨5 3,4C T I ⌝6 C S P ∧⌝7 6C T I 8 5,7C C T I ∧⌝由8得出了矛盾，根据归谬法说明原推理正确第二章1． Which of the followingequivalences is not hold?（ ）． （2） （1）(()())()()x F x G x xF x xG x ∀∧⇔∀∧∀ （2）(()())()()x F x G x xF x xG x ∃∧⇔∃∧∃（3）(())()x F x G xF x G ∀∧⇔∀∧ （4） (())()x F x G xF x G ∃∧⇔∃∧2． Suppose the universe of discourse {,}A a b =，then the notation of ()xP x ∀without using the quantifiers “∀” is ． (()()P a P b ∧)3．Suppose the universe of discourse {,,}A a b c =，then the notation of （(()())x P x Q x ∀→without using thequantifier “∀” is ．(()())(()())(()())P a Q a P b Q b P c Q c →∧→∧→4． Let ()S x be the predicate “x is an actor,” ()T x be the predicate “x is a teacher,” and (,)A x y be the predicate “x admires y ”，then the logical notation of compound proposition “All actors admire some teachers” is （ ）．(2)(1)．(()(,))x S x A x y ∀→； (2)．))),()(()((y x A y T y x S x ∧∃→∀；(3)．()()(()()(,))x y S x T y A x y ∀∃∧∧； (4)．()()(()()(,))x y S x T y A x y ∀∃∧→．5． Let ()P x be the predicate “x is a horse,” and ()Q x be the predicate “x is an animal,” then the logical notation of compound proposition “All horses are animals but not all animals are horses” is ．(()())(()())x P x Q x x Q x P x ∀→∧⌝∀→或(()())(()())x P x Q x x Q x P x ∀→∧∃∧⌝6． Let ()F x be the predicate “x is metal(金属)” and ()G y be the predicate “y is liquid ”, then the logical notation of compound proposition “Any metal can be dissolved in some liquid” is ．(()(()(,)))x F x y G y H x y ∀→∃∧7． )()()(x x P x ∃⇔∀⌝ , )()()(x x P x ∀⇔∃⌝ ．(()P x ⌝，()P x ⌝)8． Which of the following equivalences is false?（ ）（1）．(()())()()xFx Gx x F x x G x ∀∧⇔∀∧∀ （2）．(()())()()xFx Gx x F x x G x ∃∧⇔∃∧∃ （3）．(())()xFx G x F x G ∀∧⇔∀∧ （4）．(())()xFxG x F x G ∃∧⇔∃∧ 9． Translate the following argument into logical notation and then prove it by supplying explanation for each step ．“Every rational number is real number ． Some rational number are integers ． Therefore , Some real number are integers ．”（Let ()Q x denote “x is a rational number ．” ()R x ：“x is a real number ．” ()Z x ：“x is an integer ．”）))()(())()(())()((x Z x R x x Z x Q x x R x Q x ∧∃⇒∧∃∧→∀ （2分）Proof: (1) ))()((x Z x Q x ∧∃ P (6) )(a Z T(2) I(2) )()(a Z a Q ∧ ES (1) (7) )(a R T(4),(5) I(3) ))()((x R x Q x →∀ P (8) )()(a Z a R ∧ T(6),(7) I(4) )()(a R a Q → US (3) (9) ))()((x Z x R x ∧∃ EG(8)(5) )(a Q T(2) I10．Show that ))()(()())),()(()((x R x F x x xF x R y G x F x ∧∃⇒∃∧→∀．证: (1) ()xF x ∃P(2) ()F a ES(1) (3) (()(()()))x F x G x R x ∀→∧P (4) ()(()())F a G a R a →∧ US(3)(5) ()()G a R a ∧T(2)(4) I(6) ()R a T(5) I (7) ()()F a R a ∧ T(2),(5) I(8) ))()((x Z x R x ∧∃EG(7) 11．Translate the following argument into logical notation using the suggested variables and then prove it using CP-rule by supplying explanation for each step ．“If the weather bureau predicts dry weather, then I will take a hike or go swimming ．I will go swimming if and only if the weather bureau predicts warm weather ．Therefore, if I don’t go on a hike, then the weather bureau predicts wet or warm weather ．”（Let P =“The weather bureau predicts dry weather,” Q =“I will take a hike ，”R =“I will go swimming ，” W=“The weather bureau predicts warm weather ，”）．Solution ：(),()P Q R R W Q P W →∨↔⇒⌝→⌝∨Proof:1． ()P Q R →∨ P 5． R W ↔ P2． P Q R ⌝∨∨ T1，E 6． ()R W → T(5) I3． Q ⌝ P(附加前提) 7． P W ⌝∨ T(4,6) I4． P R ⌝∨ T(2, 3) I 8． ()Q P W ⌝→⌝∨ CP第三章1．Let A={1,2,3,4}，R={<1,2>,<1,3>,<2,1>,<2,2>,<2,4>,<3,3,>} is a relation on set A ． Then the matrix of R is( ) （1）（1）．0110110100100000⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦ （2）．⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡1000001111000101 （3）． ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0111101001011000 （4）． ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0101100011000111 2． Let 1R and 2R be the relations on set A ． Which of the following propositions is ture?（ ）．(1)(1)．If 1R and 2R are reflexive ，then 1R 2R is reflexive ．(2)．If 1R and 2R are irreflexive ，then 1R 2R is irreflexive ．(3)．If 1R and 2R are symmetric ，then 1R 2R is symmetric ．(4)．If 1R and 2R are transitive ，then 1R 2R is transitive ．3． Let 1R and 2R be the relations on {,,,}a b c d given by12{,,,,,,,},{,,,,,,,,,}R a a a b c d d b R a a b a c a d d b b ==then 12R R = ． {,,,,,,,,,}a a a b c d d a d b4． Let A={1,2}, then ()P A =（ ）, where ()P A is the power set of A ． (1)(1)．{,{1},{2},{1,2}}φ；(2)．{,{1},{2}}φ； (3)．{,{1,2}}φ； (4)．{,{1},{1,2}}φ．5． Let A=｛｛1，｛2，3｝｝｝， then ()A ℑ= ． {φ,｛｛1，｛2，3｝｝｝}6． Let A=｛1,2｝， then A×()ℑΦ= ．{〈1，Φ〉，〈2，Φ〉}7． Let A={1,2,3},R =}2,3,3,2,1,2,2,1,1,1{〉〈〉〈〉〈〉〈〉〈 is a relation on set A ．Then R is （ ）． (4)(1)． irreflexive ； (2)．reflexive ； (3)．transitive ； (4)．symmetric ．8．Let A={1,2,3}． R is a relation on set A ． Which of the following is transitive?（ ）．(3)(1)．R={〈1,2〉,〈2,3〉} (2)．R={〈1,2〉,〈2,1〉}(3)．R={〈1,2〉,〈2,3〉,〈1,3〉} (4)．R={〈3,2〉,〈2,3〉}9．Let A ={1，2，3} and R ={1,1,1,2,1,3,3,3}〈〉〈〉〈〉〈〉 be the relations on A ，then R has the propertise of ．antisymmetric and transitive10．Let R be the relation on A ． If R is reflexive, symmetric, antisymmetric and transitive, thenR = ，the matrix of R is ．（A I ，100010001⎛⎫ ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭ 或单位矩阵） 11．If ,A n =，then there are 22n (how many) different relations on set A ．12．Let R be a relation on set A, where A={a,b,c} and R={〈a,b 〉,〈b,c 〉,〈c,c 〉}． Draw the picture of relation R and find its matrix ．Solution ． R 的关系图为R 的关系矩阵为010001001R M ⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦13．If A n =，then there are (how many) different relations on set A ． 22n 14．If ,A n = then ()P A = ． 2n。

一、填空题1设集合，其中A＝{1,2,3}, {1,2}, 则A - B＝{3} ;(A) - (B)＝{3},{1,3},{2,3},{1,2,3}} .2. 设有限集合A, = n, 则|(A×A)| = .3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是1= {(a,1), (b,1)}, 2= {(a,2), (b,2)},3= {(a,1), (b,2)}, 4= {(a,2), (b,1)}, 其中双射的是3, 4 .4. 已知命题公式G＝(P Q)∧R，则G的主析取范式是(P ∧Q∧R)5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为12，分枝点数为3 .6设A、B为两个集合, {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)}, R2 = {(2,1),(3,2),(4,3)}, 则R1R2={(1,3),(2,2),(3,1)} , R2R1 = {(2,4),(3,3),(4,2)} _R12 ={(2,2),(3,3).10. 设有限集A, B，= m, = n, 则| |(A B)| = . 11设是三个集合，其中R是实数集，A = {x | -1≤x≤1, x R}, B = {x | 0≤x < 2, x R},则= -1<<0 , = {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 = (x)(x)，则G的前束范式是x(P(x)∨Q(x)) .15.设G是具有8个顶点的树，则G中增加21 条边才能把G变成完全图。