الدلالة: الخلاصة والتحديات

ملخص

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

أهداف التعلم

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

ما حقّقته الوحدة

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

قيمة الصيغة

عرّف الدرس الخاص بـدلالات منطق القضايا الإسنادَ بأنه دالة من المتغيرات إلى $\{0, 1\}$ ، وبرهن، بمبرهنة التعريف بالتراجع على الصيغ، على أنه يمتدّ امتدادًا وحيدًا إلى كل الصيغ ببند واحد: $v((\varphi \downarrow \psi)) = (1 - v(\varphi))(1 - v(\psi))$ . ومن الاختصارات المعتمدة حسب، من غير أن يسلّم بشيء آخر، قيمة كل رابط مشتق، مكتوبةً كثيرةَ حدود في قيم المكوّنات، ومعها جدول الاستلزام، الذي هو هنا مبرهنة. وبرهن بالاستقراء على التعقيد على توطئة التطابق، التي يلزم عنها أن جدول الصدق ذا $2^{n}$ سطرًا يحوي كل ما تقوله الإسنادات اللامتناهية عن صيغة ذات $n$ متغيرات؛ وعرّف التحقيق، والصحة المنطقية، وقابلية التحقق، والتناقض، والعرضية، ونبّه إلى أن $\not\models \varphi$ تقول إن $\varphi$ ليست صحيحة منطقيًا لا إنها تناقض، وثبّت $\top := (v_{1} \rightarrow v_{1})$ و $\bot := \neg\top$ ، وحصل على قابلية التقرير للصحة المنطقية ولقابلية التحقق بكلفة أُسّية، يخفّضها البحث الموجَّه عن إسناد داحض ولا يزيلها.

النتيجة الدلالية والتكافؤ

عرّف الدرس الخاص بـالنتيجة الدلالية والتكافؤ الدلالي النتيجةَ من مجموعة مقدمات، منتهية أو غير منتهية، وبرهن على أن لها الخواص البنيوية للاستنتاج (الانعكاسية، والرتابة، والقطع، والتعدي)، ببراهين تمرّ على الإسنادات بدلًا من أن تتعامل مع الأسطر. وقد ردّت مبرهنةُ الاستنتاج الدلالية، $\Gamma \cup \{\varphi\} \models \psi \Leftrightarrow \Gamma \models (\varphi \rightarrow \psi)$ ، إلى السطر الكاذب الوحيد في الاستلزام، وردّت النتيجةُ إلى عدم قابلية التحقق: $\Gamma \models \varphi \Leftrightarrow \Gamma \cup \{\neg\varphi\}$ غير قابلة للتحقق. وتبيّن أن التكافؤ الدلالي، المعرَّف بأنه تساوي القيم، يتطابق مع النتيجة المتبادلة ومع الصحة المنطقية للاستلزام المزدوج. وبُرهن على مبرهنتَي العمل الخاصتين به بالاستقراء على التعقيد: إبدال ورود واحد لصيغة جزئية بصيغة مكافئة لها، مع حالة الورود الكلي التي لا يجوز إغفالها، والتعويض المنتظم للمتغيرات بصيغ كيفية، الذي يحفظ الصحة المنطقية والتكافؤ والنتيجة. وبهما تُطبَّق قوانين الفهرس، المتحقَّق منها بوصفها متطابقات بين كثيرات حدود، في أي موضع من أي صيغة، وتُسلسَل.

القوانين لأي عدد من الحدود

عرّف الدرس الخاص بـقوانين دي مورغان وقوانين التوزيع المعمّمة بالتراجع، مع التجميع إلى اليسار، العطفَ والفصلَ لـ $n$ صيغة، وبرهن بالاستقراء على عدد الحدود على توطئة القيمة، التي تقول إن العطف صادق إذا وفقط إذا كانت حدوده كلها صادقة، والفصل إذا وفقط إذا كان أحدها صادقًا. وبها وبتوافق الروابط مع التكافؤ حصل على التجميعية المعمّمة، المبرهن عليها بتعاقب من التكافؤات لتصحّ أيضًا للتكافؤ الاستنتاجي، وعلى الاستقلال عن الترتيب وعن التكرار، وقوانين دي مورغان المعمّمة، والتوزيعية المعمّمة، التي بُني استقراؤها على دليلين بحيث تشمل فرضيةُ الاستقراء كلَّ أطوال القائمة الثانية؛ وحُصل على القانون الثنوي بقانون دي مورغان، من غير تكرار الاستقراء المزدوج.

