2023年计算机数学基础一离散数学期末复习参考.pdf

计算机数学基础（一）一一离散数学期末复习参考一、关于期末考试。L本学期的结业考核由形成性考核和期末考核构成。形成性考核由平时作业成绩构成，占结业考核成绩的2 0%,期末考核成绩占结业考核成绩的8 0%。2.期末考核算行全国统一考核，根据本课程考试说明，由中央电大统一命题,统一考核时间,制定统一评分标准。开办试点的地方电大组织考核。期末考核的考核内容和规定以考核说明为准；采用闭卷笔试，试卷满分1 0 0分;时限1 20分钟。试题类型及分数:单项选择题和填空题，分数约占25%。解答与计算题，分数约占5 6%;证明题，分数约占1 9%。3,考核试卷分数分布：第1编数理逻辑约30分，第2编集合论约30分，第3编图论约2 5分，第4编代数系统约15。4.易、中、较难题目在试卷中占的比例是4:4:2。二、各章重点考核内容第1章 命 题 逻 辑1.命 题 联 结 词 真 值 真 值 表 简 朴 命 题 符 号 化2.命 题 公 式 永 真 式 永 假 式 可 满 足 式3.公式等值演算（必须掌握公式基本等值式）4.求 范 式（用各种方法求合取范式、析取范式，特别是主析取范式，主合取范式等）5 .掌握逻辑推理的方法。第2章 谓 词 逻 辑1.谓 词 量 词 个 体 词 个 体 域 变 元（约束变元、自由变元）简朴命题符号化2.判别简朴谓词公式的类型（永真式、永假式、可满足式）3 .求前束范式4 .有限个体域中，求给定解释下的公式真值。第 3章 集合及其运算1 .集 合 元 素 全 集 空 集 幕 集2 .集合的关系与运算3 .有序对和笛卡儿积第 4章 关系与函数1 .二元关系及其表达方法一一集合方法、矩阵和图2 .关系的运算和复合关系、逆关系3 .二元 关 系 的 性 质（5 条性质）4 .等 价 关 系（等价类）与 偏 序 关 系（哈斯图 极大（小）元 最 大（小）元5 .函 数 复 合 函 数 单 射 满 射 和 双 射，求反函数第 5章图的基本概念1 .图 结 点 边 有 向 图 无 向 图 简 朴 图 多 重 图 完 全 图 子 图 与 生 成 子 图结点度数握手定理及其推论2 .通 路 通 路 的 长 度 初 级（简朴）通 路 回 路 初 级（简朴）回路点割集与割点 边 割 集 与 桥 连 通 图 强（单测、弱）连通3 .关联矩阵邻接矩阵第 6章 几种特殊图1 .欧拉通路（回路）欧 拉 图 哈密顿通路（回路）哈密顿图2 .平 面 图 面 的 次 数 平 面 图 相 关 定 理（定理6 8）3 .树 无 向 树 有 向 树 最 小 生 成 树 根 树 最 优 树 二 叉 树第 7章 群。1 .代 数 运 算 以 及 运 算 性 质 单 位 元、逆元，代数系统，。2.半 群 群 及 其 性 质 子 群3.循 环 群 互 换 群 元 置 换 及 置 换 群。4.群的同态与同构第 8 章 其它代数系统1 .环与域，环.2.格 有 界 格 有 余 格 分 派 格。3.布尔代数三、各章基本问题第 1 章 命 题 逻 辑1.命题符号化,是否命题判断或求真值。2.命题公式赋值，及类型判别。3 .命题公式等值判别或证明。方法有真值表法、等值演算法和主范式法.4 .求范式和主范式。5.蕴含式（推理理论）证明：方法有:真值表法、等值演算法、主析取范式法、构造证明法一一直接法、附加前提证明法和反证法。第 2 章 谓词逻辑1.命题符号化。2 .求辖域、约束变元、自由变元。3.给定解释求谓词公式的真值（多为个体域有限的情形）。4 .判断谓词公式是否重言式（用代换实例）、永假式？5 .求前束范式。第 3章 集 合 及 其 运 算求集合表达式（列举法或描述法）。2.判断集合与元素、集合与集合的关系，用金e ug,a?3.求惠集。4包含或相等的化简或证明。5.求笛卡儿积，或某些等式证明。第 4 章 二元关系与函数1 .求关系的表达式，关系矩阵、关系图，Dom（R）,Ran（R）.2.验证或证明关系的性质。3.关系计算:求u,c,4.求复合关系、逆关系及其矩阵。5.求自反闭包或对称闭包。6.验证或证明关系R是等价关系或偏序关系。7.作偏序关系的哈斯图，求极大（小）元、最大（小）元。8.验证是否是函数，是满射、单射、双射？第 5 章 图的基本概念。1.图G与G=互求。2.判断简朴图、多重图、完全图。3.求子图或生成子图。4.求结点度数或用握手定理求结点数，或判断是否度数序列。5.判断是否同构，重要用必要条件判断不同构。会作2或3个结点非同构的生成子图。6.用定理1 （握手定理）或2以及推理进行推理或计算。7.求图中通路、回路、长度或通路、回路的数目（重要用定理8）8.判断是否连通、强连通、单侧连通或弱连通。9.求点割集、割点和边割集、割边（比较简朴的图）。1 0.求有向图的邻接矩阵和可达矩阵。第 6 章几种特殊的图1.判断或作欧拉图，求欧拉通路、回路。2.判断或作哈密顿图，求哈密顿通路、回路，说明不是哈密顿图。3 .判断是否可平面图,将可平面图改画为平面图。4.求连通平面图的面、边界和次数。5.用定理6,7作某些证明或计算。如求二元完全树中树叶个数与分支点数之关系。6.判断是否树。7 .求树的结点与边的关系。8.求最小生成树和权。第 7 章 群I.验证代数运算F在A上封闭，即/,是代数系统。2.验证代数运算有结合律，互换律等。3.验证代数运算f,g有无分派律，吸取律等。o 4.求运算的单位元，逆元。5.判断是否半群、群、互换群、循环群，求生成元和循环群的子群。.7.在群中进行计算、化简等。8 .求复合置换、逆置换等。9.证明群同态、同构,找同态（同构）映射。第 8 章 其它代数系统1.验证是否为环？2.给出偏序集,判断是否为格?3 .在格中进行计算、化简或证明等。4 .布尔代数式的化简、求值或证明.四、自我练习题一、单项选择题1.给定无向图如图1所示，下面给出的顶点集的子集中，不是点割集的为()(A)W (B)d(C)a,c(D)e,g 2 .无向完全图K的不同构的生成子图有(A)6(B)5 (C)43 .在自然数集合N上，下列运算可结合的是()个.(D)3A .x*y =m a x(x,y)B .x*y-2x+yC.x*y=x2+y2D.4 .设N为自然数集合，N,。在下面4种运算下不构成代数系统的是()(A)x o y =x+y -2 xy(B)x oy=x+y(C)龙。y=xy(D)xoy-k I+y I(其中,+、一分别为普通加法和减法)5.已知偏序集的哈斯图，如图2所示，是格的为(图2二、填空题6.若命题变元P,Q,7?赋值为(1,O,l),则命题公式G=(P八Q)f R)j(P v Q)的真值是_ _ _ _ _ _ _ _ _ _ _。7.设N(x)：x是自然数，Z(y)；尸是整数，则 命 题“自然数都是整数，而有的整数不是自然数“符号化为_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _8.设4,B为任意集合，命 题A-B=0oA=B的真值为.9.设4 8为有限集，且|A|=?,|B|=，那末A与3间存在双射，当且仅当.1 0.在有向图的邻接矩阵中，第i行元素之和，第j列元素之和分别为三、化简解答题1 1 .做命题公式(Pf。)(PAQ)/P)的真值表，并判断该公式的类型.1 2.化简集合表达式：(AuBuQn(AuQ)-(Cu(C-B)-A)13.(1)将命题公式P)化为只含和A的尽也许简朴的等值式.(2)求谓词公式X/x(P-C(x)v R(/(a)的真值.其中 P:43,Q(x):xl,R(x):x 2,(4)=4.a:4.个体域。=0,4).四、计算解答题14.(1)设A和S是集合A=1 ,2,3 上的二元关系，/?=,5=,求AS,写出它的矩阵MR.S.(2)求布尔表达式E(a,/?,c)=(a+人c)+匕+c的对偶式，并求当取值0,0,1时，E(“力，c)以及其对偶式的真值。15.指出谓词公式Vx(尸(x)-G(x,z)v P(X)A玉H(x,y)AS(X)中VX和 女 的 辖域，并 指 出该公式的 约 束 变 元 和 自 由 变 元 以 及 约 束 出 现 次 数 和 自 碱 电 次 P)i(P A i 0 A (iP A 17?)不惟一.V x(P f Q(x)vR(/(a)=(P-Q(。)A(P-Q(4)v R(7(4)=(1-I)v0o0四、计算解答题14.R S=,=,-1 0 0-。M R.S=0 0 00 1 0(2)(0,0,1)=(0+0 1)+0+1 =(1 1)+0+1=1E(a,b,c)=(a+bc)+b+c 的对偶式为(a人+c)人c,其真值是(痴+1)0 1 =1 0 1 =01 5.Vx 的辖域为：尸(*).G(x,z)vP(x)mx的辖域为:H(x,y)初既是约束变元，也是自由变元，约束出现4次，自由出现1次.y是自由变元，自由出现1次.z是自由变元，自由出现1次.Vx为(Q(/(x),y)f h尸(幻o (孙2(/(2),y)A(ByQ(f(3),y)f P(2)v P(3)o (。(3,2)v Q(3,3)A(2(2,2)v 0(2,3)-0 v 1o(0 v l)A(0 v l)f 1 o l 1 6.做法如下:选边1;选边2；A选边3；选边5;选边70最小生成树为 1,2,3,5,7).如图4中粗线所示.权数为18 .1 7.设图G有 x个结点，有握手定理。2x l+2x 2+3x 4+3 x(x-2-2-3)1 2x 2。3x=24+21-1827图4x 9图 G至少有9个结点.图5满足条件的图如图5所示.五、证明题1 8.Xfxe A,eR,&SeRrS,所以 R cS 有自反性;由于凡 S 是对称的，R r S e R八&SRM J称的=e G Sw R cS/w R cSG e 5A e G S。e 7?A e R/e S/e SR,S传递=G HA G S=V X,Z RCS所以，R cS 是 传 递 的.。总之,R c S 是等价关系.1 9.一方面证*在5 上封闭.任取S 中的元素a 00 ba 00 ba 00 bx 0o y，其中。，*x00yx 00 y即运算*满足互换律。任取S 中的元素ax0。byax 00 hya 0e S ,由于or,bywR*.即*在 S 上封闭.且有x 00 y*a 00 bx 00,其中 a,h,x,y,c,d&A*,有a0a00 b0 y0 d可见,*满足结合律.0h*X00y)*c()0dax00by*c00daxe00byd0X0c0a0 xc0axe0*(*)=*h0y0d0b0yd0bydx 0ci0，任取S 中的元素有o y0b设单位元为E=a 0*x 0ax0a 0 x 0*a 0 xa 00 bo y0by0 b0 y0 b_ 0 yb_10得到4,有=ax=a，由a,b的任息性，得 x=l,y=lb y-b01e S,即 E 是 S 上关于运算*的单位元。任取S 中的元素a 00 b假如其逆元为x=x00y,应有a 00 bx0oya 00 bx0oy1ooi得到4ax=lby=1，由于 力不为0,得了=。显然a b不为0,即 x,yeR*,10 x1G S,它是a00b的逆元。S 的每个元素都有逆元,0y