الاستقراء على تعقيد الصيغ
الملخص
في هذه الحصة، ستتعلم عن نوع من الاستقراء الرياضي يُعرف بـ”الاستقراء على تعقيد التعابير”، وهو مفيد جدًا لإثبات الخصائص في المنطق الاقتراحي. من خلال مثال بسيط، وهو مبرهنة الاستبدال، ستتعلم كيفية تطبيق هذه التقنية وكيف يمكن إثبات أن خاصية معينة تنطبق على جميع التعابير في المنطق الاقتراحي. بالإضافة إلى ذلك، سيتم شرح كيفية عمل فرضية الاستقراء والخطوة الاستقرائية لتتمكن من تطبيق هذه التقنية في براهينك الخاصة.
أهداف التعلم:
في نهاية هذه الحصة، سيكون الطالب قادرًا على:
- فهم مفهوم الاستقراء على تعقيد التعابير.
- تطبيق الاستقراء الرياضي على تعقيد الصيغ في المنطق الاقتراحي.
- فهم البرهان بالاستقراء على التعقيد وكيفية تطبيقه في المنطق الاقتراحي.
المحتويات
الاستقراء على التعقيد
مثال بسيط: مبرهنة الاستبدال
الاستقراء على التعقيد
لنفرض أننا نريد إثبات أن خاصية معينة \mathcal{P} تنطبق على أي تعبير F. إحدى الطرق لإثبات ذلك هي باستخدام نوع من الاستقراء الرياضي المعروف بـ”الاستقراء على تعقيد التعابير”. يتم ذلك من خلال الخطوات التالية:
- أولاً نُظهر أن جميع التعابير الذرية تفي بهذه الخاصية (يماثل هذا حالة n=1 في الاستقراء التقليدي).
- ثم، بافتراض أن الخاصية تنطبق على أي تعبيرين F و G، نثبت بالتالي أنها تنطبق على التعابير من الشكل F\downarrow G؛ أو بشكل مكافئ، على \neg F وأحد العناصر التالية: F\wedge G, F\vee G, F\rightarrow G.
إذا تمكنا من القيام بذلك، فإننا نستنتج أن الخاصية \mathcal{P} تنطبق على جميع التعابير في المنطق الاقتراحي. وهذا ما يُعرف بـ”الاستقراء الرياضي على تعقيد التعابير”.
مثال بسيط: مبرهنة الاستبدال
لفهم أفضل لكيفية إجراء الاستقراء على تعقيد الصيغ، سنستعرض مبرهنة الاستبدال.
لنفترض أن F\equiv G. دع H تعبير يحتوي على F كتعبير فرعي و H^\prime هو التعبير الناتج عن استبدال جميع تواجدات F بـ G، إذن H\equiv H^\prime.
برهان بالاستقراء على تعقيد الصيغ
إثبات الاستقراء على التعقيد يعني إثبات أمرين: 1) الحالة الأولية (بالنسبة للصيغ الذرية) و 2) الخطوة الاستقرائية (إذا كانت تنطبق على أي تعبيرين F و G، فإنها تنطبق أيضًا على F\downarrow G أو ببساطة على \neg F وأحد ما يلي: F\vee G, F\wedge G، F\rightarrow G أو F\leftrightarrow G).
لنفترض أن H تعبير ذري، و F هو تعبير فرعي لـ H و F\equiv G. إذا كان H^\prime هو الناتج عن استبدال جميع التعابير الفرعية F في H، بما أن H هو تعبير ذري، فإنه سيتحقق H^\prime \equiv G. من ناحية أخرى، بما أن H هو تعبير ذري و F هو تعبير فرعي لـ H، إذن H\equiv F. وأخيراً سنحصل على:
H\equiv F \equiv G \equiv H^\prime
وبذلك نكون قد أثبتنا الحالة الأولية للتعبيرات الذرية.
الآن دعنا ننتقل إلى الخطوة الاستقرائية.
فرضية الاستقراء
لنفترض أن المبرهنة تنطبق على أي تعبيرين H_1 و H_2، يحتوي كل منهما على F كتعبير فرعي و F \equiv G. إذن إذا كان H_1^\prime هو ما نحصل عليه باستبدال جميع F بـ G في H_1 و H_2^\prime هو ما نحصل عليه باستبدال جميع F بـ G في H_2، فسيكون لدينا H_1\equiv H_1^\prime و H_2\equiv H_2^\prime.
الخطوة الاستقرائية
هنا سنراجع ما إذا كانت، كنتيجة لفرضية الاستقراء، المبرهنة تنطبق أيضًا على \neg H_1 (أو \neg H_2, أي منهما) وأحد ما يلي: H_1 \wedge H_2, H_1 \vee H_2, H_1 \rightarrow H_2.
إذا كان H:= \neg H_1، فإن فرضية الاستقراء ستعطينا H\equiv \neg H_1^\prime=: H^\prime ، حيث H^\prime هو نتيجة استبدال جميع F في H بـ G. وبالتالي، H\equiv H^\prime.
وبالمثل، إذا كان H:= H_1 \wedge H_2، فإن فرضية الاستقراء ستعطينا H\equiv H_1^\prime \wedge H_2 \equiv H_1^\prime \wedge H_2^\prime =: H^\prime ، حيث H^\prime هو نتيجة استبدال جميع F في H بـ G. وبالتالي، H\equiv H^\prime.
وبالتالي يكون الاستقراء قد اكتمل وتتحقق مبرهنة الاستبدال لجميع التعابير في المنطق الاقتراحي.
عند تطبيق هذا النوع من الاستقراء، يمكننا ضمان بقاء خاصية معينة تنطبق على جميع التعابير في نظام منطقي، وهو ما يعد مفيدًا بشكل خاص في المنطق الاقتراحي لبناء براهين دقيقة. بالإضافة إلى ذلك، يمتد استخدامه إلى مجالات مثل الذكاء الاصطناعي وتطوير البرمجيات، حيث يكون التحقق من الأنظمة المنطقية أمرًا بالغ الأهمية. باستخدام هذه التقنية، يمكن أتمتة البراهين وضمان اتساق التعابير المعقدة، مما يقلل من مخاطر الأخطاء ويحسن الدقة في البيئات التي تعتمد على الصلاحية الرياضية والمنطقية.