عالمية $ (+، \ Oplus) $ عبر $ \ mathbb {z} _2 ^ n $

Question

دع $ \ mathbb {z} _2 ^ n $ يكون حقل bitvectors من الطول $ n $ وتحديد عامل التشغيل XOR $ \ Oplus $ ، ومشغل الإضافات $ + $ عبر هذا الحقل، مع $ + $ وجود دلائل تجاوز الفائض المعتاد (اتخاذ إضافة معداف $ 2 ^ n $ ).

هل من الممكن التعبير عن أي تعيين $ f: \ mathbb {z} _2 ^ n \ charnarrow \ mathbb {z} _2 ^ n $ بالكامل من حيث $ \ Oplus $ و $ + $ ؟ يبدو أنه قد يكون من الممكن بسبب عدم الخططينية $ + $ .

---

على سبيل المثال، إذا تم إعطاؤنا $ n= 2 $ وهذا $ f (0)= 3، f (1)= 1، f (2)= 3، f (3)= 1 $ ، ثم يمكننا إنشاء $ f $ as $ 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 $ .