القاعدة المقبولة

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

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

لنفترض أن لدينا مجموعة من الروابط المنطقية الأساسية (على سبيل المثال،${\displaystyle \{\to ,\land ,\lor ,\bot \}}$في حالة المنطق فوق الحدسي ، أو${\displaystyle \{\to ,\bot ,\Box \}}$في حالة المنطق أحادي النمط ). تُبنى الصيغ السليمة بحرية باستخدام هذه الروابط من مجموعة لا نهائية قابلة للعد من المتغيرات الافتراضية p0 _، p1 _، ... . الاستبدال σ هو دالة من الصيغ إلى الصيغ تتبادل مع تطبيقات الروابط، أي

${\displaystyle \sigma f(A_{1},\dots ,A_{n})=f(\sigma A_{1},\dots ,\sigma A_{n})}$

لكل رابط f ، والصيغ A1 _، ...، An _. (يمكننا أيضًا تطبيق استبدالات على مجموعات الصيغ Γ، مما يجعل σΓ = { σA : A ∈ Γ}. ) علاقة النتيجة على نمط تارسكي ^{[ 1 ]} هي علاقة${\displaystyle \vdash }$بين مجموعات الصيغ، والصيغ، بحيث

لجميع الصيغ A و B ومجموعات الصيغ Γ و Δ. علاقة نتيجة بحيث

يُطلق على جميع عمليات الاستبدال σ اسم "بنيوي" . (لاحظ أن مصطلح "بنيوي" كما هو مستخدم هنا وفيما يلي لا يرتبط بمفهوم القواعد البنيوية في حسابات المتتاليات ). تُسمى علاقة الاستدلال البنيوي منطقًا افتراضيًا . الصيغة A هي نظرية منطقية .${\displaystyle \vdash }$لو${\displaystyle \varnothing \vdash A}$.

على سبيل المثال، نحدد منطقًا فوق حدسي L بعلاقة النتيجة القياسية الخاصة به${\displaystyle \vdash _{L}}$يتم توليدها بواسطة القياس المنطقي والبديهيات، ونحدد منطقًا مشروطًا عاديًا بعلاقة النتيجة الشاملة الخاصة به${\displaystyle \vdash _{L}}$تم توليدها بواسطة قاعدة الاستدلال، والضرورة، ونظريات المنطق (كبديهيات).

تُعطى قاعدة الاستدلال البنيوي ^{[ 2 ]} (أو القاعدة اختصارًا) بواسطة زوج (Γ، B )، وعادةً ما يُكتب على النحو التالي:

${\displaystyle {\frac {A_{1},\dots ,A_{n}}{B}}\qquad {\text{or}}\qquad A_{1},\dots ,A_{n}/B,}$

حيث Γ  =  { A ₁ , ... , A _n } هي مجموعة منتهية من الصيغ، و B هي صيغة. مثال على هذه القاعدة هو

${\displaystyle \sigma A_{1},\dots ,\sigma A_{n}/\sigma B}$

