离散数学(高教)概念整理

1、数理逻辑命题逻辑命题p,q,r,s非真即假的陈述句命题的真值0 1命题的陈述句所表达的判断结果原子命题（简单命题）不能被分解成更简单的命题简单命题通过联结词联结而成的命题，称为复合命题命题的符号化p: 4是素数用小写英文字母（如p:4是素数）表示命题。用小写英文字母（如p:4是素数）表示原子命题，用联结词联结原子命题表示复合命题。联结词否定连接词否p为真当且仅当p为假合取联结词p合取q为真当且仅当p，q同时为真（复合命题“p并且q”称为p与q的合取式）析取联结词p析取q为假当且仅当p，q同时为假（复合命题“p或q”称为p与q的析取式）蕴含连接词p蕴含q为假当且仅当p为真，q为假。（复合命题“如

2、果p,则q”（因为p所以q，除非q才p）称为p与q的蕴含式，p是蕴含式的前件，q是蕴含式的后件）q是p的必要条件。等价联结词p等价q当且仅当，同时为真或假。（复合命题“p当且仅当q”称作p与q的等价式） 真值表命题公式及其赋值命题常项原子命题（简单命题）的另一称呼，由于其真值确定命题变项真值可以变化的陈述句合式公式（命题公式）A，B命题变项用联结词和圆括号用一定逻辑关系连接起来的符号串，简称公式赋值（解释）给公式A中的每个命题变项各指定一个真值。这组值使A为1，则称为成真赋值。含n个命题变项的公式有2的n次方个不同赋值。含n个命题变项的公式有2的2的n次方个不同真值表情况。重言式（永真式）命题

3、公式A在各种赋值下取值均为真矛盾式（永假式）命题公式A在各种赋值下取值均为假可满足式命题公式A至少存在一个成真赋值哑元对公式A和B进行比较讨论，可知A和B共含有n个命题变项，其中A不含有的命题变项称为A的哑元，其取值不影响A的值命题逻辑等值演算等值式如果命题A和B有相同的真值表，则有命题AB为重言式，这种情况下称A与B是等值的，记作AB（重要）等值式模式常用的16条命题间的等值模式，书p18析取范式与合取范式文字命题变项及其否定的统称简单析取式，简单合取式由有限个文字构成的析取式，合取式析取范式，合取范式由有限个简单合取式的析取构成的命题公式，称为析取范式。同理为合取范式。命题公式的析取或合取

4、范式一般不唯一极小项，极大项 mi Mi简单合取式中的命题变项及它的否定式恰好出现一次，并按照下标拍好，这样的简单合取式叫做极小项。同理为极大项。n个命题变项可以产生2的n次方个极小项，每个极小项都有且仅有一个成真赋值，这一组成真赋值（01组成）转化为对应的十进制数i，将这个极小项表示为mi类似的，极大项为Mi主析取范式m0m1m3m7主合取范式所有简单合取式都是极小项的析取式，这是唯一的主析取范式。同理。联结词的完备集n元真值函数F函数F的自变量为n个命题变项，值域为0,1,这样的函数叫n元真值函数。n个命题变项一共可以构成2的2的n次方个不同的真值函数。每个真值函数与唯一的一个主析取范式（

5、主合取范式）等值，同时它们都等值于无穷多个等值的命题公式。联结词完备集S=, s是一个联结词集合，任何n元真值函数都可以仅用s中的联结词构成的公式表示.s就是联结词完备集。命题逻辑的推理理论推理A1,AkB是指从前提触发推出结论的思维过程。前提是已知的命题公式集合，结论是推出的命题公式。有效的结论命题集合Ai的合取式有0和1两种取值，只要不出现某一种赋值情况下命题集合为假，结论B为真。那么就称结论B是有效的结论。称这一种推理是正确的。证明是由一个描述推理过程的命题公式序列形式系统I书p46自然推理系统P数p47主要是用来在这个系统下构造推理的证明附加前提证明法结论为蕴含式时，可以把前件作为推理

