logo资料库

保研离散复习.pdf

发布时间：2022-06-13 发布人：admin 分类：说明书 资料大小：0.78M 资料格式：pdf 举报 版权申诉
第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
资料共10页，剩余部分请下载后查看
    离散数学复习 第一章：数理逻辑 一、 联结词 1. PQ:仅当 P 为 T、Q 为 F 时 PQ 为 F 2. P⇆ Q:相当于同或，P 和 Q 真假性相同时 P⇆ Q 为 T，否则为 F 3. 条件否定（与 PQ 相反）、异或（不可兼或，P 和 Q 真假性相同时为 F）、或 非（析取的否定，↑）、与非（合取的否定，↓） 4. 优先顺序：┓>合取∧>析取∨>>⇆ 5. 常见公式 蕴含等价式：PQ ⇆ ┓P∨Q 二、 蕴含式、等价式和对偶式 1. 重言式（永真式）、矛盾式（永假式）、偶然式 可满足式：包括重言式和偶然式 2. 蕴含:若 A→B 是一个重言式，就称作 A 蕴含 B，记作 A⇒B 3. 证明蕴含式 A⇒B 的两种方法： ①肯定前件，推出后件为真 ②否定后件，推出前件为假 具体而言： ①一边只有∨：设为真 By ZYL
    ②一边只有∧：设为假 4. 等价式：当且仅当 A⇒B 且 B⇒A 时，A⇔B 5. 任意命题公式都可由仅含{非，析取}或{非，合取}的命题公式来等价地表示 6. 对偶式：将仅含有联结词非、析取、合取（若不满足，需先做转换）的命题公 式 A 中的析取变合取，合取变析取，T 变 F，F 变 T 得到的命题公式 A*称为 A 的对偶式 7. 对偶式的扩展：任意/存在互换，蕴含的方向互换 三、 范式 1. 几个定义 1) 析取式：否定+析取 2) 合取式：否定+合取 3) 析取范式：（合取式）析取（合取式）……析取（合取式）。内合外析 4) 合取范式：（析取式）合取（析取式）……合取（析取式）。内析外合 2. 对于任何一个命题公式，都可以求得它的合取范式或者析取范式 1) 将公式中的联结词都归约成非、析取和合取 2) 利用德摩根定律将否定联结词直接移到各命题变元之前 3) 利用分配律、结合律将公式归约成合取范式或析取范式 3. 极小项：一个含 n 个命题变元的合取式，如果其中每个变元与其否定不同时存 在，但两者之一必须出现且仅出现一次 性质：真值指派和编码相同时为真，其余为假；任意两个不同极小项的合取式 永假，所有极小项的析取式永真 4. 主析取范式：仅由极小项析取得到，一个命题的主析取范式是唯一的 5. 极大项：一个含 n 个命题变元的析取式，如果其中每个变元与其否定不同时存 在，但两者之一必须出现且仅出现一次 性质：真值指派和编码相同时为假，其余为真；任意两个不同极大项的析取式 永真，所有极小项的和取式永假 6. 主合取范式：仅由极大项析取得到，一个命题的主合取范式是唯一的 四、 谓词逻辑 1. ┓(∀x)P(x) ⇔ (∃x) ┓P(x); ┓(∃x)P(x) ⇔ (∀x) ┓P(x) 2. 前束范式：一切量词都未被否定地处于公式的最前端且其辖域都延伸至公式的 末端的谓词演算公式。任一谓词公式均和一个前束范式等价。 By ZYL
    第二章：集合论 一、 集合 1. 集合 A 的幂集ρ(A)：由 A 的一切子集(包括空集和 A 自身)为元素形成的集合。 若|A|=n，则|ρ(A)|=2n 2. 补集： 1) B 相对于 A 的补集：A-B=A∩∼B=A-(A∩B) 2) （全集相对于）A 的补集：E-A=∼A 3) ∼补集符号相当于非符号，其满足德摩根律 3. 对称差 S=A⊕B：S 的元素或者属于 A，或者属于 B，但不能既属于 A 又属于 B 4. 容斥原理 二集合：|A1∪A2|=|A1|+|A2|-|A1∩A2|；多集合：（偶减奇加） 二、 笛卡尔积 1. N 元祖：一个序偶，第一元素是一个 n-1 序偶，第二元素是一个值 2. 序偶：特指二元组 3. 笛卡尔积（直积，AXB）：第一元素是 A 的元素，第二元素是 B 的元素 1) 不满足交换律和结合律 2) AXB⊆CXD ⇔A⊆C&&B⊆D 三、 关系 1. 二元关系：两个集合 A 和 B 的笛卡尔积 AXB 的任意子集 R，称为集合 A 到 B 上的二元关系，表示为∈R。其中所有的 a 的集合叫前域，所有的 b 的集 合叫值域，二者的合集叫域。 2. 二元关系的性质： 1) 两个关系进行交并补运算后仍是 R 上的关系 2) 自反：对任意 x，∈R 3) 对称：对任意 x,y，∈R 则∈R 4) 反自反：对任意 x，∉R 5) 反对称：对任意 x,y，∈R 则∉R 6) 可能有一种关系既是对称的又是反对称的（若 x!=y 则∉R） 3. 复合关系 定义：RoS 为 R 与 S 的复合关系。例如 R={},S={},那么 RoS={} 性质：满足结合律但不满足交换律 求解：布尔乘法：类似于矩阵乘法，但其中的布尔值加法是二进制加法 4. 逆关系 定义：记作 R-1，将 R 中的所有序偶反向。 特征：体现在关系矩阵上就是 R 与其逆关系的关系矩阵互为转置矩阵 性质：逆运算对交、并、差运算可分配 By ZYL
    （RoS）-1 = S-1 o R-1（位置互换） 四、 关系的闭包 1. R 的自反闭包 r（R）是包含 R 的最小的、自反的关系集合 1) R 是自反的当且仅当 r（R）=R 2) r（R）=R U IA（集合 A 上的相等关系，也就是矩阵的对角线元素） 2. R 的对称闭包 s（R）是包含 R 的最小的、对称的关系集合 1) R 是对称的当且仅当 s（R）=R 2) s（R）=R U R-1（R 的逆关系） 3. R 的传递闭包 t（R）是包含 R 的最小的、传递的关系集合 1) R 是传递的当且仅当 t（R）=R 2) 3) 利用沃舍尔（warshall）算法求传递闭包： t（R）= R U R2 U……U Rn（一般只需做几次复合运算，找出循环，n=|A|） 对矩阵 M 一列一列地看，其中第 k 列的 k1,k2,k3,…行为 1，则将整个矩阵 M 的第 k1,k2,k3,…行分别与第 k 行逻辑相加（1+1=1，0+1=1 这种） 4. 设 R 是集合 A 上的二元关系，则有 1) 如果 R 是自反的，那么 s（R）和 t（R）也是自反的。 2) 如果 R 是对称的，那么 r（R）和 t（R）也是对称的。 3) 如果 R 是传递的，那么 r（R）也是传递的，但 s（R）不是传递的。 5. 闭包运算的复合运算： 1) sr（R）= rs（R） 2) tr（R）=rt（R） 3) st（R）⊆ts（R） 五、 集合的划分与覆盖 1. 覆盖：把集合 A 分成若干个分开的非空子集，使得 A 中每个元素至少属于一个 分块，那这些分块的全体集合叫做 A 的一个覆盖。 2. 划分：对集合 A 的一个覆盖，A 中每个元素仅属于一个分块，这种情况叫划分。 其中划分的块数叫做划分的秩。 六、 等价关系和等价类 1. 设 R 是集合 A 上的一个二元关系，若 R 是自反、对称和传递的，则称 R 为等价 关系。 2. 验证自反性：IA⊆R 验证对称性：R-1⊆R 验证传递性：RoR⊆R 3. 等价类：集合 A 上等价关系 R 中 a 元素的等价类[a]R={x|x∈A 且∈R} 4. 商集：设 R 是集合 A 上的等价关系，由 R 确定的所有等价类组成的集合，称为 集合 A 上关于 R 的商集，记为 A/R，是集合 A 的一个划分。 5. 每一个划分确定 A 的一个等价关系。 七、 相容关系和相容类 1. 设 R 是集合 A 上的一个二元关系，若 R 是自反、对称的，则称 R 为相容关系。 2. 相容类 C：设 R 是集合 A 上的一个相容关系，C 是 A 的子集，如果对于 C 中任 By ZYL
    意两个元素 x,y,有∈R，称 C 是相容关系 R 产生的相容类。 3. 最大相容类 CR：不能真包含在任何其他相容类中的相容类。 相容关系图中，最大完全多边形的结点集合、一个孤立结点、以及不是完全多 边形的两个结点的连线都是最大相容类。完全多边形是指每个结点与其他所有 结点联接的多边形。 如下方的相容关系图的最大相容类为：{1, 2,6}，{1, 4, 5,6}，{1,7}，{3,6}，{8} 4. 完全覆盖 CR(A)：集合 A 上相容关系 R 所有最大相容类的集合。 八、 偏序关系和偏序集 1. 集合 A 有自反性、反对称性和传递性的二元关系 R，称 R 为偏序关系， 称为偏序集。 2. 盖住：偏序集中，x,y∈A，x!=y，∈R，不存在 z∈A，∈R 且 ∈R，则称 y 盖住了 x。 3. 哈斯图（偏序集合图） 1) 小圆圈代表元素，若∈R 且 x!=y，则 y 的圆圈在 x 上 2) 若 y 盖住了 x，则连接 x 和 y 的圆圈 4. 链：偏序集合 A 中的一个子集，其内每两个元素在哈斯图中均有线连接（包括 仅有一个元素的集合） 5. 全序集合：偏序集合 A 自身就是一个链，其偏序关系 R 称为全序关系。 6. 极大/小元：没有其他元素能盖住他/被他盖住，不唯一 上图极大元：6,5,4 极小元：1 7. 最大/小元：他盖住其他所有元素/被其他所有元素盖住，不存在或者唯一 上图最大元：无 最小元：1 8. 良序：任一非空子集存在最小元的偏序集 九、 函数 1. f 是 X 到 Y 的一个关系，当 f 满足对每一个 x∈X 都有唯一的 y∈Y 时，f 成为函 数 2. 满射：Y 中每个元素都是 X 中一个或多个的像点 3. 入射（单射）：X 中没有两个元素的像相同 By ZYL
    4. 双射：映射既是满射又是入射 5. 置换：非空集合 S 到 S 的一个双射 第三章：代数系统 一、 代数系统 1. 代数系统=非空集合+运算 2. 运算的性质 1) 封闭的、可交换的、可结合的、可分配的 2) 满足吸收率：对于可交换运算+和*，若 A 内任意两个元素 x 和 y 都有： x+(x*y)=x, x*(x+y)=x，则*和+满足吸收率 3) 等幂的：x*x=x，则*等幂 3. 幺元 e 1) 左幺元：对任意 x∈A，e*x=x；右幺元：对任意 x∈A，x*e=x 2) 幺元：e 既是左幺元又是右幺元 3) 若 A 上的*运算既有左幺元又有右幺元，则二者相等，为幺元 e，且幺元 e 唯一 4. 零元 0 1) 左零元：对任意 x∈A，0*x=0；左零元：对任意 x∈A，x*0=0 2) 零元：0 既是左零元又是右零元 3) 若 A 上的*运算既有左零元又有右零元，则二者相等，为零元 0，且零元 0 唯一 5. 逆元 x-1 1) 左逆元、右逆元、逆元定义类似 2) 若 A 上的*运算可结合且每个元素都有左逆元，则 x 的左右逆元相等且唯 一 二、 定义汇总 1. 广群：代数系统中 S 非空，*运算封闭 2. 半群：代数系统中 S 非空，*运算封闭，*运算可结合 性质：若 S 为有限集，则 S 内必有一元素 a，a*a=a，a 称为等幂元 3. 独异点：代数系统中 S 非空，*运算封闭，*运算可结合，存在幺元 4. 群：代数系统中 S 非空，*运算封闭，*运算可结合，存在幺元，其内每个 元素均存在其逆元 5. 有限群：代数系统中 S 非空，*运算封闭，*运算可结合，存在幺元，其内 每个元素均存在其逆元，S 为有限集，|S|为有限群的阶数 6. 阿贝尔群：代数系统中 S 非空，*运算封闭，*运算可结合，存在幺元，其 内每个元素均存在其逆元，*运算可交换 7. 循环群：代数系统中 S 非空，*运算封闭，*运算可结合，存在幺元，其内 每个元素均存在其逆元，其内任意元素均可由 a 的幂组成，a 称为生成元（生 By ZYL
    成元可以不唯一）。循环群必然是一种阿贝尔群。 8. 平凡子群：群 S 是群 G 的平凡子群，当且仅当 S=G 或 S={e} 三、 群的性质 1. 群中没有零元 2. 群中各元素的逆元唯一 3. 群的运算满足消去律 4. 群中的幺元为唯一的等幂元 四、 陪集 1. 如果 G 是一个群，H 是 G 的一个子群，g 是 G 的一个元素，那么 gH = {gh：对于所有 h∈H}表示 H 的左陪集， Hg = {hg：对于所有 h∈H}表示 H 的右陪集。 2. 拉格朗日定理：设 H 是有限群 G 的子群，则|H|整除|G|。 五、 同态与同构 1. 同态：代数系统和，f 是从 G 到 S 上的一个映射. a,b 是 G 的元，有 f(a*b)=f(a) °f(b)，则称 f 是由到的一个同态映射，并称 G 与 S 同 态，G～S。 2. 同构：代数系统和，如果 f 是从 G 到 S 的一个双射的同态，则称 f 是从 G 到 S 的同构映射，G 与 S 同构，G≌S。同构是一种等价关系。 3. 半群/独异点/群的同态映射仍是半群/独异点/群。 4. 同态核：代数系统和，f 是从 G 到 S 上的一个同态映射。若 S 的幺 元为 e，则 G 中所有经 f 映射后变成 e 的元素 g 的集合称为 f 的同态核。 六、 环与域 1. 代数系统中第一个二元运算为加法，第二个二元运算为乘法。 2. 为环需要满足： (1) 是阿贝尔群； (2) 是半群； (3) 乘法对加法满足左右分配律 3. 交换环：环中是可交换的 4. 含幺环：环中是独异点 5. 整环：环中是可交换独异点，且无零元（满足乘法消去律） 6. 域：环中是阿贝尔群，其中 0 表示零元 7. 整环不一定是域，但有限整环一定是域；域一定是整环。 By ZYL
    第四章：图论 一、 图 1. 图 G=，其中 V 是非空节点集，E 是边集。 1) 无向图：E 由若干无向边(v1,v2)组成 2) 有向图：E 由若干有向边组成 2. 零图：仅由孤立结点组成的图；平凡图：仅有一个孤立结点的图 3. 结点的度数 deg(v)=结点的入度（射入结点的边数）+结点的出度（从结点射出 的边数） 4. 多重图：含有平行边（连接同一对结点的边且方向相同）的图 5. 简单图：不含平行边或环的图 6. 完全图 Kn：每一对结点间都有边相连的含 n 个结点的简单图（有向或无向） 7. 图 G 的补图：图 G 所有结点和能使 G 成为完全图的添加边组成的图 8. 同构：图 A 和图 B 的结点和边存在一一对应的关系，则 A 与 B 同构 9. 删点必删边，删边不删点 二、 路与回路 1. 路：交替序列 v0e1v1e2…envn 称为 v0 到 vn 的路，边的数目 n 称为路的长度。 2. 回路：v0=vn 的路。 3. 迹：各边互不相同的路。 4. 通路：各点互不相同的路。 5. 通路一定是迹，但是迹不一定是通路。 6. 圈：除 v0=vn 外各点互不相同的路。 7. 连通图：仅有一个连通分支的图。 8. 点割集：对与连通的一个点集合 A，如果去掉 A 中所有的点后，原来的图变成 非连通图，而去除 A 的任一子集合图仍为连通图，那么这个点集合 A 就称为原 图一个点割集。 9. 割点：一个点割集只有一个点 10. 点连通度 K(G)：为产生一个不连通图需要删去的点的最少数目。完全图 Kn 的 点连通度是 n-1 11. 边割集、割边、边连通度同理 12. 有向图的连通种类 1) 弱连通：将图看作无向图后任一对节点间互相可达 2) 单侧连通：任一对节点间只有有一个节点能到达另一节点 3) 强连通：任一对节点间互相可达 4) 强连通⊆单侧连通⊆弱连通 5) 强/单侧/弱分图：简单有向图中具有对应性质的最大子图 三、 图的矩阵表示 1. 邻接矩阵：aij=1 表示有一条由 vi 到 vj 的边，否则为 0 2. 邻接矩阵性质：邻接矩阵的 n 次幂后的结果矩阵中元素 bij 表示连接 vi 到 vj 长 By ZYL
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料