山东大学网络教育《离散数学(1-3)》

《离散数学》题库答案一、选择或填空(数理逻辑部分)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),(5),(6)4、公式∀x((A(x)→B(y,x))∧ ∃z C(y,z))→D(x)中,自由变元就是( ),约束变元就是( )。

答:x,y, x,z5、判断下列语句就是不就是命题。

若就是,给出命题的真值。

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

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

(3) 您喜欢唱歌不？ (4) 若7+8＞18,则三角形有4条边。

(5) 前进！ (6) 给我一杯水吧！答:(1) 就是,T (2) 就是,F (3) 不就是(4) 就是,T (5) 不就是 (6) 不就是6、命题“存在一些人就是大学生”的否定就是( ),而命题“所有的人都就是要死的”的否定就是( )。

答:所有人都不就是大学生,有些人不会死7、设P:我生病,Q:我去学校,则下列命题可符号化为( )。

(1) 只有在生病时,我才不去学校 (2) 若我生病,则我不去学校(3) 当且仅当我生病时,我才不去学校(4) 若我不生病,则我一定去学校答:(1) P Q →⌝ (2) Q P ⌝→ (3) Q P ⌝↔ (4)Q P →⌝8、设个体域为整数集,则下列公式的意义就是( )。

大一离散数学知识点归纳离散数学是大一学生在计算机科学和相关学科中最常接触的数学分支之一。

它涉及的知识点广泛且重要，对于学习和理解其他高级课程至关重要。

下面是对大一离散数学知识点的归纳。

1. 集合论1.1 集合的定义和表示1.2 集合的运算（并、交、差、补）1.3 子集、真子集、幂集1.4 集合的基本性质（交换律、结合律、分配律）1.5 集合的等价关系和等价类1.6 集合的基数和无限集2. 逻辑与命题2.1 命题的定义和性质2.2 命题的逻辑运算（与、或、非、异或、蕴含、等价）2.3 命题的真值表和简化2.4 谓词逻辑和量词2.5 命题逻辑的推理和证明方法2.6 命题逻辑的应用（布尔代数、逻辑电路）3. 数理归纳法3.1 数学归纳法的基本原理3.2 强归纳法和弱归纳法3.3 数学归纳法的应用（证明数学命题、计算算法复杂度）4. 图论4.1 图的基本概念（顶点、边、度、路径、环）4.2 连通图和孤立点4.3 树和森林4.4 图的遍历算法（深度优先搜索、广度优先搜索）4.5 最小生成树和最短路径问题4.6 图的应用（社交网络、路线规划）5. 关系与函数5.1 关系的定义和表示5.2 关系的性质（自反性、对称性、传递性、等价关系） 5.3 关系的闭包和传递闭包5.4 函数的定义和性质5.5 单射、满射和双射5.6 函数的复合和反函数6. 组合数学6.1 排列和组合的基本概念6.2 二项式系数和杨辉三角6.3 递归和递推关系6.4 置换和循环节6.5 容斥原理和鸽笼原理6.6 组合数学的应用（概率、计数问题）7. 布尔代数7.1 逻辑代数和布尔运算7.2 布尔函数和真值表7.3 极小项和主析取范式7.4 逻辑函数的化简和设计7.5 布尔代数的应用（逻辑电路、开关网络）这些是大一离散数学课程中的一些重要知识点，通过对这些知识点的学习和理解，学生将能够为将来的计算机科学和相关领域的学习打下坚实的基础。

同时，离散数学的思维方式和证明方法也会培养学生的逻辑思维和问题解决能力。

离散数学大一上知识点总结离散数学是计算机科学和数学专业中一门重要的基础课程，它主要研究离散的数学结构和离散对象。

在大一上学期的学习中，我们学习了一些离散数学的基础知识和概念。

本文将对这些知识点进行总结和归纳。

1. 集合论(Set Theory)- 集合的定义和表示方法；- 子集、并集、交集和补集的运算；- 集合的基本运算规则；- 集合的基数和幂集；2. 命题逻辑(Propositional Logic)- 命题和命题变量；- 逻辑运算符（非、与、或、异或、蕴含、等价）；- 真值表和逻辑等价性；- 合取范式和析取范式；3. 谓词逻辑(Predicate Logic)- 谓词逻辑的基本概念；- 量词（全称量词和存在量词）；- 代入实例和量化顺序；- 合取与析取的关系；4. 图论(Graph Theory)- 图的基本概念（顶点、边、路径、环）；- 图的表示方法（邻接矩阵、邻接表）；- 图的遍历算法（深度优先遍历、广度优先遍历）；- 最短路径算法（Dijkstra算法、Floyd-Warshall算法）；5. 关系(Relations)- 关系的定义和表示方法；- 关系的性质（自反性、对称性、传递性）；- 等价关系和偏序关系；- 关系的闭包和传递闭包；6. 函数(Function)- 函数的定义和表示方法； - 单射、满射和双射的概念； - 函数的复合和反函数；- 函数的性质和分类；7. 计数(Counting)- 排列和组合的概念；- 基本计数原理和乘法原理； - 集合的幂级数；- 分配原理和容斥原理；8. 递归(Recursion)- 递归的定义和特性；- 递归关系的建立和求解； - 递归算法的设计和分析；- 递归的应用领域；9. 张量(Tensor)- 张量的定义和表示方法；- 张量的运算规则；- 张量的秩和余秩；- 张量的应用领域；10. 图的着色(Graph Coloring)- 图的着色问题的基本概念；- 色数和固定点数的关系；- 图的可着色性定理；- 图的四色定理及其证明；总结：离散数学作为计算机科学和数学领域的重要基础课程，涵盖了集合论、逻辑、图论、关系、函数、计数、递归、张量和图的着色等多个知识点。

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