بالنسبة للاستبدال σ . يمكن اشتقاق القاعدة Γ/ B في${\displaystyle \vdash }$، لو${\displaystyle \Gamma \vdash B}$تكون القاعدة مقبولة إذا كانت σB نظريةً في كل حالة من حالاتها، كلما كانت جميع الصيغ المشتقة من σΓ نظريات. ^{[ 3 ]} بعبارة أخرى، تكون القاعدة مقبولة إذا لم تؤدِّ إضافتها إلى المنطق إلى نظريات جديدة. ^{[ 4 ]} نكتب أيضًا${\displaystyle \Gamma \mathrel {|\!\!\!\sim } B}$إذا كان Γ/ B مقبولاً. (لاحظ أن${\displaystyle {\phantom {.}}\!{|\!\!\!\sim }}$(هي علاقة تبعية هيكلية بحد ذاتها.)

كل قاعدة قابلة للاستنتاج مقبولة، ولكن ليس العكس صحيحًا بشكل عام. يكون المنطق مكتملًا بنيويًا إذا كانت كل قاعدة مقبولة قابلة للاستنتاج، أي${\displaystyle {\vdash }={\,|\!\!\!\sim }}$[ ^{5 ]​}

في المنطق الذي يتميز برابط اقتران حسن السلوك (مثل المنطق فوق الحدسي أو المنطق الموجه)، توجد قاعدة${\displaystyle A_{1},\dots ,A_{n}/B}$يعادل${\displaystyle A_{1}\land \dots \land A_{n}/B}$فيما يتعلق بالمقبولية والاستنباط. لذلك، جرت العادة على التعامل فقط مع القواعد الأحادية أ / ب .

• يُعتبر حساب القضايا الكلاسيكي ( CPC ) كاملاً من الناحية الهيكلية. ^{[ 6 ]} في الواقع، لنفترض أن A / B قاعدة غير قابلة للاشتقاق، ولنُثبِّت قيمة v بحيث يكون v ( A ) = 1 و v ( B ) = 0. ولنُعرِّف استبدالًا σ بحيث يكون لكل متغير p ، σp =${\displaystyle \top }$إذا كانت v ( p ) = 1، و σp =${\displaystyle \bot }$إذا كانت v ( p ) = 0، فإن σA نظرية، لكن σB ليست كذلك (في الواقع، ¬σB نظرية ). وبالتالي، فإن القاعدة A / B غير مقبولة أيضًا. (ينطبق نفس الاستدلال على أي منطق متعدد القيم L كامل بالنسبة لمصفوفة منطقية، حيث يكون لكل عنصر اسم في لغة L ).
• قاعدة كريزل - بوتنام (المعروفة أيضًا باسم قاعدة هاروب ، أو قاعدة استقلال المقدمات )

${\displaystyle ({\mathit {KPR}})\qquad {\frac {\neg p\to q\lor r}{(\neg p\to q)\lor (\neg p\to r)}}}$

مقبول في حساب القضايا الحدسي ( IPC ). في الواقع، هو مقبول في كل منطق فوق حدسي. ^{[ 7 ]} من ناحية أخرى، الصيغة

${\displaystyle (\neg p\to q\lor r)\to ((\neg p\to q)\lor (\neg p\to r))}$

ليست هذه نظرية حدسية؛ لذا فإن KPR غير قابلة للاستنتاج في IPC . وعلى وجه الخصوص، فإن IPC ليست كاملة بنيوياً.

• القاعدة

${\displaystyle {\frac {\Box p}{p}}}$

يُعدّ هذا مقبولاً في العديد من المنطق الموجه، مثل K و D و K 4 و S 4 و GL (انظر هذا الجدول لأسماء المنطق الموجه). وهو قابل للاشتقاق في S 4، ولكنه غير قابل للاشتقاق في K أو D أو K 4 أو GL .

• القاعدة

${\displaystyle {\frac {\Diamond p\land \Diamond \neg p}{\bot }}}$

مقبول في المنطق العادي${\displaystyle L\supseteq S4.3}$[ ^{8 ]} يمكن اشتقاقها في GL و S 4.1 ^، ولكنها ليست قابلة للاشتقاق في K أو D أو K 4 أو S 4 أو S 5.

• حكم لوب

${\displaystyle ({\mathit {LR}})\qquad {\frac {\Box p\to p}{p}}}$

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

• منطق غودل-دوميت ( LC ) والمنطق الموجه Grz.3 مكتملان بنيويًا. ^{[ 9 ]} كما أن منطق المنتج الضبابي مكتمل بنيويًا أيضًا. ^{[ 10 ]}

السؤال الأساسي حول القواعد المقبولة لمنطق معين هو ما إذا كانت مجموعة جميع القواعد المقبولة قابلة للتقرير . تجدر الإشارة إلى أن المشكلة ليست تافهة حتى لو كان المنطق نفسه (أي مجموعة نظرياته) قابلاً للتقرير : فتعريف مقبولية القاعدة A / B يتضمن مُكمِّمًا شاملاً غير محدود على جميع الاستبدالات الافتراضية. وبالتالي، فإننا نعلم مسبقًا فقط أن مقبولية القاعدة في منطق قابل للتقرير هي${\displaystyle \Pi _{1}^{0}}$(أي أن مكملها قابل للتعداد بشكل متكرر ). على سبيل المثال، من المعروف أن القبول في المنطقين ثنائيي النمط K _u و K 4 _u (امتدادات K أو K 4 مع النمطية الشاملة ) غير قابل للتقرير. ^{[ 11 ]} والجدير بالذكر أن قابلية تقرير القبول في منطق النمط الأساسي K تُعد مشكلة مفتوحة رئيسية .

مع ذلك، من المعروف أن مقبولية القواعد قابلة للتقرير في العديد من المنطق الموجه والمنطق فوق الحدسي. وقد صاغ ريباكوف أولى إجراءات القرار للقواعد المقبولة في المنطق الموجه المتعدي الأساسي ، باستخدام الشكل المختزل للقواعد . ^{[ 12 ]} تُسمى القاعدة الموجهة في المتغيرات p₀ _، ...، pₖ مختزلة إذا كانت على الشكل التالي _:

${\displaystyle {\frac {\bigvee _{i=0}^{n}{\bigl (}\bigwedge _{j=0}^{k}\neg _{i,j}^{0}p_{j}\land \bigwedge _{j=0}^{k}\neg _{i,j}^{1}\Box p_{j}{\bigr )}}{p_{0}}},}$

حيث كل${\displaystyle \neg _{i,j}^{u}}$إما أن يكون فارغًا، أو نفيًا${\displaystyle \neg }$لكل قاعدة r ، يمكننا فعليًا بناء قاعدة مُختزلة s (تُسمى الشكل المُختزل لـ r ) بحيث يقبل أي منطق القاعدة r (أو يستنتجها) إذا وفقط إذا كان يقبل القاعدة s (أو يستنتجها) ، وذلك بإدخال متغيرات امتداد لجميع الصيغ الفرعية في A ، والتعبير عن النتيجة بالصيغة الانفصالية الكاملة . وبالتالي، يكفي بناء خوارزمية قرار لقبول القواعد المُختزلة.

يترك${\displaystyle \textstyle \bigvee _{i=0}^{n}\varphi _{i}/p_{0}}$نعتبر قاعدة مختصرة كما سبق. نحدد كل رابط.${\displaystyle \varphi _{i}}$مع المجموعة${\displaystyle \{\neg _{i,j}^{0}p_{j},\neg _{i,j}^{1}\Box p_{j}\mid j\leq k\}}$من عناصرها المتصلة. لأي مجموعة جزئية W من المجموعة${\displaystyle \{\varphi _{i}\mid i\leq n\}}$من بين جميع الاقترانات، دعونا نحدد نموذج كريپكي${\displaystyle M=\langle W,R,{\Vdash }\rangle }$بواسطة

${\displaystyle \varphi _{i}\Vdash p_{j}\iff p_{j}\in \varphi _{i},}$

${\displaystyle \varphi _{i}\,R\,\varphi _{i'}\iff \forall j\leq k\,(\Box p_{j}\in \varphi _{i}\Rightarrow \{p_{j},\Box p_{j}\}\subseteq \varphi _{i'}).}$

