الاستقراء على القوائم
بعد إتمام هذا القسم، ستثبت أن دالة العكس التي كتبتها بنفسك تحقق "العكس مرتين يساوي عدم العكس". والأهم من ذلك، ستختبر تعثرًا في الإثبات، وتتعلم أن ترى من موضع التعثر ما هو ناقص.
ماذا ستستطيع أن تفعل بعد التعلم
- كتابة إثبات بالاستقراء على القوائم: القائمة الفارغة، وحالة "إضافة عنصر في المقدمة"
- قراءة المبرهنة المساعدة المطلوبة من هدف لم يكتمل إثباته
- إثبات المبرهنة المساعدة أولًا، ثم استخدامها لإكمال إثبات المبرهنة الرئيسية
الخطوة 1: كتابة دالة عكس
def rev : List α → List α
| [] => []
| x :: xs => rev xs ++ [x][]هي القائمة الفارغة، وعكسها يبقى فارغًا.x :: xsتعني "العنصر الأول x، ويأتي بعده القائمة xs". لعكسها، نعكس ما يأتي بعده أولًا، ثم نلحق x في النهاية.++هي لصق قائمتين معًا.
جرّب ما يلي:
#eval rev [1, 2, 3][3, 2, 1]revالخاصة بي تستطيع عكس[1, 2, 3]
الخطوة 2: المحاولة المباشرة ثم التعثر
ما نريد إثباته هو: لأي قائمة، rev (rev xs) = xs.
الاستقراء على القوائم، مثله مثل الأعداد الطبيعية، يتكون من فرعين: nil هي القائمة الفارغة، وcons x xs ih هي "x يتبعها xs"، وih تقول إن القضية صحيحة لـ xs. اكتب وفق النمط نفسه في القسم السابق:
theorem rev_rev_try (xs : List α) : rev (rev xs) = xs := by
induction xs with
| nil => rfl
| cons x xs ih => simp [rev, ih]يجب أن ترى: يقول Lean إن هناك هدفًا لم يكتمل إثباته:
unsolved goals
case cons
α : Type u_1
x : α
xs : List α
ih : rev (rev xs) = xs
⊢ rev (rev xs ++ [x]) = x :: xsلا تتعجل في تغيير الاستراتيجية، بل اقرأ هذا الهدف. الجانب الأيسر هو rev (rev xs ++ [x])، أي عكس "قائمة ملصوقة". ih تقول إن rev (rev xs)، مع وجود ++ [x] إضافية في المنتصف، لذا لا يمكن استخدامها.
ما ينقص هو معرفة واحدة: ما نتيجة عكس عملية لصق؟
- رأيت
unsolved goals، وأستطيع الإشارة إلى موضع الاختلاف بين الهدف وih
الخطوة 3: إثبات مساعد أولًا
فكر في مثال ملموس: لصق [1, 2] مع [3, 4] ثم عكس النتيجة يعطي [4, 3, 2, 1]، أي "عكس النصف الثاني" يليه "عكس النصف الأول". اكتبها كمبرهنة، واستخدم الاستقراء مرة أخرى:
theorem rev_append (xs ys : List α) : rev (xs ++ ys) = rev ys ++ rev xs := by
induction xs with
| nil =>
simp [rev]
| cons x xs ih =>
simp [rev, ih]هذه المبرهنات الصغيرة التي تُثبت قبل المبرهنة الرئيسية من أجل إثباتها تسمى المبرهنات المساعدة (lemma).
rev_appendنجح
الخطوة 4: إكمال إثبات المبرهنة الرئيسية
سلّم المبرهنة المساعدة إلى simp:
theorem rev_rev (xs : List α) : rev (rev xs) = xs := by
induction xs with
| nil =>
rfl
| cons x xs ih =>
simp [rev, rev_append, ih]يجب أن ترى: لا توجد رسالة خطأ.
بوجود rev_append، أعيدت كتابة rev (rev xs ++ [x]) المتعثرة إلى rev [x] ++ rev (rev xs)، وعندها يمكن استخدام ih، بينما يكمل simp الباقي من تلقاء نفسه.
rev_revنجح
اختبر معرفتكتعطّل الإثبات، ويعرض Lean رسالة unsolved goals. ما الخطوة الأنسب الآن؟
نقطة تحقق
- أستطيع كتابة فرعي الاستقراء على القوائم:
nilوcons x xs ih - أستطيع تفسير سبب تعثر المحاولة الأولى
- أعرف ما هي المبرهنة المساعدة، وكيف تم التوصل إلى مبرهنة هذا القسم
rev_appendوrev_revكلاهما نجح
لم تنجح؟
**rev_rev يعرض خطأ يقول إنه لا يعرف rev_append. ** يجب كتابة المبرهنة المساعدة قبل المبرهنة التي تستخدمها. يقرأ Lean الملف من الأعلى إلى الأسفل.
**بعد simp لا يزال هناك هدف متبقٍ. ** قارن بالكود أعلاه، وتحقق مما إذا كنت قد أغفلت rev_append أو ih داخل الأقواس المربعة.
القسم التالي
أنت الآن تعرف كيف تتحقق من صحة دالة. القسم الأخير يستخدم الخطوات الثلاث نفسها — التعريف، والتعثر لإيجاد مبرهنة مساعدة، والاستقراء — لإثبات أن مصغّر مترجم (mini compiler) صحيح.