那就用数学归纳法证明一下吧。
假定串是`L_00L_10L_20...0L_i0...0L_{n-1}0L_n`
这里`L_i`表示两个0之间有`L_i`个连续"1" ，按mathe的说法，`L_i`是可以等于0的。
我们要证明的是`L_00L_10L_20...0L_i0...0L_{n-1}0L_n↔[ΣL_n]_30_{_2}`
这里`ΣL_n=\D\sum^n_{i=0}(-1)^iL_i=L_0-L_1+L_2-\cdots+(-1)^iL_i+\cdots+(-1)^nL_n`，即交错和差，`[\ ]_3`表示取模3最小非负余数，
`_2`表示取模2最小非负余数. `0_{_2}`当`n`为奇数时为0，当`n`为偶数时为空。
当`n=0`时由规则一不证自明。
当`n=1`时，先运用 "插入111” 将`L_0`加长到不短于`L_1`,
然后反复运用`101→0`同步削减`L_0`和`L_1`，
直到将`L_1`耗尽，得到`_30`.
成立。
当`n=2`时，前已得到`L_00L_1↔_30`, 所以`L_00L_10L_2↔_300L_2`,
接着运用规则一删去00，成立。
假定`n=k`成立，
当`n=k+1时`，按假定先化成`[ΣL_k]_30L_{k+1}`(k为偶数时）或者`[ΣL_k]_300L_{k+1}`(k为奇数时）
前者，`[ΣL_k]_30L_{k+1}`按`n=1`的过程化成`[ΣL_{k+1}]_30`，成立。
后者，`[ΣL_k]_300L_{k+1}`运用规则一删去00，得`[ΣL_{k+1}]_3`，成立。
所以，对于任意长的串，上述公式都成立。
在得到8#中的不变量之前，如何证明4#中的法则2？
法则2: 若A+C↔B+C，或者C+A↔C+B，则A↔B。这里“+”表示接龙。
法则2是说，两个可能不同但是等价的串，如果同一端有相同的片段，掐去后剩余的两片段仍然等价。
当然，剩余的片段可能与它原来的串不等价了，但两剩余片段保持等价。
如果C↔空，那是显然的，把C代换为空就行了。
对于C不等价于空呢？
为了证明法则2，需要定义串的逆。
定理1：对任意串A，总存在串B，使得A+B↔空。
证明：因为，1+11↔空，0+0↔空， 所以对任意串A，都可以循A从右至左逐位构成从左到右的序列B，使得 A+B↔空
定义1：如果A+B↔空，则A称为B的左逆，B称为A的右逆。
定理2：左逆↔右逆。即如果A+B↔空，则B+A↔空。
证明：由定理1假定B+C↔空，则A↔A+(B+C)=(A+B)+C↔C, 从B+C↔空 由法则一将C替换为A得 B+A↔空。
由定理2，逆不分左右，所以定义1需要简化：
定义2：如果A+B↔空，A与B互称为彼此的逆。
有了逆的概念，就可以证明法则二了。
由A+C↔B+C，设C的逆为C‘， 则A+C+C'↔B+C+C' → A↔B
若C+A↔C+B，则C'+C+A↔C'+C+B → A↔B.
（不过，有定理1和定义1就够证明法则二了）
6个类中，除了1和11是互逆对，空, 0, 01, 10都是自逆的。 肯定可以
页:
1
[2]