دوال الصدق

سلك الدرس الخاص بـالتمام الوظيفي الطريق المعاكس، من الجدول إلى الصيغة. فعدّ دوال الصدق ذات $n$ وسيطًا (وهي $2^{2^{n}}$ )، وبيّن أن كل صيغة تمثّل واحدة منها بالضبط وأن صيغتين متكافئتان إذا وفقط إذا مثّلتا الدالة نفسها، وبرهن على مبرهنة التمام الوظيفي: عطف السطر صادق في سطره بالضبط، وفصل عطوف الأسطر التي تساوي فيها الدالة $1$ يمثّلها. ولمّا كانت هذه الصيغة سلسلةً من الدوائر والأقراص، فإن النفي المشترك وحده كافٍ؛ وبمعيار النفي المشترك تكفي أيضًا $\{\neg, \wedge\}$ و $\{\neg, \vee\}$ و $\{\neg, \rightarrow\}$ والنفي البديل؛ وبمبدأ الانغلاق تحفظ كل صيغ $\{\wedge, \vee, \rightarrow, \leftrightarrow\}$ القيمة $1$ ، فلا تكفي هذه المجموعة.

الأشكال الناظمية

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

الخوارزمية والدارات

حوّل الدرس الخاص بـخوارزمية الشكل الناظمي وتطبيقاتها برهانَ الوجود الثاني إلى إجراء يعمل على الكتابات: حذف الروابط غير $\neg$ و $\wedge$ و $\vee$ ، ونقل النفي حتى المتغيرات، والتوزيع. وبرهن على صحتها بالإبدال في الكتابات، الذي يكيّف مبرهنة الإبدال مع الاختصارات، وعلى توقفها بثلاثة مقاييس تتناقص في كل خطوة، آخرها يقرأ العطف ضربًا؛ وبرهن أيضًا على أن الشكل العطفي للصيغة $\bigvee_{i=1}^{n} (p_i \wedge q_i)$ له بالضرورة $2^{n}$ عبارة، فليس النموّ عيبًا في الخوارزمية. ثم حصل على الأشكال الناظمية لصندوق أسود من جدوله، وبسّطها بدمج الأسطر المتجاورة، وحوّلها إلى دارات مفاتيح يكون توصيلها قيمةَ صيغتها.

يجمع الرسم الآتي المقاطع الستة في سلسلة واحدة. كل عقدة في العمود تعريفٌ أو نتيجة، مرقّمة بحسب الترتيب المنطقي، وموصولة بقوس بالحلقات السابقة التي يستعملها برهانها؛ وحولها تطفو الدعامات، أي المبادئ والأدوات التي تعود إليها السلسلة مرة بعد مرة، وكلٌّ منها موصول بخط متّصل بالحلقات التي تستند إليها وبخط منقّط بالحلقة التي يُرسى فيها، إلا ما لا تبرهن عليه هذه السلسلة (القراءة الوحيدة مع التراجع، والاستقراء، والاختصارات المعتمدة، من الوحدة الأولى)، فيُرسم أطواقًا. والنقر على دعامة يُبرز كل الحلقات التي تستعملها، وكل حلقة تحيل إلى الدرس الذي يُبرهن عليها فيه. ولنلاحظ أن الاستقراء وقيم الروابط هما أكثر الدعامات ارتيادًا في الوحدة، وأن توطئة القيمة، وإن بُرهن عليها في الدرس الثالث، تسند كل ما تقوله الدروس الثلاثة الأخيرة تقريبًا عن العطوف والفصول.

دعامات السلسلة

