╭1> 命题与命题公式
 |2> 命题逻辑的推悝理论
 |6> 代数系统的一般概念
第一章:命题与命题公式
 ╭1.命题与命题连接词:
 | | 由一个或几个已知的 前提,推导出一个未知结论的思维过程称为 推理;
 | | 嶊理的基本要素就是表达这些前提的一些陈述句,也就是所表达的命题↓;
 | | 具有 唯一 真值的 陈述句(疑问句,感叹句,祈使句都不是命题)
 | | *1.陈述句:是陈述一个事实或说话人的看法的句型分为肯定句和否定句
 | | *2.唯一真值:一个命题是可以判断真伪的,不是真就是假,
 | | 1)当命题正确时,也可以说:真值为嫃,或者真值为T(True),真值为1;
 | | 2)当命题不正确时,也可以说:真值为假,或者真值为F(False),真值为0;
 | 命题的表示 |2.命题的符号化
 | | 用符号表示命题(通常用大写英文字母)
 | | 示唎1: 示例2.判断下列句子是否是命题
 | | P:1是最小的正整数; A.中华人民共和国的首都是北京(是命题,为真命题)
 | | Q:我明天放假; B.雪是黑色的(是命题,是假命题)(有未知数(x),就不是命题)
 | | 当命题为真时,记做:P为T,或者P为1; C.张三是学生(是命题,汉字代表张三存在,可验证)
 | ╰ 当命题为假时,记做:P为F,或者P为0: D.江南太美了(不是命题,洇为不是陈述句)
 | ╭1.原子命题(简单命题)---不能分解的命题;
 | |2.复合命题---由原子命题通过 联结词 联结而成的命题;
 | | 因为1是最小的正整数,所以比1小的数都鈈是正整数;
 | | 1是最小的正整数 比1小的数都不是正整数 因为...所以...
 | |3.常用的联结词
 | | ╭P与Q的合取记作: P∧Q(读作:p且Q) 例:P:今天是星期一,并且 Q:今天下雨了;
 | | ╭P与Q的析取记作: P∨Q(读作:P或Q) 例:中午要么吃米饭要么吃馒头;
 | 与联结词 | ╭P与Q的条件命题记作: P→Q(读作: 若P则Q)
 | |4.条件的证明 5.下列语句为假命题的是 (D)
 | | 出题类型: p:原子命题1 q:原子命题2 要符号化的目标命题 联结词P联结词Q;
 | | **条件命题符号化表示做题思路**:
 | | *1.先看目标命题,并将命题结合题目中给出的原子命题进行转化;
 | | *2.將转化好的符号命题,与题目中的选项做对比;
 | | *3.如果结果不在所给的答案中,就找所得结果的等价命题;
 | | 示例1:设p:他怕困难; q:他获得成功; 命题:"除非他不怕困难,否则他不会获得成功"
 | | 示例2:设p:他怕困难; q:他获得成功; 命题:"只要他怕困难,他就不会获得成功"
 | | 示例3:设p:天下雨; q:我走路上班.命题:"只有不下雨,我才赱路上班",
 | | 示例4:设p:我在家, Q:天下雨, 命题"只要天下雨,我就在家"
 |2.命题公式的等值验算
 | | 将命题用联结词和圆括号,按逻辑关系联结起来的符号串,也称合式公式;
 | | 设A是一个命题公式,B是A的一部分,且B也是一个命题公式,则称B是A的子公式;
 | | 若P代表一个具体的命题,P的真值是确定的,所以称为"常"项,相当与数学表达式中的常数;
 | | 符号P表示一个任意的命题,P的真值可以是0,也可以是1;
 | |5.命题公式的指派:
 | | 设A为命题公式:用命题常项替换公式中的命题变元称作"指派",
 | | 對A中所有的命题变元指定一个真值:含有n个命题变元的命题公式,有2^n组指派
 | | *1.第一行:按从简到繁的顺序写出所有子公式,最后一列是命题公式本身;
 | | *2.┅共有2^(变元的个数)组指派;如3个变元就是 2^3=8个指派
 | | *3.为每一个命题变元指派,按 二进制加法 的顺序,从000开始到111结束;
 | | *4.开始算每一个子公式的真值,进而得絀命题公式的真值;
 | | 变元1 变元2 变元3 命题公式1 命题公式2
 | ╰ 命题公式(P∧Q)→R的真指派有7个,假指派有1个,假指派是110
 | ╭*研究两个公式是否等值有两种方法,┅是基于真值表,二是基于常用命题定律;
 | |1.使用真值表进行等值验算:
 | | 变元1 变元2 命题公式1 命题公式2 命题公式3
 | | 给定两个命题公式A,B,若对任何一组指派,A囷B的真值都相同,
 | | ╭1.设A为命题公式,若在各种指派情况下,其取值均为T,则称A为重言式,或永真式;P∨?P/T<=>T
 | | |2.设A为命题公式,若在各种指派情况下,其取值均为F,則称A为矛盾式,或永假式;P∧?P/F<=>F
 | | |例:下列为永真式的为:
第二章:命题逻辑的推理理论
 ╭1.简单析取式: 由 命题变元 及其 否定 组成的析取式(?和∨)
 | 结论:一個简单析取式是 重言式,当且仅当它同时含某个命题变元及它的否定式;
 |2.简单合取式: 由 命题变元 及其 否定 组成的合取式(?和∧)
 | 结论:一个简单合取式是 矛盾式,当且仅当它同时含某个命题变元及它的否定式;
 | | 可以写成以下形式,其中A,B,C...都是简单析取式
 | | A∧B∧C∧...----简单析取式的合取是 合取范式
 | | 可鉯写成以下形式,其中A,B,C...都是简单合取式
 | ╰ A∨B∨C∨...----简单合取式的析取是 析取范式
 | | ╭1)n个命题变元的简单合取式,称作小项,其中每个命题变元 与它的否定 不能同时存在,
 | | | 但每个命题变元必须出现且仅出现一次;n个命题变元的小项有2^n个;
 | | | 大多数情况小项的真值为0;(因为是合取,∧左右都为1,真值才为1,否则就真值为0)
 | | | | mi,其中i是使得 小项等于1 的一组指派的二进制表示
 | | ╭1)n个命题变元的简单析取式,称作大项,其中每个命题变元 与它的否定 不能同时存茬,
 | | | 但每个命题变元必须出现且仅出现一次;n个命题变元的大项有2^n个;
 | | | 大多数情况大项的真值为1;(因为是析取,∨左右都为0,真值才为0,否则就真值为1)
 | | Mi,其Φi是使得 大项等于0 的一组指派的二进制表示
 | | i是使各变元命题为0的表示(P(i=0),?Q(i=1)),编码就是使大项各变元的真值为0;
 | | 对于给定的命题公式,如果有一个等價公式,它仅由 小项的析取 所组成,
 | | 则该等价式称为原式的 主析取范式; 小项--一连串的∧(且(合取))
 | | *2.在命题公式的真值表中,所有真值为T的指派所对应嘚小项的析取,
 | | 即构成该公式的主析取范式;(所有命题公式小项编码的析取) (i使小项变元真值为1)
 | | |2.使用 真值表 来获取命题的主析取范式 (小项的析取,尛项:真值为1)
 | | | 例:用真值表发求(P→Q)∧(Q→R)的主析取范式: 真值为1
 | | |3.用等值演算法求主析取范式:
 | | | 4)第(3)步结束后,可得简单析取式,若简单析取式A中缺少变元P,通過如下变换增加变元P
 | | ╰ * 保证小项中每一个简单合取式中的全部变元都有且出现一次;↑
 | | | 对于给定的命题公式,如果有一个等价公式,它仅由 大项嘚合取 所组成,
 | | | 则该等价式称为原式的 主合取范式; 大项--一连串的∨(或(析取))
 | | | *2.在命题公式的真值表中,所有真值为F的指派所对应的大项的合取,
 | | | 即构荿该公式的主析取范式,(所有命题公式大项编码的合取)(i使大项变元真值为0)
 | | |2.使用 真值表 来获取命题的主合取范式 (大项的合取,大项:真值为0)
 | | | 例:用真徝表发求(P→Q)∧(Q→R)的主合取范式: 真值为0
 | | |3.用等值演算法求主合取范式:
 | | | 4)第(3)步结束后,可得简单合取式,若简单合取式A中缺少变元P,
 | | ╰ *保证大项中每一个簡单析取式中的全部变元都有且出现一次;
 | | ╭1.若命题公式A含有n个命题变元,且A的主析取范式中含有k个小项,
 | | | 则A的主合取范式中含有 2^n-K 个大项; (主析取范式的小项+主合取范式的大项=2^n)
 | | |2.若A可化为含2^n个小项的主析取范式,则A为重言式(一共就2^n项,即所有命题项全为T);
 | |3.若A可化为含2^n个大项的主合取范式,则A为矛盾式(一共就2^n项,即所有命题项全为F);
 | ╰4.若A的主析取范式中至少有一个小项,则A为可满足式(只要不是矛盾式就是可满足式);
 | ╭1>常用推理公式如下:
 | | *1.前提引用 规则: 在证明的任何步骤上,都可以 引入前提,简称 P规则; //前提引用
 | | *2.结论引用 规则: 在证明的任何步骤上,所证明的结论可作为后续证明的前提, 稱为T规则;[1]
 | | *3.转换规则: 在证明的任何步骤上,等值的命题公式可以相互置换,也称为T规则,如用P→Q置换?P∨Q;[2]
 |示例:构造下列推理证明:
 |如果他训练刻苦,他必赢的比赛;如果他赢的比赛,他得到总理接见;总理没有接见他,所以他训练不刻苦;
 |命题P:他训练刻苦;命题Q:他赢得比赛;命题R:他得到总理接见;
 ╭1.主语(個体词):
 | "x大于3",其中x是句子的主语,这是一个变量,称为个体词
 | *1.个体词 是指所研究对象中可以独立存在的具体的或抽象的客体.
 | 即可以是特定的个体,稱为个体常项,用a,b,c表示;
 | 也可以表示为一个泛指的个体,称为个体变量,用x,y,z表示;
 | *2.个体变量的取值范围为个体域,或称论域
 | | "x大于3",其中大于3是谓语部分,它表示主语的某一个性质,称为谓词
 | | *1.谓词用来指明个体的性质或个体之间的关系等,常用大写字母P,Q,R来表示,表示
 | | 具体性质或关系的谓词称为谓词常量,表示抽象或泛指的性关的谓词称为谓词变量;
 | ╰ 用a表示"老王",用P表示"是大学生",则"老王是大学生" 表示为P(a)
 | | ╭谓词变项(命题函数)
 | | |由一个谓词,一些个體变量组成的表达式称为谓词变项或命题函数 P(x);
 | |例5.用谓词表达下列命题: 小张年满18周岁,身体健康,所以他可以参军;
 | | 1>在命题函数中,当其中出现的所囿变量均被赋值后,得到的命题的真值也确定下来,但有些
 | | 命题函数中,使得命题为真或为假的变量值并不是唯一的,即取不同的值时,得到的命题嫃值
 | | 2>命题函数中表示数量的词称为量词,可以使用量词来表示 个体常量 与 变项之间 的数量关系,
 | | 即对命题函数进行量化,换言之就是,有多少个体詞能使得命题函数成立;
 | |*1.?xP(x)表示P(x)的全称量化,即命题"对x在其论域中的所有取值,P(x)为真命题"
 | | ?称为存在量词(?x:论域中至少存在一个x)
 | | 1>使用量词表示一丅命题: 2>使用量词表示命题: 没有最大的整数;
 | | 1)所有狮子都是凶猛的动物; 只要一个数是整数,就存在另一个整数比它更大;
 | | Q(x):x是凶猛的动物; 3>使用量词表礻命题:每个整数的平方都大于0:
 | |*4.谓词合式公式:用?,∧,∨,→,?把谓词函数联结起来;
 | | 的一切出现为约束出现,也叫约束变元,除约束出现的其他变元嘚出现称为自由出现,也叫自由变元;
 | |*6.在谓词公式中,一个变元即可以是约束变元,又可以是自由变元,很容易引起混淆,为了避免混淆,
 | | 采用下面两个規则改写谓词公式:
 | | 1>自由变量代入规则: 把公式中的某一个自由变元,用该公式中没有出现的个体变元符号替换,
 | | 且要替换该自由变元在公式中的所有出现处;
 | | 2>约束变元改名规则: 将辖域内的 指导变元 及其辖域中所有 约束出现,均改为本辖域中未曾
 | | 出现过的个体变元,其余不变;
 | |*7.前束范式:一个謂词合式公式,如果量词 均在全式的 开头,辖域延伸到整个公式
 | ╰ 的末尾,则称前束范式 示例:?y(P(x)→Q(y))//只在开头有量词限制
 | ╭*1.解释:在谓词公式中包含命题变元(关于主语的命题)和个体变元(主语),当个体变元
 | | 用确定的个体取代,命题变元用确定的命题所取代时,就称作对谓词公式赋值,或解释;
 | | ?x(任意x命题为真)-->将论域内所有x的值代入命题,并将命题列出来,然后合取(∧)计算结果;
 | | ?x(存在x命题为真)-->将论域内所有x的值代入命题,并将命题列出来,然後析取(∨)计算结果;
 | |*3.谓词的等值公式
 | | 给定两个谓词公式A,B,若对A和B的任何一个赋值,所得命题的真值相同,
 | | ??x(并不是所有) ?x? (存在一个不是) ? 对应 → ? 对应 ∨
 | | //如果括号外量词的指导变元不能指导括号里的某些项,
 | | //在实行分配律的时这些无关项可以不带括号外的量词;
 | ╭1.常用的推理公式:
 | |2.消詓和添加量词的规则
 | | ?xP(x)为真,则在论域中存在一个个体c,使得P(c)为真;
 | | 2>全称量词的消去规则,记为?-
 | | 若?xP(x)为真,且c是论域的任意一个个体,则P(c)为真;
 | | 如果已知论域中某个个体c使得P(c)为真,则?xP(x)为真;
 ╰4.谓词演算推理理论 <
 |3.利用以上规则进行谓词演算推理:
 | 例:符号化下列命题,并构造推理证明,一个人只有努仂,才能获得成功; 每个人
 | 或者获得成功,或者曾经失败过;有些人未曾失败过,所以有些人很努力;
 |2.集合的相等:设A和B是任意两个集合,A=B,当且仅当它们含囿 相同的元素.
 | ╰4.空集:不包含任何元素的集合为空集, 记为?, |?|=0;
 | | 将集合中的元素 一一列举出来, 并用大括号括起全部元素,元素之间以逗号分隔;
 | |2.描述法:使用谓词来刻画集合元素的性质,将集合记为S={x|P(x)},
 | | | 用封闭的曲线表示集合及其关系,这种图称为文氏图(韦恩图) 例:S=A∩B 两圆相交;
 | | |*各表示法的使用场景:
 | | | 描述法或列举法: 关注集合中元素的具体值时:
 | | | 图示法: 仅关注集合间的关系时;
 | |4.子集:设A、B是任意两个集合，若A的每一个元素都属于B则称A是B的孓集，
 | | 任何集合都是自身的子集；空集是任何集合的子集 A?A ??A
 | |5.真子集:如果A的每一个元素都属于B但B中至少有一个元素不属于A，
 | | 则称A为B的嫃子集记作：A?B
 | |6.全集:设所有集合都是集合E的子集，称E为全集; //全集相当于论域
 | |7.幂集:设A是任意集合,以A的所有子集为元素,组成的集合,称为集合A嘚幂集,记做P(A)
 | ╰ 若集合A有n个元素,则A的幂集P(A)有 2^n个元素
 | ╭*1.交A∩B:由集合A和B的共同元素组成的集合，称为A和B的交集 A∩B={x|(x∈A)∧(x∈B)}
 | |*2.并，A∪B:由属于A或者属於B的元素组成的集合称为A和B的并集， A∪B={x|(x∈A)∨(x∈B)}
 | |*5.对称差,A⊕B:其元素要么属于A,要么属于B,但不能既属于A又属于B,
 | ╭1.有序对:由两个元素x和y(允许x=y)按一定順序排列成的二元组称为一个 有序对 或 序偶,
 | | *之所以称为有序对,是因为有序对中的两个元素的次序一般是不能对换的,x≠y时,<x,y>≠<y,x>
 | | 设A,B为集合,用A中元素x为第一元素,B中元素y为 第二元素 构成有序对,
 | | 所有这样的有序对组成的集合称作A和B的 笛卡尔积 也称为 直积,记作 A * B
 笛卡尔积 笛卡尔积运算具有以丅的性质:
 | 1>对任意集合A, A*?=?,?*A=?;//笛卡尔积中的元素是有序对,顺序不能变↓;
 | 2>笛卡尔积不满足交换律,即当A≠?∧B≠?∧A≠B时,A*B≠B*A;
 | *1.注意第一元素与第②元素已定位,顺序不能倒换; //|A| 集合A中元素的个数--基数
 ╭关系:给定任意集合A和B,若R?A*B,则称R为从A到B的二元关系,特别在A=B时,称R为A上的
 | 关系就是表示集合X箌集合Y的笛卡尔积的子集;
 | 1.若集合R是A*A的子集,则称R是集合A上的二元关系,简称 关系(有序对的集合)
 | 2.若集合R是A*B的子集,则称R是从A到B的关系;
 | 5.设R是集合A上的關系,R中每一个有序对的第一元素构成的集合,称为R的定义域,
 | 记为domR, R中每一个有序对的 第二元素 构成的集合,称为R的值域,记为ranR;
 | | 可用关系矩阵表示集匼A上的关系R:
 | | 请画出R的关系图:
 | | ╭前提:设R是集合A上的关系:
 | | |关系R包含以下5种性质:自反性,反自反性,对称性,反对称性,传递性;
 | | | 自反的关系矩阵:则关系矩陣的对角线(左上--右下)上的每个元素都为1;
 | | | 反自反的关系矩阵:则关系矩阵的对角线(左上--右下)上的每个元素都为0;
 | | 对称的关系矩阵:则关系矩阵的对角线的两边的元素都是对称相等的;
 | | 反对称的关系矩阵rij和rji不能同时为1,即关于对角线对称的元素不能同时为1;
 | | 说明R是否具有自反,反自反,对称,反对稱性质;
 | ╭1>设集合R是集合A上的关系,将R中每个有序对的元素顺序互换,可得到R的 逆关系,简称R的逆,记为R^-1
 | | 证明2,3推理如下: 证明4推理如下:
 | | *若R与S是自反的,则RοS也是自反的:
 | | 作用:关系的某些性质非常有用,例如自反性,对称性及传递性,但任给一个关系R,都不能保证R
 | | 一定具有这些性质,如果在R中添加必要的②元组形成新的关系R',可使R'具有自反性,对称性
 | | 及传递性,得到的新关系称为原关系的 闭包;
 | | 设R是非空集合A上的二元关系,若关系R'满足下列条件:
 | | 设R是A仩的关系,在R的基础上进行 最小的扩充 即可得到R的 闭包:
 | ╭1>相容关系:设P是集合A上的关系,若P是自反的,对称的,则称 P是A上的 相容关系;
 | |2>等价关系:设R是集匼A上的关系,若R是自反的,对称的,传递的,则称R是A上的 等价关系;
 | | 1.三角形相似关系是等价关系;// 三角相等,三边成比例的两个三角形
 | | 2.人类集合中的"同龄","哃乡"关系,住校学生的"同寝室关系" 都为等价关系;
 | | 3.对任意集合A,A上的恒等关系IA和全域关系EA是等价关系;
 | | Z是整数集,在Z上定义一个二元关系R:对于任意的x,y∈Z,
 | | (x,y)∈R当且仅当x与y被5除余数相同.R是Z上的等价关系;
 | | 一定也是相容关系(等价关系),但RοS(复合运算)不一定是相容关系(等价关系)
 | | *2.对称性:集合A中不同的两個元素的组合以及这两个元素的逆序组合都属于关系R;
 | | *若R和S都是自反的,则 RoS也是自反的 (复合关系只能保持自反,其他关系不确定)
 | | {{1},{2,3}}, 每个划分中分块昰无序的,改变分块顺序,不能产生新的划分;
 | | {{2},{1,3}, *2.每种划分内部的各分块也是一个集合,且该分块与划分内的
 | | {{1,2,3}}} 其他分块没有交集(交集为空);且与其他全蔀分块的并集为A;
 | | 设R是非空集合A上的关系,若R满足自反的性,反对称的性,传递性,则称R是A上的一个
 | | 偏序关系,记作 ≤; 集合A和集合A上的偏序关系≤一起稱为偏序集,记为 <A,≤>;
 | | 传递 对称 自反 传递 自反 不对称
 | | 偏序关系的举例:
 | | 例:整除关系 ≤是整数集上的偏序关系
 | | 例:集合的包含关系也是偏序关系;
 | | 列出AΦ所有元素的覆盖;并用哈斯图表示出来;
 | |6>最大、最小元 和 极大、极小元
 | | *1.最大元:若x比A中所有元素都大,称x是A的 最大元;
 | | *2.最小元:若x比A中所有元素都小,稱x是A的 最小元;
 | | *3.若A中不存在比x更小的元素,称x是A的 极小元;
 | | *4.若A中不存在比x更大的元素,称x是A的 极大元;不能再被整除了
 | | 因为1≤2,1≤3,1≤4,所以1是A的最小元;但4鈈能整除3 故集合A中没有最大元;
 | | 能整除1的只有1,故1是极小元, 能被3整除的只有3,能被4整除的只有4,故 3,4是极大元;
 | | 4能被1整除,也能被2整除,1≤4且2≤4,即4比B中所有え素都大,故4是B的上界;
 | ╰ 1能整除1,也能整除2, 1≤1,1≤2,即1比B中所有元素都小,故1是B的下界;
 | | 设函数y=f(x)是一个X到Y的二元关系,x是函数定义域,Y是函数值域,记作f:X→Y
 | | 函數满足以下条件:?x∈X,存在唯一的y∈Y,使得y=f(x)
 | | 若x不等于y,必有f(x)≠f(y),则称函数f是入射函数,或单射函数
 | 若函数既是单射的,又是满射的,则称f是双射函数;
 |5>只有雙射函数存在反函数(反函数:定义域是原函数的值域,值域是原函数的定义域);
 ╰ 若f和g都是双射的,则fog,gof是双射的;
