下载文档原格式
2.8、C1∧C2≈Res(C1,C2)2.10、（消解的完全性）一个合取范式是不可满足的当且仅当它有否证.3.1、由命题公式A1, A2, …, Ak推B的推理正确当且仅当A1∧A2∧…∧Ak→B为重言式.（推理正确不能保证结论一定正确）4.1、闭式在任何解释下都是命题5.1、（前束范式存在定理）一阶逻辑中的任何公式都存在与之等值的前束范式6.1、空集是任何集合的子集。
（推论：空集是唯一的）6.2、（包含排斥原理）设集合S上定义了n条性质，其中具有第i 条性质的元素构成子集Ai, 那么集合中不具有任何性质的元素数为：6.3、德摩根律：A-(B⋃C)=(A-B)⋂(A-C)A-(B⋂C)=(A-B)⋃(A-C)~(B⋃C)=~B~⋂C~(B⋂C)=~B~⋃C7.9、设R为A上的关系, 则(1) R 在A上自反当且仅当IA ⊆R(2) R 在A上对称当且仅当R=R^(-1)(3) R 在A上传递当且仅当R︒R ⊆R7.10、设R为A上的关系, 则有(1) r(R)=R∪R^0(2) s(R)=R∪R^(-1)(3) t(R)=R∪R^2∪R^3∪…9.1、设◦为S上的二元运算，el和er分别为S中关于运算的左和右单位元，则el = er = e为S上关于◦运算的惟一的单位元.9.2、设◦为S上的二元运算，θl和θr分别为S中关于运算的左和右单位元，则θl = θr = θ为S上关于◦运算的惟一的零元.9.3、设◦为S上的二元运算，e和θ分别为◦运算的单位元和零元，如果S至少有两个元素，则e≠θ.9.4、设◦为S上可结合的二元运算, e为该运算的单位元, 对于x∈S 如果存在左逆元yl 和右逆元yr, 则有yl = yr= y, 且y是x 的惟一的逆元.10.2、G为群，∀a,b∈G，方程ax=b和ya=b在G中有解且仅有惟一解. （G中适合消去律）10.3、G为群，a∈G且|a| = r. 设k是整数，则(1) a^k = e当且仅当r | k(r整除k)(2 )|a^-1| = |a|10.4、（子群判定定理一）设G为群，H是G的非空子集，则H是G的子群当且仅当(1) ∀a,b∈H有ab∈H(2) ∀a∈H有a^-1∈H.10.5、（子群判定定理二）设G为群，H是G的非空子集. H是G的子群当且仅当∀a,b∈H有ab^-1∈H.10.6、（子群判定定理三）设G为群，H是G的非空有穷子集，则H是G的子群当且仅当∀a,b∈H有ab∈H.10.7、设H是群G的子群，则He=H，∀a∈G有a∈Ha10.8、设H是群G的子群，则∀a,b∈G有：a∈Hb ⇔ab-1∈H ⇔Ha=Hb10.9、设H是群G的子群，在G上定义二元关系R：∀a,b∈G, <a,b>∈R ⇔ab-1∈H则R是G上的等价关系，且[a]R = Ha.推论：设H是群G的子群, 则(1) ∀a,b∈G，Ha = Hb或Ha∩Hb = ∅(2) ∪{Ha | a∈G} = G10.10、（Lagrange）设G是有限群，H是G的子群，则：|G| = |H|·[G:H]其中[G:H] 是H在G中的不同右陪集(或左陪集) 数，称为H在G 中的指数.推论1：设G是n阶群，则∀a∈G，|a|是n的因子.推论2：对阶为素数的群G，必存在a∈G使得G = <a>.10.11、（循环群的生成元）设G=<a>是循环群. ：(1) 若G是无限循环群，则G只有两个生成元，即a和a-1.(2) 若G是n 阶循环群，则G含有φ(n)个生成元. 对于任何小于n且与n 互质的数r∈{0,1,…,n-1}, ar是G的生成元.10.12、（循环群的子群）设G=<a>是循环群.(1) 设G=<a>是循环群，则G的子群仍是循环群.(2) 若G=<a>是无限循环群，则G的子群除{e}以外都是无限循环群.(3) 若G=<a>是n阶循环群，则对n的每个正因子d，G恰好含有一个d 阶子群.14.1、（握手定理）在任何无向图中，所有顶点的度数之和等于边数的2倍.14.2、（握手定理）在任何有向图中，所有顶点的度数之和等于边数的2倍；所有顶点的入度之和等于所有顶点的出度之和，都等于边数.推论：任何图(无向或有向) 中，奇度顶点的个数是偶数.14.5、在n 阶图G中，若从顶点vi 到vj（vi≠vj）存在通路，则从vi 到vj 存在长度小于或等于n-1 的通路.推论：在n 阶图G中，若从顶点vi 到vj（vi≠vj）存在通路，则从vi 到vj 存在长度小于或等于n-1的初级通路（路径）.14.7、对任意无向图G中，有：κ(G)λ≤(G)δ≤(G)14.8、D强连通当且仅当D中存在经过每个顶点至少一次的回路14.9、D单向连通当且仅当D中存在经过每个顶点至少一次的通路14.10、无向图G=<V,E>是二部图当且仅当G中无奇圈15.1、无向图G是欧拉图当且仅当G连通且无奇度数顶点.15.2、无向图G是半欧拉图当且仅当G 连通且恰有两个奇度顶点.15.5、G是非平凡的欧拉图当且仅当G是连通的且是若干个边不重的圈的并.15.6、设无向图G=<V,E>是哈密顿图，对于任意V1⊂V且V1∅≠，均有p(G-V1) ≤ |V1|设无向图G=<V,E>是半哈密顿图，对于任意的V1⊂V且V1∅≠均有p(G-V1) ≤ |V1|+1 15.7、设G是n阶无向简单图，若对于任意不相邻的顶点vi,vj，均有d(vi)+d(vj) ≥n-1则G 中存在哈密顿通路.推论：设G为n(n≥3) 阶无向简单图，若对于G中任意两个不相邻的顶点vi,vj，均有d(vi)+d(vj) ≥n则G中存在哈密顿回路，从而G为哈密顿图.16.1、设G=<V,E>是n阶m条边的无向图，则下面各命题是等价的：(1) G 是树(2) G 中任意两个顶点之间存在惟一的路径.(3) G 中无回路且m=n-1.(4) G 是连通的且m=n-1.(5) G 是连通的且G 中任何边均为桥.(6) G 中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到惟一的一个含新边的圈.16.2、设T是n阶非平凡的无向树，则T 中至少有两片树叶.16.3、无向图G具有生成树当且仅当G连通.推论1 ：G为n阶m条边的无向连通图，则m≥n-1.推论2 ：余树的边数为m-n+1.推论3 ：余树为G的生成树T的余树，C为G中任意一个圈，则C与余树一定有公共边17.3、平面图各面次数之和等于边数的两倍.17.4、极大平面图是连通的，并且n（n≥3）阶极大平面图中不可能有割点和桥.17.5、设G为n（n≥3）阶极大平面图，则G的每个面的次数均为3.17.6、（欧拉公式）设G为n阶m条边r个面的连通平面图，则n-m+r=217.7、（欧拉公式的推广）设G是具有k（k≥2）个连通分支的平面图，则n-m+r=k+117.8、设G为连通的平面图，且deg(Ri)≥l, l≥3，则m≤ l(n-2)/( l-2)推论：K5，K3,3不是平面图17.10、设G为n（n≥3）阶m条边的简单平面图，则m≤3n-6.17.11、设G为n（n≥3）阶m条边的极大平面图，则m=3n-6.17.12、设G 为简单平面图，则δ(G)≤5.17.13、G是平面图⇔G中不含与K5或K3,3同胚的子图.17.14、G是平面图⇔G中无可收缩为K5或K3,3的子图18.3、设n阶图G中无孤立顶点.(1) 设M为G中一个最大匹配，对于G中每个M非饱和点均取一条与其关联的边，组成边集N，则W=M⋃N为G中最小边覆盖.(2) 设W1为G中一个最小边覆盖；若W1中存在相邻的边就移去其中的一条，设移去的边集为N1，则M1=W1-N1为G中一个最大匹配.(3) G中边覆盖数α1与匹配数β1满足α1+β1=n.推论：设G是n阶无孤立顶点的图. M为G中的匹配，W是G中的边覆盖，则|M| ≤ |W|，等号成立时，M为G中完美匹配，W为G中最小边覆盖.18.4、M为G中最大匹配当且仅当G中不含M的可增广交错路径.18.5、（Hall定理）设二部图G=<V1,V2,E>中，|V1|≤|V2|. G中存在从V1到V2的完备匹配当且仅当V1中任意k(k=1,2,…,|V1|)个顶点至少与V2中的k个顶点相邻.本定理中的条件常称为“相异性条件”.18.6、设二部图G=<V1,V2,E>中，V1中每个顶点至少关联t (t≥1)条边，而V2中每个顶点至多关联t 条边，则G 中存在V1到V2的完备匹配.18.7、对于任意无向图G，均有χ(G) ≤∆(G)+1几个相关性质:χ(G)=1当且仅当G为零图χ(Kn)=n若G为奇圈或奇阶轮图，则χ(G)=3，若G为偶阶轮图，则χ(G)=4.若G的边集非空，则χ(G)=2当且仅当G为二部图18.8、（Brooks定理）若连通无向图G不是Kn,（n≥3），也不是奇数阶的圈，则χ(G) ≤∆(G) 18.10、（四色定理）任何平面图都是4-可着色的。
离散数学第二版最全课后习题答案详解离散数学是现代数学的一个重要分支，它在计算机科学、信息科学、电气工程等领域都有着广泛的应用。
对于学习离散数学的同学们来说，课后习题的解答是巩固知识、加深理解的重要环节。
本文将为您提供离散数学第二版的最全课后习题答案详解，希望能对您的学习有所帮助。
在开始讲解具体的习题答案之前，让我们先简要回顾一下离散数学的主要内容。
离散数学包括集合论、数理逻辑、图论、代数结构等几个部分。
集合论是离散数学的基础，它研究集合的性质、运算和关系。
在集合论的习题中，常见的问题包括集合的表示、集合的运算（并集、交集、补集等）、集合的包含关系以及集合的基数等。
例如，有这样一道习题：设集合 A ＝｛1, 2, 3}，B ＝｛2, 3, 4}，求 A ∪ B 和A ∩ B。
答案是：A ∪ B ＝｛1, 2, 3, 4}，A ∩ B ＝｛2, 3}。
这是因为并集是包含两个集合中所有元素的集合，而交集是同时属于两个集合的元素组成的集合。
数理逻辑是研究推理和证明的工具，它包括命题逻辑和谓词逻辑。
在数理逻辑的习题中，需要掌握命题的符号化、逻辑公式的等价变换、推理规则的应用等。
比如，给出这样一个命题：“如果今天下雨，那么我就不去公园”，将其符号化。
我们可以设“今天下雨”为 P，“我去公园”为 Q，那么这个命题可以符号化为P → ¬Q。
图论是研究图的性质和应用的分支。
图的概念在计算机网络、交通运输等领域有着重要的应用。
图论的习题常常涉及图的表示、顶点的度、路径、连通性、图的着色等问题。
假设有这样一道题：一个无向图有 10 个顶点，每个顶点的度都为 6，求这个图的边数。
根据顶点度数之和等于边数的两倍这个定理，我们可以计算出边数为 30。
代数结构则包括群、环、域等概念，在这部分的习题中，需要理解和运用代数结构的定义和性质来解决问题。
接下来，我们具体来看一些习题的详细解答。
例 1：设集合 A ＝｛x ｜ x 是小于 10 的正奇数}，B ＝｛x ｜ x 是小于 10 的正偶数}，求 A B。
离散数学-详解离散数学（Discrete Mathematics）目录• 1 什么是离散数学• 2 离散数学的发展• 3 离散数学与现代信息技术• 4 参考文献什么是离散数学离散数学是研究离散量的结构及其相互关系的数学学科，离散数学是数学几个分支的总称，研究基于离散空间而不是连续的数学结构。
更一般地，离散数学被视为处理可数集合（与整数子集基数相同的集合，包括有理数集但不包括整数集）的数学分支。
与光滑变化的实数不同，离散数学的研究对象———例如整数、图和数学逻辑中的命题———不是光滑变化的，而是拥有不等、分立的值。
离散数学中的对象集合可以是有限或者是无限的。
特别是，有限数学一词通常指代离散数学处理有限集合的那些部分，特别是在与商业相关的领域。
包括基本的概率论、线性规划、矩阵和行列式的理论。
离散数学的应用遍及现代科学技术的诸多领域，它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学等必不可少的科研基础。
离散数学的发展历史上，离散数学涉及各个领域的一系列挑战性问题。
在图论中，大量研究的动机是企图证明四色定理。
这些研究虽然从1852年开始，但是直至1976年四色理论才得到证明，是由肯尼斯·阿佩尔和沃尔夫冈·哈肯大量使用计算机辅助来完成的。
在逻辑领域，大卫·希尔伯特于1900年提出的公开问题清单的第二个问题是要证明算术公理是一致的。
1931年，库尔特·哥德尔的第二不完备定理证明这是不可能的———至少算术本身不可能。
大卫·希尔伯特的第十个问题是要确定某一整系数多项式丢番图方程是否有一个整数解。
1970年，尤里·马季亚谢维奇证明这不可能做到。
第二次世界大战时盟军基于破解纳粹德军密码的需要，带动了密码学和理论计算机科学的发展。
英国的布莱切利园因而发明出第一部数字电子计算器———巨像计算机。
离散数学（1）复习笔记Ch1 命题逻辑的基本概念1.1 命题命题：能判断真假且⾮真即假的陈述句。
命题的真值，真命题，假命题。
* 真值待定 *简单命题 | 原⼦命题，复合命题。
1.2 常⽤的5个命题联结词否定，合取，析取，蕴涵，双蕴涵。
* 异或 | 排斥或 | 不可兼或 * 注意语义判断。
* p→q = ﹁ p∨q ** 必要条件 * 只有……才……；仅当……，……；……，仅当……。
注意命题符号化的蕴涵⽅向。
* domain * A horse is white. （×）联结词集，⼀元联结词，⼆元联结词。
* 优先顺序 * （），﹁，∧，∨，→，↔1.3 合式公式及其赋值命题常项 | 命题常元（值是确定的），命题变项 | 命题变元（真值可以变化的陈述句）。
合式公式 | 命题公式 | 命题形式 | 公式（wff）（well formed formulas），原⼦命题公式（单个命题变项），⼦公式。
* 单个命题变项是合式公式，没说命题常项。
*赋值 | 解释，成真赋值，成假赋值。
真值表。
* 真值表要点：赋值从00…0开始，按照⼆进制加法，直到11…1为⽌；按照运算的优先次序写出各⼦公式。
*命题公式的分类：重⾔式 | 永真式，⽭盾式 | 永假式，可满⾜式。
1.4 重⾔式与代⼊规则代⼊规则。
* 1. 公式中被代换的只能是命题变项（原⼦命题），⽽不能是复合命题。
2.对公式中某命题变项施以代⼊，必须对该公式中出现的所有同⼀命题变项施以相同的代换。
* 1.5 命题形式化命题形式化 | 符号化。
* 注意充分条件和必要条件的区别 ** 注意语义是否考虑完整 *1.6 波兰表达式中置式 | 中缀式，前置式 | 前缀式 | 波兰式，后置式 | 后缀式 | 逆波兰式。
Ch2 命题逻辑的等值和推理演算2.1 等值定理等值 | 等价，等值定理：设A，B为两个命题公式，A = B的充分必要条件是 A↔B为⼀个重⾔式。
离散数学知识点总结离散数学知识点总结同时要善于总结，在学习《离散数学》的过程，对概念的理解是学习的重中之重。
本文就来分享一篇离散数学知识点总结，希望对大家能有所帮助！一、认知离散数学离散数学是计算机科学基础理论的核心课程之一，是计算机及应用、通信等专业的一门重要的基础课。
它以研究量的结构和相互关系为主要目标，其研究对象一般是有限个或可数个元素，充分体现了计算机科学离散性的特点。
学习离散数学的目的是为学习计算机、通信等专业各后续课程做好必要的知识准备，进一步提高抽象思维和逻辑推理的能力，为计算机的应用提供必要的描述工具和理论基础。
1．定义和定理多离散数学是建立在大量定义、定理之上的逻辑推理学科，因此对概念的理解是学习这门课程的核心。
在学习这些概念的基础上，要特别注意概念之间的联系，而描述这些联系的实体则是大量的定理和性质。
在考试中有一部分内容是考查学生对定义和定理的识记、理解和运用，因此要真正理解离散数学中所给出的每个基本概念的真正的含义。
比如，命题的定义、五个基本联结词、公式的主析取范式和主合取范式、三个推理规则以及反证法；集合的五种运算的定义；关系的定义和关系的四个性质；函数（映射）和几种特殊函数（映射）的定义；图、完全图、简单图、子图、补图的定义；图中简单路、基本路的定义以及两个图同构的定义；树与最小生成树的定义。
掌握和理解这些概念对于学好离散数学是至关重要的。
2. 方法性强在离散数学的学习过程中，一定要注重和掌握离散数学处理问题的方法，在做题时，找到一个合适的解题思路和方法是极为重要的`。
如果知道了一道题用怎样的方法去做或证明，就能很容易地做或证出来。
反之，则事倍功半。
在离散数学中，虽然各种各样的题种类繁多，但每类题的解法均有规律可循。
所以在听课和平时的复习中，要善于总结和归纳具有规律性的内容。
在平时的讲课和复习中，老师会总结各类解题思路和方法。
作为学生，首先应该熟悉并且会用这些方法，同时，还要勤于思考，对于一道题，进可能地多探讨几种解法。
