تابع اکثریت

تابع اکثریت (به انگلیسی: Majority function) در منطق بولی، تابع اکثریت (تابع میانه نیز نامیده می‌شود) تابعی است با N ورودی به یک خروجی. مقدار عملگر صفر (False) خواهد بود اگر پنجاه درصد یا بیش از پنجاه درصد آرگومنت‌ها صفر(False) باشد و برعکس. در فرمول زیر این مورد بیان شده است

$\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$

مقدار ۱/۲- در فرمول برای شکستن ورودی‌ها به ترتیب صفرها وقتی که n زوج است بکار می‌رود، اگر از مقدار ۱/۲- صرفنظر شود برای دسته بندی یک‌ها بکار می‌رود.

مدارهای بولی

یک گیت اکثریت یک دروازهٔ منطقی است که در مدارات پیچیده و دیگر کاربردها در مدارهای بولی استفاده می‌شود. دروازهٔ اکثریت مقدار صحیح را بر می‌گرداند اگر و فقط اگر پنجاه درصد یا بیشتر مقدارهای ورودی صحیح باشد. به عنوان مثال، در یک تمام جمع‌کننده خروجی نقلی با اعمال یک تابع اکثریت با سه ورودی پیدا خواهد شد. همچنین با اعمال چند دروازهٔ منطقی تکرار این بخش را می‌توان ساده‌تر کرد. نتیجهٔ اکثریت در مدارات پیچیده بیان می‌کند که تابع اکثریت نمی‌تواند با استفاده از مدار AC0 با سایز sub exponential محاسبه شود.

فرمول تکرار (یکنواخت) برای تابع اکثریت

برای n=۱ عملگر میانه (اکثریت) یک عملیات شناسایی یگانه x است. برای n=۳ عملگر سه‌گانهٔ میانه می‌تواند با استفاده از ارتباط و گسست به فرم $xy+yz+zx$ بیان شود. پرواضح است که این فرم بیان می‌کند مستقلاً برای عملگرهای مشابه نماد + از Exclusive Or یا Inclusive or نشات گرفته می‌شود. برای یک n دلخواه، یک فرمول تکرار (یکنواخت) برای اکثریت با سایز O(n5.3) وجود دارد. این با استفاده از روش احتمالات ثابت می‌شود. در نتیجه این یک فرمول غیرساختگی است. هرچند می‌توان با استفاده از شبکهٔ بخش‌بندی از "Ajtai, Komlos" و "Szemeredi" یک فرمول روشن و مشخص برای اکثریت بدست آورد.

ویژگی‌ها

برای سه متغیر 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>>

منابع

Valiant, L. (1984). "Short monotone formulae for the majority function". Journal of Algorithms 5 (3): 363–366. doi:10.1016/0196-6774(84)90016-6.. Knuth, Donald E. (2008). Introduction to combinatorial algorithms and Boolean functions. The Art of Computer Programming 4a. Upper Saddle River, NJ: Addison-Wesley. pp. 64–74. ISBN 0-321-53496-4.