قابلية الإرضاء

في المنطق الرياضي ، تكون الصيغة قابلة للتحقيق إذا كانت صحيحة عند تعيين قيم معينة لمتغيراتها . على سبيل المثال، الصيغة${\displaystyle x+3=y}$يكون قابلاً للإرضاء لأنه صحيح عندما${\displaystyle x=3}$و${\displaystyle y=6}$بينما الصيغة${\displaystyle x+1=x}$لا يمكن تحقيقها على مجموعة الأعداد الصحيحة. المفهوم المقابل لقابلية التحقيق هو الصلاحية ؛ تكون الصيغة صحيحة إذا كان كل تعيين لقيم متغيراتها يجعلها صحيحة. على سبيل المثال،${\displaystyle x+3=3+x}$صحيح على الأعداد الصحيحة، ولكن${\displaystyle x+3=y}$ليس كذلك.

من الناحية الرسمية، تُدرس قابلية الإرضاء بالنسبة لمنطق ثابت يُحدد بنية الرموز المسموح بها، مثل منطق الرتبة الأولى ، أو منطق الرتبة الثانية ، أو منطق القضايا . ومع ذلك، فبدلاً من أن تكون قابلة الإرضاء خاصية نحوية، فهي خاصية دلالية لأنها ترتبط بمعنى الرموز ، على سبيل المثال، معنى${\displaystyle +}$في صيغة مثل${\displaystyle x+1=x}$رسميًا، نُعرّف التفسير (أو النموذج ) بأنه إسناد قيم للمتغيرات وإسناد معنى لجميع الرموز غير المنطقية الأخرى، ويُقال إن الصيغة قابلة للتحقيق إذا كان هناك تفسير يجعلها صحيحة. ^{[ 1 ]} في حين أن هذا يسمح بتفسيرات غير قياسية للرموز مثل${\displaystyle +}$يمكن تقييد معناها من خلال تقديم بديهيات إضافية . تتناول مسألة قابلية الإرضاء وفقًا للنظريات قابلية إرضاء صيغة ما بالنسبة لنظرية رسمية ، وهي مجموعة (محدودة أو غير محدودة) من البديهيات.

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

تُعدّ مسألة تحديد ما إذا كانت صيغة في منطق القضايا قابلةً للإرضاء مسألةً قابلةً للتقرير ، وتُعرف بمسألة الإرضاء البولياني (SAT). وبشكل عام، فإنّ مسألة تحديد ما إذا كانت جملة في منطق الرتبة الأولى قابلةً للإرضاء ليست قابلةً للتقرير. في الجبر الشامل ، ونظرية المعادلات ، وإثبات النظريات الآلي ، تُستخدم طرق إعادة كتابة المصطلحات ، وإغلاق التطابق ، والتوحيد لمحاولة تحديد قابلية الإرضاء. وتعتمد قابلية تقرير نظرية معينة على ما إذا كانت هذه النظرية خالية من المتغيرات وعلى شروط أخرى. ^{[ 2 ]}

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

بالنسبة للمنطق الذي لا يتضمن النفي، مثل حساب القضايا الإيجابي ، قد لا تكون مسألتا الصلاحية والإرضاء مرتبطتين. في حالة حساب القضايا الإيجابي ، تكون مسألة الإرضاء بديهية، إذ أن كل صيغة قابلة للإرضاء، بينما تكون مسألة الصلاحية مسألة كاملة من نوع co-NP .

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

في منطق الرتبة الأولى ، تُعدّ مسألة الإرضاء غير قابلة للتقرير . وبشكل أدق، هي مسألة كاملة من نوع co-RE، وبالتالي فهي غير قابلة للتقرير الجزئي . ^{[ 3 ]} ترتبط هذه الحقيقة بعدم قابلية تقرير مسألة الصلاحية في منطق الرتبة الأولى. وقد طرح ديفيد هيلبرت مسألة حالة مسألة الصلاحية لأول مرة ، فيما يُعرف بمسألة القرار . تُعدّ الصلاحية الشاملة لصيغة ما مسألة قابلة للتقرير الجزئي وفقًا لنظرية غودل للاكتمال . إذا كانت مسألة الإرضاء أيضًا مسألة قابلة للتقرير الجزئي، فإن مسألة وجود النماذج المضادة ستكون كذلك (للصيغة نماذج مضادة إذا وفقط إذا كان نفيها قابلاً للإرضاء). وبالتالي، ستكون مسألة الصلاحية المنطقية قابلة للتقرير، وهو ما يتناقض مع نظرية تشرش-تورينج ، وهي نتيجة تُشير إلى الإجابة السلبية لمسألة القرار.

