ما هو التحقق الرسمي
التحقق الرسمي هو استخدام برهان رياضي لإثبات أن برنامجًا ما يلبي المتطلبات لجميع المدخلات، مع جعل الحاسوب يفحص كل خطوة من خطوات هذا البرهان. ولا يختلف عن الاختبار إلا في شيء واحد: الاختبار يفحص المدخلات التي جرّبتها، بينما الإثبات يغطيها كلها.
يبدأ هذا القسم ببناء درجات سُلَّم ليجعل هذه الجملة ملموسة. لا تحتاج إلى تثبيت أي شيء.
ماذا ستستطيع أن تفعل بعد هذه الدراسة
- أن تشرح ما يضمنه كل من الاختبار والإثبات
- أن تفهم ما تقوله نظرية Lean
- أن تعرف ماذا يعني "اجتاز Lean الفحص" وماذا لا يعني
لنبنِ درجات سُلَّم أولًا
نبني درجات السُلَّم من الطوب: الدرج الأولى 1 قطعة، والدرجة الثانية 2 قطعة، والدرجة الثالثة 3 قطعة. كم قطعة نحتاج لبناء n درجة إجمالًا؟
العد واحدًا واحدًا (اختبار)
1 + 2 + … + 4 = 10
n=4 ✓
هل جربت 1 قيمة n. حرّك شريط التمرير وجرّب قيمًا أخرى. لكن قيم n لا نهائية، ولن نتمكن من تجربتها كلها أبدًا.
اجمعها (إثبات)
خذ نسخة مطابقة من الدرجات، واعكسها.
لقد قمت بأمرين مختلفين:
- سحب المنزلق وعدّ الطوب: في كل مرة تعرف الإجابة لقيمة واحدة من n فقط. مهما جرّبت كثيرًا، يبقى الأمر "هذه القيم القليلة من n لا مشكلة فيها".
- تركيب مستطيل: رأيت جميع قيم n دفعة واحدة. مهما كان عدد الدرجات، تتكوّن النسختان معًا تمامًا في n صفًا و n + 1 عمودًا، لذا فإن مجموع قطع طوب النسختين هو n × (n + 1) قطعة.
الأول هو الاختبار، والثاني هو الإثبات.
- لقد سحبت المنزلق وركّبت المستطيل
كتابة الدرجات كبرنامج
أمر عدّ الطوب، مكتوبًا كدالة في Lean، يبدو هكذا. لا مشكلة إن لم تفهم التفاصيل؛ فهو يقول: "عدد قطع طوب درجات n = عدد قطع الدرجات n − 1 الأولى + عدد القطع n للدرجة رقم n":
def sumTo : Nat → Nat
| 0 => 0
| n + 1 => sumTo n + (n + 1)دالة واحدة، نوعان من الفحص
طريقة الاختبار: اختر عددًا واحسبه.
#eval sumTo 100ينبغي أن ترى:
5050100 × 101 ÷ 2 يساوي أيضًا 5050، الأمر متطابق. لكن هذا يثبت الصحة فقط عندما n = 100. وماذا عن n = 101؟ وماذا عن n = مئة مليون؟ يمكنك اختبار المزيد، لكنك لن تنتهي أبدًا.
طريقة الإثبات: اكتب النتيجة التي توصلت إليها عند تركيب المستطيل كجملة تصح لجميع قيم n، ثم أثبتها.
theorem sumTo_formula (n : Nat) : 2 * sumTo n = n * (n + 1) := by
induction n with
| zero =>
rfl
| succ k ih =>
simp [sumTo]
rw [Nat.mul_add, ih]
simp [Nat.mul_add, Nat.add_mul]
omegaلا مشكلة إن لم تفهم الآن الجزء الذي يلي by، فهذا محتوى الأقسام القادمة. انظر فقط إلى السطر الأول:
theorem sumTo_formula: نظرية، اسمهاsumTo_formula.(n : Nat): لأي عدد طبيعي n.2 * sumTo n = n * (n + 1): عدد قطع طوب النسختين يساوي n × (n + 1). وهو بالضبط المستطيل الذي ركّبته.
اجتاز Lean فحص هذا الإثبات. ومن الآن فصاعدًا تصح هذه الجملة لكل عدد طبيعي، دون حاجة إلى مزيد من الاختبار.
- أستطيع أن أشرح ما يضمنه كل من
#eval sumTo 100وtheorem sumTo_formula
ماذا يحدث إذا أخطأت
لنفترض أنك حفظت الصيغة خطأً وظننت أن جمع 1 حتى n يساوي n × n:
theorem wrong_formula (n : Nat) : sumTo n = n * n := by
induction n with
| zero => rfl
| succ k ih => simp [sumTo, ih]; omegaلن يقبل Lean. تبدأ إجابته بهذه الجملة:
omega could not prove the goal:لا يمكنك التسلل بالاعتماد على "يبدو متقاربًا تقريبًا". قضية خاطئة لا يمكن إثباتها مهما كتبت. وهذا هو سبب موثوقية التحقق الرسمي: الذي يفحص الإثبات هو برنامج، لا صبر إنسان.
اختبر معرفتككتبت 200 اختبار لدالة ترتيب، ونجحت جميعها. ماذا يعني هذا؟
ما لا يضمنه
ما يضمنه Lean هو: الجملة التي كتبتها قد أُثبتت. ولا يضمن أن الجملة التي كتبتها هي فعلًا ما أردته.
النظرية أعلاه تقول "ضعف sumTo n يساوي n × (n + 1)". إذا كنت تريد في الأصل خاصية أخرى لكنك كتبت هذه الجملة، فلن يستطيع Lean مساعدتك. لذلك فإن قراءة السطر الأول من النظرية أهم من قراءة الإثبات. الإثبات اتركه لـ Lean ليفحصه، أما القضية فعليك أنت قراءتها.
- أعرف أن "اجتياز الإثبات" يضمن صحة القضية، لا يضمن أن القضية كُتبت وفق المتطلبات
نقاط فحص
- أستطيع أن أشرح التحقق الرسمي في جملة واحدة: استخدام الإثبات لإثبات صحة البرنامج لجميع المدخلات، مع جعل الحاسوب يفحص الإثبات
- أستطيع أن أشرح الفرق بين الاختبار والإثبات: المدخلات المجرَّبة، جميع المدخلات
- أستطيع قراءة معنى كل جزء من
theorem 名字 (n : Nat) : 命题 - أعرف أن قضية خاطئة لا يمكن إثباتها في Lean
مفاهيم خاطئة شائعة
«التحقق الصوري هو مجرد مزيد من الاختبارات.» لا. الاختبار يعني تشغيل البرنامج وملاحظة النتائج، أما البرهان فيثبت دون تشغيل البرنامج؛ فهو يستنبط انطلاقًا من التعريفات، ويغطي جميع الحالات دفعة واحدة.
«إذا نجح البرهان، فلا توجد أي مشكلة في البرنامج.» البرهان يخص فقط العبارة التي كتبتها. أما الخصائص التي لم تُدرج في القضية فليست ضمن الضمان.
أسئلة شائعة
ماذا يعني التحقق الصوري؟
التحقق الصوري هو استخدام البراهين الرياضية لإثبات أن برنامجًا ما يلبي المتطلبات لجميع المدخلات، مع جعل الحاسوب يتحقق من كل خطوة في ذلك البرهان. ولا يوجد سوى فرق واحد بينه وبين الاختبار: الاختبار يتحقق من المدخلات التي جرّبتها، بينما البرهان يغطيها كلها. التعريف الوارد في بداية هذه الصفحة وقسم «لنبنِ درجات سُلَّم أولًا» يوضحان ذلك بمثال القوالب الطوبية.
ماذا يعني Lean 4؟
Lean 4 أداة تُستخدم لكتابة البرامج وكتابة البراهين. في هذه الصفحة استخدمتَها لتعريف الدالة sumTo، ثم استخدمتَ theorem لكتابة قضية تنطبق على جميع الأعداد الطبيعية، مع تحقق Lean من كل خطوة في البرهان. الذي يتحقق من البرهان هو برنامج، لا صبر إنسان.
كيف تُكتب عملية التحقق الصوري؟
اكتب أولًا الخاصية التي تريد إثباتها في صورة قضية تنطبق على جميع المدخلات، مثل theorem sumTo_formula (n : Nat) : 2 * sumTo n = n * (n + 1)، ثم قدّم برهانًا ليتحقق منه الحاسوب. البرهان الوارد في هذه الصفحة يستخدم الاستقراء الرياضي، وتفاصيله تُعرض في الأقسام اللاحقة.
إذا نجح البرهان، فهل يعني ذلك أن البرنامج خالٍ من أي مشكلات؟
لا. ما يضمنه Lean هو أن العبارة التي كتبتها قد بُرهنت، لا أن تلك العبارة هي فعلًا ما تريده. الخصائص التي لم تُدرج في القضية ليست ضمن الضمان، لذلك فهم السطر الأول من النظرية أهم من فهم البرهان، انظر قسم «ما لا يضمنه».
القسم التالي
إذا أردت أن تجعل Lean يتحقق من هذه الشيفرة بنفسك، فابدأ بتثبيت Lean 4.