Универсальность $ (+, \ oplus) $ более $ \ mathbb {z} _2 ^ n $

Question

Пусть $ \ mathbb {z} _2 ^ n $ - поле Bitvectors длины $ n $ И определите оператор XOR $ \ Oplus $ и оператор добавления $ + $ на этом поле, С $ + $ имеется обычная семантика переполнения (прокатайте модуль $ 2 ^ n $ ).

Можно ли высказать какое-либо сопоставление $ f: \ mathbb {z} _2 ^ n \ prevarrow \ mathbb {z} _2 ^ n $ полностью с точки зрения $ \ oplus $ и $ + $ ? Похоже, это может быть возможно из-за нелинейности $ + $ .

---

Например, если нам дали $ n= 2 $ и что $ f (0)= 3, f (1)= 1, F (2)= 3, F (3)= 1 $ , то мы могли бы построить $ f $ как <класс span= «Математический контейнер»> $ F (x)= x \ oplus (x + 3) $ .

Answer 1

Нет.Например, вы не можете выразить функцию $ f (x)= x >> 1 $ .В целом наименее значимый бит $ f (x) $ зависит только от наименее значимого бита $ x$ .Вы можете доказать, что по структурной индукции, используя следующие два свойства: $ (A \ Oplus B) \ bmod 2= (A \ bmod 2) \ oplus (b \ bmod 2) $ и $ (a + b) \ bmod 2= (a \ bmod 2) + (b \ bmod 2) \ bmod 2 $ .