دعونا نتعرف على مفهوم تراكب (أو فرض) الدوال، والذي يتكون من استبدال دالة من وسيطة أخرى بدلاً من وسيطة دالة معينة. على سبيل المثال، تراكب الوظائف يعطي وظيفة، ويتم الحصول على الوظائف بالمثل

بشكل عام، لنفترض أن الدالة معرفة في مجال معين والدالة معرفة في مجال وقيمها كلها موجودة في المجال، فإن المتغير z، كما يقولون، من خلال y، هو في حد ذاته دالة لـ

بالنظر إلى قيمة معينة، يجدون أولاً القيمة y المقابلة لها (وفقًا للقاعدة التي تتميز بالعلامة)، ثم يحددون القيمة المقابلة y (وفقًا للقاعدة

تتميز بعلامة، وتعتبر قيمتها مطابقة لـ x المحدد. الوظيفة الناتجة من دالة أو دالة معقدة هي نتيجة تراكب الدوال

إن الافتراض بأن قيم الدالة لا تتجاوز حدود المنطقة Y التي تم تعريف الدالة فيها هو افتراض مهم للغاية: إذا تم حذفه، فقد ينتج عن ذلك العبث. على سبيل المثال، بافتراض أننا لا نستطيع إلا أن نأخذ في الاعتبار قيم x التي بخلاف ذلك لن يكون التعبير منطقيًا.

ونرى أنه من المفيد التأكيد هنا على أن توصيف الدالة على أنها معقدة لا يرتبط بطبيعة الاعتماد الوظيفي لـ z على x، ولكن فقط بالطريقة التي يتم بها تحديد هذا الاعتماد. على سبيل المثال، أدخل y لـ ثم

هنا تم تحديد الوظيفة كوظيفة معقدة.

الآن بعد أن تم فهم مفهوم تراكب الوظائف بشكل كامل، يمكننا أن نميز بدقة أبسط فئات الوظائف التي تمت دراستها في التحليل: وهي في المقام الأول الوظائف الأولية المذكورة أعلاه ثم جميع تلك التي يتم الحصول عليها منها باستخدام أربع عمليات حسابية وتراكبات، تم تطبيقها على التوالي لعدد محدود من المرات. ويقال أنه يتم التعبير عنها من خلال الابتدائية في شكلها النهائي؛ في بعض الأحيان يطلق عليهم أيضًا اسم الابتدائي.

بعد ذلك، بعد أن أتقن جهاز تحليلي أكثر تعقيدا (سلسلة لا حصر لها، تكاملات)، سوف نتعرف على وظائف أخرى تلعب أيضا دورا مهما في التحليل، ولكنها تتجاوز بالفعل فئة الوظائف الأولية.

يجب أن تكون هناك دالة f(x 1 , x 2 , ... , x n) ووظائف

ثم سوف نقوم باستدعاء الدالة تراكب وظيفةو(س 1، س 2، ...، س ن) والوظائف .

بمعنى آخر: دع F = ( f j ) - مجموعة من الدوال الجبرية المنطقية، ليست بالضرورة محدودة. تسمى الدالة f تراكب دوال من المجموعة F أو دالة فوق F إذا تم الحصول عليها من دالة عن طريق استبدال واحد أو أكثر من متغيراتها بوظائف من المجموعة F.

مثال.

دع مجموعة من الوظائف تعطى

F = (f 1 (x 1), f 2 (x 1 , x 2 , x 3), f 3 (x 1 , x 2)).

إذن، تراكبات الدوال من F ستكون، على سبيل المثال، الدوال:

ي 1 (x 2 , x 3) = f 3 (f 1 (x 2), f 1 (x 3));

ي 2 (س 1 ، س 2) = ف 2 (س 1 ، ف 1 (س 1)، ف 3 (س 1 ، س 2)).

DNF المثالي - تراكب الوظائف من مجموعة

. ð

تعريف.

يسمى نظام الوظائف ممتلىء، في حالة استخدام عمليات التراكب واستبدال المتغيرات، يمكن الحصول على أي وظيفة من وظائف جبر المنطق من وظائف هذا النظام. ð

لدينا بالفعل مجموعة معينة من الأنظمة الكاملة:

;

لأن ;

لأن ;

(س+ص، ص ص، ١). ð

كيف يمكننا تحديد الشروط التي يكتمل فيها النظام؟ يرتبط بشكل وثيق بمفهوم الاكتمال مفهوم الطبقة المغلقة.

فصول مغلقة.

تسمى المجموعة (الفئة) K من وظائف جبر المنطق فئة مغلقة، إذا كانت تحتوي على جميع الدوال التي تم الحصول عليها من K بعمليات التراكب وتغيير المتغيرات، ولا تحتوي على أي دوال أخرى.

دع K يكون مجموعة فرعية من الوظائف من P 2 . إغلاق K هو مجموعة كل الدوال المنطقية التي يمكن تمثيلها باستخدام عمليات التراكب وتغيير متغيرات الدوال من المجموعة K. ويشار إلى إغلاق المجموعة K بالرمز [K].

من حيث الإغلاق، يمكننا إعطاء تعريفات أخرى للإغلاق والاكتمال (أي ما يعادل التعريفات الأصلية):

K هي فئة مغلقة إذا كان K = [K]؛

K هو نظام كامل إذا كان [K] = P 2 .

أمثلة.

* (0)، (1) - فصول مغلقة.

* مجموعة الدوال لمتغير واحد تعتبر فئة مغلقة.

* - فصل مغلق .

* الفئة (1، x+y) ليست فئة مغلقة.

دعونا نلقي نظرة على بعض أهم الطبقات المغلقة.

1.ت0- فئة الوظائف التي تحافظ على 0.

دعونا نشير بـ T 0 إلى فئة جميع وظائف الجبر المنطقي f(x 1 , x 2 , ... , x n) مع الحفاظ على الثابت 0، أي الوظائف التي f(0, ... , 0) ) = 0.

من السهل أن نرى أن هناك وظائف تنتمي إلى T 0، ووظائف لا تنتمي إلى هذه الفئة:

0، x، xy، xÚy، x+y О T 0 ;

ويترتب على حقيقة أن Ï T 0، على سبيل المثال، أنه لا يمكن التعبير عنها بالانفصال والوصل.

نظرًا لأن جدول الدالة f من الفئة T 0 يحتوي على القيمة 0 في السطر الأول، فبالنسبة للوظائف من T 0، يمكنك تعيين قيم تعسفية فقط على مجموعة 2 n - 1 من القيم المتغيرة، أي

,