Aالقراءة الوحيدة والتراجع. إذا كان $\sigI\varphi\psi = \sigI\varphi'\psi'$ ، والسلاسل الأربع كلها صيغ، فإن $\varphi = \varphi'$ و $\psi = \psi'$ ؛ ومن ثمّ فإن قاعدةً تحسب قيمة $\sigI\varphi\psi$ من $\varphi$ ومن $\psi$ ومن قيمتيهما تعرّف دالة وحيدة على الصيغ. بُرهن عليها في الوحدة الأولى. يُقبل دون برهان في هذه الوحدة.
Bالاستقراء. البسيط والقوي على الأعداد الطبيعية، وعلى تعقيد الصيغ، وحالتاه الوحيدتان المتغيرات والنفي المشترك $(\varphi \downarrow \psi)$ . بُرهن عليه في الوحدة الأولى. يُقبل دون برهان في هذه الوحدة.
Cالاختصارات المعتمدة. $\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)$ . ثُبّتت في الوحدة الأولى. يُقبل دون برهان في هذه الوحدة.
Dقيم الروابط. مع $a = v(\varphi)$ و $b = v(\psi)$ : $v(\neg\varphi) = 1 - a$ ، و $v((\varphi \vee \psi)) = a + b - ab$ ، و $v((\varphi \wedge \psi)) = ab$ ، و $v((\varphi \rightarrow \psi)) = 1 - a(1 - b)$ ، و $v((\varphi \leftrightarrow \psi)) = ab + (1 - a)(1 - b)$ ، و $v((\varphi \veebar \psi)) = a + b - 2ab$ ، حيث $a^{2} = a$ . تثبت في: 1. تمديد الإسناد.
Eتوطئة التطابق. إذا اتفق إسنادان على متغيرات $\varphi$ أعطيا $\varphi$ القيمة نفسها؛ ولذلك فإن الجدول ذا $2^{n}$ سطرًا يقول كل شيء. تثبت في: 2. توطئة التطابق والجداول.
Fالإبدال الدلالي. إذا كان $\theta \eqsem \theta'$ وكانت $\chi'$ تنتج من $\chi$ بإبدال ورود واحد لـ $\theta$ بـ $\theta'$ ، فإن $\chi \eqsem \chi'$ . تثبت في: 7. مبرهنة الإبدال الدلالي.
Gقوانين التكافؤ. النفي المزدوج، والجمود، والتبديلية، والتجميعية، والتوزيعية، ودي مورغان، والامتصاص، والمحايد، والهيمنة، والثالث المرفوع، وعدم التناقض، لصيغ كيفية. تثبت في: 9. قوانين التكافؤ.
Hتوطئة القيمة. $v\left( \bigwedge_{i=1}^{n} \varphi_i \right) = 1$ إذا وفقط إذا كان $v(\varphi_i) = 1$ لكل $i$ ؛ و $v\left( \bigvee_{i=1}^{n} \varphi_i \right) = 1$ إذا وفقط إذا كان $v(\varphi_i) = 1$ لبعض $i$ . تثبت في: 10. توطئة القيمة والتوافق.

المقطع 1 قيمة الصيغة
- أن تحسب قيمة صيغة ببند النفي المشترك، وأن تستخرج من الاختصارات قيمة كل رابط مشتق.
- أن تبرهن على توطئة التطابق، وأن تسوّغ بها كفاية الجدول ذي $2^{n}$ سطرًا.
- أن تصنّف الصيغ والمجموعات من غير أن تخلط بين $\not\models \varphi$ والتناقض، وأن تحسم الصحة المنطقية بالبحث عن إسناد داحض.
1. تمديد الإسناد. كل إسناد $v$ يمتدّ امتدادًا وحيدًا إلى كل الصيغ بالبند $v((\varphi \downarrow \psi)) = (1 - v(\varphi))(1 - v(\psi))$ ؛ وبفكّ الاختصارات تُحسب قيمة $\neg$ ، و $\vee$ ، و $\wedge$ ، و $\rightarrow$ ، و $\leftrightarrow$ ، و $\veebar$ .
  تستند إلى: A (القراءة الوحيدة والتراجع), C (الاختصارات المعتمدة). يُبرهن في: دلالات منطق القضايا.
2. توطئة التطابق والجداول. إذا اتفق $v$ و $v'$ على $V(\varphi)$ فإن $v(\varphi) = v'(\varphi)$ ، بالاستقراء على التعقيد؛ ومن ثمّ فإن قيم $\varphi$ في كل الإسنادات هي بالضبط قيمها في الأسطر الـ $2^{n}$ من جدولها.
  تستعمل: 1. تمديد الإسناد. تستند إلى: B (الاستقراء). يُبرهن في: دلالات منطق القضايا.
