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

في المنطق البولياني ، دالة الأغلبية (وتسمى أيضًا عامل الوسيط ) هي الدالة البوليانية التي تُقيّم إلى خطأ عندما يكون نصف الوسائط أو أكثر خطأ، وصواب خلاف ذلك، أي أن قيمة الدالة تساوي قيمة أغلبية المدخلات.

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

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

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

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

بالنسبة لأي x و y و z ، فإن عامل الوسيط الثلاثي ⟨ x , y , z ⟩ يحقق المعادلات التالية.

• ⟨ x , y , y ⟩ = y
• ⟨ x , y , z ⟩ = ⟨ z , x , y ⟩
• ⟨ x , y , z ⟩ = ⟨ x , z , y ⟩
• ⟨ ⟨ x , w , y ⟩ , w , z ⟩ = ⟨ x , w , ⟨ y , w , z ⟩ ⟩

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

تشمل الخصائص المفيدة الأخرى لدالة الوسيط الثلاثي ما يلي:

• بفرض أن ⟨ x , y , z ⟩ = w ، ⟨ x , y , w ⟩ = z
• ⟨ ¬x , ¬y , ¬z ⟩ = ¬ ⟨ x , y , z ⟩
• ⟨ س , ص , س ⊕ ص ⊕ ض ⟩ = ⟨ س , ص , ¬ض ⟩
• ⟨ ¬x , y , x ⊕ y ⊕ z ⟩ = ⟨ ¬x , y , z ⟩

تُجبر معظم التطبيقات عمدًا على استخدام عدد فردي من المدخلات لتجنب التعامل مع مسألة ما يحدث عندما يكون نصف المدخلات صفرًا والنصف الآخر واحدًا. أما الأنظمة القليلة التي تحسب دالة الأغلبية على عدد زوجي من المدخلات، فغالبًا ما تكون منحازة نحو الصفر، أي أنها تُنتج الصفر عندما يكون نصف المدخلات صفرًا. على سبيل المثال، بوابة الأغلبية ذات الأربعة مدخلات تُنتج مخرجًا صفريًا فقط عندما يظهر صفران أو أكثر في مدخلاتها. ^{[ 1 ]} في بعض الأنظمة، يمكن حسم التعادل عشوائيًا. ^{[ 2 ]}

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

لأي قيمة n، توجد صيغة رتيبة للأغلبية بحجم O( n ≤ ^5.3 ). وقد تم إثبات ذلك باستخدام الطريقة الاحتمالية . وبالتالي، فإن هذه الصيغة غير بنائية. ^{[ 3 ]}

توجد طرق لإيجاد صيغة صريحة لحجم معظم كثيرات الحدود:

• خذ الوسيط من شبكة فرز ، حيث كل "سلك" للمقارنة والتبديل هو ببساطة بوابة OR وبوابة AND. بنية Ajtai – Komlós – Szemerédi (AKS) مثال على ذلك.
• اجمع مخرجات دوائر الأغلبية الأصغر. ^{[ 4 ]}
• إزالة العشوائية من برهان فاليانت لصيغة رتيبة. ^{[ 5 ]}

• الجبر البولياني (البنية)
• الجبر البولياني المعرف بشكل أساسي
• خوارزمية التصويت بالأغلبية لبوير-مور
• مشكلة الأغلبية (الأتمتة الخلوية)

• كنوت، دونالد إي. (2008). مقدمة في الخوارزميات التوافقية والدوال البولية . فن برمجة الحاسوب . المجلد  4أ. أبر سادل ريفر، نيوجيرسي: أديسون-ويسلي. الصفحات 64-74 . ISBN  978-0-321-53496-5.

الوسائط المتعلقة بوظائف الأغلبية على ويكيميديا ​​كومنز