حان الوقت لمراجعة خاصية أخرى تُستخدم بشكل متكرر في المنطق الاقتراحي، نحن نتحدث عن إثباتات قوانين دي مورجان للتوزيع بين الاقتران والانفصال. استخدام هذه القوانين شائع في نظرية المجموعات وبالتالي يمتد عبر جميع الرياضيات: من نظرية الاحتمالات، الطوبولوجيا وحتى لها وجود في الإلكترونيات والبرمجة. كالمعتاد، سنقوم بتفصيل إثباتات هذه القوانين باستخدام تقنيات الاستنتاج التي حصلنا عليها حتى الآن.

قوانين دي مورغان

قوانين دي مورغان هي مجموعة من التكافؤات التي تُشكّل توزيع النفي مع الاقتران والانفصال. تُعبّر عنها رسميًا من خلال التكافؤات التالية:

\neg(\alpha \wedge \beta) \dashv \vdash (\neg\alpha \vee \neg \beta)

\neg(\alpha \vee \beta) \dashv \vdash (\neg\alpha \wedge \neg \beta)

يمكن الحصول على هذه التكافؤات المثبتة دون الحاجة إلى إثبات مثل الذي قمنا به حتى الآن، حيث يمكننا الاعتماد على التعريفات التي تربط الاقتران بالانفصال وبعض اللعب بتكافؤ النفي المزدوج والاستبدالات. من تعريف الاقتران يتبع أن:

(A \wedge B):= \neg(\neg A \vee \neg B)

بتطبيق نفي على كلا الجانبين من هذا التعبير لدينا:

\neg(A \wedge B):= \neg\neg(\neg A \vee \neg B)

ثم، بواسطة تكافؤ النفي المزدوج نحصل على:

\neg(A \wedge B)\dashv \vdash (\neg A \vee \neg B)

وأخيرًا، باستبدال A=\alpha و B=\beta، نحصل على التكافؤ الأول لدي مورغان:

\boxed{\neg(\alpha \wedge \beta) \dashv \vdash (\neg\alpha \vee \neg \beta)}

للحصول على الثاني يمكننا الاستمرار في اللعب بالتعبير الذي كان لدينا قبل الاستبدال بإضافة نفي مرة أخرى إلى كلا الجانبين، وبالتالي:

\neg\neg(A \wedge B)\dashv \vdash \neg(\neg A \vee \neg B)

ثم، بواسطة النفي المزدوج نحصل على:

\neg(\neg A \vee \neg B) \dashv \vdash (A \wedge B)

إذا استبدلنا في هذا التعبير الأخير A=\neg\alpha و B=\neg\beta، سوف نصل إلى:

\neg(\neg \neg\alpha \vee \neg \neg\beta) \dashv \vdash (\neg\alpha \wedge \neg\beta)

مما يؤدي بسبب تكافؤ النفي المزدوج إلى التكافؤ الثاني لدي مورغان:

\boxed{\neg( \alpha \vee \beta) \dashv \vdash (\neg\alpha \wedge \neg\beta)}

بالإضافة إلى ذلك، بشكل مشابه تمامًا يمكننا الحصول على بعض الأشكال الإضافية، وهي ليست سوى تنويعات مما استعرضناه للتو:

\neg(\neg\alpha \wedge \beta) \dashv \vdash (\alpha \vee \neg \beta)

\neg(\neg\alpha \vee \beta) \dashv \vdash (\alpha \wedge \neg \beta)

\neg(\alpha \wedge \neg\beta) \dashv \vdash (\neg\alpha \vee \beta)

\neg(\alpha \vee \neg\beta) \dashv \vdash (\neg\alpha \wedge \beta)

قواعد التوزيع بين الاقتران والانفصال

كما يشير اسمها، تتيح لنا هذه القواعد توزيع الاقتران والانفصال داخل التعبير. تُلخّص هذه القوانين في التكافؤات التالية:

كما اعتدنا في ما رأيناه حتى الآن، رغم أن هذا نتيجة معروفة إلا أن إثباتها ليس بالأمر البسيط. ولكي نكمل هذا الإثبات يجب التفكير في كلا الاتجاهين، ولكن في هذه المرة سأقدم الإثبات في اتجاه واحد فقط، ويبقى الإثبات في الاتجاه العكسي كتمرين للقارئ.

∧ – التوزيع

لإثبات أن \{(\alpha \wedge(\beta \vee\gamma))\}\vdash((\alpha \wedge \beta)\vee(\alpha \wedge \gamma)) لدينا التفكير التالي.

بهذا يتضح أن \{(\alpha \wedge(\beta \vee\gamma))\}\vdash((\alpha \wedge \beta)\vee(\alpha \wedge \gamma)). الآن حان دورك لتجربة ما تعلمته وتهتم بإثبات بنفسك أن \{((\alpha \wedge \beta)\vee(\alpha \wedge \gamma))\}\vdash (\alpha \wedge(\beta \vee\gamma)).

∨ – التوزيع

إثبات \{(\alpha \vee(\beta \wedge\gamma))\}\vdash((\alpha \vee \beta)\wedge(\alpha \vee \gamma)) يتم الحصول عليه من خلال الاستنتاج التالي:

هذا هو نصف الإثبات، الآن فقط يتبقى عمل العكس، ولكن ذلك يبقى كتمرين للقارئ :3

الاعتبارات النهائية

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

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

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