3. التصنيف والحسم. كل صيغة هي واحد بالضبط من ثلاثة: صحيحة منطقيًا، أو عرضية، أو تناقض؛ و $\varphi$ صحيحة منطقيًا إذا وفقط إذا كانت $\neg\varphi$ تناقضًا، وهي تناقض إذا وفقط إذا كان $\models \neg\varphi$ . و $\top$ والثالث المرفوع صحيحان منطقيًا، و $\bot$ تناقض، وتُحسم الصحة المنطقية وقابلية التحقق بالمرور على الأسطر.
  تستند إلى: D (قيم الروابط), E (توطئة التطابق). يُبرهن في: دلالات منطق القضايا.
المقطع 2 النتيجة الدلالية والتكافؤ
- أن تحسم النتيجة الدلالية من مجموعات منتهية أو غير منتهية، بتقديم نموذج مضاد أو بالبرهان على أنه لا يوجد.
- أن تطبّق مبرهنة الاستنتاج الدلالية وردَّ النتيجة إلى عدم قابلية التحقق.
- أن تميّز إبدال ورود واحد من التعويض المنتظم، وأن تبرهن على كليهما بالاستقراء على التعقيد.
- أن تُرسي تكافؤات بتعاقبات، مسمّيًا كل قانون تسمية صحيحة.
1. النتيجة وخواصها. $\Gamma \models \varphi$ إذا كان كل إسناد يحقق $\Gamma$ يحقق $\varphi$ ؛ و $\emptyset \models \varphi$ إذا وفقط إذا كان $\models \varphi$ ؛ وتصحّ الانعكاسية والرتابة والقطع والتعدي، والمجموعة غير القابلة للتحقق تلزم عنها كل صيغة.
  تستعمل: 3. التصنيف والحسم. يُبرهن في: النتيجة الدلالية والتكافؤ الدلالي.
2. الاستنتاج الدلالي وعدم قابلية التحقق. $\Gamma \cup \{\varphi\} \models \psi \Leftrightarrow \Gamma \models (\varphi \rightarrow \psi)$ بالسطر الكاذب الوحيد في الاستلزام؛ و $\{\varphi_1, \ldots, \varphi_n\} \models \psi \Leftrightarrow\; \models (\varphi_1 \rightarrow (\varphi_2 \rightarrow \cdots (\varphi_n \rightarrow \psi) \cdots))$ ؛ و $\Gamma \models \varphi$ إذا وفقط إذا كانت $\Gamma \cup \{\neg\varphi\}$ غير قابلة للتحقق.
  تستعمل: 4. النتيجة وخواصها. تستند إلى: D (قيم الروابط). يُبرهن في: النتيجة الدلالية والتكافؤ الدلالي.
3. التكافؤ الدلالي. $\varphi \eqsem \psi$ إذا وفقط إذا كان $\varphi \models \psi$ و $\psi \models \varphi$ ، وإذا وفقط إذا كان $\models (\varphi \leftrightarrow \psi)$ ؛ والتكافؤ انعكاسي وتناظري ومتعدٍّ، والصيغتان المتكافئتان قابلتان للتبادل مقدمتين ونتيجتين.
  تستعمل: 4. النتيجة وخواصها. تستند إلى: D (قيم الروابط). يُبرهن في: النتيجة الدلالية والتكافؤ الدلالي.
4. مبرهنة الإبدال الدلالي. إذا كان $\theta \eqsem \theta'$ فإن الإبدال في $\chi$ لورود واحد لـ $\theta$ بـ $\theta'$ ، بما في ذلك الورود الكلي، يعطي صيغة مكافئة لـ $\chi$ ؛ وكذلك الإبدال المتزامن في كل الورودات.
  تستعمل: 1. تمديد الإسناد, 6. التكافؤ الدلالي. تستند إلى: A (القراءة الوحيدة والتراجع), B (الاستقراء). يُبرهن في: النتيجة الدلالية والتكافؤ الدلالي.
