离散数学与期末复习 .ppt

第一部分 1.命题符号化（注意区分命题逻辑和谓词逻辑） 例：p:我有时间，q:我去公园，则命题 “我去公园仅当我有时间”符号化为 例：“能者多劳，但多劳未必是能者” （个体域分别为：人类全体、全总个体域） 2. 命题公式 （1）、公式的取值、公式的类型 （永真式、永假式、可满足式） （2）、基本公式（等值式、蕴含式） （3）、范式、主范式（编码表示） 已知含命题变量 p,q,r 的公式 A 的成真赋值是： 001，010，101，则A的主析取范式是__________ 主合取范式是____________用编码表示__________ （4）、前束范式 若个体域D={ 1，2 } 求上述公式的真值 3、构造推理证明 （结论的有效性证明，命题逻辑部分） P.21. 例1. 31——1. 34 P.26.习题16 第二部分1、集合的运算（特别是广义交、广义并、幂集、对称差运算）2、关系的表示（集合、矩阵） 3、关系的性质和判定（自反、反自反、对称、反对称、传递，等价、偏序关系，否定及证明） 6、等价关系、等价类及其性质7、偏序集（ 哈斯图、极大元、极小元、最大元、最小元、上界、下界、上确界、下确界 ） 8、函数、 单射函数、满射函数A={1，2，3},R是A上的关系，1,1 、 2,3 ?R要使 R 为 A上的单射函数，则必有___ _ ?R 解: 若 R 是 A 上的关系,则 R = {3,7,4,6,5,5,6,4,7,3} 这时 R 具有对称性, 若 R 视为从 A 到 B 的关系,则 R = {0, 10,1, 9,4, 6,6, 4,8, 2 其关系矩阵是 例：证明或否定命题：若 R 是 A 上等价关 系，则 R2 也是 A 上等价关系。 第三部分 1、代数运算与代数系统 （一元、二元代数运算、运算的封闭性）； 2、特殊的代数运算 （结合律、交换律、幂等律、分配律、吸收律、消去律）； 3、代数系统的特殊元素 （单位元、零元、幂等元、某元素的逆元）； 4、特殊的代数系统——群的判定 例：从运算表检验交换律、结合律、幂等律、单位元、零元、幂等元、某元素的逆元. 解：由表的对称性可得运算满足交换律， 由表中各行各列元素互不相同，可得运算满足 消去律， 考虑结合律 显然，a 是单位元，所以是结合元, 考察b的结合性：作 L(b)、R（b)如下 L(b) b a d c a b a d c b a b c d c d c b a d c d a b 第四部分1、图的基本概念（有向图、无向图、图的表示、图的阶、零图、平凡图、完全图、简单图、图的同构、图的连通、连通分支数、子图、生成子图、诱导子图、割点、桥） 3、图的矩阵表示邻接矩阵及应用（P.137定理7.7）、 可达矩阵、图的应用（P. 140例 7.10） (2)、有向树（有向树的表示、根树、最优二叉树、最佳前缀码、哈夫曼编码） 例： 一古代国王在宫中接见他的2n个卫士（n≥2），已知某些卫士相互有仇，且每个卫士的仇人不超过n－1人，证明可以将这2n个卫士围成一圆圈，使每个卫士都不与他的仇人相邻而坐. 例： 今有a , b , c , d , e , f , g 7 个人，已知下列事实：a会讲英语； b会讲英语和汉语； c会讲英语、意大利语和俄语； d会讲日语和汉语； e会讲德语和意大利语； f会讲法语、日语和俄语； g会讲法语和德语. 问：能否将这7个人围一圆桌而坐使每个人都能和他身边的人交谈？若能请给予安排.  证明：由于 T 是完全二叉树， 所以，T 中各顶点度数只能为 1，2，3 所以，T 的总度数为 n+2+3（ ︱E ︱ － n ） = 3 ︱E ︱ － 2 n +2 另一方面，由握手定理，T 的总数度为 2︱E ︱ 所以， 3 ︱E ︱ － 2 n +2 = 2︱E ︱ 即︱E ︱ = 2 n － 2 = 2（ n － 1） 类似的 P. 171 . 练习 29 例：设T是无向树，△（T）≤5，它有40个1度点、20个2度点、31个3度点，问T有多少个4度点？有多少个5度点？ * * 火车未必都比汽车跑得快 化前束范式 解：原式 5、关系的运算 1