结构归纳法

✍ dations ◷ 2025-06-08 01:14:19 #算法,数据结构,数学推理,良基性

结构归纳法是应用在数理逻辑、计算机科学、图论和一些其他数学领域的证明方法(比如Los's定理的证明),是一般化的数学归纳法 (数学归纳法仅仅定义在自然数上)。

其通常用来证明一些命题 (), 是递归定义结构(例如树和表)的一种。良基偏序是定义在这种结构上的。结构归纳法的证明是由证明命题对于所有的极小结构成立,以及如果他在一个结构 的基础结构中成立,那么其一定也在整个 中成立这些组成。比如,如果一个结构是个这样一个表,含有偏序 '<',只要表 在表 的尾部,那么 < 。在这样的排序中,空的 list 是唯一的最小元素。结构归纳法中,一些命题 () 的证明由两个部分组成:

考虑一下下面表的性质:

    length (L ++ M) = length L + length M          

这里的++ 表示表的加法运算

为了证明这个结论,我们需要定义一下length和加法运算:

    length  = 0                  length (h:t) = 1 + length t   
     ++ list = list               (h:t) ++ list = h: (t ++ list) 

这里的()代表头部是和尾部是的表。我们定义命题()指在当是时,在整个表中EQ成立。因此,我们应该证明在表中()成立。下面,我们将用结构归纳法证明。

首先我们应该证明成立;也就是,是空表(list )时EQ在整个表中成立。想一想EQ:

         length (L ++ M) = length L     + length M         length (++ M) = length     + length M         length       M = 0       + length M  (根据 加法定则1)         length       M = length     + length M  (根据 长度定则1)

因此这个定理的第一部分也就证明了,即当是时,EQ在整个中成立, 因为等式的两边相等。

现在我们需要证明,当是一个非空的表时,()成立。因为非空, 所以他一定会有首部元素, 设为, 和尾部元素,设为,因此我们可以将非空的表表示为 ()。归纳假设为当是时,EQ对于所有的值都成立:

    length (xs ++ M) = length xs + length M        (假设)

我们想要说明如果这样成立,那么当是尾部是的表时,EQ对于所有的值都成立。接着进行演算:

    length (L ++ M) = length L      + length M       length ((x:xs)++ M) = length (x:xs) + length M    length (x:(xs ++ M)) = length (x:xs) + length M   (根据 加法定则2)    1 + length (xs ++ M) = length (x:xs) + length M   (根据 长度定则2)    1 + length (xs ++ M) = 1 + length xs + length M   (根据 长度定则2)        length (xs ++ M) =     length xs + length M

结果正是我们的归纳假设, 我们成功了。

和标准的数学归纳法等价于良序原理一样, 结构归纳法也等价于良序原理。如果某种整个结构的集容纳一个良基偏序, 那么每个非空子集一定都含有最小元素。(其实这也是良基的定义) 这个辅助定理用这种形式定义的意义在于他能够让我们推论出,如果这里有某个我们需要证明的定理的反例,那么就一定存在一个极小的反例。如果我们能够指出他的存在,也就意味着有一个更小的反例, 我们得到一个矛盾了(因为最小的反例不是最小的),因此反例的集一定是空集。

这种论证的一个实例:考虑一下所有二叉树的集合。我们将证明在完全二叉树中叶子的数目比内部节点的数目多一个。假设这里有一个反例;那么就一定存在含有极小可能数目的内部节点的一个树。这个反例有个内部节点和个叶子,这里有+1 ≠ 。而且要是非平凡的,因为平凡的树 = 0而且 = 1因此不具有反例的条件。因此至少含有其亲代交点是一个内部节点的一个叶子。从树上删掉这个叶子和他的父辈, 将被删叶子的节点的兄弟节点提升到被删叶子从前父辈节点所占有的位置。这样做将和减少了1,因此新的树也有+1 ≠ ,这样就得到了一个更小的反例。但是在归纳假设中,已经是最小的反例了;因此,开始的或许有些反例的猜想被证明了是错误的。 '更小'的偏序意味着只要比的节点少那么 < 。

结构递归和结构归纳法的关系就象普通的递归和普通的数学归纳法一样。

相关

  • 生物圈生物系统层级关系:生物圈 > 生态系统 > 群落 > 种群 > 个体生物圈(Biosphere)是指地球上所有生态系的统合整体,是地球的一个外层圈,其范围为海平面上下垂直10公里。它包括地球上
  • 耐受免疫耐受(英语:immune tolerance或immunological tolerance)是指免疫系统对特定抗原的特异性无应答状态。免疫耐受包括天然免疫耐受与诱导免疫耐受。天然免疫耐受或自身耐受(sel
  • 毛细血管内增生性肾小球肾炎毛细血管内增生性肾小球肾炎(Endocapillary proliferative glomerulonephritis)是肾小球肾炎(Glomerulonephritis)的一种形式,它可以与肾炎有关。这可能与细小病毒B19(Parvov
  • 公共工程公共工程 是一个广泛类别的 基础设施 项目。通常是由政府 资助和建成的,用于社区 及其周边地区的娱乐、就业和健康和安全。 它们包括公共建筑(市政建筑物, 学校, 医院), 运输
  • 塞拉塞拉国家森林(英语:Sierra National Forest)是美国一座国家森林,位于加利福尼亚州境内、内华达山脉中部的西坡上。该森林最出名的是其山景,以及充沛的自然资源。森林的管理办公室
  • 大动脉炎大动脉炎(Takayasu arteritis,TA)是一种累及主动脉及其主要分支以及肺动脉的慢性进行性非特异炎性疾病:841。疾病由日本医生高安右人(Mikito Takayasu)在1908年首次报告,因此又被
  • 宁要社会主义的草,不要资本主义的苗宁要社会主义的草,不要资本主义的苗是文革结束后批判的四人帮言论之一。类似的说法还有“宁要社会主义的低产,不要资本主义的高产”、“宁要社会主义的低速度,不要资本主义的高
  • 八代拓八代拓(1993年1月6日-)是日本的男性声优。出身于岩手县。日本播音演技研究所出身。隶属于VIMS。首次接演主角的作品是《虎面人W》的东直人/虎面人。2018年,获得第12回声优奖的新
  • 塞米兹·阿里帕夏塞米兹·阿里·帕夏(土耳其语:Semiz Ali Paşa;?-1565年6月28日),波斯尼亚人德夫希尔梅出身的奥斯曼帝国政治家,在1549年至1553年出任埃及省总督,在苏里曼大帝驸马鲁斯坦帕夏死后于1
  • Old Town Road《Old Town Road》(字面意思:“”)是美国说唱歌手利尔·纳斯·X的一首歌,于2018年12月3日首次独立发行。积累一定人气后,该单曲被一主要唱片公司哥伦比亚唱片重新发行。利尔·纳