数学公式的智能分解,刘硕军,Lambda演算：,演算（lambda calculus）是一套用于研究函数定义、函数应用和递归的形式系统。 Lambda表达式： 1.任一个变元是一个项 2.若，是项，则（）也是项（函数应用） 是一个项，而是一个变元，则（，）也是一个项,Lambda演算变量绑定规则：,在一个-项中，变量要么是自由出现的，要么是被一个符号绑定的（以函数方式理解，既被绑定的项是与函数的值相关的） 1. 在表达式x中，如果x本身就是一个变量，那么x就是一个单独的自由出现。 2. 在表达式 x.E中，E中所有的x的出现都被前面的那个所绑定。 3. 在表达式(MN )中，变量的自由出现就是M和N中所有变量的自由出现。,De Bruijin Notation,它是lambda演算的一种表示形式，该表示形式利用数字替换变量来实现对lambda演算更加简单的形式化表示。,同理 x,y,z,xz(yz)可以写成De Bruijin Notation 形式为 31（21） y z z x y x,利用Binary Lambda演算研究Kolmogorov复杂性。,Binary lambda转换依据下面三条小公式： 这里，我们称|M |为M的大小（size）。例如Lambda演算表达式x.x改写成Binary Lambda演算为0010，即x.x 0010，而x y.x 0000110，x.x x 00011010，三者的大小（size）分别为4、7、8。,数学公式复杂度计算方法：,我们首先来分析一个数学公式的构成及影响因素：我们可以将任何一个数学表达式E转换为树形结构。 1.符号（运算符、数字、变量、符号常量、函数） 2.相应的树形结构组合规则,复杂度计算表达式：,因此，设E为表达式E转为无类型结构的二进制Lamda演算表达式，Pi为结点对象，则Pi可能为数字、符号常量、变量，则表达式E的表示复杂度Cr为：,表示复杂度计算步骤：,步骤一：将数学表达式E转换为树形结构，并对所有叶子结点根据结点的类型采用不同的二进制编码方法表示，下面对不同的结点类型给出了具体的长度计算方法： 整数： 小数： 分数： 变量与符号常量 不同的变量和符号常量有相同的表示复杂度，本文中采用了一个常量值8（ASCII码的二进制长度）作为变量和符号常量的表示复杂度。,步骤2：,对所有结点依次用无类型变量s1、s2、s3、进行替换；然后将替换后的表达式树用Lambda演算表示出来，表示方法如下：一个一元运算可表示为xa.ax，一个二元运算可表示为xya.axy，一个三元运算可表示为xyza.axyz，以此类推，一个n元运算可表示为S1 S2 S3Sna. aS1 S2 S3Sn。,步骤3：,步骤三：将Lambda演算表达式转换为De Bruijn Index形式，转换规则为：对于Lambda演算表达式M中每一变量按其被绑定的次序用相应的数字替换。如x.y.z.xz(yz)写成De Bruijn Notation形式为31(21)。,步骤4：,步骤四：将De Bruijn Index形式的Lambda演算表达式转换为Binary Lambda演算表达式，则二进制位数长度即为数学表达式E的组合规则部分的复杂度。,步骤5：,利用下面公式计算得出表达式E的表示复杂度。,Example:,该公式化为前缀表示方法为： 因此，数学公式转换为树形结构如下一页图所示其中叶子结点包括x、3、3、x、2，按结点类型计算其表示复杂度为:,将表达式中具体元素用无类型符号替代，另外一张图显示了用无类型符号S1, S2, S3替代各元素后的树形结构图,该结构图显示了lambda表达式的组合规则。然后将数学表达式组合规则用Lambda Calculus表示为:,将表达式重写为De Bruijn Notation格式,可将De Bruijn Notation格式的表达式转化为Binary Lambda Calculus表达式：,0001011000010110000101101110110000110000101101110110000101101110110 则数学表达式的组合规则的复杂度为该Binary Lambda Calculus表达式的长度。因此表达式(5-9)的组合规则的复杂度为67，叶子结点的复杂度为30，整个表达式的表示复杂度为97。,讨论：,结构复杂度对表达式复杂度的影响是不是过大？ 向量，有下标的参数？,