اكتمال الوظائف

في المنطق ، تُعرَّف المجموعة الكاملة وظيفيًا من الروابط المنطقية أو عوامل التشغيل البوليانية بأنها تلك التي يمكن استخدامها للتعبير عن جميع جداول الصواب الممكنة من خلال دمج عناصر المجموعة في تعبير بولياني . ^{[ 1 ] [ 2 ]} ومن أشهر مجموعات الروابط الكاملة {AND, NOT}. كل من المجموعتين { NAND } و { NOR } كاملتان وظيفيًا . أما المجموعة { AND , OR } فهي غير كاملة، نظرًا لعدم قدرتها على التعبير عن النفي.

يمكن أيضًا تسمية البوابة (أو مجموعة البوابات) التي تكون كاملة وظيفيًا بالبوابة الشاملة (أو مجموعة البوابات الشاملة).

في سياق منطق القضايا ، تسمى المجموعات الكاملة وظيفيًا من الروابط أيضًا ( تعبيريًا ) كافية . ^{[ 3 ]}

من منظور الإلكترونيات الرقمية ، تعني الاكتمال الوظيفي إمكانية تحقيق كل بوابة منطقية ممكنة كشبكة من البوابات من الأنواع المحددة في المجموعة. وعلى وجه الخصوص، يمكن تجميع جميع البوابات المنطقية إما من بوابات NAND الثنائية فقط، أو من بوابات NOR الثنائية فقط .