5. التعويض المنتظم. إذا كان $w(v_n) = v(\sigma(v_n))$ فإن $v(\sigma(\chi)) = w(\chi)$ ؛ ومن ثمّ إذا كان $\models \chi$ كان $\models \sigma(\chi)$ أيضًا، والتعويض يحفظ التكافؤ والنتيجة، ولا يحفظ قابلية التحقق ولا العرضية.
  تستعمل: 1. تمديد الإسناد, 4. النتيجة وخواصها, 6. التكافؤ الدلالي. تستند إلى: A (القراءة الوحيدة والتراجع), B (الاستقراء). يُبرهن في: النتيجة الدلالية والتكافؤ الدلالي.
6. قوانين التكافؤ. يُتحقَّق من قوانين الفهرس بوصفها متطابقات بين كثيرات حدود مع $a^{2} = a$ ؛ وبالإبدال والتعدي تُطبَّق على الصيغ الجزئية وتُسلسَل.
  تستعمل: 3. التصنيف والحسم, 6. التكافؤ الدلالي. تستند إلى: D (قيم الروابط), F (الإبدال الدلالي). يُبرهن في: النتيجة الدلالية والتكافؤ الدلالي.
المقطع 3 القوانين لأي عدد من الحدود
- أن تفكّ العطوف والفصول ذات $n$ حدًّا إلى سلاسل مجمَّعة إلى اليسار، وأن تحسب قيمتها.
- أن تبرهن بالاستقراء على عدد الحدود على التجميعية المعمّمة، والاستقلال عن الترتيب، وقوانين دي مورغان المعمّمة.
- أن تبرهن على التوزيعية المعمّمة بالاستقراء على دليلين، وأن تعدّ الحدود التي تنتجها.
1. توطئة القيمة والتوافق. إذا كان $\alpha \eqsem \alpha'$ و $\beta \eqsem \beta'$ فإن $\neg\alpha \eqsem \neg\alpha'$ و $(\alpha \wedge \beta) \eqsem (\alpha' \wedge \beta')$ و $(\alpha \vee \beta) \eqsem (\alpha' \vee \beta')$ ؛ والعطف ذو $n$ حدًّا يساوي $1$ إذا وفقط إذا ساوت كل الحدود $1$ ، والفصل إذا وفقط إذا ساوى أحدها $1$ ، والحدود المتكافئة تعطي عطوفًا وفصولًا متكافئة.
  تستعمل: 6. التكافؤ الدلالي. تستند إلى: D (قيم الروابط), B (الاستقراء). يُبرهن في: قوانين دي مورغان وقوانين التوزيع المعمّمة.
2. التجميعية والترتيب. عطف عطفَي قائمتين يكافئ عطف ضمّهما، وكل تجميع يكافئ التجميع إلى اليسار؛ والقائمتان اللتان لهما الحدود نفسها تعطيان عطوفًا وفصولًا متكافئة، أيًّا كان الترتيب والتكرار.
  تستند إلى: H (توطئة القيمة), G (قوانين التكافؤ), B (الاستقراء). يُبرهن في: قوانين دي مورغان وقوانين التوزيع المعمّمة.
3. قوانين دي مورغان المعمّمة. $\neg \bigwedge_{i=1}^{n} \varphi_i \eqsem \bigvee_{i=1}^{n} \neg\varphi_i$ و $\neg \bigvee_{i=1}^{n} \varphi_i \eqsem \bigwedge_{i=1}^{n} \neg\varphi_i$ : يُطبَّق قانون الحدّين على الوصل الأخير، وفرضية الاستقراء على ما يبقى في الداخل.
  تستند إلى: H (توطئة القيمة), G (قوانين التكافؤ), B (الاستقراء). يُبرهن في: قوانين دي مورغان وقوانين التوزيع المعمّمة.
4. التوزيعية المعمّمة. $\left( \bigvee_{i=1}^{n} \varphi_i \right) \wedge \left( \bigvee_{j=1}^{m} \psi_j \right) \eqsem \bigvee_{i,j} (\varphi_i \wedge \psi_j)$ ، مع $nm$ حدًّا بالترتيب المعجمي؛ والقانون الثنوي، الذي يوزّع فصل عطفين، بقانون دي مورغان.
  تستعمل: 11. التجميعية والترتيب, 12. قوانين دي مورغان المعمّمة. تستند إلى: H (توطئة القيمة), G (قوانين التكافؤ), B (الاستقراء). يُبرهن في: قوانين دي مورغان وقوانين التوزيع المعمّمة.
