دالة منطقية

يمكن أن يكون للدالة المنطقية مجموعة متنوعة من الخصائص: ^{[ 7 ]}

• الثابت : يكون صحيحًا دائمًا أو خاطئًا دائمًا بغض النظر عن وسيطاته.
• رتيبة : بالنسبة لأي توليفة من قيم الوسائط، فإن تغيير قيمة وسيط من خطأ إلى صواب لا يؤدي إلا إلى تغيير الناتج من خطأ إلى صواب، وليس العكس. يُقال إن الدالة رتيبة بالنسبة لمتغير معين إذا كانت رتيبة بالنسبة للتغيرات في ذلك المتغير.
• الخطي : بالنسبة لكل متغير، فإن قلب قيمة المتغير إما أن يحدث فرقًا دائمًا في قيمة الحقيقة أو لا يحدث فرقًا أبدًا ( دالة التكافؤ ).
• متناظر : القيمة لا تعتمد على ترتيب وسائطها.
• القراءة مرة واحدة : يمكن التعبير عنها باستخدام العطف ، والفصل ، والنفي مع وجود نسخة واحدة من كل متغير.
• متوازنة : إذا احتوى جدول الحقيقة الخاص بها على عدد متساوٍ من الأصفار والآحاد. وزن هامينغ للدالة هو عدد الآحاد في جدول الحقيقة.
• المنحني : جميع مشتقاته متوازنة (طيف الارتباط الذاتي يساوي صفرًا)
• مقاومة الارتباط من الرتبة m : إذا كان الناتج غير مرتبط بجميع التركيبات (الخطية) لأكثر من m وسيطًا
• مراوغ : إذا كان تقييم الدالة يتطلب دائمًا قيمة جميع الوسائط
• تُعتبر الدالة المنطقية دالة شيفر إذا كان من الممكن استخدامها لإنشاء (عن طريق التركيب) أي دالة منطقية عشوائية (انظر اكتمال الوظائف ).
• الدرجة الجبرية للدالة هي رتبة الحد الأحادي الأعلى رتبة في صورته الجبرية الطبيعية

يحاول مفهوم تعقيد الدوائر تصنيف الدوال المنطقية وفقًا لحجم أو عمق الدوائر التي يمكنها حسابها.

يمكن تحليل الدالة البوليانية باستخدام نظرية توسيع بول إلى عوامل شانون الموجبة والسالبة ( توسيع شانون )، وهي الدوال من الرتبة ( k -1) الناتجة عن تثبيت أحد الوسائط (على 0 أو 1). تُعرف الدوال العامة من الرتبة k التي يتم الحصول عليها بفرض قيد خطي على مجموعة من المدخلات (فضاء فرعي خطي) بالدوال الفرعية . ^{[ 8 ]}

المشتقة البوليانية للدالة بالنسبة لأحد وسيطاتها هي دالة من الرتبة ( k -1) تكون صحيحة عندما يكون ناتج الدالة حساسًا لمتغير الإدخال المُختار؛ وهي عملية XOR بين العاملين المرافقين المتناظرين. تُستخدم المشتقة والعامل المرافق في توسيع ريد-مولر . يمكن تعميم هذا المفهوم كمشتقة من الرتبة k في الاتجاه dx، تُحسب كفرق (XOR) بين الدالة عند x و x + dx. ^{[ 8 ]}

تحويل موبيوس ( أو تحويل بول-موبيوس ) لدالة منطقية هو مجموعة معاملات متعددة حدودها ( صيغتها الجبرية العادية )، كدالة لمتجهات أس أحادي الحد. وهو تحويل ذاتي العكس . يمكن حسابه بكفاءة باستخدام خوارزمية الفراشة (" تحويل موبيوس السريع ")، المشابهة لتحويل فورييه السريع . ^{[ 9 ]} الدوال المنطقية المتطابقة تساوي تحويل موبيوس الخاص بها، أي أن قيم جدول الحقيقة (الحد الأدنى) تساوي معاملاتها الجبرية (أحادية الحد). ^{[ 10 ]} يوجد 2^2^( k -1) دالة متطابقة لـ k وسيط. ^{[ 11 ]}

تحويل والش لدالة منطقية هو دالة عددية صحيحة من الرتبة k تُعطي معاملات تحليل إلى دوال خطية ( دوال والش )، وهو مشابه لتحليل الدوال الحقيقية إلى توافقيات بواسطة تحويل فورييه . مربع هذا التحويل هو طيف القدرة أو طيف والش . معامل والش لمتجه بت واحد هو مقياس لارتباط هذا البت بمخرج الدالة المنطقية. تُعرف القيمة القصوى (بالقيمة المطلقة) لمعامل والش بخطية الدالة . ^{[ 8 ]} يُعرف أعلى عدد من البتات (الرتبة) التي تكون فيها جميع معاملات والش تساوي صفرًا (أي الدوال الفرعية متوازنة) بالمرونة ، ويُقال إن الدالة محصنة ضد الارتباط عند هذه الرتبة. ^{[ 8 ]} تلعب معاملات والش دورًا رئيسيًا في تحليل التشفير الخطي .

الارتباط الذاتي للدالة المنطقية هو دالة عددية صحيحة من الرتبة k، تُعطي الارتباط بين مجموعة معينة من التغيرات في المدخلات ومخرجات الدالة. بالنسبة لمتجه بتات مُعطى، يرتبط هذا الارتباط بوزن هامينغ للمشتقة في ذلك الاتجاه. يُعرف معامل الارتباط الذاتي الأقصى (بالقيمة المطلقة) بالمؤشر المطلق . ^{[ 7 ] [ 8 ]} إذا كانت جميع معاملات الارتباط الذاتي تساوي صفرًا (أي أن المشتقات متوازنة) لعدد معين من البتات، يُقال إن الدالة تُحقق معيار الانتشار حتى تلك الرتبة؛ أما إذا كانت جميعها صفرًا، فإن الدالة تُسمى دالة منحنية . ^{[ 12 ]} تلعب معاملات الارتباط الذاتي دورًا رئيسيًا في تحليل التشفير التفاضلي .

