string - 反向二进制字符串的证明？

Question

如果w : {1...L} → {0,1} 是二进制字符串，则 w 的补码，记为 w ^C，是长度为L的字符串，定义为： w ^c (i) = 1 - w(i ）。w的倒数，表示为 w ^R，是长度为L的字符串，由 w ^R (i) = w(L + 1 - i) 定义。使用这些定义仔细证明，对于每个二进制字符串 x，(x ^C ) ^R = (x ^R ) ^C。

我不知道如何开始这个问题。我真的不想要一个直接的答案我想学习如何通过归纳来回答未来的问题

Answer 1

如果我看到的解决方案是最简单的，那么这是一个相当全面的练习。

我建议您首先证明以下引理：

引理 1： (w0) ^C =(w ^C )1

引理 2： (w0) ^R =0(w ^R )

引理 1 和 2 都可以通过对w的长度进行归纳来证明。严格按照给定的规则去做是乏味的，但不是很难。

通过相同的论点论证以下引理也成立

引理 1b : (w1) ^C =w ^C 0

引理 2b : (w1) ^R =1(w ^R )

有了这些引理，您应该能够解决显示 (x ^C ) ^R =(x ^R ) ^C的原始问题。

对L（即单词的长度）进行归纳。基本情况应该是微不足道的。在归纳步骤中，您最终会得到类似

归纳假设

• (u ^C ) ^R =(u ^R ) ^C。

左显示：

• ((u0) ^C ) ^R =((u0) ^R ) ^C

和（以此类推）

• ((u1) ^C ) ^R =((u1) ^R ) ^C

解决此步骤将涉及上述引理。