ثم يقدم ما يلي معيارًا خوارزميًا للقبول في K 4: ^{[ 13 ]}

النظرية . القاعدة${\displaystyle \textstyle \bigvee _{i=0}^{n}\varphi _{i}/p_{0}}$لا يكون مقبولاً في K 4 إذا وفقط إذا وُجدت مجموعة${\displaystyle W\subseteq \{\varphi _{i}\mid i\leq n\}}$بحيث

1. ${\displaystyle \varphi _{i}\nVdash p_{0}}$بالنسبة للبعض${\displaystyle i\leq n,}$
2. ${\displaystyle \varphi _{i}\Vdash \varphi _{i}}$لكل${\displaystyle i\leq n,}$
3. لكل مجموعة جزئية D من W يوجد عناصر${\displaystyle \alpha ,\beta \in W}$بحيث تكون المكافئات

${\displaystyle \alpha \Vdash \Box p_{j}}$إذا وفقط إذا${\displaystyle \varphi \Vdash p_{j}\land \Box p_{j}}$لكل${\displaystyle \varphi \in D}$

${\displaystyle \alpha \Vdash \Box p_{j}}$إذا وفقط إذا${\displaystyle \alpha \Vdash p_{j}}$و${\displaystyle \varphi \Vdash p_{j}\land \Box p_{j}}$لكل${\displaystyle \varphi \in D}$

ينطبق هذا على جميع قيم j .

