دالة الأغلبية

في المنطق البوليني، داله الأغلبية(وتسمى أيضًا المشغل الوسيط) هي وظيفة من مدخلات n إلى مخرج واحد، تكون قيمة العملية خاطئة عندما تكون الوسيطات n / 2 أو أكثر خاطئة، وتكون صحيحة بخلاف ذلك، وبدلاً من ذلك، تمثيل القيم الحقيقية كـ 1 والقيم الخاطئة كـ 0، قد تستخدم

$\langle p_{1},\dots ,p_{n}\rangle =\operatorname {Majority} \left(p_{1},\dots ,p_{n}\right)=\left\lfloor {\frac {1}{2}}+{\frac {\left(\sum _{i=1}^{n}p_{i}\right)-1/2}{n}}\right\rfloor .$

تعمل " − 1/2" في الصيغة على قطع الروابط لصالح الأصفار عندما تكون n زوجية. إذا تم حذف المصطلح " − 1/2"، فيمكننا استخدام الصيغة للدالة التي تقطع الروابط لصالح الروابط الأخرى

تفرض معظم التطبيقات عمدًا عددًا فرديًا من المدخلات حتى لا تضطر إلى التعامل مع ما يحدث عندما تكون نصف المدخلات بالضبط 0 والنصف الآخر يكون 1، غالبًا ما تكون الأنظمة القليلة التي تحسب دالة الأغلبية على عدد زوجي من المدخلات منحازة نحو "0" - فهي تنتج "0" عندما يكون نصف المدخلات بالضبط 0 - على سبيل المثال، بوابة أغلبية ذات 4 مدخلات لها 0 مخرج عندما يظهر صفران أو أكثر عند مدخلاته. في عدد قليل من الأنظمة، يمكن كسر الرابط بشكل عشوائي.

دوائر بوليان

دائره كبرى 3 بت

دائره كبرى3 بت

بوابة الأغلبية هي بوابة منطقية تستخدم في تعقيد الدوائر والتطبيقات الأخرى للدارات المنطقية، تعود بوابة الأغلبية صحيحة إذا كان أكثر من 50٪ من مدخلاتها صحيحة.

على سبيل المثال، في الجوامع الكامله، يتم العثور على ناتج الحمل من خلال تطبيق الدالة الكبرى على المدخلات الثلاثة، على الرغم من أنه في كثير من الأحيان يتم تقسيم هذا الجزء من الأفعى إلى عدة بوابات منطقية أبسط.

تحتوي العديد من الأنظمة على تكرار المعيار الثلاثي؛ يستخدمون وظيفة الأغلبية لفك تشفير منطق الأغلبية لتصحيح الخطأ.

تؤكد النتيجة الرئيسية في تعقيد الدائرة أنه لا يمكن حساب وظيفة الأغلبية بواسطة دارات AC0 ذات الحجم الفرعي الأسي.

الخصائص

للحصول على أي x و y و z، المشغل المتوسط الثلاثي ⟨ x,y, ⟩ يرضي المعادلات التالية.

• ⟨ ص، ⟩ = ذ
• ⟨ ص، ⟩ = ⟨ س، ⟩
• ⟨ ص، ⟩ = ⟨ ض، ⟩
• ⟨ ث، ⟩ ث، ⟩ = ⟨ ث، ذ ⟨ ث، ⟩

النظام المجرد الذي يرضي هذه البديهيات هو الجبر المتوسط.

صيغ روتينيه للأغلبية

بالنسبة إلى n = 1، يكون العامل الوسيط هو عملية الهوية الأحادية x فقط ، بالنسبة إلى n = 3، يمكن التعبير عن العامل الوسيط الثلاثي باستخدام الاقتران والانفصال مثل xy + yz + zx ، من اللافت للنظر أن هذا التعبير يشير إلى نفس العملية بشكل مستقل عما إذا كان الرمز + يُفسر على أنه شامل أو حصري.

بالنسبة إلى n التعسفي، توجد صيغة رتيبة لغالبية الحجم O (n ^5.3). تم إثبات ذلك باستخدام الطريقة الاحتمالية. وبالتالي، فإن هذه الصيغة غير بناءة.

توجد مقاربات لصيغة صريحة لغالبية الحجم كثيرة الحدود:

• خذ الوسيط من شبكة الفرز، حيث يكون كل «سلك» للمقارنة والتبديل عبارة عن بوابة OR وبوابة AND. و Ajtai – Komlós – Szemerédi البناء (AKS) مثال على ذلك.
• اجمع نواتج دوائر الأغلبية الأصغر.
• ألغِ عشوائيًا البرهان الاقوى لصيغة رتيبة.