تابع بولی متقارن

در ریاضیات، یک تابع بولی متقارن، یک تابع بولی است که مقدار آن به ترتیب بیت های ورودی آن بستگی ندارد، یعنی فقط به تعداد یک ها (یا صفرها) در ورودی بستگی دارد.^[۱]

به همین دلیل آنها را به عنوان توابع شمارش بولی نیز می شناسند.^[۲]

تعداد $2^{(n+1)}$ تابع بولی n متغیره متقارن وجود دارد. به‌جای استفاده از جدول درستی که به‌طور سنتی برای نمایش توابع بولی به کار می‌رود، می‌توان از یک نمایش فشرده‌تر برای یک تابع بولی متقارن n متغیره استفاده کرد: بردار (n+1) تایی که در آن مقدار عنصر i ام (i=0,...,n) برابر با مقدار تابع برای بردار ورودی با i عدد "۱" است. از نظر ریاضی، توابع بولی متقارن به‌طور یک‌به‌یک با توابعی که n+1 عنصر را به دو عنصر $f:\{0,1,...,n\}\rightarrow \{0,1\}$ نگاشت می‌کنند، متناظر هستند.

توابع بولی متقارن برای دسته‌بندی مسائل رضایت‌پذیری بولی استفاده می‌شوند.

موارد خاص

تعدادی از موارد خاص قابل شناسایی هستند:

تابع اکثریت : مقدار این تابع برای بردارهای ورودی با بیش از n/2 عدد "۱"، برابر با ۱ است.
توابع آستانه : مقدار این تابع برای بردارهای ورودی با k یا بیشتر عدد "۱" (برای یک مقدار ثابت k)، برابر با ۱ است.
توابع همه-مساوی و نه-همه-مساوی : مقدار این توابع برابر با ۱ است زمانی که تمام مقادیر ورودی یکسان باشند(نباشند).
توابع شمارش دقیق : مقدار این توابع برای بردارهای ورودی با دقیقاً k عدد "۱" (برای یک مقدار ثابت k)، برابر با ۱ است.
- تابع تک‌فعال یا تابع ۱ در n: مقدار این تابع برابر با ۱ است اگر بردار ورودی دقیقاً یک عدد "۱" داشته باشد.
- تابع تک‌خاموش : مقدار این تابع برابر با ۱ است اگر بردار ورودی دقیقاً یک عدد "۰" داشته باشد.
توابع هم‌نهشتی : مقدار این توابع برابر با ۱ است اگر تعداد اعداد "۱" در بردار ورودی با k مود m (برای k, m ثابت) برابر باشد.
تابع توازن : مقدار این تابع برابر با ۱ است اگر تعداد اعداد "۱" در بردار ورودی فرد باشد.

نسخه‌های n متغیره AND، OR، XOR، NAND، NOR و XNOR نیز توابع بولی متقارن هستند.

ویژگی‌ها

در ادامه، $f_{k}$ نشان‌دهنده مقدار تابع $f:\{0,1\}^{n}\longrightarrow \{0,1\}$ است، هنگامی که به بردار ورودی با وزن k اعمال شود.

وزن

وزن تابع را می‌توان از بردار مقدار آن محاسبه کرد:

$|f|=\sum _{k=0}^{n}{\binom {n}{k}}f_{k}$

فرم نرمال جبری

فرم نرمال جبری یا شامل همه مونو‌میال‌های مربوط به مرتبه خاص m است یا هیچ‌کدام از آن‌ها را شامل نمی‌شود. تبدیل موبیوس ${\widehat {f}}$ این تابع نیز یک تابع متقارن است. بنابراین، این فرم می‌تواند توسط یک بردار ساده (n+1) بیتی، یعنی بردار ANF ${\widehat {f}}_{m}$ توصیف شود. بردارهای ANF و مقدار با رابطه موبیوس به هم مرتبط هستند:

${\widehat {f}}_{m}=\bigoplus _{k_{2}\subseteq m_{2}}f_{k}$

که در آن $k_{2}\subseteq m_{2}$ شامل تمامی وزن‌های k است که نمایش در مبنای ۲ آن‌ها توسط نمایش در مبنای ۲ از m پوشش داده شده است (بر اساس قضیه لوکاس).^[۳]

به‌طور مؤثر، یک تابع بولی متقارن n متغیره متناظر با یک تابع بولی معمولی $\log(n)$ متغیره است که بر روی نمایش در مبنای ۲ وزن ورودی عمل می‌کند.

برای مثال، برای توابع سه‌متغیره:

${\widehat {f}}_{0}=f_{0}$

${\widehat {f}}_{1}=f_{0}\oplus f_{1}$

${\widehat {f}}_{2}=f_{0}\oplus f_{2}$

${\widehat {f}}_{1}=f_{0}\oplus f_{1}\oplus f_{2}\oplus f_{3}$