يمكن إيجاد معايير مماثلة للمنطق S 4 و GL و Grz . ^{[ 14 ]} علاوة على ذلك، يمكن اختزال المقبولية في المنطق الحدسي إلى المقبولية في Grz باستخدام ترجمة غودل-ماكينزي-تارسكي : ^{[ 15 ]}

${\displaystyle A\,|\!\!\!\sim _{IPC}B}$إذا وفقط إذا${\displaystyle T(A)\,|\!\!\!\sim _{Grz}T(B).}$

قام ريباكوف (1997) بتطوير تقنيات أكثر تطوراً لإثبات قابلية الحسم في القبول، والتي تنطبق على فئة قوية (لا نهائية) من المنطق المتعدي (أي، توسيع K 4 أو IPC ) والمنطق فوق الحدسي، بما في ذلك على سبيل المثال S 4.1، S 4.2، S 4.3، KC ، T _k (بالإضافة إلى المنطق المذكور أعلاه IPC ، K 4، S 4، GL ، Grz ). ^{[ 16 ]}

على الرغم من إمكانية حسمها، فإن مشكلة القبول تتسم بتعقيد حسابي عالٍ نسبيًا ، حتى في المنطق البسيط: فقبول القواعد في المنطق المتعدي الأساسي IPC و K⁴ و S⁴ و GL و Grz هو مسألة كاملة من نوع coNEXP . ^{[ 17 ]} ويجب مقارنة ذلك بمشكلة الاشتقاق (للقواعد أو الصيغ) في هذه المنطق، والتي هي مسألة كاملة من نوع PSPACE . ^{[ 18 ]}

يرتبط مفهوم القبول في منطق القضايا ارتباطًا وثيقًا بالتوحيد في نظرية المعادلات للجبر الموجه أو جبر هيتينغ . وقد طوّر غيلاردي (1999، 2000) هذا الارتباط. في الإطار المنطقي، يُعرَّف موحد الصيغة A في لغة المنطق L ( موحد L اختصارًا) بأنه استبدال σ بحيث تكون σA نظرية في L. (باستخدام هذا المفهوم، يمكننا إعادة صياغة قبول القاعدة A / B في L على النحو التالي: "كل موحد L للصيغة A هو موحد L للصيغة B "). يكون موحد L σ أقل عمومية من موحد L τ ، ويُكتب على النحو σ ≤ τ ، إذا وُجد استبدال υ بحيث

${\displaystyle \vdash _{L}\sigma p\leftrightarrow \upsilon \tau p}$

لكل متغير p ، تُعرَّف المجموعة الكاملة من مُوحِّدات الصيغة A بأنها مجموعة S من مُوحِّدات L للصيغة A ، بحيث يكون كل مُوحِّد L للصيغة A أقل عمومية من مُوحِّد ما من S. أما المُوحِّد الأكثر عمومية (MGU) للصيغة A فهو مُوحِّد σ بحيث تكون { σ } مجموعة كاملة من مُوحِّدات الصيغة A. وبناءً على ذلك، إذا كانت S مجموعة كاملة من مُوحِّدات الصيغة A ، فإن القاعدة A / B تكون مقبولة من حيث L إذا وفقط إذا كان كل σ في S مُوحِّد L للصيغة B. وبالتالي، يُمكننا تحديد القواعد المقبولة إذا استطعنا إيجاد مجموعات كاملة من المُوحِّدات ذات سلوك جيد.

تُعدّ الصيغ الإسقاطية فئة مهمة من الصيغ التي تمتلك مُوحِّدًا عامًا للغاية : وهي صيغ A بحيث يوجد مُوحِّد σ لـ A بحيث

${\displaystyle A\vdash _{L}B\leftrightarrow \sigma B}$

لكل صيغة B. لاحظ أن σ هي وحدة منطقية متعددة (MGU) لـ A. في المنطق الموجه المتعدي والمنطق فوق الحدسي ذي خاصية النموذج المحدود ، يمكن وصف الصيغ الإسقاطية دلاليًا بأنها تلك التي تتمتع مجموعة نماذج L المحدودة الخاصة بها بخاصية التمديد : ^{[ 19 ]} إذا كان M نموذج كريپكي L محدودًا بجذر r ومجموعة عناصره أحادية ، وكانت الصيغة A صحيحة عند جميع نقاط M باستثناء r ، فيمكننا تغيير قيم المتغيرات في r بحيث تصبح A صحيحة عند r أيضًا. علاوة على ذلك ، يقدم البرهان بناءً صريحًا لوحدة منطقية متعددة (MGU) لصيغة إسقاطية معينة A.