أين هي مجموعة الوظائف التي تحافظ على 0 وتعتمد على متغيرات n.

دعونا نبين أن T 0 هي فئة مغلقة. منذ xÎT 0، لتبرير الانغلاق يكفي إظهار الانغلاق فيما يتعلق بعملية التراكب، لأن عملية تغيير المتغيرات هي حالة خاصة من التراكب مع الدالة x.

يترك . ثم يكفي أن نبين ذلك. وهذا الأخير يتبع من سلسلة المساواة

2. ت 1- فئة وظائف الحفاظ 1.

دعونا نشير بـ T 1 إلى فئة جميع وظائف الجبر المنطقي f(x 1, x 2, ... , x n) مع الحفاظ على الثابت 1، أي الوظائف التي f(1, ... , 1) ) = 1.

من السهل أن نرى أن هناك دوال تنتمي إلى T 1، ودوال لا تنتمي إلى هذه الفئة:

1, x, xy, xÚy, x°y О T 1 ;

0, , س+ص Ï تي 1 .

من حقيقة أن x + y Ï T 0 يترتب على ذلك، على سبيل المثال، أنه لا يمكن التعبير عن x + y بدلالة الانفصال والاقتران.

يتم نقل النتائج المتعلقة بالفئة T 0 بشكل تافه إلى الفئة T 1 . وهكذا لدينا:

T 1 - فئة مغلقة؛

.

3. ل- فئة الوظائف الخطية.

دعونا نشير بـ L إلى فئة جميع وظائف الجبر المنطقي f(x 1 , x 2 , ... , x n) الخطية:

من السهل أن نرى أن هناك وظائف تنتمي إلى L ووظائف لا تنتمي إلى هذه الفئة:

0, 1, x, x+y, x 1 ° x 2 = x 1 + x 2 + 1, = x+1 О L;

دعونا نثبت، على سبيل المثال، أن xÚy Ï L .

ولنفترض العكس. سنبحث عن تعبير لـ xÚy على شكل دالة خطية ذات معاملات غير محددة:

بالنسبة لـ x = y = 0 لدينا a=0،

لـ x = 1، y = 0 لدينا ب = 1،

بالنسبة لـ x = 0، y = 1 لدينا g = 1،

لكن بالنسبة لـ x = 1, y = 1 لدينا 1v 1 ¹ 1 + 1، وهو ما يثبت عدم خطية الدالة xy.

إن الدليل على إغلاق فئة الدوال الخطية واضح تمامًا.

بما أن الدالة الخطية يتم تحديدها بشكل فريد من خلال تحديد قيم n+1 للمعامل a 0 , ... , a n فإن عدد الدوال الخطية في فئة L (n) من الدوال اعتمادًا على متغيرات n يساوي 2 ن+1 .

.

4. س- فئة الوظائف الذاتية المزدوجة.

يعتمد تعريف فئة الوظائف المزدوجة الذاتية على استخدام ما يسمى بمبدأ الازدواجية والوظائف المزدوجة.

تسمى الوظيفة المحددة بالمساواة المزدوج للوظيفة .

من الواضح أنه يتم الحصول على جدول الوظيفة المزدوجة (مع الترتيب القياسي لمجموعات القيم المتغيرة) من جدول الوظيفة الأصلية عن طريق قلب عمود قيم الوظيفة (أي استبدال 0 بـ 1 و 1 بـ 0) وقلبها.

من السهل رؤية ذلك

(x 1 Ú x 2)* = x 1 Ù x 2 ,

(x 1 Ù x 2)* = x 1 Ú x 2 .

ويترتب على التعريف أن (f*)* = f، أي أن الدالة f ثنائية لـ f*.

دع الوظيفة يتم التعبير عنها باستخدام التراكب من خلال وظائف أخرى. والسؤال هو، كيفية بناء صيغة قابلة للتنفيذ؟ دعونا نشير بـ = (x 1, ..., x n) إلى جميع رموز المتغير المختلفة الموجودة في المجموعات.

نظرية 2.6.إذا تم الحصول على الدالة j كتراكب للدوال f، f 1، f 2، ...، f m، فهذا يعني

الوظيفة المزدوجة للتراكب هي تراكب الوظائف المزدوجة.

دليل.

