نمایش مبدأ برای تمامیت فانکشنال

در [[منطق]]، یک مجموعه کامل فانکشنال از [[رابط منطقی|رابط‌های منطقی]] یا [[تابع بولی|عملگرهای بولین]]، مجموعه ای است که می‌توان با ترکیب اعضای [[مجموعه (ریاضیات)|مجموعه]] در یک عبارت بولین تمام [[جدول ارزش|جدول‌های درستی]] ممکن را به دست آورد.<ref name="Enderton2001">{{citation|last1=Enderton|first1=Herbert|title=A mathematical introduction to logic|publisher=[[Academic Press]]|location=Boston, MA|edition=2nd|isbn=978-0-12-238452-3|year=2001}}. ("Complete set of logical connectives").</ref><ref name="Nolt1998">{{citation|last1=Nolt|first1=John|last2=Rohatyn|first2=Dennis|last3=Varzi|first3=Achille|title=Schaum's outline of theory and problems of logic|publisher=[[McGraw–Hill]]|location=New York|edition=2nd|isbn=978-0-07-046649-4|year=1998}}. ("[F]unctional completeness of [a] set of logical operators").</ref> یک مجموعه معروف کامل از رابط‌ها {AND, NOT} است که شامل [[عطف منطقی|وَ]] و [[نقیض]] باینری می‌شود. هر کدام از مجموعه‌های [[مجموعه تک‌عضوی|تک عضوی]] {[[خط شفر|NAND]]} و {[[نقیض یا|NOR]]} نیز کامل فانکشنال هستند.

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

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

در چارچوب [[حساب گزاره‌ای|منطق گزاره ای]]، مجموعه‌های کامل رابط‌ها، '''کافی (adequate)''' نیز نامیده می‌شوند.<ref name="Smith2003">{{Citation|last=Smith|first=Peter|title=An introduction to formal logic|publisher=[[Cambridge University Press]]|isbn=978-0-521-00804-4|year=2003}}. (Defines "expressively adequate", shortened to "adequate set of connectives" in a section heading.)</ref>

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

== مقدمه ==
متون مدرن منطق معمولاً زیرمجموعه ای از رابط‌ها را اولیه می‌دانند: [[عطف منطقی|وَ]] (<math>\land</math>)؛ [[فصل منطقی|یا]] (<math>\lor</math>)؛ [[نقیض]] (<math>\neg</math>)؛ [[شرطی مادی|شرطی]] (<math>\to</math>)؛ و احتمالاً [[دوشرطی منطقی|دوشرطی]] (<math>\leftrightarrow</math>) در صورت تمایل می‌توان رابط‌های بیشتری را با تعریف آنها بر اساس این رابط‌های اولیه تعریف کرد. به عنوان مثال، NOR (گاهی نشان داده شده با <math>\downarrow</math> ، نقیض یا) را می‌توان به عنوان عطف دو نقیض بیان کرد:
{{وسط‌چین}}
: <math>A \downarrow B := \neg A \land \neg B</math>
{{پایان وسط‌چین}}
به‌طور مشابه، نقیض وَ، NAND (گاهی نشان داده شده با <math>\uparrow</math>)، می‌تواند بر اساس یا و نقیض تعریف شود. هر رابط باینری را می‌توان بر حسب <math>\{ \neg, \land, \lor, \to, \leftrightarrow \}</math>، پس این یک مجموعهٔ کامل است.

با این حال، این مجموعه هنوز شامل بخشی زائد است: یک مجموعه کامل ''مینیمال'' نیست، چرا که دوشرطی و شرطی می‌تواند توسط رابط‌های دیگر تعریف شوند:
{{وسط‌چین}}
: <math>\begin{align}
 A \to B &:= \neg A \lor B\\
 A \leftrightarrow B &:= (A \to B) \land (B \to A).
\end{align}</math>
{{پایان وسط‌چین}}
بنابراین مجموعهٔ کوچکتر <math>\{\neg, \land, \lor\}</math> نیز کامل است اما این مجموعه هنوز حداقل اندازه را ندارد. رابط <math>\lor</math> می‌تواند به این شکل تعریف شود:
{{وسط‌چین}}
: <math>A \lor B := \neg(\neg A \land \neg B).</math>
{{پایان وسط‌چین}}
به‌طور جایگزین، <math>\land</math> ممکن است بر حسب <math>\lor</math> به شکلی مشابه تعریف شود، یا <math>\lor</math> ممکن است بر حسب <math> \rightarrow </math> تعریف شود:
{{وسط‌چین}}
: <math> \ A \vee B := \neg A \rightarrow B. </math>
{{پایان وسط‌چین}}
هیچ ساده‌سازی بیشتر از این امکان‌پذیر نیست. پس، هر مجموعه دو عنصری از روابط شامل رابط <math>\neg</math> و یک رابط از اعضای مجموعه <math>\{\land, \lor, \rightarrow\}</math>، یک [[زیرمجموعه|زیر مجموعه]] کامل مینیمال از مجموعه ی<math>\{\neg, \land, \lor, \to, \leftrightarrow\}</math> می‌سازد.

== تعریف رسمی ==
با در نظر گرفتن دامنه بولین به صورت '''B''' = {۰٬۱}، مجموعه ''F'' از توابع بولین ''ƒ'' <sub>i</sub>: '''B''' <sup>''n <sub>i</sub>''</sup> → '''B''' '''کامل به صورت فانکشنال''' است اگر کلون تولید شده روی '''B''' توسط توابع اساسی ''ƒ<sub>i</sub>'' برای همه [[عدد صحیح|اعداد صحیح]] اکیداً ''مثبت''، شامل تمام توابع ''ƒ:'' '''B''' <sup>''n''</sup> → '''B''' شود. به عبارت دیگر، این مجموعه کامل فانکشنال است اگر هر تابع بولین که حداقل یک متغیر را می‌گیرد بتواند بر حسب توابع ''ƒ'' <sub>i</sub> نشان داده شود. از آنجا که هر تابع بولین شامل لااقل یک متغیر را می‌توان بر حسب توابع بولین باینری نشان داد، ''F'' کامل فانکشنال است اگر و فقط اگر هر تابع بولین باینری را بتوان برحسب توابع در ''F'' بیان کرد.

شرایطی طبیعی تر این خواهد بود که کلون تولید شده توسط ''F''، برای تمام اعداد صحیح {{Nowrap|''n'' ≥ ۰}} از توابع ''ƒ:'' '''B''' <sup>''n''</sup> → '''B''' تشکیل شود. با این حال، مثالهای ذکر شده در بالا با این تعریف قوی تر کامل فانکشنال نیستند زیرا در صورتی که ''F'' خود دارای لااقل یک تابع nullary نباشد، نمی‌توان یک [[آریتی (ریاضی)|تابع nullary]]، یا به عبارت دیگر یک عبارت ثابت را بر حسب ''F'' نوشت. با در نظر گرفتن این تعریف قوی تر، کوچکترین مجموعه‌های کامل فانکشنال دارای ۲ عنصر هستند.

یک شرایط طبیعی دیگر این است که کلون تولید شده توسط ''F'' همراه با دو ثابت nullar کامل فانکشنال، یا در حالت معادل آن کامل فانکشنال به معنای قوی شرح داده شده در پاراگراف قبلی باشد. مثال تابع بولین مشخص شده توسط ''S'' (''x''، ''y'' , ''z'') = ''z'' اگر ''x'' = ''y'' و ''S'' (''x''، ''y'' , ''z'') = ''x'' در غیر این صورت نشان می‌دهد که این شرایط در مقایسه با تمامیت فانکشنال اکیداً ضعیف تر است.<ref name="Wesselkamper1975a">{{Citation|title=A sole sufficient operator|url=http://projecteuclid.org/euclid.ndjfl/1093891614|year=1975|last=Wesselkamper, T.C.|journal=Notre Dame Journal of Formal Logic|volume=16|pages=86–88|doi=10.1305/ndjfl/1093891614}}</ref><ref name="Massey1975">{{Citation|title=Concerning an alleged Sheffer function|url=http://projecteuclid.org/euclid.ndjfl/1093891898|year=1975|last=Massey, G.J.|journal=Notre Dame Journal of Formal Logic|volume=16|pages=549–550|doi=10.1305/ndjfl/1093891898|number=4}}</ref><ref name="Wesselkamper1975b">{{Citation|title=A Correction To My Paper" A. Sole Sufficient Operator|url=http://projecteuclid.org/euclid.ndjfl/1093891899|year=1975|last=Wesselkamper, T.C.|journal=Notre Dame Journal of Formal Logic|volume=16|pages=551|doi=10.1305/ndjfl/1093891899|number=4}}</ref>

== ویژگی‌های تمامیت فانکشنال ==
[[امیل لئون پست|امیل پست]] ثابت کرد که یک مجموعه از رابط‌های منطقی کامل است اگر و فقط اگر زیر مجموعه هیچ‌یک از مجموعه‌های تشکیل شده از رابط‌های زیر نباشد:
* رابط‌های [[تابع یکنوا|یکنواخت]]، تغییر مقدار ارزش هر متغیرهای متصل از '''F''' به '''T''' بدون تغییر هیچ از '''T''' به '''F''' هرگز باعث نمی‌شود که این رابط‌ها مقدار خروجی خود را از '''T''' به '''F''' تغییر دهند، به عنوان مثال : <math>\vee, \wedge, \top, \bot</math>
* رابط‌های [[تبدیل آفین|آفین]]، به طوری که هر متغیر متصل یا همیشه یا هرگز بر ارزش خروجی این رابط‌ها تأثیری نمی‌گذارد، به عنوان مثال: <math>\neg, \top, \bot, \leftrightarrow, \nleftrightarrow</math>
* رابط‌های '''خود دوگانه(self-dual)'''، که برابر [[قوانین دمورگان|دمورگان دوئال]] خود هستند. اگر مقادیر ارزش همه متغیرها معکوس شود، مقدار ارزش خروجی این رابط‌ها نیز معکوس می‌شود، به عنوان مثال: <math>\neg</math> ، ''[[تابع اکثریت|MAJ]]'' (''p''، ''q'' , ''r'').
* رابط‌های '''حافظ حقیقت(truth-preserving)؛''' آن ها[[ارزش درستی|مقدار ارزش]] '''T''' را تحت هر تفسیری که '''T''' را به همه متغیرها نسبت می‌دهد، برمی‌گردانند، به عنوان مثال:<math>\vee, \wedge, \top, \rightarrow, \leftrightarrow</math>
* رابط‌های '''حافظ کذب(falsity-preserving)؛''' آنها مقدار ارزش '''F''' را تحت هر تفسیری که '''F را''' به همه متغیرها اختصاص می‌دهد، برمی‌گردانند، به عنوان مثال: <math>\vee, \wedge, \bot, \nrightarrow, \nleftrightarrow</math>

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

== مجموعه‌های عملگر مینیمال کامل فانکشنال ==
وقتی یک رابط منطقی یا عملگر بولین به تنهایی کامل شود، به آن '''تابع Sheffer'''<ref name="Martin1989">The term was originally restricted to ''binary'' operations, but since the end of the 20th century it is used more generally. {{Citation|title=Systems of logic|year=1989|last=Martin, N.M.|publisher=Cambridge University Press|isbn=978-0-521-36770-7|page=54}}.</ref> یا گاهی اوقات '''عملگر به تنهایی کافی (sole sufficient operator)''' می‌گویند. [[عمل یگانی|عملگر یگانی]] با این ویژگی وجود ندارد. [[خط شفر|NAND]] و [[نقیض یا|NOR]]، که [[جبر بولی|نسبت به یکدیگر دوئال]] هستند، تنها دو تابع باینری شفر هستند. این‌ها توسط[[چارلز سندرز پیرس]] حدود ۱۸۸۰ کشف شدند، اما منتشر نشدند و به‌طور مستقل دوباره کشف و توسط هنری ام شفر در سال ۱۹۱۳ منتشر شد.<ref name="Scharle1965">{{Citation|title=Axiomatization of propositional calculus with Sheffer functors|url=http://projecteuclid.org/euclid.ndjfl/1093958259|year=1965|last=Scharle, T.W.|journal=Notre Dame J. Formal Logic|pages=209–217|volume=6|doi=10.1305/ndjfl/1093958259|number=3}}.</ref> در اصطلاحات الکترونیک دیجیتال، [[دروازه نقیض و|گیت باینری NAND]] و [[دروازه نقیض یا|گیت باینری NOR]] تنها [[دروازه منطقی|گیت‌های منطقی جهانی]] باینری هستند.

مجموعه‌های زیر، مجموعه‌های رابط‌های منطقی کامل فانکشنال مینیمال با [[آریتی (ریاضی)|آریتی]] ≤ ۲ هستند.<ref name="Wernick">Wernick, William (1942) "Complete Sets of Logical Functions," ''Transactions of the American Mathematical Society 51'': 117&#x2013;32. In his list on the last page of the article, Wernick does not distinguish between ← and →, or between <math>\nleftarrow</math> and <math>\nrightarrow</math>.</ref>

; <nowiki>تک عضوی:</nowiki>
: {↑}، {↓}.
;<nowiki> دو عضوی:</nowiki>
: <math>\{\vee, \neg\}</math> ، <math>\{\wedge, \neg\}</math> ، <math>\{\to, \neg\}</math> ، <math>\{\gets, \neg\}</math> ، <math>\{\to, \bot\}</math> ، <math>\{\gets, \bot\}</math> ، <math>\{\to, \nleftrightarrow\}</math> ، <math>\{\gets, \nleftrightarrow\}</math> ، <math>\{\to, \nrightarrow\}</math> ، <math>\{\to, \nleftarrow\}</math> ، <math>\{\gets, \nrightarrow\}</math> ، <math>\{\gets, \nleftarrow\}</math> ، <math>\{\nrightarrow, \neg\}</math> ، <math>\{\nleftarrow, \neg\}</math> ، <math>\{\nrightarrow, \top\}</math> ، <math>\{\nleftarrow, \top\}</math> ، <math>\{\nrightarrow, \leftrightarrow\}</math> ، <math>\{\nleftarrow, \leftrightarrow\}.</math>
;<nowiki> سه عضوی:</nowiki>
: <math>\{\lor, \leftrightarrow, \bot\}</math> ، <math>\{\lor, \leftrightarrow, \nleftrightarrow\}</math> ، <math>\{\lor, \nleftrightarrow, \top\}</math> ، <math>\{\land, \leftrightarrow, \bot\}</math> ، <math>\{\land, \leftrightarrow, \nleftrightarrow\}</math> ، <math>\{\land, \nleftrightarrow, \top\}.</math>

هیچ مجموعه مینیمال بیش از سه رابط منطقی که کامل باشد وجود ندارد.<ref name="Wernick">Wernick, William (1942) "Complete Sets of Logical Functions," ''Transactions of the American Mathematical Society 51'': 117&#x2013;32. In his list on the last page of the article, Wernick does not distinguish between ← and →, or between <math>\nleftarrow</math> and <math>\nrightarrow</math>.</ref> به منظور خواندن لیست‌های بالا، عملگرهایی که یک یا چند ورودی را نادیده می‌گیرند حذف شده‌اند. به عنوان مثال، اپراتوری که ورودی اول را نادیده می‌گیرد و نقیض ورودی دوم را خروجی می‌دهد، می‌تواند جایگزین نقیض غیرمستقیم شود.

== مثال‌ها ==
* نمونه‌هایی از استفاده از تمامیت <code>NAND</code> (↑):<ref>"NAND Gate Operations" at http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html</ref>
** ¬A ≡ A ↑ A
** A &#x2227; B ≡ ¬ (A ↑ B) ≡ (A ↑ B) ↑ (A ↑ B)
** A &#x2228; B ≡ (A ↑ A) ↑ (B ↑ B)
* نمونه‌هایی از استفاده از تمامیت <code>NOR</code> (↓):<ref>"NOR Gate Operations" at http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nor.html</ref>
** ¬A ≡ A ↓ A
** A &#x2228; B ≡ ¬ (A ↓ B) ≡ (A ↓ B) ↓ (A ↓ B)
** A &#x2227; B ≡ (A ↓ A) ↓ (B ↓ B)

توجه داشته باشید که یک [[مدار الکترونیکی]] یا عملکرد نرم‌افزاری را می‌توان با استفاده مجدد، به منظور کاهش تعداد گیت‌ها، بهینه‌سازی کرد. به عنوان مثال، عملیات "A &#x2227; B"، هنگامی که توسط گیت‌های ↑ بیان می‌شود، با استفاده مجدد از "A ↑ B" اجرا می‌شود.
{{وسط‌چین}}
X ≡ (A ↑ B); A &#x2227; B ≡ X ↑ X
{{پایان وسط‌چین}}
== در حوزه‌های دیگر ==
گذشته از رابط‌های منطقی (عملگرهای بولین)، تمامیت را می‌توان در حوزه‌های دیگری نیز تعریف کرد. به عنوان مثال، مجموعه ای از دروازه‌های برگشت‌پذیر، کامل نامیده می‌شوند، اگر بتواند هر عملگر برگشت‌پذیر را بیان کند.

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

در [[رایانش کوانتومی|محاسبات کوانتومی]]، [[تبدیل آدامار|گیت هادامارد]] و [[دروازه‌های منطقی کوانتومی|گیت T]] جهانی هستند، البته با [[دروازه‌های منطقی کوانتومی|تعریف کمی محدود کننده تر]] از تمامیت فانکشنال.

== نظریه مجموعه‌ها ==
بین [[جبر مجموعه‌ها]] و [[جبر بولی]] یک [[یک‌ریختی|ایزومورفیسم]] وجود دارد، و آن این است که آنها ساختار یکسانی دارند. اگر عملگرهای بولی را به عملگرهای مجموعه مپ کنیم، متن ترجمه شده بالا به زبان نظریه مجموعه‌ها، برای مجموعه‌ها نیز معتبر است: بسیاری از «مجموعه‌های مینیمال کامل عملگرهای [[نظریه مجموعه‌ها|نظریه مجموعه ها]]» وجود دارند که می‌توانند هرگونه رابط دیگری را تولید کنند. {¬, &#x2229;} و {¬، &#x222A; } مشهورترین «مجموعه عملگر مینیمال کامل اپراتور» هستند. اگر [[مجموعه جهانی]] [[پارادوکس راسل|ممنوع باشد]]، عملگرهای مجموعه محدود به حفظ کذب (Ø) هستند و نمی‌توانند معادل جبر بولی کامل فانکشنال باشند.

== جستارهای وابسته ==
* [[تمامیت (منطق)]]
* [[جبر مجموعه‌ها]]
* [[جبر بولی]]
* [[ادات شفر|منطق NAND]]

== منابع ==
{{پانویس}}
{{پانویس|۲}}

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