هذه المقالة يتيمة. ساعد بإضافة وصلة إليها في مقالة متعلقة بها

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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى التنقل اذهب إلى البحث

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

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

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

دوائر بوليان[عدل]

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

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

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

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

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

الخصائص[عدل]

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

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

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

صيغ روتينيه للأغلبية[عدل]

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

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

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

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

ملاحظات[عدل]

 

  1. ^ Peterson, William Wesley; Weldon, E.J. (1972). Error-correcting Codes. MIT Press. ISBN 9780262160391. الوسيط |CitationClass= تم تجاهله (مساعدة)
  2. ^ Chaouiya, Claudine; Ourrad, Ouerdia; Lima, Ricardo (July 2013). "Majority Rules with Random Tie-Breaking in Boolean Gene Regulatory Networks". PLoS ONE. 8 (7). Public Library of Science. doi:10.1371/journal.pone.0069626. الوسيط |CitationClass= تم تجاهله (مساعدة)
  3. ^ Valiant, Leslie (1984). "Short monotone formulae for the majority function". Journal of Algorithms. 5 (3): 363–366. doi:10.1016/0196-6774(84)90016-6. الوسيط |CitationClass= تم تجاهله (مساعدة)
  4. ^ Amano, Kazuyuki (2018). "Depth Two Majority Circuits for Majority and List Expanders". Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. 117 (81): 1–13. doi:10.4230/LIPIcs.MFCS.2018.81. الوسيط |CitationClass= تم تجاهله (مساعدة)
  5. ^ Hoory, Shlomo; Magen, Avner; Pitassi, Toniann (2006). "Monotone Circuits for the Majority Function". Springer (باللغة الإنجليزية): 410–425. doi:10.1007/11830924_38. مؤرشف من الأصل في 17 أبريل 2021. الوسيط |CitationClass= تم تجاهله (مساعدة)

مراجع[عدل]

  • Knuth, Donald E. (2008). Introduction to combinatorial algorithms and Boolean functions. 4a. Upper Saddle River, NJ: Addison-Wesley. صفحات 64–74. ISBN 0-321-53496-4. الوسيط |CitationClass= تم تجاهله (مساعدة)

انظر أيضًا[عدل]

  • الجبر البوليني (هيكل)
  • تعريف الجبر المنطقي قانونيًا
  • بوير مور خوارزمية تصويت الأغلبية
  • مشكلة الأغلبية (الجهاز الخلوي)