الاستنتاج: مقدمة

قبل أن تبدأ الوحدة، قِس نقطة انطلاقك. إنه تقييم ذاتي قصير: لا يُمنح عليه درجة، وتُحفظ نتيجته في متصفحك فقط.

1. السؤال 1من وحدات سابقةالسلسلة $\sigI\sigI\sigO\sigI\sigO\sigO\sigI\sigO\sigI$ صيغة مركبة على الشكل $\sigI\varphi\psi$. فما مكوّنتاها $\varphi$ و$\psi$؟

   $\varphi = \sigI\sigO\sigI\sigO\sigO\sigI$ و$\psi = \sigO\sigI$.

   $\varphi = \sigI\sigO\sigI$ و$\psi = \sigO\sigO\sigI\sigO\sigI$.

   تقبل تحليلين، بحسب الموضع الذي تُقطع فيه السلسلة بعد القرص الأول.

   $\varphi$ هي كل السلسلة التي تلي القرص الأول، و$\psi$ هي السلسلة الفارغة.

2. السؤال 2من وحدات سابقةفي برهان بالاستقراء القوي على أن كل عدد طبيعي $n$ يحقق خاصية $P(n)$، ماذا يمكن افتراضه عند البرهان على $P(n)$؟

   أن $P(m)$ تتحقق لكل عدد طبيعي $m$ أصغر من $n$.

   أن $P(n - 1)$ تتحقق فقط.

   أن $P(m)$ تتحقق لكل عدد طبيعي $m$ أصغر من $n$ أو يساويه.

   لا شيء، إلى أن يُبرهن كلٌّ على حدة على $P(1)$ و$P(2)$.

3. السؤال 3من وحدات سابقةبالاختصارات المعتمدة في الدورة، أيّ صيغة تدلّ عليها $(\varphi \rightarrow \psi)$ إذا كُتبت بالنفي المشترك والنفي؟

   $\neg(\neg\varphi \downarrow \psi)$.

   $(\neg\varphi \downarrow \psi)$.

   $\neg(\varphi \downarrow \neg\psi)$.

   لا صيغة بعينها: الأمر يتوقّف على الطريقة التي يُقرَّر أن تُقرأ بها.

4. السؤال 4المخطط A1 هو $(\varphi \rightarrow (\psi \rightarrow \varphi))$. فهل الصيغة $(v_{1} \rightarrow (v_{2} \rightarrow v_{3}))$ حالة خاصة من A1؟

   لا: كان يجب أن يُعوَّض الورود الأول والورود الأخير لـ$\varphi$ بالصيغة نفسها، وهما هنا $v_{1}$ و$v_{3}$.

   نعم، مع $\varphi := v_{1}$ و$\psi := v_{2}$.

   نعم، لأن كل استلزام تاليه استلزام آخر حالة خاصة من A1.

   لا، لأن الحالات الخاصة من مخطط لا يمكن أن تحتوي على متغيرات.

5. السؤال 5في استنتاج يوجد من قبل السطران $\psi$ و$(\varphi \rightarrow \psi)$، حيث $\varphi$ و$\psi$ صيغتان مختلفتان. ما الصيغة التي تتيح قاعدة الوضع كتابتها إذا طُبّقت على هذين السطرين؟

   لا شيء: قاعدة الوضع تقتضي المقدَّم $\varphi$، والذي لدينا هو التالي.

   $\varphi$.

   $(\psi \rightarrow \varphi)$.

   $\neg\varphi$.

6. السؤال 6من المعلوم أن $\{\varphi\} \vdash \psi$، أي أن هناك استنتاجًا لـ$\psi$ مقدمته الوحيدة $\varphi$. فماذا تؤكّد مبرهنة الاستنتاج حينئذ؟

   أن $\vdash (\varphi \rightarrow \psi)$: الاستلزام مبرهنة.

   أن $\vdash \psi$: يمكن حذف المقدمة ببساطة.

   أن $\vdash (\psi \rightarrow \varphi)$.

   أن $\{\psi\} \vdash \varphi$.

7. السؤال 7ماذا يُستنتج، دون مقدمات أخرى، من المجموعة $\{(\varphi \rightarrow \psi), (\psi \rightarrow \chi)\}$؟

   $(\varphi \rightarrow \chi)$.

   $\chi$، بتطبيق قاعدة الوضع مرتين.

   $(\chi \rightarrow \varphi)$.

   $(\varphi \wedge \chi)$.

8. السؤال 8قاعدة إبدال النفي المزدوج تغيّر، في سطر، ورودًا واحدًا فقط لصيغة جزئية، وتعمل على سلسلة اللغة الأساسية. كم ورودًا للصيغة الجزئية $\neg v_{1}$ تحتوي السلسلة التي تدلّ عليها $(v_{1} \rightarrow v_{2})$؟

   ورودان.

   ورود واحد، هو الذي يقابل المقدَّم.

   لا ورود: الصيغة لا تحتوي على نفي.

   أربعة.

9. السؤال 9ما الصيغة التي تُحصَّل من $(\neg\varphi \rightarrow \psi)$ بعكس النقيض، دون إضافة نفي مزدوج؟

   $(\neg\psi \rightarrow \varphi)$.

   $(\psi \rightarrow \neg\varphi)$.

   $(\varphi \rightarrow \neg\psi)$.

   $(\neg\psi \rightarrow \neg\varphi)$.

10. السؤال 10هل تدلّ $(\varphi \vee \psi)$ و$(\neg\varphi \rightarrow \psi)$ على الصيغة نفسها؟

    لا: الأولى هي $\neg(\varphi \downarrow \psi)$ والثانية $\neg(\neg\neg\varphi \downarrow \psi)$؛ وهما صيغتان مختلفتان، متكافئتان استنتاجيًا.

    نعم، بتعريف الاستلزام.

    نعم، لأن كلتيهما تُقرأ «$\varphi$ أو $\psi$».

    لا، ولا تُستنتج إحداهما من الأخرى.

11. السؤال 11من المعلوم أن $\varphi \dashv\vdash \varphi'$، أي أن كلًّا منهما تُستنتج من الأخرى. فما الذي يسوّغ أن $\neg\varphi \dashv\vdash \neg\varphi'$ أيضًا؟

    مبرهنة، هي إبدال المتكافئات، يُبرهن عليها بمبرهنة الاستنتاج وعكس النقيض.

    لا تسويغ خاص: يكفي «نفي الطرفين» في التكافؤ.

    تعريف النفي، لأن $\neg\varphi$ هي $(\varphi \downarrow \varphi)$.

    لا شيء، لأن ذلك غير صحيح: قد يفصل النفي بين صيغ متكافئة.

12. السؤال 12من مجموعة المقدمات $\Gamma \cup \{\neg\varphi\}$ تُستنتج صيغة $\chi$ ونفيها $\neg\chi$. فماذا يمكن أن يُستخلص؟

    أن $\Gamma \vdash \varphi$.

    أن $\Gamma \vdash \neg\varphi$.

    أن أيّ صيغة تُستنتج من $\Gamma$.

    لا شيء: الاستنتاج الذي ينتهي إلى تناقض لا يبرهن على شيء.

13. السؤال 13ما الصيغة التي يكافئها نفي الاستلزام، $\neg(\varphi \rightarrow \psi)$؟

    $(\varphi \wedge \neg\psi)$.

    $(\neg\varphi \rightarrow \neg\psi)$.

    $(\varphi \rightarrow \neg\psi)$.

    $(\neg\varphi \wedge \psi)$.