ي*(x 1 ,...,x n) = ` f(`x 1 ,...,`x n) =

لقد تم إثبات النظرية. ð

يتبع مبدأ الازدواجية من النظرية: إذا كانت الصيغة A تدرك الوظيفة f(x 1 , ... , x n)، فإن الصيغة التي تم الحصول عليها من A عن طريق استبدال الوظائف المضمنة فيها بوظائفها المزدوجة تحقق الوظيفة المزدوجة f *(x 1، ...، xn).

دعونا نشير بواسطة S إلى فئة جميع الوظائف المزدوجة الذاتية من P 2:

S = (و | و* = و )

من السهل أن نرى أن هناك وظائف تنتمي إلى S ووظائف لا تنتمي إلى هذه الفئة:

0, 1, س ص, س ص ص .

والمثال الأقل تافهة للوظيفة المزدوجة الذاتية هو الوظيفة

h(x, y, z) = xy Ú xz Ú ​​​​yz;

باستخدام نظرية الدالة المزدوجة للتراكب، لدينا

h*(x, y, z)= (x Ú y)Ù(x Ú z) Ù (y Ù z) = x y Ú x z Ú y z; ح = ح* ; ح أو س.

بالنسبة للوظيفة الذاتية المزدوجة، فإن الهوية تحمل

وهكذا على مجموعات و، والتي سنسميها بالعكس، فإن الدالة الذاتية المزدوجة تأخذ قيمًا متضادة. ويترتب على ذلك أن الوظيفة المزدوجة الذاتية يتم تحديدها بالكامل من خلال قيمها في النصف الأول من صفوف الجدول القياسي. ولذلك فإن عدد الدوال الذاتية المزدوجة في صنف S(n) من الدوال المعتمدة على متغيرات n يساوي:

.

دعونا الآن نثبت أن الفئة S مغلقة. منذ xÎS، لتبرير الانغلاق يكفي إظهار الانغلاق فيما يتعلق بعملية التراكب، لأن عملية تغيير المتغيرات هي حالة خاصة من التراكب مع الدالة x. يترك . ثم يكفي أن نبين ذلك. يتم تثبيت الأخير مباشرة:

5. م- فئة الوظائف الرتيبة.

قبل تعريف مفهوم الدالة الرتيبة في جبر المنطق، من الضروري إدخال علاقة ترتيب على مجموعة مجموعات متغيراتها.

يقولون أن المجموعة تأتي قبل المجموعة (أو "ليس أكثر من"، أو "أقل من أو يساوي")، واستخدم الترميز إذا كان a i £ b i للجميع i = 1، ... ، n. إذا و، فسنقول أن المجموعة تسبق المجموعة تمامًا (أو "أقل تمامًا"، أو "أقل من" المجموعة)، ونستخدم الترميز . تسمى المجموعات و قابلة للمقارنة إذا كان أي منهما أو . في حالة عدم وجود أي من هذه العلاقات، تسمى المجموعات و غير قابلة للمقارنة. على سبيل المثال، (0، 1، 0، 1) £ (1، 1، 0، 1)، ولكن المجموعات (0، 1، 1، 0) و (1، 0، 1، 0) لا يمكن مقارنتها. وبالتالي، فإن العلاقة £ (التي تسمى غالبًا علاقة الأسبقية) هي ترتيب جزئي للمجموعة B n. فيما يلي الرسوم البيانية للمجموعات المرتبة جزئيًا B 2 وB 3 وB 4.

تعد علاقة النظام الجزئي المقدمة مفهومًا مهمًا للغاية يتجاوز نطاق الدورة التدريبية لدينا.

الآن لدينا الفرصة لتحديد مفهوم الوظيفة الرتيبة.

تسمى وظيفة الجبر المنطقي رتيب، إذا كان لأي مجموعتين و، بحيث يستمر عدم المساواة . تتم الإشارة إلى مجموعة جميع الوظائف الرتيبة لجبر المنطق بواسطة M، ويتم الإشارة إلى مجموعة جميع الوظائف الرتيبة المعتمدة على متغيرات n بواسطة M(n).

من السهل أن نرى أن هناك وظائف تنتمي إلى M ووظائف لا تنتمي إلى هذه الفئة:

0، 1، x، xy، xÚy О M؛

x+y, x®y, x°y Ï M .

دعونا نبين أن فئة الدوال الرتيبة M هي فئة مغلقة. منذ xОМ، لتبرير الانغلاق يكفي إظهار الانغلاق فيما يتعلق بعملية التراكب، لأن عملية تغيير المتغيرات هي حالة خاصة من التراكب مع الدالة x.

يترك . ثم يكفي أن نبين ذلك.

دع مجموعات من المتغيرات، على التوالي، الوظائف j، f 1، ... ، f m، ومجموعة متغيرات الوظيفة j تتكون من تلك المتغيرات التي تظهر في الوظائف f 1، ... ، f m فقط. دع و يكون مجموعتين من قيم المتغير و . تحدد هذه المجموعات المجموعات القيم المتغيرة ، مثل ذلك . بسبب رتابة الوظائف f 1 , ... , f m

وبسبب رتابة الدالة f

من هنا نحصل

عدد الوظائف الرتيبة التي تعتمد على المتغيرات n غير معروف بالضبط. يمكن الحصول على الحد الأدنى بسهولة:

حيث - هو الجزء الصحيح من n/2.

كما يتبين ببساطة أن التقدير أعلاه مرتفع جدًا:

يعد تحسين هذه التقديرات مهمة مهمة ومثيرة للاهتمام للبحث الحديث.

معيار الاكتمال

الآن أصبحنا قادرين على صياغة وإثبات معيار الاكتمال (نظرية بوست)، الذي يحدد الشروط الضرورية والكافية لاكتمال نظام من الوظائف. دعونا نستهل صياغة وإثبات معيار الاكتمال بعدة مصطلحات ضرورية لها فائدة مستقلة.

ليما 2.7. Lemma حول الوظيفة غير الذاتية المزدوجة.

إذا كانت f(x 1 , ... , x n)Ï S ، فيمكن الحصول على ثابت منه عن طريق استبدال الدالتين x و `x.

دليل. منذ fÏS، هناك مجموعة من قيم المتغيرات
=(أ 1،...،أ ن) هكذا

و(`أ 1،...,`أ ن) = و(أ 1،...,أ ن)

دعنا نستبدل الوسائط في الدالة f:

x i تم استبداله بـ ,

وهذا هو، دعونا نضع وننظر في الوظيفة

وهكذا حصلنا على ثابت (رغم أنه من غير المعروف أي ثابت هو: 0 أو 1). ð

ليما 2.8. Lemma حول الوظيفة غير الرتيبة.

إذا كانت الدالة f(x 1 ,...,x n) غير رتيبة، f(x 1 ,...,x n) Ï M، فيمكن الحصول على النفي منها عن طريق تغيير المتغيرات واستبدال الثوابت 0 و 1.

دليل. بما أن f(x 1 ,...,x n) Ï M، فهناك مجموعات من قيم متغيراتها، , ، بحيث، ولقيمة واحدة على الأقل i، a i< b i . Выполним следующую замену переменных функции f:

x سيتم استبدالي بـ

بعد هذا الاستبدال نحصل على دالة ذات متغير واحد j(x)، والتي لدينا:

هذا يعني أن j(x)=`x. تم إثبات الليما. ð

ليما 2.9.ليما حول الدالة غير الخطية.

إذا كان f(x 1 ,...,x n) Ï L فمنه عن طريق استبدال الثوابت 0, 1 واستخدام الدالة `x يمكننا الحصول على الدالة x 1 &x 2 .

دليل. دعونا نمثل f باعتباره DNF (على سبيل المثال، DNF مثالي) ونستخدم العلاقات:

مثال. دعونا نعطي مثالين لتطبيق هذه التحولات.

وبالتالي، فإن الدالة المكتوبة في شكل عادي منفصل، بعد تطبيق العلاقات المشار إليها، وفتح الأقواس والتحويلات الجبرية البسيطة، تصبح متعددة الحدود mod 2 (متعددة حدود Zhegalkin):

حيث A 0 ثابت، و A i هو اقتران بعض المتغيرات من الرقم x 1,..., x n, i = 1, 2, ..., r.

إذا كان كل اقتران A i يتكون من متغير واحد فقط، فإن f هي دالة خطية، مما يتعارض مع شرط lemma.

وبالتالي، في متعددة حدود Zhegalkin للدالة f يوجد مصطلح يحتوي على عاملين على الأقل. وبدون فقدان العمومية، يمكننا أن نفترض أنه من بين هذه العوامل هناك متغيرات x 1 و x 2. ثم يمكن تحويل كثير الحدود على النحو التالي:

و = x 1 x 2 f 1 (x 3 ,..., x n) + x 1 f 2 (x 3 ,..., x n) + x 2 f 3 (x 3 ,..., x n) + f 4 (× 3،...، × ن)،

