تمامیت فانکشنال

در منطق، یک مجموعه کامل فانکشنال از رابط‌های منطقی یا عملگرهای بولین، مجموعه ای است که می‌توان با ترکیب اعضای مجموعه در یک عبارت بولین تمام جدول‌های درستی ممکن را به دست آورد. یک مجموعه معروف کامل از رابط‌ها {AND, NOT} است که شامل وَ و نقیض باینری می‌شود. هر کدام از مجموعه‌های تک عضوی {NAND} و {NOR} نیز کامل فانکشنال هستند.

یک گیت یا مجموعه ای از گیت‌ها که کامل هستند، گیت یا گیت‌های جهانی نیز نامیده می‌شوند.

یک مجموعه کامل از گیت‌ها، ممکن است به عنوان بخشی از محاسبه خود «بیت‌های زباله» را استفاده یا تولید کند که یا بخشی از ورودی نیستند یا بخشی از خروجی سیستم نیستند.

در چارچوب منطق گزاره ای، مجموعه‌های کامل رابط‌ها، کافی (adequate) نیز نامیده می‌شوند.

از نظر الکترونیک دیجیتال، تمامیت تابع به این معنی است که هر گیت منطقی می‌تواند به عنوان شبکه ای از گیت‌های مشخص شده توسط مجموعه ساخته شود. به‌طور خاص، همه گیت‌های منطقی را می‌توان فقط از گیت های NAND باینری، یا فقط از گیت‌های NOR باینری ساخت.

مقدمه

متون مدرن منطق معمولاً زیرمجموعه ای از رابط‌ها را اولیه می‌دانند: وَ ($\wedge$)؛ یا ($\vee$)؛ نقیض ($\mathrm{\neg }$)؛ شرطی ($\to$)؛ و احتمالاً دوشرطی ($\leftrightarrow$) در صورت تمایل می‌توان رابط‌های بیشتری را با تعریف آنها بر اساس این رابط‌های اولیه تعریف کرد. به عنوان مثال، NOR (گاهی نشان داده شده با $\downarrow$ ، نقیض یا) را می‌توان به عنوان عطف دو نقیض بیان کرد: الگو:وسط‌چین

$A\downarrow B:=\mathrm{\neg }A\wedge \mathrm{\neg }B$

الگو:پایان وسط‌چین به‌طور مشابه، نقیض وَ، NAND (گاهی نشان داده شده با $\uparrow$)، می‌تواند بر اساس یا و نقیض تعریف شود. هر رابط باینری را می‌توان بر حسب $\{\mathrm{\neg },\wedge ,\vee ,\to ,\leftrightarrow \}$، پس این یک مجموعهٔ کامل است.

با این حال، این مجموعه هنوز شامل بخشی زائد است: یک مجموعه کامل مینیمال نیست، چرا که دوشرطی و شرطی می‌تواند توسط رابط‌های دیگر تعریف شوند: الگو:وسط‌چین

$\begin{array}{cc}A\to B& :=\mathrm{\neg }A\vee B\\ A\leftrightarrow B& :=(A\to B)\wedge (B\to A).\end{array}$

الگو:پایان وسط‌چین بنابراین مجموعهٔ کوچکتر $\{\mathrm{\neg },\wedge ,\vee \}$ نیز کامل است اما این مجموعه هنوز حداقل اندازه را ندارد. رابط $\vee$ می‌تواند به این شکل تعریف شود: الگو:وسط‌چین

$A\vee B:=\mathrm{\neg }(\mathrm{\neg }A\wedge \mathrm{\neg }B).$

الگو:پایان وسط‌چین به‌طور جایگزین، $\wedge$ ممکن است بر حسب $\vee$ به شکلی مشابه تعریف شود، یا $\vee$ ممکن است بر حسب $\to$ تعریف شود: الگو:وسط‌چین

$A\vee B:=\mathrm{\neg }A\to B.$

الگو:پایان وسط‌چین هیچ ساده‌سازی بیشتر از این امکان‌پذیر نیست. پس، هر مجموعه دو عنصری از روابط شامل رابط $\mathrm{\neg }$ و یک رابط از اعضای مجموعه $\{\wedge ,\vee ,\to \}$، یک زیر مجموعه کامل مینیمال از مجموعه ی$\{\mathrm{\neg },\wedge ,\vee ,\to ,\leftrightarrow \}$ می‌سازد.

تعریف رسمی

با در نظر گرفتن دامنه بولین به صورت B = {۰٬۱}، مجموعه F از توابع بولین ƒ _i: B ^{n _i} → B کامل به صورت فانکشنال است اگر کلون تولید شده روی B توسط توابع اساسی ƒ_i برای همه اعداد صحیح اکیداً مثبت، شامل تمام توابع ƒ: B ⁿ → B شود. به عبارت دیگر، این مجموعه کامل فانکشنال است اگر هر تابع بولین که حداقل یک متغیر را می‌گیرد بتواند بر حسب توابع ƒ _i نشان داده شود. از آنجا که هر تابع بولین شامل لااقل یک متغیر را می‌توان بر حسب توابع بولین باینری نشان داد، F کامل فانکشنال است اگر و فقط اگر هر تابع بولین باینری را بتوان برحسب توابع در F بیان کرد.