في المنطق المتعدي الأساسي IPC و K 4 و S 4 و GL و Grz (وبشكل أعم في أي منطق متعدٍ يتمتع بخاصية النموذج المحدود، والذي تحقق مجموعة إطاره المحدود نوعًا آخر من خصائص التمديد)، يمكننا فعليًا بناء تقريب إسقاطي Π ( A ) لأي صيغة A : ^{[ 20 ]} مجموعة محدودة من الصيغ الإسقاطية بحيث

1. ${\displaystyle P\vdash _{L}A}$لكل${\displaystyle P\in \Pi (A),}$
2. كل عنصر موحد لـ A هو عنصر موحد لصيغة من Π( A ).

يترتب على ذلك أن مجموعة وحدات التوحيد الكبرى لعناصر Π( A ) هي مجموعة كاملة من وحدات التوحيد لـ A. علاوة على ذلك، إذا كانت P صيغة إسقاطية، فإن

${\displaystyle P\,|\!\!\!\sim _{L}B}$إذا وفقط إذا${\displaystyle P\vdash _{L}B}$

لأي صيغة B. وبالتالي نحصل على التوصيف الفعال التالي للقواعد المقبولة: ^{[ 21 ]}

${\displaystyle A\,|\!\!\!\sim _{L}B}$إذا وفقط إذا${\displaystyle \forall P\in \Pi (A)\,(P\vdash _{L}B).}$

ليكن L منطقًا. تُسمى مجموعة R من القواعد المقبولة في L أساسًا ^{[ 22 ]} للقواعد المقبولة، إذا أمكن اشتقاق كل قاعدة مقبولة Γ/ B من R والقواعد القابلة للاشتقاق في L ، باستخدام الاستبدال والتركيب والتخفيف. بعبارة أخرى، R أساس إذا وفقط إذا${\displaystyle {\phantom {.}}\!{|\!\!\!\sim _{L}}}$هي أصغر علاقة تبعية هيكلية تتضمن${\displaystyle \vdash _{L}}$و R .