حيث f 1 (x 3 ,..., x n) ¹ 0 (وإلا فإن كثير الحدود لا يتضمن أداة العطف التي تحتوي على أداة العطف x 1 x 2).

ليكن (a 3 ,...,a n) بحيث يكون f 1 (a 3 ,...,a n) = 1. إذن

ي(x 1 ,x 2) = f(x 1 ,x 2 , أ 3 ,...,أ n) = x 1 x 2 +ax 1 +bx 2 +g ,

حيث a، b، g هي ثوابت تساوي 0 أو 1.

دعونا نستخدم عملية النفي التي لدينا ونفكر في الدالة y(x 1 ,x 2) التي تم الحصول عليها من j(x 1 ,x 2) كما يلي:

ص(x 1 ,x 2) = ي(x 1 +ب, x 2 +a)+ab+g.

من الواضح أن

ص(x 1 ,x 2) =(x 1 +ب)(x 2 +a)+a(x 1 +b)+b(x 2 +a)+g+ab+g = x 1 x 2.

لذلك،

ص(x 1 ,x 2) = x 1 x 2 .

وقد ثبت ليما تماما. ð

ليما 2.10.الفكرة الرئيسية لمعيار الاكتمال.

إذا كانت الفئة F=( f ) من دوال الجبر المنطقي تحتوي على دوال لا تحافظ على الوحدة، ولا تحافظ على 0، فهي غير ثنائية ذاتية وغير رتيبة:

ومن ثم من دوال هذا النظام، ومن خلال عمليات التراكب واستبدال المتغيرات، يمكن الحصول على الثوابت 0، 1 والدالة.

دليل. دعونا نفكر في الوظيفة. ثم

.

هناك حالتان محتملتان للاعتبارات اللاحقة، تم تحديدهما في العرض التالي كـ 1) و2).

1). تأخذ الوظيفة الموجودة في مجموعة الوحدة القيمة 0:

.

لنستبدل جميع متغيرات الدالة بالمتغير x. ثم الوظيفة

هناك، لأن

و .

لنأخذ وظيفة غير ذاتية مزدوجة. نظرًا لأننا حصلنا بالفعل على الوظيفة، فمن خلال lemma على وظيفة غير مزدوجة ذاتية (lemma 2.7. ) يمكنك الحصول على ثابت من. ويمكن الحصول على الثابت الثاني من الأول باستخدام الدالة. لذلك، في الحالة الأولى، يتم الحصول على الثوابت والنفي. . أما الحالة الثانية، ومعها القاعدة الرئيسية لمعيار الاكتمال، فقد تم إثباتها بشكل كامل. ð

نظرية 2.11.معيار اكتمال أنظمة الدوال في جبر المنطق (نظرية بوست).

لكي يكتمل نظام الوظائف F = (f i ) ، من الضروري والكافي ألا يكون واردًا بالكامل في أي من الفئات الخمس المغلقة T 0، T 1، L، S، M، أي ل كل فئة من الفئات T 0 , T 1 , L , S, M في F هناك وظيفة واحدة على الأقل لا تنتمي إلى هذه الفئة.

ضروري. دع F يكون نظامًا كاملاً. لنفترض أن F موجودة في إحدى الفئات المشار إليها، فلنرمز إليها بـ K، أي. FÍ K. التضمين الأخير مستحيل، لأن K هي فئة مغلقة وليست نظامًا كاملاً.

قدرة. دع نظام الوظائف بأكمله F = (f i ) غير موجود في أي من الفئات الخمس المغلقة T 0 , T 1 , L , S , M لنأخذ الوظائف التالية في F :

ثم، بناءً على الليما الرئيسية (lemma 2.10 ) من دالة لا تحافظ على 0، دالة لا تحافظ على 1، دوال غير ثنائية وغير رتيبة، يمكن الحصول على الثوابت 0، 1 ودالة النفي:

.

استنادًا إلى lemma على الوظائف غير الخطية (lemma 2.9 ) من الثوابت والنفي والدالة غير الخطية يمكننا الحصول على الاقتران:

.

نظام الوظيفة - نظام كامل حسب نظرية إمكانية تمثيل أي دالة من جبر المنطق في صورة عادية انفصالية مثالية (لاحظ أنه يمكن التعبير عن الانفصال من خلال الربط والنفي في الصورة ).

تم إثبات النظرية بشكل كامل. ð

أمثلة.

1. دعونا نبين أن الدالة f(x,y) = x|y تشكل نظامًا كاملاً. لنقم ببناء جدول قيم الدالة x½y:

س	ذ	س|ص

f(0,0) = 1، وبالتالي x | ييت 0 .

f(1,1) = 0، وبالتالي x | نعم 1 .

f(0,0) = 1، f(1,1) = 0، وبالتالي x | يم.

f(0,1) = f(1,0) = 1، - في المجموعتين المتقابلتين x | y تأخذ نفس القيم، لذلك x | نعم.

وأخيرًا، ماذا تعني عدم خطية الدالة؟
س | ذ.

بناءً على معيار الاكتمال، يمكننا القول أن f(x,y) = x | y يشكل نظاما كاملا. ð

2. دعونا نبين أن نظام الوظائف يشكل نظاما كاملا.

حقًا، .

وهكذا وجدنا من بين وظائف نظامنا: دالة لا تحفظ 0، دالة لا تحفظ 1، دوال غير ثنائية ذاتية، غير رتيبة وغير خطية. واستنادا إلى معيار الاكتمال، يمكن القول بأن نظام الوظائف يشكل نظاما كاملا. ð

وهكذا نحن مقتنعون بأن معيار الاكتمال يوفر طريقة بناءة وفعالة لتحديد اكتمال أنظمة الدوال في جبر المنطق.

دعونا الآن نصوغ ثلاث نتائج طبيعية من معيار الاكتمال.

النتيجة الطبيعية 1. أي فئة مغلقة K من وظائف جبر المنطق التي لا تتطابق مع مجموعة وظائف جبر المنطق بأكملها (K¹P 2) موجودة في واحدة على الأقل من الفئات المغلقة المنشأة.

تعريف.تسمى الفئة المغلقة K قبل الكامل، إذا كانت K غير مكتملة ولأي دالة fÏ K فإن الفئة K È (f) مكتملة.

ويترتب على التعريف أن الفصل المكتمل مغلق.

النتيجة الطبيعية 2.في جبر المنطق هناك خمس فئات فقط مكتملة، وهي: T 0، T 1، L، M، S.

