تابع زوجیت

در جبر بولی، **تابع زوجیت** (Parity Function) به یک تابع بولی گفته می‌شود که مقدار یک دارد، اگر و تنها اگر بردار ورودی دارای تعداد فردی از یک باشد. تابع زوجیت برای دو ورودی، همان تابع یای انحصاری خواهد بود.

تابع زوجیت در بررسی نظری پیچیدگی مدار برای توابع بولی اهمیت دارد.

خروجی یک تابع زوجیت، یک بیت زوجیت است.

## تعریف
تابع زوجیت n-متغیره، یک تابع بولی f: \{0, 1\}^n \rightarrow \{0, 1\} است با خاصیت f(x) = 1 بودن، اگر و تنها اگر تعداد یک ها در بردار x \in \{0, 1\}^n فرد باشد. به عبارت دیگر، f به صورت زیر تعریف می‌شود:f(x)=x_1 \oplus x_2 \oplus ... \oplus x_nکه \oplus نمایانگر یای انحصاری است.

## ویژگی‌ ها
زوجیت تنها وابسته به تعداد یک‌ها است، بنابراین یک تابع بولی متقارن است.

تابع زوجیت n-متغیره و نقیض آن، تنها توابع بولی هستند که همه فرم‌‌های نرمال اجتماعی، بیشینه 2^{n-1} تک جمله ای با طول n را دارند و همه فرم‌‌های نرمال اشتراکی بیشینه 2^{n-1} عبارت با طول n را دارند.

## پیچیدگی محاسباتی
تعدادی از اولین تلاش‌ها در پیچیدگی محاسباتی تابع زوجیت، در حدود سال 1961، توسط بلا سوبوتوفسکایا بود که نشان می‌داد اندازه یک عملگر بولی که زوجیت را محاسبه می‌کند، باید حداقل \Omega(n^{3/2}) باشد. این کار از روش محدودیت‌های تصادفی استفاده می‌کند. توان 3/2 توسط بررسی‌های دقیق توسط مایک پترسون و اوری زویک (1993) به 1.63 و سپس توسط يوهان هوستاد به 2 (1998) افزایش یافت.

در اوایل دهه 1980، مریک فرست، جیمز ساکس و مایکل سیپسر و به صورت جداگانه میکلوس اجتای، کران پایینی بیش از یک چند جمله ای روی اندازه مدار بولی با عمق ثابت پیدا کردند. برای مثال، آنها نشان دادند که مدارهایی با اندازه چندجمله‌ای و عمق ثابت نمی‌توانند تابع زوجیت را محاسبه کنند. نتایج مشابهی برای توابع اکثریت، ضرب و بسته ترانزیتی، با استفاده از کاهش از تابع زوجیت به‌دست آمد.

هوستاد (1987) کران پایینی نمایی روی اندازه مدارهای بولی با عمق ثابت برای تابع زوجیت پیدا کرد. لم تعویض هوستاد ابزار تخصصی کلیدی است که برای این کران‌های پایین استفاده می‌شود. در سال 1994 برای این کار به یوهان هوستاد جایزه گودل داده شد. نتیجه دقیق این است که مدارهای عمق-k با گیت‌های AND، OR و NOT نیاز به اندازه exp(\Omega(n^{1/{k-1}})) دارند تا تابع زوجیت را محاسبه کنند. این تقریباً بهینه در حد نامتناهی است، چون مدارهای عمق-k وجود دارند که زوجیت را محاسبه می‌کنند و دارای اندازه exp(O(n^{1/{k-1}})t) هستند.

## نسخه نامتناهی
تابع زوجیت نامتناهی، یک تابع f:\{0, 1\}^\omega \rightarrow \{0, 1\} است که به هر رشته نامتناهی دودویی، 0 یا 1 اختصاص می‌دهد که ویژگی مقابل را دارد: اگر w و v رشته‌های دودویی نامتناهی باشند که فقط در تعداد محدودی از جایگاه‌ها متفاوت هستند، پس f(w) = f(v) اگر و تنها اگر w و v روی تعداد یکسان از جایگاه‌هایشان متفاوت اند.

با فرض اصل موضوع انتخاب، می‌توان ثابت کرد که توابع زوجیت وجود دارند و تعداد 2^{2^{\aleph_0}} از آنها وجود دارد؛ دقیقا به تعداد تمام توابع از \{0, 1\}^\omega به \{0, 1\}. کافیست برای هر کلاس هم ارزی، رابطه \sim (هم توانی) یک نماینده انتخاب کنیم، که این رابطه به این صورت تعریف شده است: w \sim v اگر w و v در تعداد متناهی از جایگاه‌هایشان متفاوت اند. با این نماینده‌ها، ما می‌توانیم همه آنها را به صفر اختصاص دهیم؛ بقیه f مقدار بدون ابهام نتیجه‌گیری می‌شوند.

یک ساختار دیگر از تابع زوجیت نامتناهی می‌تواند توسط یک اولترافیلتر غیر اصلی U روی \omega تولید شود. وجود اولترافیلترهای غیراصلی روی \omega از اصل موضوع انتخاب تبعیت می‌کند، و کاملا ضعیف تر از آن است. برای هر w: \omega \rightarrow \{0, 1\}، ما مجموعه \}is even A_w = \{n \in \omega \mid \{k \le n \mid w(k)=0\} را در نظر ‌می‌گیریم. تابع زوجیت نامتناهی f با نگاشت w به 0 تعریف می‌شود، اگر و تنها اگر A_w عنصری از اولترافیلتر باشد.

مهم است حداقلی از اصل انتخاب را فرض کنیم تا ثابت کنیم که توابع زوجیت نامتناهی وجود دارند. اگر f یک تابع زوجیت نامتناهی باشد، و ما تصویر وارون f^{-1}[0] را به شکل یک زیرمجموعه از فضای کانتور \{0, 1\}^\omega فرض کنیم، بنابراین f^{-1}[0] یک مجموعه ناشمارا است و ویژگی بایر را ندارد. بدون اصل موضوع انتخاب، نسبت به نظریهٔ مجموعه‌های چرملو–فرنکل سازگار است که تمام زیرمجموعه‌های فضای کانتور شمارا باشند و ویژگی بایر را داشته باشند و بنابراین، هیچ تابع زوجیت نامتناهی موجود نیست. به عنوان مثال، این گزاره در مدل سولووی برقرار است.

## منابع

رده:توابع و نگاشت‌ها
رده:جبر بولی