لاحظ أن قابلية حسم القواعد المقبولة لمنطق قابل للحسم تُكافئ وجود قواعد تكرارية (أو قابلة للتعداد التكراري ): فمن جهة، تُعدّ مجموعة جميع القواعد المقبولة قاعدة تكرارية إذا كانت قابلية الحسم قابلة للحسم. ومن جهة أخرى، تكون مجموعة القواعد المقبولة دائمًا قابلة للتعداد التكراري المشترك، وإذا كان لدينا أيضًا قاعدة قابلة للتعداد التكراري، فإن مجموعة القواعد المقبولة تكون أيضًا قابلة للتعداد التكراري؛ وبالتالي فهي قابلة للحسم. (بعبارة أخرى، يمكننا حسم قابلية حسم A / B باستخدام الخوارزمية التالية : نبدأ بالتوازي بحثين شاملين ، أحدهما عن استبدال σ يوحد A دون B ، والآخر عن اشتقاق A / B من R و${\displaystyle \vdash _{L}}$(يجب أن تسفر إحدى عمليات البحث في النهاية عن إجابة.) بصرف النظر عن قابلية الحسم، فإن الأسس الصريحة للقواعد المقبولة مفيدة لبعض التطبيقات، على سبيل المثال في تعقيد البرهان . ^{[ 23 ]}

بالنسبة لمنطق معين، يمكننا أن نسأل عما إذا كان له أساس تكراري أو محدود من القواعد المقبولة، وأن نقدم أساسًا صريحًا. إذا لم يكن للمنطق أساس محدود، فإنه مع ذلك يمكن أن يكون له أساس مستقل : أساس R بحيث لا تكون أي مجموعة جزئية فعلية من R أساسًا له.

بشكل عام، لا يُمكن قول الكثير عن وجود قواعد ذات خصائص مرغوبة. على سبيل المثال، في حين أن المنطق الجدولي يتميز عمومًا بسلوك جيد، وقابلية وضع بديهيات محدودة دائمًا، إلا أن هناك منطقًا جدوليًا موجّهًا بدون قاعدة محدودة أو مستقلة من القواعد. ^{[ 24 ]} القواعد المحدودة نادرة نسبيًا: حتى المنطق المتعدي الأساسي IPC و K4 و S4 و GL و Grz لا يمتلك قاعدة محدودة من القواعد المقبولة، ^{[ 25 ]} على الرغم من امتلاكه قواعد مستقلة. ^{[ 26 ]}

تكون القاعدة Γ/ B صالحة في إطار كريپكي مشروط أو حدسي${\displaystyle F=\langle W,R\rangle }$إذا كان ما يلي صحيحًا لكل عملية تقييم${\displaystyle \Vdash }$في فا :

إن كان ذلك للجميع${\displaystyle A\in \Gamma }$${\displaystyle \forall x\in W\,(x\Vdash A)}$، ثم${\displaystyle \forall x\in W\,(x\Vdash B)}$.

(يمكن تعميم التعريف بسهولة ليشمل الأطر العامة ، إذا لزم الأمر.)

ليكن X مجموعة جزئية من W ، و t نقطة في W. نقول إن t هي

• سلف انعكاسي ضيق لـ X ، إذا كان لكل y في W : t R y إذا وفقط إذا كان t = y أو لبعض x في X : x = y أو x R y ،
• سلف ضيق غير انعكاسي لـ X ، إذا كان لكل y في W : t R y إذا وفقط إذا كان لبعض x في X : x = y أو x R y .

نقول أن الإطار F له أسلاف محكمين انعكاسيين (غير انعكاسيين ) ، إذا كان لكل مجموعة جزئية محدودة X من W ، يوجد سلف محكم انعكاسي (غير انعكاسي) لـ X في W.

لدينا: ^{[ 31 ]}

• تكون القاعدة مقبولة في قانون العقوبات الدولي إذا وفقط إذا كانت صالحة في جميع الأطر الحدسية التي لها أسلاف انعكاسية محكمة.
• تكون القاعدة مقبولة في K 4 إذا وفقط إذا كانت صالحة في جميع الأطر المتعدية التي لها أسلاف ضيقة انعكاسية وغير انعكاسية،
• تكون القاعدة مقبولة في S 4 إذا وفقط إذا كانت صالحة في جميع الأطر الانعكاسية المتعدية التي لها أسلاف انعكاسية محكمة،
• تكون القاعدة مقبولة في GL إذا وفقط إذا كانت صالحة في جميع الأطر العكسية المتعدية ذات الأساس الجيد والتي لها أسلاف ضيقة غير انعكاسية.

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

على الرغم من أن التصنيف العام للمنطق الكامل هيكليًا ليس بالمهمة السهلة، إلا أن لدينا فهمًا جيدًا لبعض الحالات الخاصة.

المنطق الحدسي نفسه ليس مكتملاً بنيوياً، لكن أجزاءه قد تتصرف بشكل مختلف. بمعنى آخر، أي قاعدة خالية من الفصل أو قاعدة خالية من الاستلزام مقبولة في منطق فوق حدسي قابلة للاستنتاج. ^{[ 32 ]} من ناحية أخرى، قاعدة النعناع

${\displaystyle {\frac {(p\to q)\to p\lor r}{((p\to q)\to p)\lor ((p\to q)\to r)}}}$

مقبول في المنطق الحدسي ولكنه غير قابل للاستنتاج، ولا يحتوي إلا على الاستلزام والفصل.

نعرف المنطق المتعدي غير الكامل بنيويًا. يُسمى المنطق كاملًا بنيويًا وراثيًا إذا كان أي امتداد له كاملًا بنيويًا. على سبيل المثال، المنطق الكلاسيكي، بالإضافة إلى المنطقين LC و Grz.3 المذكورين أعلاه، كاملان بنيويًا وراثيًا. وقدّم كلٌ من سيتكين وريباكوف وصفًا كاملًا للمنطق الموجه المتعدي والحدسي الفائق الكامل بنيويًا وراثيًا. أي أن المنطق الحدسي الفائق يكون كاملًا بنيويًا وراثيًا إذا وفقط إذا لم يكن صالحًا في أي من أطر كريپكي الخمسة ^{[ 9 ].}

وبالمثل، يكون امتداد K 4 كاملاً بنيوياً وراثياً إذا وفقط إذا لم يكن صالحاً في أي من أطر كريپكي العشرين المحددة (بما في ذلك الأطر الحدسية الخمسة المذكورة أعلاه). ^{[ 9 ]}

توجد منطقات كاملة بنيوياً ليست كاملة بنيوياً وراثياً: على سبيل المثال، منطق ميدفيديف كامل بنيوياً، ^{[ 33 ]} ولكنه مدرج في المنطق غير الكامل بنيوياً KC .

القاعدة التي تحتوي على معلمات هي قاعدة من الشكل التالي:

${\displaystyle {\frac {A(p_{1},\dots ,p_{n},s_{1},\dots ,s_{k})}{B(p_{1},\dots ,p_{n},s_{1},\dots ,s_{k})}},}$

تُقسّم متغيراتها إلى متغيرات "عادية" pᵢ _، ومعاملات sᵢ . تكون القاعدة مقبولة _من النوع L إذا كان كل _{مُوحِّد} من النوع L، σ، _{للمجموعة} A بحيث يكون σᵢ = sᵢ لكل i، هو أيضًا مُوحِّد للمجموعة B. وتنطبق نتائج قابلية الحسم الأساسية للقواعد المقبولة أيضًا على القواعد ذات المعاملات. ^{[ 34 ]}  

قاعدة الاستنتاجات المتعددة هي زوج (Γ,Δ) من مجموعتين محدودتين من الصيغ، مكتوبة على النحو التالي:

${\displaystyle {\frac {A_{1},\dots ,A_{n}}{B_{1},\dots ,B_{m}}}\qquad {\text{or}}\qquad A_{1},\dots ,A_{n}/B_{1},\dots ,B_{m}.}$

تكون هذه القاعدة مقبولة إذا كان كل عنصر موحد في Γ عنصرًا موحدًا لصيغة ما من Δ. ^{[ 35 ]} على سبيل المثال، يكون المنطق L متسقًا إذا وفقط إذا كان يقبل القاعدة

${\displaystyle {\frac {\;\bot \;}{}},}$

والمنطق فوق الحدسي يتمتع بخاصية الفصل إذا وفقط إذا كان يقبل القاعدة

${\displaystyle {\frac {p\lor q}{p,q}}.}$

مرة أخرى، تُعمَّم النتائج الأساسية المتعلقة بالقواعد المقبولة بسلاسة لتشمل قواعد الاستنتاجات المتعددة. ^{[ 36 ]} في المنطق الذي يتضمن صيغة مختلفة لخاصية الفصل، تتمتع قواعد الاستنتاجات المتعددة بنفس القدرة التعبيرية لقواعد الاستنتاج الواحد: على سبيل المثال، في S 4، تكون القاعدة المذكورة أعلاه مكافئة لـ

${\displaystyle {\frac {A_{1},\dots ,A_{n}}{\Box B_{1}\lor \dots \lor \Box B_{m}}}.}$

ومع ذلك، يمكن في كثير من الأحيان استخدام قواعد الاستنتاجات المتعددة لتبسيط الحجج.

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

${\displaystyle {\frac {\Gamma \vdash A,\Delta \qquad \Pi ,A\vdash \Lambda }{\Gamma ,\Pi \vdash \Delta ,\Lambda }}.}$

(يُقال أحيانًا، مجازًا، إن حساب التتابعات (الكامل) يقبل القطع، أي أن نسخته الخالية من القطع تقبله). ومع ذلك، فإن القبول في حسابات التتابعات عادةً ما يكون مجرد صيغة رمزية للقبول في المنطق المقابل: أي حساب تتابعات كامل (على سبيل المثال) للمنطق الحدسي يقبل قاعدة تتابع إذا وفقط إذا كان IPC يقبل قاعدة الصيغة التي نحصل عليها بترجمة كل تتابع.${\displaystyle \Gamma \vdash \Delta }$إلى تركيبتها المميزة${\displaystyle \bigwedge \Gamma \to \bigvee \Delta }$.

• إضافة أسماء جديدة للثوابت والدوال
• التوسع المحافظ

• W. Blok, D. Pigozzi, Algebraizable logics , Memoirs of the American Mathematical Society 77 (1989), no. 396, 1989.
• أ. تشاغروف وم. زاخارياشيف، المنطق الموجه ، سلسلة أدلة أكسفورد للمنطق، المجلد 35، مطبعة جامعة أكسفورد، 1997. ISBN 0-19-853779-4
• ب. سينتولا وج. ميتكالف، الاكتمال البنيوي في المنطق الضبابي ، مجلة نوتردام للمنطق الصوري 50 (2009)، العدد  2، الصفحات  153-182. doi : 10.1215/00294527-2009-004
• AI Citkin, On structurally complete superintuitionistic logics , Soviet Mathematics - Doklady, vol. 19 (1978), pp.  816 – 819.
• إس. غيلاردي، التوحيد في المنطق الحدسي ، مجلة المنطق الرمزي 64 (1999)، العدد 2، الصفحات  859-880. مشروع إقليدس JSTOR
• س. غيلاردي، أفضل حلول المعادلات النمطية ، حوليات المنطق البحت والتطبيقي 102 (2000)، العدد 3، الصفحات  183-198. doi : 10.1016/S0168-0072(99)00032-9
• ر. إيمهوف ، حول القواعد المقبولة لمنطق القضايا الحدسي ، مجلة المنطق الرمزي 66 (2001)، العدد 1، الصفحات  281-294. مشروع إقليدس JSTOR
• آر. إيمهوف، المنطق الوسيط وقواعد فيسر ، مجلة نوتردام للمنطق الصوري 46 (2005)، العدد 1، الصفحات  65-81. doi : 10.1305/ndjfl/1107220674
• ر. إيمهوف، حول قواعد المنطق الوسيط ، أرشيف المنطق الرياضي ، 45 (2006)، العدد 5، الصفحات  581-599. doi : 10.1007/s00153-006-0320-8
• إي. جيرابيك، القواعد المقبولة للمنطق الموجه ، مجلة المنطق والحوسبة 15 (2005)، العدد 4، الصفحات  411-431. doi : 10.1093/logcom/exi029
• إي. جيرابيك، تعقيد القواعد المقبولة ، أرشيف المنطق الرياضي 46 (2007)، العدد 2، الصفحات  73-92. doi : 10.1007/s00153-006-0028-9
• إي. جيرابيك، الأسس المستقلة للقواعد المقبولة ، مجلة المنطق التابعة لمجموعة IGPL، المجلد 16 (2008)، العدد 3، الصفحات  249-267. doi : 10.1093/jigpal/jzn004
• م. كراخت، علاقات النتائج المشروطة ، في: دليل المنطق المشروط (تحرير: ب. بلاكبيرن، ج. فان بنثام، و ف. وولتر)، دراسات في المنطق والاستدلال العملي، المجلد 3، إلسيفير، 2007، الصفحات  492-545. ISBN 978-0-444-51690-9
• P. Lorenzen، Einführung in die operative Logik und Mathematik , Grundlehren der mathematischen Wissenschaften vol. 78، سبرينغر-فيرلاغ، 1955.
• G. Mints and A. Kojevnikov، أنظمة Frege البديهية متكافئة متعدد الحدود ، Zapiski Nauchnyh Seminarov POMI 316 (2004)، الصفحات من  129 إلى 146. مضغوط PS
• T. Prucnal, Structural completeness of Medvedev's propositional calculus , Reports on Mathematical Logic 6 (1976), pp.  103–105.
• تي. بروسنال، حول مسألتين لهارفي فريدمان ، ستوديا لوجيكا 38 (1979)، العدد 3، الصفحات  247-262. doi : 10.1007/BF00405383
• P. روزيير, القواعد المقبولة في حساب الاقتراحات الحدسية , دكتوراه. أطروحة، جامعة باريس السابعة ، 1992. PDF
• في. في. ريباكوف، مقبولية قواعد الاستدلال المنطقي ، دراسات في المنطق وأسس الرياضيات، المجلد 136، إلسيفير، 1997. ISBN 0-444-89505-1
• ف. وولتر، م. زاخارياشيف، عدم قابلية حسم مسائل التوحيد والقبول لمنطقي الوسائط والوصف ، معاملات ACM في المنطق الحسابي 9 (2008)، العدد 4، المقالة رقم 25. doi : 10.1145/1380572.1380574 PDF