تعتبر النصوص الحديثة في المنطق عادةً مجموعة فرعية من الروابط المنطقية أساسية: العطف (${\displaystyle \land }$); الفصل (${\displaystyle \lor }$النفي (​${\displaystyle \neg }$); شرط مادي (${\displaystyle \to }$)؛ وربما الشرط الثنائي (${\displaystyle \leftrightarrow }$يمكن تعريف روابط إضافية، إذا رغبنا في ذلك، بتعريفها بدلالة هذه الروابط الأساسية. على سبيل المثال، NOR (نفي الفصل، ويُشار إليه أحيانًا بـ${\displaystyle \downarrow }$يمكن التعبير عن ) كربط بين نفيين:

${\displaystyle A\downarrow B:=\neg A\land \neg B}$

وبالمثل، فإن نفي العطف، NAND (يُشار إليه أحيانًا بـ${\displaystyle \uparrow }$يمكن تعريف الروابط الثنائية من حيث الفصل والنفي. ويمكن تعريف كل رابط ثنائي من حيث${\displaystyle \{\neg ,\land ,\lor ,\to ,\leftrightarrow \}}$وهذا يعني أن هذه المجموعة كاملة وظيفيًا. ومع ذلك، فهي تحتوي على تكرار: هذه المجموعة ليست مجموعة كاملة وظيفيًا دنيا ، لأن الشرطية والشرطية الثنائية يمكن تعريفهما بدلالة الروابط الأخرى كما يلي:

${\displaystyle {\begin{aligned}A\to B&:=\neg A\lor B\\A\leftrightarrow B&:=(A\to B)\land (B\to A).\end{aligned}}}$

ويترتب على ذلك أن المجموعة الأصغر${\displaystyle \{\neg ,\land ,\lor \}}$وهي أيضًا مكتملة وظيفيًا. (وقد تم إثبات اكتمالها الوظيفي أيضًا بواسطة نظرية الشكل الطبيعي الانفصالي .) ^{[ 4 ]} ولكن هذا لا يزال غير أدنى، حيث${\displaystyle \lor }$يمكن تعريفها على النحو التالي:

${\displaystyle A\lor B:=\neg (\neg A\land \neg B).}$

بدلاً عن ذلك،${\displaystyle \land }$يمكن تعريفها من حيث${\displaystyle \lor }$بطريقة مماثلة، أو${\displaystyle \lor }$يمكن تعريفها من حيث${\displaystyle \rightarrow }$:

${\displaystyle \ A\vee B:=\neg A\rightarrow B.}$

لا يمكن إجراء أي تبسيطات أخرى. وبالتالي، فإن كل مجموعة من عنصرين من الروابط تحتوي على${\displaystyle \neg }$وواحد من${\displaystyle \{\land ,\lor ,\rightarrow \}}$هي مجموعة فرعية وظيفية كاملة دنيا من${\displaystyle \{\neg ,\land ,\lor ,\to ,\leftrightarrow \}}$.

بالنظر إلى المجال البولياني B = {0, 1} ، فإن مجموعة الدوال البوليانية fᵢ : ^_Bⱼᵢ → B تُعتبر كاملة _{وظيفيًا} إذا احتوى الاستنساخ  على B الناتج عن الدوال الأساسية fᵢ على _جميع الدوال fᵢ  : Bⱼᵢ ^→ B ، لجميع الأعداد الصحيحة الموجبة تمامًا n ^≥ 1. بعبارة أخرى، تكون المجموعة كاملة وظيفيًا إذا أمكن التعبير عن كل دالة بوليانية تأخذ متغيرًا واحدًا على الأقل بدلالة الدوال fᵢ _. وبما أنه يمكن التعبير عن كل دالة بوليانية لمتغير واحد على الأقل بدلالة الدوال البوليانية الثنائية، فإن F تكون كاملة وظيفيًا إذا وفقط إذا أمكن التعبير عن كل دالة بوليانية ثنائية بدلالة الدوال في F.

الشرط الأكثر طبيعية هو أن تتكون المجموعة المستنسخة المولدة بواسطة F من جميع الدوال f  : B ⁿ → B ، لجميع الأعداد الصحيحة n ≥ 0. مع ذلك، فإن الأمثلة المذكورة أعلاه ليست كاملة وظيفيًا بهذا المعنى الأدق، لأنه لا يمكن كتابة دالة صفرية ، أي تعبير ثابت، بدلالة F إذا لم تحتوي F نفسها على دالة صفرية واحدة على الأقل. وفقًا لهذا التعريف الأدق، فإن أصغر المجموعات الكاملة وظيفيًا ستحتوي على عنصرين.

من الشروط الطبيعية الأخرى أن يكون المستنسخ الناتج عن الدالة F ، بالإضافة إلى دالتي الثابت الصفري، مكتملًا وظيفيًا، أو مكافئًا له، مكتملًا وظيفيًا بالمعنى الدقيق للفقرة السابقة. ويُبين مثال الدالة البوليانية المعطاة بالصيغة S ( x , y , z ) = z إذا كان x = y، و S ( x , y , z ) = x فيما عدا ذلك، أن هذا الشرط أضعف بكثير من الاكتمال الوظيفي. ^{[ 5 ] [ 6 ] [ 7 ]}

أثبت إميل بوست أن مجموعة الروابط المنطقية تكون كاملة وظيفيًا إذا وفقط إذا لم تكن مجموعة فرعية من أي من مجموعات الروابط التالية:

• الروابط الرتيبة ؛ تغيير قيمة الصواب لأي متغير متصل من خطأ إلى صواب دون تغيير أي متغير من صواب إلى خطأ لا يؤدي أبدًا إلى تغيير قيمة الإرجاع لهذه الروابط من صواب إلى خطأ ، على سبيل المثال${\displaystyle \vee ,\wedge ,\top ,\bot }$.
• الروابط الخطية ، بحيث يؤثر كل متغير متصل إما دائمًا أو لا يؤثر أبدًا على قيمة الصواب التي تُرجعها هذه الروابط، على سبيل المثال${\displaystyle \neg ,\top ,\bot ,\leftrightarrow ,\nleftrightarrow }$.
• الروابط الذاتية المزدوجة ، والتي تساوي ثنائيتها من نوع دي مورغان ؛ إذا عُكست قيم الصواب لجميع المتغيرات، فإن قيمة الصواب التي تُرجعها هذه الروابط ستُعكس أيضًا، على سبيل المثال${\displaystyle \neg }$، maj ( p , q , r ) .
• الروابط التي تحافظ على الصدق ؛ فهي تُعيد قيمة الصدق T في أي تفسير يُسند T إلى جميع المتغيرات، على سبيل المثال${\displaystyle \vee ,\wedge ,\top ,\rightarrow ,\leftrightarrow }$.
• الروابط التي تحافظ على الزيف ؛ فهي تُعيد قيمة الصواب F تحت أي تفسير يُسند F إلى جميع المتغيرات، على سبيل المثال${\displaystyle \vee ,\wedge ,\bot ,\nrightarrow ,\nleftrightarrow }$.

قدّم بوست وصفًا كاملاً لشبكة جميع المستنسخات ( مجموعات العمليات المغلقة تحت التركيب والتي تحتوي على جميع الإسقاطات) على المجموعة المكونة من عنصرين { T , F } ، والتي تُسمى اليوم شبكة بوست ، مما يستلزم النتيجة المذكورة أعلاه كنتيجة بسيطة: مجموعات الروابط الخمس المذكورة هي بالضبط المستنسخات غير التافهة القصوى. ^{[ 8 ]}

عندما يكون رابط منطقي واحد أو عامل بولياني مكتملًا وظيفيًا بذاته، يُطلق عليه اسم دالة شيفر ^{[ 9 ]} أو أحيانًا عامل كافٍ وحيد . لا توجد عوامل أحادية بهذه الخاصية. بوابتا NAND و NOR ، وهما دالتان ثنائيتان ، هما دالتا شيفر الثنائيتان الوحيدتان. اكتشفهما تشارلز ساندرز بيرس حوالي عام 1880، لكنهما لم ينشرا، ثم أعاد هنري إم. شيفر اكتشافهما بشكل مستقل ونشرهما عام 1913. ^{[ 10 ]} في مصطلحات الإلكترونيات الرقمية، تُعد بوابة NAND الثنائية (↑) وبوابة NOR الثنائية (↓) بوابتي المنطق العالميتين الثنائيتين الوحيدتين .

فيما يلي الحد الأدنى من المجموعات الكاملة وظيفيًا للروابط المنطقية ذات عدد المعاملات ≤  2: ^{[ 11 ]}

عنصر واحد

{↑}, {↓}.

عنصران

${\displaystyle \{\vee ,\neg \}}$،${\displaystyle \{\wedge ,\neg \}}$،${\displaystyle \{\to ,\neg \}}$،${\displaystyle \{\gets ,\neg \}}$،${\displaystyle \{\to ,\bot \}}$،${\displaystyle \{\gets ,\bot \}}$،${\displaystyle \{\to ,\nleftrightarrow \}}$،${\displaystyle \{\gets ,\nleftrightarrow \}}$،${\displaystyle \{\to ,\nrightarrow \}}$،${\displaystyle \{\to ,\nleftarrow \}}$،${\displaystyle \{\gets ,\nrightarrow \}}$،${\displaystyle \{\gets ,\nleftarrow \}}$،${\displaystyle \{\nrightarrow ,\neg \}}$،${\displaystyle \{\nleftarrow ,\neg \}}$،${\displaystyle \{\nrightarrow ,\top \}}$،${\displaystyle \{\nleftarrow ,\top \}}$،${\displaystyle \{\nrightarrow ,\leftrightarrow \}}$،${\displaystyle \{\nleftarrow ,\leftrightarrow \}.}$

ثلاثة عناصر

${\displaystyle \{\lor ,\leftrightarrow ,\bot \}}$،${\displaystyle \{\lor ,\leftrightarrow ,\nleftrightarrow \}}$،${\displaystyle \{\lor ,\nleftrightarrow ,\top \}}$،${\displaystyle \{\land ,\leftrightarrow ,\bot \}}$،${\displaystyle \{\land ,\leftrightarrow ,\nleftrightarrow \}}$،${\displaystyle \{\land ,\nleftrightarrow ,\top \}.}$

لا توجد مجموعات وظيفية كاملة دنيا تضم ​​أكثر من ثلاثة روابط منطقية ثنائية على الأكثر. ^{[ 11 ]} وللحفاظ على سهولة قراءة القوائم أعلاه، تم حذف المعاملات التي تتجاهل مدخلًا واحدًا أو أكثر. على سبيل المثال، يمكن استبدال المعامل الذي يتجاهل المدخل الأول ويُخرج نفي المدخل الثاني بنفي أحادي.

أثبتت ورقة ألفريد تارسكي بعنوان "حول المصطلح الأولي للوجستيات" أن${\displaystyle \{\leftrightarrow \}}$^{[ 12 ]} مكتمل وظيفيًا، ولكن هذا يعمل فقط إذا تم استخدام التحديد الكمي على القضايا (أداة من منطق الدرجة الثانية )، لذلك لا يتم احتسابه في القائمة أعلاه.

• أمثلة على استخدام NAND(↑) الاكتمال. كما هو موضح في ^{[ 13 ]}
  • ¬ أ ≡ أ ↑ أ
  • A ∧ B ≡ ¬( A ↑ B ) ≡ ( A ↑ B ) ↑ ( A ↑ B )
  • A ∨ B ≡ (¬ A ) ↑ (¬ B ) ≡ ( A ↑ A ) ↑ ( B ↑ B )
• أمثلة على استخدام NOR(↓) الاكتمال. كما هو موضح في ^{[ 14 ]}
  • ¬ أ ≡ أ ↓ أ
  • A ∨ B ≡ ¬( 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

إلى جانب الروابط المنطقية (المعاملات البوليانية)، يمكن إدخال مفهوم الاكتمال الوظيفي في مجالات أخرى. على سبيل المثال، تُسمى مجموعة من البوابات العكسية مكتملة وظيفيًا إذا كانت قادرة على التعبير عن كل معامل عكسي.

تُعدّ بوابة فريدكين ذات المدخلات الثلاثة بوابةً عكسيةً كاملةً وظيفيًا بحد ذاتها  ، فهي عاملٌ كافٍ بمفردها. وهناك العديد من البوابات المنطقية الشاملة الأخرى ذات المدخلات الثلاثة، مثل بوابة توفولي .

في الحوسبة الكمومية ، تعتبر بوابة هادامارد وبوابة CNOT وبوابة T عالمية، وإن كان ذلك بتعريف أكثر تقييدًا قليلاً من تعريف الاكتمال الوظيفي.

يوجد تماثل بين جبر المجموعات والجبر البولياني ، أي أنهما يشتركان في البنية نفسها . بالتالي، إذا قمنا بتحويل المؤثرات البوليانية إلى مؤثرات مجموعات، فإن النص "المترجم" أعلاه ينطبق أيضًا على المجموعات: فهناك العديد من "المجموعات الكاملة الدنيا لمؤثرات نظرية المجموعات" التي يمكنها توليد أي علاقات مجموعات أخرى. من أشهر "المجموعات الكاملة الدنيا للمؤثرات" {¬, ∩ } و {¬, ∪ } . إذا كانت المجموعة الشاملة محظورة ، فإن مؤثرات المجموعات تقتصر على الحفاظ على الزيف (Ø)، ولا يمكن أن تكون مكافئة للجبر البولياني الكامل وظيفيًا.

• جبر المجموعات – الهويات والعلاقات التي تتضمن المجموعات 
• الجبر البولياني – التلاعب الجبري بـ "صحيح" و "خطأ" 
• الاكتمال (المنطق) - سمة من سمات بعض الأنظمة المنطقية 
• ثنائية الاقتران/الفصل – خصائص تربط بين الاقتران المنطقي والفصل 
• قائمة بمواضيع الجبر البولياني
• منطق NAND – منطق مبني فقط من بوابات NAND 
• منطق NOR – صنع بوابات أخرى باستخدام بوابات NOR فقط 
• حاسوب ذو مجموعة تعليمات واحدة – آلة مجردة تستخدم تعليمة واحدة فقط