离散数学知识点.docx

一、逻辑和证明
命题逻辑
命题：是一个可以判断真假的陈述句。
联接词：A、V、-、 ？、?0记住“ p仅当q”意思是“如果p,则q"，即p-
记住“ q除非p”意思是“ ？p“q”。会考察条件语句翻译成汉语
构造真值表
p
qZ+正整数集，Q有理数集，R实数集，R+正实数集，C
复数集。
A和B相等当仅当？x(x G A?xG B); A是B的子集当仅当？x(x G Qx G B);
A是 B 的真子集当仅当？x(x GA- x G B) A ?x(x?A A x G B)。
募集：集合元素的所有可能组合，肯定有 ？何它自身。如？的募集就是{?},而{?}
的募集是{? , {?}}。
笛卡尔积：AX B,结果是序偶，其中的一个子集叫一个关系。
带量词和集合符号如？xGR (x2>0)是真的，则所有真值构成真值集。
集合恒等式
名称
(A U B)'=A' n B'?
(A n B)'=A' U B'
德摩根律
AU (A n B)=A
An (A U B)=A
吸收律
函数
考虑A-B的函数关系，定义域、陪域(实值函数、整数值函数)、值域、像集
(定义域的一个子集在值域的元素集合)
一对一或者单射：B可能有多余的元素，但不重复指向
映上或者满射：B中没有多余的元素，但可能重复指向。
一一对应或者双射：符合上述两种情况的函数关系。
反函数：如果是一一对应的就有反函数，否则没有。
合成函数：f o g(a)=f(g(a)), 一般来说交换律不成立。
序列
无限集分为：一组是和自然数集合有相同基数， 另一组是没有相同基数。 前者是
可数的，后者不可数。想要证明一个无限集是可数的只要证明它与自然数之间有一 一对应的关系。
如果A和B是可数的，则 AU B也是可数的。
如果存在一对一函数f从A到B和一对一函数g从B到A,那么A和B之间是一 一对应的。
求和公式：
a+ar+ar 2+ar3+...+ar n = (ar n+1-a)/(r-1)
1+2+3+...+n = n(n+1)/2
1+22+32+...+n 2 = n(n+1)(2n+1)/6
1+23+33+...+n 3 = n 2(n+1) 2/4

普通矩阵和、减、乘积，0-1矩阵还可以A、V、O （和相乘类似，用V代替 +, 用A代替X）
九、关系

设A和B是集合，从A到B的二元关系是 AX B的子集。一个从 A到B的二元关
系是集合R,第一个元素取自 A第二个元素取自B,当（a,b）属于R时写作aRbo
集合A上的关系是A到A的关系，有n个元素就有n2个有序对，n2个有序对就有 2n2个关系。
考虑集合A到A的关系R:
任意aG A都有（a, a） G R,则R是集合A上的自反关系。
任意a, bGA,若（a, b） G R都有（b, a） G R,则R是对称关系。
任意a, bGA,若（a, b） G R且（b, a） G R一定有a=b,则R是反对称关系。
任意 a, b, c G A,若（a, b） G R 且（b, c） G R一定有（a, c） G R,则 R是 传递关系。
若R是A到B的关系，S是B到C的关系，R与S的合成Ro S是有序数对（a, c）。 其中a GA, cGC,且存在一个bGB使得（a, b） G R, （b, c） G S。二元关系的5 种复合要会翻译成汉语。
关系的表示
0-1矩阵法：A有n个元素，B有m个元素，用一个 nXm的矩阵M表示，m=1 表示有关系。自反关系的 0-1矩阵主对角线全为1;对称关系的0-1矩阵是对称阵；
反对称关系的0-1矩阵关于主对角线反对称。
M1UR2=M1 V M2, MmRkM1A M2, M1 0 RkMQM2。
有向图法：A有n个元素，每一个关系是一条有向边。自反关系的图每一个顶点 都有一个环；对称关系的图在不同顶点之间每一条边都存在与之对应的反方向边 (也
可用无向图)；反对称关系的图在不同顶点之间每一条边都不存在与之对应的反方 向边；传递关系的图在 3个不同顶点之间构成正确方向的三角形。
关系的闭包
自反闭包：RUA,其中△ ={ (a, a) |a G A}
对称闭包：R并 R1,其中 R1={ (b,a) | (a, b) G R}
传递闭包：r矩阵传递闭包=mvm[2] v m[3] ... v mT] , 了解沃舍尔算法
等价关系：自反、对称且传递的关系
集合 A 的元素 a在 R上的 等价类[a]={s|(a,s) G R A s G A}。如 A={1,2,3,4,5,6,7,8} , R={(a,b)|a = b