لإثبات النتيجة الطبيعية، ما عليك سوى التحقق من عدم وجود أي من هذه الفئات في الأخرى، وهو ما يتم تأكيده، على سبيل المثال، من خلال جدول الوظائف التالي الذي ينتمي إلى فئات مختلفة:

	T0	تي 1	ل	س	م
	+	-	+	-	+
	-	+	+	-	+
	-	-	+	+	-

النتيجة الطبيعية 3.من أي نظام كامل للوظائف يمكن اختيار نظام فرعي كامل لا يحتوي على أكثر من أربع وظائف.

ويترتب على إثبات معيار الاكتمال أنه لا يمكن تمييز أكثر من خمس وظائف. من إثبات الليما الرئيسي (Lemma 2.10 ) يتبع ذلك إما أن يكون غير ثنائي بذاته أو لا يحفظ الوحدة وليس رتيباً. ولذلك، ليست هناك حاجة لأكثر من أربع وظائف.

- (أواخر Lat. superpositio، - تراكب، من Lat. superpositus - موضوعة في الأعلى) (التكوين) - عملية منطقية رياضية. حساب التفاضل والتكامل، والذي يتكون من الحصول على k.l. وظائف معينة f و g حساب التفاضل والتكامل لوظيفة جديدة g (f) (تعبير g... ... الموسوعة الفلسفية

يمكن أن يشير مصطلح التراكب (التراكب) إلى المفاهيم التالية: تركيب التراكب للوظائف (وظيفة معقدة) مبدأ التراكب هو مبدأ في الفيزياء والرياضيات يصف تراكب العمليات (على سبيل المثال، الموجات)، ونتيجة لذلك، ... ... ويكيبيديا

تكوين الوظائف، وتكوين وظيفة معقدة من وظيفتين... الموسوعة الرياضية

هذا المصطلح له معاني أخرى، انظر التراكب. ميكانيكا الكم ويكيبيديا

تحتوي هذه المقالة أو القسم على قائمة المصادر أو المراجع الخارجية، لكن مصادر الأقوال الفردية تظل غير واضحة بسبب عدم وجود الحواشي... ويكيبيديا

في نظرية الأنظمة الوظيفية المنفصلة، ​​الدالة البوليانية هي دالة من النوع، حيث تكون مجموعة منطقية وn عدد صحيح غير سالب، وهو ما يسمى arity أو محلية الدالة. يتم تفسير العناصر 1 (واحد) و0 (صفر) بشكل قياسي ... ... ويكيبيديا

من أهم أسس الرياضيات والرياضيات. تحتوي الفئات المنطقية للمفاهيم التي تكون بمثابة توضيحات. مفاهيم الدالة الحسابية القابلة للحساب بشكل فعال والمسند الحسابي الذي يمكن تحديده بشكل فعال، وفي النهاية، و... ... الموسوعة الفلسفية

الوظيفة، يمكن إجراء حساب قيم السرب باستخدام إجراء أو خوارزمية فعالة محددة مسبقًا. السمة المميزة للعمليات الحسابية هي حساب الكميات المطلوبة من المشاكل التي تحدث بشكل تسلسلي من البيانات الأولية... ... الموسوعة الرياضية

من الضروري نقل محتويات هذه المقالة إلى مقالة "تمايز دالة معقدة". يمكنك مساعدة المشروع من خلال الجمع بين المقالات. إذا كان من الضروري مناقشة جدوى الدمج، فاستبدل هذا القالب بالقالب ((للدمج)) ... ويكيبيديا

- (لاتينية: التركيب التركيبي، الربط، الإضافة، الاتصال): يحتوي ويكاموس على مقالة "التركيب" التركيب الفني (الفنون الجميلة) هو عنصر تنظيمي لشكل فني يعطي... ويكيبيديا

كتب

• الرياضيات المنفصلة. الإنشاءات النظرية الأساسية. الجزء السادس، أ. الدليل هو الجزء السادس من قسم "الإنشاءات النظرية الأساسية للرياضيات المنفصلة". بوصة. يتناول الحادي عشر المفاهيم التالية: تركيبات الوظائف (الفقرة 1)؛ المهام،...

تقوم الأجهزة المنطقية المنفصلة ذات الدورة الواحدة (التي لا تحتوي على عناصر الذاكرة) بتنفيذ مجموعة معينة من وظائف الجبر المنطقي عند الإخراج `ف م =(F 1 ،F 2 ،…،ف م)، والتي تعتمد في كل لحظة فقط على حالة مدخلات الجهاز `س ن =(س 1 ،x 2 ،…،x ن): `F م = `F م(`س ن). ومن الناحية العملية، يتم تصميم وتصنيع هذه الأجهزة من عناصر منفصلة غير قابلة للتجزئة تنفذ مجموعة (نظام) معين ( F) الوظائف الأساسية للجبر عن طريق ربط مخرجات بعض العناصر بمدخلات عناصر أخرى.

عند تصميم الأجهزة المنطقية، تكون الأسئلة التالية ذات صلة.

1. يتم إعطاء نظام الوظائف الأولية ( F). ما هي وظائف الإخراج واويمكن الحصول عليها باستخدام وظائف من ( F}?

2. مجموعة من وظائف الإخراج المنطقية ( F) (على وجه الخصوص، يساوي مجموعة كاملة من وظائف الجبر المنطق ر 2). ما ينبغي أن يكون النظام الأولي للوظائف الأولية ( F) ، مما يوفر إمكانية الحصول عند الإخراج على أي من وظائف المجموعة ( F}?

لتقديم إجابة معقولة على هذه الأسئلة، يتم استخدام مفاهيم التراكب والانغلاق واكتمال أنظمة الوظائف.

تعريف.دعونا نفكر في مجموعة من الروابط المنطقية ( F) ، المقابلة لبعض أنظمة الوظائف ( F} . انتهى التراكب{F) هي أي دالة j يمكن تحقيقها بواسطة صيغة فوق ( F}.

من الناحية العملية، يمكن تمثيل التراكب كنتيجة لاستبدال الوظائف من ( F) كوسيطات لدالة من نفس المجموعة.

مثال 1. النظر في نظام الوظائف ( F} = {F 1 (X) =`س، ف 2 (س، ص)= X&ذ، ف 3 (س، ص)=XÚ ذ). الاستبدال في الدالة F 3 (س، ص) بدلاً من الوسيطة الأولى Xوظيفة F 1 (X)، بدلاً من الثاني - F 2 (س، ص) ، نحصل على التراكب ح(س، ص)=F 3 (F 1 (X)،F 2 (س، ص))=`سÚ X& في. ويرد التنفيذ المادي للاستبدال في الشكل 1.18.

تعريف.يترك م- مجموعة معينة من وظائف الجبر المنطقي ( ص 2). مجموعة جميع التراكبات انتهت ممُسَمًّى دائرة مقصورةمجموعات مويشار إليه بـ [ م]. يستلم [ م] بواسطة المجموعة الأصلية ممُسَمًّى عملية الإغلاق. مجموعة من ممُسَمًّى فئة مغلقة وظيفيا، لو [ م] = م. مجموعة فرعية مÍ ممُسَمًّى نظام كامل وظيفيا في M، لو [ م] = م.

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

ملحوظات. 1.من الواضح أن أي نظام من الوظائف ( F) مكتمل وظيفيًا في حد ذاته.

2 . وبدون فقدان العمومية، يمكننا أن نفترض أن وظيفة الهوية F(X)=س، الذي لا يغير القيم الحقيقية للمتغيرات، هو في البداية جزء من أي نظام من الوظائف.

مثال 2. بالنسبة لأنظمة الوظائف التي تمت مناقشتها أدناه ( F) قم بما يلي:

1) العثور على الإغلاق [ F],

2) معرفة ما إذا كان النظام ( F) فئة مغلقة،

3) العثور على أنظمة كاملة وظيفيا في ( F}.

حل.

أنا. ( F}={0} . عند استبدال الدالة ( f 0) نستقبله في أنفسنا، أي. لم يتم إنشاء وظائف جديدة. هذا يعني: [ F] = {F). النظام المدروس هو فئة مغلقة وظيفيا. النظام الكامل وظيفيا فيه واحد ويساوي الكل ( F}.

ثانيا. ( F} = {0,Ø } . الاستبدال Ø (Ø X) يعطي وظيفة مماثلة لا توسع النظام الأصلي رسميًا. ومع ذلك، عند استبدال Ø (0) نحصل على وحدة مماثلة - دالة جديدة لم تكن موجودة في النظام الأصلي: Ø (0)=1 . تطبيق جميع البدائل الأخرى لا يؤدي إلى ظهور وظائف جديدة، على سبيل المثال: ØØ 0 = 0، 0(ط X)=0.

وهكذا، فإن استخدام عملية التراكب جعل من الممكن الحصول على مجموعة أوسع من الوظائف من تلك الأصلية [ F]=(0,Ø ,1). وهذا يعني إدخالًا صارمًا: ( F} Ì [ F]. نظام المصدر ( F) ليست فئة مغلقة وظيفيا. بالإضافة إلى النظام نفسه ( F) لا توجد فيها أنظمة أخرى كاملة وظيفيا، لأنه في حالة تضييقها من وظيفة واحدة و =لا يمكن إلغاء الصفر عن طريق الاستبدال، ولا يمكن الحصول على الصفر المطابق من دالة النفي وحدها.

ثالثا. ( F) = (& ,Ú ,Ø ).إغلاق هذا النظام هو مجموعة كاملة من وظائف جبر المنطق ص 2، حيث يمكن تمثيل صيغة أي منها على أنها DNF أو CNF، والتي تستخدم وظائف أولية ( F) = (&،Ú،Ø). هذه الحقيقة هي دليل بناء على اكتمال نظام الوظائف المدروس في ص 2: [F]= ف 2 .

منذ ذلك الحين في ص 2 يحتوي على عدد لا نهائي من الدوال الأخرى بخلاف ( F) = (& ,Ú ,Ø ) فهذا يعني حدوثًا صارمًا: ( F}Ì[ F]. النظام المدروس ليس فئة مغلقة وظيفيا.

بالإضافة إلى النظام نفسه، ستكون الأنظمة الفرعية مكتملة وظيفيًا ( F) 1 = (&، Ø ) و ( F) 2 = (Ú ,Ø ). يأتي هذا من حقيقة أنه باستخدام قواعد De Morgan، يمكن التعبير عن وظيفة الجمع المنطقية Ú من خلال (&، Ø)، ودالة الضرب المنطقية & من خلال (Ú، Ø):

(X & في) = Ø (` XÚ` في), (X Ú في) = Ø ( X &`في).

