تمامیت فانکشنال
در منطق، یک مجموعه کامل فانکشنال از رابط‌های منطقی یا عملگرهای بولین، مجموعه ای است که می‌توان با ترکیب اعضای مجموعه در یک عبارت بولین تمام جدول‌های درستی ممکن را به دست آورد. یک مجموعه معروف کامل از رابط‌ها {AND, NOT} است که شامل وَ و نقیض باینری می‌شود. هر کدام از مجموعه‌های تک عضوی {NAND} و {NOR} نیز کامل فانکشنال هستند.
یک گیت یا مجموعه ای از گیت‌ها که کامل هستند، گیت یا گیت‌های جهانی نیز نامیده می‌شوند.
یک مجموعه کامل از گیت‌ها، ممکن است به عنوان بخشی از محاسبه خود «بیت‌های زباله» را استفاده یا تولید کند که یا بخشی از ورودی نیستند یا بخشی از خروجی سیستم نیستند.
در چارچوب منطق گزاره ای، مجموعه‌های کامل رابط‌ها، کافی (adequate) نیز نامیده می‌شوند.
از نظر الکترونیک دیجیتال، تمامیت تابع به این معنی است که هر گیت منطقی می‌تواند به عنوان شبکه ای از گیت‌های مشخص شده توسط مجموعه ساخته شود. به‌طور خاص، همه گیت‌های منطقی را می‌توان فقط از گیت های NAND باینری، یا فقط از گیت‌های NOR باینری ساخت.
متون مدرن منطق معمولاً زیرمجموعه ای از رابط‌ها را اولیه می‌دانند: وَ (formula_1)؛ یا (formula_2)؛ نقیض (formula_3)؛ شرطی (formula_4)؛ و احتمالاً دوشرطی (formula_5) در صورت تمایل می‌توان رابط‌های بیشتری را با تعریف آنها بر اساس این رابط‌های اولیه تعریف کرد. به عنوان مثال، NOR (گاهی نشان داده شده با formula_6 ، نقیض یا) را می‌توان به عنوان عطف دو نقیض بیان کرد:
به‌طور مشابه، نقیض وَ، NAND (گاهی نشان داده شده با formula_8)، می‌تواند بر اساس یا و نقیض تعریف شود. هر رابط باینری را می‌توان بر حسب formula_9، پس این یک مجموعهٔ کامل است.
با این حال، این مجموعه هنوز شامل بخشی زائد است: یک مجموعه کامل "مینیمال" نیست، چرا که دوشرطی و شرطی می‌تواند توسط رابط‌های دیگر تعریف شوند:
بنابراین مجموعهٔ کوچکتر formula_11 نیز کامل است اما این مجموعه هنوز حداقل اندازه را ندارد. رابط formula_2 می‌تواند به این شکل تعریف شود:
به‌طور جایگزین، formula_1 ممکن است بر حسب formula_2 به شکلی مشابه تعریف شود، یا formula_2 ممکن است بر حسب formula_17 تعریف شود:
هیچ ساده‌سازی بیشتر از این امکان‌پذیر نیست. پس، هر مجموعه دو عنصری از روابط شامل رابط formula_3 و یک رابط از اعضای مجموعه formula_20، یک زیر مجموعه کامل مینیمال از مجموعه یformula_21 می‌سازد.
با در نظر گرفتن دامنه بولین به صورت B = {۰٬۱}، مجموعه "F" از توابع بولین "ƒ" : B → B کامل به صورت فانکشنال است اگر کلون تولید شده روی B توسط توابع اساسی "ƒ" برای همه اعداد صحیح اکیداً "مثبت"، شامل تمام توابع "ƒ:" B → B شود. به عبارت دیگر، این مجموعه کامل فانکشنال است اگر هر تابع بولین که حداقل یک متغیر را می‌گیرد بتواند بر حسب توابع "ƒ" نشان داده شود. از آنجا که هر تابع بولین شامل لااقل یک متغیر را می‌توان بر حسب توابع بولین باینری نشان داد، "F" کامل فانکشنال است اگر و فقط اگر هر تابع بولین باینری را بتوان برحسب توابع در "F" بیان کرد.
شرایطی طبیعی تر این خواهد بود که کلون تولید شده توسط "F"، برای تمام اعداد صحیح از توابع "ƒ:" B → B تشکیل شود. با این حال، مثالهای ذکر شده در بالا با این تعریف قوی تر کامل فانکشنال نیستند زیرا در صورتی که "F" خود دارای لااقل یک تابع nullary نباشد، نمی‌توان یک تابع nullary، یا به عبارت دیگر یک عبارت ثابت را بر حسب "F" نوشت. با در نظر گرفتن این تعریف قوی تر، کوچکترین مجموعه‌های کامل فانکشنال دارای ۲ عنصر هستند.
یک شرایط طبیعی دیگر این است که کلون تولید شده توسط "F" همراه با دو ثابت nullar کامل فانکشنال، یا در حالت معادل آن کامل فانکشنال به معنای قوی شرح داده شده در پاراگراف قبلی باشد. مثال تابع بولین مشخص شده توسط "S" ("x"، "y" , "z") = "z" اگر "x" = "y" و "S" ("x"، "y" , "z") = "x" در غیر این صورت نشان می‌دهد که این شرایط در مقایسه با تمامیت فانکشنال اکیداً ضعیف تر است.
امیل پست ثابت کرد که یک مجموعه از رابط‌های منطقی کامل است اگر و فقط اگر زیر مجموعه هیچ‌یک از مجموعه‌های تشکیل شده از رابط‌های زیر نباشد:
در واقع، پست توضیحات کاملی از شبکه همه کلون‌ها (مجموعه‌هایی از عملیات بسته نسبت به ترکیب و شامل تمام پیش‌بینی‌ها) در مجموعه دو عنصری {T, F}، که امروزه شبکه پست نامیده می‌شود ارائه داد که نتیجه ساده ای را به دست می‌آورد: پنج مجموعه رابط ذکر شده دقیقاً ماکسیمال کلون‌ها هستند.
وقتی یک رابط منطقی یا عملگر بولین به تنهایی کامل شود، به آن تابع Sheffer یا گاهی اوقات عملگر به تنهایی کافی (sole sufficient operator) می‌گویند. عملگر یگانی با این ویژگی وجود ندارد. NAND و NOR، که نسبت به یکدیگر دوئال هستند، تنها دو تابع باینری شفر هستند. این‌ها توسطچارلز سندرز پیرس حدود ۱۸۸۰ کشف شدند، اما منتشر نشدند و به‌طور مستقل دوباره کشف و توسط هنری ام شفر در سال ۱۹۱۳ منتشر شد. در اصطلاحات الکترونیک دیجیتال، گیت باینری NAND و گیت باینری NOR تنها گیت‌های منطقی جهانی باینری هستند.
مجموعه‌های زیر، مجموعه‌های رابط‌های منطقی کامل فانکشنال مینیمال با آریتی ≤ ۲ هستند.هیچ مجموعه مینیمال بیش از سه رابط منطقی که کامل باشد وجود ندارد. به منظور خواندن لیست‌های بالا، عملگرهایی که یک یا چند ورودی را نادیده می‌گیرند حذف شده‌اند. به عنوان مثال، اپراتوری که ورودی اول را نادیده می‌گیرد و نقیض ورودی دوم را خروجی می‌دهد، می‌تواند جایگزین نقیض غیرمستقیم شود.توجه داشته باشید که یک مدار الکترونیکی یا عملکرد نرم‌افزاری را می‌توان با استفاده مجدد، به منظور کاهش تعداد گیت‌ها، بهینه‌سازی کرد. به عنوان مثال، عملیات "A ∧ B"، هنگامی که توسط گیت‌های ↑ بیان می‌شود، با استفاده مجدد از "A ↑ B" اجرا می‌شود.
X ≡ (A ↑ B); A ∧ B ≡ X ↑ X
گذشته از رابط‌های منطقی (عملگرهای بولین)، تمامیت را می‌توان در حوزه‌های دیگری نیز تعریف کرد. به عنوان مثال، مجموعه ای از دروازه‌های برگشت‌پذیر، کامل نامیده می‌شوند، اگر بتواند هر عملگر برگشت‌پذیر را بیان کند.
دروازه فردکین ۳ ورودی به خودی خود یک گیت برگشت‌پذیر کامل است - یک عملگر به تنهایی کافی. بسیاری از گیت‌های منطقی جهانی سه ورودی دیگر مانند دروازه Toffoli نیز وجود دارند.
در محاسبات کوانتومی، گیت هادامارد و گیت T جهانی هستند، البته با تعریف کمی محدود کننده تر از تمامیت فانکشنال.
بین جبر مجموعه‌ها و جبر بولی یک ایزومورفیسم وجود دارد، و آن این است که آنها ساختار یکسانی دارند. اگر عملگرهای بولی را به عملگرهای مجموعه مپ کنیم، متن ترجمه شده بالا به زبان نظریه مجموعه‌ها، برای مجموعه‌ها نیز معتبر است: بسیاری از «مجموعه‌های مینیمال کامل عملگرهای نظریه مجموعه ها» وجود دارند که می‌توانند هرگونه رابط دیگری را تولید کنند. {¬, ∩} و {¬، ∪ } مشهورترین «مجموعه عملگر مینیمال کامل اپراتور» هستند. اگر مجموعه جهانی ممنوع باشد، عملگرهای مجموعه محدود به حفظ کذب (Ø) هستند و نمی‌توانند معادل جبر بولی کامل فانکشنال باشند.