قوانين دي مورغان وقوانين التوزيع

بنت الدروس السابقة من هذه الوحدة، الواحد فوق الآخر، أدوات الاستنتاج: نظام المسلّمات وقاعدة الوضع، والتقنيات الأساسية الأربع وإبدال النفي المزدوج، وتناظرات الروابط وتقنيات المنطق الكلاسيكي. ولا يضيف هذا الدرس أي قاعدة جديدة؛ بل يجعلها تعمل معًا. وإذا كان الأمر كذلك، فليست أهميته في المنطوقات، التي قد تكون معروفة من دورات أخرى، بقدر ما هي في طريقة الحصول عليها: كل سطر يجب أن يُبرَّر بمسلّمة، أو بمقدمة، أو بتعريف، أو بإحدى القاعدتين الأوليتين، أو بنتيجة سبق البرهان عليها، ولا يجوز لأي سطر أن يستند إلى ما «يبدو بديهيًا».

ما يُستعمل وكيف يترابط

من الدرس الخاص بـالأنظمة الاستنتاجية الصورية تؤخذ مسلّمات لوكاشيفيتش A1 وA2 وA3، وقاعدة الوضع (وضع)، مع المقدمات أيضًا، والانعكاسية (انعكاس: إذا كان $\varphi \in \Gamma$ فإن $\Gamma \vdash \varphi$)، والرتابة (رتابة)، والقطع (قطع: إذا كان $\Gamma \vdash \varphi_i$ لكل $i$ وكان $\Gamma \cup \{\varphi_1, \ldots, \varphi_n\} \vdash \psi$ فإن $\Gamma \vdash \psi$)، ومبرهنة الاستنتاج (استنتاج)، والتكافؤ الاستنتاجي ($\varphi \dashv\vdash \psi$ إذا كان $\{\varphi\} \vdash \psi$ و$\{\psi\} \vdash \varphi$)، مع خواصه: فهو انعكاسي ومتناظر ومتعدٍّ، وإذا كان $\varphi \dashv\vdash \psi$ فإن $\Gamma \vdash \varphi$ إذا وفقط إذا $\Gamma \vdash \psi$. ومن الدرس الخاص بـأربع تقنيات للاستنتاج يؤخذ النفي المزدوج (نفي مزدوج: $\varphi \dashv\vdash \neg\neg\varphi$)، وعكس النقيض (عكس النقيض)، ولا سيما $(\varphi \rightarrow \psi) \dashv\vdash (\neg\psi \rightarrow \neg\varphi)$، والقاعدة الأولية الثانية لنظام الدورة، إبدال النفي المزدوج (إبدال النفي المزدوج)، التي تبقى معها مبرهنة الاستنتاج صحيحة: إذا نتجت $\chi'$ من $\chi$ بإبدال ورود لصيغة جزئية $\theta$ بـ$\neg\neg\theta$، أو ورود لـ$\neg\neg\theta$ بـ$\theta$، فإنه من $\chi$ يُستدل على $\chi'$؛ والسطر المستخرج هكذا من السطر $i$ يُبرَّر بـإبدال النفي المزدوج$(i)$. ومن نتائجها المباشرة $(\varphi \downarrow \psi) \dashv\vdash (\neg\neg\varphi \downarrow \psi)$ و$(\varphi \downarrow \psi) \dashv\vdash (\varphi \downarrow \neg\neg\psi)$، وبوجه عام $\chi \dashv\vdash \chi'$ حين تنتج $\chi'$ من $\chi$ بإبدال النفي المزدوج؛ ومن ذلك يلزم أن إبدال النفي المزدوج$(i)$ ينطبق أيضًا على سطر من الشكل $\chi \dashv\vdash \varphi$، لتغيير نفي مزدوج في $\varphi$. ومن الدرس الخاص بـتناظرات الروابط يؤخذ إبدال المتكافئات (إبدال) والتناظرات (تناظر)، ومنها $(\varphi \vee \psi) \dashv\vdash (\psi \vee \varphi)$ و$(\varphi \wedge \psi) \dashv\vdash (\psi \wedge \varphi)$.

