أهداف التعلم:
بنهاية هذه الحصة، سيكون الطالب قادرًا على:

1. التعرف على نوعين من الاختبارات التي يجب تمييزها: الاختبارات الداخلية أو الاستنتاجية والاختبارات الخارجية أو الميتا-رياضية.
2. تطبيق الاستقراء الرياضي لإجراء إثباتات حول الأعداد الطبيعية وفي المنطق الاقتراحي.
3. استخدام رموز الجمع والطرح لكتابة تعبيرات المنطق الاقتراحي.
4. فهم الشكل العام لقوانين دي مورغان وقوانين التوزيع في المنطق الاقتراحي.
5. فهم مفهوم فرضية الاستقراء ودورها في الإثبات بالاستقراء.

الفهرس
الاختبارات الداخلية والخارجية
اختبارات بالاستقراء الرياضي
اختبارات بالاستقراء في المنطق الاقتراحي
الشكل العام لقوانين دي مورغان
الشكل العام لقوانين التوزيع

الاختبارات الداخلية والخارجية

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

اختبارات بالاستقراء الرياضي

الاستقراء الرياضي هو طريقة إثبات تسمح لنا بإثبات أن بعض الأمور تصح لجميع الأعداد الطبيعية.

مثال:
يمكن إثبات أن أي عدد من الشكل 11^n - 4^n، حيث n هو أي عدد طبيعي، دائمًا ما يكون قابلًا للقسمة على 7.
إثبات: إذا لاحظنا ما يحدث مع n=1، سنرى أن:

11^1 - 4^1 = 7

ومن الواضح أن هذا العدد يقبل القسمة على 7.

الآن، لنفترض أن 11^n - 4^n قابل للقسمة على عدد n=k. من هنا، سنثبت أن هذه الصيغة ستظل صحيحة أيضًا لـn=k+1. يمكننا القيام بذلك على النحو التالي:

11^{k+1} - 4^{k+1}=11 \cdot 11^{k} - 4 \cdot 4^{k}=11 \cdot 11^{k} - (11-7) \cdot 4^{k}=11 \cdot 11^{k} - 11 \cdot 4^{k} + 7\cdot 4^{k}=11 ( 11^{k} - 4^{k} ) + 7\cdot 4^{k}

وبالتالي، إذا كان 11^k - 4^k قابلاً للقسمة على 7، فبالتالي سيكون كذلك 11 ( 11^{k} - 4^{k} ) + 7\cdot 4^{k}، وهو ما يعادل القول بأن 11^{k+1} - 4^{k+1} قابلاً للقسمة على 7. من هنا، إذا كان 11^k - 4^k قابلاً للقسمة على k=1، فسيكون كذلك لـk=2, k=3, k=4,\cdots وهكذا، وبالتالي، قابلاً للقسمة على أي n\in\mathbb{N}. عندما يحدث هذا نقول إن الاستقراء مكتمل. ■

اختبارات بالاستقراء في المنطق الاقتراحي

للاختبارات بالاستقراء التي سنقوم بها لاحقًا، سيكون من الضروري أولاً إدخال الاتفاقية التالية للترميز

ترميز: لنفرض أن F_1,\cdots, F_n هو مجموعة محدودة من التعبيرات العشوائية في المنطق الاقتراحي. يتم إدخال الجمعيات والطرحيات لهذه التعبيرات من خلال:

\displaystyle \bigwedge_{i=1}^n F_i := F_1\wedge \cdots \wedge F_n

\displaystyle \bigvee_{i=1}^n F_i := F_1\vee \cdots \vee F_n

بهذا سنتمكن الآن من التعامل مع الشكلين العامين التاليين.

الشكل العام لقوانين دي مورغان

بالنسبة لمجموعة محدودة من التعبيرات في المنطق الاقتراحي F_1,\cdots, F_n, ستتحقق دائمًا الخاصيتان التاليتان:

\displaystyle\neg\left(\bigwedge_{i=1}^n F_i \right) \equiv \left( \bigvee_{i=1}^n \neg F_i \right)

\displaystyle\neg\left(\bigvee_{i=1}^n F_i \right) \equiv \left( \bigwedge_{i=1}^n \neg F_i \right)

إثبات: أولاً سنثبت بالاستقراء على n أن \neg\left(\bigwedge_{i=1}^n F_i \right) \equiv \left( \bigvee_{i=1}^n \neg F_i \right)

أولاً يجب أن نراجع ما يحدث في الحالة الأولية n=1. في هذه الحالة، من الواضح أن \neg F_1 \equiv \neg\left(\bigwedge_{i=1}^1F_i\right)\equiv \left(\bigvee_{i=1}^n \neg F_i \right) \equiv\neg F_1

لنفترض الآن أن الخاصية تعمل لـn=k; أي أنه بالنسبة لمجموعة محدودة من التعبيرات F_1, F_2, \cdots, F_k يتم الوفاء بها:

\displaystyle \neg\left(\bigwedge_{i=1}^k F_i\right) \equiv \left(\bigvee_{i=1}^k \neg F_i\right)

ثم سنثبت أن هذا ينطبق على

\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right) \equiv \left(\bigvee_{i=1}^{k+1} \neg F_i\right)

باستخدام تعريف الجمعية، نجد أن:

\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right) := \neg\left[\left(\bigwedge_{i=1}^{k} F_i\right) \wedge F_{k+1}\right]

على هذا التعبير، يمكننا تطبيق قوانين دي مورغان (العادية على مصطلحين) للحصول على:

\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right)\equiv \left[\neg\left(\bigwedge_{i=1}^{k} F_i\right) \vee \neg F_{k+1}\right]

الآن، إذا طبقنا فرضية الاستقراء، سنحصل على:

\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right)\equiv \left[ \left(\bigvee_{i=1}^k \neg F_i\right) \vee \neg F_{k+1}\right] := \left(\bigvee_{i=1}^{k+1}\neg F_i \right)

ولهذا السبب، يكون الاستقراء مكتملاً وتكون الخاصية صالحة لكل n بشكل عام. يمكن الحصول على العلاقة الثانية بطريقة مشابهة تمامًا، لذا سأتركها كتمرين للقارئ، هاها!

الشكل العام لقوانين التوزيع

على غرار قوانين دي مورغان، يمكن تعميم قوانين التوزيع على النحو التالي. لنفترض أن \{F_1, \cdots, F_n\} و\{G_1,\cdots, G_m\} هما مجموعتان محددتان من التعبيرات العشوائية، فإن المعادلات التالية صحيحة:

\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^m G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^m(F_i\vee G_j) \right) \right]

\displaystyle \left[ \left(\bigvee_{i=1}^n F_i \right) \wedge \left(\bigvee_{j=1}^m G_j \right) \right] \equiv \left[\bigvee_{i=1}^n\left(\bigvee_{j=1}^m(F_i\wedge G_j) \right) \right]

إثبات: لبناء هذا الإثبات، يجب علينا القيام باستقراء مزدوج على n وm. سأقوم أولاً بالاستقراء على n ثم على m للإثبات \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^m G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^m(F_i\vee G_j) \right) \right]

إذا أخذنا m=1, فإن هذا التعبير يمكن كتابته على النحو التالي

\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^1 G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^1(F_i\vee G_j) \right) \right].

وهو ما يعادل القول:

\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee G_1 \right] \equiv \left[\bigwedge_{i=1}^n\left( F_i\vee G_1 \right) \right].

سنثبت الآن هذا التعبير بالاستقراء على n.

إذا أخذنا n=1, فسيتم تقليل التعبير إلى

F_1 \vee G_1 \equiv F_1 \vee G_1.

هذا ما نعرفه بالفعل، وهو صحيح. الآن لنفترض أنه صحيح لـn=k أي أن فرضية الاستقراء ستكون:

\displaystyle \left[ \left(\bigwedge_{i=1}^k F_i \right) \vee G_1 \right] \equiv \left[\bigwedge_{i=1}^k\left( F_i\vee G_1 \right) \right].

ثم، من هذا سنثبت أنه صحيح أيضًا لـn=k+1.

بحسب تعريف الاقتران، لدينا:

\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 \right] := \left[\left(\left(\bigwedge_{i=1}^{k}F_i \right)\wedge F_{k+1} \right) \vee G_1 \right]

الآن، باستخدام توزيع \vee، نحصل على:

\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 \right] \equiv \left[\left(\left(\bigwedge_{i=1}^{k}F_i \right)\vee G_{1} \right) \wedge \left(F_{k+1} \vee G_1 \right) \right]

وعند هذه النقطة يمكننا استخدام فرضية الاستقراء للحصول على:

\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 \right] \equiv \left[\left(\bigwedge_{i=1}^k\left( F_i\vee G_1 \right) \right) \wedge \left(F_{k+1} \vee G_1 \right) \right] := \left[\bigwedge_{i=1}^{k+1}(F_{i}\vee G_1 \right]

لذلك، لقد أثبتنا بالاستقراء أنه لكل n\in\mathbb{N} يصح

\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right)\vee G_1\right] \equiv \left[\bigwedge_{i=1}^n(F_i\vee G_1)\right]

بعد إتمام الاستقراء على n تأكدنا من صحة الحالة الأولية لـm=1, الآن علينا فقط إتمام الاستقراء على m. للقيام بذلك، نضع فرضية الاستقراء لـm=l، أي أنه يصح

\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^l G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j) \right) \right]

وسنثبت من هذا أنه يصح أيضًا لـm=l+1.

كما هو الحال دائمًا، نبدأ من تعريف الاقتران، فنحصل على

\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] := \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\left(\bigwedge_{j=1}^{l} G_j \right) \wedge G_{l+1}\right) \right]

الآن، باستخدام توزيع \vee، نحصل على

\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \left( \left(\bigwedge_{i=1}^n F_i \right) \vee \left( \bigwedge_{j=1}^l G_j \right) \right) \wedge \left( \left( \bigwedge_{i=1}^n F_i \right)\vee G_{ل+1} \right) \right]

وبالتالي، باستخدام فرضية الاستقراء يمكننا كتابة

\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{ل+1} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j) \right) \wedge \left( \left( \bigwedge_{i=1}^n F_i \right)\vee G_{ل+1} \right) \right]

وإذا أخذنا الآن نتيجة الاستقراء على n

\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{ل+1} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^ل(F_i\vee G_j) \right) \wedge \left( \bigwedge_{i=1}^n (F_i \vee G_{ل+1} )\right) \right]

وبالتالي، من خلال تعريف الاقتران، لدينا

\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{ل+1} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^{ل+1}(F_i\vee G_j) \right) \right]

وبالتالي، فإن الاستقراء على m مكتمل، والتعبير

\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{m} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^{m}(F_i\vee G_j) \right) \right]

صحيح لجميع n,m\in\mathbb{N}.

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