ترتبط معاملات والش لدالة منطقية ومعاملات الارتباط الذاتي الخاصة بها بما يعادل نظرية وينر-خينشين ، التي تنص على أن الارتباط الذاتي وطيف القدرة يشكلان زوج تحويل والش. ^{[ 8 ]}

أي دالة منطقية${\displaystyle f(x):\{0,1\}^{n}\rightarrow \{0,1\}}$يمكن تمديدها (استيفاؤها) بشكل فريد إلى المجال الحقيقي بواسطة متعدد الحدود متعدد الخطية في${\displaystyle \mathbb {R} ^{n}}$، تم إنشاؤها عن طريق جمع قيم جدول الحقيقة مضروبة في كثيرات الحدود المؤشرة :$${\displaystyle f^{*}(x)=\sum _{a\in {\{0,1\}}^{n}}f(a)\prod _{i:a_{i}=1}x_{i}\prod _{i:a_{i}=0}(1-x_{i})}$$على سبيل المثال، امتداد دالة XOR الثنائية${\displaystyle x\oplus y}$يكون$${\displaystyle 0(1-x)(1-y)+1x(1-y)+1(1-x)y+0xy}$$وهو ما يساوي$${\displaystyle x+y-2xy}$$ومن الأمثلة الأخرى النفي (${\displaystyle 1-x}$)، و (${\displaystyle xy}$) و أو (${\displaystyle x+y-xy}$عندما تكون جميع المعاملات مستقلة (لا تشترك في أي متغيرات)، يمكن إيجاد الصيغة متعددة الحدود للدالة بتطبيق كثيرات حدود المؤثرات في صيغة منطقية بشكل متكرر. وعند حساب المعاملات بتردد 2 ، نحصل على الصيغة الجبرية العادية ( متعددة حدود زيغالكن ).

يمكن اشتقاق تعابير مباشرة لمعاملات متعددة الحدود عن طريق أخذ مشتقة مناسبة:$${\displaystyle {\begin{array}{lcl}f^{*}(00)&=&(f^{*})(00)&=&f(00)\\f^{*}(01)&=&(\partial _{1}f^{*})(00)&=&-f(00)+f(01)\\f^{*}(10)&=&(\partial _{2}f^{*})(00)&=&-f(00)+f(10)\\f^{*}(11)&=&(\partial _{1}\partial _{2}f^{*})(00)&=&f(00)-f(01)-f(10)+f(11)\\\end{array}}}$$ويمكن تعميم ذلك على أنه عكس موبيوس لمجموعة متجهات البت المرتبة جزئيًا :$${\displaystyle f^{*}(m)=\sum _{a\subseteq m}(-1)^{|a|+|m|}f(a)}$$أين${\displaystyle |a|}$يشير إلى وزن متجه البتات${\displaystyle a}$. عند أخذها بتردد 2، يكون هذا هو تحويل موبيوس البولياني ، مما يعطي معاملات الشكل الطبيعي الجبري :$${\displaystyle {\hat {f}}(m)=\bigoplus _{a\subseteq m}f(a)}$$في كلتا الحالتين، يتم حساب المجموع على جميع متجهات البتات a التي يغطيها m ، أي أن بتات "الواحد" من a تشكل مجموعة فرعية من بتات الواحد من m .

عندما يقتصر المجال على المكعب الفائق ذي الأبعاد n${\displaystyle [0,1]^{n}}$، متعددة الحدود${\displaystyle f^{*}(x):[0,1]^{n}\rightarrow [0,1]}$تُعطي هذه القيمة احتمال الحصول على نتيجة إيجابية عند تطبيق الدالة المنطقية f على n من المتغيرات العشوائية المستقلة ( برنولي )، باحتمالات فردية x . وتُعدّ معضلة التراكم لدوال التكافؤ حالة خاصة من هذه الحقيقة . كما يُمكن استخدام الصيغة متعددة الحدود للدالة المنطقية كامتداد طبيعي لها في المنطق الضبابي .

غالباً ما يتم اعتبار المجال المنطقي كـ${\displaystyle \{-1,1\}}$، حيث يُقابل الخطأ ("0") القيمة 1، والصواب ("1") القيمة -1 (انظر تحليل الدوال المنطقية ). متعدد الحدود المقابل لـ${\displaystyle g(x):\{-1,1\}^{n}\rightarrow \{-1,1\}}$ثم يُعطى بالصيغة التالية:$${\displaystyle g^{*}(x)=\sum _{a\in {\{-1,1\}}^{n}}g(a)\prod _{i:a_{i}=-1}{\frac {1-x_{i}}{2}}\prod _{i:a_{i}=1}{\frac {1+x_{i}}{2}}}$$يُبسط استخدام المجال البولياني المتناظر بعض جوانب التحليل ، حيث أن النفي يُقابل الضرب في -1، والدوال الخطية أحادية الحد (XOR هو الضرب). وبالتالي، يتوافق هذا الشكل متعدد الحدود مع تحويل والش (المعروف أيضًا في هذا السياق بتحويل فورييه ) للدالة (انظر أعلاه). كما أن لكثير الحدود نفس التفسير الإحصائي كما هو الحال في المجال البولياني القياسي، باستثناء أنه يتعامل الآن مع القيم المتوقعة.${\displaystyle E(X)=P(X=1)-P(X=-1)\in [-1,1]}$(انظر إلى نظرية التراكم للحصول على مثال).