موضوع مقاله: تمامیت فانکشنال | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # تمامیت فانکشنال | مقدمه: در منطق، یک مجموعه کامل فانکشنال از رابط‌های منطقی یا عملگرهای بولین، مجموعه ای است که می‌توان با ترکیب اعضای مجموعه در یک عبارت بولین تمام جدول‌های درستی ممکن را به دست آورد.. | ## بخش 1: تمامیت فانکشنال | یک گیت یا مجموعه ای از گیت‌ها که کامل هستند، گیت یا گیت‌های جهانی نیز نامیده می‌شوند. یک مجموعه کامل از گیت‌ها، ممکن است به عنوان بخشی از محاسبه خود «بیت‌های زباله» را استفاده یا تولید کند که یا بخشی از ورودی نیستند یا بخشی از خروجی سیستم نیستند. به‌طور خاص، همه گیت‌های منطقی را می‌توان فقط از گیت های NAND باینری، یا فقط از گیت‌های NOR باینری ساخت. مقدمه متون مدرن منطق معمولاً زیرمجموعه ای از رابط‌ها را اولیه می‌دانند: وَ ؛ یا ؛ نقیض ؛ شرطی ؛ و احتمالاً دوشرطی در صورت تمایل می‌توان رابط‌های بیشتری را با تعریف آنها بر اساس این رابط‌های اولیه تعریف کرد. به عنوان مثال، NOR (گاهی نشان داده شده با ، نقیض یا) را می‌توان به عنوان عطف دو نقیض بیان کرد: به‌طور مشابه، نقیض وَ، NAND (گاهی نشان داده شده با )، می‌تواند بر اساس یا و نقیض تعریف شود. با این حال، این مجموعه هنوز شامل بخشی زائد است: یک مجموعه کامل مینیمال نیست، چرا که دوشرطی و شرطی می‌تواند توسط رابط‌های دیگر تعریف شوند: بنابراین مجموعهٔ کوچکتر نیز کامل است اما این مجموعه هنوز حداقل اندازه را ندارد. رابط می‌تواند به این شکل تعریف شود: به‌طور جایگزین، ممکن است بر حسب به شکلی مشابه تعریف شود، یا ممکن است بر حسب تعریف شود: هیچ ساده‌سازی بیشتر از این امکان‌پذیر نیست. پس، هر مجموعه دو عنصری از روابط شامل رابط و یک رابط از اعضای مجموعه ، یک زیر مجموعه کامل مینیمال از مجموعه ی می‌سازد. تعریف رسمی با در نظر گرفتن دامنه بولین به صورت B = {۰٬۱}، مجموعه F از توابع بولین ƒ i: B n i → B کامل به صورت فانکشنال است اگر کلون تولید شده روی B توسط توابع اساسی ƒi برای همه اعداد صحیح اکیداً مثبت، شامل تمام توابع ƒ: B n → B شود. به عبارت دیگر، این مجموعه کامل فانکشنال است اگر هر تابع بولین که حداقل یک متغیر را می‌گیرد بتواند بر حسب توابع ƒ i نشان داده شود. | ## بخش 2: تمامیت فانکشنال | از آنجا که هر تابع بولین شامل لااقل یک متغیر را می‌توان بر حسب توابع بولین باینری نشان داد، F کامل فانکشنال است اگر و فقط اگر هر تابع بولین باینری را بتوان برحسب توابع در F بیان کرد. شرایطی طبیعی تر این خواهد بود که کلون تولید شده توسط F، برای تمام اعداد صحیح از توابع ƒ: B n → 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 تغییر دهند، به عنوان مثال : رابط‌های آفین، به طوری که هر متغیر متصل یا همیشه یا هرگز بر ارزش خروجی این رابط‌ها تأثیری نمی‌گذارد، به عنوان مثال: رابط‌های خود دوگانه(self-dual)، که برابر دمورگان دوئال خود هستند. اگر مقادیر ارزش همه متغیرها معکوس شود، مقدار ارزش خروجی این رابط‌ها نیز معکوس می‌شود، به عنوان مثال: ، MAJ (p، q , r). رابط‌های حافظ حقیقت(truth-preserving)؛ آن هامقدار ارزش T را تحت هر تفسیری که T را به همه متغیرها نسبت می‌دهد، برمی‌گردانند، به عنوان مثال: رابط‌های حافظ کذب(falsity-preserving)؛ آنها مقدار ارزش F را تحت هر تفسیری که F را به همه متغیرها اختصاص می‌دهد، برمی‌گردانند، به عنوان مثال: در واقع، پست توضیحات کاملی از شبکه همه کلون‌ها (مجموعه‌هایی از عملیات بسته نسبت به ترکیب و شامل تمام پیش‌بینی‌ها) در مجموعه دو عنصری {T, F}، که امروزه شبکه پست نامیده می‌شود ارائه داد که نتیجه ساده ای را به دست می‌آورد: پنج مجموعه رابط ذکر شده دقیقاً ماکسیمال کلون‌ها هستند. این‌ها توسطچارلز سندرز پیرس حدود ۱۸۸۰ کشف شدند، اما منتشر نشدند و به‌طور مستقل دوباره کشف و توسط هنری ام شفر در سال ۱۹۱۳ منتشر شد.. | ## بخش 3: تمامیت فانکشنال | در اصطلاحات الکترونیک دیجیتال، گیت باینری NAND و گیت باینری NOR تنها گیت‌های منطقی جهانی باینری هستند. به منظور خواندن لیست‌های بالا، عملگرهایی که یک یا چند ورودی را نادیده می‌گیرند حذف شده‌اند. به عنوان مثال، اپراتوری که ورودی اول را نادیده می‌گیرد و نقیض ورودی دوم را خروجی می‌دهد، می‌تواند جایگزین نقیض غیرمستقیم شود. به عنوان مثال، عملیات "A ∧ B"، هنگامی که توسط گیت‌های ↑ بیان می‌شود، با استفاده مجدد از "A ↑ B" اجرا می‌شود. X ≡ (A ↑ B); A ∧ B ≡ X ↑ X در حوزه‌های دیگر گذشته از رابط‌های منطقی (عملگرهای بولین)، تمامیت را می‌توان در حوزه‌های دیگری نیز تعریف کرد. به عنوان مثال، مجموعه ای از دروازه‌های برگشت‌پذیر، کامل نامیده می‌شوند، اگر بتواند هر عملگر برگشت‌پذیر را بیان کند. دروازه فردکین ۳ ورودی به خودی خود یک گیت برگشت‌پذیر کامل است - یک عملگر به تنهایی کافی. در محاسبات کوانتومی، گیت هادامارد و گیت T جهانی هستند، البته با تعریف کمی محدود کننده تر از تمامیت فانکشنال. نظریه مجموعه‌ها بین جبر مجموعه‌ها و جبر بولی یک ایزومورفیسم وجود دارد، و آن این است که آنها ساختار یکسانی دارند. اگر عملگرهای بولی را به عملگرهای مجموعه مپ کنیم، متن ترجمه شده بالا به زبان نظریه مجموعه‌ها، برای مجموعه‌ها نیز معتبر است: بسیاری از «مجموعه‌های مینیمال کامل عملگرهای نظریه مجموعه ها» وجود دارند که می‌توانند هرگونه رابط دیگری را تولید کنند. | ## جمع‌بندی | اگر مجموعه جهانی ممنوع باشد، عملگرهای مجموعه محدود به حفظ کذب (Ø) هستند و نمی‌توانند معادل جبر بولی کامل فانکشنال باشند.