我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:双彩网 > 蕴含谓词 >

《离散数学》总复习汇总ppt

归档日期:06-15       文本归类:蕴含谓词      文章编辑:爱尚语录

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  adfadffd 4、设*运算是X中的可结合的二元运算,并且对任意的x, y? X, 若x*y=y*x,则x=y。证明:X中的每个元素都是等幂的。 证: 对任意的x ? X, 要证明x是等幂的,即证明:x*x=x 因为:*运算是X中的可结合的二元运算 所以:x*(x*x)=(x*x)*x 由已知:x*y=y*x ? x=y 得:x*x=x 5、设A, *是个代数系统,使得对任意的a, b, c, d ?A有: a*a=a (a*b)*(c*d) = (a*c)*(b*d) 证明:a*(b*c)=(a*b)*(a*c) 证:左式=a*(b*c) (因为a*a=a) =(a*a)*(b*c) (因为(a*b)*(c*d)=(a*c)*(b*d)) =(a*b)*(a*c)=右式 6、设X为集合,证明< ρ(X), ∩ >与< ρ(X), ∪ >是同构的。 证:对任意的S?ρ(X), 设 f(S)=~S (1)来证f是个同态映射,即证:f(S1∩S2) = f(S1)∪f(S2) ) f(S1∩S2) = ~(S1∩S2) = ~S1∪~S2 = f(S1)∪f(S2) (2)来证f是个双射函数 任取S1, S2?ρ(X), 且S1 ≠ S2, f(S1)=~S1, f(S2)=~S2 因为S1 ≠ S2,所以, ~S1 ≠ ~S2,即f(S1) ≠ f(S2)。故f是单射的;又因为f是ρ(X)到ρ(X)的自身的映射,故f是满射的。即f为双射。 7、设A, *是半群,对于A中的每一个元素a和b,若a≠b,则 a*b≠b*a( a*b=b*a ? a=b ) (1)证明对于A中的一切a,有a*a=a。 (2)对于A中任意的a和b, 证明a*b*a=a。 (3)对于A中任意的a, b和c,证明a*b*c=a*c。 证: (1) a*a=a 因为A, *是半群,*运算可结合,所以: (a*a)*a=a*(a*a) ? a*a=a (2)证明:对于A中任意的a和b, 证明a*b*a=a。 证:能推出 (a*b*a)*a = a*(a*b*a)即可。 (a*b*a)*a (*运算可结合) =a*b*(a*a) = a*b*a (由(1)知) =(a*a)*b*a (由(1)知) = a*(a*b*a) (由提示) 即: (a*b*a)*a = a*(a*b*a) 故有 a*b*a = a (3)对于A中任意的a, b和c,证明a*b*c=a*c。 证:能推出(a*b*c)*(a*c) = (a*c)*(a*b*c)即可。 (a*b*c)*(a*c) (*运算可结合) =a*b*(c*a*c) (由(2)) =a*b*c (由(2)) =(a*c*a)*b*c (*运算可结合) =(a*c)*(a*b*c) (由提示) 即: (a*b*c)*(a*c) =(a*c)*(a*b*c) 故: a*b*c=a*c 8、设G, °是一个群,b? G,定义函数f: G→G且给定成:对任意的x? G,f(x)=b°x°b-1。 证明:f是从G, °到G, °的一个同构映射。 证: (1)显然G, °与G, °同类型; (2)单射: 对任意的x, y?G, 证明:f(x)=f(y) ? x=y f(x)=f(y) ? b°x°b-1 = b°y°b-1 (消去律) ? x°b-1=y°b-1 (消去律) ? x=y (3)满射 【f: G→G ,f(x)=b°x°b-1】 对任意的y ?G,证明:在G中至少存在一个原像b-1°y°b,使得: f(b-1°y°b) =b°(b-1°y°b)°b-1 =(b°b-1)°y°(b°b-1) =e°y°e =y (4)证明f是个同态映射(即:运算的像=像的运算) 对任意的x, y? G f(x°y) =b°(x°y)°b-1 (由f的定义) = b°(x°e°y)°b-1 (群中存在幺元e) = b°(x°b-1°b°y)°b-1 = (b°x°b-1)°(b°y°b-1) (结合律) =f(x)°f(y) (由f的定义) 或: f(x°y) = b°(x°y)°b-1 f(x)°f(y)= (b°x°b-1) °(b°y°b-1 ) (因°可结合)、 = b°x°(b-1 °b)°y°b-1 = b°x°e°y°b-1 = b°(x°y)°b-1 7、证明在完全2杈树中,边的总数m=2(nt-1) 证: 设完全2杈树有m条边,则有m+1个结点 根结点的度为2,叶结点的度为1,其余结点的度为3,则: 2+nt+(m+1-1-nt)*3=2m 2+nt+3m-3nt = 2m 解得:m=2(nt-1) 3、每个自然数不是奇数就是偶数。如果自然数是偶数,当且仅当它能被2整除。并非每个自然数都能被2整除。因此,有的自然数是奇数。 【提示:P(x):x是自然数,Q(x):x是奇数,R(x):x是偶数,S (x):x能被2整出】 证: 先符号化: (?x)(P(x)→(Q(x)∨R(x))),(?x)(P(x)∧R(x)?S(x)),?(?x)(P(x)→S(x)) ? (?x)(P(x)∧Q(x)) 第二次测试题 1. 设A={1,2,3,4,6,12},R为A上的整除关系,则R为A上的偏序关系。 (1)试画出R的哈斯图 (2)并给出子集{2,3,6}的最大元和最小元、极大元和极小元、上界和下界、上确界和下确界。 2. 设T是一棵完全k元树,其中分枝结点数为i,叶结点数为t。试证明k与分枝结点数为i,叶结点数为t有如下关系式成立: (k?1)i = t?1 3. 使用推论规则证明下列各题: (1) P→(Q∨R),Q→?P,S→?R,P ? ?S(用P,T规则) (2) (?X) ( P(X)∨Q(X) ) ? ┐(??) P(X)→(?X)Q(X)。 5、 设n阶无向图G有m条边,其中,nk个结点的度为k, 其余结点的度为k+1,证明: nk=n(k+1) - 2m 证:由握手定理知: nk× k + (n-nk) × (k+1) = 2m 整理得:nk=n(k+1) - 2m 。 6、一棵树有2个点的度为2,1 个点的度为3,3个点的度为4,其余结点的度为1,问该树有多少度为1的点? 解:设有x个结点的度为1;则: 2 × 2+1 × 3+3 × 4+x × 1=2 ×(2+1+3+x-1) 19+x=10+2x 解得:x=9 * * 《离散数学》总复习 第一部分 数理逻辑。包括命题逻辑和谓词逻辑。 一、离散数学的主要内容有哪些? 离散数学的主要内容可以分为四个部分: 第二部分 集合论。包括集合、关系和函数。 第三部分 代数系统。包括代数系统的一般概念,几类典型的代数系统。 第四部分 图论。包括图的基本概念,几种特殊的图。 二、考试 1、题型 考试试题的题型有:单项选择题,10道题,占10分。填空题,共10个空,占10分。计算题,共4小题,占20分。证明题,共5题,占30分。 2、难易程度 考试题的难度不会超过教材、参考书和模拟试题的难度。以简单题占60%,较难题占30%,难题占10%。 3、考试范围 考试试题覆盖《离散数学》的全部内容。 第一部分 数理逻辑 一、内容提要 1、命题及其联结词(非、与、或、单条件、双条件)。 2、命题公式的析取范式和合取范式(主范式)。 3、命题公式间的等价关系和蕴含关系。 4、命题演算的推理理论。 5、谓词公式的有关概念(量词、谓词、变元、线、谓词公式间的等价关系和蕴含关系。 7、谓词演算的推理理论。 二、重点和难点 1、命题公式间的等价关系和蕴含关系。 2、命题演算的推理理论(包括命题符号化)。 3、谓词公式间的等价关系和蕴含关系。 4、谓词演算的推理理论(包括命题符号化) 。 三、例题 1、证明推理: (?x)(P(x) ?(Q(x)?R(x))), (?x)P(x)?(?x)(P(x)?R(x)) 证: ① (?x)P(x) P ②P(c) ES, ① ③(?x)(P(x) ?(Q(x)?R(x))) P ④P(c) ?(Q(c)?R(c)) US, ③ ⑤Q(c)?R(c) T, ②, ④, I ⑥R(c) T, ⑤, I ⑦P(c)?R(c) T, ②, ⑥, I ⑧(?x)(P(x)?R(x)) EG, ⑦ 2、证明推理: ?(P?Q)??(R?S), (Q?P)??R, R ? P?Q 证: ① R P ② (Q?P)??R P ③ (Q?P) T,①,②,I ④ R?S T,①,I ⑤ ?(P?Q)??(R?S) P ⑥ P?Q T,④,⑤,I ⑦ P?Q T,③,⑥,I 第二部分 集合论 集合论包括集合、二元关系和函数,它们之间的关系是:二元关系是一种特殊的集合,集合中的元素都是序偶;函数是一种特殊的二元关系。 一、内容提要 1、集合的两种表示方法:列举法和描述法。 2、特殊的集合:空集、全集、子集和幂集。 3、集合的运算:并、交、差和对称差,各种运算的性质。 4、集合运算的基本定律:交换律,结合律,分配律,吸收律,德.摩根律等。 5、有序n元组、n维笛卡尔积。 6、关系的定义:笛卡尔积的子集。 7、关系的表示方法:集合、矩阵和关系图。 8、关系的性质:自反性、反自反性、对称性、反对称性和传递性。 9、关系的运算:复合运算、逆运算和闭包运算。 10、特殊的二元关系及其相关特性:等价关系(自反性、对称性、传递性)、偏序关系(自反性、反对称性、传递性)、等价类、偏序关系中的特殊元素(极大元、上界等)。 11、函数的定义、函数的定义域和值域。 12、函数的性质:单射、满射和双射。 13、函数的运算:复合函数、逆函数。 14、集合的基数。 二、重点和难点 1、掌握元素与集合之间的关系,集合与集合之间的关系。 2、运用集合运算的基本定律去化简集合表达式或证明集合等式。 3、掌握二元关系的五个性质和二元关系的运算。 4、等价关系的证明、等价类的求解,偏序关系的特定元素的求解。 5、函数的性质,求复合函数和逆函数。 三、例题 1、?????? ?????这两个关系是否正确? 答:正确。在?????中?表示元素;在?????中?表示空集。 2、求R={1,2, 2,3, 3,4}的传递闭包。 解:R的传递闭包={1,2, 2,3, 3,4, 1,3, 2,4,1,4}。 注意:求传递闭包是一个不断重复合并有序对的过程。有序对1,4往往被漏掉。 3、化简集合表达式:((A∩B)∪A)⊕((B∩~B)⊕A⊕(B∪~B)) 解: ((A∩B)∪A)⊕((B∩~B)⊕A⊕(B∪~B)) (吸收律和零律) =A⊕?⊕A⊕U (同一律) = A⊕A⊕U (零律) = ?⊕U = U 4、设集合A={a, b, c, d, e},偏序关系R的哈斯图如图所示,若A的子集B={c, d, e},求:(1)用列举法写出偏序关系R的集合表达式;(2)写出集合B的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界。 解:(1)R=IA?{d,b, d,c, d,a, b,a, c,a, e,c, e,a} (2)集合B的极大元:c,极小元:d、e,最大元:c,最小元:无,上界:c、a,上确界:c,下界:无,下确界:无。 5、已知f:R?R且f(x)=(x+4)3- 2,已知g:R?R且g(x)=3x+5, 求: f与g的合成函数,并求3在f与g的合成函数下的函数值。 解: (1) f°g: R?R,且 (f°g)(x)=g(f(x))=g((x+4)3 - 2)=3((x+4)3 - 2)+5=3(x+4)3-1 (f ° g)(3)=3*(3+4)3-1=1028 第三部分 代数系统 一、内容提要 1、代数系统的定义(封闭性)、特殊元素(幺元,零元、逆元、幂等元)。 2、代数系统之间的关系:子代数,同态(单同态、满同态、同构)。 3、同余关系的定义和商代数。 4、半群、独异点和群的定义及其相互间的关系。 5、群的基本性质:消去律、元素的阶。 6、循环群的性质及生成元。 7、子群的定义及判定方法、正规子群的定义及判定方法、子群的陪集。(拉格朗日定理) 8、环和域的定义。 9、子环的定义及其判定方法。 10、格的定义及其性质。 11、特殊的格:分配格、有界格、有补格、有补分配格。 12、布尔代数及其性质。 二、重点和难点 1、代数系统的定义及特异元素,如何证明两个代数系统同态与同构。 2、循环群的定义及其性质。 3、子群的定义及其判定方法。 4、格的定义及其性质。 三、例题 1、设R是实数集,在R上定义二元运算*,?x, y?R,定义x*y=x+y+2xy。试说明*是否满足结合律、交换律?是否存在幺元?若存在请求出幺元 。 解: ?x,y,z?R, ①(x*y)*z=(x+y+2xy)*z=(x+y+2xy)+z+2(x+y+2xy)z =x+(y+z+2yz)+ 2x(y+z+2yz)= x*(y+z+2yz)=x*(y*z) *运算可结合。 ② x*y=x+y+2xy=y*x *运算可交换。 ③ 设幺元为e,?x?R, e*x=x*e=x+e+2xe=x,由x的任意性,得e=0?R,幺元为0。 2. 给定代数系统U=X,°,V=Y,*,W=Z, ? ,设f: X→Y是从U到V的同态,g: Y→Z是从V到W的同态,则g°f: X→Z必是从U到W的同态。 证:对任意的a, b? X,证明: g°f(a°b)=g°f(a)?g°f(b) g°f(a°b)= g(f(a°b)) = g(f(a)*f(b)) (f是同态映射) = g(f(a))?g(f(b)) (g是同态映射) = g°f(a)?g°f(b) 3、设G, *是群,a, b∈G,且(a*b)2=a2*b2,证明a*b=b*a。 证:因为群满足消去律,所以 (a*b)2=a2*b2 ?(a*b)*(a*b)=(a*a)*(b*b) (因*可结合) ?a*(b*a)*b= a*(a*b)*b (群满足左右消去律) ? b*a=a*b 第四部分 图论 一、内容提要 1、图的基本概念:无向图、有向图、简单图、结点的度数、子图、补图、图的同构。 2、握手定理:所有结点的度数之和等于边数的2倍。 3、图的连通性:割边、割点、边割集、点割集。通路、回路、连通分支。 4、图的矩阵表示:邻接矩阵、关联矩阵。 5、欧拉图和哈密尔顿图的定义和判定条件。 6、树的定义、性质、判定条件和遍历。 7、二部图和平面图的定义、性质和判定条件 二、重点和难点 1、掌握图的基本概念。 2、运用握手定理解题。 3、利用图的矩阵求两个结点间的通路条数。 4、欧拉图和哈密尔顿图的判定。 5、树的遍历方法。 三、例题 1、设T是完全2杈树,有t片树叶,i个分支点,证明: i = t-1 (即:在完全2杈中,分支结点数比树叶数少1) 证:由握手定理知: 2+t+(i+t-1-t) × 3=2m =2(t+i-1) 即:t+3i-1 = 2t + 2i -2 解得: i = t-1 2、设T是完全2杈树,有t片树叶,i个分支点,证明T的边数m=2t-2 。 证:设T有m条边,根据握手定理可得: 2+t+(i+t-1-t) × 3=2m 即:3i + t - 1=2m, i=t-1 3(t-1)+t-1=2m ? 4t+4=2m 解得:m=2t - 2。故结论成立。 3、在n阶简单有向图中,完全有向图的边数为n(n-1)。 证:完全有向图中任意两个结点间都有方向相反的两条边,所以: m=2Cn2=2*n(n-1)/2=n(n-1) 4、对于(n, n+1)的图G,则G中至少有一个点的度大于等于3。 证:现假设图G中所有结点的度均小于3, 即≤ 2,由握手定理知: =2(n+1) 矛盾 ≤ 2n 又因为 则: 即得: 2(n+1) ≤ 2n

本文链接:http://jamescaronna.com/yunhanweici/102.html