في نظرية النماذج ، تكون الصيغة الذرية قابلة للتحقيق إذا وُجدت مجموعة من عناصر بنية ما تجعل الصيغة صحيحة. ^{[ 4 ]} إذا كانت A بنية، وφ صيغة، و a مجموعة من العناصر، مأخوذة من البنية، والتي تحقق φ، فإنه يُكتب عادةً على النحو التالي:

A ⊧ φ [a]

إذا لم يكن لـ φ متغيرات حرة، أي إذا كانت φ جملة ذرية ، وكانت محققة بواسطة A ، فإنه يُكتب

A ⊧ φ

في هذه الحالة، يمكن القول أيضًا أن A نموذج لـ φ، أو أن φ صحيحة في A. إذا كانت T مجموعة من الجمل الذرية (نظرية) التي تحققها A ، يُكتب

أ ⊧ ت

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

لا يشترط أن تتطابق قابلية الإرضاء المحدودة وقابلية الإرضاء بشكل عام. على سبيل المثال، لننظر إلى صيغة منطق الرتبة الأولى التي تم الحصول عليها من خلال ربط الجمل التالية، حيث${\displaystyle a_{0}}$و${\displaystyle a_{1}}$هي ثوابت :

• ${\displaystyle R(a_{0},a_{1})}$
• ${\displaystyle \forall xy(R(x,y)\rightarrow \exists zR(y,z))}$
• ${\displaystyle \forall xyz(R(y,x)\wedge R(z,x)\rightarrow y=z))}$
• ${\displaystyle \forall x\neg R(x,a_{0})}$

الصيغة الناتجة لها نموذج لانهائي${\displaystyle R(a_{0},a_{1}),R(a_{1},a_{2}),\ldots }$لكن يمكن إثبات أنه ليس له نموذج نهائي (بدءًا من حقيقة${\displaystyle R(a_{0},a_{1})}$وباتباع سلسلة${\displaystyle R}$بالنسبة للذرات التي يجب أن توجد وفقًا للبديهية الثانية، فإن محدودية النموذج تتطلب وجود حلقة، وهو ما يخالف البديهيتين الثالثة والرابعة، سواء أكانت الحلقة تعود إلى نقطة البداية أم لا.${\displaystyle a_{0}}$أو على عنصر مختلف).

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

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

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

مصدر الجدول: بوكمير وويسبفينينغ . ^{[ 5 ] : 754}

بالنسبة للقيود الخطية، يقدم الجدول التالي صورة أكثر اكتمالاً.

مصدر الجدول: بوكمير وويسبفينينغ . ^{[ 5 ] : 755}

• 2- الرضا
• مشكلة إرضاء المنطق البولياني
• قابلية إرضاء الدائرة
• مسائل كارب الـ 21 الكاملة من فئة NP
• صحة
• إرضاء القيود

• بولوس، جورج؛ بورغيس، جون؛ جيفري، ريتشارد (2007). الحوسبة والمنطق (الطبعة الخامسة  ). مطبعة جامعة كامبريدج.

• دانيال كرونينغ ؛ عوفر ستريشمان (2008). إجراءات اتخاذ القرار: منظور خوارزمي . سبرينغر ساينس آند بيزنس ميديا. ISBN 978-3-540-74104-6.
• أ. بير؛ م. هيول؛ هـ. فان مارين؛ ت. والش، محرران (2009). دليل الإرضاء . دار نشر IOS. رقم ISBN 978-1-60750-376-7.