طريقة البرهان بالخلف وبالمضاد للنقيض

البرهان بالخلف

المبدأ: لإثبات $P$ ، نفترض $\neg P$ (نقيض $P$ ) ونُظهر أن ذلك يؤدي إلى تناقض.

مثال كلاسيكي: $2$ عدد غير نسبي

الفرضية الخلفية: لنفترض أن $2 \in Q$ . إذن $2 = \frac{p}{q}$ حيث $p, q$ عددان صحيحان، $q \neq = 0$ ، والكسر غير قابل للاختزال (أي $pgcd (p, q) = 1$ ).

بتربيع الطرفين: $2 = \frac{p ^{2}}{q ^{2}}$ ، أي $p^{2} = 2 q^{2}$ . إذن $p^{2}$ زوجي، وبالتالي $p$ زوجي. لنكتب $p = 2 k$ .

إذن $4 k^{2} = 2 q^{2}$ ، أي $q^{2} = 2 k^{2}$ . إذن $q^{2}$ زوجي، وبالتالي $q$ زوجي.

لكن إذن $p$ و $q$ كلاهما زوجيان، وبالتالي $pgcd (p, q) \geq 2$ . تناقض مع «كسر غير قابل للاختزال».

الاستنتاج: $2 \in / Q$ .

البرهان بالمضاد للنقيض

المبدأ: لإثبات « $P \Rightarrow Q$ »، نُثبت « $\neg Q \Rightarrow \neg P$ ». وهما متكافئان (منطق الرتبة الأولى).

مثال: إذا كان $n^{2}$ زوجيا، فإن $n$ زوجي

البرهان المباشر: صعب. بالمضاد للنقيض، نُثبت « $n$ فردي $\Rightarrow n^{2}$ فردي».

إذا كان $n$ فرديا، فإن $n = 2 k + 1$ . إذن $n^{2} = (2 k + 1)^{2} = 4 k^{2} + 4 k + 1 = 2 (2 k^{2} + 2 k) + 1$ وهو فردي.

بالمضاد للنقيض: إذا كان $n^{2}$ زوجيا، فإن $n$ زوجي. $■$

متى نستعمل كل طريقة؟

بالخلف: عندما تتعلق القضية بالاستحالة أو الوحدانية («لا يوجد...»، «وحيد»).
بالمضاد للنقيض: عندما يكون الاستدلال المباشر معقدا، لكن المضاد للنقيض بسيط.

أخطاء يجب تجنبها

نفي الخاصية بشكل خاطئ: نقيض « $\forall x, P (x)$ » هو « $\exists x, \neg P (x)$ »، وليس « $\forall x, \neg P (x)$ ».
الاستنتاج السريع: يجب أن تكتب صراحة «تناقض مع...»، وإلا قد يشك المصحح.
الخلط بين المضاد للنقيض والعكس: عكس « $P \Rightarrow Q$ » هو « $Q \Rightarrow P$ » (وليسا متكافئين).

المكممات الواجب إتقانها

نفي مفيد:

$\neg (\forall x, P (x)) \equiv \exists x, \neg P (x)$
$\neg (\exists x, P (x)) \equiv \forall x, \neg P (x)$
$\neg (P \Rightarrow Q) \equiv P \land \neg Q$

المزيد من التمارين: فصل المنطق للجذع المشترك.