01串的增减操作问题

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

肯定可以