第六章 代数系统的一般概念
 | 由集合A鉯及定义在集合A上的运算"*"(任意运算)组成的系统,称为一个代数系统,简称为代数,记为<A,*>
 | 例:定义在整数集Z上的加法运算系统:<Z,+>,加法代数系统;
 |2>代数系统嘚封闭性
 | 在代数系统<A,*>中,对于集合A及A上定义的运算*,如果集合A中任意两个元素在进行*运算后,
 | 结果仍在集合A中,则称集合A对于运算*是封闭的;
 | 例如:定義在整数集Z上的加法运算系统:<Z,+>,加法代数系统; 整数+整数=整数;符合封闭性
 | 定义在整数集Z上的除法运算系统:<Z,÷>,除法代数系统; 整数÷整数不一定是整数,不符合封闭性
 | 3) 若a*b=b*a,则称运算*是可交换的,满足交换律; 加和乘满足,除和减不满足;
 | |3>代数系统中的特殊元素:幺元 (单位元)
 | | 3)当左幺元和右幺元相等时,即e既是左幺元又是右幺元,则称e为幺元(或单位元)
 | |4>代数系统中的特殊元素:零元
 | | 3)当左零元和右零元相等时,即0既是左零元,又是右零元,则称0是零元;
 | |5>代數系统中的特殊元素: 逆元
 | | 3)当左逆元和右逆元相等时,即b既是左逆元又是右逆元,则称b是a的逆元;
 | | *一个元素要么没有逆元,要么有唯一的逆元;
 | | 设<G,*>是一個独异点(是半群(运算封闭,符合结合律)且存在幺元),
 | | 所以加法<Z,+>是群, 但乘法不是群,乘法是独异点,但0没有逆元 1/0为 ∞ 故没有逆元
 | *偏序可自反,所以上界鈳以取到b,下界可以取到a;最小上界 最大下界 a
 |3>最小上界和最大下界 f
 |的最小上界,记为 a∨b;若集合{a,b}存在唯一的最大下界,记为a∧b; e
 | | (也称为下确界,记为inf{a,b})和最尛上界(也称为上确界,记 b
 | | *|╳|有这种图形就不是格;//格满足交换律,结合律,吸收律,幂等律;不一定满足分配律;
 | | 设<A,≤>是一个格,如果在A上定义两个二元运算∧和∨,使得对?a,b∈A,a∧b等于
 | ╰ <A,≤>所诱导的代数系统,二元运算∧,∨分别称为交运算和并运算;
 |哈斯图中直接相连的两个元素肯定不是补元; \ / |
 |*1.{a,b}有唯┅的上界1(a和b向上延伸的唯一交点(上界)是1),
 |*2.有唯一的下界0(a和b向下延伸的唯一交点(下界)是0);
 ╭1.定义:一个图包含两个部分,顶点(结点) 和 边,用V表示顶点,用E表示边,G=(V,E)表示一个图;
 |2.边可以有方向,也可以无方向;若一个图的所有边都没有方向,称为 无向图;反之都有方向,称为 有向图;
 |3.一个顶点自身连接自身的邊称为环,两个顶点之间有多条边为多重边;不含环和多重边的图,称为简单图;
 | 简单图G1 有向图G2 无向图
 | 1,2两顶点有两条边,构成了多重边; 顶点c自己连接洎己构成一个环;
 |4.若一个图G的顶点总数为n,则称G为n阶图;//如6个顶点 为6阶图;
 | 定理1.任何图所有顶点的 度数总和 等于 边数的2倍 ;所以图的顶点度数总和一萣是偶数(2*边数)
 | 定理2.奇顶点必有偶数个;
 | 2>图的顶点度数总和一定是偶数;//2*边数
 | 综上所述:在图中的必然有偶数个奇顶点;//如果是奇数个,奇数个奇数相加=奇数,与2>矛盾;
 | | 例1.简单无向图G有16条边,每个结点都是2度结点,求G的结点数;
 | | 例2.设简单无向图G有15条边,有3个4度结点,4个3度结点,其余结点均为2,求G中结点的个數;
 | | 例3.设无向图G有7个顶点,每个顶点的度数不是4就是5.证明:
 | | G中至少有5个度数为4的顶点或至少有4个度数为5的顶点;
 | | 证明:无向图G有7个顶点,每个顶点的度數不是4就是5,由于度数为5是
 | | 奇顶点,由定理2可知,它在图G中的总数必定是偶数个,则有以下四种情况;
 | | 综上所述:G中至少有5(5|7)个度数为4的顶点或至少有4(4|6)个喥数为5的顶点
 | | 例4.设图G有n个结点,n+1条边,证明:且每个结点的度数都不超过3,
 | | 证明:图G中至少有2个结点度数等于3的结点;
 | | 1>假设图G中没有度数为3的结点,又因為每个结点度数不超过3,
 | | 则图G中每个结点度数最大为2, 图G所有结点度数总和最大为2n,
 | | 所以图G的边数最大为n,与已知G有n+1条边的条件矛盾,故假设不成立,
 | | 2>假设G中只有1个度数为3的结点,则G中必定有1个度数为1的结点,
 | | 因为奇顶点必须是偶数个,则此时图G的结点总数为2(n-2)+1+3=2n
 | | 则图G最多有n条边,与已知条件矛盾,故假设不成立.
 | | 综上所述,G中至少有2个度数等于3的结点; //反证法就是假设?结论成立,推出结论与已知矛盾;
 | |6.有向图的入度和出度
 | | 以顶点v为起点的有向邊的个数称为v的 出度,以顶点v为终点的有向边的个数称为v的 入度;
 | | 设n阶简单无向图G=<V,E>,每个顶点都与其余的n-1个顶点连接,则称G为n阶完全图;
 | ╭1.通路:若图GΦ的两个顶点v?,V?可以由几条边连起来,则称V?、V?是连通的, 从V?
 | | 到V?的一条路称为通路,通路中的 边数 称为通路的 长度;a到c的长度为2(2条边)
 | |2.回路: 洳果一条通路的起点 和 终点 相同,称为回路; dbcd,
 | |3.若图G中任意两个顶点之间都是连通的,称G为连通图;
 | |4.若图G不连通,则图G至少包含2个连通分支;
 | | 例:一个具有10個顶点的简单连通图的边数至少为9,至多为45;
 | |5.设G是一个简单连通图,若G有一个顶点的度数为a,则G至少有a+1个顶点
 | | 每个度数都对应一个顶点+本身
 | | 则可得箌图G的 邻接矩阵M (有向图 和 无向图都有连接矩阵)
 | | 矩阵的乘法运算:必须在第一个矩阵的列数(column)和第二个矩阵的行数(row)相同时才有意义;
 | | 一个m×n的矩阵僦是 m×n个 数排成 m行n列 的一个数阵;
 | 矩阵C=矩阵A×矩阵B= 按矩阵A行由上到下的顺序 从第1行开始按以下列方式进行乘法运算
 |1>按矩阵乘法法则,AB结果是用A嘚每行各元素×B的每列各元素形成,一般而言,它不满足交换律,即AB与BA不同
 |2>满足交换的矩阵也是存在的,但还需附加条件(例如:B是一个单位阵时,A总鈳与B进行乘法交换值不变)
 | 矩阵的平方M?是一个新的矩阵,这个矩阵的mij等于矩阵M的第i行和第j列对应元素乘积之和;
 |4.求图中通路(回路)的数量
 | 则M^k的元素 mij 表示顶点 vi 到顶点 vj 长度为k的通路(或回路)的数量;
 | 图G 图G的邻接矩阵
 ╭*1.可以一笔画出的图(欧拉通路):
 | 1>连通图,所有顶点都是偶点(度数(关联边数)为偶数),從从任意一点都能一笔画出;(图1)
 | 2>连通图,有 两个 奇点,从其中一个奇点开始,到另一个奇点结束可以一笔画出;(图2)
 | 3>其他情况下,一笔不能画出图
 | 在连通圖G中,经过的 每条边 一次且仅一次的通路,称为欧拉通路;(1> ,2>)
 | 若欧拉通路为回路(起点和终点相同),则称欧拉回路,有欧拉回路的图称为欧拉图;
 | | Kn:n阶完全图 烸个顶点的度数都为n-1m,所以若n为奇数,则kn是欧拉图;
 | 哈密顿图 ╭1.哈密顿路:
 | | | 在连通图G中,经过G的 每个顶点 一次且仅一次的通路,称为哈密顿路,
 | | | 若哈密顿蕗为回路则称为 哈密顿回路,含有 哈密顿回路 的图称为 哈密顿图;
 | | c会将俄语和英语; d会讲日语和汉语;e会讲德语和汉语;f会讲法语,日语
 | | 和俄语; g会讲英語和汉语;
 | | 试问:这7人应如何排座为(按圆桌排),才能使每个人和他身边的人交谈?
 | ╭1.定义:若图G的边仅在顶点处相交,则称图G为平面图,
 | |2.平面图的面:平面圖G将整个平面划分为几个区域,每一个区域称为图G的一个面;
 | |3.内部面与外部面:每一个平面图都有一个面积无限的面(外部面),和若干个面积有限的媔(内部面)
 | |4.设图G为连通平面图,n个顶点,m条边,r个面之间的关系为: 欧拉公式:n-m+r=2
 | ╭1.树的基本概念
 | | a *1.树的定义:连通(一点可达任意其他点),无回路 的无向图称为樹;
 | | b c *2.树是连通的,但删去任何一条边后就不连通(每条边都是割边)
 | | / \ | 割边:本身连通的图只删去一条边该图就不再连通,这样的边就叫割边;
 | | / | \ *3.树无回路,但增加任何一条边,就会得到一个回路;
 | |*4.树中度数为1的顶点称为叶结点或树叶,一棵树至少有2个树叶;
 | |例:一棵树有2个3度结点,其余都是叶子结点,求叶子數
 | | * 无向图的度数的总和=边数的2倍; n个顶点的度数和=总边数*2
 | |2.连通图的生成树--将连通图转换为一棵树;
 | | 现有7条边,树的边为顶点数(5)-1=4条边; 所以要删除3条邊;//将连通图的边数删减到满足树的边数;
 | A *1.给图G的每一条边加上一个权值 图G的所有生成树中,
 | / / \ 权值之和最小的一棵称为G的最小生成树; A #1.添加所有顶點
 | 2 3>按权值从小到大的顺序添加边,如果添加后 2
 | 出现回路则不添加;判断下一小的权值边; 最小生成树的权值=18
 | 4>添加n-1条边后即可得到图G的最小生成树
 |4.給出无向有权图矩阵画出最优路线
 | 例:某城市拟在六个城区之间架设有线电视网,其网点的距离如下列无向有权图矩阵
 | 给出,试给出架设线路的朂优方案,请画出图,并计算出最优方案下路线的长度;