ومن الدرس الخاص بـتقنيات المنطق الكلاسيكي تؤخذ القواعد الآتية، كلها مع مجموعة $\Gamma$ من المقدمات. إدخال الفصل (إدخال $\vee$): إذا كان $\Gamma \vdash \varphi$ فإن $\Gamma \vdash (\varphi \vee \psi)$ و$\Gamma \vdash (\psi \vee \varphi)$. حذف الفصل (حذف $\vee$، القياس الفصلي): إذا كان $\Gamma \vdash (\varphi \vee \psi)$ و$\Gamma \vdash \neg\varphi$ فإن $\Gamma \vdash \psi$. إدخال العطف (إدخال $\wedge$): إذا كان $\Gamma \vdash \varphi$ و$\Gamma \vdash \psi$ فإن $\Gamma \vdash (\varphi \wedge \psi)$. حذف العطف (حذف $\wedge$): إذا كان $\Gamma \vdash (\varphi \wedge \psi)$ فإن $\Gamma \vdash \varphi$ و$\Gamma \vdash \psi$. قانون الثالث المرفوع (ثالث مرفوع): $\vdash (\varphi \vee \neg\varphi)$. والبرهان بالحالات (حالات) بصورتيه: إذا كان $\Gamma \cup \{\varphi\} \vdash \chi$ و$\Gamma \cup \{\neg\varphi\} \vdash \chi$ فإن $\Gamma \vdash \chi$؛ وإذا كان $\Gamma \cup \{\varphi\} \vdash \chi$ و$\Gamma \cup \{\psi\} \vdash \chi$ و$\Gamma \vdash (\varphi \vee \psi)$ فإن $\Gamma \vdash \chi$. وفي الاستنتاجات يُستشهد بالصورة الأولى بسطرين، حالات$(i, j)$، وبالثانية بثلاثة، حالات$(i, j, k)$، بترتيب المنطوق: الحالتان، ثم الفصل في الآخر. ويذكّر ذلك الدرس أيضًا بأن كل قاعدة سبق البرهان عليها تصح داخل سياق $\Gamma$، وعلى هذا النحو يُستعمل هنا النفي المزدوج وعكس النقيض.

أسماء السلسلة والصيغ المتكافئة

لنتذكر، من الدرس الخاص بـلغة منطق القضايا، أن الروابط غير $\downarrow$ اختصارات لها تعريف معتمد ووحيد: $\neg\varphi := (\varphi \downarrow \varphi)$، و$(\varphi \vee \psi) := \neg(\varphi \downarrow \psi)$، و$(\varphi \wedge \psi) := \neg(\neg\varphi \vee \neg\psi)$، و$(\varphi \rightarrow \psi) := (\neg\varphi \vee \psi)$، و$(\varphi \leftrightarrow \psi) := ((\varphi \rightarrow \psi) \wedge (\psi \rightarrow \varphi))$، و$(\varphi \veebar \psi) := \neg(\varphi \leftrightarrow \psi)$. والتعريف لا يقرر شيئًا عن الصيغ: إنه يعطي اسمًا ثانيًا لسلسلة كانت موجودة من قبل. ومن ذلك يلزم أنه إذا دلّت عبارتان على السلسلة نفسها، أمكن وضع إحداهما مكان الأخرى في أي موضع، حتى داخل صيغة أكبر، لأن ما يُكتب هو المتتالية نفسها من الدوائر والأقراص. وهكذا فإن $\neg(\varphi \wedge \psi)$ و$\neg\neg(\neg\varphi \vee \neg\psi)$ هما السلسلة نفسها: الثانية تنتج من كتابة بسط العطف داخل الأولى. وفي الاستنتاجات يُبرَّر هذا التغيير في الاسم بـ«تعريف»، متبوعًا بالرابط الذي يُبسط أو يُطوى.

