常用wap网站开发工具 手机网站制,泉州手工外发加工网,网站怎么投放广告,电子商务网站提供的主要功能有目录 前言数理逻辑命题逻辑基本概念命题等价命题蕴含对偶与范式推理理论 谓词逻辑基本概念谓词演算的等价式与蕴含式谓词演算的推理推论 集合论基本概念特殊运算运算性质包容排斥原理#xff08;容斥原理#xff09; 序偶与笛卡尔积关系关系的基础概念关系的性质复合关系和逆… 目录 前言数理逻辑命题逻辑基本概念命题等价命题蕴含对偶与范式推理理论 谓词逻辑基本概念谓词演算的等价式与蕴含式谓词演算的推理推论 集合论基本概念特殊运算运算性质包容排斥原理容斥原理 序偶与笛卡尔积关系关系的基础概念关系的性质复合关系和逆关系闭包运算集合的划分等价关系与等价类相容关系序关系 函数基本概念复合函数、特征函数与基数 代数系统代数结构基本概念半群、群、子群阿贝尔群、循环群置换群陪集和拉格朗日定理同态和同构环与域 格和布尔代数格的基本概念特殊的格 布尔代数 图论基本概念和性质特殊的图欧拉图汉密尔顿图平面图对偶图与着色树与生成树根树 前言
本篇为《离散数学》学科的个人复习笔记知识点有所偏重。 课本是上海科学技术文献出版社左孝凌版的《离散数学》。 课本中定义和定理过多文章中只记录课本中和课堂上重要常用的的定义和定理不会做深入的解释会有一些疏漏。 因为部分符号打不出来所以中间插入的图片会比较多。 已完结。如有错误烦请提出。 以下是正文
离散数学主要分为四部分
数理逻辑集合论代数系统图论
数理逻辑
古典逻辑
亚里士多德的三段论 大前提 -- 小前提 -- 结论 莱布尼兹把推理归纳为符号计算提出思维运算的思想。 布尔发明布尔代数,亦可解释为集合代数 摩根几乎同时独立地作出重要贡献 弗雷格第一个提出公理化谓语逻辑系统“概念文字”是亚里士多德以来逻辑的重大进展基本实现莱布尼兹的梦想。
数理逻辑的内容 命题逻辑 谓词逻辑 公理化集合论 递归论 证明论 命题逻辑
基本概念
定义 命题是一个能判断真假的陈述句 命题不能是疑问句、命令句、感叹句等
真值的几点说明 时间性 区域性 标准性 定义 对于一个任意给定的命题如果不能分解为更简单的命题就称为原子命题反之成为复合命题。 命题联结词 否定合取析取蕴含(条件)、等值 需要注意的有
条件蕴含当且仅当 P 为真Q 为假时P→Q 为假否则 P→Q 均为真。 条件 → 决定了哪个作为前件哪个作为后件。双条件等值当且仅当P、Q相同的时候P↔Q为真否则为假。优先级 否定 合取 析取 条件 双条件 不可兼或 不可兼析取▽ 与异或相似
例题 公式分类
赋值永远是“真”值的式子称为永真公式又称重言式。
赋值永远是“假”值的式子称为永假公式又称矛盾式。
既有真值又有假值的式子称为可满足式 命题等价
定义 如果对两个公式不论作何种指派它们的真值均相同则称是逻辑等价的亦说等价于记A⇔B. 定理 命题公式A⇔B的充要条件是A↔B为永真式。 常用等价式 除了利用真值表的方法证明两个命题公式的等价还可以采用等价代换等价置换的方法进行证明。 利用公式的等值演算可以实现以下三个基本目的 判定命题公式的基本类型即判定或证明一个命题公式为永真或永假 证明两个命题公式之间具有等值关系 对复杂的命题公式进行化简。 命题蕴含
定义 命题公式称为永真蕴含命题公式当且仅当→是一个永真式记作 注意 AB 与 A→ 的区别 其他联结词的补充
对偶与范式
对偶
范式 简单合取式又称小项真值表中小项为“真”全体小项的析取式即为主析取范式为永真式。 简单析取式又称大项真值表中大项为“假”全体大项的合取式即为主合取范式为永假式。
对于任意命题公式都存在与其等值的析取范式和合取范式。 真值表中小项为真大项为假。
例离散数学程序实验C语言——程序求主析取范式和主合取范式 输入一个逻辑表达式根据真值表法求取该表达式的主合取范式和主析取范式。
算法思路 把命题公式改为后缀表达式并把后缀处理的结果保存在结构体里对各个逻辑运算符号进行优先级的定义按照后缀表达式的方法进行赋值计算并将结果输出存储为真值表。按照真值表选择输出主合取范式和主析取范式。 此处附上实验代码仅供参考
#includestdio.h
#includestring.h
#define T 1
#define F 0
struct Stack{int top;char zf[80];
}number{-1},symbol{-1};
//number储存后缀表达式结果
//symbol 操作符栈用来保存操作符
int book[26];//记录变元元素和个数
int num0;//记录变元的个数
int alphabet_true_false[26];
int enum_result[80];
char str_copy[80];
void numbers(char str[]);
void strings(char str[]);
void reverse_polish(char s[]);
int check(int num);
void function(int num);int main()
{int i0;char str[80];printf(**************************************\n);printf(使用小写字母表示变元\n使用‘’表示合取\n使用‘|’表示析取,\n使用‘’表示条件,\n使用‘’表示双条件\n);printf(**************************************\n);strings(str);reverse_polish(str);function(num);return 0;
}void numbers(char str[]){int i,lenstrlen(str);for(i0;ilen;i){if(str[i]astr[i]z){if(book[str[i]-a]0){ book[str[i]-a]1; num; } } }
}void strings(char str[]){int i;gets(str);strcpy(str_copy,str);numbers(str);//记录变元的个数,用全局变量num储存 int lenstrlen(str);for(i0;ilen;i){switch(str[i]){case !:str[i])5;break;case :str[i])4;break;case |:str[i])3;break;case :str[i])2;break;case :str[i])1;break; }}
}void reverse_polish(char s[]){int i,lenstrlen(s);for(i0;ilen;i){if(s[i]as[i]z){//如果是命题变元就直接入number栈 number.zf[number.top]s[i]; }else if(s[i])s[i]5)){ //符号为逻辑运算符if(symbol.top-1||symbol.zf[symbol.top])){ symbol.top;symbol.zf[symbol.top]s[i];}else if(s[i]symbol.zf[symbol.top]){symbol.top;symbol.zf[symbol.top]s[i];}else{while(symbol.top!-1s[i]symbol.zf[symbol.top]){number.top;number.zf[number.top]symbol.zf[symbol.top];--symbol.top;}--i;}}else if(s[i](||s[i])){ if(s[i](){symbol.top;symbol.zf[symbol.top]s[i];}else{while(symbol.zf[symbol.top]!(){number.top;number.zf[number.top]symbol.zf[symbol.top];--symbol.top; }if(symbol.top!-1)--symbol.top;}} }while(symbol.top!-1){number.top;number.zf[number.top]symbol.zf[symbol.top];--symbol.top; }
}int check(int num){struct Stack ans{-1};int i,k0,len0,temp;for(i0;i26;i){if(book[i]){len;alphabet_true_false[i]enum_result[k];}}for(i0;inumber.top;i){if(number.zf[i]anumber.zf[i]z){ans.top;ans.zf[ans.top]alphabet_true_false[number.zf[i]-a];}else{switch(number.zf[i]){case .:ans.zf[ans.top]!ans.zf[ans.top];break;case -:ans.zf[ans.top-1]ans.zf[ans.top-1]ans.zf[ans.top];--ans.top;break;case ,:ans.zf[ans.top-1]ans.zf[ans.top-1] | ans.zf[ans.top];--ans.top;break;case :ans.zf[ans.top-1]!ans.zf[ans.top-1]|ans.zf[ans.top];--ans.top;break;case *:ans.zf[ans.top-1](!ans.zf[ans.top-1]|ans.zf[ans.top])(!ans.zf[ans.top]|ans.zf[ans.top-1]);--ans.top;}}}printf(%4d\n,ans.zf[0]); return ans.zf[0];
}void function(int num){int i,j;int conjunction_top-1,disjunction_top-1;int result_conjunction[80]{0};int result_disjunction[80]{0};for(i0;i26;i)if(book[i])printf(%4c|,ia);putchar( ),puts(str_copy);for(i0;i(1num);i){// memset(enum_result,0,num);for(j0;jnum;j){if(i(1(num-j-1))){enum_result[j]T;}else{enum_result[j]F;}printf(%4d|,enum_result[j]);}if(check(num)){result_disjunction[disjunction_top]i;}else{result_conjunction[conjunction_top]i;}}puts(\n主析取范式为);for(i0;idisjunction_top;i){printf(m%d%s,result_disjunction[i],i^disjunction_top?:);}puts(\n主合取范式为);for(i0;iconjunction_top;i){printf(M%d%s,result_conjunction[i],i^conjunction_top?|:);}
}推理理论
验证推理有效性的方法 真值表 命题演算 命题演算三要素 推理依据 推理规则 推理方法 推理规则 P 规则引入前提规则在推导的任何步骤上都可以引入前提。 T 规则引入结论规则在推导过程中如果前面有一个或多个命题公式永真蕴含命题公式 S那么就可以把公式 S 也引入到推导过程之中。 CP规则如果H1∧H2∧…∧Hn∧R S,则H1∧H2∧…∧Hn R→S 推理依据 主要指已知的逻辑等价式和逻辑蕴含式 推理方法 直接证法 间接证法反证法 和 附加前提条件证法 直接推理 由一组前提利用P规则T规则直接推演得到有效结论的方法。 条件论证附加前提条件证法 如果要证明的结论是R→S形式则可以把结论中R→S的前件R作为附加前提与给定的前提一起推出后件S即可。 反证法 要证明H1H2…HnC,只要证明 {H1H2…Hn , ﹁C} 是不相容的即可 解释要证明H1H2…HnC,只要证明 H1∧H2∧…∧H3F 即可
谓词逻辑
基本概念 在研究命题逻辑中原子命题是命题演算中最基本的单位不再对原子命题进行分解这样会产生两大缺点 1不能研究命题内部的结构成分和内部逻辑的特征 2也不可能表达两个原子命题所具有的共同特征甚至在命题逻辑中无法处理一些简单又常见的推理过程。 因此
我们可将原子命题分解成两部分个体名词代词 谓词动词。
在命题的研究中基于谓词分析的逻辑称为谓词逻辑。谓词逻辑是命题逻辑的扩充和发展。 客观世界中可以独立存在的具体或抽象对象称为个体客体,表示个体的词称为个体词。若个体词以常量的方式表示特定个体则称之为个体常量若个体词以变量的方式泛指不确定的个体则称之为个体变量。 表示个体客体特征、性质或关系的词称为谓词。 谓词与个体常量一起可以表示一个命题
由一个谓词和一些个体变元组成的表达式称为简单谓词函数。如果一个函数包含n个个体变元则称为n元简单谓词函数。
谓词函数不是命题只有当所有的个体变元都用确定的个体代入时才表示一个命题
由简单谓词函数和命题连结词组成的表达式称为复合谓词函数。
对于一个谓词函数每个个体变元都有其取值范围该取值范围称为是该个体变元的个体域论域
全称量词 “∀”几种表达式的读法 ∀ x P(x) “对所有的xx 是…” ∀ x ¬ P(x) “对所有xx 不是…” ¬∀ x P(x) “并不是对所有的xx 是…” ¬∀ x ¬ P(x) “并不是所有的xx 不是…”。
存在量词 “∃”几种表达式的读法 ∃ x P(x) “存在一个 x使 x 是…” ∃ x ¬ P(x) “存在一个 x使 x 不是…” ¬ ∃ x P(x) “不存在一个 x使 x 是…” ¬ ∃ x ¬ P(x) “不存在一个 x使 x 不是…”。 例题 约束变元 辖域紧接在量词后面括号内的谓词公式。 例如 ∀x P(x) ∃ x (P(x) ∧ Q(x)) 。 若量词后括号内为原子谓词公式则括号可以省去。 约束变元在量词的辖域内且与量词下标相同的变元。 自由变元当且仅当不受量词的约束。
对于一个公式如果量词均在全式的开头它们的作用域延伸到整个公式的末尾则该公式叫做前束范式
谓词演算的等价式与蕴含式 谓词演算的推理推论 命题推理的基本元素 推理规则P规则、T规则、CP规则 推理方法真值表法、直接证法、间接证法 推理依据等价式、蕴含式 在谓词演算中由于在前提和结论中的谓词公式常带有量词因而要使用命题演算的等价式和蕴含式需要消去和添加量词。
谓词演算的推理规则 全称指定(US)、存在指定(ES)、全称推广(UG)、存在推广(EG)。 例题
集合论
基本概念
集合定义集合是包含不同对象的一个无序的聚集。集合元素在集合里面叫做A包含a记作a ∈ A。
集合的描述有列举法一一列举几个里面的元素还有采用集合构造器叙述法。
集合相等两个集合当且仅当它们拥有相同的元素。就是说A与B是集合则A与B相等的条件是当且仅当任意X(X∈A X∈B)若A与B相等则AB 特殊运算 运算性质 包容排斥原理容斥原理 序偶与笛卡尔积
序偶有序二元组的称呼可以看作一个有顺序的集合记作A,B
序偶不同于集合的是序偶是有顺序的A,B ! B,A相当于键值对。
笛卡尔积A与B是集合那么A与B的笛卡尔积相当于A*B表示a,b,其中a∈A ,b∈B 满足分配律
关系
关系的基础概念
集合A与B的关系可以记作 A * B里面的子集属于一个关系也就是说一个从A到B的二元关系就是A * B的子集。
我们可以这么记对于一个二元关系RR里面的任意一个序偶x,y可以记作x,y∈R 或者x,y !∈ R
要么是xRy 或者 x !R y 前域在二元关系x,y E R里面由所有x组成的集合叫做前域。
值域在二元关系x,y E R里面由所有y组成的集合叫做值域。
域由前域与值域最初 相当于前域与值域的并集。
关系矩阵我们有两个有限集合X {x1,x2,x3,……,xm}Y{y1,y2,y3,……,yn}R是X到Y上的一个二元关系那么就有相应的关系矩阵M [rij]m*n
关系的性质
自反的关系R是集合X上面的二元关系如果对于每一个x ∈X,有xRx就称R是自反的。
反自反关系我们在自反的基础上面不能出现xRx的情况。
对称关系对于关系里面x,y ∈ X每当xRy就有yRx就X上面关系R是对称的。
反对称关系大概地说集合 X 上的二元关系 R 是反对称的当且仅当不存在X里的一对相异元素a, b它们相互 R-关系于彼此
传递关系对于x, y, z ∈ X每当xRy, yRz时就有xRz,就称R在X上是传递的。
关系的性质 该有的序偶不能没有 自反性应该含有所有x, x 对称性如果有x, y就应该有y, x 传递性如果有x, y和y, z就应该有x, z 该有的序偶没有就不满足 不该有的序偶不能有 反自反性不应该含有任何x, x 反对称性如果有x, y就不应该有y, x 不该有的序偶有了就不满足 从关系矩阵、关系图来判断五个性质: 1、自反的: 关系矩阵的对角线上元素全为1,关系图中每个结点均有自回路。 2、对称的: 关系矩阵是对称矩阵关系图中若两个结点之间有有向弧则必成对出现 3、反自反的: 关系矩阵中对角线元素全为0,关系图中每个结点都没有自回路。 4、反对称的: 关系矩阵以对角线对称的元素不能同时为1(但可为对称阵同时为0) 关系图中如果两个结点之间有有向弧则不能成对出现。 5、传递性: 不能明确判断只能用定义。
特殊关系的性质
空关系 反自反性对称性反对称性传递性 全域关系自反性对称性传递性 恒等关系自反性对称性传递性
复合关系和逆关系
复合关系: 定义: R是X到Y的关系S是Y到Z的关系则R和S的复合关系R°S称为R和S的复合关系表示为: RoS {x,z|x∈X且z∈Z(y∈Y ,x, y∈R且y,z ∈S)} 复合关系相当于一个个元素进行传递看是否满足传递关系。
逆关系: R是X到Y的二元关系把R中每一序偶的元素次序颠倒得到的关系称为R的逆关系记作R^c:
闭包运算 来自https://blog.csdn.net/weixin_46503355/article/details/108060144
集合的划分
把一个集合A分成若干叫做划分。
等价关系与等价类
若集合A上的关系R满足自反性对称性传递性则称R为A上的等价关系。
等价类 商集
R是A上等价关系由R的所有等价类构成的集合称为A关于R的商集。记作A/R。 即 等价关系与划分
相容关系
对于A上的关系R若R是自反的对称的则称R是相容关系。
序关系
偏序关系 A上一个关系R若R满足自反性反对称性和传递性则R是A上的一个偏序关系。记作≼ 设≼为偏序关系, 如果x, y∈≼, 则记作 x≼y, 读作 x小于或等于y 序偶A,≼ 称偏序集 在偏序集合A,≼ 中设R为非空集合A上的偏序关系, x, y∈A, 如果 x ≺ y且不存在 z ∈ \in ∈A 使得 x ≺ z ≺ y, 则称 y 盖住覆盖x. 链与反链 在偏序集合A,≼ 中在A的一个子集中如果每两个元素都是有关系的则称该子集为链。
如果子集中每两个元素是无关系的则称这个子集为反链。
全序关系 在偏序集 A,≼ 若A是一个链则称A,≼ 为全序集合或线序集合。在这种情况下二元关系≼称为全序关系或线序关系。
哈斯图
对序关系关系图的一种简化画法
① 由于序关系自反各结点都有环省去
② 由于序关系反对称且传递所以关系图中任何两个不同的结点直接不会有双向的边或通路所以省去边的箭头把向上的方向定为箭头方向
③ 由于序关系传递所以省去所有推定的边。
设A,≼为偏序集, B⊆A, y∈B. 若 ∀x(x∈B→y≼x) 成立, 则称 y 为 B 的最小元.唯一 若 ∀x(x∈B→x≼y) 成立, 则称 y 为 B 的最大元.唯一 若 ¬∃x (x∈B∧x ≺ y) 成立, 则称 y 为B的极小元.局部最大 若 ¬∃x (x∈B∧y ≺ x) 成立, 则称 y 为B的极大元.局部最大 设A, ≼为偏序集, B⊆A, y∈A. 若 ∀x(x∈B→x≼y) 成立, 则称 y 为B的上界. 若 ∀x(x∈B→y≼x) 成立, 则称 y 为B的下界. 令C{y | y为B的上界}, 则称C的最小元为B的最小上界 或 上确界. 令D{y | y为B的下界}, 则称D的最大元为B的最大下界 或 下确界. 函数
基本概念
函数 设 F 为二元关系, 若任意x∈domF 都存在唯一的y∈ranF 使 xFy 成立, 则称 F 为函数
对于函数F, 如果有 xFy, 则记作 yF(x), 并称 y 为F 在 x 的值.
f的前域就是函数f(x)的定义域记作domf X f 的值域 ranf ⊆ Y 集合Y称作 f 的共域.
满射 若 ranf Y,则称映射为满射上映射 单射入射 不同x对应不同的y 双射 若映射 f 既是满射又是入射则称这个映射是双射。
复合函数、特征函数与基数
设F, G是函数, 则F○G也是函数, 且满足 (1) dom(F○G){x|x∈domF∧F(x)∈domG} (2) 任意x∈dom(F○G)有F○G(x)F(G(x)) 反函数 设 f:A→B且f为双射则 f-1 :B→A且f-1也为双射. 若 f: A→B 为双射则 f-1: B→A 称为 f 的反函数 两个函数的复合是一个函数 特征函数 特征函数: χA:E→{0,1}, χA(x)1⟺x∈A 当 Φ⊂A⊂E时, χA是满射 基数 设A, B是集合, 如果存在着从A到B的双射函数A到B是单射和满射, 就称A和B是等势的, 记作A≈B. 如果A不与B 等势, 则记作A≉B. 也可定义为 给出两个集合两个集合的元素间一一对应则A,B等势记作A~B双射 N ≈ Z ≈ Q ≈ N×N
任何实数区间都与实数集合R等势
所有与集合A等势的集合所组成的集合叫做集合A的基数记作K[A]。
与自然数集合等势的任意集合称为可数的。
我们把有限集和可数集称为至多可数集。
可数集的任何无限子集是可数的
任一无限集必含可数子集。 任一无限集必与某一真子集等势。
若集合A到集合B存在一个入射则A基数不大于B基数即A≤B。
代数系统
代数结构
基本概念
一个集合加上若干个运算就表示一个代数系统记A,f1,f2,······。 对集合A一个An 到B的映射成为A上的n元运算。
可以用运算表来分析代数系统。
性质
封闭性
x∈A,b∈Aa*b∈A 满足性质时运算表中 运算表中每个元素都属于A。
交换律 x * y y * x 满足性质时运算表中 运算表关于主对角线对称。 分配律 x * (y ^ z) (x ^ y ) * (x ^ z) 无法从运算表中看出。 吸收律 x * (y ^ z) x x ^ (y * z) x 无法从运算表中看出。 等幂性 x * x x 满足性质时运算表中 主对角线上每一元素都与它所在行列表头元素相同。 零元 x * ⊙ ⊙右零元 ⊙ * x ⊙左零元 满足性质时运算表中 零元元素所对应的行和列中的元素都与该元素相同。
幺元单位元 x * e x;右幺元 e * x x;左幺元 满足性质时运算表中 幺元所对应的行或列都与运算表中的行和列一致。
逆元 x * y e;y是x的右逆元 y * x e;y是x的左逆元
其他定理
零元不存在逆元 在满足结合律时一个数的逆元是唯一的。 若a * a a 则a为等幂元。
半群、群、子群
广群 满足封闭性的代数系统 封闭性
半群 可结合的广群 封闭性、可结合
独异点 存在幺元的半群 封闭性、可结合、存在幺元、
群 任意元素存在逆元的独异点。 封闭性、可结合、存在幺元、两个元素间存在逆元
定理及推论 独异点在运算表中没有相同的行与列。(a-1)-1 a ;(a*b)-1 b-1 * a-1 ;有限群G中元素个数为有限群的阶数。 整数集合I,是个群。设S,*是半群、独异点或群如果S是一个有限群则必有a∈S使得a * a a。(存在等幂元)在群G,中对于任意a,b,c属于G如果ab ac 或者ba c*a 则有b c。消去律设S是一个非空集合从集合S到S的一个双射称为S的一个置换。 群的运算表G,*中的每一行或是每一列都是G的元素的一个置换。在群G,*中除了幺元e不可能有其他的等幂元。对于群G,*设存在子集S, ,那么G,中的幺元一定是S, *的幺元。对于群G,*设存在子集S, *若S{e},或者S G则称S, *是G, *的平凡子集。对于群G,B是G的非空子集若B是一个有限集那么只要运算 * 在B上封闭则B,必然是 G, *的子群。 阿贝尔群、循环群
交换群又称阿贝尔群指运算满足交换律的群。
循环群 设G, *为群若在G中有一个元素a是的G中的任意元素都由a的幂组成则称该群为循环群元素a成为循环群的生成元。
生成元可不唯一。 任一个循环群必是交换群。 若G阶数为n即 |G| n则 an e ; 其中e为幺元n是使 an e 的最小正整数称n为元素a的阶数。 置换群
暂略。
陪集和拉格朗日定理
设G, *是一个群H, *为一子群a是G中元素 aH{a * h|h∈H} H关于a的左陪集 Ha{h * a|h∈H} H关于a的右陪集 a称为陪集的代表元素
划分 每个元素非空。不存在空块 所有元素并集为G 任两个元素交集为空 等价关系 关系R满足自反、对称、传递 若x,y∈ R称x等价于y记作x~y 等价类 有等价关系的元素组成的一个集合记为[a]R a称为[a]R的代表元素 商集 A/R 以R的所有等价类作为元素的集合称为A关于R的商集 子群的指数 G对H的陪集的集合的基数即陪集的数目记为[G:H ] 若A,B表示集合
A和B的积 AB {a * b | a∈A , b∈B }
A和B的逆 A-1 {a-1 | a∈A }
拉格朗日定理 H为G的子群则 R{a,b|a∈G,b∈G且a-1 *b∈H} R是G上的一个等价关系。 对于a∈G若记[a]R{x|x∈G且a,x∈R}则[a]RaH 如果G是有限群|G|n|H|m则m|n。 | 表示整除 推论 素数阶群的子群一定是平凡群。质数阶的群不存在非平凡子群 设G,*是n阶群则对任意a∈G有ane 有限群中元素的阶能整除群的阶 素数阶群一定是循环群且每个非幺元均为生成元 设G, *是n阶有限群那么对于任意的a∈Ga的阶必是n的因子且必有an e这里e是G, *的幺元如果n为质数则G, *必为循环群。 同态和同构
设A *和B, ^ 是两个代数系统。
f是A到B的一个映射。
对任意x,y∈A有 f(x * y ) f(x) ∧ f(y) 则称f为由A *到B, ^ 的一个同态映射。 记为 A ~ B f(A), *为A,⋆的一个同态象
若f同时是双射则称f为同构映射。 同构关系是等价关系
记作A ≌ B 性质 若G *是半群则f(G) *也是半群。 若G *是独异点则f(G) *也是独异点。 若G *是群则f(G) *也是群。
同态核 设f为群G *到群G‘ *的同态映射e’为G’的幺元记 Ker(f) {x | x∈ G 且 f(x) e’ } 称Ker(f) 为同态映射f的核简称同态核。
环与域 设A, , *是一个代数系统 若满足 A,是阿贝尔群交换群A, *是半群运算* 对运算满足分配律。 则称A, ,* 为环。 为了区别环中的两个运算通常称运算为环中的加法·运算为环中的乘法。 零元 加法单位元记为0(θ) 单位元 乘法单位元记为1 负元 加法逆元记为-x 逆元 乘法逆元记为x-1
例子 R,,· 实数环 Q,,· 有理数环 I,,· 整数环 Mn(I),, · n阶整数矩阵环 Nk , k, ×k 模k整数环 Z[i], , ·(Z[i]abi,a,b∈Z,i2-1) 高斯整数环 (复数) R[x] ,, · R[x]为实数多项式 设A, , *是一个代数系统 若满足 A,是阿贝尔群交换群A, *是可交换独异点且无零因子。运算* 对运算满足分配律。 则称A, ,* 为整环。 整环中的无零因子条件等价于乘法消去律。 设A, , *是一个代数系统 若满足 A,是阿贝尔群交换群A-{⊙}, *是阿贝尔群运算* 对运算满足分配律。 则称A, ,* 为域。 性质 1.域一定是整环。 2.有限整环必是域。 3.任一个环的同态象是一个环
设V1A,,∘和V2B,⊛,◎是两环其中、∘、⊛和◎都是二元运算。 f 是从A到B的一个映射使得 对∀a, b∈A有 f(a*b)f(a)⊛f(b) f(a∘b)f(a)◎f(b) 则称f是环V1到环V2的同态映射
分类 如果f是单射、满射和双射分别称f是单同态、满同态和同构 同态像及其特性 f(A),⊛,◎是A,*,∘的同态像。 任何环的同态像是环 格和布尔代数
格的基本概念
设A, ≤ 是一个偏序集如果A中任意两个元素都有最小上界和最大下界则称A, ≤ 为格。
在格A, ≤ 中定义∨和∧两个运算a∨b表示求a和b的最小上界a∧b表示求a和b的最大下届分别称其为并运算和交运算。
全序集是一个格不是所有偏序集都是格.
性质
设A, ≤ 为格是一个格由A, ≤ 为格诱导的代数系统为A,∨,∧则A,∨,∧具有的性质有 交换律 a∨bb∨aa∧bb∧a。 结合律 a ∨b∨ca∨b∨ c a ∧b∧ca∧b∧ c。 吸收律 a ∨a∧b a a ∧a∨b a。 幂定律 a∨a a a∧a a 定理 设A,∨,∧为一个代数系统其中∨和∧都是二元运算且满足交换性、结合性、吸收性则A上存在偏序关系≤使得A,≤是一个格。 满足吸收律可推出它们一定满足幂等律。
∨和∧不一定满足分配律但是一定有分配不等式 a∨(b∧c)≤(a∨b)∧(a∨c) (a∧b)∨(a∧c)≤a∧(b∨c)
格的对偶原则 可以参考之前对对偶规则的定义对偶后用≥代替≤。
特殊的格
设A, ≤ 为格是一个格由A, ≤ 为格诱导的代数系统为A,∨,∧
分配格 若代数系统满足分配律则为分配格 链一定是分配格 有界格 格有全上界和全下界。
有补格 每个元素都有补元 补元 在有界格A, ≤ 中对于一个元素a,如果有b∈A,使得a∨b 1a∧b 01是格的上确界0是格的下确界 则b是a的补元 一个元素可以存在多个补元也可以没有补元。 布尔格 有补分配格
布尔代数
一个有补分配格称为布尔格由布尔格诱导的代数系统A,∨,∧称为布尔代数。
具有有限个元素的布尔代数叫做有限布尔代数
设A, ≤ 是一个具有全下界0的有限格则对于任何一个非零元素b至少存在一个原子a使得a小于等于b。
若a1,a2 ······an是A中满足ai≤b的所有原子则 b (a1)∨(a2)∨ ······ ∨(a n)
图论
基本概念和性质
定义 一个图是一个三元组V(G) , E(G) , ∮ 其中V(G)是一个非空的结点集合 E(G)是边集合 ∮是E到结点序偶的函数
一个结点的度数用dut(V)表示
仅由孤立结点组成的图称为零点仅由一个孤立结点构成的图称为平凡图。
定理
每个图中结点度数的总和等于边数的两倍 ∑v∈Vdeg(V) 2 | E |在任何图中度数为奇数的结点必定是偶数个含有平行边的图称为多重图不含由平行边和自环的图称为简单图。
由n个结点的无向完全图记作Kn n个结点的无向完全图Kn的边数为 n/2 * (n-1)
在有向图中,从顶点v0到顶点vn的一条路径是图中的边的序列,其中每一条边的终点是下一条边的起点。
路径与回路 —条路径中,如果同一条边不出现两次,则称此路径是简单路径。 —条路径中如果同一顶点不出现两次,则称此路径是基本路径(或叫链)。 如果路径的始点vo和终点vn相重合,即vovn ,则此路径称为回路。 没有相同边的回路称为简单回路,通过各顶点不超过一次的回路称为基本回路。 路径P中所含边的条数称为路径P的长度。 在无向图G中若结点u和结点v之间存在一条路则称u和v是连通的。 结点之间的连通性是结点集上的等价关系因此对应这个等价关系我们可以对这个图G做出一个划分把V分成非空子集V1V2,V3,······Vm使得两个结点vk和vj是连通的当且仅当它们同属一个Vi。我们把子图G(V1),G(V2),······G(Vm)称作G的连通分支把G的连通分支数目记作WG 若图G只有一个连通分支则G是连通图
如果图中任意一对顶点都是连通的则称此图是连通图否则称G是非连通图。
子图 如果V(H)⊆V(G)且E(H)⊆E(G),则称H是G的子图记作H⊆G。 生成子图 若H是G的子图且V(H)V(G)则称H是G的生成子图
最大度和最小度 Δ(G)为G的最大度 δ(G)为G的最小度
割点 设无向图GV,E为连通图若有点集V1 是V的子集使得G中删除了V1的所有结点以后所得的图不是连通图二删除除了V1的任何真子集后所得到的图仍是连通图则称V1为点割集 若一个点构成点割集则称这个点为割点。
连通度 k(G) min{| V1 | | V1 是G的点割集} 作为图G的点连通度连通度。 连通度数值上等于点割集元素个数 表示为了产生一个不连通图需要删去的点的最少数目。 完全图中 Kp 中 k(Kp) p-1 且删去p-1个结点后会产生一个平凡图。 与点割集定义类似我们定义边割集和割边也称桥
设无向图GV,E为连通图若边集E1 是E的子集使得G中删除了E1的所有边以后所得的图不是连通图二删除除了E1的任何真子集后所得到的图仍是连通图则称V1为边割集 若一条边构成边割集则称这个边为割边或桥。
同样与点连通度相似我们定义边连通度 λ(G) min{| E1 | | E1 是G的边割集} 边连通度数值上等于边割集元素个数 表示为了产生一个不连通图需要删去的边的最少数目。 对平凡图可以定义λ(G) 0此外一个不连通图也有λ(G) 0。
对于任何一个图都有 k(G) λ(G) δ(G) 一个连通无向图G中结点v是割点的充要条件是 存在两个结点u和w使得u和w的每一条路都通过v。 弱连通性和强连通性 一个有向图D(V,E)将有向图的所有的有向边替换为无向边所得到的图称为原图的基图. 如果一个有向图的基图是连通图则有向图D是弱连通的否则称D为非连通的. 若D中任意两点u,v都有从u可达v或从v可达u,则称D是单向连通的; 若D中每点u均可达其他任一点v,则称D是强连通的。 一个有向图是强连通的当且仅当G中有一个回路它至少包含每个结点一次。 在简单有向图中具有强连通性的最大图称为强分图。 具有单侧连通性的最大子图称为单侧分图。 具有弱连通性的最大子图称为弱分图。
图的矩阵表示 邻接矩阵 当vi ,adj vj 时a i*j 1 当vi nadj vj 时或 ij 时a i*j 0 adj表示联结nadj表示不联结 对于无向图邻接矩阵是对称的。 定理 设A(G)是图G的邻接矩阵则(A(G))l中的i行j列元素ali*j 等于G中联结vi和vj的长度为l的路的数目 可达性矩阵 当vi 至少存在一条路到达 vj 时a i*j 1 当vi 不存在一条路到达 vj 时或 ij 时a i*j 0 完全关联矩阵和关联矩阵
关联矩阵M(G)是由 G的结点 和G的边集构成的 当vi 关联 ej 时a i*j 1 当vi 不关联 ej 时a i*j 0 从关联矩阵中可以得到
图中每一边关联两个结点故M(G)的每一列只有两个1.每一行元素的和数是对应结点的度数。一行中元素全为0其对应的结点为孤立节点。两个平行边其对应的两列相同。同一个图当结点或边的编序不同时其对应的M(G)仅有行序和列序的不同。
完全关联矩阵 关联矩阵M(G)是由 G的结点 和G的边集构成的 当vi 是 ej起点 时a i*j 1 当vi 是 ej终点 时a i*j -1 当vi 不关联 ej 时a i*j 0 如果一个连通图G有 r 个结点则其完全关联矩阵M(G)的秩为r-1 即 rank M(G) r-1。
特殊的图
欧拉图
可见 哥尼斯堡七桥问题
给定无孤立节点图G若存在一条路经过图中每边一次且仅一次该条路称为欧拉路。 若存在一条回路经过图中每条边一次且仅一次则称为回路为欧拉回路。 具有欧拉回路的图称作欧拉路。
无向图G具有一条欧拉路当且仅当G是连通的且由零个或两个奇数度结点。
对于有向图 给定有向图G通过图中每边一次且仅一次的一条单向路(回路)称作单向欧拉路(回路)。 有向图G具有一条单向欧拉回路当且仅当是连通的且每个结点入度等于出度。 一个有向图G具有单向欧拉路当且仅当它是连通的而且除两个结点外每个结点的入度等于出度但这两个结点中一个结点的入度比出度大1另一个结点的入度比出度小1。 汉密尔顿图
给定图G若存在一条路经过图中的每个结点恰好一次这条路称作汉密尔顿路。 若存在一条回路经过图中的每个结点恰好一次这条回路称作汉密尔顿回路。
具有汉密尔顿回路的图称作汉密尔顿图。
若图GVE具有汉密尔顿回路则对于结点集v的每个非空子集S均有 W(G-S)≤|S| 成立。 其中W(G-S)是G-S中连通分支数。
汉密尔顿图的判定
虽然汉密尔顿回路问题与欧拉回路问题在形式上极为相似但对图G是否存在汉密尔顿回路还无充要的判别准则。下面我们给出一个无向图具有汉密尔顿路的充分条件。
若G中每一对结点度数之和大于等于n-1则G中存在一条汉密尔顿路。若G中每一对结点度数之和大于等于n则G中催在一条汉密尔顿回路。
闭包 给定G{V,E}有n个结点若将G中度数之和至少为n的非邻接结点点连接起来得到G‘重复这一步骤则得到了G的闭包记作C(G)
平面图
平面图的定义 在一个平面画出一个图如果图的每条边都互不相交则称这个图为平面图。
边 连通平面图G由图中的边所包围的区域在区域内既无节点也无边这样的区域叫做面。
一个平面图面的次数之和等于其边数的2倍
欧拉公式
设一个连通的平面图v个结点e个边和r个面则满足
v-er 2
性质及定理 设G是连通简单平面图 则满足 e ≤ 3v - 6 给定两个图G1,G2如果它们是同构的或者通过反复插入或出去度数为2的结点后使得G1和G2同构则称两图在2度结点内同构。 库拉图斯基定理: 一个图是平面图当且仅当它不包含与K3.3或K5 同构的子图 也就是说如果 K3,3 或 K5 可以通过不断细分变成这副图则这幅图是非平面图。
对偶图与着色
本处图片及叙述摘自 https://blog.csdn.net/qq_37868325/article/details/83867178 对于每一个平面图 都有与其相对应的对偶图. 我们假设上面的例图是图G 与其对应的对偶图G* 那么对于G来说 G上面的每一个点 对应的是G里面的每一个面. 比如说下面就是G*. 上面的点就是对偶图G里的点. 那么关于对偶图G里的边呢 ? 对于G中本来的每条边e 他是两个面(比如说面f1和f2)的交边 那么在对偶图里 我们对这两个面(f1 f2)所映射在G里的点连线(f1* 连向f2*). 如果f1 f2(比如说G中5 6这条边 边的两侧都是同一个面 那我们就建一条回边. 图就长这样(回边在5 6那里).
自对偶图 如果图G的对偶图G‘同构于G则称图G是自对偶图。
性质及定理
对于n个结点的完全图Kn 有x(Kn) n;设G为一个至少具有三个结点的连通平面图则G中必定有一个节点u使得 deg(u) ≤ 5任意平面图G最多是5-色的若G是自对偶的则e 2v-2 教材P321课后题
树与生成树
定义 一个连通且无回路的无向图称为树。 书中度数为1的结点称为树叶。 度数大于1 的结点称为分结点或者内点。 一个无回路的无向图称为森林它的每个连通分支是树。
定理及性质
给定图T以下关于树的定义是等价的 无回路的连通图无回路且e v-1其中e为边数v为结点数。连通且e v-1无回路但增加一条新边得到一个且仅有一个回路连通但山区任一条边后不连通每一对结点之间有一条且仅有一条路 任一棵树中至少有两片树叶若图G的生成子图是一棵树则称该树为G的生成树。 设G有一条生成树T则T的边称作树枝 图G的不在生成树中的边称作弦 所有弦的集合称作生成树T的补 连通图至少有一棵生成树一条回路和任何一棵生成树的补至少有一条公共边一个边割集和任何生成树的补至少有一条公共边。在图G的所有生成树中树权最小的那棵生成树称作最小生成树。 求最小生成树的两种算法可见 数据结构笔记中的算法数据结构笔记
根树
定义 如果一个有向图在不考虑边的方向是是一棵树那么这个有向图称为有向树。 一棵有向树如果恰有一个结点的入度为0 其余所有结点的入度都为1则称为根树。 入度为0的结点称为根出度为0的结点称为叶出度不为0的结点叫做分枝点或者内点。 根树包含一个或多个结点这些节点中摸一个称为根其他所有结点都被分成有限个子根树。 在根树中若每一个结点的出度小于或等于m则称这个树为m叉树。 如果每一个结点的出度恰好等于m或0则称这棵树为完全m叉树若其所有树叶层次相同成为正则m叉树。当m2时称为二叉树。 在根树中一个结点的通路长度就是从树根到此结点的通路中的边数。我们把分枝点的通路长度称为内部通路长度。树叶的通路长度叫做外部通路长度。
性质及定理
设有完全m叉树其树叶数为t分枝点数为i则 (m-1) i t-1 若完全二叉树中有n个分枝点且内部通路长度的总和为 I 外部通路长度的总和为 E 则 E I 2n 在带权二叉树中若带权为wi的树叶其通路长度为L(wi)我们把w(T) ∑i1t wiL(wi) 称为该带权二叉树的权。 在所有带权的w1,w2,······wi的二叉树中w(T)最小的那棵树称为最优树设T为带权w1≤ w2,≤···≤wi的最优树则 带权w1,w2的树叶vw1vw2是兄弟。以树叶vw1vw2为儿子的分枝点其通路长度最长。 设T为带权w1≤ w2,≤···≤wi的最优树若将以带权w1和w2的树叶为儿子的分枝点改为带权w1w2的树叶得到一棵新树T‘则T’也是最优树。
前缀码问题 哈夫曼编码可见数据结构笔记哈夫曼编码部分数据结构笔记
