01串的增减操作问题

hujunhua

“好像是那么回事，但结论总显得不流畅”

那就用数学归纳法证明一下吧。
假定串是`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_{[n]_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最小非负余数，
`[n]_2`表示取模2最小非负余数. `0_{[n]_2}`当`n`为奇数时为0，当`n`为偶数时为空。
当`n=0`时由规则一不证自明。
当`n=1`时，先运用 "插入111” 将`L_0`加长到不短于`L_1`,
                    然后反复运用`101→0`同步削减`L_0`和`L_1`，
                    直到将`L_1`耗尽，得到`[L_0-L_1]_30`.
                    成立。
当`n=2`时，前已得到`L_00L_1↔[L_0-L_1]_30`, 所以`L_00L_10L_2↔[L_0-L_1]_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`，成立。
所以，对于任意长的串，上述公式都成立。

hujunhua

在得到8#中的不变量之前，如何证明4#中的法则2？

法则2: 若A+C↔B+C，或者C+A↔C+B，则A↔B。这里“+”表示接龙。

法则2是说，两个可能不同但是等价的串，如果同一端有相同的片段，掐去后剩余的两片段仍然等价。

当然，剩余的片段可能与它原来的串不等价了，但两剩余片段保持等价。

如果C↔空，那是显然的，把C代换为空就行了。

对于C不等价于空呢？

hujunhua

为了证明法则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都是自逆的。

lihpb00

肯定可以