五、归纳法
1.一般归纳法
①基础步骤：证明P(0)为真
②归纳步骤：在P(n）为真的前提下（归纳假设），证明P(n+1)为真
其中书上提到了一个有趣的证明：证明所有马的颜色都相同。
错误的关键为，不存在基础步骤到归纳步骤的推理关系。
即是归纳步骤运用到的步骤也要同样能运用到P(0)与P(1)之中
2.强归纳法
与一般归纳法的区别：在归纳假设中，可以假设P(0)……P(n)都为真，再证明P(n+1)为真
六、状态机
1.不变性原理
如果状态机保持不变性在初始状态为真，则所有可达状态皆为真。
理解：如果对于某个状态机，对于初始状态的某个谓词的保持不变性为真，那么他的所有可达状态都具有某个性质。
不变性原理证明：归纳法
龙胆虎威终结篇证明
基本步骤：对于初始状态P(0,0),看作3的0倍，成立。
归纳步骤：假设P(n)成立，证明P（N+1）为真
动作一：装满小壶，r=(b,3)，P（r）为真
动作二：大壶倒入小壶
1.小壶装不完大壶的水，则r=（b-(3-l),3），均为3的倍数
2.装的完，略
动作三：小壶倒入大壶，也成立
其余动作略，得证。
2.偏序正确性和终止性（程序验证需要的两个特性）
也就是状态机验证的两个特性。
偏序正确性：计算偏序关系的过程如果有结果，则结果是正确的。
终止性：过程会产生最终结果。
3.派生变量
符合某些既变化的变量，比如严格递减递增。
关于东南方向跳跃机器人的思考
：良序集合是否可以互相映射?
七、递归数据类型
递归数据类型分为两部分：
基本情形：数据类型的已知元素
构造情形：如何从基本情形中构造新元素。
结构归纳法：如何从递归数据类型中推理（证明）出一些性质
结构归纳法也要分两步分别证明，证明基础情形和构造情形均符合归纳假设（性质）。
一般来说基础情形证x=λ的情况符合，构造情形x=证正常情形。均只有一个变量。
