تابع اکثریت
تابع اکثریت (به انگلیسی: Majority function)
در منطق بولی، تابع اکثریت (تابع میانه نیز نامیده میشود) تابعی است با N ورودی به یک خروجی. مقدار عملگر صفر (False) خواهد بود اگر پنجاه درصد یا بیش از پنجاه درصد آرگومنتها صفر(False) باشد و برعکس. در فرمول زیر این مورد بیان شده است
مقدار ۱/۲- در فرمول برای شکستن ورودیها به ترتیب صفرها وقتی که n زوج است بکار میرود، اگر از مقدار ۱/۲- صرفنظر شود برای دسته بندی یکها بکار میرود.
مدارهای بولی
یک گیت اکثریت یک دروازهٔ منطقی است که در مدارات پیچیده و دیگر کاربردها در مدارهای بولی استفاده میشود. دروازهٔ اکثریت مقدار صحیح را بر میگرداند اگر و فقط اگر پنجاه درصد یا بیشتر مقدارهای ورودی صحیح باشد. به عنوان مثال، در یک تمام جمعکننده خروجی نقلی با اعمال یک تابع اکثریت با سه ورودی پیدا خواهد شد. همچنین با اعمال چند دروازهٔ منطقی تکرار این بخش را میتوان سادهتر کرد. نتیجهٔ اکثریت در مدارات پیچیده بیان میکند که تابع اکثریت نمیتواند با استفاده از مدار AC0 با سایز sub exponential محاسبه شود.
فرمول تکرار (یکنواخت) برای تابع اکثریت
برای n=۱ عملگر میانه (اکثریت) یک عملیات شناسایی یگانه x است. برای n=۳ عملگر سهگانهٔ میانه میتواند با استفاده از ارتباط و گسست به فرم
ویژگیها
برای سه متغیر 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.