下载  >  课程资源  >  讲义  > 离散数学.pdf

离散数学.pdf 评分

第一编 数理逻辑 第二编 集合论
在简单命题中,表示个体的性质或个体之间联系的词称为谓词,表示数量的词称为量词,量 词一般有两种:全称量词Ⅴ和存在量词彐 2.2合式公式 阶谓词逻辑的字母表∑为 个体常元a,b,c, 个体变元|x,y,z,… 函数符号f,g,h,…(n元函数f可记为f) 谓词符号|P,Q,R 联结词∧V… 量词 y彐 辅助符号|() 项的归纳定乂如下:()个体常元和个体变元是项:(2)若t,t,t,…是项,则f(t,t,t,…) 是项;(3)只有通过有限次使用(1)和(2)所得到的符号串是项。 设t,t,t,…t是项,则称P(t,t,t,…t)为原子公式。 合式公式的归纳定义如下:(1)原了公式是合式公式;(2)若A,B是合式公式,则(-A),(A ∧),(AVB),(A→B),(A<B),xA,彐xA是合式公式;(3)只有通过有限次使用(1),(2) 所得到的符号串才是合式公式 在合式公式QXA中,称A为Q的辖域,其中Q为或彐。变元ⅹ在Qx及Q的辖域中的出现称 为ⅹ的约束出现,并称x为约束变元;x的非约束出现称为ⅹ的自由出现,并称ⅹ为自由 变元 换名规则:若要将约束变元ⅹ改为y,则①1)将Qx中的ⅹ及在Q的辖域中自由出现的x均改 为y:(2)y不在限制x的量词的辖域中出现。 2永貞公式 合式公式G的一个Ⅰ是由一个非空集合D(称为I的论域)和如下一组规则组成 (1)对G中的每一个个体常元和自由个体变元指定D中的一个元素 (2)对G中的每一个n元函数,指定D上的一个n元函数 3)对G中的每一个n元谓词符号,指定D上的一个n元谓词。 永真式 2.4范式 称下述形式的公式为前束范式: QxQx Qx Q…B,其中Q为或彐,B是不含任何量词 的公式。并称 Qx Q为前束词,称B为母式。 Skolem范式 设前束范式为QxQx…Qx…QxB。若Qx为]x(至tsr),那么(1)当Qx左边无全 称量词时,用B中未出现的个体常元a支代替B中ⅹ的所有出现,并删支出Qx:(2)当Q X左边的所有全称量词为QxQx,…,Qx(1至 )时,取B中未出现的s元函数符 号f,用£(x,x,x)代替B中x的所有出现,并删支Qx。这种消去量词的变换 称为 Skolem变换 ▲2.5推理理论 (1)全称指定规则(US规则): (2)存在推广规则(EG规则): (3)存在指定规则(ES规则): (4)全称推广规则(UG规则): 第二编集合论 第三章集合 1集合的基本概念及其表示法 集合,N,I,Q,R,C ●设A是任意集合,A表示A所含有的元素的个数。 (1)若A=0,则称A是空集,记作 (2)若A是自然数,则称A是有限集。 (3)若A无穷大,则称A是无限集。 ▲集合的表示法:(1)列举法按某一次序列出集合的全部或部分元素,并用一对花括号括起 (2)措述法用谓词描述出集合元素的公共特征,其形式为S={x|P(x)} (3)归纳定义法通常包括以下三步 ①基本步S非空且S中的任意元素均是A的元素 ②归纳步给出一组规则,从A的元素出发,依据这些规则所得到的仍是A的元素; ③极小化若S的任意元素均是A的元素,并且S满足①和②,则S与A有相同的元素 元素可以多次出现的集合为多重集,无特別说明,集合均指一般集合,不是多重集 3.2集合的运算 并差 完全以集合为元素的集合称为集类,常用字 表小 义交 广义并: 环和 环积 幂:设A是集合,则称{xxA为A的幂集,A的幂集即是由A的所有子集组成的集合。 3.3基本集合恒等式 3.4容斥原理 3.5集合的笛卡尔积 ●称〈x,y)=(x},{x,y}}为由x和y组成的有序二重组,也称为序偶。 ●设n∈I,x,x,…,x是n个任意的元素。(1)若n-1,则令<x>=x;(2)若n=2,则令 x,x>-{x},{x,x}};(3)若n>2,则令<x,x,…,x〉<x,x,…,x>,x>.称<x,x,…,x 是由ⅹ,x,…,x组成的有序n重组,称x(1<i<n)是它的第i个分量 ●设n∈Ⅰ,集合A,A,…,A的笛卡尔积AA…A定义为AA…A={<a,a,…a> ∈A,i=1,2,3…n}.称n为该笛卡尔积的维数。若A=A=…A,则记AAA…A为A 笛卡尔积满足下列分配律 第四章二元关系 ●设n∈I,,A,…,A是n个集合,R≤A,称R是集合A,A,…,A上的n元关 系。若A=A=…=A=A,则称R是A上的n元关系。当n=2时,称R是A到A的二元关 系,A称为R的前域,A称为R的陪域,称dom(R)={x|x∈A∧<x,y>∈R}为R的定义域, 称ran(R)={y|y∈AA<,y>∈R}为R的值域。 若<a,b>∈R,则说a与b有关系R,常用中缀法记为aRb;若<a,b>∈R,则说a与b没有关系 R,常用中缀法记为aRb。 由于任意集合均有两个平凡子集,即空集和集合自身,因此称AA…A上的关系为空关 系,称AA…A为全域关系 A上的关系{x,x>x∈A称为A上的恒等关系,记为I ●设R∈A,RsA.若(1)n=m;(2) ;(3)集合R和R柑等,则称关系R与R相 等,记为R=R。 ▲关系的表示 (1)集合表示法;(2)关系矩阵表示法;(3关系图表示法。 4.2关系的性质 ●设A是集合,RAA。(1)右Vx(xA→xRx),则称R是自反的:(2)若x(xCA→xx),则 称R是反自反的:(3若xy(x∈A∧y∈A∧xRy→yRx),则称R是对称的:(4)若x∨y(x ∈A∧y∈A∧xRy∧yRx→x=y),则称R是反对称的:(5)若 VxVyVZ(x∈A∧y∈A∧z∈A∧ Ry yrz→xRz),则称R是传递的 4.3关系的运算 ●设A,B是集合,RAB,且S∈AB,则交R∩S,并RUS,差RS和补R均是A和B上 的二元关系,且x(R∩S)y台xRy∧xSy,x(RUS)分XRy∨xSy,x(R-S)分ⅹRy∧xSy,xRy分 R ●设A和B是集合,RsAB,令RBA且R={<y,x|xRy},则称R是R的逆关系。 ▲设A和B是集合,R≌AB(i=1,2),则1)R=R;(2R∩R=R∩R;3)R∪R=R∪R(4R-R=R-R; 5)R=R:(6)若R=R,则RR ●关系的合成:设A,B和C是集合,RAB,RBC,R与R的合成关系是 RRCAC, 且RR={<X,2>x∈A∧z∈C∧彐y(y∈B∧ xR yAyR Z)} 合成运算不满足交换律,但是它满足结合律。 关系的幂:设A是集合,RsAA,n∈N,则R的n次幂定义为R=I,R=RR ●设A是集合,R三AA。若R≤AA,且满足:(1)R是自反的(对称的、传递的);(2)RR 3若RsAA且满足:①R是自反的(对称的、传递的),②RR,则≤R:那么称R是R 的白反(对称、传递)闭包,记为r(R)(s(R),t(R)) ▲设A是集合,R≤AA,则(1)R是自反的当且仅当r(R)=R;(2)R是对称的当且仅当s(R)=R 3)R是传递的当且仅当t(R)=R。 ▲设A是集合,RAA,则(1r(R)=R∪I;(2s(R)=R∪R;3t(R)=∪R 设A是集合,R∈AA(i=1,2),若RR,则(1r(R)cr(R);()s(R)cs(R);(3)t(R) t(R); ▲设A是集合,R三AA,(1)若R是自反的,则s(R)和t(R)自反的;(2)若R是对称的,则 r(R)和t(R)是对称的;(3)若R是传递的,则r(R)传递的。 ▲设A是集合,RAA,则(1rs(R)=sr(R);(2rt(R)=tr(R);(3st(R)sts(R) 4.4等价关系和划分 ●设A是集合,RsAA。若R是自反的、对称的和传递的,则称R是A上的等价关系,并 且若aRb,则说a与b等价。 ●设R是集合A上的等价关系。对任何a∈A,称[a]={x|x∈A∧xRa}为a关于R的等价类 (有时简记为「a1),并且称a为「a1的代表元;若等价类个数有限,则称R的不同类的 个数为R的秩,否则称R的秩是无限的,称{[a]|aCA为A关于R的商集,记为A/R。 ▲设R是A上的等价关系,A=,a,b∈A,则()[a]=;(2)aRb当且仅当[a]=b;(3)[a]=[b 或者[a]∩[b]= ●设集合A=,∈(A)。若满足:(1)∈;(2)中任意两个不同元素不相交;(3)U=A 则称是A的一个划分,且称中的元素为划分块:若有限,则称的不同划分块的个数 为的秩,否则称的秩是无限的。 ▲设集合A=,R是A上的等价关系,则A/R是A的一个划分。 ▲设集合A-,R和R是A上的等价关系,则R=R当月仅当A/R=A/R。 等价关系可以诱导一个划分,一个等价关系所诱导的划分是惟一的。 ▲设是非空集合A的划分,定义A上的二元关系R为:aRb当且仅当a和b同属于A的 个划分块。则R是A上的等价关系 设集合A=,是A的个划分,R是A上的个等价关系,则诱导R当且仅当R诱导。 个等价关系可以惟一诱导出一个划分,一个划分也可惟一确定一个等价关系。 ▲设集合A=,和是A的划分,且它们诱导的等价关系分别为R和R,那么细分当且 仅当R≤R ●设集合A=,和是A划分。(1)若是A的划分,且①纽分和;②若细分和,则细 分,则称是与的积。记为.(2)若是A的划分,且①和细分;②若和细分 则细分,则称是与的和。记为 ▲设集合A=,和是A的划分,且它们诱导的等价关系分别为R和R,那么(1)R∩R诱 导的划分是;(2)t(RUR)诱导的划分是 1.5序关系 序关系是一类重要的元关系,它提供了比较集合中元素的一种方法。 ●偏序关系:设A是集合,RsAA。若R是自反的、反对称的和传递的,则称R是A上的 偏序关系,并称<A,R>是偏序集。 偏序关系有吋也称作半序或部分序关系,常用表示偏序关系。 覆盖:设R是集合A上的偏序关系,a∈A.若b∈A满足(1)aRb且b=a:(2若x∈A使得aRx 且xRb,则必有x=a或x=b.那么称b是a关于R的覆盖 ●拟序关系:设A是集合,RsAA。若R是反自反的和传递的,则称R是A上的拟序关系, 并称<A,R>是拟序集。 ▲拟序关系是反对称的。 ▲设A是集合。R≤AA。(1)若R是偏序关系,则R-I是拟序关系;(2)若R是找序关系,则 R∪I是偏序关系。 ●全序关系:设<A,>是偏序集,若∨xy(x∈A∧y∈A→xy∨yx),则称是A上的全 序关系到,并称<A,>为全序集。全序关系也称作线序关系,全序集<A,>也称作线序集 或链 ●良序关系:设<A,>是偏序集,若对任意的S,=SsA,则S有最小元,那么称是A上 的良序关系,并称<A,>为良序集。 4.6柑容关系 ●设A是集合,RsAA。若R是自反的和对称的,则称R是A上的相容关系:若aRb,则称 与y相谷,否则称x与y不相容。 ●设R是集合A上的相容关系。(1)若=C=A,且∨a,b∈C,有lRb,则称C是R的一个相容 类。(2)若C是R的相容类,∨b∈C,则必有a∈C使得aRb,那么称C是R的一个极大相容 类 ▲求极大相容类的方法:(1)关系图法; (2)关系矩阵法 第五章函数 5.1函数的基本概念和性质 设X和Y是任意集合,fcXY.若x(x∈X→!y(y∈Y∧<x,y>∈f)),则称f是从X到Y 的函数,记为f:X→Y. 设f:X→Y,X=.定义RXX为x,xCX,xRx当且仅当f(x)=f(x),则易证F是Ⅹ 上的等价关系(称之为由f诱导的等价关系),并且由关系R确定的划分为{f({y})y ∈Y∧f(y})=}.令g:X→X/R,g(x)=「x],称g是由f诱导的规范映射。可见对给定的 一个函数均可得到一个规范映射。 ●设X和Y是任意集合,则从X到Y的所有函数构成的集合记为Y,即Y=ff:X→Y 当一个函数是递归定义时,常需要验证函数是良定的(we11- defined) ●设f:X→Y.(1)若f(X)=Y,则称f是满射的。(2)若∨xx(x∈X∧f(x)=f(x)→x=x),则称 f是单射的。(3若f既是单射的,又是满射的,则称f是双射的。 ●集合的的特征函数:设U是全集,AsU。定义A的特征函数为:U→{0,1},(x)= 5.2函数的合成 ▲设f:X→Y,g:Y→Z,则f与g的合成关系fg是从到Z的函数,并月对一切x∈X,f g(x)=g(f(x)) ▲设f:Ⅹ→Y,g:Y→Z,则(1)若f和g是满射,则gf是满射;(2)若f和g是单射,则gf是 单射;(3)若f和g是双射,则gf是双射。 ▲设『:Ⅹ→,g:Y→Z,则(1)若g是满射,则g是满射;(2)若g∫是单射,则『是满射;(3) 若gf是双射,则g是满射月f是单射。 5.3逆函数 设f:X→Y是双射,则f的逆关系f是从Y到Ⅹ的函数。 ▲设f是从X到Y的双射,g是从Y到X的函数,则f=g当且仅当gf=1且fg=1 ●设f:X→Y。若有g:Y→Ⅹ使得gf=1和fg=1成立,则称g是f的逆函数,并称f是可 逆的。 ●(1)若有g:X→Y,使得gf=1成立,则称g是f的左可逆函数,并称f是左可逆的。(2)若 有g:X→Y,使得g-1成立,则称g是「的右可逆函数,并称是右可逆的。 ▲设f:X→Y,X=,则(1)f是左可逆的当且仅当f是单射;(2)f是右可逆的当且仅当f是满射; (3)是可逆的当且仅当f是双射,或当且仅当f既是左可逆的,又是右可逆的 第六章集合的基数 6.1可数集和尢限集 ●设S是任一集合,称S=SU{S}的后继集 ●自然数N的归纳定义是:(1)∈N;(2)若n∈N,则n∈N;(3)若S∈N,且满足①∈S;② 若n∈S,则n∈S;则S=N。 若m,m∈N,n∈N使m∈n,则称m小于m,记为mn 设A和B是任意集合,若存在从A到B的双射,则称A与B是等势的,记为AB;若A 与B不等势,则记为AB。 ●右有ncN,使得N-A,则称A是有限集,且称其基数为n,记为|A|=n;右A不是有限集, 则称A是无限集。 ▲任何有限子集都不能与亡的真子集等势 设A是任意集合。若NA,则称A是可数无限集,并称A的基数为(读作阿列夫零), 记为|=。有限集与可数无限集称为可数集或可列集;非可数集合称为不可数集 ▲可数集的任何子集都是可数集。可数个可数集的并集是可数集。右A和B是可数集,则 AB是可数集 ▲实数集合的子集「0,1不是可数无限集合 ●设A是任意集合。若[0,1]A,则称A的基数为(读作阿列夫),并称A是具有连续统 势的集合,记为A ▲设A,B,C和D是任意集合,A~B,C~D,A∩C=B∩D=,则AUC~BUD 6.2集合基数的比较 ●设A和B是任意集合。若存在从A到B的双射函数,则称A和B具有相同的基数。 设A和B是任意集合,则A|=B,A<B|和A|>B恰有一个成立 设A和B是任意集合。若A≡|B,且B|≡|A,则|A|=|B 要证明A与B有相同的基数,只需找一个从A到B的双射即可。而此定理告诉我们,只要找 个从A到B的单射和个从B到A的单射就能证明A与B有相同的基数。 ▲下列三个条件是等价的:(1)A是无限集;(2)A有可数无限子集;(3)A有与其白身等势的 真子集 ▲(1)若A是有限集,则|A<<.2)若A是无限集合,则 ▲设A是任意集合,则|A|<|(A) 第七章代数系统 ●设A为非空集合,n∈Ⅰ,函数r:A→A称为A上的一个n元运算,n称为该运算的阶。 特别地,A中的每一个元素称为A上的一个0元运算 ●设。是集合A上的n元运算,S是A的非空子集,若∨a,a,…;a∈S,有。(a,a,…,a) ∈S,则称S关于运算。是封闭的。 ▲设。是A上的n元运算,是(A)的非空集合,若∨S∈,S关于。封闭,则∩关于 也封闭,即广义交保持封闭性。 ●设*是集合A上的二元运算。若∨a,b∈A,有a*b-b*a,则称*是可交换的,或称*满足交 换律 ●设*是集合A上的二元运算。若∨a,b,c∈A,有(a*b)*C=(来C),则称来是可结合的,或 称*满足结合律。 ●设*和。是A上的二元运算。(1)若Va,b,c∈A,有a*(°c)=(ab)°(a*c),则称*关于是左 可分配的。(2)若∨a,b,c∈A,有(b°c)*a=(b*a)°(c*a),则称*关于°是左可分配的。(3)若 *关于°既是左可分配的,又是右可分配的,则称*关于°是满足分配律 ▲设*是A上可结合的二元运算,则n∈I,∨a,a,…,a∈A,表达式a*a…经任 意加括号而计算出的结果不变 若*是A上可结合的二元运算,则∨a∈A及ym,n∈I,有a*a=a,(a)=a ●设*是A集合上的二元运算。(1)若彐e∈A,使得∨a∈A,有*a=a,则称e为关于的左单 位元,也称左幺元。(2)若彐e∈A,使得∨a∈A,有a*e=a,则称e为关于的右单位元, 也称右幺元。(3)若彐e∈A,使得a∈A,有e*=a*e=,则称e为关于的单位元,也称 幺元 ▲设*是A上的二元运算,e和e分别是关于的左、右单位元,则e=e,且它是关于*的惟 单位元 ●设*是集合A上的二元运算。()若彐0∈A,使得∨a∈A,有0*a=0,则称0为关于水的 左零元。(2)若彐0∈A,使得∨a∈A,有a*0=0,则称0为关于*的右零元。(3)若彐0∈A, 使得a∈A,有0*a*0-0,,则称0为关于半的零元。 ▲设*是集合A上的二元运算,0和0分别是关于*的左、右零元,则0=0,且它是关于8 的惟一零元 ●设*是集合A上的二元运算,e是关于*的单位元,a∈A.(1)若彐a∈A,使得a*a=c,则称a 关于*是左可逆的,并称a是a的关于*的左逆元。(2)若彐a∈A,使得a*a=e,则称a关 于来是右可逆的,并称a是a的关于来的右逆元。(3)若彐a∈A,使得a来a=a*a=e,则称a 关于*是可逆的,找称a为a的关于的逆元

...展开详情
所需积分/C币:19 上传时间:2018-06-29 资源大小:445KB
举报 举报 收藏 收藏
分享 分享
离散数学(第七版) 高清中文完整版 PDF 作者:Richard Johnsonbaugh(R. 约翰逊鲍夫)

离散数学(第七版),高清PDF扫描版。本书从算法分析和问题求解的角度,全面系统地介绍了离散数学的基础概念及相关知识,并在其前一版的基础上进行了修改与扩展。书中通过大量实例,深入浅出地讲解了数理逻辑、组合算法、图论、Boole代数、网络模型、形式语言与自动机理论、计算几何等与计算机科学密切相关的前沿课题,既着重于各部分内容之间的紧密联系,又深入探讨了相关的概念、理论、算法和实际应用。本书内容叙述严谨、推演详尽,各章配有相当数量的习题与书后的提示和答案,为读者迅速掌握相关知识提供了有效的帮助。

立即下载
离散数学第五版高清中文pdf

离散数学第五版高清中文pdf。。。。。。。。。。。。。。。。。。。。。。。。。

立即下载
离散数学屈婉婷最新版本第五版.pdf

离散数学屈婉婷最新版本第五版,清晰整齐,正版 离散数学屈婉婷最新版本第五版,清晰整齐,正版

立即下载
离散数学 第三版 方世昌 带完整目录

离散数学 第三版(扫描版) 方世昌 带完整目录 第1章 数理逻辑 1.1 命题 1.2 重言式

立即下载
离散数学(第七版)高清中文完整版 PDFRichard Johnsonbaugh

离散数学(第七版) 高清中文完整版 PDF 作者:Richard Johnsonbaugh

立即下载
离散数学的应用.pdf

本文档介绍了离散数学在数据结构、数据库、编译原理、人工智能、通信等领域的的应用情况,并在最后举了一个简单的生活中的例子来说明。

立即下载
02324 成人自考教材 离散数学 2014版

02324 成人自考教材 离散数学 2014版 成人自考教材电子版

立即下载
离散数学(左孝凌)-教材.pdf

本书是计算机科学核心课程——离散数学的基本教材。全书共分五篇。前四篇分别介绍了数理逻辑,集合论,代数结构和图论四个专题。第五篇为应用部分,主要介绍形式语言与自动机以及纠错码初步。内容叙述严谨,推演详尽,大部分概念都用实例说明并配有相当数量的习题。   本书可作为理工科院校计算机专业的离散数学教材,也可作为自动控制、电子工程、管理科学等有关专业的教学用书,并可供计算机科研工作者及有关工程技术人员参考。

立即下载
离散数学及其应用(中文第六版) 扫描版19.8M pdf格式

离散数学及其应用(中文第六版) 扫描版19.8M pdf格式 【高清重制】

立即下载
离散数学及其应用(高清版)

本书是经典的离散数学教程,本书全面而系统地介绍了离散数学的理论和方法,内容涉及数学推理、组合分析、离散结构、算法思想以及应用和建模,可以为算法和数据结构的学习打下扎实的基础

立即下载
离散数学耿素云屈婉玲编著.pdf

离散数学耿素云屈婉玲编著.pdf

立即下载
离散数学及其应用(第五版中文版 清晰文字版pdf)part1

[分五卷压缩,其余四卷在我的资源列表;收取一分,纯属被迫,望谅解,也希望你能好哈读这本书,因为它真的是学计算机的好书] 想做创造者还是只做编码员?在于你是否学了这本书! 本书是经典的离散数学教材,为全球多所大学广为采用。本书全面而系统地介绍了离散数学的理论和方法,内容涉及数学推理、组合分析、离散结构和算法设计。全书取材广泛,除包括定义、定理的严密陈述外,还配备大量的实例和图表的说明,各种练习和题目,以及丰富的历史资料和网站资源。第5版在前四版的基础上做了大量的改进,使其成为更有效的教学工具。 本书可作为高等院校数学、计算机科学和计算机工程等专业的教材或参考书。

立即下载
离散数学第2版.pdf

科大《离散数学》课程教材,数学一定多做题,请搭配《“离散数学 学习指导与习题解析》一起使用

立即下载
离散数学及其应用 .pdf

带笔记!! 带书签目录!! 高清!! 本书是经典的离散数学教材,为全球多所大学广为采用。本书全面而系统地介绍了离散数学的理论和方法,内容涉及逻辑和证明,集合、函数、序列、求和与矩阵,计数,关系,图,树,布尔代数。全书取材广泛,除包括定义、定理的严格陈述外,还配备大量的实例和图表说明、各种练习和题目。第7版在前六版的基础上做了大量的改进,使其成为更有效的教学工具。本书可作为高等院校数学、计算机科学和计算机工程等专业的教材或参考书。

立即下载
离散数学PDF高清版

离散数学的高清扫描版,PDF格式,如果你想成为真正的编程高手,这本书就是内功心法!

立即下载