أنظمة فرعية أخرى كاملة وظيفيا في ( F) لا.

التحقق من اكتمال النظام الفرعي للوظيفة ( F) 1 م ( F) في جميع أنحاء النظام ( F) يمكن أن تنتج عن طريق الخلط ( F) 1 إلى آخر، من الواضح أنه كامل في ( F)نظام.

عدم اكتمال النظام الفرعي ( F) 1 في ( F)يمكن التحقق منها عن طريق إثبات حدوث صارم لـ [ F 1 ] م [ F].

تعريف.مجموعة فرعية مÍ ممُسَمًّى أساس وظيفي(أساس)أنظمة م، لو [ م] = موبعد حذف أي وظيفة منه، لا تكتمل مجموعة الوظائف المتبقية فيه م .

تعليق. أسس نظام الوظائف (F)هي جميع أنظمتها الفرعية كاملة وظيفيا (F) 1- لا يمكن تخفيضها دون فقدان الاكتمال فيها (F).

مثال 3. بالنسبة لجميع الأنظمة المذكورة في المثال 2، ابحث عن القواعد.

حل.في الحالتين 1 و2، تكون الأنظمة نفسها فقط مكتملة وظيفيًا ومن المستحيل تضييق نطاقها. وبالتالي، فهي أيضًا قواعد.

في الحالة 3 يوجد اثنان مكتملان وظيفيًا في ( F)الأنظمة الفرعية ( F) 1 = (&,Ø) و ( F) 2 =(Ú,Ø) ، والتي لا يمكن اختزالها دون فقدان الاكتمال. سيكونون أساس النظام ( F} = {&,Ú,Ø}.

تعريف.السماح للنظام ( F) هي فئة مغلقة. مجموعتها الفرعية ( F) 1 م ( F) وتسمى فئة المبتدئين في{F)، لو ( F) 1 غير مكتمل في ( F} ([F 1 ] م [ F])، ولأي وظيفة j من النظام ( F)، غير متضمنة في ( F) 1 (يO( F} \ {F) 1) صحيح: [ يÈ { F} 1 ] = [F]، أي. إضافة جي كي ( F) 1 يجعلها كاملة في ( F} .

مهام

1. تحقق من إغلاق مجموعات الوظائف:

أ) (Ø)؛ ب) (1، Ø)؛ ج) ((0111)؛ (10));د) ((11101110); (0110));د) ((0001); (00000001); (0000000000000001); … ).

2. التحقق من اكتمال الأنظمة الوظيفية في ص 2:

أ) (0، Ø)؛ ب) ((0101) , (1010) ); الخامس )؛ د) ((0001) ، (1010)).