المقطع 4 دوال الصدق
- أن تعدّ دوال الصدق، وأن تحسم التكافؤ بمقارنة الدالتين اللتين تمثّلهما صيغتان.
- أن تبني صيغة الجدول، وأن تكتب أي دالة بالنفي المشترك وحده.
- أن تبرهن على كفاية مجموعة روابط بمعيار النفي المشترك، أو على عدم كفايتها بخاصية تحفظها صيغها.
1. دوال الصدق. توجد $2^{2^{n}}$ دالة صدق ذات $n$ وسيطًا؛ والصيغة التي متغيراتها من بين $v_1, \ldots, v_n$ تمثّل واحدة منها بالضبط، $f_\varphi$ ، و $\varphi \eqsem \psi \Leftrightarrow f_\varphi = f_\psi$ .
  تستعمل: 6. التكافؤ الدلالي. تستند إلى: E (توطئة التطابق). يُبرهن في: التمام الوظيفي.
2. التمام الوظيفي. عطف السطر يساوي $1$ في سطره بالضبط؛ وفصل عطوف الأسطر التي تساوي فيها $f$ القيمة $1$ ، أو $(v_{1} \wedge \neg v_{1})$ إن لم يوجد أيٌّ منها، يمثّل $f$ ؛ وكل صيغة تكافئ صيغة جدولها.
  تستعمل: 14. دوال الصدق. تستند إلى: H (توطئة القيمة), D (قيم الروابط). يُبرهن في: التمام الوظيفي.
3. مجموعات كافية وغير كافية. النفي المشترك كافٍ لأن الاختصارات تُفكّ؛ وإذا عبّرت صيغ $K$ عن قيمة $(1 - a)(1 - b)$ فإن المجموعة $K$ كافية، مثل $\{\neg, \wedge\}$ و $\{\neg, \vee\}$ و $\{\neg, \rightarrow\}$ و $\{\uparrow\}$ ؛ وصيغ $\{\wedge, \vee, \rightarrow, \leftrightarrow\}$ تساوي $1$ حين تساوي كل المتغيرات $1$ ، فهذه المجموعة غير كافية.
  تستعمل: 15. التمام الوظيفي. تستند إلى: C (الاختصارات المعتمدة), B (الاستقراء), D (قيم الروابط). يُبرهن في: التمام الوظيفي.
المقطع 5 الأشكال الناظمية
- أن تتعرّف الحرفيات والعبارات والأشكال الناظمية، مميّزًا شكل السلسلة من قيمتها.
- أن تبني الأشكال القانونية من الجدول، وأن تبرهن على وحدانيتها.
- أن تبرهن بالاستقراء على وجود الأشكال الناظمية بفرضية استقراء تطلب كليهما.
- أن تحسم بنظرة واحدة الصحة المنطقية لشكل عطفي وقابلية التحقق لشكل فصلي.
1. الحرفيات والازدواجية. $\neg\ell \eqsem \ell^{*}$ ؛ والعطف الأولي قابل للتحقق إذا وفقط إذا لم يحوِ زوجًا متتامًّا، والعبارة صحيحة منطقيًا إذا وفقط إذا حوت زوجًا منها؛ ونفي الشكل الناظمي يكافئ ثنويّه، فيكون الشكل العطفي لـ $\varphi$ هو ثنويّ الشكل الفصلي لـ $\neg\varphi$ .
  تستعمل: 12. قوانين دي مورغان المعمّمة. تستند إلى: G (قوانين التكافؤ), F (الإبدال الدلالي), H (توطئة القيمة). يُبرهن في: الأشكال الناظمية.
2. الأشكال القانونية. إذا كانت $\varphi$ قابلة للتحقق فهي تكافئ شكلها القانوني الفصلي، وإذا لم تكن صحيحة منطقيًا فهي تكافئ شكلها القانوني العطفي؛ ومتى ثُبّتت المتغيرات $v_1, \ldots, v_n$ كان الشكلان القانونيان متكافئين إذا وفقط إذا كانا السلسلة نفسها، وكانت الصيغتان القابلتان للتحقق متكافئتين إذا وفقط إذا كان لهما الشكل القانوني الفصلي نفسه.
  تستعمل: 15. التمام الوظيفي, 17. الحرفيات والازدواجية. تستند إلى: H (توطئة القيمة), E (توطئة التطابق). يُبرهن في: الأشكال الناظمية.
