DM期末复习14-15(Zhang)

1、离散数学期末复习 （14-15第2学期） 试卷题型 o 计算与证明 主要内容 o 数理逻辑 命题逻辑、一阶逻辑 o 集合与关系 集合基本概念及运算、二元关系、函数 o 代数 代数系统、同态与同构、群、环、域 o 图论 图的基本概念、二部图，欧拉图，哈密顿图 命题逻辑 o 命题：简单命题，复合命题 o 命题公式，命题公式的赋值，真值表 o 公式的分类：重言式，矛盾式，可满足式 常用的等值式 1.双重否定律A A 2.幂等律A AA,A AA 3.交换律AB BA， AB BA 4.结合律(AB)C A(BC) (AB)C A(BC) 5.分配律 A(BC) (AB)(AC) A(BC) (AB)

2、(AC) 6.德摩根律 (AB) AB (AB) AB 7.吸收律 A(AB) A， A(AB) A 8.零律 A1 1,A0 0 9.同一律 A0 A，A1 A 10.排中律 AA 1 11.矛盾律 AA 0 常用的等值式 12.蕴涵等值式 AB AB 13.等价等值式 AB (AB)(BA) 14.假言易位 AB BA 15.等价否定等值式 AB AB 16.归谬论 (AB)(AB) A o 等值演算： 熟记24条等值式 例：用等值演算法证明等值式 (pq)(pr) (p(qr) 解： (pq)(pr) (p q) (p r) p (q r) p(qr) o 范式：简单析取（合取）式，析取

3、（合取） 范式，主析取（合取）范式(极小项m、极 大项M)(配m， 配M，互补关系) o 如何求主析取（合取）范式？ 1. 求简单析取（合取） 2. 利用对的分配律（ 对的分配律） 例：求公式( pq)( q p)的主析取范 式和主合取范式 o 解： ( pq)( q p) (pq) ( q p) ( p q) ( q p) ( p q) ( q p) ( q p) (p q) (p q) ( p q) (p q) (p q) 320 mmm 极小项、成真赋值极小项、成真赋值 推理理论 o推理： （A1A2 Ak）B为重言式 推理正确记为：（A1A2 Ak） B o能利用推理定律（8条）及推理

4、规则（前提引入，结 论引入，置换规则）进行简单的推理 o附加前提证明法，归谬法 1. (A1 A2 Ak) (A B) 等价于(A1 A2 Ak A) B 2. (A1 A2 Ak) B 等价于（ A1 A2 Ak B ） (1) A (AB) 附加律 (2) (AB) A 化简律 (3) (AB)A B 假言推理 (4) (AB)B A 拒取式 (5) (AB)B A 析取三段论 (6) (AB) (BC) (AC) 假言三段论 (7) (AB) (BC) (A C) 等价三段论 (8) (AB)(CD)(AC) (BD) 构造性二难 例：构造推理证明 (qr) 前提引入 q r 置换 q

5、r 蕴含等值式 r 前提引入 q 拒取式（或 析取三段论） p q 前提引入 p 拒取式 一阶逻辑 o 基本概念：个体词（个体常项a,b,c，个 体变项x,y,z,），谓词F,G,H(n元谓词)， 个体域D（全总个体域），量词（全称量词 ，存在量词 ） o 在一阶逻辑中的命题符号化（注意在全总个 体域下引入特性谓词） o 一阶逻辑公式（谓词公式） o 换名规则（针对约束出现的项）目的：避免 混淆） o 解释：个体域，特定元素，特定函数，特定 谓词（在解释D下谓词公式的真值） o 谓词公式的分类：逻辑有效式（永真式）， 矛盾式（永假式），可满足式 o 一阶逻辑等值式 命题逻辑等值式的代换实例、消

6、去量词等值式 （个体域有限的情形）、 量词否定等值式、量词 辖域收缩与扩张等值式 、量词分配等值式 o 特别地，注意 （1） x(A(x)B(x) xA(x)xB(x) （2） x(A(x)B(x) xA(x)xB(x) o 证明一阶逻辑等值式 o 谓词演算推理理论（不要求） o 谓词公式的前束范式 o 例：(1)xF(x,y)yG(x,y) tF(t,y)wG(x,w) (换名规则) tw(F(t,y)G(x,w) (量词域的收缩等值式) 复习重点（一） o 命题符号化 o 判断公式类型 o 等值演算证明 o 求范式（主析取、主合取、量词前束） o 构造推理证明 集合 o 基本概念：集合，子

7、集，真子集，全集，空 集，幂集P(A) o 集合的基本运算：交，并，补（绝对补， 相对补A-B），对称差AB o 集合的运算律（23条） 和命题逻辑等值式比较，少了关于蕴含式的 5个等值式（20-24），多了差运算及全集 和空集的德摩根定律的4条运算律（17，18， 21，22） o另外还有一些重要的结果，见P.61 o集合恒等式的证明：两种方法（利用运算律，命题演算） 例：证明 A(BC)(AB)( AC) 证明证明 1： 对任意的对任意的x，有，有 xA(BC) xA x BC xA (xBxC) xA (xBxC) xA (x B x C) (xAx B) (xAx C) xAB xAC

8、 x(AB)(AC) 所以所以 A(BC)(AB)( AC) 证明证明2： A(BC) =A (B C) = A (B C) = (A B) (A C) (AB)( AC) o 集合的计数：文氏图，容斥原理 o 容斥原理：（多还少补） m mk kj ji i1 1 m m2 21 1 1 1m m k kj ji i m mj ji i1 1 j ji i m m 1 1i i i i m m2 21 1 | |A AA AA A| |1 1) )( (| |A AA AA A| | | |A AA A| | |A A| | | |A AA AA A| | | |A AA AA A| |1)

9、1)( (| |A AA AA A| | | |A AA A| | |A A| | |S S| | | |A AA AA A| | m m2 21 1 m m k kj j m mk kj ji i1 1 i i j j m mj ji i1 1 i i m m 1 1i i i i m m2 21 1 o 例：求1到1000之间(包含1和1000在内)既不能 被5和6，也不能被8整除的数有多少个？ o 解：设 Sx|xZ1x1000 A x|xSx可被5整除 B x|xSx可被6整除 C x|xSx可被8整除 |T|表示有穷集T中的元素数 x表示小于等于x的最大整数 lcm(x1,x2,xn

10、)表示x1,x2,xn的最小公倍数 |A|1000/5200，|B|1000/6166，|C|1000/8 125， |AB|1000/lcm(5,6)33，|AC|1000/lcm(5,8)25， |BC|1000/lcm(6,8)41 |ABC| 1000/lcm(5,6,8)8 由容斥原理得, 600600 8 8- -41)41)2525(33(33125)125)166166(200(200- -10001000 | |C CB BA A| | |)|)C CB B| | |C CA A| | |B BA A(|(| |)|)C C| | |B B| | |A A(|(| |S S|

11、 | |C CB BA A| | 二元关系和函数 o 有序n元组，笛卡尔积 o 笛卡尔积对和满足分配律 o 关系的定义 o 关系的表示（关系图，关系矩阵） o 关系的运算：定义域domR, 值域ranR，域 fldR, 逆，合成（复合），限制 FG | t(GF) 幂 （多次合成），像 RAB n R o 关系的性质：自反，对称（反对称），传递 o 关系性质在关系图或关系矩阵上的体现形式 o 关系运算和关系性质（ P.88 表4-2） o 关系的闭包: 自反闭包r(R)，对称闭包s(R)， 传递闭包t(R) r(R)RR0 MrM+I s(R)RR-1 MsM+M-1 t(R)RR2R3 Mt

12、M+M2 +M3 + 特殊的二元关系：等价与偏序 o 等价关系：满足自反性，对称性，传递性 o 等价类，划分 o 例：由n|x-y得到整数集Z的分类：模n剩余 类Zn；进一步地，定义Zn中加法和乘法运算 o 偏序关系：满足自反性，反对称性，传递性 o 哈斯（Hasse）图 o 最大（小）元，极大（小）元，上（下）界， 最小上界，最大下界（上下确界） 特殊的二元关系：函数 o 函数（映射）f: A B o B上A：BA =f| f: A B o 满射、单射、双射 o 函数的运算： 复合、反函数 复习重点（二） o 集合运算、包含排斥原理、等式证明 o 关系表示、关系性质、关系运算 o 等价关系与

13、分类 o 偏序集及其最大（小）元、极大（小）元、 上（下）界、上（下）确界 o 函数 代数系统 o 单位元（幺元），逆元，零元：要求对给定的运算能确 定其是否有幺元，逆元或零元 o 代数系统同态（保持运算），单同态，满同态，同构 o 不可交换：*= *= o 可结合：(*)*= *= *(*)= *= o 不是幂等的 o 设是幺元，则 S ， *= *= 则=，解 得=，即为幺元。 o 设是零元，则 S ， *= * = 则=， 无解。即无零元。 o 设 S，设是它的逆元 * = *= = 从而，a=1/x,b=-y/x o 所以当x 0时， 可逆，且 x y x yx , 1 , 1 例、设

14、G是整数加群， k为给定的整数。在 G上定义运算： x*y=x+y-k， 证明：是交换群。 群，环，域 o 群的定义，子群的定义及判定，元素的阶（周期） 的定义及计算，循环群，生成子群 o n元对称群Sn，置换的轮换分解，运算，求逆 o 环的定义，特殊的环：交换环，含幺环，无零因子 环，整环，除环（非0元可逆） o 群(Zn,+),环(Zn,+,) o 域（交换的除环） 复习重点（三） o 运算、运算律、幺元、零元、逆元 o 同态、单（满）同态、同构 o 群的定义、运算表、元素的阶、子群 o 置换的轮换分解、运算、逆 o 环的定义、可逆元、整环、域的定义 图 o 图的基本定义：有向图，无向图，图的度 （最大（小）度，最大（出，入）度 ） o 图的度序列（能否构成图及简单图），握手 定理 o 连通图，连通分支 o (无向、有向)图的