Skip to content

إجراء الاستقراء على الأعداد الطبيعية ​

بعد إنهاء هذا القسم، ستكون قادرًا على إثبات عبارة «صحيحة لكل عدد طبيعي n». ذلك الـ sumTo_formula الذي لم تكن تفهمه في القسم الأول، ستقرؤه بنفسك في نهاية هذا القسم.

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

  • ذكر الجزأين اللذين يتكون منهما الإثبات بالاستقراء
  • قراءة فرضية الاستقراء ih ومعرفة ما هي وأين يمكن استخدامها
  • كتابة إثبات استقرائي كامل باستخدام induction n with

لماذا نحتاج إلى الاستقراء ​

إن decide في القسم السابق يستطيع فقط حساب أرقام محددة. أما «لكل n» فهناك عدد لا نهائي من الحالات، لا يمكن حسابها جميعًا.

طريقة الاستقراء هي إثبات أمرين فقط:

  1. يصح عندما يكون n يساوي 0.
  2. إذا كان صحيحًا لـ k، فإنه صحيح أيضًا لـ k + 1.

بوجود هذين الشرطين، يصح 0، ومن ثم يصح 1، ومن ثم يصح 2، وهكذا دواليك، حتى يأتي دور كل عدد طبيعي. الأمر أشبه بإسقاط صف من قطع الدومينو: تسقط القطعة الأولى، وكل قطعة قادرة على إسقاط القطعة التالية.

في Lean، يقابل هذان الأمران فرعين:

text
induction n with
| zero => إثبات الحالة التي يكون فيها n يساوي 0
| succ k ih => إثبات الحالة التي يكون فيها n يساوي k + 1، ويمكن استخدام ih

ih هو «إذا كان صحيحًا لـ k» الوارد في البند 2. إنه فرضية، ومضمونها هو استبدال n في العبارة بـ k.

تطبيق عملي: 0 + n = n ​

تبدو هذه العبارة وكأنها لا تحتاج إلى إثبات. لكن الجمع في Lean معرَّف بشكل متكرر على العدد الثاني، فـ n + 0 يمكنه حساب n مباشرة، أما 0 + n فلا. جرّب وسترى:

lean
example (n : Nat) : 0 + n = n := by
  rfl
text
is not definitionally equal to the right-hand side

لذلك نستخدم الاستقراء. قم بذلك بنفسك، وانتبه إلى شكل ih في الفرع الثاني:

البرهنة بنفسكإثبات الاستقراء الأول: 0 + n = nالحالة والأخطاء من Lean 4.35.0 توليد
theorem zero_add' (n : Nat) : 0 + n = n := by
  induction n with
  | zero =>
    rfl
  | succ k ih =>
    rw [Nat.add_succ]
  rw [ih]

نكتبه على شكل كود:

lean
theorem zero_add' (n : Nat) : 0 + n = n := by
  induction n with
  | zero =>
    rfl
  | succ k ih =>
    rw [Nat.add_succ]
    rw [ih]

يُستخدم فيه مبرهنة جاهزة، ابحث عما تقوله:

lean
#check @Nat.add_succ
text
Nat.add_succ : ∀ (n m : Nat), n + m.succ = (n + m).succ

m.succ هو m + 1. تقول هذه المبرهنة: إن n + (m + 1) يساوي (n + m) + 1. بعد إعادة الكتابة بها، يظهر في الهدف 0 + k، وهو بالضبط الطرف الأيسر من ih، فيمكن استخدام ih لإعادة الكتابة مرة أخرى.

هكذا هو نمط الإثبات بالاستقراء: إعادة تنظيم حالة k + 1 بحيث تظهر حالة k، ثم استخدام فرضية الاستقراء.

  • أكملت إثبات zero_add' في التمارين
  • أستطيع ذكر مضمون ih في هذا الإثبات: 0 + k = k

العودة إلى صيغة الجمع ​

الدالة والمبرهنة من القسم الأول:

lean
def sumTo : Nat → Nat
  | 0 => 0
  | n + 1 => sumTo n + (n + 1)

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

الآن يمكن قراءتهما:

  • induction n with: استقراء على n.
  • فرع zero: n يساوي 0، وكلا الطرفين يُحسب إلى 0، rfl.
  • فرع succ k ih: ih هو 2 * sumTo k = k * (k + 1).
    • simp [sumTo]: حسب التعريف، يُفك sumTo (k + 1) إلى sumTo k + (k + 1).
    • rw [Nat.mul_add, ih]: نضرب 2 داخل القوسين فيظهر 2 * sumTo k، فنستبدله بـ ih.
    • السطران الأخيران: ما تبقى هو حساب حسابي بحت، نفك الضرب ونتركه لـ omega.

النمط لم يتغير: نفك التعريف، ونُظهر حالة k، ونستخدم ih، ونترك الباقي للتكتيكات التلقائية.

  • أستطيع الإشارة إلى الخطوة التي استُخدمت فيها فرضية الاستقراء في sumTo_formula

اختبر معرفتكفي فرع succ k ih، ماذا تنص فرضية الاستقراء ih؟

نقطة تفتيش ​

  • أستطيع ذكر الجزأين اللذين يتكون منهما الإثبات بالاستقراء: حالة 0، ومن k إلى k + 1
  • أستطيع كتابة بنية induction n with | zero => … | succ k ih => …
  • أعرف أن ih فرضية وليست هدفًا
  • فهمت ما يفعله كل سطر في sumTo_formula

لم تنجح؟ ​

**succ لا تعرف ما الخطوة التالية في الفرع. ** انظر هل يظهر الطرف الأيسر من ih في الهدف. إن لم يظهر، فوسّع التعريف أو أعد الصياغة أولًا حتى يظهر.

** اسم الفرع مكتوب خطأً. ** الفرعان للأعداد الطبيعية يُسميان دائمًا zero و succ. أما k و ih فهما اسمان اخترتهما أنت.

القسم التالي ​

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

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.