形考任务一试题及答案题目为随机，用查找功能(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))中的（）。

《离散数学》题库答案一、选择或填空（数理逻辑部分）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），（5），（6）4、公式∀x((A(x)→B(y ，x))∧ ∃z C(y ，z))→D(x)中，自由变元是( )，约束变元是( )。

答：x,y, x,z5、判断下列语句是不是命题。

若是，给出命题的真值。

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

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

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

(5) 前进！ (6) 给我一杯水吧！答：（1） 是，T （2） 是，F （3） 不是（4） 是，T （5） 不是 （6） 不是6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。

答：所有人都不是大学生，有些人不会死7、设P ：我生病，Q ：我去学校，则下列命题可符号化为( )。

(1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校(3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校答：（1） P Q →⌝ （2） Q P ⌝→ （3） Q P ⌝↔ （4）Q P →⌝8、设个体域为整数集，则下列公式的意义是( )。

(1) ∀x ∃y(x+y=0) (2) ∃y ∀x(x+y=0)答：（1）对任一整数x 存在整数 y 满足x+y=0（2）存在整数y 对任一整数x 满足x+y=09、设全体域D 是正整数集合，确定下列命题的真值：(1) ∀x ∃y (xy=y) ( ) (2) ∃x ∀y(x+y=y) ( )(3) ∃x ∀y(x+y=x) ( ) (4) ∀x ∃y(y=2x) ( )答：（1） F （2） F （3）F （4）T10、设谓词P(x)：x 是奇数，Q(x)：x 是偶数，谓词公式 ∃x(P(x)∨Q(x))在哪个个体域中为真?( )(1) 自然数 (2) 实数 (3) 复数 (4) (1)--(3)均成立答：（1）11、命题“2是偶数或-3是负数”的否定是（ ）。

山东大学网络教育离散数学卷(1)-参考答案-CAL-FENGHAI-(2020YEAR-YICAI)_JINGBIAN山东大学网络教育离散数学试卷 （参考答案）一、 选择题1、设}}8,7,6{},5,4{},3,2,1{{=A ，下列选项正确的是：（3）（1）A ∈1 （2）A ⊆}3,2,1{ （3）A ⊂}}5,4{{ （4）A ∈∅2、对任意集合C B A ,,，下述论断正确的是：（1）（1）若C B B A ⊆∈,，则C A ∈ （2）若C B B A ⊆∈,，则C A ⊆（3）若C B B A ∈⊆,，则C A ∈ （4）若C B B A ∈⊆,，则C A ⊆3、假设},,{c b a A =上的关系如下，具有传递性的关系是：（4）（1）},,,,,{>><><><><<a b b a a a a c c a（2）},,,{>><><<a a a c c a（3）},,{>><<a c c a（4）},{><c a4、非空集合A 上的空关系R 不具备下列哪个性质：（1）（1）自反性 （2）反自反性 （3） 对称性 （4）传递性5、假设},,{c b a A =，}2,1{=B ，令：B A f →:，则不同的函数个数为：（2）（1）2+3个 （2）32个 （3）32⨯个 （4）23个6、假设},,{c b a A =，}2,1{=B ，下列哪个关系是A 到B 的函数：（3）（1）}2,1,2,1,2,1,{>><><><><><<=c c b b a a f（2）},,,,,,{>><><><><><<=c c a c b b a b b a a a f（3）}1,2,1,{>><><<=c b a f（4）},1,2,1{>><><<=c b a f7、一个无向简单图G 有m 条边，n 个顶点，则图中顶点的总度数为：（3）（1）2m （2）2n （3）m 2 （4）n 28、一个图是欧拉图是指：（1）（1）图中包含一条回路经过图中每条边一次且仅一次；（2）图中包含一条路经过图中每条边一次且仅一次；（3）图中包含一条回路经过图中每个顶点一次且仅一次；（4）图中包含一条路经过图中每个顶点一次且仅一次。

山东大学《离散数学》
2021-2022学年第一学期期末试卷
一、选择题（）
25分
二、用主析取范式或主合取范式判断下述每一对公式是否等值．（10分）
(1)A=(p q)(p q r)，B=(p(q r))(q(p r))
(2)A=(p(p q))r，B=(p q)(r q)
三、将下列命题符号化，并求命题的真值.（15分）
(1)只要4是偶数，5就是奇数.
(2)如果4是偶数，则5也是偶数.
(3)只有4是偶数，5才是偶数.
四、指出下述推理满足的推理定律.（50分）
(1)如果今天天气好,我外出游玩.如果今天天气不好,我也外出游玩.所以我外出游玩.
(2)如果今天天气好,我外出游玩.我没有外出游玩.所以今天天气不好.
(3)如果今天天气好,我外出游玩.如果我外出游玩,我去颐和园.所以,如果今天天气好,我去颐和园.
(4)李四喜欢吃甜的和酸的.所以李四喜欢吃甜的.
(5)a是偶数或是素数.a是奇数.所以a是偶数.。