انتقل إلى المحتوى
Topos Uranos
العربية

النتيجة الدلالية والتكافؤ الدلالي

ملخص

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

أهداف التعلم

  1. أن يقرّر هل صيغةٌ ما نتيجةٌ دلالية لمجموعة صيغ، منتهية أو غير منتهية، بعرض إسناد يدحض ذلك أو بالبرهان على أنه لا يوجد.
  2. أن يبرهن على خواص النتيجة الدلالية، وعلى مبرهنة الاستنتاج الدلالية، وعلى ردّ النتيجة إلى عدم القابلية للتحقق، وأن يطبّقها.
  3. أن يثبت تكافؤات دلالية بجداول الصدق، وبالحساب بالقيم، وبتعاقبات من التكافؤات، مسمّيًا كل قانون باسمه الصحيح.
  4. أن يبرهن بالاستقراء على التعقيد على مبرهنة الإبدال الدلالي وعلى مبرهنة التعويض المنتظم، وأن يميّز متى تنطبق كلٌّ منهما.

ما يُستعمل من الدرس السابق

أعطى الدرس الخاص بـدلالات منطق القضايا الصيغَ معنى، وهذا الدرس يعدّه معلومًا. الإسناد دالة v ⁣:V→{0,1}v\colon V \to \{0, 1\} تُسند إلى كل متغير قيمة صدق، 11 (صواب) أو 00 (خطأ). وبمبرهنة التعريف بالتراجع على الصيغ، من الدرس الخاص بـالاستقراء، يمتد كل إسناد بطريقة وحيدة إلى جميع الصيغ بواسطة بند النفي المشترك، وهو البند الوحيد اللازم، لأن اللغة لها رابط واحد فقط:

v((φ↓ψ))=1  ⇔  v(φ)=0,    v(ψ)=0v((\varphi \downarrow \psi)) = 1 \;\Leftrightarrow\; v(\varphi) = 0, \;\; v(\psi) = 0

وبسبب وحدانية التمديد، يُكتب v(φ)v(\varphi) أيضًا لقيمة التمديد؛ والحرف vv بلا دليل يدلّ دائمًا على إسناد (وv′v'، ww، uu على إسنادات أخرى)، في حين تحمل المتغيرات دائمًا دليلها. وكما في الدرس الخاص بـالصورنة، تسمّي pp وqq وrr وss وtt المتغيرات من v1v_1 إلى v5v_5، وV(φ)V(\varphi) هي مجموعة متغيرات φ\varphi. ويقال إن vv يحقق φ\varphi، ويُكتب v⊨φv \models \varphi، عندما v(φ)=1v(\varphi) = 1، وإنه يدحضها، v⊭φv \not\models \varphi، عندما v(φ)=0v(\varphi) = 0. وتكون الصيغة صحيحة منطقيًا (أو تحصيل حاصل)، ويُكتب ⊨φ\models \varphi، إذا حققها كل إسناد؛ وقابلة للتحقق إذا حققها إسناد ما؛ وغير قابلة للتحقق (أو تناقضًا) إذا لم يحققها أي إسناد؛ وعرضية إذا كانت قابلة للتحقق دون أن تكون صحيحة منطقيًا. ويحقق إسنادٌ مجموعةً Γ\Gamma من الصيغ، v⊨Γv \models \Gamma، عندما يحقق كل واحدة منها، وتكون Γ\Gamma قابلة للتحقق إذا حققها إسناد ما، وغير قابلة للتحقق في الحالة المعاكسة. وأخيرًا، ⊤:=(v1→v1)\top := (v_1 \rightarrow v_1) و⊥:=¬⊤\bot := \neg\top، بحيث يكون v(⊤)=1v(\top) = 1 وv(⊥)=0v(\bot) = 0 لكل إسناد.

ويُستعمل من ذلك الدرس فوق ذلك نتيجتان. الأولى توطئة التطابق: إذا تطابق إسنادان على متغيرات φ\varphi تطابقا على φ\varphi؛ وبها لا تتوقف قيمة صيغة ذات nn متغيرات إلا على 2n2^{n} توافيق، ويكون جدول صدقها منتهيًا. والثانية مبرهنة قيم الروابط المشتقة، التي تحسب انطلاقًا من الاختصارات المعتمدة قيمة كل رابط بوصفها كثيرة حدود في قيم المكوّنات. إذا كان a=v(φ)a = v(\varphi) وb=v(ψ)b = v(\psi):

v(¬φ)=1−a,v((φ∨ψ))=a+b−ab,v((φ∧ψ))=abv(\neg\varphi) = 1 - a, \qquad v((\varphi \vee \psi)) = a + b - ab, \qquad v((\varphi \wedge \psi)) = ab
v((φ→ψ))=1−a(1−b),v((φ↔ψ))=ab+(1−a)(1−b),v((φ⊻ψ))=a+b−2abv((\varphi \rightarrow \psi)) = 1 - a(1 - b), \qquad v((\varphi \leftrightarrow \psi)) = ab + (1 - a)(1 - b), \qquad v((\varphi \veebar \psi)) = a + b - 2ab

تقوم براهين هذا الدرس، في معظمها، على مقارنة قيم الصدق، وتتيح كثيرات الحدود هذه إجراء ذلك بحساب بدلًا من استعراض الحالات. وقاعدتها الإضافية الوحيدة أن 00 و11 هما العددان الوحيدان اللذان يساويان مربعهما: إذا كانت قيمة xx هي 00 أو 11، فإن x2=xx^{2} = x وx(1−x)=0x(1 - x) = 0. ويحسن، فوق ذلك، أن تكون في المتناول ثلاث كتابات أخرى للقيم نفسها، تُحصل بفكّ الجداءات:

v((φ↓ψ))=(1−a)(1−b),v((φ∨ψ))=1−(1−a)(1−b),v((φ↔ψ))=1−a−b+2abv((\varphi \downarrow \psi)) = (1 - a)(1 - b), \qquad v((\varphi \vee \psi)) = 1 - (1 - a)(1 - b), \qquad v((\varphi \leftrightarrow \psi)) = 1 - a - b + 2ab

الأولى هي بند النفي المشترك (جداء 1−a1 - a و1−b1 - b يساوي 11 تمامًا عندما a=b=0a = b = 0)؛ والثانية تقول إن الفصل يساوي 00 فقط إذا ساوى المكوّنان كلاهما 00؛ والثالثة أن الاستلزام المزدوج يساوي 11 إذا a=ba = b (لأن 1−2a+2a2=11 - 2a + 2a^{2} = 1) ويساوي 00 إذا a≠ba \neq b (لأنه حينئذ a+b=1a + b = 1 وab=0ab = 0).