الاكتمال (المنطق)

تكون اللغة الرسمية كاملة التعبير إذا استطاعت التعبير عن الموضوع الذي صُممت من أجله.

تعتبر مجموعة الروابط المنطقية المرتبطة بنظام رسمي كاملة وظيفيًا إذا كان بإمكانها التعبير عن جميع الوظائف الافتراضية .

الاكتمال الدلالي هو عكس السلامة في الأنظمة الصورية . يكون النظام الصوري مكتملًا من حيث التكرار أو "مكتملًا دلاليًا" عندما تكون جميع عباراته التكرارية نظريات ، بينما يكون النظام الصوري "سليمًا" عندما تكون جميع نظرياته تكرارية (أي أنها صيغ صحيحة دلاليًا: صيغ صحيحة في كل تفسير للغة النظام يتوافق مع قواعده). أي أن النظام الصوري يكون مكتملًا دلاليًا إذا:

${\displaystyle \models _{\mathcal {S}}\varphi \ \implies \ \vdash _{\mathcal {S}}\varphi .}$^{[ 1 ]}

على سبيل المثال، تثبت نظرية غودل للاكتمال الاكتمال الدلالي لمنطق الرتبة الأولى .

يكون النظام الرسمي S كاملاً بقوة أو كاملاً بالمعنى القوي إذا كان لكل مجموعة من المقدمات Γ، يمكن اشتقاق أي صيغة تتبع دلالياً من Γ من Γ. أي:

${\displaystyle \Gamma \models _{\mathcal {S}}\varphi \ \implies \ \Gamma \vdash _{\mathcal {S}}\varphi .}$

يكون النظام الرسمي S كاملاً من حيث الدحض إذا كان قادراً على استنتاج خطأ من كل مجموعة صيغ غير قابلة للإرضاء . أي:

${\displaystyle \Gamma \models _{\mathcal {S}}\bot \ \implies \ \Gamma \vdash _{\mathcal {S}}\bot .}$^{[ 2 ]}

كل نظام كامل بقوة يكون أيضًا كاملًا من حيث الدحض. وبشكل بديهي، تعني الاكتمالية القوية أنه، بالنظر إلى مجموعة من الصيغ${\displaystyle \Gamma }$، من الممكن حساب كل نتيجة دلالية${\displaystyle \varphi }$ل${\displaystyle \Gamma }$بينما تعني اكتمالية الدحض أنه، بالنظر إلى مجموعة من الصيغ${\displaystyle \Gamma }$وصيغة${\displaystyle \varphi }$، من الممكن التحقق مما إذا${\displaystyle \varphi }$هو نتيجة دلالية لـ${\displaystyle \Gamma }$.

تشمل أمثلة الأنظمة الكاملة في دحض الحجج ما يلي: حل SLD على عبارات هورن ، والتراكب على منطق الرتبة الأولى الشرطي المعادل، وحل روبنسون على مجموعات العبارات. ^{[ 3 ]} أما الأخير فليس كاملاً تماماً: على سبيل المثال${\displaystyle \{a\}\models a\lor b}$ينطبق هذا حتى في المجموعة الفرعية الافتراضية لمنطق الرتبة الأولى، ولكن${\displaystyle a\lor b}$لا يمكن استخلاصها من${\displaystyle \{a\}}$بقرار. ومع ذلك،${\displaystyle \{a,\lnot (a\lor b)\}\vdash \bot }$يمكن استخلاصها.

يكون النظام الصوري S كاملاً نحوياً أو استنتاجياً أو أقصىياً أو منفياً إذا كان لكل جملة (صيغة مغلقة) φ في لغة النظام إما φ أو ¬φ نظرية في S. والاكتمال النحوي خاصية أقوى من الاكتمال الدلالي. إذا كان النظام الصوري كاملاً نحوياً، تُسمى النظرية الصورية المقابلة له كاملة إذا كانت نظرية متسقة . وتُبين نظرية عدم الاكتمال لغودل أن أي نظام قابل للحساب يتمتع بقوة كافية، مثل حساب بيانو ، لا يمكن أن يكون متسقاً وكاملاً نحوياً في آن واحد.

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

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

تكون النظرية كاملة النموذج إذا وفقط إذا كان كل تضمين لنماذجها تضمينًا أوليًا .