دالة الأغلبية
بدايةً، في المنطق البوليني، داله الأغلبية(وتسمى كذلك المشغل الوسيط) هي وظيفة من مدخلات n إلى مخرج واحد، تكون قيمة العملية خاطئة عندما تكون الوسيطات n / 2 أو أكثر خاطئة، وتكون صحيحة بخلاف ذلك، وبدلاً من ذلك، تمثيل القيم الحقيقية كـ 1 والقيم الخاطئة كـ 0، قد تستعمل
وعلى صعيد آخر، تفرض أغلب التطبيقات عمدًا عددًا فرديًا من المدخلات حتى لا تضطر إلى التعامل مع ما يحدث عندما تكون نصف المدخلات بالضبط 0 والنصف الآخر يكون 1، غالبًا ما تكون الأنظمة القليلة التي تحسب دالة الأغلبية على عدد زوجي من المدخلات منحازة نحو "0" - فهي تنتج "0" عندما يكون نصف المدخلات بالضبط 0 - مثلًا، بوابة أغلبية ذات 4 مدخلات لها 0 مخرج عندما يظهر صفران أو أكثر عند مدخلاته. في عدد قليل من الأنظمة، يمكن كسر الرابط بشكل عشوائي.
من جهة ثانية، تعمل " − 1/2" في الصيغة على قطع الروابط لصالح الأصفار عندما تكون n زوجية. إذا تم حذف المصطلح " − 1/2"، فيمكننا استخدام الصيغة للدالة التي تقطع الروابط لصالح الروابط الأخرى
الخصائص
وفي هذا السياق، للحصول على أي x و y و z، المشغل المتوسط الثلاثي ⟨ x,y, ⟩ يرضي المعادلات التالية.
⟨ ص، ⟩ = ⟨ س، ⟩
⟨ ص، ⟩ = ذ
⟨ ص، ⟩ = ⟨ ض، ⟩
⟨ ث، ⟩ ث، ⟩ = ⟨ ث، ذ ⟨ ث، ⟩
النظام المجرد الذي يرضي هذه البديهيات هو الجبر المتوسط.
دوائر بوليان
وفي السياق ذاته، تؤكد النتيجة الرئيسية في تعقيد الدائرة أنه لا يمكن حساب وظيفة الأغلبية بواسطة دارات AC0 ذات الحجم الفرعي الأسي.
ومن ناحية أخرى، تحتوي الكثير من الأنظمة على تكرار المعيار الثلاثي؛ يستعملون وظيفة الأغلبية لفك تشفير منطق الأغلبية لتصحيح الخطأ.
وفي هذا الصدد، بوابة الأغلبية هي بوابة منطقية تستعمل في تعقيد الدوائر والتطبيقات الأخرى للدارات المنطقية، تعود بوابة الأغلبية صحيحة إذا كان أكثر من 50٪ من مدخلاتها صحيحة.
إضافةً إلى ذلك، مثلًا، في الجوامع الكامله، يتم العثور على ناتج الحمل من خلال تطبيق الدالة الكبرى على المدخلات الثلاثة، على الرغم من أنه في كثير من الأحيان يتم تقسيم هذا الجزء من الأفعى إلى عدة بوابات منطقية أبسط.
صيغ روتينيه للأغلبية
إضافةً إلى ذلك، خذ الوسيط من شبكة الفرز، حيث يكون كل «سلك» للمقارنة والتبديل عبارة عن بوابة OR وبوابة AND. و Ajtai – Komlós – Szemerédi البناء (AKS) مثال على ذلك.
توجد مقاربات لصيغة صريحة لغالبية الحجم كثيرة الحدود:
اجمع نواتج دوائر الأغلبية الأصغر.
من جانب آخر، بالنسبة إلى n التعسفي، توجد صيغة رتيبة لغالبية الحجم O (n 5.3). تم إثبات ذلك باستخدام الطريقة الاحتمالية. وبالتالي، فإن هذه الصيغة غير بناءة.
في هذا الإطار، بالنسبة إلى n = 1، يكون العامل الوسيط هو عملية الهوية الأحادية x فقط ، بالنسبة إلى n = 3، يمكن التعبير عن العامل الوسيط الثلاثي باستخدام الاقتران والانفصال مثل xy + yz + zx ، من اللافت للنظر أن هذا التعبير يشير إلى نفس العملية بشكل مستقل عما إذا كان الرمز + يُفسر على أنه شامل أو حصري.
ألغِ عشوائيًا البرهان الاقوى لصيغة رتيبة.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