على أن التكافؤ الاستنتاجي ليس تطابقًا. فكون $\varphi \dashv\vdash \neg\neg\varphi$ معناه أن كلًّا منهما تُستنتج من الأخرى، لا أنهما السلسلة نفسها: $\neg\neg\varphi$ أطول بكثير من $\varphi$. ومن ثم فإن العلم بأن $\varphi \dashv\vdash \varphi'$ لا يجيز، من غير قيد، كتابة $\varphi'$ مكان $\varphi$ داخل صيغة أكبر. ولا يجيز كذلك «نفي الطرفين»: فكون $\varphi \dashv\vdash \varphi'$ يلزم عنه $\neg\varphi \dashv\vdash \neg\varphi'$ مبرهنةٌ، هي إبدال المتكافئات، يستعمل برهانها عكس النقيض، وليس عملية بديهية. وهناك حالة وحيدة يجيز فيها النظام الإبدال مباشرة، في أي موضع من صيغة: حالة إبدال $\theta$ بـ$\neg\neg\theta$، أو العكس، وهي قاعدة إبدال النفي المزدوج؛ وقد بيّن الدرس الخاص بالأنظمة الاستنتاجية، بالعلامة، أن هذه الحالة نفسها لا تُستنتج من المسلّمات وقاعدة الوضع، فكان لا بد من التسليم بها قاعدةً. وليس هذا الحرص تنطعًا؛ بل هو ما يميز البرهان من تلاعب بالرموز قد يؤدي، إذا طُبّق على روابط أخرى أو في أنظمة أخرى، إلى أباطيل.

نتيجتان تحددان بدقة ما هو مسموح به. الأولى هي القضية الخاصة بخواص التكافؤ الاستنتاجي من الدرس الخاص بـالأنظمة الاستنتاجية الصورية: إذا كان $\Gamma \vdash \varphi$ و$\varphi \dashv\vdash \varphi'$ فإن $\Gamma \vdash \varphi'$، بحيث يمكن تطبيق تكافؤ استنتاجي على الصيغة الكاملة لسطر ما؛ والتكافؤ الاستنتاجي انعكاسي ومتناظر ومتعدٍّ، بحيث تترابط التكافؤات (إذا كان $\chi \dashv\vdash \varphi$ و$\varphi \dashv\vdash \varphi'$ فإن $\chi \dashv\vdash \varphi'$)، وتكون العبارتان اللتان تدلّان على السلسلة نفسها، بالانعكاسية، متكافئتين استنتاجيًا. والثانية، التوطئة الآتية، تجمع، ليسهل الاستشهاد بها، تمديد إبدال المتكافئات إلى الفصل والعطف، الذي يبرهن عليه الدرس الخاص بالتناظرات للنفي والاستلزام والنفي المشترك ويمدّه إلى هذين الرابطين في إحدى مسائله المحلولة.

ومن الآن فصاعدًا يدل «إبدال» على إبدال المتكافئات في أي صورة من صوره، ومنها صور هذه التوطئة، ويمكن تطبيقه مرات متتالية، طبقةً بعد طبقة، للوصول إلى صيغة جزئية واقعة في أي عمق. وحين يُحصل على سطر من السطر $i$ بتطبيق تكافؤ سبق البرهان عليه، سواء على الصيغة كلها أو، بإبدال، على أحد أجزائها، يُبرَّر باسم ذلك التكافؤ ورقم السطر: نفي مزدوج$(i)$، «إبدال، دي مورغان$(i)$». أما تغيير الاسم، الذي لا يطبّق أي تكافؤ بل يعيد كتابة السلسلة نفسها، فيُبرَّر بالطريقة نفسها، بـ«تعريف» متبوعًا بالرابط الذي يُبسط أو يُطوى: تعريف $\wedge$ $(i)$. والقضية الواردة في الدرس الخاص بالأنظمة الاستنتاجية الصورية تضمن أن هذه الأسطر مبرَّرة، سواء أكان السطر $i$ يقرر $\Gamma \vdash \varphi$ أم يقرر تكافؤًا $\chi \dashv\vdash \varphi$ يمتد خطوةً بعد خطوة.