Skip to content

الاستقراء على القوائم ​

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

ماذا ستستطيع أن تفعل بعد التعلم ​

  • كتابة إثبات بالاستقراء على القوائم: القائمة الفارغة، وحالة "إضافة عنصر في المقدمة"
  • قراءة المبرهنة المساعدة المطلوبة من هدف لم يكتمل إثباته
  • إثبات المبرهنة المساعدة أولًا، ثم استخدامها لإكمال إثبات المبرهنة الرئيسية

الخطوة 1: كتابة دالة عكس ​

lean
def rev : List α → List α
  | [] => []
  | x :: xs => rev xs ++ [x]
  • [] هي القائمة الفارغة، وعكسها يبقى فارغًا.
  • x :: xs تعني "العنصر الأول x، ويأتي بعده القائمة xs". لعكسها، نعكس ما يأتي بعده أولًا، ثم نلحق x في النهاية. ++ هي لصق قائمتين معًا.

جرّب ما يلي:

lean
#eval rev [1, 2, 3]
text
[3, 2, 1]
  • rev الخاصة بي تستطيع عكس [1, 2, 3]

الخطوة 2: المحاولة المباشرة ثم التعثر ​

ما نريد إثباته هو: لأي قائمة، rev (rev xs) = xs.

الاستقراء على القوائم، مثله مثل الأعداد الطبيعية، يتكون من فرعين: nil هي القائمة الفارغة، وcons x xs ih هي "x يتبعها xs"، وih تقول إن القضية صحيحة لـ xs. اكتب وفق النمط نفسه في القسم السابق:

lean
theorem rev_rev_try (xs : List α) : rev (rev xs) = xs := by
  induction xs with
  | nil => rfl
  | cons x xs ih => simp [rev, ih]

يجب أن ترى: يقول Lean إن هناك هدفًا لم يكتمل إثباته:

text
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]، أي "عكس النصف الثاني" يليه "عكس النصف الأول". اكتبها كمبرهنة، واستخدم الاستقراء مرة أخرى:

lean
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:

lean
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) صحيح.

gaodong.aiAboutPrivacyContact

Independent tutorials, not affiliated with any product mentioned. Product names and trademarks belong to their owners. Check official pages for prices and policies.