شرایطی طبیعی تر این خواهد بود که کلون تولید شده توسط F، برای تمام اعداد صحیح الگو:Nowrap از توابع ƒ: B ⁿ → B تشکیل شود. با این حال، مثالهای ذکر شده در بالا با این تعریف قوی تر کامل فانکشنال نیستند زیرا در صورتی که F خود دارای لااقل یک تابع nullary نباشد، نمی‌توان یک تابع nullary، یا به عبارت دیگر یک عبارت ثابت را بر حسب F نوشت. با در نظر گرفتن این تعریف قوی تر، کوچکترین مجموعه‌های کامل فانکشنال دارای ۲ عنصر هستند.

یک شرایط طبیعی دیگر این است که کلون تولید شده توسط F همراه با دو ثابت nullar کامل فانکشنال، یا در حالت معادل آن کامل فانکشنال به معنای قوی شرح داده شده در پاراگراف قبلی باشد. مثال تابع بولین مشخص شده توسط S (x، y , z) = z اگر x = y و S (x، y , z) = x در غیر این صورت نشان می‌دهد که این شرایط در مقایسه با تمامیت فانکشنال اکیداً ضعیف تر است.

ویژگی‌های تمامیت فانکشنال

امیل پست ثابت کرد که یک مجموعه از رابط‌های منطقی کامل است اگر و فقط اگر زیر مجموعه هیچ‌یک از مجموعه‌های تشکیل شده از رابط‌های زیر نباشد:

• رابط‌های یکنواخت، تغییر مقدار ارزش هر متغیرهای متصل از F به T بدون تغییر هیچ از T به F هرگز باعث نمی‌شود که این رابط‌ها مقدار خروجی خود را از T به F تغییر دهند، به عنوان مثال : $\vee ,\wedge ,\mathrm{\top },\mathrm{\perp }$
• رابط‌های آفین، به طوری که هر متغیر متصل یا همیشه یا هرگز بر ارزش خروجی این رابط‌ها تأثیری نمی‌گذارد، به عنوان مثال: $\mathrm{\neg },\mathrm{\top },\mathrm{\perp },\leftrightarrow ,\nleftrightarrow$
• رابط‌های خود دوگانه(self-dual)، که برابر دمورگان دوئال خود هستند. اگر مقادیر ارزش همه متغیرها معکوس شود، مقدار ارزش خروجی این رابط‌ها نیز معکوس می‌شود، به عنوان مثال: $\mathrm{\neg }$ ، MAJ (p، q , r).
• رابط‌های حافظ حقیقت(truth-preserving)؛ آن هامقدار ارزش T را تحت هر تفسیری که T را به همه متغیرها نسبت می‌دهد، برمی‌گردانند، به عنوان مثال:$\vee ,\wedge ,\mathrm{\top },\to ,\leftrightarrow$
• رابط‌های حافظ کذب(falsity-preserving)؛ آنها مقدار ارزش F را تحت هر تفسیری که F را به همه متغیرها اختصاص می‌دهد، برمی‌گردانند، به عنوان مثال: $\vee ,\wedge ,\mathrm{\perp },\nrightarrow ,\nleftrightarrow$

در واقع، پست توضیحات کاملی از شبکه همه کلون‌ها (مجموعه‌هایی از عملیات بسته نسبت به ترکیب و شامل تمام پیش‌بینی‌ها) در مجموعه دو عنصری {T, F}، که امروزه شبکه پست نامیده می‌شود ارائه داد که نتیجه ساده ای را به دست می‌آورد: پنج مجموعه رابط ذکر شده دقیقاً ماکسیمال کلون‌ها هستند.

مجموعه‌های عملگر مینیمال کامل فانکشنال

وقتی یک رابط منطقی یا عملگر بولین به تنهایی کامل شود، به آن تابع Sheffer یا گاهی اوقات عملگر به تنهایی کافی (sole sufficient operator) می‌گویند. عملگر یگانی با این ویژگی وجود ندارد. NAND و NOR، که نسبت به یکدیگر دوئال هستند، تنها دو تابع باینری شفر هستند. این‌ها توسطچارلز سندرز پیرس حدود ۱۸۸۰ کشف شدند، اما منتشر نشدند و به‌طور مستقل دوباره کشف و توسط هنری ام شفر در سال ۱۹۱۳ منتشر شد. در اصطلاحات الکترونیک دیجیتال، گیت باینری NAND و گیت باینری NOR تنها گیت‌های منطقی جهانی باینری هستند.

مجموعه‌های زیر، مجموعه‌های رابط‌های منطقی کامل فانکشنال مینیمال با آریتی ≤ ۲ هستند.

تک عضوی:

{↑}، {↓}.

دو عضوی:

$\{\vee ,\mathrm{\neg }\}$ ، $\{\wedge ,\mathrm{\neg }\}$ ، $\{\to ,\mathrm{\neg }\}$ ، $\{\leftarrow ,\mathrm{\neg }\}$ ، $\{\to ,\mathrm{\perp }\}$ ، $\{\leftarrow ,\mathrm{\perp }\}$ ، $\{\to ,\nleftrightarrow \}$ ، $\{\leftarrow ,\nleftrightarrow \}$ ، $\{\to ,\nrightarrow \}$ ، $\{\to ,\nleftarrow \}$ ، $\{\leftarrow ,\nrightarrow \}$ ، $\{\leftarrow ,\nleftarrow \}$ ، $\{\nrightarrow ,\mathrm{\neg }\}$ ، $\{\nleftarrow ,\mathrm{\neg }\}$ ، $\{\nrightarrow ,\mathrm{\top }\}$ ، $\{\nleftarrow ,\mathrm{\top }\}$ ، $\{\nrightarrow ,\leftrightarrow \}$ ، $\{\nleftarrow ,\leftrightarrow \}.$

سه عضوی:

$\{\vee ,\leftrightarrow ,\mathrm{\perp }\}$ ، $\{\vee ,\leftrightarrow ,\nleftrightarrow \}$ ، $\{\vee ,\nleftrightarrow ,\mathrm{\top }\}$ ، $\{\wedge ,\leftrightarrow ,\mathrm{\perp }\}$ ، $\{\wedge ,\leftrightarrow ,\nleftrightarrow \}$ ، $\{\wedge ,\nleftrightarrow ,\mathrm{\top }\}.$

هیچ مجموعه مینیمال بیش از سه رابط منطقی که کامل باشد وجود ندارد. به منظور خواندن لیست‌های بالا، عملگرهایی که یک یا چند ورودی را نادیده می‌گیرند حذف شده‌اند. به عنوان مثال، اپراتوری که ورودی اول را نادیده می‌گیرد و نقیض ورودی دوم را خروجی می‌دهد، می‌تواند جایگزین نقیض غیرمستقیم شود.

مثال‌ها

• نمونه‌هایی از استفاده از تمامیت NAND (↑):
  • ¬A ≡ A ↑ A
  • A ∧ B ≡ ¬ (A ↑ B) ≡ (A ↑ B) ↑ (A ↑ B)
  • A ∨ B ≡ (A ↑ A) ↑ (B ↑ B)
• نمونه‌هایی از استفاده از تمامیت NOR (↓):
  • ¬A ≡ A ↓ A
  • A ∨ B ≡ ¬ (A ↓ B) ≡ (A ↓ B) ↓ (A ↓ B)
  • A ∧ B ≡ (A ↓ A) ↓ (B ↓ B)

توجه داشته باشید که یک مدار الکترونیکی یا عملکرد نرم‌افزاری را می‌توان با استفاده مجدد، به منظور کاهش تعداد گیت‌ها، بهینه‌سازی کرد. به عنوان مثال، عملیات "A ∧ B"، هنگامی که توسط گیت‌های ↑ بیان می‌شود، با استفاده مجدد از "A ↑ B" اجرا می‌شود. الگو:وسط‌چین X ≡ (A ↑ B); A ∧ B ≡ X ↑ X الگو:پایان وسط‌چین

در حوزه‌های دیگر

گذشته از رابط‌های منطقی (عملگرهای بولین)، تمامیت را می‌توان در حوزه‌های دیگری نیز تعریف کرد. به عنوان مثال، مجموعه ای از دروازه‌های برگشت‌پذیر، کامل نامیده می‌شوند، اگر بتواند هر عملگر برگشت‌پذیر را بیان کند.

دروازه فردکین ۳ ورودی به خودی خود یک گیت برگشت‌پذیر کامل است - یک عملگر به تنهایی کافی. بسیاری از گیت‌های منطقی جهانی سه ورودی دیگر مانند دروازه Toffoli نیز وجود دارند.

در محاسبات کوانتومی، گیت هادامارد و گیت T جهانی هستند، البته با تعریف کمی محدود کننده تر از تمامیت فانکشنال.

نظریه مجموعه‌ها

بین جبر مجموعه‌ها و جبر بولی یک ایزومورفیسم وجود دارد، و آن این است که آنها ساختار یکسانی دارند. اگر عملگرهای بولی را به عملگرهای مجموعه مپ کنیم، متن ترجمه شده بالا به زبان نظریه مجموعه‌ها، برای مجموعه‌ها نیز معتبر است: بسیاری از «مجموعه‌های مینیمال کامل عملگرهای نظریه مجموعه ها» وجود دارند که می‌توانند هرگونه رابط دیگری را تولید کنند. {¬, ∩} و {¬، ∪ } مشهورترین «مجموعه عملگر مینیمال کامل اپراتور» هستند. اگر مجموعه جهانی ممنوع باشد، عملگرهای مجموعه محدود به حفظ کذب (Ø) هستند و نمی‌توانند معادل جبر بولی کامل فانکشنال باشند.

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

• تمامیت (منطق)
• جبر مجموعه‌ها
• جبر بولی
• منطق NAND