6、前提，使结论为后件归谬法使结论的否命题作为前提能退出矛盾，则证明一阶逻辑基本概念一阶命题符号化x(M(x)F(x)1个体词a,b,x,y研究对象中独立存在的客体。取值范围叫做“个体域”。默认个体域为“全总个体域”2谓词F（） G（，）刻画个体词性质或关系的词。比如说“是无理数”。含有个命题变项的谓词叫做元谓词。以个体域为定义域，,为值域的元函数或关系。量词 全称量词“任意”存在量词“存在”一阶语言（花体）由抽象符号构成的用于一阶逻辑的形式语言。项个体常项，个体变项，元函数（自变量为项）是花体的项。指导变元量词的辖域例如，就叫做指导变元，是量词的辖域，在辖域中的所有出现称为约束出现，其他变项叫自

7、由出现合式公式（谓词公式）一阶语言下的合式公式。闭式（封闭的公式）公式中不含自由出现的个体变项.解释I解释就是对抽象一阶语言的在I的具体含义，包括四个部分：非空个体域D1每一个个体常项在D1中的对应每一个n元函数在D1上的对应每一个谓词符号在D1上的对应永真式（逻辑有效式），永假式，可满足式同上文。在任何解释下均为真的公式为永真式。这里不存在重言式的说法。代换实例用谓词公式A1，A2代换命题公式A0中的命题变项p1,p2得到的公式A叫做A0的代换实例。重言式的代换实例都是永真式。一阶逻辑等值验算等值式这个等值式是一阶逻辑下的等值式。定义同上。当A等价B为永真式，称AB是等值式。等值式类型书p6

8、9比如说任意x有（A（x）B）等价于存在x满足A（x）并且B一阶逻辑前束范式就是要求把所有量词放到最前方。去掉重名变量。集合论集合基本概念A=无序，唯一，确定幂集P（A）或花体pA，2AA的全体子集构成的集合集合的运算并集AB交集AB-相对补集A-Bx属于A但是不属于B的部分组成的集合对称差集ABx属于A和x属于B的部分，不包括既属于A又属于B绝对补集A给定全集中不属于A的部分A广义并A的元素（是个集合）的元素构成的集合A广义交A（非空）的所有元素的公共元素组成的集合有穷集的计数文氏图容斥定理p90集合恒等式p92有序对和笛卡尔积有序对两个元素按一定顺序排列成的二元组，x叫第一元素，y叫第二元

9、素笛卡尔积AB集合A中的元素作为第一元素，集合B中的元素作为第二元素，构成有序对。这样的有序对组成的集合叫做A和B的笛卡尔积笛卡尔积，对并和交运算满足分配率A包含于C并且B包含于D的时候可以推出，AB包含于CD二元关系R（关系） 是个集合一个集合。如果它是空集，或者他的元素都是有序对，则这个集合是一个二元关系，记作R。如果R，可记作xRy.从A到B的二元关系AB（A和B的笛卡尔积）的任何子集定义的二元关系（子集不止一个，这个就不止一个）A=B时叫做A上的二元关系，A上有2的n平方次方个不同二元关系R为A上的二元关系即A的所有元素作第一元素组合A的所有元素作第二元素的有序对的集合.空关系空集是A

10、A的子集，叫做A上的空关系全域关系EAEA=AA=|xA并且yA恒等关系IAIA=|xA小于等于关系LA关系矩阵，关系图p105关系的运算R的定义域domRR中所有有序对的第一元素构成的集合R的值域ranRR中所有有序对的第二元素构成的集合R的域fldR定义域和值域的并集R的逆关系（R的逆）R-1这个集合的元素(有序对)为R中的有序对第一元素第二元素互换G对F的右复合FG=|存在tF并且G F和G是二元关系右复合支持结合律A上的二元关系和恒等关系的符合为A上的二元关系R在A上的限制RA（半个箭头）R为二元关系，A为集合，“R在A上的限制”也是个二元关系（集合），其中有序对的第一元素也是A的元素

11、A在R下的像RARA是一个集合，元素是既是R中有序对的第一元素，又是A中元素的元素。R的n次幂Rn首先，R是A上的二元关系，不是随便什么二元关系。R的0次幂是A的恒等关系IA，即第一元素=第二元素的有序对组成的集合R的第n+1次幂=R的n次幂R并且，必有s,t使得R的s次幂=R的t次幂关系的性质（R为A上的关系）自反性IAR任意x,如果x是A的元素可以推出R对称性R=R-1任意x,y，如果x,y是A的元素并且属于R可以推出R传递性RRR任意x,y,z，如果x,y,z是A的元素并且属于R并且属于R可以推出R关系的闭包R的自反闭包R r(R)在R中添加尽可能少的有序对，得到R，使R具有自反性对称闭

12、包s(R)传递闭包t(R)等价关系与划分等价（=自反，对称，传递）关系等价是一个对于关系的定语。R为A上的关系，如果R是自反的，对称的，传递的，则称R为A上的等价关系。若R，称x等价于y，记作xyx与y模n相等 xy(mod n)x除以n的余数与y除以n的余数相等在整数集上，模n是个等价关系。x关于R的等价类 xR(x或x)R为A上的等价关系。x关于R的等价类（简称x的等价类）是A中所有与x等价的元素构成的集合。A关于R的商集 A/RR为非空集合A上的等价关系，R的所有等价类作为元素的集合称为A关于R的商集，记作A/R,即=x|xA。也就是元素是集合的集合。A的子集族P(A),A的某些子集构成

13、的集合A的一个划分子集族满足下面三个条件时，叫做A的一个划分，中的元素（就是A的子集）叫做A的划分块空集不属于中的任意两个元素（集合）交集为空的广义并（中的元素（A的子集）的元素的并集）就是A商集就是一个划分偏序关系偏序(=自反，反对称，传递)关系如果，记作xy，表示按照这个顺序x排在y的前边或者x就是y恒等关系，小于或等于关系，乘除关系，包含关系都是偏序关系x与y可比x与y可比等价于，xy或者yx全序关系（线序关系）设R是非空集合A上的偏序关系，如果任意x,y属于A，x与y都是可比的（也就是A的所有元素都出现在这个R中）则称R为A上的全序关系偏序集A和A上的偏序关系一起组成的集合，记作y覆盖

14、x(y是x的后继)xy且不存在z使得xzy，则称y覆盖x偏序集的哈斯图如果xy，就把x画在y的下方，并且如果y还覆盖x，就用一条线段连接xy最小元，极小元，最大元，极大元偏序集，B包含于A，y是B的元素对于任意B 中的元素x都有y小于等于x，y为最小元对于任意B中的元素x并且xy使都推出x=y，y是极小元最小元存在时，要求最小元和B中的其他元素都可比，所以不一定存在，如果存在一定是唯一的。极小元不一定和B中所有元素都可比，所以一定存在，并且可能不唯一。上界，下界偏序集，B包含于A，y是A的元素（注意，上面y是属于B的）对于任意B 中的元素x都有y小于等于x成立，y为B的下界对于任意B 中的元素

15、x都有x小于等于y成立，y为B的上界B的上界可知可能不止一个，最小的叫最小上界（上确界），最大下界同理。B的最大元一定是B的最小上界，反之不一定（因为可能不存在最大元）函数函数y=F(x)函数是一种特殊的二元关系。每一个定义域中的x有唯一的值域中的y与它构成关系xFy，F就是函数从A到B的函数f f:ABAB为集合，A=f定义域，f值域包含于BB上A BA所有从A到B的函数组成的集合A1在f下的像 f(A1)A1是A的子集，集合f(A1)=f(x)|xA1称为A1在f下的像B1在f下的完全原像 f-1(B1)集合f-1(B1)是满足f(x)属于B1的x的集合满射函数f:AB只要值域包含于B，当

16、值域等于B的时候称它是满射的单射对于函数本身要求每一个x有y与之对应（不要求y不相等），也即对于同一个y可能有不止一个x是它的第一元素。当只有唯一的x(即不同的x)与它对应是，称为函数是单射的。双射函数既是满射又是单射时常函数 f(x)=cA上的恒等函数IA IAx=x单调递增、减当函数f:A映射B，A，B为偏序集时，如果x1x2,有f(x1)=f(x2)称为单调递增。注意这里的大小不是指数值而是二元关系的前后性 A的特征函数XA:A0,1函数XA（a）=1，当a是A的元素 0，当a不是A到商集A/R的自然映射 gg是一个映射 g(a)=a 即a关于R的等价类（A中与a等价的元素构成的集合）函

17、数的复合与反函数函数的复合FG函数是一种二元关系（元素为有序对的集合），函数的复合就是关系的右复合函数的复合传递满射，单射，双射。即比如函数f,g满射则f复合g也满射。反函数f-1（双射函数才有反函数）函数的逆运算不一定是函数，只是二元关系。只有双射函数才有反函数，表示从B映射到A的函数。函数和它反函数的复合为恒等关系IA双射函数与集合的基数集合的势量度集合元素多少的量等势AB存在从A到B的双射函数，即A和B等势B优势于A AB存在从A到B的单射函数把自然数定义为集合0=后继n+=nn（也就是说紧跟着n的自然数（n+1）定义的集合就是n定义的集合元素n组成的集合，类似于数学归纳法的概念）举例

18、3=0,1,2所以m=n（元素意义）等价于mn（集合等势）mn等价于mn有穷集，无穷集一个集合是有穷的当且仅当他与（唯一的）某个自然数等势。否则为无穷集。有穷集合A的基数 |A|（cardA）与有穷集A等势的哪个唯一的自然数就是A的基数（由于等势就是存在双射函数，也就是一一对应，其实基数就是A中元素的个数）集合的基数就是集合的势。两个集合基数相等等价于他们等势。自然数集合N的基数0阿列夫零一个标记，即为自然数的基数。是最小的无穷基数。实数集R的基数阿列夫可数集（可列集）当cardA阿列夫零时，称A为可数集代数结构二元运算及其性质S上的二元运算（简称二元运算）函数f:SSS 称为S上的二元运算（

19、也就是对S中的元素组成的有序对进行操作（也就是操作有序对的第一第二元素）映射到S上的元素）比如说f:NNN，f()=x+y（加法可以，减法就不行，可能有负数就不是N的元素了，称N对减法“不封闭”）算符 *用这些符号代表f对于有序对第一第二元素的操作S上的一元运算从S映射到S的函数叫做一元运算运算在S上适合“交换律”对于任意x,y有xy=yx，即说运算在S上适合交换律结合律(x*y)*z=x*(y*z), 即说运算*在S上适合结合律幂等律S任意x,xx=x, 即说运算在S上适合幂等律幂等元S中某些x满足幂等律，则称x为运算的幂等元分配率吸收率单位元如果e对于任意x都有ex=x且xe=x，则称e为

20、关于运算的单位元（唯一），只成立其一为左单位元/右单位元零元如果对任意x都有x=且x=，则称零元（唯一）只成立其一为左零元/右零元逆元yx=e时，y为左逆元，同理为右逆元，同时成立为逆元（唯一），称x可逆消去律当x不是零元的时候，对于任意x,y,z，如果xy=xz的时候可以推出y=z，则运算满足左消去律，同理为满足右消去律，同时满足消去律代数系统代数系统（代数）V=非空集合S和S上k个一元或二元运算组成的系统，称为一个代数系统，简称代数模n加法xyxy=(x+y)mod n模n乘法xy(实际符号为在内)=(xy)mod n代数常数（特异元素）在代数系统中比较重要的特定元素，比如说零元，单位元同

21、类型的代数系统（构成成分相同）运算的个数相同：比如说你是我是，都是两个对应运算的元数相同：都是二元运算代数常数个数相同：都有单位元和零元则称两个代数系统具有相同的构成成分，运算性质（满不满足交换律，结合律等等性质）却不一定一样子代数系统(子代数)BB是个集合，元素包含于代数系统V的元素集合S，B对V的所有运算f1,f2都封闭，代数常数也相同，就称是V的子代数系统，简称B平凡的子代数V最大和最小的子代数，一个是它自身，一个是它的所有代数常数组成的积代数V=V1 和V2是同类型的代数系统，定义二元运算，A和B的笛卡尔积中的有序对，两对作运算，等于V1,V2,是V的因子代数代数系统同态，同构同态映射

22、(同态)f：ABA中两个元素的运算结果映射到B=A的两个元素映射到B对应两个元素的运算结果如果f是单射，就叫单同态如果f是满射，就叫满同态，V2叫V1的同态像 V1V2同构V1V2如果f是双射函数，就说明V1同构于V2群的定义及其性质群和半群都是具有一个二元运算的代数系统半群V=代数系统V唯一的二元运算，是可结合的，V就是半群幺半群（独异点）V=半群有关于运算的单位元e群G（结合性，单位元，逆元）运算有结合性，有单位元，每个元素有子集的逆元，V就是群，通常记为G省略算符xy变成xy由于只有一个运算，所以省略算符表示，记住，这不是乘法简写群G的阶（群的基数）前面说过，集合元素的个数大致等同于集合

23、的基数（等势概念），这里也叫阶平凡群只含单位元的群阿贝尔群（交换群）二元运算可交换群G元素a的n次幂a的0次幂=单位元e其他的就是做运算一个个叠上去负数次幂=a的逆元的正数次幂G的元素a的阶a|k| (也叫a是k阶元)使a的k次幂=e不是等于自身，是等于单位元的最小正整数k为a的阶（周期）若不存在，a为无限阶元对于单位元来说，它的阶是1，因为任何元素的1次幂是它本身子群与群的陪集分解子群HGH 是G的非空子集，如果H是群，它就是G的子群平凡子群G（最大）和e(最小)，叫做G的平凡子群非空子集是子群的判定定理第一种：a,b属于H的时候，ab属于H，并且a的逆元也属于H第二种：a,b属于H的时候，

24、ab-1属于H第三种：H有穷集，a,b属于H的时候，ab属于H概括的说，子群必须满足逆元和单位元存在由a生成的子群a的所有幂构成的集合（G的）中心CC是与G中所有元素可交换的元素组成的集合由B生成的子群所有包含B的子群的交集群G的子群格(这是个偏序集)S是G的所有子群的集合，R是运算，ARB表示A是B的子群因为是偏序集，所以可以画出哈斯图陪集Ha=ha|hHa是G的元素，Ha是子群H在G中的右陪集两个同子群的陪集要么相等，要么相交为空集给定子群的所有右陪集的集合是G的一个划分陪集的代表元素a正规子群（不变子群）对G的任何元素，比如说a,都有aH=Ha，则H叫正规子群H在G中的指数G:HH在G中

25、的陪集数目，叫做H在G中的指数拉格朗日定理|G|=|H|G:H循环群与置换群循环群G=a叫做G的生成元循环群有n阶循环群和无限循环群生成元的个数求法无限循环群只有两个a和a-1n阶生成群生成元是有与n互素的数的个数互素=两个数公约数只有1比如n等于6，从0数到n-1,有1,5与n互素，所以有两个生成元这两个生成元就是a的1次方，a的5次方即互素数是a的幂求循环群子群的的方法G=是n阶循环群，求出n的所有正因子，是G唯一的d阶子群S上的n元置换：S S双射函数。S是正整数1到n的集合的乘积 这两个函数的复合S上的k阶轮换理解一下轮换的意思就知道是怎么置换的了。如果k=2,就叫做对换任何n元置换可

26、以表示成不交的轮换之积轮换表示式=（1,5,2,3,6）（4）举例的是一个六阶的S，其中1换到5,5换到21阶轮换可以省略n元对称群所有的n元置换构成的集合Sn，置换的乘法满足结合律，（1）是单位元，逆置换就是逆元，所以Sn关于置换的乘法构成一个群环与域环是具有两个二元运算的代数系统环构成交换群（结合，逆元，单位元，交换）构成半群（结合）关于+适合分配率（1（2+3）=12+13）这就是个环模n的整数环Zn=0,1,2,n-1，后面那是模n加法，模n乘法为了表述方便，以后都把+作为环的第一个运算，叫环中的加法，同理环中的乘法，同时把0作为环中加法单位元，1作为环中乘法单位元。他们都不是常规意义

27、上的+，0,1了交换环环中乘法满足交换律含幺环环中乘法存在单位元无零因子环要是ab=0，只可能是a为0或者b为0整环上述三点都满足域R是整环R只要有两个元素R中元素（除0外）都有逆元图论图无序积AB=a,b|aA并且bB无序对a,b可记作(a,b)无向图G=无向图G是一个有序的二元组顶点集V（非空有穷集）其中元素称为顶点或结点边集E=VV的有穷多重（元素可重复出现）的子集元素称为无向边，简称边有向图D=E是笛卡尔积VV的有穷多重子集图的阶顶点数就是图的阶，n个顶点的图叫n阶图零图一条边也没有的图平凡图只有一个点，没有边的图空图没有顶点的图（也就没有边）标定图给每个顶点和每一条变指定符号的图有向

28、图的基图把有向边改成无向边的无向图边与点的关联次数一个边连接的两个点，叫做他的端点端点不同时，与某个端点关联次数为1相同为2不关联，为0环=端点相同的边点与点相邻两点之间有一条边连接边与边相邻两个边至少有一个公共端点孤立点没有边关联的顶点点的邻域N（v）所有与点v相邻的的点的集合点的关联集I（v）所有与点v关联的边的集合平行边关联两个点的边多于一条，这些边叫平行边重数平行边的条数简单图不含平行边和环的图度数d(v)这个点作为边的端点的次数有向图按照作为起点和终点分为入度和出度，和为度数最大度（G） 最小度（G）图里最大的度数和最小的度数的表示悬挂顶点度数为1的点悬挂边=和悬挂顶点关联的边握手定

29、理无向图：度数之和=2边数有向图：出度=入度=边数度数列d=(d1,d2,dn) 举例（5,3,3,1）每一个对应点集中的一个点的度数只有其中所有度数和为偶数时，d才是可图化的对于n阶简单图来说，最大度数小于等于n-1（可以判断能不能简单图化）图的同构G1G2这两个图的点可以一一对应，且对应点间的重数相同n阶（无向）完全图Kn首先它是n阶无向简单图，每个顶点都与其他所有顶点相邻n阶竞赛图（有向）有向简单图的基图是无向完全图k-正则图n阶无向简单图的每个点的度数相等为k边数m=kn/2子图边集是G的边集的子集，点集是G的点集的子集的图是G的子图生成子图点集不变，边集是子集的图G的V1导出子图GV

30、1V1里面的顶点关联的边都带上G的E1导出子图GE1E1里面的边关联的顶点都带上G的补图G补图的点集和原来一样，补图的边集是原来没有的边补图与G同构，G是自补图G-e,G-v,G-E,G-V从图G中取出某条边，某个点，某个边集，某个点集Ge边的收缩删掉这个边后，把它原本关联的两个点用一个点代替，这个点连接这两个点原本相邻的点通路与回路通路=点边点边点边点长度通路中边的条数回路始点与终点相同的通路简单通路边各异的通路路径（初级通路）点也各异的通路圈路径的起点与终点相同长度相同的圈都是同构的图的连通性点u,v是连通的 uvu到v之间存在通路连通图任何两个顶点之间都是连通的连通分支GViVi是V关于

31、顶点连通关系的一个等价类这个点集的导出子图叫G的一个连通分支(也就是G中一个互相连通的部分)连通分支数p(G)如字面意义，连通图的p=1距离d(u,v)u,v之间最短的通路的长度，不连通时为正无穷G的点割集点集子集V，去掉这其中的点后，连通分支数变多（被隔成了更多块）如果只把V中的部分点去掉，连通分支数不变如果V只有一个元素，那个唯一的点叫做割点G的边割集（割集）定义同点割集，去掉这些边后，连通分支数变多如果E只有一个元素，那唯一的边叫桥（割边）（点）连通度（G）是G的所有点割集中阶数最小（元素个数最少）的那个点割集的阶数比如G有割点，连通度就是1非连通图的连通度为0k-连通图连通度大于等于k的图只要G是k-连通图，去掉任何k-1个顶点，他还是连通的边连通度（G）类比上方vi可达vj vivj（有向图）表示从vi到vj存在通路（这里有方向的概念）强连通图（有向图）任何两个点都是双向可达的有向图=至少一个回路经过所有点二部图G（G中没有奇圈）G中每条边的端点，都是一个属于V1，一个属于V2完全二部图Kr,sV1中