1、遥感数字图像处理复习 命题公式（proposition formula） 由命题常元、变元和联结词组成的形式更为复杂的命题 命题公式（ proposition formula ）定义 命题常元和命题变元是命题公式，特别的称作原子公式或原子 如果A,B是命题公式，那么(A), (AB), (AB), (AB), (AB)也是命题公式 只有有限步引用上述两条所组成的符号串是命题公式 重言式（永真式）tautology 命题变元的所有赋值都是命题公式的成真赋值 矛盾式（永假式、不可满足式）contradiction 命题变元的所有赋值都是命题公式的成假赋值 可满足式(contingency) 命题公
2、式至少有一个成真赋值 重言式的代入原理(rule of substitution) 将重言式A中的某个命题变元p的所有出现都代换为命题公式B，得到的命题公式记作A(B/p)，A(B/p)也是重言式。 命题公式的替换原理(rule of replacement) 将命题公式A中的子公式C的部分出现替换为和C逻辑等价的公式D（CD ），得到的命题公式记作B，则AB。 真值函数（truth function） 如果将联结词看作逻辑运算符，那么包含命题变元p1, p2, pn的公式A可以看作是p1, p2, pn的真值函数 指派（赋值assignments） 对任意给定的p1, p2, pn的一种取值
3、状况，称为指派或者赋值 析取范式(disjunctive normal form) 公式A称作公式A的析取范式，如果 AA A为合取子句或者若干合取子句的析取 合取范式(conjunctive normal form) 公式A称作公式A的合取范式，如果 AA A为析取子句或者若干析取子句的合取 主析取范式(major disjunctive form) 公式A称作公式A(p1, p2, pn)的主析取范式，如果 A是A的析取范式 A中每一个合取子句里p1, p2, pn均恰出现一次 主合取范式(major conjunctive form) 公式A称作公式A(p1, p2, pn)的主合取范式
4、，如果 A是A的合取范式A中每一个析取子句里p1, p2, pn均恰出现一次 联结词集的完备性 如果任意一个真值函数都可以用仅包含某个联结词集中的联结词的命题公式表示，则称这个联结词集为功能完备集 形式系统是一个符号体系 系统中的概念由符号表示 推理过程即符号变换的过程 以若干最基本的重言式作为基础，称作公理（axioms） 系统内符号变换的依据是若干确保由重言式导出重言式的规则，称作推理规则（rules of inference） 公理和推理规则确保系统内由正确的前提总能得到正确的推理结果 证明(proof) 公式序列A1,A2,Am称作Am的一个证明，如果Ai(1im)或者是公理，或者由A
5、j1,Ajk(j1,jki)用推理规则推得。 当这样的证明存在时，称Am为系统的定理(theorem)，记作*Am（*是形式系统的名称），或者简记为Am 演绎(deduction) 设为一公式集合。公式序列A1,A2,Am称作Am的以为前提的演绎，如果Ai(1im)或者是中的公式，或者是公理，或者由Aj1,Ajk(j1,jk0)是公式； 如果A,B是公式，v为任一个体变元，那么(A), (AB), (vA)（或(vA(v)）均为公式 除有限次数使用上述两个条款确定的符号串外，没有别的东西是公式 全称封闭式(generalization closure) 设v1,vn是公式A中的自由变元，那么公
6、式v1vnA（或v1vnA(v1,vn)）称为公式A的全称封闭式。 A中不含自由变元时，A的全称封闭式为其自身 演绎结果 在ND中，称A为的演绎结果，即NDA简记为A，如果存在如下序列： (=1)1A1, 2A2, , nAn(n=,An=A) 使得iAi (1in) 或者是公理； 或者是jAj (ji) 或者是对j1Aj1， jkAjk（j1,jki）使用推理规则导出的 如果有A，且=，则称A为ND的定理 外延公理(extensionality axiom) 两个集合A和B相等当且仅当它们具有相同的元素。 A=B x(xAxB) 0,1=1,0=x|x=0x=1 说明集合元素的无序性，以及集
7、合表示形式的不唯一性 概括公理(comprehension axiom) 对于任意个体域U，任一谓词公式P都确定一个以该域中的对象为元素的集合S。 S=x|xUP(x) 规定了集合成员的确定性空集：P(x)为永假式 正规公理(regularity axiom) 不存在集合A1,A2,A3,使得A3A2A1 直观来说就是集合的有限可分，个体域的元素是“基本粒子” 正规公理确立了元素和集合的不同层次性，集合不能是自己的成员 排除了A=A这样的“病态”集合 幂集(power set)运算 对任意集合A，(A)称作A的幂集，定义为：(A)=x|xA A的所有子集作为元素构成的集合 集合族(collec
8、tions) 如果集合C中的每个元素都是集合，称C为集合族 集合族的标志集(index set) 如果集合族C可以表示为某种下标的形式 C=Sd|dD 那么这些下标组成的集合称作集合族C的标志集 标志集可以是自然数、某些连续符号等 广义并 C=x|S(SCxS) 集合族中所有集合的并集 广义交 C=x|S(SCxS) 集合族中所有集合的交集 归纳定义(inductive definition) 基础条款 规定某些元素为待定义集合成员，集合其它元素可以从基本元素出发逐步确定 归纳条款 规定由已确定的集合元素去进一步确定其它元素的规则 终极条款 规定待定义集合只含有基础条款和归纳条款所确定的成员
9、基础条款和归纳条款称作“完备性条款”，必须保证毫无遗漏产生集合中所有成员 终极条款又称“纯粹性条款”，保证集合中仅包含满足完备性条款的那些对象 二元有序组，或者二元组(2-tuple)，或者序偶(ordered pairs) 设a,b为任意对象，称集合族a,a,b为二元有序组，简记为 称a为的第一分量，b为第二分量 n元有序组(n-tuple) 递归定义：n=2时，=a1,a1,a2 n2时，=, an ai称为n元组的第i分量 对任意集合A,A2,A，A1A2称作集合A1，A2的笛卡儿积，定义如下： A1A2 = | uA1,vA2 A1A2 An =(A1A2 An-1) An R称为集合
10、A1,A2,An-1到An的n元关系，如果R是A1A2An的一个子集。当A1=A2=An-1=An时，也称R为A上的n元关系 关系相等 如果关系R和S具有相同的前域和陪域，并且xy(xRyxSy) 合成运算(composition)（复合运算） R为A到B的二元关系，RAB，S为B到C的二元关系，SBC，R和S的合成关系RS定义为： RS=|xAzCy(yBxRyySz) 简化形式： RS=|y(xRyySz) 关系矩阵表示的合成运算 关系合成运算对应关系矩阵的乘法 将数乘换成合取，将数加换成析取 运算的封闭性 如果关系R的某个性质经过关系运算后仍然保持，则称该性质对这个运算封闭 类比：整数大
11、于0的性质，对加运算封闭，但是对于减运算不封闭 等价关系（equivalent relation） 等价关系R为A上的自反、对称、传递的二元关系 xRx；xRyyRx；xRyyRzxRz 等价类（equivalent class） 设R为A上的等价关系，对于每个aA，a的等价类记做aR(简记a)，定义为：aR=x|xA xRa，a称作aR的代表元素 等价类是A的子集，每个代表元素确定一个等价类 例子：“模2相等”，有2个等价类：0和1 相等关系EA有|A|个不同的等价类，每个等价类都是单元素集合 全关系AA只有一个等价类A 划分（partitions） 满足下列条件的集合A的子集族 B(B B
12、) =A B B(BBBB B B=) 中的元素称为划分的单元 特别约定A=时只有划分 很明显，A上的等价关系R的所有等价类的集合，构成A的一个划分，称作等价关系R对应的划分 xR|xA，所有等价类的集合是一个划分 反过来，集合A的一个划分，也对应A上的一个等价关系R，称作划分对应的等价关系 R=| B(BxByB) R=BBB= BB|B 积划分运算 划分1和2的积划分12是满足如下条件的划分： 12细于1和2 如果某个划分细于1和2，则一定细于12 也就是说， 12是细于1和2的最粗划分 积划分对应于等价关系交运算 那么和划分是否对应于等价关系的并运算呢？ 否！等价关系中的传递性质对于并运
13、算不封闭 针对传递性质扩展并运算结果 二元关系R的传递闭包t(R) t(R) 是传递的，Rt(R) 对于A上的任意一个具有传递性质且包含R的关系R，t(R)R 和划分对应于等价关系并运算结果的传递闭包 R1和R2分别是1和2对应的等价关系，则1+2是等价关系t(R1R2)对应的划分 商集(quotient sets) R是A上的等价关系，称A的划分aR|aA为A的R商集，记做A/R 每一个划分均为A上的一个商集，相应的商集的和、积对应于划分的和与积。 序关系（ordered relation） 序关系R为集合A上的自反、反对称、传递的二元关系 xRx, xRyyRxx=y, xRyyRzxRz
14、 存在序关系R的集合A称作有序集（ordered set），用二元有序组表示，一般的有序集表示成 哈斯图（Hasse graph） 对序关系关系图的一种简化画法 由于序关系自反，各结点都有环，省去； 由于序关系反对称且传递，所以关系图中任何两个不同的结点直接不会有双向的边或通路，所以省去边的箭头，把向上的方向定为箭头方向 由于序关系传递，所以省去所有推定的边，即ab,bc有ac，省去ac边 链（chain） 如果子集B中的任意两个元素都是可以比较的 xy(x,yBxyyx) 反链（anti chain）子集B中的任意两个元素都是不可比较的xy(x,yBxy (xy)(yx) 是有限的有序集，B
15、A 如果A中最长的链长度为n 则A存在一个划分，划分有n个单元，每个单元都是一反链 半序关系（Partially ordered relation） 序关系R为集合A上的反自反、反对称、传递的二元关系 (xRx), xRyyRxx=y, xRyyRzxRz 函数(function)定义 如果X到Y的二元关系fXY，对于每个xX，都有唯一的yY，使得f，则称f为X到Y的函数，记做：f:XY 当X=X1Xn时，称f为n元函数 函数的相等和包含 f:AB，g:CD 如果A=C，B=D，且对每个xA，都有f(x)=g(x)，则函数f等于g，记为f=g 如果AC，B=D，且对每个xA，都有f(x)=g(
16、x)，则函数f包含于g，记为fg 单射函数(injection) 如果任意x1x2有f(x1)f(x2) 满射函数(surjection) 如果任意y都有x使得y=f(x)，即Ran(f)=Y 双射函数(bejection) 如果f既是单射函数又是满射函数，称作双射函数也称作“一一对应” 函数作为关系，可以求逆，但是f是否函数？ 如果f不是单射，则f无法满足单值性 如果f不是满射，则Dom(f)Y 所以只有双射函数存在逆函数 双射函数f的逆函数(inverse function)记做f-1，也是双射函数，称f是可逆的 简单图simple graph：无环和重边的无向图 完全图complete
17、graph：任何两个不同结点间都有边关联的简单图，记做Kn 孤立结点isolated vertex：不是任何边的端点的结点 零图：仅有孤立结点构成的图（E=） 正则图 所有顶点的度均相同的图称为正则图(regular graph)，按照顶点的度数k称作k-正则图 Kn是n-1正则图 生成子图spanning subgraph 如果G1是G2的子图，且V1=V2 G1,G2互为补图 V1=V2, E1E2=, 是完全图 图的同构isomorphic |V1|=|V2|, |E1|=|E2| 如果可以将V1中所有的结点一一对应地置换为V2中的结点名后得到的图等于G2 u可达v(accessible
18、) u=v，或者存在一条u到v的路径 连通的无向图connected 无向图中任意两个顶点都是可达的 强连通的有向图 有向图中任意两个顶点都是互相可达的 单向连通的有向图 任意两个顶点，至少从一个顶点到另一个是可达的 弱连通的有向图 将有向图看作无向图时是连通的 连通分支（connected component） 图G的连通子图G，而且G不是任何其它连通子图的真子图（最大性） 欧拉图Euler graph 如果图G上有一条经过所有顶点、所有边的闭路径（允许顶点重复） 欧拉路径Euler walk 如果图G上有一条经过所有顶点、所有边的路径（允许顶点重复） 哈密顿图Hamilton graph
19、如果图G上有一条经过所有顶点的回路（不要求经过所有边） 也称作哈密顿回路 哈密顿通路Hamilton path 如果图G上有一条经过所有顶点的通路（非回路） 邻接矩阵(adjacency matrix) 无重边的有向图G=，其邻接矩阵AG定义为 aij=1, 当E aij=0, 当E是一个|V|V|矩阵 关联矩阵（简单无向图） 表示顶点和边的关联关系，n*m矩阵 通过矩阵的秩来判定图的连通分支个数 路径矩阵walk matrix 图G=的邻接矩阵A A(m)=A A A 路径矩阵B=A A(2) A(3) A(|V|) B的每个分量bij表示vi到vj是否有路径 可达性矩阵 P=I B，I是n
20、*n的单位矩阵 加上顶点的自身可达性 满足如下条件的无向图G= 有非空集合X,Y, X Y=V, X Y= ，且 每个vi,vjE，都有viXvjY或者viYvjX 可以用G=表示二分图bipartite graph 如果X,Y中任意两个顶点之间都有边，则称为完全二分图complete bipartite graph 完全二分图可以记作K|X|,|Y| 二分图的等价条件：G至少要有两个顶点，而且G中所有回路的长度都是偶数 匹配matching 将E的子集M称作一个匹配，如果M中的任意两条边都没有公共端点 边数最多的匹配称作最大匹配maximal matching 如果X(Y)中的所有的顶点都出
21、现在匹配M中，则称M是X(Y)-完全匹配perfect matching 如果M既是X-完全匹配，又是Y-完全匹配，称M是完全匹配 如果无向图G可以在一个平面上图示出来，并且各边仅在顶点处相交，称作平面图planar graph，否则是非平面图 K5和K3,3都不是平面图 它们都是正则图 任意去掉一条边，都成为平面图 K5是顶点数最少的非平面图 K3,3是边数最少的非平面图 平面图等价条件 G或者G的子图作任何同胚操作后得到的图均不能以K5及K3,3为子图(1930,Kuratowski) 同胚操作就是在原图的边上增加或者删除二度节点 根树rooted tree递归定义 一个孤立节点v0是根树
22、，v0称为树根 如果T1,T2,Tk是根树，其树根分别是v1,v2,vk，则 V=V(T1) V(T2) V(Tk) v0； E=E(T1) E(T2) E(Tk) v0,v1 v0,v2 v0,vk T=也是根树，v0称为树根 代数结构algebraic structure 在一个对象集合上定义若干运算，并设定若干公理描述运算的性质 运算operator Sn到S的一个函数，称为n元运算 常用*表示二元运算，*(x,y)常记做x*y 常用表示一元运算 运算的基本性质 普遍性：S中的所有元素都可参加运算 xy$z(x*y=z) 单值性：相同的元素运算结果也相同且唯一 xyxy(x=xy=yx*y=x*y) 封闭性：任何元素参加运算的结果也是S中的元素 xy$z(x*y=zzS) 代数结构的定义 非空集合S，称作代数结构的载体 载体S上的若干运算 一组刻画载体上各运算性质的公理 可约cancelable元素 中元素a，如果对任意x,yS有 a*x=a*y蕴涵x=y（左可约） x*a=y*a蕴涵x=y（右可约） 那么a称为可约的 同类型代数结构 |S|=|S| 运算的元数相同 同构的代数结构 存在S-S的一一映射h S中运算的像等于运算数像在S的运算结果 h(x*y)= h(x)*h(y) 同态映射homomorphism 对于代数结构和S