3. الوجود بالاستقراء. $(\varphi \downarrow \psi) \eqsem (\neg\varphi \wedge \neg\psi)$ ؛ والأشكال الناظمية مغلقة بالنسبة إلى العطف والفصل، الشكل الفصلي للعطف والشكل العطفي للفصل بالتوزيعية المعمّمة؛ وبالاستقراء، مع فرضية استقراء على الشكلين، لكل صيغة شكل فصلي وشكل عطفي.
  تستعمل: 17. الحرفيات والازدواجية, 11. التجميعية والترتيب, 13. التوزيعية المعمّمة. تستند إلى: B (الاستقراء), F (الإبدال الدلالي). يُبرهن في: الأشكال الناظمية.
4. ما يُرى بنظرة واحدة. الشكل العطفي صحيح منطقيًا إذا وفقط إذا حوت كل عبارة منه زوجًا متتامًّا؛ والشكل الفصلي قابل للتحقق إذا وفقط إذا وُجد عطف أولي لا يحوي أيًّا منها.
  تستعمل: 17. الحرفيات والازدواجية. تستند إلى: H (توطئة القيمة). يُبرهن في: الأشكال الناظمية.
المقطع 6 الخوارزمية والدارات
- أن تطبّق خوارزمية إعادة الكتابة، وأن تختار الحذف المناسب للاستلزام المزدوج.
- أن تبرهن على صحتها وتوقفها، وأن تشرح لماذا قد ينمو الشكل العطفي نموًّا أُسّيًا.
- أن تحصل على الأشكال الناظمية لصندوق أسود وتبسّطها، وأن تبني منها دارات مفاتيح.
1. صحة الخوارزمية وتوقفها. إبدال كتابة جزئية بكتابة مكافئة يعطي كتابة مكافئة؛ وكل قاعدة تكافؤ، والكتابة غير القابلة للاختزال شكل ناظمي بتجميع ما؛ والمقاييس $M_1$ ، و $M_2$ ، مع $M_2(\neg\varphi) = 2^{M_2(\varphi)}$ ، و $M_3$ ، مع $M_3(\varphi \wedge \psi) = M_3(\varphi)\,M_3(\psi)$ ، تتناقص في كل خطوة.
  تستعمل: 19. الوجود بالاستقراء, 11. التجميعية والترتيب. تستند إلى: G (قوانين التكافؤ), D (قيم الروابط), B (الاستقراء). يُبرهن في: خوارزمية الشكل الناظمي وتطبيقاتها.
2. النموّ الأُسّي. $\bigvee_{i=1}^{n} (p_i \wedge q_i)$ تكافئ شكلًا عطفيًا ذا $2^{n}$ عبارة، وكل شكل عطفي مكافئ لها له على الأقل $2^{n}$ عبارة غير صحيحة منطقيًا.
  تستعمل: 19. الوجود بالاستقراء, 17. الحرفيات والازدواجية. تستند إلى: H (توطئة القيمة). يُبرهن في: خوارزمية الشكل الناظمي وتطبيقاتها.
3. الأسطر المتجاورة والدارات. $(\kappa \wedge \ell) \vee (\kappa \wedge \ell^{*}) \eqsem \kappa$ والتكافؤ الثنوي؛ ودارة التوالي والتوازي توصل في الحالة $v$ إذا وفقط إذا كان $v(\varphi_C) = 1$ ، وكل دالة صدق تحقّقها دارة ما.
  تستعمل: 15. التمام الوظيفي, 18. الأشكال القانونية, 17. الحرفيات والازدواجية, 11. التجميعية والترتيب. تستند إلى: G (قوانين التكافؤ), F (الإبدال الدلالي), D (قيم الروابط), B (الاستقراء). يُبرهن في: خوارزمية الشكل الناظمي وتطبيقاتها.

نحو ما وراء النظرية. تتوقف السلسلة حيث تملك الدلالة إجراءً لكل سؤال عن الصيغ. ويبقى أن نعرف هل يتطابق ما هو صادق في كل إسناد بالضبط مع ما يُستنتج في النظام: وستقارن الوحدة التالية بين المفهومين.