3. البحث عن خاتمة نظام الوظائف وأساسه:

أ) (0، 1، Ø)؛ ب) ((1000)، (1010)، (0101))؛ ج) ((0001)، (1110)، (10))؛ د) ((1010)، (0001)، (0111)).

1.10.2 الدوال التي تحافظ على الثوابت. الفئتان T 0 و T 1

تعريف.وظيفة F(`س ن) يحفظ 0 إذا F(0,..., 0) = 0. وظيفة F(`س ن) يحفظ 1 إذا F(1, ... , 1) = 1.

الكثير من الميزات نيتم الإشارة إلى المتغيرات التي تخزن 0 و 1، على التوالي، ت 0 نو ت 1 ن. جميع مجموعات وظائف الجبر المنطقي التي تحافظ على 0 و 1 , دل ت 0 و ت 1 . كل مجموعة ت 0 و ت 1 هو فصل دراسي مغلق في ر 2 .

من الوظائف الأولية إلى ت 0 و تيتم تضمين 1 في وقت واحد، على سبيل المثال، & وÚ. انتماء أي وظيفة إلى الطبقات ت 0 , تيمكن التحقق من 1 من خلال القيمة الأولى والأخيرة لمتجه القيم في جدول الحقيقة أو عن طريق استبدال الأصفار والواحدات مباشرة في الصيغة عند تحديد الدالة تحليلياً.

تعريف.ينسخهو استبدال يتم فيه استبدال نفس المتغير في دالة بدلاً من عدة متغيرات مستقلة. في هذه الحالة، ستكون قيم المتغيرات في المجموعات التي أخذت قيمًا مستقلة عن بعضها البعض في السابق هي نفسها دائمًا.

مهام

1.التحقق من عضوية الفصل ت 0 و تي 1المهام:

