我要投搞

标签云

收藏小站

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

当前位置:小鱼儿玄机1站开奘结果 > 前束范式 >

计算机数学基础离散数学部分DOC

归档日期:07-21       文本归类:前束范式      文章编辑:爱尚语录

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

  离散数学复习提纲 一、基本内容 数理逻辑部分 1.理解命题概念,会判别语句是不是命题.理解五个联结词:否定、析取、合取、条件、和双条件及其真值表,会将简单命题符号化. 具有确定真假意义的陈述句称为命题. 命题必须具备:其一,语句是陈述句;其二,语句有唯一确定的线.了解公式的概念(公式、赋值、成真指派和成假指派)和公式真值表的构造方法.能熟练地作公式真值表.理解永真式和永假式概念,掌握其判别方法. 判定命题公式类型的方法:其一是真值表法,其二是等价演算法. 3.了解公式等价概念,掌握公式的重要等价式和判断两个公式是否等价的有效方法:等价演算法、列真值表法和主范式方法. 4.理解析取范式和合取范式、极大项和极小项、主析取范式和主合取范式的概念,熟练掌握它们的求法. 命题公式的范式不惟一,但主范式是惟一的. 命题公式A有n个命题变元,A的主析取范式有k个极小项,有m个极大项,则 求命题公式A的析取(合取)范式的步骤. 求命题公式A的主析取(合取)范式的步骤. 5.要理解并掌握推理理论的规则、重言蕴含式和等价式,掌握命题公式的证明方法:真值表法、直接证法、间接证法. 重点:命题与联结词,公式与解释,真值表,公式的类型及判定,主析取(合取)范式,命题演算的推理理论. 6.理解谓词、量词、个体词、个体域,会将简单命题符号化. 原子命题分成个体词和谓词,个体词可以是具体事物或抽象的概念,分个体常项和个体变项.谓词用来刻划个体词的性质或之间的关系. 量词分全称量词,存在量词. 命题符号化注意:使用全称量词,特性谓词后用;使用存在量词,特性谓词后用. 7.了解原子公式、谓词公式、变元(约束变元和自由变元)与辖域等概念.掌握在有限个体域下消去公式的量词和求公式在给定解释下真值的方法. 由原子公式、联结词和量词构成谓词公式.谓词公式具有真值时,才是命题. 在谓词公式中,会区分约束变元和自由变元. 在非空集合D(个体域)上谓词公式A的一个解释或赋值有3个条件. 在任何解释下,谓词公式A取线,A为逻辑有效式(永线,A为永假式;至少有一个解释使公式A取线,A称为可满足式. 在有限个体域下,消除量词的规则为:设D={},则 会求谓词公式的真值,量词的辖域,自由变元、约束变元,以及换名规则、代入规则等. 掌握谓词演算的等价式和重言蕴含式.并进行谓词公式的等价演算. 8.了解前束范式的概念,会求公式的前束范式的方法. 若一个谓词公式F等价地转化成 ,那么就是F的前束范式.前束范式仍然是谓词公式. 9.了解谓词逻辑推理的四个规则.会给出推理证明. 谓词演算的推理是命题演算推理的推广和扩充,命题演算中基本等价式,重言蕴含式以及P,T,CP规则在谓词演算中仍然使用.谓词逻辑的推理演算引入了US规则(全称量词指定规则),UG规则(全称量词推广规则),ES规则(存在量词指定规则),EG规则(存在量词推广规则)等. 集合论部分 1.理解集合、元素、集合的包含、子集、相等,以及全集、空集和幂集等概念,熟练掌握集合的表示方法. 具有确定的,可以区分的若干事物的全体称为集合,其中的事物叫元素. 集合的表示方法:列举法和描述法. 注意:集合的表示中元素不能重复出现,集合中的元素无顺序之分. 掌握集合包含(子集)、真子集、集合相等等概念. 注意:元素与集合,集合与子集,子集与幂集,空集与所有集合的关系:空集是惟一的,它是任何集合的子集. 集合A的幂集P(A)=, A的所有子集构成的集合.若A=n,则P(A)=2n. 2.熟练掌握集合A和B的并、交,补集(A补集总相对于一个全集).差集A-B,对称差等运算,并会用文氏图表示. 掌握集合运算律(运算的性质). 3.掌握用集合运算基本规律证明集合恒等式的方法. 集合的运算问题:其一是进行集合运算;其二是运算式的化简;其三是恒等式证明. 证明方法有二:(1)要证明A=B,只需证明A是B的子集,又B是A的子集; (2)通过运算律进行等式推导. 4.了解有序对和笛卡儿积的概念,掌握笛卡儿积的运算. 有序对就是有顺序二元组,如x, y,x, y 的位置是确定的,不能随意放置. 注意:有序对a,b(b, a,以a, b为元素的集合{a, b}={b, a};有序对(a, a)有意义,而集合{a, a}是单元素集合,应记作{a}. 集合A,B的笛卡儿积A×B是一个集合,规定A×B={x,y(x(A,y(B},是有序对的集合.笛卡儿积也可以多个集合合成,A1×A2×…×An. 5.理解关系的概念:二元关系、空关系、全关系、恒等关系.掌握关系的集合表示、关系矩阵和关系图,掌握关系的集合运算和求复合关系、逆关系的方法. 二元关系是一个有序对集合,,记作xRy. 关系的表示方法有三种:集合表示法, 关系矩阵:R(A×B,R的矩阵. 关系图:R是集合上的二元关系,若ai, bj(R,由结点ai画有向弧到bj构成的图形. 空关系(是唯一、是任何关系的子集的关系; 全关系; 恒等关系,恒等关系的矩阵MI是单位矩阵. 关系的集合运算有并、交、补、差和对称差. 复合关系; 复合关系矩阵:(按布尔运算); 有结合律:(R(S)(T=R((S(T),一般不可交换. 逆关系; 逆关系矩阵满足:; 6.理解关系的性质(自反性和反自反性、对称性和反对称性、传递性的定义以及矩阵表示或关系图表示),掌握其判别方法(利用定义、矩阵或图,充分条件),知道关系闭包的定义和求法. 注:(1)关系性质的充分必要条件: ① R是自反的; ②R是反自反的; ③R是对称的 ; ④R是反对称的; ⑤R是传递的. (2)IA具有自反性,对称性、反对称性和传递性.EA具有自反性,对称性和传递性.故IA,EA是等价关系.(具有反自反性、对称性、反对称性和传递性.IA也是偏序关系. 7.理解等价关系和偏序关系概念,掌握等价类的求法和作偏序集哈斯图的方法.知道极大(小)元,最大(小)元的概念,会求极大(小)元、最大(小)元、最小上界和最大下界. 等价关系和偏序关系是具有不同性质的两个关系. 知道等价关系图的特点和等价类定义,会求等价类. 一个子集的极大(小)元可以有多个,而最大(小)元若有,则惟一.且极元、最元只在该子集内;而上界与下界可以在子集之外.由哈斯图便于确定任一子集的最大(小)元,极大(小)元. 8.理解函数概念:函数(映射),函数相等,复合函数和反函数.理解单射、满射和双射等概念,掌握其判别方法. 函数是一种特殊的关系.集合A×B的任何子集都是关系,但不一定是函数.函数要求对于定义域A中每一个元素a,B中有且仅有一个元素与a对应,而关系没有这个限制. 二函数相等是指:定义域相同,对应关系相同,而且定义域内的每个元素的对应值都相同. 函数有:单射——若; 满射——f(A)=B或使得y=f(x); 双射——单射且满射. 复合函数 即. 复合成立的条件是:.一般,但. 反函数——若f:A(B是双射,则有反函数f-1:B(A, , 重点:关系概念与其性质,等价关系和偏序关系,函数. 图论部分 1.理解图的概念:结点、边、有向图,无向图、简单图、完全图、结点的度数、边的重数和平行边等.理解握手定理. 图是一个有序对V,E,V是结点集,E是联结结点的边的集合. 掌握无向边与无向图,有向边与有向图,混合图,零图,平凡图、自回路(环),无向平行边,有向平行边等概念. 简单图,不含平行边和环(自回路)的图、 在无向图中,与结点v((V)关联的边数为结点度数(v);在有向图中,以v((V)为终点的边的条数为入度-(v),以v((V)为起点的边的条数为出度+(v),deg(v)=deg+(v) +deg-(v). 无向完全图Kn以其边数;有向完全图以其边数. 了解子图、真子图、补图和生成子图的概念. 生成子图——设图G=V, E,若E((E,则图V, E(是V, E的生成子图. 知道图的同构概念,更应知道图同构的必要条件,用其判断图不同构. 重要定理: (1) 握手定理 设G=V,E,有; (2) 在有向图D=V, E中,; (3) 奇数度结点的个数为偶数个. 2.了解通路与回路概念:通路(简单通路、基本通路和复杂通路),回路(简单回路、基本回路和复杂回路).会求通路和回路的长度.基本通路(回路)必是简单通路(回路). 了解无向图的连通性,会求无向图的连通分支.了解点割集、边割集、割点、割边等概念.了解有向图的强连通强性;会判别其类型. 设图G=V,E,结点与边的交替序列为通路.通路中边的数目就是通路的长度.起点和终点重合的通路为回路.边不重复的通路(回路)是简单通路(回路);结点不重复的通路(回路)是基本通路(回路). 无向图G中,结点u, v存在通路,u, v是连通的,G中任意结点u, v连通,G是连通图.P(G)表示图G连通分支的个数. 在无向图中,结点集V((V,使得P(G-V()P(G),而任意V((V(,有P(G-V()=P(G),V(为点割集. 若V(是单元集,该结点v叫割点;边集E((E,使得P(G-V()P(G),而任意E((E(,有P(G-E()=P(G),E(为边割集.若E(是单元集,该边e叫割边(桥). 要知道:强连通单侧连通弱连通,反之不成立. 3.了解邻接矩阵和可达矩阵的概念,掌握其构造方法及其应用. 重点:图的概念,握手定理,通路、回路以及图的矩阵表示. 4.理解欧拉通路(回路)、欧拉图的概念,掌握欧拉图的判别方法. 通过连通图G的每条边一次且仅一次的通路(回路)是欧拉通路(回路).存在欧拉回路的图是欧拉图. 欧拉回路要求边不能重复,结点可以重复.笔不离开纸,不重复地走完所有的边,走过所有结点,就是所谓的一笔画. 欧拉图或通路的判定定理 (1) 无向连通图G是欧拉图(G不含奇数度结点(即G的所有结点为偶数度); (2) 非平凡连通图G含有欧拉通路(G最多有两个奇数度的结点; (3) 连通有向图D含有有向欧拉回路(D中每个结点的入度=出度. 连通有向图D含有有向欧拉通路(D中除两个结点外,其余每个结点的入度=出度,且此两点满足deg-(u)-deg+(v)=(1. 5.理解汉密尔顿通路(回路)、汉密尔顿图的概念,会做简单判断. 通过连通图G的每个结点一次,且仅一次的通路(回路),是汉密尔顿通路(回路).存在汉密尔顿回路的图是汉密尔顿图. 汉密尔顿图的充分条件和必要条件 (1) 在无向简单图G=V,E中,(V((3,任意不同结点,则G是汉密尔顿图.(充分条件) (2) 有向完全图D=V,E, 若,则图D是汉密尔顿图. (充分条件) (3) 设无向图G=V,E,任意V1(V,则W(G-V1)((V1((必要条件) 若此条件不满足,即存在V1(V,使得P(G-V!)(V1(,则G一定不是汉密尔顿图(非汉密尔顿图的充分条件). 6.了解平面图概念,平面图、面、边界、面的次数和非平面图.掌握欧拉公式的应用. 平面图是指一个图能画在平面上,除结点之外,再没有边与边相交. 面、边界和面的次数等概念. 重要结论:(1)平面图. (2)欧拉公式:平面图 面数为r,则(结点数与面数之和=边数+2) (3)平面图. 会用定义判定一个图是不是平面图. 7.理解平面图与对偶图的关系、对偶图在图着色中的作用,掌握求对偶图的方法. 给定平面图G=〈V,E〉,它有面F1,F2,…,Fn,若有图G*=〈V*,E*〉满足下述条件: ⑴对于图G的任一个面Fi,内部有且仅有一个结点vi*∈V*; ⑵对于图G的面Fi,Fj的公共边ek,存在且仅存在一条边ek*∈E*,使ek*=(vi*,vj*),且ek*和ek相交; ⑶当且仅当ek只是一个面Fi的边界时,vi*存在一个环ek*和ek相交; 则图G*是图G的对偶图. 若G*是G的对偶图,则G也是G*的对偶图.一个连通平面图的对偶图也必是平面图. 8.掌握图论中常用的证明方法. 重点:欧拉图和哈密顿图、平面图的基本概念及判别. 9.了解树、树叶、分支点、平凡树、生成树和最小生成树等概念,掌握求最小生成树的方法. 连通无回路的无向图是树.树的判别可以用图T是树的充要条件(等价定义). 注意:(1) 树T是连通图; (2)树T满足m=n-1(即边数=顶点数-1). 图G的生成子图是树,该树就是生成树. 每边指定一正数,称为权,每边带权的图称为带权图.G的生成树T的所有边的权之和是生成树T的权,记作W(T).最小生成树是带权最小的生成树. 10.了解有向树、根树、有序树、二叉树、二叉完全树、正则二叉树和最优二叉树等概念.了解带权二叉树、最优二叉树的概念,掌握用哈夫曼算法求最优二叉树的方法. 有向图删去边的方向为树,该图为有向树. 对非平凡有向树,恰有一个结点的入度为0(该结点为树根),其余结点的入度为1,该树为根树.每个结点的出度小于或等于2的根树为二叉树;每个结点的出度等于0或2的根树为二叉完全树;每个结点的出度等于2的根树称为正则二叉树. 有关树的求法: (1)生成树的破圈法和避圈法求法; (2)最小生成树的克鲁斯克尔求法; (3) 最优二叉树的哈夫曼求法 重点:树与根树的基本概念,最小生成树与最优二叉树的求法. 代数结构部分 1. 二元运算(定义,封闭性)、运算表 2.各种定律(交换、结合、幂等、分配、吸收、消去、幺元、零元、逆元) 3·代数系统、子代数、积代数(定义、特殊元素、代数常数) 4·同态与同构(同态等式、证明) 5·半群、独异点 6·群、子群、阿贝尔群、生成子群、元素的阶(周期)、循环群(定义与证明) ·环、含幺环、零因子、无零因子环、整环、除环与域 7·格(两种定义)、分配格、有界格、布尔格(判断) 练习题 数理逻辑部分 (一) 1.填空题 (1) 公式(p((q)(((p(q)的成真赋值为__________________; (2) 设p, r为真命题,q, s为假命题,则复合命题(p(q)(((r(s)的真值为________; (3) 设p, q均为命题,在_________________________条件下,p与q的排斥或也可以写成p与q的相容或; (4) 公式((p(q)与(p((q)(((p(q)共同的成真赋值为____________; (5) 设A为任意的公式,B为重言式,则A(B的类型为______________. 2.将下列命题或语句符号化 (1) 不是无理数是不对的; (2) 小刘既不怕吃苦,又很钻研; (3) 只有不怕困难,才能战胜困难; (4) 只要别人有困难,老王就帮助别人,除非困难解决了; (5) 整数n是偶数当且仅当n能被2整除. 3.求复合命题的线,q:旧金山是美国的首都,r:一年分四季. (1) ((p(q)(r)((r((p(q)); (2) (((q(p)((r(p))((((p((q)(r). 4.判断推理是否正确 设y=2x,x为实数. 推理如下: 若y在x=0可导,则y在x=0连续. y在x=0连续. 所以,y在x=0可导. 5.判断公式的类型 (1) (((p(q)(((p((q)(((p(q)))(r; (2) (p(((q(p))((r(q); (3) (p((r)((q(r). (二) 1.填空题. (1) 设A为含命题变项p、q、r的重言式,则公式A( (((q)→r)的类型为___________; (2) 设B为含命题变项p、q、r的矛盾式,则公式(((p(q)→r)的类型为___________; (3) 设p、为命题变项,则(((q)的成线) 设p、为真命题,r、s为假命题,则复合命题(r)(((q→s)的真值为___________; (5) 矛盾式的主析取范式为____________; (6) 设公式A含命题变项p、q、r,又已知A的主合取范式为,则A的主析取范式为. 2.用等值演算法求公式的主析取范式或主合取范式 (1) 求公式p→(r)((p(((q((r)))的主析取范式; (2) 求公式 (((p→q))(((q→(p)的主合取范式; (3) 求公式(q)((p→q))((q→p)的主析取范式,再由主析取范式求出主合取范式. 3.用真值表求公式(p→)(r的主析取范式 4.将公式p→(q→r)化成与之等值且仅含(, (}中联结词的公式. 5.用主析取范式判断(与(q)((((p(q))是否等值. 1.填空题 (1) 为拒取式推理定律; (2) 为析取三段论推理定律; (3) 为假言三段论推理定律; (4) 为假言推理定律. 2.判断推理是否正确,并证明之方法不限 (1) 如果王红学过英语和法语,则她也学过日语.可她没有过日语,但学过法语所以,她也没学过英语; (2) 若小李是文科学生,则他爱看电影.小李不是文科学生所以他不爱看电影. 设y=2x,x为实数. 推理如下: 若y在x=0可导,则y在x=0连续. y在x=0连续. 所以,y在x=0可导.3.在自然推理系统中,用直接证明法构造下面推理的证明 (1) 前提:→(r, r 结论: (2) 前提:→r, q→s, p,q 结论:4.在自然推理系统中,用附加前提证明法证明下面推理. (1) 前提:→p, q 结论:→(s (2) 前提:→q, (p(r, q→s 结论:→r 5.在自然推理系统中,用归谬法证明下面推理. 前提:→(q→r), p(q 结论:6.在自然推理系统中,构造下面用自然语言给出的推理. 若小张喜欢数学,则小李或小赵也喜欢数学.若小李喜欢数学,他也喜欢物理.小张确实喜欢数学,可小李不喜欢物理所以小赵喜欢数学.填空题 (1) 设F(x):x具有性质F,G(x):x具有性质G. 命题对所有的x而言,若x有性质F,则x就有性质G的符号化形式为__________________________; (2) 设F(x):x具有性质F,G(x):x具有性质G. 命题有的x有性质F有性质G的符号化形式为__________________________; (3) 设F(x):x具有性质F,G(y):y具有性质G. 命题若所有的x都有性质F,则所有的y都有性质G的符号化形式为__________________________; (4) 设F(x):x具有性质F,G(y):y具有性质G. 命题若存在x具有性质F,则所有的y都没有性质G的符号化性质为__________________________; (5) 设A为任意的一阶逻辑公式,若A中_________________,则称A为封闭的公式; (6) 在一阶逻辑中将命题符号化时,若没指明个体域,则使用________________个体域. 2. 用0元谓词将下列命题符号化 (1) 只要4不是素数,3就是素数; (2) 只有2是偶数,4才是偶数; (3) 5是奇数当且仅当5不能被2整除. 3. 在一阶逻辑中将下列命题符号化 (1) 所有的整数,不是负整数,就是正整数,或者是0; (2) 有的实数是有理数,有的实数是无理数; (3) 发明家都是聪明的并且是勤劳的.王前进是发明家所以王前进是聪明的并且是勤劳的. 4.在一阶逻辑中,将下列命题符号化 (1) 实数不都是有理数; (2) 不存在能表示成分数的无理数. 5.在一阶逻辑中,将下列命题符号化 (1) 若x与y都是实数且xy,则x+2y+2; (2) 不存在最大的自然数. 6.证明题 (1) 证明为可满足式但不是永线) 证明为永线) (y)的前束范式为; (2) 由量词,)(B(x))(________________; (3)(x(F(x)(B)( ________________;(4) 公式(y(G(x)((xF(x))((yG(y))((xF(x)的类型为 (5) 取解释I为:个体域为具有性质F,在I下((xF(x)的线) 前提:(x(yF(x,y) 结论:以上推理是错误的,某学生却给出了如下证明: ① (x(yF(x,y) 前提引入 ② (yF(y,y) ①(( 此证明错. 2.在有限个体域内消去量词. (1) 个体域,公式为 ((y(F(x)(G(y)) (2) 个体域,公式为(x(y(F(x,y)(G(y,x)) 3.求前束范式.(1) (x(F(x,y)((y(G(x,y)((zH(x,y,z))); (2) ((xF(x,y)((yG(x,y,z))((zH(z). 4.在自然推理系统L 中,构造下面推理的证明. (1) 前提:( 结论:( (2) 前提:结论:5.在自然推理系统F中,构造用自然语言描述的推理. 火车都比汽车快,汽车都比轮船快,a是火车,b是汽车,c是轮船.所以,a比b快,b比c快.1. 填空题 (1) 设A={2,a,{3},4}, B={(, 4,{a},3},则A(B=______________________________; (2) 设A={{{1,2}},{1}},则P(A)=__________________________________________; (3) 设X,Y,Z为任意集合,且X(Y={1,2,3}, X(Z={2,3,4},若2(Y, 则一定有_______; A. 1(Z B. 2(Z C. 3(Z D. 4(Z (4) 下列命题中为真的是________________________________________________; A. {a,{b}}({{a,{b}}} B. ((P(({(,{(}}) C. {a}(X(a(X D. X(Y=Y(X=( E. X(Y=X(X((Y (5) 设[0,1]和(0,1)分别表示实数集上的闭区间和开区间,则下列命题中为真的是 _____________________________________; A. {0,1}( (0,1) B. {0,1}( [0,1] C. (0,1)([0,1] D. [0,1](Q E. {0,1}(Z (6) 设[a,b], (c,d)代表实数区间,那么([0,4]([2,6])((1,3)=_________________________. 2. 简答题 (1) 设E={1,2,...,12},A={1,3,5,7,9,11}, B={2,3,5,7,11},C={2,3,6,12}, D={2,4,8},计算:A(B, A(C, C((A(B), A(B, C(D, B(D. (2) 设A={{a},{a,b}}, 求(A, (A, ((A(((A. (3) 设A, B, C为集合,判断下列集合等式是否为恒等式,并说明理由. (A(B(C)((A(B) = C, A((B(C) = (A(B) ( (A(C) (4) 找出下列集合等式成立的充分必要条件, 并简单说明理由. (A(B)((A(C)=( 3. 证明题 (1) A(B ( C(B(C(A; (2) A(B=E ( (A(B ( (B(A. 4. 应用题 一个学校有507, 292, 312和344个学生分别选了微积分、离散数学、数据结构或程序设计语言课,且有14人选了微积分和数据结构课,213人选了微积分和程序设计语言课,211人选了离散数学和数据结构课,43人选了离散数学和程序设计语言课,没有学生同时选微积分和离散数学课,也没有学生同时选数据结构和程序设计语言课。问有多少学生在微积分、离散数学、数据结构或程序设计语言中选了课? 已知a、b、c、d、e、f、g 中,会讲的语言分别为 a:英语、德语 b:英语、汉语 c:英语、意大利语、俄语 d:汉语、日语 e:意大利语、德语 f:俄语、日语、法语 g:德语、法语 问能否将他们的座位安排在圆桌旁,使得每个人都能与他身边的人交谈?1. 填空题 (1) 设A={1,2,3},A上的关系R={x,y x=y+1或x=y(1},R的补关系也是A上的关系,其中={x,y x,y(R},则=_________________________________________; (2) A={1,2,3}, B={4,5,6,8},R与S是从A到B的关系,且xRy当且仅当gcd(x,y)=1, 即x与y的最大公约数等于1,xSy当且仅当x+y8,则R(S=___________________________; (3) 下列各关系中具有自反性和对称性的关系是______________________________; R1是自然数集合N上的关系,且xR1y当且仅当x+y是偶数 R2是自然数集合N上的关系,且xR2y当且仅当xy或yx. R3是自然数集合N上的关系,且xR3y当且仅当 x+y(3. R4是有理数集合Q上的关系,且xR4y当且仅当y=x+2. R5是自然数集合N上的关系,且xR5y当且仅当x(y=4. (4) 已知R(A(A且A={a,b,c},R的关系矩阵 M(R)= 则传递闭包t(R)的关系矩阵M(t(R))=______________________________________.; (5) 设集合X={1,2,3},下列关系中__________________________不是等价的; A={1,1, 2,2, 3,3} B={1,1,2,2,3,3,3,2,2,3} C={1,1,2,2,3,3,1,4} D={1,1,2,2,1,2,2,1,1,3,3,1,3,3,2,3,3,2} (6) 设A={a,b,c,d,e,f},R是A上的二元关系,其关系定义如下: R={a,b,b,c,c,a,e,f,f,e}, 使得Rs=Rt成立的最小的自然数s,t(st)是_________________________. 2. 简答题 (1) 给出集合A={a,b,c}上的一个关系R,使得R不具有以下五种性质(自反、反自反、对称、反对称、传递)中的任何一种,解释为什么所给的关系没有这些性质,并画出R的关系图. (2) 设A={a,b,c,d,e,f}, R是A上的二元关系,且R={a,c, c,d, d,a}.设R*=tsr(R), 则R*是A上的等价关系. 写出R*的关系表达式和商集A/R*. 3. 证明题 (1) 指出下面命题证明中的错误: 命题:设R是集合A上的对称、传递的关系,则R是自反的. 证:设x(A,根据对称性由x,y(R得到y,x(R,再使用传递性得到x,x(R. 从而证明了R的自反性. (2) 设R是A上任意自反和传递的关系,证明R°R=R. 该命题的逆命题是否成立,证明你的结论. 4. 应用题 在一个道路网络上连接有8个城市,分别标记为a,b,c,d,e,f,g,h. 城市之间的直接连接的道路是单向的,有a(b, a(c, b(g, g(b, c(f, f(e, b(d, d(f. 对每一个城市求出从它出发能够到达的所有其他城市.1. 填空题 (1) 设X={a,b,c},Y={1,2,3},f={a,1,b,2,c,3},则下面命题中惟一正确的是_________; A. f是从X到Y的二元关系,但不是从X到Y的函数; B. f是从X到Y的函数, 但不是满射,也不是单射; C. f是从X到Y的满射, 但不是单射; D. f是从X到Y的双射. (2) 设f:Z(Z(Z, Z为整数集,(n,k(Z(Z,f(n,k)=n2k,则ranf=_______________; (3) 设A={a,b,c},R={a,b,b,a}(IA是A上的等价关系,设自然映射g:A(A/R,那么g(a)=____________________; (4) 设f:R(R, f(x)=x2(3x+2, 其中R为实数集,则 f({1,3})(f(1({(6})=____________; (5) 设R为实数集合,f:R(R, f(x)=x2(x+2,g:R(R, g(x)=x(3, 则f(g(x)=__________;(6) 设f:A(A, 如果f是双射的,则f°f(1=__________________. () 公式((p(q)与(p((q)(((p(q)共同的成真赋值为____________; (设p、为真命题,r、s为假命题,则复合命题(r)(((q→s)的真值为___________; () ((A(B)((B((C)(_________________为假言三段论推理定律; () 设A为任意的一阶逻辑公式,若A中_________________,则称A为封闭的公式; () 前提:(结论:以上推理是错误的,某学生却给出了如下证明: ① (x(yF(x,y) 前提引入 ② (yF(y,y) ①(( 此证明错. () 设[a,b], (c,d)代表实数区间,那么([0,4]([2,6])((1,3)=_________________________. ( 设集合X={1,2,3},下列关系中__________________________不是等价的; A={1,1, 2,2, 3,3} B={1,1,2,2,3,3,3,2,2,3} C={1,1,2,2,3,3,1,4} D={1,1,2,2,1,2,2,1,1,3,3,1,3,3,2,3,3,2}(14) 设f:A(A, 如果f是双射的,则f°f(1=__________________. 2. 简答题 (1) 下面定义中的哪些函数是从实数集R到R的双射函数?如果不是,说明理由. f(x)=1, x0, f(x)= (1, x(0, g(x)=lnx, x0 h(x)=1/(x3+8), x ( (2 t(x)=x3+8 (2) 计算以下集合A,B,C的基数. L是坐标平面上的一条直线,A是L上所有点的集合; S={a,b},B是S上的字符构成的有限长度的串的集合; C是某个服务器登录密码的集合,要求每个密码由6位构成,每位可以是小写的英文字母或者十进制数字. (3) 对于以下给定的每组集合X和Y,构造从X到Y的双射函数. A. X=2Z={2k k(Z},Y=N,其中Z为整数集合,N为自然数集合. B. X=R, Y=(0,+(),其中R为实数集合. C. X=P({a,b}), Y={0,1}{a,b} (4) f:A(B导出的A上的等价关系R定义如下:R={x,yx,y(A且f(x)=f(y)}. 设f1, f2, f3, f4(NN,且满足: f1(n)=n, (n(N f2(n)=1, n为奇数;f2(n)=0, n为偶数 f3(n)=j, n=3k+j, j=0,1,2, k(N f4(n)=j, n=6k+j, j=0,1,…,5, k(N Ri为fi导出的等价关系,i=1,2,3,4. 求商集N/Ri, i=1,2,3,4. 并求H={10k k(N}在f1, f2, f3, f4下的像. 3. 证明题 (1) 设满射函数f:A(A, 且f(f=f, 证明f=IA; (2) 设A,B,C是集合,且A(B=A(C=(, B(C, 证明A(B(A(C. 4. 应用题 设cardA=(, B是A的可数子集,card(A(B)是否为可数的?解释你的结果. 图论部分 (一) 1.填空题 (1) n阶k-正则图G的边数m=; (2) n阶竞赛图的基图为; (3) 3阶3条边的所有非同构的有向图共有个; (4) G为无向n(n≥3)阶圈,则k(G)=; (5) 命题图中极大路径为最长路径的线)阶简单回路,则D的可达矩阵为 2.解无向图 (1) 无向图G有8条边,1个度顶点,2个2度顶点,1个5度顶点,其余顶点的度数均为3,求3度顶点的个数; (2) 无向图G的边数m=16,3个4度顶点,4个3度顶点,其余顶点的度数均小于3.问G至少有几个顶点 3.证明题 (1) 设d1d2,…,dn为n个互不相同的正整数,证明d1d2,…,dn不可简单图化. (2) 设无向简单图G中无悬挂顶点即度顶点,证明G中必含3的圈. 4.画非同构的子图 (1) 画出K5的3条边的所有非同构的子图; (2) 画出3阶有向完全图的所有2条边的非同构的子图. 1.填空题 (1) 在完全图K2kk≥2)上至少加条边,才能使所得图为欧拉图; (2) 当n为时,完全图Kn既是欧拉图,又是哈密顿图; (3) 完全二部图Krs(r,s≥2且为偶数中的欧拉回路共含条边; (4)完全二部图Kr,s为哈密顿图,则rs应满足______________; (5) 命题强连通的有向图都是哈密顿图的真值为______________; (6) 命题G为n阶无向简单图,若((V(G),u与v不相邻,满足:d(u)+d(v)≤n(1 则G不是哈密顿图的真值为______________. () n阶竞赛图的基图为; () 当n为时,完全图Kn既是欧拉图,又是哈密顿图; () n阶m条边的无向连通图G,对应它的生成树T有个基本回路; () 设G是由K1、K2K3组成的平面图,则G共有_________个面; .证明题 (1) 若无向图G为欧拉图,证明G中无桥; (2) 设G为无向连通图,C为G中一条初级回路圈,若从C上删除任何一条边后,C中剩下的边构造的路径都是G中最长的路径,证明C为G中的哈密顿回路. .应用题 已知a、b、c、d、e、f、g 中,会讲的语言分别为 a:英语、德语 b:英语、汉语 c:英语、意大利语、俄语 d:汉语、日语 e:意大利语、德语 f:俄语、日语、法语 g:德语、法语 问能否将他们的座位安排在圆桌旁,使得每个人都能与他身边的人交谈?1.填空题 (1) 6阶无向连通图至多有棵生成树; (2) n阶m条边的无向连通图G,对应它的生成树T有个基本回路; (3) 设是各边带权均为1的阶带权图的一棵最小生成树,则W(T)= (4) n(n≥3)阶无向树T中,≤((T)(___________; (5) 高为的正则2叉树至少有片树叶; (6) 波兰符号法的运算规则是. 2.解无向树或画非同构的无向树 (1) 已知无向树T中,有3个3度顶点,2个4度顶点,其余的顶点均为树叶,求 T的树叶数; (2) 下面两组数中,哪个些能充当无向树的度数列若能,至少画出3棵非同构的无向树 ① 1, 1, 1, 2, 2, 2, 2, 3 ② 1, 1, 1, 2, 2, 2, 2, 5 3.求最优树 求带权为55,6,7,10,15,20,30的最优树T,并求W(T). 证明题 (1) 设T为无向图G的一棵生成树,是T的余树,证明中不含G的割集; (2) 设T是r叉正则树,i是分支点数,t是树叶数,证明:(r(1)= t(1.1. 填空题 (1) 设A={1,(1},则A关于普通加法、减法、乘法、除法中_____________运算是封闭的; (2) 设R*为非零实数集,以下各式右边的运算为普通四则运算, a(b = (a+b)/2, a?b = a/b, a?b = ab, a◇b = a+b 则在R*上不可结合的运算是_________________运算; (3) 设Z4 = {0,1,2,3}, (为模4乘法, 即x(y = (xy) mod 4. 则Z4, (的运算表为 __________________; (4) 设Z为整数集,(a,b(Z, a(b = a+b(1, (a(Z, a的逆元a(1 =______________; (5) 设代数系统V=2Z,+,其中Z为整数集合,2Z = {2k k(Z}, +为普通加法. 则V的子代数是_____________________________________; (6) 设代数系统V=A,+,A=, +为矩阵加法. 则V中运算的单位元和矩阵的逆元分别是__________________________________. 2. 简答题 (1) 判断正整数集合Z+ 和下面的每个二元运算是否构成代数系统. 如果是,则说明这个运算是否适合交换律、结合律和幂等律,并求出单位元和零元. a(b = max(a,b), a?b = min(a,b), a?b = ab, a◇b = (a/b)+(b/a) (2) 设A={a,b},试给出A上所有的一元运算,并找出一个既不可交换也不可结合的二元运算. (3) 设代数系统V1,V2,V3中的运算分别如表9.8所示,说明这些运算是否满足交换律、结合律和幂等律,求出单位元、零元和所有可逆元素的逆元(如果存在的线) 代数系统V=P({a,b}),(,(为集合的对称差运算,求出V的所有子代数,并说明那些是非平凡的线) 设V=A,(是代数系统,V中适合结合律,存在单位元,且每个元素都有逆元,证明(a,b,c(A,a°b=a°c ( b=c. (2) 设V1=Q*,·和V2=Q,+是代数系统,其中Q是有理数集合,Q*=Q({0}.·和+分别代表普通乘法和加法. 证明不存在V1到V2的同构. 4.应用题 设(是非空有穷字母表,(是(上的有限个字符构成的序列. 序列中的字符个数称为串的长度,记作(. (表示空串,(=0. 对任意的k(N,令(k表示(上的所有长度为k的串的集合,那么表示(上的所有串的集合. 在(*定义连接运算°,((1,(2((*,(1=a1a2…am, (2=b1b2…bn,那么(1°(2= a1a2…amb1b2…bn. 回答下面的问题: 如果(=n,card(*等于什么? (*与连接运算构成代数系统,分析这个系统是否满足交换律、结合律、幂等律和消去律,是否具有单位元和零元. (3) 令f:(*(N,f(()=(,证明f构成(*,°到N,+的满同态映射.1. 填空题 (1) 设G=a为12阶循环群, 则G的4阶子群是______________; (2) 设Zn是模n的整数环,在_________________条件下, Zn构成域; (3) 设G=S4为4元对称群,则 (1 2 3 4) =__________________________________; (4) 设G=a是24阶循环群,则G的生成元为______________________________; (5) 设R为实数环,M2(Z)为2阶实数矩阵环,那么在它们的直积R(M2(R),+,(中, =___________________________; (6) Z和Zn分别表示整数环和模n整数环,则f?:Z(Zn,f(x)=_________________是Z到Zn的满同态映射. 2. 简答题 (1) 判断下面集合对于给定运算能否构成群,并简要说明理由. A. 非零实数集合R*关于°运算,其中a°b = 2ab; B. G=关于矩阵乘法. (2) 举出不同的环,各满足以下条件: R1:没有单位元,但是存在子环S含有单位元; R2:有单位元,子环S有单位元,但是这两个单位元不相等. (3) 设Zn为模n整数加群, f:Z12(Z3, f(x) = (x) mod 3, 验证f为同态映射. 说明f是否为单同态和满同态. (4) 设G =Z24,(, 求出G的全体子群,并画出子群格. 3. 证明题 (1) 设G为群,证明G为Abel群的充要条件是对于G中任意元素a,b有(ab)2=a2b2. (2) 设G为群,(为G上等价关系,且满足(a, b, c(G,ab(ac ( b(c. 证明等价类 [e] = {x e(x, x(G}构成G的子群. 设V=A,(是代数系统,V中适合结合律,存在单位元,且每个元素都有逆元,证明(a,b,c(A,a°b=a°c ( b=c. 设G为群,证明G为Abel群的充要条件是对于G中任意元素a,b有(ab)2=a2b2. , (a,b∈Z 有 a?b = a+b(1, a◇b = a+b(ab. 证明Z, ?,◇构成环 (6)判断正整数集合Z+ 和下面的每个二元运算是否构成代数系统. 如果是,则说明这个运算是否适合交换律、结合律和幂等律,并求出单位元和零元. a(b = max(a,b), a?b = min(a,b), a?b = ab, a◇b = (a/b)+(b/a) 4. 应用题 某一通讯编码的码字x=(x1,x2,…,x7),其中x1,x2,x3和x4为数据位, x5,x6和x7为校验位,并且满足: x5=x1(x2(x3,x6=x1(x2(x4,x7=x1(x3(x4 这里的(是模2加法. 设S为所有这样的码字构成的集合,在S上定义二元运算如下: (x,y(S, x°y=(x1(y1,x2(y2,…,x7(y7) 验证S,°构成一个群.填空题 (1) 设代数系统V=A,+,A=, +为矩阵加法. 则V中运算的单位元和矩阵的逆元分别是__________________________________. (2) n阶循环群的生成元有______个即_____ _,无限循环群的生成元有___________个即___________; () 设n为正整数,Sn为n的正因子集,S关于整除关系构成格,令n=1,2,3,4,5,6, 那么当n=________________时,Sn构成布尔格; (设X={1,2,3,5,6,10,15,30}, Y={2,3,6,12,24,36}, W={1,2,3,6,18,54}, T={2n n为正整数}, 这些集合中关于整除关系构成格的有_______________________; () 图11.9的哈斯图中构成分配格的有______________________; () 设P是命题 (a(b)((b(c)((c(a)?(a(b)((b(c)((c(a), P的对偶命题是 _________________________________________________; () 设L为钻石格,则L有_____________________个2元子格; (8) 设n为正整数,Sn为n的正因子集,S关于整除关系构成格,令n=1,2,3,4,5,6, 那么当n=________________时,Sn构成布尔格; () 设B, (, (, (, 0,1是布尔代数,同一律的表达式是______________________. 2. 简答题 (1) 设A= {1, 2, 5, 10, 11, 22, 55, 110}, A关于整除关系构成格L. 求L中所有有补元素的补元. (2) 设L是模12加群Z12,(的子群格,给出L的所有4元子格. (3) 在布尔代数中化简下列公式: (a(b()((a(b)( (4) 设R为实数集,At = {x x(R ( Kt( x ( t+1},其中K0 = K2 = 0, K1 = K3 = (1, K4 = (2. 令S = {At t = 0,1,2,3,4}. 画出偏序集S,(的哈斯图并求它的极大、极小、最大、最小元. 说明该偏序集构成什么格? (5) 设G=Z5,(. 令G上所有自同构构成的群为AutG,给出AutG的运算表并画出它的子群格L的哈斯图. 说明这个格是否为分配格、有补格、布尔格. 3. 证明题 (1) 设I是格L的非空子集,如果满足下述条件,则称I为L的理想: (a,b(I有a(b(I, (a(I, (x(L 有x?a(x(I 证明I是L的子格. (2) 在格L中如果(a,b,c(L有a((b(c)=(a(b)((a(c)成立,证明(a,b,c(L有 a((b(c)=(a(b)((a(c) 成立. 6 图11.9

  国开(广西)50753-中国传统文化概观-2019春形成性考核作业4(25分)-辅导资料.docx

  国开(广西)50753-中国传统文化概观-2019春形成性考核作业3(25分)-辅导资料.docx

  《习 近 平新时代中国特色社会主义思想第十讲-坚定不移贯彻新发展理念》.ppt

本文链接:http://scrinzoom.com/qianshufanshi/604.html