تابع اکثریت سه‌متغیره با بردار مقدار $(0,0,1,1)$ ، بردار ANF $(0,0,1,0)$ را دارد، یعنی:

$Maj(x,y,z)=xy\oplus xz\oplus yz$

چندجمله‌ای مکعب واحد

ضرایب چندجمله‌ای حقیقی که با تابع در $\{0,1\}^{n}$ مطابقت دارد، به صورت زیر داده می‌شود:

$f_{m}^{*}=\sum _{k=0}^{m}(-1)^{|k|+|m|}{\binom {m}{k}}f_{k}$

برای مثال، چندجمله‌ای تابع اکثریت سه‌متغیره دارای ضرایب $(0,0,1,-2)$ است:

$Maj(x,y,z)=(xy+xz+yz)-2(xyz)$

مثال ها

16 تابع بولی متقارن از سه متغیر
مقادیر تابع				مقادیر بردار	وزن	نام	توضیح غیررسمی	بردار ANF
0	1	2	3	مقادیر بردار	وزن	نام	توضیح غیررسمی	بردار ANF
غ	غ	غ	غ	(0,0,0,0)	0	ثابت نادرست	"هرگز"	(0,0,0,0)
غ	غ	غ	ص	(0,0,0,1)	1	AND سه‌طرفه، آستانه(3)، شمارش(3)	"هر سه"	(0,0,0,1)
غ	غ	ص	غ	(0,0,1,0)	3	شمارش(2)، یک-سرد	"دقیقا دو"	(0,0,1,1)
غ	غ	ص	ص	(0,0,1,1)	4	اکثریت، آستانه(2)	"اکثرأ" و "حداقل دو"	(0,0,1,0)
غ	غ	ص	غ	(0,1,0,0)	3	شمارش(1)، یک-گرم	"دقیقاً یک"	(0,1,0,1)
غ	ص	غ	ص	(0,1,0,1)	4	XOR سه‌طرفه، فرد	"یکی یا سه"	(0,1,0,0)
غ	ص	ص	غ	(0,1,1,0)	6	نابرابر	"یکی یا دو"	(0,1,1,0)
ص	غ	غ	غ	(0,1,1,1)	7	OR سه‌طرفه، آستانه(1)	"هرکدام"، "حداقل یکی"	(0,1,1,1)
ص	غ	غ	غ	(1,0,0,0)	1	NOR سه‌طرفه، شمارش(0)	"هیچکدام"	(1,1,1,1)
ص	غ	غ	ص	(1,0,0,1)	2	کاملاً برابر	"همه یا هیچ"	(1,1,1,0)
ص	غ	ص	غ	(1,0,1,0)	4	XNOR سه‌طرفه، زوج	"هیچ یا دو"	(1,1,0,0)
ص	غ	ص	ص	(1,0,1,1)	5		"نه دقیقا یک"	(1,1,0,1)
ص	ص	غ	غ	(1,1,0,0)	4	قضیه شاخ	"حداکثر یک"	(1,0,1,0)
ص	غ	ص	ص	(1,1,0,1)	5		"نه دقیقا دو"	(1,0,1,1)
ص	ص	ص	غ	(1,1,1,0)	7	NAND سه‌طرفه	"حداکثر رو"	(1,0,0,1)
ص	ص	ص	ص	(1,1,1,1)	8	ثابت درست	"همیشه"	(1,0,0,0)

جستارهای وابسته

تابع متقارن

مراجع

↑ Ingo Wegener, "The Complexity of Symmetric Boolean Functions", in: Computation Theory and Logic, Lecture Notes in Computer Science, vol. 270, 1987, pp. 433–442
↑ "BooleanCountingFunction—Wolfram Language Documentation". reference.wolfram.com. Retrieved 2021-05-25". reference.wolfram.com (به انگلیسی). Retrieved 2024-11-19.
↑ «Canteaut, A.; Videau, M. (2005). "Symmetric Boolean functions"». . IEEE Transactions on Information Theory. 51 (8): 2791–2811. doi:10.1109/TIT.2005.851743. ISSN 1557-9654.

[1] Ingo Wegener, "The Complexity of Symmetric Boolean Functions", in: Computation Theory and Logic, Lecture Notes in Computer Science, vol. 270, 1987, pp. 433–442

[2] "BooleanCountingFunction—Wolfram Language Documentation". reference.wolfram.com. Retrieved 2021-05-25". reference.wolfram.com (به انگلیسی). Retrieved 2024-11-19.

[3] «Canteaut, A.; Videau, M. (2005). "Symmetric Boolean functions"». . IEEE Transactions on Information Theory. 51 (8): 2791–2811. doi:10.1109/TIT.2005.851743. ISSN 1557-9654.

[۱]

[۲]

[۳]