أ) الجمع المعمم، ب) الضرب المعمم، ج) الثوابت، د) xyÚ yz، د) X® في® xy، ه) XÅ في، و)( X 1 أ … Å Xن) ® ( ذ 1 أ … Å ذحصيرة ن، مÎ ن.

2. إثبات تقارب كل فئة من الفئات ت 0 و ت 1 .

3. إثبات أنه إذا F(`س ن) Ï ت 0، ومنه، عن طريق تكرار الاستبدال، يمكنك الحصول على الثابت 1 أو النفي.

4. إثبات أنه إذا F(`س ن) Ï ت 1 ، ومنه، عن طريق تكرار الاستبدال، يمكنك الحصول على الثابت 0 أو النفي.

5. إثبات اكتمال كل فصل من الفصول ت 0 و ت 1 (على سبيل المثال، عن طريق تقليل النظام المعزز إلى ( F} = {& ,Ú ,Ø }).

6. العثور على أصل الطبقات ت 0 نو ت 1 ن.

يجب أن يكون هناك بعض المجموعة ك، تتكون من عدد محدود من الوظائف المنطقية. تراكب الوظائف من هذه المجموعة هو الوظائف الجديدة التي يتم الحصول عليها من خلال تطبيق عدد محدود من العمليتين؛

يمكنك إعادة تسمية أي متغير مضمن في دالة من ك;

بدلاً من أي متغير يمكنك وضع دالة من المجموعة كأو تراكب تم تشكيله مسبقًا.

ويسمى التراكب أيضًا وظيفة معقدة.

مثال 7. 1. إذا أعطيت وظيفة واحدة X|ذ(سكتة شيفر)، فإن تراكباتها، على وجه الخصوص، ستكون الوظائف التالية س|س,س|(س|ص),س|(ص|ض) إلخ.

بالإغلاقمجموعة من الوظائف من كتسمى مجموعة جميع التراكبات. فئة الوظيفة كمُسَمًّى مغلق، إذا تزامن إغلاقه مع نفسه.

تسمى مجموعة الوظائف مكتملإذا كان إغلاقه يتزامن مع جميع الوظائف المنطقية. بمعنى آخر، المجموعة الكاملة هي مجموعة من هذه الوظائف التي يمكن من خلالها التعبير عن جميع الوظائف المنطقية الأخرى.

تسمى المجموعة الكاملة غير الزائدة من الوظائف بالأساس("غير زائدة عن الحاجة" تعني أنه إذا تمت إزالة بعض الوظائف من المجموعة، فلن تكون هذه المجموعة مكتملة بعد الآن).

مثال 7.2. إن أدوات الاقتران والانفصال والنفي هي مجموعة كاملة (كنا مقتنعين بذلك في القسم 5)، ولكنها ليست أساسًا، حيث أن هذه المجموعة زائدة عن الحاجة، حيث أنه باستخدام قواعد دي مورجان يمكن للمرء إزالة أدوات الاقتران أو الانفصال. يمكن تمثيل أي دالة على أنها متعددة حدود Zhegalkin (القسم 6). من الواضح أن اقتران الدوال ووحدة الجمع 2 والثوابت 0 و1 هي مجموعة كاملة، ولكن هذه الوظائف الأربع ليست أيضًا أساسًا، حيث أن 1+1=0، وبالتالي يمكن استبعاد الثابت 0 من المجموعة الكاملة set (لإنشاء كثيرات الحدود، يعد ثابت Zhegalkin 0 ضروريًا لأن التعبير "1+1" ليس كثير حدود Zhegalkin).

من السهل أن نرى أن إحدى الطرق للتحقق من اكتمال بعض المجموعات لهو التحقق من أن وظائف مجموعة كاملة أخرى يتم التعبير عنها من خلال وظائف من هذه المجموعة (يمكنك التحقق من ذلك من خلال وظائف من ليمكن للمرء أن يعبر عن الارتباط والنفي أو الانفصال والنفي.

هناك وظائف تكون إحدى هذه الوظائف في حد ذاتها أساسًا (هنا يكفي التحقق من الاكتمال فقط؛ وعدم التكرار واضح). تسمى هذه الوظائف وظائف شيفر. يرجع هذا الاسم إلى حقيقة أن ضربة شيفر هي الأساس. تذكر أن عدد شيفر يتم تعريفه بواسطة جدول الحقيقة التالي:

وبما أنه واضح، أي أن النفي هو تراكب لضربة شيفر، والانفصال إذن ، السكتة الدماغية شيفر هي في حد ذاتها الأساس. وبالمثل، فإن سهم بيرس هو دالة شيفر (يمكن للطلاب التحقق من ذلك بأنفسهم). بالنسبة للدوال المكونة من 3 متغيرات أو أكثر، هناك الكثير من دوال Sheffer (بالطبع، يعد التعبير عن دوال منطقية أخرى من خلال دالة Sheffer لعدد كبير من المتغيرات أمرًا صعبًا، لذلك نادرًا ما يتم استخدامها في التكنولوجيا).

لاحظ أن جهاز الحوسبة يعتمد في أغلب الأحيان على مجموعة كاملة من الوظائف (غالبًا على قواعد). إذا كان الجهاز يعتمد على الاقتران والانفصال والنفي، فإن مشكلة تصغير DNF مهمة لهذه الأجهزة؛ إذا كان الجهاز يعتمد على وظائف أخرى، فمن المفيد أن تكون قادرًا على تقليل التعبيرات من خلال هذه الوظائف خوارزميًا.

دعنا ننتقل الآن إلى توضيح اكتمال مجموعات محددة من الوظائف. للقيام بذلك، قمنا بإدراج أهم 5 فئات من الوظائف:

• ت 0 هي مجموعة كل تلك الوظائف المنطقية التي تأخذ القيمة 0 في مجموعة الصفر ( ت 0 هي فئة الوظيفة، الحفاظ على 0);
• ت 1 هي مجموعة جميع الوظائف المنطقية التي تأخذ القيمة 1 في مجموعة الوحدة ( ت 1 هي فئة دالة، وحدة الحفظ) (لاحظ أن عدد الوظائف من صالمتغيرات التي تنتمي إلى الفئتين T 0 و T 1 تساوي 2 2n-1)؛
• ل- فصل خطيالوظائف، أي الوظائف التي يحتوي متعدد الحدود Zhegalkin فيها فقط على الدرجات الأولى من المتغيرات؛
• م- فصل رتيبالمهام. دعونا نصف فئة هذه الوظائف بمزيد من التفصيل. يجب أن يكون هناك مجموعتين من صالمتغيرات: s1 = (x 1, x 2,..., x n)

ق 1 = ( X 1 , X 2 , … , س ن) و ق 2 = (ذ 1 , ذ 2, … , ص ص). سنقول أن المجموعة s 1 أقل من المجموعة s 2 (s 1 £ s 2 )، إذا كانت جميعها x i £ y i .ومن الواضح، ليس كل مجموعات منصالمتغيرات قابلة للمقارنة مع بعضها البعض (على سبيل المثال، متىن = 2 المجموعتان (0،1) و (1،0) غير قابلتين للمقارنة مع بعضهما البعض). وظيفة منصتسمى المتغيراترتيب, إذا كان في مجموعة أصغر فإنه يأخذ قيمة أقل أو مساوية. وبطبيعة الحال، لا ينبغي اختبار هذه التفاوتات إلا على مجموعات قابلة للمقارنة. من الواضح أن المجموعات غير القابلة للمقارنة هي تلك التي يوجد فيها بعض الإحداثيات من النوع (0,1) في مجموعة واحدة و(1,0) في مجموعة أخرى في الأماكن المقابلة (في الرياضيات المنفصلة، ​​تعد الوظائف الرتيبة مجرد "وظائف متزايدة بشكل رتيب" ، لا يتم أخذ الوظائف "المتناقصة بشكل رتيب" في الاعتبار هنا).

مثال. في الجدول التالي الوظائف F 1 ,F 2 هي وظائف رتيبة، والوظائف F 3 ,F 4 - لا.

يتم ضمان الترتيب الطبيعي للمتغيرات من خلال حقيقة أنه إذا كانت مجموعة ما أصغر من مجموعة أخرى، فمن الضروري أن تكون موجودة في جدول الحقيقة أعلىمجموعة "أكبر". لهذا إذا كان في جدول الحقيقة()هناك أصفار في الأعلى,ومن ثم الوحدات,فإن هذه الوظيفة رتيبة بالتأكيد.ومع ذلك، فإن الانقلابات ممكنة، أي أن واحدًا يأتي قبل بعض الأصفار, لكن الوظيفة لا تزال رتيبة(في هذه الحالة يجب أن تكون المجموعات المقابلة للصفر "العلوي" والصفر "الأدنى". لا تضاهى; يمكن للمرء التحقق من أن الوظيفة التي قدمها جدول الحقيقة مع الترتيب الطبيعي لمجموعة المتغيرات(00010101)، رتيب)؛

نظرية .فئات الدالة T 0 ,ت 1 ,ل,م,س مغلقة.

يأتي هذا البيان مباشرة من تعريف هذه الفئات نفسها، وكذلك من تعريف الانغلاق.

في نظرية الدوال البوليانية، تعتبر نظرية ما بعد التالية مهمة جدًا.

نظرية بوست .لكي تكتمل مجموعة من الوظائف K، من الضروري والكافي أن تتضمن وظائف لا تنتمي إلى كل فئة من الفئات T 0 ,ت 1 ,ل,م,س.

لاحظ أن ماذا ضروري هذا صياغات بديهي لذا كيف لو هذا كل شئ المهام من توظيف لمتضمنة الخامس واحد من المدرجة الطبقات، الذي - التي و الجميع التراكبات, أ وسائل، و دائرة مقصورة توظيف متضمنة كان الخامس هذا فصل و فصل للا استطاع يكون ممتلىء.

قدرة هذا صياغات مثبت كافٍ صعب، لهذا لا يظهر هنا.

من هذه النظرية تتبع طريقة بسيطة إلى حد ما لتحديد مدى اكتمال مجموعة معينة من الوظائف. ولكل وظيفة من هذه الوظائف، يتم تحديد العضوية في الفئات المذكورة أعلاه. يتم إدخال النتائج في ما يسمى جدول المشاركات(في مثالنا، تم تجميع هذا الجدول لأربع وظائف، وتشير علامة "+" إلى أن الوظيفة تنتمي إلى الفئة المقابلة، وعلامة "-" تعني أن الوظيفة غير مدرجة فيها).

وفقًا لنظرية بوست، ستكون مجموعة الوظائف كاملة إذا وفقط إذا كان هناك ناقص واحد على الأقل في كل عمود من جدول النشر. وهكذا يتبين من الجدول أعلاه أن هذه الوظائف الأربع تشكل مجموعة كاملة، لكن هذه الوظائف ليست أساسًا. من هذه الوظائف يمكنك تشكيل قاعدتين: F 3 ,F 1 و F 3 ,F 2. المجموعات الكاملة هي أي مجموعات تحتوي على بعض الأساس.

يستنتج مباشرة من جدول Post أن عدد الوظائف الأساسية لا يمكن أن يكون أكثر من 5. وليس من الصعب إثبات أن هذا العدد في الواقع أقل من أو يساوي 4.