Вспомогательные материалы

Примечание: данная статья использует вспомогательные теоремы, такие как “Общий коммутативный закон” и “О количестве подмножеств в данном множестве”. Поскольку мне на данный момент не удалось найти их аналоги на англоязычных ресурсах, я приведу их формулировки в данном разделе.

Теорема “Общий коммутативный закон”: пусть \(G\) – непустое множество, \(+\) – ассоциативная и коммутативная бинарная алгебраическая операция, определённая в G. Тогда для любых элементов \(a_i \in G\), \(i = \overline{1, n}\), \(n \in \mathbb{N}\) ряд \(\alpha_1+\alpha_2+\ldots+\alpha_n\) не меняет своего значения от перестановки слагаемых.

Теорема “О количестве подмножеств в данном множестве”: пусть \(G\) – произвольное конечное множество. Тогда если \(\left| G \right| = n \in \mathbb{N}\) – мощность множества G, то существует \(2^n\) подмножеств в множестве G.

Примечание: XOR, \(\oplus\) (англ. eXclusive OR) – операция сложения по модулю 2.

Вспомогательное определение: XOR-суммой над непустой конечной последовательностью \(\{ \alpha_i \}_{i = 1}^{n}\), где \(\alpha_i \in \{ 0, 1 \}\) – биты, \(i = \overline{1, n}\), \(n \in \mathbb{N}\), называется операция:
\(\oplus { \left( \{ \alpha_i \}_{i = 1}^{n} \right) } = \) \(\alpha_1\) \(\oplus\) \(\alpha_2\) \(\oplus\) \(\ldots\) \(\oplus\) \(\alpha_n\).

Теорема “О количестве XOR-сумм над заданной последовательностью бит”

Формулировка: Пусть задана последовательность бит \(\{ \alpha_i \}_{i = 1}^{n}\) (длины \(n\)), \(\alpha_i \in \{ 0, 1 \}\) \(i = \overline{1, n}\), \(n \in \mathbb{N}\). Тогда существует \(2^{n}-1\) непустых различных последовательностей, составленных из элементов последовательности \(\{ \alpha_i \}_{i = 1}^{n}\), для которых определены соответствующие XOR-суммы.

Доказательство базируется на простом рассмотрении свойств операции XOR. В силу того, что операция XOR \(\oplus\) ассоциативна и коммутативна, она удовлетворяет условиям теоремы “Общий коммутативный закон”. Дополнительно присутствует свойство операции \(\oplus\), именуемое самообратностью: \(a \oplus a = 0\) \(\forall a \in \{0, 1\}\). Следовательно, при выборе последовательности на значение XOR-суммы не влияют порядок выбираемых элементов и элементы, выбранные чётное количество раз (в силу самообратности операции). Но тогда для заданной последовательности \(\{ \alpha_i \}_{i = 1}^{n}\) составленные из её элементов последовательности-операнды имеют представление \(\{ \alpha_i \}_{i \in A \ne \emptyset}^{A \subseteq \{1, 2, \ldots n\}}\). Иными словами, составление последовательности-операнда из элементов заданной последовательности бит эквивалентно выбору подмножества из заданного множества (так как составленные последовательности-операнды представляют из себя последовательности элементов, каждый из которых является уникальным (в силу самообратности операции XOR), и при этом перестановка данных элементов последовательности не влияет на результат, в силу справедливости теоремы “Общий коммутативный закон” для операции XOR, а это означает, что эти последовательности-операнды эквивалентны множествам относительно операции XOR). Теорема “О количестве подмножеств в данном множестве” говорит, что количество подобных выборов равно \(2^{n}\), но в силу того, что данная теорема включает в допустимый выбор подмножеств пустое множество, (а условие теоремы исключает возможную ситуацию), вычтем единицу (пустую последовательность) от общего количества последовательностей. Таким образом, существует ровно \(2^{n}-1\) непустых различных последовательностей, составленных из элементов последовательности \(\{ \alpha_i \}_{i = 1}^{n}\), для которых определены соответствующие XOR-суммы. Теорема доказана.

Следствие: в силу доказанной теоремы, XOR-сумму над подпоследовательностью можно переопределить как XOR-сумму над множеством индексов соответствующих бит последовательности.