مقالات

3.1: البراهين المباشرة - الرياضيات


نشاط المعاينة 1 (تعريف الأقسام والمقسومات والمتعددة)
درسنا في القسم 1.2 مفاهيم الأعداد الزوجية والأعداد الصحيحة الفردية. فيما يلي تعريف رسمي لما يعنيه القول بأن عددًا صحيحًا غير صفري (م ) يقسم عددًا صحيحًا (n ).

تعريف

عدد صحيح غير صفري (م ) يقسم عدد صحيح (n ) بشرط وجود عدد صحيح (q ) بحيث (n = m cdot q ). نقول أيضًا أن (m ) هو ملف المقسوم عليه من (n ) ، (م ) هو أ عامل من (n ) ، و (n ) هو ملف مضاعف من (م ). العدد الصحيح 0 ليس مقسومًا على أي عدد صحيح. إذا كان (a ) و (b ) عددًا صحيحًا و (a ne 0 ) ، فإننا كثيرًا ما نستخدم الترميز (a | b ) كاختصار لـ " (a ) divides (b) ). "

ملاحظة حول التدوين: كن حذرا مع التدوين (أ | ب ). هذا لا يمثل العدد المنطقي ( dfrac {a} {b} ). يمثل الترميز (a | b ) علاقة بين الأعداد الصحيحة (a ) و (b ) وهو ببساطة اختصار لـ " (a ) divides (b )."

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

يمكن كتابة تعريف "القسمة" في شكل رمزي باستخدام محددات كمية مناسبة على النحو التالي: عدد صحيح غير صفري (م ) يقسم عدد صحيح (n ) بشرط أن (( موجود q في mathbb {Z}) (n = m cdot q) ).

  1. استخدم تعريف القسمة لشرح سبب 4 يقسم 32 ولشرح سبب 8 قسمة -96.
  2. أعط عدة أمثلة لعددين صحيحين حيث لا يقسم العدد الصحيح الأول العدد الصحيح الثاني.
  3. وفقًا لتعريف "القسمة" ، هل العدد الصحيح 10 يقسم العدد الصحيح 0؟ أي 10 مقسوم على 0؟ يشرح.
  4. استخدم تعريف "القسمة" لإكمال الجملة التالية في شكل رمزي: "العدد الصحيح غير الصفري (m ) لا يقسم العدد الصحيح (n ) يعني أن ..."
  5. استخدم تعريف "القسمة" لإكمال الجملة التالية دون استخدام رموز المحددات الكمية: "العدد الصحيح غير الصفري (م ) لا يقسم العدد الصحيح (n ). .... "
  6. أعط ثلاثة أمثلة مختلفة لثلاثة أعداد صحيحة حيث يقسم العدد الصحيح الأول العدد الصحيح الثاني ويقسم العدد الثاني على العدد الصحيح الثالث.

    كما رأينا في القسم 1.2 ، كثيرًا ما يستخدم التعريف عند إنشاء وكتابة البراهين الرياضية. ضع في اعتبارك التخمين التالي:

    تخمين: دع (a ) و (b ) و (c ) تكون أعدادًا صحيحة مع (a ne 0 ) و (b ne 0 ). إذا قسم (أ ) (ب ) و (ب ) قسم (ج ) ، فإن (أ ) يقسم (ج ).

  7. اشرح لماذا تقدم الأمثلة التي أنشأتها في الجزء (6) دليلاً على صحة هذا التخمين.

    في القسم 1.2 ، تعلمنا أيضًا كيفية استخدام ملف تعرف على الجدول للمساعدة في تنظيم أفكارنا عند محاولة بناء دليل على بيان. إذا لزم الأمر ، راجع المادة المناسبة في القسم 1.2.

  8. اذكر بالضبط ما سنفترضه إذا كنا نحاول كتابة دليل على التخمين السابق.
  9. استخدم تعريف "التقسيمات" للوصول إلى بعض الاستنتاجات بناءً على افتراضاتك في الجزء (8).
  10. اذكر بالضبط ما سنحاول إثباته إذا كنا نحاول كتابة دليل على التخمين.
  11. استخدم تعريف القسمة لكتابة إجابة على السؤال ، "كيف يمكننا إثبات ما ذكرناه في الجزء (10)؟

معاينة النشاط 2 (التقاويم والساعات)
يهدف نشاط المعاينة هذا إلى المساعدة في فهم مفهوم التطابق ، والذي سيتم دراسته في نهاية هذا القسم.

  1. لنفترض أنه يوم الثلاثاء الآن. (أ) ما هو اليوم الذي سيكون بعد ثلاثة أيام من الآن؟
    (ب) في أي يوم ستكون بعد 10 أيام من الآن؟
    (ج) في أي يوم سيكون بعد 17 يومًا من الآن؟ في أي يوم سيكون بعد 24 يومًا من الآن؟
    (د) ابحث عن عدة أرقام طبيعية أخرى (س ) بحيث يكون يوم الجمعة (س ) يومًا من الآن.
    (هـ) إنشاء قائمة (بترتيب تصاعدي) بالأرقام 3 ؛ 10 ؛ 17 ؛ 24 ، والأرقام التي أنشأتها في الجزء (1 د). اختر أي رقمين من هذه القائمة واطرح أحدهما من الآخر. كرر هذا عدة مرات.
    (و) ما هو القاسم المشترك بين الأرقام التي حصلت عليها في الجزء (1 هـ)؟
  2. افترض أننا نستخدم ساعة من اثني عشر ساعة دون تمييز بين A.M. و P.M. افترض أيضا أن الوقت الحالي هو 5:00 (أ) كم سيكون الوقت بعد 4 ساعات من الآن؟
    (ب) كم الساعة ستكون 16 ساعة من الآن؟ كم ستكون الساعة بعد 28 ساعة من الآن؟
    (ج) ابحث عن عدة أرقام طبيعية أخرى (س ) بحيث تكون 9:00 (س ) ساعات من الآن.
    (د) إنشاء قائمة (بترتيب تصاعدي) بالأرقام 4 ؛ 16 ؛ 28 ، والأرقام التي أنشأتها في الجزء (2 ج). كرر هذا عدة مرات.
    (هـ) ما هو القاسم المشترك بين الأرقام التي حصلت عليها في الجزء (2 د)؟
  3. هذا استمرار للجزء (1). افترض أنه يوم الثلاثاء حاليًا.

    (أ) في أي يوم كان قبل 4 أيام؟
    (ب) في أي يوم كان قبل 11 يومًا؟ في أي يوم كان قبل 18 يومًا؟
    (ج) ابحث عن عدة أرقام طبيعية أخرى (س ) بحيث كان يوم الجمعة (س ) قبل أيام.
    (د) إنشاء قائمة (بترتيب تصاعدي) تتكون من الأرقام 18 ؛ 11 ؛ 4 ، الأضداد من الأرقام التي أنشأتها في الجزء (3 ج) والأرقام الموجبة في القائمة من الجزء (1 هـ). اختر أي عددين من هذه القائمة واطرح أحدهما من الآخر. كرر هذا عدة مرات.
    (هـ) ما هو القاسم المشترك بين الأرقام التي حصلت عليها في الجزء (3)؟

بعض المصطلحات الرياضية

في القسم 1.2 ، قدمنا ​​فكرة الدليل المباشر. منذ ذلك الحين ، استخدمنا بعض المصطلحات الشائعة في الرياضيات دون الكثير من الشرح. قبل المضي قدمًا ، سنناقش بعض المصطلحات الرياضية المستخدمة بشكل متكرر.

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

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

بالنظر إلى أي نقطتين مميزتين ، يوجد خط واحد يحتوي على هاتين النقطتين.

يتم استخدام خصائص إغلاق أنظمة الأرقام التي تمت مناقشتها في القسم 1.1 وخصائص أنظمة الأرقام في الجدول 1.2 في الصفحة 18 كبديهيات في هذا النص.

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

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

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

بناء البراهين الرياضية

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

في القسم 1.2 ، قدمنا ​​استخدام أ تعرف على الجدول لمساعدتنا في تنظيم عملنا عندما نحاول إثبات بيان. قدمنا ​​أيضًا بعض الإرشادات لكتابة البراهين الرياضية بمجرد إنشاء البرهان. يجب مراجعة هذه الإرشادات قبل المتابعة.

يرجى تذكر أنه عندما نبدأ عملية كتابة الدليل ، فإننا في الأساس "ننقل الأخبار". أي أننا اكتشفنا الدليل بالفعل ، والآن نحتاج إلى الإبلاغ عنه. غالبًا لا تصف هذه التقارير عملية اكتشاف الأخبار (الجزء الاستقصائي من العملية).

في كثير من الأحيان ، تكون الخطوة الأولى هي تطوير التخمين. غالبًا ما يتم ذلك بعد العمل داخل كائنات معينة لبعض الوقت. هذا ما فعلناه في معاينة النشاط ( PageIndex {1} ) عندما استخدمنا أمثلة لتقديم دليل على صحة التخمين التالي:

تخمين: دع (a ) و (b ) و (c ) تكون أعدادًا صحيحة مع (a ne 0 ) و (b ne 0 ). إذا قسم (أ ) (ب ) و (ب ) قسم (ج ) ، ثم (أ ) قسم (ج ).

قبل أن نحاول إثبات تخمين ، يجب أن نتأكد من أننا اكتشفنا بعض الأمثلة. هذا يعني ببساطة بناء بعض الأمثلة المحددة حيث تفي الأعداد الصحيحة أ ، ب ، ج بفرضية التخمين لمعرفة ما إذا كانت ترضي أيضًا الاستنتاج. لقد فعلنا هذا مع هذا التخمين في معاينة النشاط ( PageIndex {1} ).

سنبدأ الآن جدول المعرفة لهذا التخمين.

خطوةيعرفسبب
(ف ) (a ) ، (b ) ، (c in mathbb {Z} ) ، (a ne 0 ) ، (b ne 0 ) ، (a | b ) و (ب | ج )فرضية
(ف ) 1
.........
(س ) 1
(س ) (أ | ج )
خطوةتبينسبب

السؤال الخلفي الذي نطرحه هو ، "كيف يمكننا إثبات أن (أ ) يقسم (ج )؟" تتمثل إحدى الإجابات في استخدام التعريف وإظهار وجود عدد صحيح (q ) بحيث (c = a cdot q ). قد تكون هذه الخطوة (س ) 1 في جدول المعرفة.

علينا الآن إثبات وجود عدد صحيح (q ) ، لذلك نسأل السؤال ، "كيف نثبت وجود هذا العدد الصحيح؟" عندما نكون في مثل هذه المرحلة من العملية العكسية للإثبات ، فإننا عادة ما ننتقل إلى ما هو معروف لإثبات وجود الكائن أو للعثور على الكائن الذي نحاول إثبات وجوده أو بنائه. غالبًا ما نقول إننا نحاول "بناء" الكائن أو على الأقل إثبات وجوده من المعلومات المعروفة. لذلك في هذه المرحلة ، ننتقل إلى الجزء الأمامي من الدليل لمحاولة إثبات وجود عدد صحيح (q ) مثل (c = a cdot q ).

السؤال الأمامي الذي نطرحه هو ، "ما الذي يمكننا استنتاجه من الحقائق (أ | ب ) و (ب | ج )؟" مرة أخرى ، باستخدام التعريف ، نعلم أن هناك أعدادًا صحيحة (s ) و (t ) مثل (b = a cdot s ) و (c = b cdot t ). قد تكون هذه الخطوة (P ) 1 في جدول المعرفة.

المفتاح الآن هو تحديد كيفية الانتقال من (P ) 1 إلى (Q ) 1. بمعنى ، هل يمكننا استخدام الاستنتاجات بأن الأعداد الصحيحة (s ) و (t ) موجودة لإثبات وجود العدد الصحيح (q ) (من العملية السابقة). باستخدام المعادلة (b = a cdot s ) ، يمكننا استبدال (a cdot s ) بـ (b ) في المعادلة الثانية ، (c = b cdot t ). هذا يعطي

(ج = ب cdot t )
(= (a cdot s) cdot t )
(= a (s cdot t) ).

استخدمت الخطوة الأخيرة الخاصية الترابطية للضرب. (انظر الجدول 1.2 في الصفحة 18.) يوضح هذا أن (c ) يساوي (a ) مرات بعض الأعداد الصحيحة. (هذا لأن (s cdot t ) هو عدد صحيح من خلال خاصية الإغلاق للأعداد الصحيحة.) لذلك على الرغم من أننا لم نستخدم الحرف (q ) ، فقد وصلنا إلى الخطوة (Q ) 1. يتبع جدول المعرفة المكتمل.

خطوةيعرفسبب
(ف ) (a ) ، (b ) ، (c in mathbb {Z} ) ، (a ne 0 ) ، (b ne 0 ) ، (a | b ) و (ب | ج )فرضية
(ف ) 1

(( موجود s في mathbb {Z}) (ب = أ cdot s) )
(( موجود t في mathbb {Z}) (ج = ب cdot t) )

تعريف "الانقسامات"
(ف ) 2 (c = (a cdot s) cdot t )استبدال (ب )
(ف ) 3 (c = a cdot (s cdot t ))الخاصية الترابطية للضرب
(س ) 1 (( موجود q في mathbb {Z}) (ج = أ cdot q) )الخطوة (ف ) 3 وخصائص إغلاق الأعداد الصحيحة
(س ) (أ | ج )تعريف "الانقسامات"

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

يمكننا الآن الإبلاغ عن الأخبار من خلال كتابة إثبات رسمي.

نظرية 3.1

دع (a ) و (b ) و (c ) تكون أعدادًا صحيحة مع (a ne 0 ) و (b ne 0 ). إذا قسم (أ ) (ب ) و (ب ) قسم (ج ) ، ثم (أ ) قسم (ج ).

دليل

نفترض أن (a ) و (b ) و (c ) هي أعداد صحيحة مع (a ne 0 ) و (b ne 0 ). نفترض أيضًا أن (أ ) يقسم (ب ) وأن (ب ) يقسم (ج ). سنثبت أن (أ ) يقسم (ج ).

نظرًا لأن (أ ) يقسم (ب ) و (ب ) يقسم (ج ) ، فهناك أعداد صحيحة (ق ) و (تي ) بحيث

[b = a cdot s و ]

[c = b cdot t ]

يمكننا الآن استبدال تعبير (b ) من المعادلة (1) في المعادلة (2). هذا يعطي

(c = (a cdot s) cdot t ).

باستخدام خاصية المرافقة في الضرب ، يمكننا إعادة ترتيب الجانب الأيمن من المعادلة الأخيرة للحصول عليها

(c = a cdot (s cdot t) ).

نظرًا لأن كلا من s و t عدد صحيح ، وبما أن الأعداد الصحيحة مغلقة أثناء الضرب ، فإننا نعلم أن (s cdot t in mathbb {Z} ). لذلك ، تثبت المعادلة السابقة أن (أ ) يقسم (ج ). وبالتالي ، فقد أثبتنا أنه عندما تكون (a ) و (b ) و (c ) أعدادًا صحيحة مع (a ne 0 ) و (b ne 0 ) بحيث يكون (a ) ) يقسم (ب ) و (ب ) يقسم (ج ) ، ثم (أ ) يقسم (ج ).

إرشادات الكتابة لأرقام المعادلات

لقد كتبنا إثبات النظرية 3.1 وفقًا للإرشادات المقدمة في القسم 1.2 ، ولكن العنصر الجديد الذي ظهر في هذا الدليل هو استخدام أرقام المعادلات. فيما يلي بعض الإرشادات التي يمكن استخدامها أرقام المعادلة.

إذا كان من الضروري الإشارة إلى معادلة لاحقًا في برهان ، فيجب توسيط هذه المعادلة وعرضها. ثم يجب إعطاؤه رقمًا. يجب كتابة رقم المعادلة بين قوسين على نفس السطر مثل المعادلة في الهامش الأيمن كما هو موضح في المثال التالي.

نظرًا لأن (x ) عدد صحيح فردي ، يوجد عدد صحيح (n ) مثل ذلك

[س = 2 ن + 1 ].

لاحقًا في الإثبات ، قد يكون هناك سطر مثل

ثم ، باستخدام النتيجة في المعادلة (1) ، نحصل عليها. .

لاحظ أننا لم نقم بترقيم كل معادلة في النظرية 3.1. يجب علينا فقط ترقيم تلك المعادلات التي سنشير إليها لاحقًا في البرهان ، ويجب علينا فقط معادلات الأرقام عندما يكون ذلك ضروريًا. على سبيل المثال ، بدلاً من ترقيم المعادلة ، غالبًا ما يكون من الأفضل استخدام عبارة مثل ، "المعادلة السابقة تثبت ذلك. "أو" يمكننا إعادة ترتيب المصطلحات على الجانب الأيمن من المعادلة السابقة ". لاحظ أيضًا أن كلمة "معادلة" لا تُكتب بأحرف كبيرة عندما نشير إلى معادلة برقم. على الرغم من أنه قد يكون من المناسب استخدام حرف "E" الكبير ، إلا أن العرف المعتاد في الرياضيات هو عدم الكتابة بالأحرف الكبيرة.

التحقق من التقدم 3.2 (خاصية القواسم)

  1. أعط ما لا يقل عن أربعة أمثلة مختلفة من الأعداد الصحيحة (أ ) و (ب ) و (ج ) مع (أ ني 0 ) بحيث (أ ) يقسم (ب ) و (أ) يقسم (ج ).
  2. لكل مثال في الجزء (1) ، احسب المجموع (b + c ). هل العدد الصحيح (أ ) يقسم المجموع (ب + ج )؟
  3. أنشئ جدول معرفة للافتراض التالي: لجميع الأعداد الصحيحة (أ ) و (ب ) و (ج ) مع (أ ني 0 ) ، إذا (أ ) يقسم (ب ) و (أ ) يقسم (ج ) ، ثم يقسم (ب + ج ).
إجابه

أضف النصوص هنا. لا تحذف هذا النص أولا.

استخدام الأمثلة المضادة

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

لكل عدد صحيح (n ) ، إذا كانت 5 قسمة (n ^ 2 - 1 ) ، ثم 5 قسامات (n - 1 ).

لنفترض أننا بدأنا في محاولة إثبات هذا الاقتراح. في العملية السابقة ، يمكننا القول أنه من أجل إثبات أن 5 أقسام (n - 1 ) ، يمكننا إظهار وجود عدد صحيح (ك ) بحيث

(Q_1 ): (n - 1 = 5k ) أو (n = 5k + 1 ).

بالنسبة للعملية إلى الأمام ، يمكننا القول أنه منذ 5 انقسامات (n ^ 2 - 1) ، نعلم أن هناك interger (m ) بحيث

(P_1 ): (n ^ 2-1 = 5 م ) أو (n ^ 2 = 5 م + 1 ).

تكمن المشكلة في عدم وجود طريقة مباشرة لاستخدام (P_1 ) لإثبات (Q_1 ). في هذه المرحلة ، سيكون من الجيد تجربة بعض الأمثلة من أجل (n ) ومحاولة إيجاد مواقف تكون فيها فرضية الاقتراح صحيحة. (في الواقع ، كان يجب القيام بذلك قبل أن نبدأ بمحاولة إثبات الاقتراح.) يلخص الجدول التالي نتائج بعض هذه الاستكشافات بقيم (n ).

(ن) (n ^ 2 -1 )هل 5 قسمة ( (n ^ 2 - 1 )) (ن - 1 )هل 5 قسمة ( (n - 1 ))
10نعم0نعم
23لا1لا
38لا2لا
415نعم3لا

يمكننا التوقف عن استكشاف الأمثلة الآن لأن الصف الأخير في الجدول يقدم مثالاً حيث تكون الفرضية صحيحة والاستنتاج خاطئ. تذكر من القسم 2.4 (انظر الصفحة 69) أن أ مكافحة المثال للحصول على بيان بالنموذج ( forall x in U) (P (x)) ) هو عنصر a في المجموعة العامة التي يكون (P (a) ) خطأ. لذلك فقد أثبتنا بالفعل أن نفي الاقتراح صحيح.

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

تخمين. لكل عدد صحيح (n ) ، إذا كانت 5 قسمة ( (n ^ 2 ) - 1) ، إذن 5 قسامات ( (n ) - 1).

العدد الصحيح (n ) = 4 هو مثال مضاد يثبت أن هذا التخمين خاطئ. لاحظ أنه عندما (n ) = 4 ، (n ^ 2 ) - 1 = 15 و 5 قسمة 15. ومن ثم ، فإن فرضية التخمين صحيحة في هذه الحالة. بالإضافة إلى ذلك ، (n ) - 1 = 3 و 5 لا تقسم 3 وبالتالي فإن نتيجة التخمين خاطئة في هذه الحالة. نظرًا لأن هذا مثال حيث تكون الفرضية صحيحة والاستنتاج خاطئ ، فإن التخمين خاطئ.

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

التحقق من التقدم 3.3: استخدام مثال مضاد

استخدم مثالاً مضادًا لإثبات أن العبارة التالية خاطئة.

لجميع الأعداد الصحيحة (أ ) و (ب ) ، إذا كانت 5 قسمة (أ ) أو 5 قسمة (ب ) ، ثم 5 قسمة (5 (أ ) + (ب )).

إجابه

أضف النصوص هنا. لا تحذف هذا النص أولا.

التطابق

ما يسميه علماء الرياضيات التطابق هو مفهوم يستخدم لوصف الدورات في عالم الأعداد الصحيحة. على سبيل المثال ، يعتبر يوم الأسبوع ظاهرة دورية حيث يتكرر يوم الأسبوع كل سبعة أيام. الوقت من اليوم هو ظاهرة دورية لأنه يتكرر كل 12 ساعة إذا استخدمنا تنسيق 12 ساعة أو كل 24 ساعة إذا استخدمنا تنسيق 24 ساعة. لقد اكتشفنا هاتين الظاهرتين الدوريتين في معاينة النشاط ( PageIndex {2} ).

على غرار ما رأيناه في نشاط المعاينة ( PageIndex {2} ) ، إذا كان يوم الاثنين حاليًا ، فسيكون يوم الأربعاء بعد يومين من الآن ، و 9 أيام من الآن ، و 16 يومًا من الآن ، و 23 يومًا من الآن ، و قريبا. بالإضافة إلى ذلك ، كان الأربعاء قبل 5 أيام ، قبل 12 يومًا ، قبل 19 يومًا ، وهكذا. باستخدام الأرقام السالبة للوقت في الماضي ، نقوم بإنشاء قائمة الأرقام التالية:

..., -19, -12, -5, 2, 9, 16, 23, ...

لاحظ أننا إذا طرحنا أي رقم في القائمة أعلاه من أي رقم آخر في تلك القائمة ، فسنحصل على مضاعف الرقم 7. على سبيل المثال ،

مثال:

16-2 = 14 = 7 ( cdot ) 2

(-5) - (9) = -14 = 7 ( cdot ) (-2)

16 - (-12) = 28 = 7 ( cdot ) 4.

باستخدام مفهوم التطابق ، يمكننا أن نقول إن جميع الأرقام في هذه القائمة هي وحدة 7 متطابقة ، لكن علينا أولاً تحديد متى يكون رقمان متطابقين مع رقم طبيعي (n ).

تعريف

دعنا (n in mathbb {N} ). إذا كان (أ ) و (ب ) عددًا صحيحًا ، فإننا نقول ذلك (a ) مطابق (b ) modulo (n ) بشرط أن (n ) يقسم (أ - ب ). التدوين القياسي لهذا هو (a equiv b ) (mod (n )). يُقرأ هذا على أنه " (a ) مطابق (b ) modulo (n )" أو " (a ) مطابق (b ) mod (n )."

لاحظ أنه يمكننا استخدام تعريف القسمة لنقول أن (n ) يقسم (أ - ب ) إذا وفقط إذا كان هناك عدد صحيح (ك ) بحيث (أ - ب = ن ك ). حتى نتمكن من الكتابة

(a equiv b ) (mod (n )) تعني (( موجود ك في mathbb {Z}) (أ - ب = ن ك) ) ، أو
(a equiv b ) (mod (n )) تعني (( موجود ك في mathbb {Z}) (أ = ب + ن ك) ).

هذا يعني أنه من أجل إيجاد الأعداد الصحيحة المتطابقة مع (b ) modulo (n ) ، نحتاج فقط إلى إضافة مضاعفات (n ) إلى (b ). على سبيل المثال ، للعثور على الأعداد الصحيحة المتطابقة مع 2 modulo 5 ، نضيف مضاعفات 5 إلى 2. وهذا يعطي القائمة التالية:

... -13, -8, -3, 2, 7, 12, 17,...

يمكننا أيضًا كتابة هذا باستخدام مجموعة الرموز ونقول ذلك

{ (a in mathbb {Z} | a equiv 2 ) (mod 5)} = {... -13، -8، -3، 2، 7، 12، 17، ...}

فحص التقدم 3.4 (مطابقة Modulo 8)

  1. حدد ما لا يقل عن ثمانية أعداد صحيحة مختلفة تتوافق مع 5 modulo 8.
  2. يستخدم مجموعة ملاحظات البناء والطريقة الأخرى لتحديد هذه مجموعة من الأعداد الصحيحة

    التي تتطابق مع 5 modulo 8.

  3. اختر عددين صحيحين متطابقين مع 5 modulo 8 وأضفهما. ثم كرر هذا مع ما لا يقل عن خمسة أزواج أخرى من الأعداد الصحيحة المتطابقة مع 5 modulo 8.
  4. اشرح سبب تطابق جميع المبالغ التي تم الحصول عليها في الجزء (3) مع 2 modulo 8.
إجابه

أضف النصوص هنا. لا تحذف هذا النص أولا.

سوف ندرس مفهوم وحدة التطابق (n ) بمزيد من التفصيل لاحقًا في النص. في الوقت الحالي ، سنعمل على تعريف وحدة التطابق (n ) في سياق البراهين. على سبيل المثال ، يجب أن تقدم جميع الأمثلة المستخدمة في فحص التقدم 3.4 دليلًا على صحة الاقتراح التالي.

الاقتراح 3.5.

لجميع الأعداد الصحيحة (a ) و (b ) ، إذا (a equiv 5 ) (mod 8) و (b equiv 5 ) (mod 8) ، ثم ( (a ) + (ب )) ( equiv ) 2 (تعديل 8).

التحقق من التقدم 3.6 (إثبات الاقتراح 3.5)

سنستخدم "أسئلة رجعية" و "أسئلة إلى الأمام" للمساعدة في بناء دليل على الاقتراح 3.5. لذلك ، قد نسأل ، "كيف نثبت أن ( (a ) + (b )) ( equiv ) 2 (mod 8)" إحدى الطرق للإجابة على هذا هو استخدام تعريف التطابق و اذكر أن ( (a ) + (b )) ( equiv ) 2 (mod 8) بشرط أن 8 أقسام ( (a + b - 2 )).

  1. استخدم تعريف القسمة لتحديد طريقة لإثبات أن 8 قواسم ( (أ + ب - 2 )).

    ننتقل الآن إلى ما نعرفه ونسأل ، "ماذا يمكننا أن نستنتج من الافتراضات التي (a equiv 5 ) (mod 8) و (b equiv 5 ) (mod 8)." يمكننا مرة أخرى استخدام تعريف التطابق واستنتاج أن 8 أقسام ( (أ ) - 5) و 8 أقسام ( (ب ) - 5).

  2. استخدم تعريف التقسيمات للوصول إلى استنتاجات بناءً على الحقائق التي تقسم 8 ( (أ ) - 5) و 8 أقسام ( (ب ) - 5).
  3. حل معادلة من الجزء (2) من أجل (أ ) ومن أجل (ب ).
  4. استخدم النتائج من الجزء (3) لإثبات أن 8 قواسم ( (أ + ب - 2 )).
  5. اكتب إثباتًا للمقترح 3.5.
إجابه

أضف النصوص هنا. لا تحذف هذا النص أولا.

إرشادات الكتابة الإضافية

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

  1. اعرف جمهورك. يجب أن يكون لدى كل كاتب فكرة واضحة عن الجمهور المستهدف لمقطع ما. بهذه الطريقة ، يمكن للكاتب أن يعطي المقدار الصحيح من المعلومات بالمستوى المناسب من التطور للتواصل بشكل فعال. هذا ينطبق بشكل خاص على الكتابة الرياضية. على سبيل المثال ، إذا كان عالم الرياضيات يكتب حلاً لمشكلة كتاب مدرسي لكتيب حلول للمعلمين ، فستكون الكتابة مختصرة مع حذف العديد من التفاصيل. ومع ذلك ، إذا كانت الكتابة لدليل حلول الطلاب ، فسيتم تضمين المزيد من التفاصيل.
  2. استخدم جمل كاملة وهيكل الفقرة المناسب. القواعد الجيدة هي جزء مهم من أي كتابة. لذلك ، يجب الالتزام بقواعد النحو المقبولة. انتبه جيدًا إلى بنية الجمل. اكتب البراهين باستخدام جمل كاملة ولكن تجنب الجمل غير المباشرة. أيضًا ، لا تنسَ علامات الترقيم ، واستخدم دائمًا المدقق الإملائي عند استخدام معالج النصوص.
  3. أبقيها بسيطة. غالبًا ما يكون من الصعب فهم الحجة الرياضية بغض النظر عن مدى جودة كتابتها. لا تدع كتابتك تجعل الأمر أكثر صعوبة للقارئ. استخدم جملًا توضيحية بسيطة وفقرات قصيرة ، كل منها بنقطة بسيطة.
  4. اكتب المسودة الأولى لإثباتك ثم قم بمراجعتها. تذكر أن الدليل مكتوب حتى يتمكن القراء من قراءة وفهم المنطق في الدليل. كن واضحًا ومختصرًا. قم بتضمين التفاصيل ولكن لا تتجول. لا تكتفي بالمسودة الأولى للإثبات. اقرأها وصقلها. تمامًا مثل أي نشاط جدير بالاهتمام ، فإن تعلم كتابة الرياضيات بشكل جيد يتطلب الممارسة والعمل الجاد. قد يكون هذا محبطًا. يمكن للجميع التأكد من وجود بعض البراهين التي يصعب تكوينها ، لكن تذكر أن البراهين جزء مهم جدًا من الرياضيات. لذا اعمل بجد واستمتع.
  5. لا تستخدم ( ast ) للضرب أو ˆ للأسس. اترك هذا النوع من التدوين لكتابة رمز الكمبيوتر. استخدام هذا الترميز يجعل من الصعب على البشر القراءة. بالإضافة إلى ذلك ، تجنب استخدام / للقسمة عند استخدام كسر معقد.

    على سبيل المثال ، من الصعب جدًا قراءة ( (x ^ 3 - 3x ^ 2 + 1/2) / (2x / 3 - 7 )) ؛ الكسر

    [ dfrac {x ^ 3 - 3x ^ 2 + dfrac {1} {2}} { dfrac {2x} {3} - 7} ]

    أسهل بكثير للقراءة.

  6. لا تستخدم رمزًا رياضيًا في بداية الجملة. على سبيل المثال ، لا يجب أن نكتب ، "دع n يكون عددًا صحيحًا. ن هو عدد صحيح فردي بشرط أن. . " يجد الكثير من الناس صعوبة في قراءته وغالبًا ما يتعين عليهم إعادة قراءته لفهمه. سيكون من الأفضل أن تكتب ، "العدد الصحيح n هو عدد صحيح فردي بشرط ذلك. . "
  7. استخدم اللغة الإنجليزية وقلل من استخدام التدوين المرهق. لا تستخدم الرموز الخاصة للمحددات الكمية ( forall ) (للجميع) ، (موجود ) (موجود) ، ( epsilon ) (مثل ذلك) ، أو ( لذلك ) (لذلك) في الكتابة الرياضية الرسمية. غالبًا ما تكون الكتابة أسهل ، وعادة ما تكون أسهل في القراءة ، إذا تم استخدام الكلمات الإنجليزية بدلاً من الرموز. على سبيل المثال ، لماذا تجعل القارئ يفسر

    [( forall x in mathbb {R}) ( موجود y في mathbb {R}) (x + y = 0) ]

    عندما يكون من الممكن الكتابة
    لكل رقم حقيقي (س ) ، يوجد رقم حقيقي (ص ) مثل (س + ص = 0 ) ، أو بإيجاز أكثر (إذا كان ذلك مناسبًا) ،

كل رقم حقيقي له معكوس جمعي.

تمرين للقسم 3.1

  1. إثبات كل من العبارات التالية:

    (أ) لجميع الأعداد الصحيحة (أ ) و (ب ) و (ج ) مع (أ ني 0 ) ، إذا (أ | ب ) و (أ | ج ) ، ثم (أ | (قبل الميلاد) ).
    (ب) لكل (n in mathbb {Z} ) ، إذا كان (n ) عددًا صحيحًا فرديًا ، فإن (n ^ 3 ) هو عدد صحيح فردي.
    (ج) لكل عدد صحيح (أ ) ، إذا قسمت 4 ( (أ ) - 1) ، فحينئذٍ 4 أقسام ( (أ ^ 2 ) - 1).

  2. لكل مما يلي ، استخدم مثالاً مضادًا لإثبات أن العبارة خاطئة.

    (أ) لكل عدد طبيعي فردي (n ) ، إذا (n> 3 ) ، ثم 3 قسمة ( (n ^ 2 ) - 1).
    (ب) لكل عدد طبيعي (n ) ، ( (3 cdot 2 ^ n + 2 cdot 3 ^ n + 1 )) هو عدد أولي.
    (ج) لجميع الأعداد الحقيقية (x ) و (y ) ، ( sqrt {x ^ 2 + y ^ 2}> 2xy ).
    (د) لكل عدد صحيح (أ ) ، إذا كانت 4 قسمة ( (أ ^ 2 ) - 1) ، ثم 4 قسمة ( (أ ) - 1).

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

    (أ) لجميع الأعداد الصحيحة (أ ) ، (ب ) ، (ج ) مع (أ ني 0 ) ، إذا (أ | ب ) ، ثم (أ | (قبل الميلاد) ) ).
    (ب) لجميع الأعداد الصحيحة (أ ) و (ب ) مع (أ ني 0 ) ، إذا (6 | (أب) ) ، ثم (6 | أ ) أو (6 | ب ).
    (ج) لجميع الأعداد الصحيحة (أ ) و (ب ) و (ج ) مع (أ ني 0 ) ، إذا كان (أ ) يقسم ( (ب ) - 1) و (a ) يقسم ( (c ) -1) ، ثم (a ) يقسم ( (bc ) - 1).
    (د) لكل عدد صحيح (n ) ، إذا كانت 7 قسمة ( (n ^ 2 - 4 )) ، ثم 7 قسمة ( (n - 2 )).
    (هـ) لكل عدد صحيح (n ) ، (4n ^ 2 + 7n + 6 ) هو عدد صحيح فردي.
    (و) لكل عدد صحيح فردي (n ) ، (4n ^ 2 + 7n + 6 ) هو عدد صحيح فردي
    (ز) لجميع الأعداد الصحيحة (أ ) ، (ب ) ، (د ) مع (د ني 0 ) ، إذا كان (د ) يقسم كلا من (أ - ب ) و (أ + ب ) ، ثم (د ) يقسم (أ ).
    (ح) لجميع الأعداد الصحيحة (أ ) ، (ب ) ، (ج ) مع (أ ني 0 ) ، إذا (أ | (قبل الميلاد) ) ، ثم (أ | ب ) أو (أ | ج ).

  4. (أ) إذا كان (x ) و (y ) عددًا صحيحًا و (xy = 1 ) ، اشرح لماذا (x = 1 ) أو (x = -1 ).
    (ب) هل الافتراض التالي صحيح أم خطأ؟
    لجميع الأعداد الصحيحة غير الصفرية (أ ) و (ب ) ، إذا (أ | ب ) و (ب | أ ) ، ثم (أ = م ب ).
  5. إثبات الاقتراح التالي:

    لنفترض أن (أ ) عددًا صحيحًا. إذا كان هناك عدد صحيح (n ) مثل (a | (4n + 3) ) و (a | (2n + 1) ) ، إذن (a = 1 ) أو (a = - 1 ).

    تلميح: استخدم حقيقة أن القواسم الوحيدة للعدد 1 هي 1 و -1.

  6. حدد ما إذا كانت كل من العبارات التالية صحيحة أم خاطئة. إذا كانت العبارة صحيحة ، فاكتب إثباتًا رسميًا لتلك العبارة ، وإذا كانت خاطئة ، فقم بتوفير مثال مضاد يوضح أنها خاطئة. (أ) لكل عدد صحيح (أ ) ، إذا كان هناك عدد صحيح ( n ) بحيث (a ) يقسم ( (8n + 7 )) و (a ) يقسم ( (4n + 1 )) ، ثم (a ) يقسم 5.
    (أ) لكل عدد صحيح (أ ) ، إذا كان هناك عدد صحيح (n ) بحيث (أ ) يقسم ( (9 ن + 5 )) و (أ ) يقسم ( (6 ن) + 1 )) ، ثم (a ) يقسم 7.
    (ج) لكل عدد صحيح (n ) ، إذا كان (n ) فرديًا ، فعندئذٍ 8 قسمة ( (n ^ 4 + 4n ^ 2 + 11 )).
    (د) لكل عدد صحيح (n ) ، إذا كان (n ) فرديًا ، فعندئذٍ 8 قسمة ( (n ^ 4 + n ^ 2 + 2n )).
  7. دع (a ) عددًا صحيحًا ودع (n in mathbb {N} ).

    (أ) أثبت أنه إذا (a equiv 0 ) (mod (n )) ، إذن (n | a ).
    (ب) إثبات أنه إذا (n | a ) ، ثم (a equiv 0 ) (mod (n )).

  8. لنفترض أن (أ ) و (ب ) أعداد صحيحة. أثبت أنه إذا (a equiv 2 ) (mod 3) و (b equiv 2 ) (mod 3) ، إذن

    (أ) (أ + ب ما يعادل 1 ) (تعديل 3).
    (ب) (أ cdot ب مكافئ 1 ) (تعديل 3).

  9. لنفترض أن (أ ) و (ب ) أعداد صحيحة. أثبت أنه إذا (a equiv 7 ) (mod 8) و (b equiv 3 ) (mod 8) ، إذن

    (أ) (أ + ب مكافئ 2 ) (تعديل 8).
    (ب) (أ cdot ب مكافئ 5 ) (تعديل 8).

  10. حدد ما إذا كانت كل من الافتراضات التالية صحيحة أم خاطئة. برر كل استنتاج.

    (أ) لجميع الأعداد الصحيحة (أ ) و (ب ) ، إذا (أب مكافئ 0 ) (تعديل 6) ، ثم (أ مكافئ 0 ) (تعديل 6) أو (ب equiv ) (mod 6).
    (ب) لكل عدد صحيح (أ ) ، إذا (a equiv 2 ) (تعديل 8) ، ثم (a ^ 2 equiv 4 ) (تعديل 8).
    (ج) لكل عدد صحيح (a ) ، إذا (a ^ 2 equiv 4 ) (تعديل 8) ، ثم (a equiv 2 ) (تعديل 8).

  11. لنكن (n ) عددًا طبيعيًا. إثبات كل مما يلي:

    (أ) لكل عدد صحيح (a ) ، (a equiv a ) (mod (n )).
    هذا يسمى خاصية انعكاسية نموذج التطابق (n ).
    (ب) لكل عدد صحيح (a ) و (b ) ، إذا (a equiv b ) (mod (n )) ، ثم (b equiv a ) (mod (n )).
    هذا يسمى خاصية متماثلة نموذج التطابق (n ).
    (ج) لكل عدد صحيح (أ ) ، (ب ) و 9 ج ) ، إذا (أ مكافئ ب ) (تعديل (n )) و (ب مكافئ ج ) ( mod (n )) ، ثم (a equiv c ) (mod (n )).
    هذا يسمى خاصية متعدية نموذج التطابق (n ).

  12. لنفترض أن (n ) عددًا طبيعيًا واجعل (a ) و (b ) و (c ) و (d ) أعدادًا صحيحة. إثبات كل مما يلي.

    (أ) إذا (a equiv b ) (mod (n )) و (c equiv d ) (mod (n )) ، إذن ((a + c) equiv (b + د) ) (تعديل (n )).
    (ب) إذا (a equiv b ) (mod (n )) و (c equiv d ) (mod (n )) ، إذن (ac equiv bd ) (mod (ن)).

  13. (أ) اجعل (أ ) ، (ب ) ، و (ج ) أرقامًا حقيقية مع (أ ني 0 ). اشرح كيفية استخدام جزء من الصيغة التربيعية (يسمى المميز) لتحديد ما إذا كانت المعادلة التربيعية (ax ^ 2 + bx + c = 0 ) لها حلان للأرقام الحقيقية ، أو حل رقم حقيقي واحد ، أو لا يوجد حل للأرقام الحقيقية . (راجع التمرين (11) في القسم 1.2 للحصول على بيان بالصيغة التربيعية.)

    (ب) إثبات أنه إذا كانت (أ ) و (ب ) و (ج ) أرقامًا حقيقية يكون (أ> 0 ) و (ج <0 ) ، إذن حل واحد من المعادلة التربيعية (ax ^ 2 + bx + c = 0 ) رقم حقيقي موجب.

    (ج) أثبت أنه إذا كان (a ) و (b ) و (c ) أرقامًا حقيقية ، إذا (a ne 0 ) ، (b> 0 ) و ( dfrac {b} {2} < sqrt {ac} ) ، فإن المعادلة التربيعية (ax ^ 2 + bx + c = 0 ) ليس لها حل رقم حقيقي.

  14. لنفترض أن (ح ) و (ك ) أرقام حقيقية واجعل (r ) رقمًا موجبًا. معادلة الدائرة التي يكون مركزها عند النقطة ( (h )، (k )) ونصف قطرها (r ) هو

    [(x - h) ^ 2 + (y - k) ^ 2 = r ^ 2 ].

    نعلم أيضًا أنه إذا كان (أ ) و (ب ) أرقامًا حقيقية ، إذن

    ( bullet ) النقطة ( (a )، (b )) داخل الدائرة إذا ((a - h) ^ 2 + (b - k) ^ 2 ( bullet ) النقطة ( (a )، (b )) موجودة على الدائرة إذا ((a - h) ^ 2 + (b - k) ^ 2 = r ^ 2 ).
    ( bullet ) النقطة ( (a )، (b )) خارج الدائرة إذا ((a - h) ^ 2 + (b - k) ^ 2> r ^ 2 ).

    أثبت أن جميع النقاط الموجودة في الدائرة أو داخلها والتي تكون معادلتها ((x - 1) ^ 2 + (y - 2) ^ 2 = 4 ) داخل الدائرة التي تكون معادلتها (x ^ 2 + y ^ 2 = 26 ).

  15. لنكن (r ) رقمًا حقيقيًا موجبًا. معادلة دائرة نصف قطرها (r ) مركزها الأصل هي (x ^ 2 + y ^ 2 = r ^ 2 ).

    (أ) استخدم التفاضل الضمني لتحديد ( dfrac {dy} {dx} ).
    (ب) اجعل ( (a ) ، (b )) نقطة على الدائرة مع (a ne 0 ) و (b ne 0 ). أوجد ميل الخط المماس للدائرة عند النقطة ( (أ ) ، (ب )).
    (ج) إثبات أن نصف قطر الدائرة إلى النقطة ( (أ ) ، (ب )) عمودي على خط المماس للدائرة عند النقطة ( (أ ) ، (ب ) ). تلميح: خطان (ليس أي منهما أفقيًا) متعامدين إذا وفقط إذا كانت منتجات منحدراتهما تساوي -1.

  16. حدد ما إذا كانت كل من العبارات التالية صحيحة أم خاطئة. قدم مثالاً مضادًا للبيانات الخاطئة وقدم دليلًا كاملاً على تلك البيانات الصحيحة.

    (أ) لجميع الأعداد الحقيقية (x ) و (y ) ، ( sqrt {xy} le dfrac {x + y} {2} ).
    (ب) لجميع الأعداد الحقيقية (x ) و (y ) ، (xy le ( dfrac {x + y} {2}) ^ 2 ).
    (ج) لجميع الأعداد الحقيقية غير السالبة (x ) و (y ) ، ( sqrt {xy} le dfrac {x + y} {2} ).

  17. استخدم إحدى القيم الحقيقية في المساواة في التمرين (16) لإثبات الاقتراح التالي.

    لكل رقم حقيقي (a ) ، قيمة (x ) التي تعطي الحد الأقصى لقيمة (y = x (a - x) ) هي (x = dfrac {a} {2} ).

  18. (أ) اذكر نظرية فيثاغورس للمثلثات القائمة.
    سيتم استخدام المخططات الموجودة في الشكل 3.1 لحل المشكلات في هذا التمرين.
    (ب) في الرسم البياني الموجود على اليسار (x ) هو طول أحد ضلعي المثلث متساوي الأضلاع و (h ) هو طول ارتفاع المثلث متساوي الأضلاع. توضح التسمية في الرسم التخطيطي حقيقة أن الارتفاع يتقاطع مع قاعدة المثلث متساوي الأضلاع في منتصف القاعدة. استخدم ال

    شكل 3.1: مخططات للتمرين (18)
    نظرية فيثاغورس لإثبات أن مساحة هذا المثلث متساوي الأضلاع هي ( dfrac { sqrt3} {4} x ^ 2 ).
    (ج) في الرسم البياني على اليمين ، ( bigtriangleup ABC ) مثلث قائم الزاوية. بالإضافة إلى ذلك ، يوجد مثلث متساوي الأضلاع مبني على جانبي هذا المثلث القائم الزاوية. إثبات أن مساحة المثلث متساوي الأضلاع على الوتر تساوي مجموع مساحات المثلثات متساوية الأضلاع المبنية على جانبي المثلث القائم الزاوية.
  19. تقييم البراهين
    سيظهر هذا النوع من التمارين بشكل متكرر في الكتاب. في كل حالة ، هناك دليل مقترح على الاقتراح. ومع ذلك ، قد يكون الاقتراح صحيحًا أو قد يكون خاطئًا.

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

    (أ) اقتراح. إذا كانت m عددًا صحيحًا زوجيًا ، فإن (5m + 4 ) عدد صحيح زوجي.

    دليل. نرى ذلك (5 م + 4 = 10 ن + 4 = 2 (5 ن + 2) ). لذلك ، (5m + 4 ) عدد صحيح زوجي.

    (ب) اقتراح. لجميع الأعداد الحقيقية (x ) و (y ) ، إذا (x ne y ) ، (x> 0 ) ، و (y> 0 ) ، ثم ( dfrac {x } {y} + dfrac {y} {x}> 2 ).

    دليل. بما أن (س ) و (ص ) عدد حقيقي موجب ، فإن (س ص ) موجب ويمكننا ضرب طرفي المتباينة في (س ص ) للحصول على

    [( dfrac {x} {y} + dfrac {y} {x}) cdot xy> 2 cdot xy ]
    [x ^ 2 + y ^ 2> 2xy ].

    من خلال دمج كل الحدود على الجانب الأيسر من المتباينة ، نرى ذلك (x ^ 2 - 2xy + y ^ 2> 0 ) ثم تحليل الجانب الأيسر ، نحصل على ((x - y) ^ 2> 0 ). بما أن (x ne y )، ((x - y) ne 0 ) وهكذا ((x - y) ^ 2> 0 ). هذا يثبت أنه إذا (x ne y ) ، (x> 0 ) ، و (y> 0 ) ، أي (y> 0 ) ، ثم ( dfrac {x} {y} + dfrac {y} {x}> 2 ).

    (ج) الاقتراح. لجميع الأعداد الصحيحة (a ) و (b ) و (c ) ، إذا (a | (bc) ) ، ثم (a | b ) أو (a | c ).

    دليل. نفترض أن (أ ) و (ب ) و (ج ) أعداد صحيحة وأن (أ ) يقسم (ق ). لذلك ، يوجد عدد صحيح (ك ) مثل (bc = ka ). نحن الآن نعامل (k ) كـ (k = mn ) ، حيث (m ) و (n ) هي أعداد صحيحة. ثم نرى ذلك

    [bc = mna ].

    هذا يعني أن (b = ma ) أو (c = na ) وبالتالي ، (a | b ) أو (a | c ).

    (د) الاقتراح. لجميع الأعداد الصحيحة الموجبة (أ ) و (ب ) و (ج ) و ((أ ^ ب) ^ ج = أ ^ (ب ^ ج) ).
    هذا الاقتراح خاطئ كما هو موضح في المثال المقابل التالي: إذا سمحنا (أ = 2 ) ، (ب = 3 ) ، و (ج = 2 ) ، إذن

    [(a ^ b) ^ c = a ^ {b ^ c} ]
    [(2^3)^2 = 2 ^{3^2}]
    [8^2 = 2^9]
    [64 ne 512 ]

    الاستكشافات والأنشطة

  20. مطابقة Modulo 6

    (أ) أوجد العديد من الأعداد الصحيحة المتطابقة مع 5 modulo 6 ثم قم بتربيع كل من هذه الأعداد الصحيحة.
    (ب) لكل عدد صحيح (م ) من الجزء (20 أ) ، حدد عددًا صحيحًا (ك ) بحيث (0 لو ك <6 ) و (م ^ 2 مكافئ ك ) (تعديل 6) ثم ...
    (ج) بناءً على العمل الوارد في الجزء (20 ب) ، أكمل التخمين التالي:

    لكل عدد صحيح (م ) ، إذا (م مكافئ 5 ) (تعديل 6) ، ثم ...
    (د) أكمل جدول المعرفة للتخمين في الجزء (20 ج) أو اكتب دليلًا على التخمين.

  21. ثلاثية فيثاغورس. ثلاثة أرقام طبيعية (أ ) و (ب ) و (ج ) مع (أ <ب <ج ) تسمى ثلاثية فيثاغورس بشرط أن (أ ^ 2 + ب ^ 2 = ج ^ 2 ). راجع التمرين (13) في الصفحة 29 في القسم 1.2. يتم استدعاء ثلاثة أعداد طبيعية أعداد طبيعية متتالية إذا كان من الممكن كتابتها بالصيغة (م ) ، (م ) + 1 ، و (م ) + 2 ، حيث (م ) هو رقم طبيعي.

    (أ) حدد كل ثلاثية فيثاغورس المكونة من ثلاثة أعداد طبيعية متتالية. (اذكر نظرية وأثبتها).
    (ب) حدد كل ثلاثية فيثاغورس التي يمكن كتابتها بالصيغة (م ) ، (م +7 ) ، و (م + 8 ) ، حيث (م ) عدد طبيعي. اذكر نظرية وأثبتها.

إجابه

أضف النصوص هنا. لا تحذف هذا النص أولا.


دليل مباشر على أن $ 1 + 3 + 5 + cdots + (2n - 1) = n cdot n $

(1) إثبات باستخدام "طريقة جاوس":

$ تبدأ 2 (1 + 3+ 5 + ldots (2n-1)) & amp = & amp big [1 + (2n-1) big] + big [3 + (2n-3) big] + ldots + big [(2n-1) + 1 big] & amp = & amp underbrace <2n + 2n + ldots + 2n> _ < text <$ n $ times >> & amp = & amp2n (n). نهايةلذلك ، يتبع ذلك $ (1 + 3 + ldots (2n-1)) = n times n. $

(2) إثبات بالاستقراء: دع $ P (n) $ يكون البيان:

"لكل الأعداد الصحيحة الموجبة $ n $، $ 1 + 3 + ldots + (2n-1) = n ^ 2 $."

بالنسبة إلى $ n = 1 $ بوضوح ، $ (2 cdot 1) - 1 = 1 cdot 1 $ بحيث يكون $ P (1) $ صحيحًا. لنفترض أن النتيجة معلقة لـ $ n = k $ ، أي أن $ P (k) $ صحيح. نظرًا لأن $ P (k) $ صحيح ، فهذا يعني أن لدينا المساواة التالية عند $ n = k $:

إذا أضفت $ 2k + 1 $ إلى كلا طرفي هذه المعادلة ، فستحصل على ذلك

يوضح أن النتيجة ثابتة لـ $ n = k + 1 $ ، أي $ P (k + 1) $ صحيحة. لذلك وفقًا لمبدأ الاستقراء الرياضي ، $ 1 + 3 + ldots + (2n-1) = n cdot n $ لجميع الأعداد الصحيحة الموجبة $ n $.

(3) لنفترض أنك علمت فقط أن مجموع الأعداد الصحيحة المتتالية $ n $ هو $ n (n + 1) / 2 $. ثم

$ تبدأ1 +2 + ldots + 2n & amp = & amp frac <2n (2n + 1)> <2> يشير إلى 1 + 3 + ldots + (2n-1) & amp = & amp n (2n + 1) - 2 (1 + ldots + n) & amp = & amp 2n ^ 2 + n - 2 يسار ( frac<2> right) & amp = & amp 2n ^ 2 + n - n ^ 2 - n & amp = & amp n ^ 2. نهاية$

(4) إثبات باستخدام المجاميع المتداخلة (فكرة بيل دوبوك):

(5) إثبات بطريقة الفروق (القوة الغاشمة): دع $ a_n = sum_^ ن 2 ك -1 دولار. ثم نرى أن $ a_1 = 1 $ ، $ a_2 = 4 $ ، $ a_3 = 9 $ ، إلخ.

الآن ننظر إلى الفروق الأولى 4 - 1 = 3 دولارات ، 9 - 4 = 5 دولارات ، 16 - 9 = 7 دولارات ، إلخ. ثم عندما ننظر إلى الاختلاف الثاني ، لاحظ أنه ثابت: 5-3 دولارات = 2 $ ، 7-5 دولارات = 2 دولار ، إلخ ، لذلك نفترض ذلك

حيث $ a، b، c $ ثوابت يجب تحديدها. التوصيل في $ n = 1،2،3 $ يعطينا 3 دولارات مرات 3 $ نظام خطي لحلها ، أي النظام الخطي

$ اليسار [ البدء 1 & amp 1 & amp 1 4 & amp 2 & amp 1 9 & amp 3 & amp 1 end يمين] يسار [ ابدأ أ ب ج نهاية right] = left [ start 1 4 9 نهاية حق]

محدد مصفوفة المعامل هو

$ تبدأ 1 (2-3) - 1 (4-9) + 1 (12-81) & amp = & amp -1 + 5-69 & amp neq & amp 0 end$ لذلك لدينا حل فريد. من السهل ملاحظة أن $ a = 1 ، b = 0 ، c = 0 $ هو حل للنظام الخطي أعلاه. بالسطر السابق ، هو الحل الوحيد لذلك انتهينا.

(6) إثبات بواسطة bash مباشر: لنفترض أنك عرفت فقط أن مجموع الأعداد الصحيحة الأولى $ n $ هو $ n (n + 1) / 2 $. ثم


الرياضيات المتقطعة مقدمة مفتوحة

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

طوابع الفرع

يفتش! 22

تحتاج إلى إرسال طرد بالبريد ، ولكن لا تعرف حتى الآن مقدار الطوابع البريدية التي ستحتاجها. لديك إمداد كبير من طوابع 8 سنتات وطوابع 5 سنت. ما هي كميات الطوابع البريدية التي يمكنك إجراؤها بالضبط باستخدام هذه الطوابع؟ ما هي المبالغ التي يستحيل صنعها؟

ربما عند التحقيق في المشكلة أعلاه ، اخترت بعض المبالغ من الطوابع البريدية ، ثم اكتشفت ما إذا كان بإمكانك تحقيق هذا المبلغ باستخدام طوابع 8 سنت و 5 سنتات فقط. ربما فعلت هذا بالترتيب: هل يمكنك عمل سنت واحد من رسوم البريد؟ هل يمكنك جني سنتان؟ 3 سنتات؟ وما إلى ذلك وهلم جرا. إذا كان هذا ما فعلته ، فأنت في الواقع تجيب على أ تسلسل من الأسئلة. لدينا طرق للتعامل مع التسلسلات. دعونا نرى ما إذا كان ذلك يساعد.

في الواقع ، لن نجعل سلسلة من الأسئلة ، بل سلسلة من البيانات. لنفترض أن (P (n) ) عبارة "يمكنك عمل (n ) سنتات من الطوابع البريدية باستخدام طوابع 8 سنت و 5 سنتات فقط." نظرًا لأن كل قيمة من (n text <،> ) (P (n) ) عبارة عن بيان ، فهي إما صحيحة أو خاطئة. لذلك إذا شكلنا تسلسل البيانات

يبدأ ف (1) ، ف (2) ، ف (3) ، ف (4) ، ldots نهاية

سيتكون التسلسل من (T ) 's (صحيح) و (F )' (للخطأ). في حالتنا الخاصة يبدأ التسلسل

لأن (P (1) ، P (2) ، P (3) ، P (4) ) كلها خاطئة (لا يمكنك عمل 1 أو 2 أو 3 أو 4 سنتات من البريد) ولكن (P (5) ) صحيح (استخدم طابعًا واحدًا بخمسة سنتات) ، وهكذا.

لنفكر قليلاً في كيفية إيجاد قيمة (P (n) ) لبعض (n ) محدد (ستكون "القيمة" إما (T ) أو (F )). كيف وجدنا قيمة الحد (n ) من سلسلة من الأرقام؟ كيف وجدنا (a_n text <؟> ) كانت هناك طريقتان يمكننا القيام بذلك: إما أن تكون هناك صيغة مغلقة لـ (a_n text <،> ) حتى نتمكن من توصيل (n ) في الصيغة والحصول على قيمة الإخراج لدينا ، أو كان لدينا تعريف تعاودي للتسلسل ، لذلك يمكننا استخدام المصطلحات السابقة للتسلسل لحساب المصطلح (n ) th. عند التعامل مع تسلسل البيانات ، يمكننا استخدام أي من هذه الأساليب أيضًا. ربما توجد طريقة لاستخدام (n ) نفسها لتحديد ما إذا كان بإمكاننا صنع (n ) سنتًا من الطوابع. سيكون هذا مثل صيغة مغلقة. أو بدلاً من ذلك ، يمكننا استخدام المصطلحات السابقة في تسلسل (العبارات) لتحديد ما إذا كان بإمكاننا صنع (n ) سنتًا من طابع البريد. بمعنى ، إذا عرفنا قيمة (P (n-1) text <،> ) فهل يمكننا الانتقال من ذلك إلى قيمة (P (n) text <؟> ) سيكون ذلك شيئًا مثل تعريف متكرر للتسلسل. تذكر أن العثور على تعريفات متكررة للتسلسلات كان غالبًا أسهل من العثور على صيغ مغلقة. وينطبق الشيء نفسه هنا.

لنفترض أنني أخبرتك أن (P (43) ) صحيح (صحيح). هل يمكنك تحديد قيمة (P (44) ) من هذه الحقيقة (سواء كانت صحيحة أم خطأ)؟ نعم يمكنك ذلك. حتى لو كنا لا نعرف بالضبط كيف صنعنا 43 سنتًا من طوابع 5 و 8 سنتات ، فنحن نعلم أن هناك طريقة ما للقيام بذلك. ماذا لو استخدمت بهذه الطريقة ما لا يقل عن ثلاثة طوابع بخمسة سنتات (15 سنتًا)؟ يمكننا استبدال هذه الطوابع الثلاثة التي يبلغ سعرها 5 سنتات بطابعين من فئة 8 سنتات (صنع 16 سنتًا). ارتفع إجمالي الطوابع البريدية بمقدار 1 ، لذلك لدينا طريقة لكسب 44 سنتًا ، لذا فإن (P (44) ) صحيح. بالطبع ، افترضنا أن لدينا ما لا يقل عن ثلاثة طوابع بخمسة سنتات. ماذا لو لم نفعل؟ ثم يجب أن يكون لدينا ثلاثة طوابع على الأقل من فئة 8 سنتات (مما يجعل 24 سنتًا). إذا استبدلنا هذه الطوابع الثلاثة التي يبلغ سعرها 8 سنتات بخمس طوابع بخمسة سنتات (مما يجعل 25 سنتًا) ، فعندئذٍ مرة أخرى ، قمنا بزيادة إجمالينا بمقدار سنت واحد حتى نتمكن من صنع 44 سنتًا ، لذا فإن (P (44) ) صحيح.

لاحظ أننا لم نقول عن كيفية ربح 44 سنتًا ، فقط يمكننا ذلك ، على أساس أنه يمكننا جني 43 سنتًا. كيف نعرف أنه يمكننا جني 43 سنتًا؟ ربما لأننا نعلم أنه يمكننا صنع (42 ) سنتًا ، وهو ما نعلم أنه يمكننا القيام به لأننا نعلم أنه يمكننا جني 41 سنتًا ، وما إلى ذلك. إنها العودية! كما هو الحال مع التعريف العودي للتسلسل العددي ، يجب أن نحدد القيمة الأولية. في هذه الحالة ، القيمة الأولية هي " (P (1) ) خطأ." هذا ليس جيدًا ، لأن علاقة التكرار لدينا تقول فقط أن (P (k + 1) ) صحيح إذا (P (k) ) صحيح أيضًا. نحتاج إلى بدء العملية بـ true (P (k) text <.> ) لذا بدلاً من ذلك ، قد نرغب في استخدام " (P (31) ) is true" كشرط أولي.

بتجميع كل هذا معًا ، نصل إلى الحقيقة التالية: من الممكن (بالضبط) جعل أي مبلغ بريدي أكبر من 27 سنتًا باستخدام طوابع 5 سنت و 8 سنتات فقط. 4 هذا لا يدعي أنه لا توجد مبالغ أقل من 27 سنتًا يمكن إجراؤها أيضًا. بمعنى آخر ، (P (k) ) صحيح لأي (k ge 28 text <.> ) لإثبات ذلك ، يمكننا القيام بما يلي:

أظهر أن (P (28) ) صحيح.

أثبت أنه إذا كان (P (k) ) صحيحًا ، فإن (P (k + 1) ) يكون صحيحًا (لأي (k ge 28 )).

افترض أننا فعلنا هذا. ثم نعلم أن الحد 28 من التسلسل أعلاه هو (T ) (باستخدام الخطوة 1 ، الشرط الأولي أو) ، وأن كل مصطلح بعد 28 هو (T ) أيضًا (باستخدام الخطوة 2 ، التكرار جزء أو). هذا هو الشكل الذي سيبدو عليه الدليل بالفعل.

دليل

لنفترض أن (P (n) ) عبارة "من الممكن عمل (n ) سنتًا من الطوابع البريدية باستخدام طوابع 5 سنت و 8 سنتات." سنظهر أن (P (n) ) صحيح للجميع (n ge 28 text <.> )

أولاً ، نوضح أن (P (28) ) صحيح: (28 = 4 cdot 5+ 1 cdot 8 text <،> ) حتى نتمكن من صنع (28 ) سنتًا باستخدام أربعة 5- سنت وطوابع 8 سنت.

افترض الآن أن (P (k) ) صحيح بالنسبة لبعض (k ge 28 text <.> ) ثم من الممكن عمل (k ) سنتًا باستخدام طوابع 5 سنت و 8 سنت. لاحظ أنه منذ (k ge 28 text <،> ) لا يمكن أن نستخدم أقل من ثلاثة طوابع بخمسة سنتات و أقل من ثلاثة طوابع من فئة 8 سنتات: استخدام اثنين من كل طوابع سيعطي 26 سنتًا فقط. الآن إذا صنعنا (ك ) سنتًا باستخدام ثلاثة طوابع على الأقل من فئة 5 سنتات ، فاستبدل ثلاثة طوابع من فئة 5 سنت بطابعين من فئة 8 سنتات. هذا يستبدل 15 سنتًا من رسوم البريد بـ 16 سنتًا ، وينتقل من إجمالي (ك ) سنت إلى (ك + 1 ) سنت. إذن (P (k + 1) ) صحيح. من ناحية أخرى ، إذا صنعنا (ك ) سنتًا باستخدام ثلاثة طوابع على الأقل من فئة 8 سنتات ، فيمكننا استبدال ثلاثة طوابع من فئة 8 سنتات بخمسة طوابع بخمسة سنتات ، والانتقال من 24 سنتًا إلى 25 سنتًا ، مما يعطي إجمالي (ك + 1 ) سنتًا من الطوابع البريدية. إذن في هذه الحالة أيضًا (P (k + 1) ) صحيح.

لذلك ، وفقًا لمبدأ الاستقراء الرياضي ، (P (n) ) صحيح للجميع (n ge 28 text <.> )

قسم إضفاء الطابع الرسمي على البراهين

ما فعلناه في مثال الطوابع أعلاه يعمل مع العديد من أنواع المشكلات. يكون الإثبات بالاستقراء مفيدًا عند محاولة إثبات العبارات المتعلقة بجميع الأعداد الطبيعية ، أو جميع الأعداد الطبيعية الأكبر من بعض الحالات الأولى الثابتة (مثل 28 في المثال أعلاه) ، وفي بعض المواقف الأخرى أيضًا. على وجه الخصوص ، يجب استخدام الاستقراء عندما يكون هناك طريقة ما للانتقال من حالة إلى أخرى - عندما يمكنك دائمًا معرفة كيفية "القيام بواحدة أخرى".

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

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

هذا هو الهيكل العام للإثبات بالاستقراء الرياضي:

هيكل إثبات التعريفي

ابدأ بقول ما هو البيان الذي تريد إثباته: "دع (P (n) ) يكون البيان ..." لإثبات أن (P (n) ) صحيح للجميع (n ge 0 text <،> ) عليك إثبات حقيقتين:

الحالة الأساسية: أثبت أن (P (0) ) صحيح. أنت تفعل هذا مباشرة. هذا غالبا ما يكون سهلا.

الحالة الاستقرائية: أثبت أن (P (k) imp P (k + 1) ) للجميع (k ge 0 text <.> ) أي إثبات ذلك لأي (k ge 0 ) إذا كان (P (k) ) صحيحًا ، فسيكون (P (k + 1) ) صحيحًا أيضًا. هذا دليل على عبارة if… then… ، لذا يمكنك افتراض أن (P (k) ) صحيح ( (P (k) ) يسمى الفرضية الاستقرائية). يجب عليك بعد ذلك شرح سبب صحة (P (k + 1) ) أيضًا ، بالنظر إلى هذا الافتراض.

بافتراض أنك ناجح في كلا الجزأين أعلاه ، يمكنك أن تستنتج ، "لذلك وفقًا لمبدأ الاستقراء الرياضي ، فإن العبارة (P (n) ) صحيحة للجميع (n ge 0 text <.> )"

في بعض الأحيان ، تكون العبارة (P (n) ) صحيحة فقط لقيم (n ge 4 text <،> ) على سبيل المثال ، أو بعض القيم الأخرى. في مثل هذه الحالات ، استبدل جميع الأرقام 0 أعلاه بـ 4 (أو القيمة الأخرى).

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

الحث قوي! فكر في مدى سهولة هزيمة الدومينو عندما لا تضطر إلى دفع كل قطعة دومينو بنفسك. ما عليك سوى بدء التفاعل المتسلسل ، والاعتماد على القرب النسبي لقطع الدومينو للعناية بالباقي.

فكر في دراستنا للتسلسل. من الأسهل العثور على تعريفات متكررة للتسلسلات من الصيغ المغلقة. الانتقال من حالة إلى أخرى أسهل من الانتقال مباشرة إلى حالة معينة. هذا هو الشيء العظيم في الاستقراء. بدلاً من الانتقال مباشرةً إلى الحالة (التعسفية) لـ (n text <،> ) نحتاج فقط إلى تحديد كيفية الانتقال من حالة إلى أخرى.

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

أمثلة على القسم الفرعي

فيما يلي بعض الأمثلة على الإثبات بالاستقراء الرياضي.

مثال 2.5.1

إثبات لكل رقم طبيعي (n ge 1 ) أنه (1 + 2 + 3 + cdots + n = frac<2> نص <.> )

أولاً ، لنفكر بطريقة استقرائية في هذه المعادلة. في الواقع ، نحن نعلم أن هذا صحيح لأسباب أخرى (يتبادر إلى الذهن العكس والإضافة). ولكن لماذا يمكن أن يكون الاستقراء قابلاً للتطبيق؟ يضيف الجانب الأيسر الأرقام من 1 إلى (n text <.> ) إذا عرفنا كيفية القيام بذلك ، فإن إضافة مصطلح واحد فقط ( (n + 1 )) لن يكون بهذه الصعوبة. على سبيل المثال ، إذا افترضنا (n = 100 text <،> ) أننا نعلم أن مجموع أول 100 رقم هو (5050 ) (لذا (1 + 2 + 3 + cdots + 100 = 5050 ) text <،> ) وهذا صحيح). الآن لإيجاد مجموع أول 101 رقم ، من المنطقي أن تضيف 101 إلى 5050 فقط ، بدلاً من حساب المجموع بالكامل مرة أخرى. سيكون لدينا (1 + 2 + 3 + cdots + 100 + 101 = 5050 + 101 = 5151 نص <.> ) في الواقع ، سيكون من السهل دائمًا إضافة مصطلح آخر. هذا هو السبب في أننا يجب أن نستخدم الحث.

دليل

لنفترض أن (P (n) ) هو البيان (1 + 2 + 3 + cdots + n = frac<2> text <.> ) سنوضح أن (P (n) ) صحيح لجميع الأعداد الطبيعية (n ge 1 text <.> )

الحالة الأساسية: (P (1) ) هي العبارة (1 = frac <1 (1 + 1)> <2> ) وهي صحيحة بوضوح.

الحالة الاستقرائية: لنكن (k ge 1 ) عددًا طبيعيًا. افترض (للاستقراء) أن (P (k) ) صحيح. هذا يعني (1 + 2 + 3 + cdots + k = frac<2> text <.> ) سنثبت أن (P (k + 1) ) صحيح أيضًا. بمعنى ، يجب أن نثبت أن (1 + 2 + 3 + cdots + k + (k + 1) = frac <(k + 1) (k + 2)> <2> text <.> ) لإثبات هذه المعادلة ، ابدأ بإضافة (ك + 1 ) إلى كلا طرفي الفرضية الاستقرائية:

يبدأ 1 + 2 + 3 + cdots + k + (ك + 1) = فارك <2> + (ك + 1). نهاية

الآن ، بتبسيط الجانب الأيمن نحصل على:

وبالتالي فإن (P (k + 1) ) صحيح ، لذا وفقًا لمبدأ الاستقراء الرياضي (P (n) ) صحيح لجميع الأعداد الطبيعية (n ge 1 text <.> )

لاحظ أنه في جزء الإثبات الذي أثبتنا فيه (P (k + 1) ) من (P (k) text <،> ) استخدمنا المعادلة (P (k) text <. > ) كانت هذه الفرضية الاستقرائية. عادة ما تكون معرفة كيفية استخدام الفرضيات الاستقرائية مباشرة عند إثبات حقيقة حول مبلغ كهذا. في البراهين الأخرى ، يمكن أن يكون أقل وضوحًا حيث يناسب.

مثال 2.5.2

أثبت أنه بالنسبة للجميع (n in N text <،> ) (6 ^ n - 1 ) هو مضاعف 5.

مرة أخرى ، ابدأ بفهم ديناميكيات المشكلة. ماذا تفعل الزيادة (n )؟ دعنا نحاول مع بعض الأمثلة. إذا كان (n = 1 text <،> ) إذن نعم ، (6 ^ 1 - 1 = 5 ) هو مضاعف 5. كيف تبدو الزيادة (n ) إلى 2؟ نحصل على (6 ^ 2 - 1 = 35 text <،> ) وهو مرة أخرى من مضاعفات الرقم 5. التالي ، (n = 3 text <:> ) ولكن بدلاً من مجرد البحث عن (6 ^ 3) - 1 نص <،> ) ماذا فعلت الزيادة في (n )؟ سنستمر في طرح 1 ، لكننا الآن نضرب في 6 أخرى أولاً. إذا نظرنا بطريقة أخرى ، فإننا نضرب رقمًا واحدًا أكثر من مضاعف 5 في 6 (لأن (6 ^ 2 - 1 ) هو مضاعف 5 ، لذلك (6 ^ 2 ) هو واحد أكثر من a مضاعفات 5). كيف تبدو الأرقام التي هي أكثر من مضاعف 5؟ يجب أن يكون لديهم آخر رقم 1 أو 6. ماذا يحدث عندما تضرب هذا الرقم في 6؟ يعتمد على الرقم ، ولكن على أي حال ، يجب أن يكون الرقم الأخير من الرقم الجديد هو 6. وبعد ذلك إذا طرحت 1 ، تحصل على آخر رقم 5 ، أي مضاعف 5.

النقطة هي أنه في كل مرة نضرب فيها في ستة أخرى فقط ، لا نزال نحصل على رقم مع آخر رقم 6 ، لذا فإن طرح 1 يعطينا مضاعفًا لـ 5. الآن البرهان الرسمي:

دليل

لنفترض أن (P (n) ) هي العبارة ، " (6 ^ n - 1 ) من مضاعفات 5." سنثبت أن (P (n) ) صحيح للجميع (n in N text <.> )

الحالة الأساسية: (P (0) ) صحيحة: (6 ^ 0 -1 = 0 ) وهي من مضاعفات 5.

الحالة الاستقرائية: لنكن (ك ) عددًا طبيعيًا تعسفيًا. افترض ، من أجل الاستقراء ، أن (P (k) ) صحيح. وهذا يعني أن (6 ^ k - 1 ) هو مضاعف (5 text <.> ) ثم (6 ^ k - 1 = 5j ) لبعض الأعداد الصحيحة (j text <.> ) هذا يعني أن (6 ^ k = 5j + 1 text <.> ) اضرب كلا الجانبين في (6 text <:> )

يبدأ 6^ = 6 (5 ي + 1) = 30 ج + 6. نهاية

لكننا نريد أن نعرف عن (6 ^ - 1 نص <،> ) لذا اطرح 1 من كلا الجانبين:

بالطبع (30j + 5 = 5 (6j + 1) text <،> ) كذلك من مضاعفات الرقم 5.

لذلك (6 ^ - 1 ) هو مضاعف 5 ، أو بعبارة أخرى ، (P (k + 1) ) صحيح. وبالتالي ، وفقًا لمبدأ الاستقراء الرياضي (P (n) ) يكون صحيحًا للجميع (n in N text <.> )

كان علينا أن نكون أذكياء قليلاً (أي استخدم بعض الجبر) لتحديد موقع (6 ^ ك - 1 ) داخل (6 ^) - 1 ) قبل أن نتمكن من تطبيق الفرضية الاستقرائية. هذا ما يمكن أن يجعل البراهين الاستقرائية صعبة.

في المثالين أعلاه ، بدأنا بـ (n = 1 ) أو (n = 0 text <.> ) يمكننا البدء لاحقًا إذا احتجنا إلى ذلك.

مثال 2.5.3

إثبات ذلك (n ^ 2 lt 2 ^ n ) لجميع الأعداد الصحيحة (n ge 5 text <.> )

أولا ، فكرة الحجة. ماذا يحدث عندما نزيد (n ) بمقدار 1؟ في الجانب الأيسر ، نزيد قاعدة المربع وننتقل إلى رقم المربع التالي. على الجانب الأيمن ، نزيد من القوة 2. وهذا يعني أننا نضاعف العدد. إذن السؤال هو ، كيف ترتبط مضاعفة العدد بالزيادة إلى المربع التالي؟ فكر في شكل الفرق بين مربعين متتاليين. لدينا ((n + 1) ^ 2 - n ^ 2 text <.> ) هذه العوامل:

يبدأ (ن + 1) ^ 2 - ن ^ 2 = (ن + 1-ن) (ن + 1 + ن) = 2 ن + 1. نهاية

لكن مضاعفة الجانب الأيمن يزيده بمقدار (2 ^ n text <،> ) منذ (2 ^ = 2 ^ n + 2 ^ n text <.> ) عندما يكون (n ) كبيرًا بما يكفي ، (2 ^ n & gt 2n + 1 text <.> )

ما نقوله هنا هو أنه في كل مرة يزداد (n ) يزيد الجانب الأيسر بمقدار أقل من الجانب الأيمن. لذلك إذا بدأ الجانب الأيسر أصغر (كما يحدث عندما (n = 5 )) ، فلن يلحق بالركب أبدًا. الآن الدليل الرسمي:

دليل

لنفترض أن (P (n) ) هو البيان (n ^ 2 lt 2 ^ n text <.> ) سنثبت أن (P (n) ) صحيح لجميع الأعداد الصحيحة (n ge 5 نص <.> )

الحالة الأساسية: (P (5) ) هي البيان (5 ^ 2 lt 2 ^ 5 text <.> ) منذ (5 ^ 2 = 25 ) و (2 ^ 5 = 32 text <،> ) نرى أن (P (5) ) صحيح بالفعل.

الحالة الاستقرائية: لنكن (k ge 5 ) عددًا صحيحًا عشوائيًا. افترض ، من أجل الاستقراء ، أن (P (k) ) صحيح. وهذا يعني أن (k ^ 2 lt 2 ^ k text <.> ) سوف نثبت أن (P (k + 1) ) صحيح ، أي ((k + 1) ^ 2 لتر 2 ^ text <.> ) لإثبات عدم المساواة ، ابدأ بالجانب الأيسر واعمل باتجاه الطرف الأيمن:

يبدأ (k + 1) ^ 2 amp = k ^ 2 + 2k + 1 amp amp lt 2 ^ k + 2k + 1 amp ldots text amp lt 2 ^ k + 2 ^ k amp ldots text <منذ> 2k + 1 lt 2 ^ k text k ge 5. amp = 2 ^. أمبير نهاية

بعد المساواة وعدم المساواة من خلال ، نحصل على ((k + 1) ^ 2 lt 2 ^ text <،> ) بمعنى آخر ، (P (k + 1) text <.> ) لذلك وفقًا لمبدأ الاستقراء الرياضي ، (P (n) ) صحيح للجميع (n ) 5 نص <.> )

قد يذكرك المثال السابق بـ مبدأ مضمار السباق من حساب التفاضل والتكامل ، الذي ينص على أنه إذا (f (a) lt g (a) text <،> ) و (f '(x) lt g' (x) ) لـ (x & gt a text <،> ) ثم (f (x) lt g (x) ) لـ (x & gt a text <.> ) نفس الفكرة: الوظيفة الأكبر تزداد بمعدل أسرع من الدالة الأصغر ، لذلك ستبقى الدالة الأكبر أكبر. في الرياضيات المنفصلة ، ليس لدينا مشتقات ، لذلك ننظر إلى الاختلافات. وبالتالي فإن الاستقراء هو السبيل للذهاب.

تحذير:

مع القوة العظيمة تأتي المسؤولية العظيمة. الاستقراء ليس سحرًا. يبدو من القوي جدًا أن تكون قادرًا على افتراض أن (P (k) ) صحيح. بعد كل شيء ، نحاول إثبات صحة (P (n) ) والفرق الوحيد هو في المتغير: (k ) مقابل (n text <.> ) هل نفترض أن ما نحن تريد أن تثبت صحتها؟ ليس صحيحا. نفترض أن (P (k) ) صحيح فقط من أجل إثبات صحة (P (k + 1) ).

ما زلت تعتقد أنه يمكنك إثبات أي شيء بالاستقراء. ضع في اعتبارك هذا "الدليل" غير الصحيح على أن كل كندي له نفس لون العين: لنفترض أن (P (n) ) هو البيان الذي يشير إلى أن أي كندي (n ) له نفس لون العين. (P (1) ) صحيح ، لأن كل شخص لديه نفس لون عينه. افترض الآن أن (P (k) ) صحيح. أي ، افترض أنه في أي مجموعة من الكنديين ، كل شخص لديه نفس لون العين. الآن فكر في مجموعة تعسفية من (ك + 1 ) الكنديين. يجب أن يكون أول (ك ) من هؤلاء جميعًا نفس لون العين ، نظرًا لأن (P (k) ) صحيح. أيضًا ، يجب أن يكون (ك ) الأخير من نفس لون العين ، لأن (P (k) ) صحيح. لذلك في الواقع ، يجب أن يكون لكل فرد في المجموعة نفس لون العين. إذن (P (k + 1) ) صحيح. لذلك وفقًا لمبدأ الاستقراء الرياضي ، (P (n) ) صحيح للجميع (n text <.> )

من الواضح أن هناك خطأ ما. تكمن المشكلة في أن الدليل الذي يشير إلى (P (k) ) يعني (P (k + 1) ) يفترض أن (k ge 2 text <.> ) لقد أظهرنا فقط (P (1) )) صحيح. في الواقع ، (P (2) ) خطأ.

الاستقراء القوي للفرع الفرعي

يفتش! 23

ابدأ بقطعة ورق مربعة. تريد تقطيع هذا المربع إلى مربعات أصغر ، دون ترك أي نفايات (يجب أن تكون كل قطعة من الورق في نهاية المطاف مربعة). من الواضح أنه من الممكن قطع المربع إلى 4 مربعات. يمكنك أيضًا تقطيعه إلى 9 مربعات. اتضح أنه يمكنك قطع المربع إلى 7 مربعات (على الرغم من أنه ليس جميعها بنفس الحجم). ما هي أعداد المربعات الأخرى التي يمكن أن تنتهي بها؟

في بعض الأحيان ، لإثبات صحة (P (k + 1) ) ، سيكون من المفيد معرفة ذلك (P (k) ) و (ف (ك -1) ) و (P (k-2) ) كلها صحيحة. ضع في اعتبارك اللغز التالي:

لديك لوح شوكولاتة مستطيل الشكل ، مكون من (n ) مربعات متطابقة من الشوكولاتة. يمكنك أن تأخذ مثل هذا الشريط وكسره على طول أي صف أو عمود. كم مرة سيتعين عليك كسر الشريط لتقليله إلى (n ) مربعات شوكولاتة واحدة؟

في البداية ، قد يبدو هذا السؤال مستحيلاً. ربما قصدت أن أسأل عن أصغر عدد فترات الراحة اللازمة؟ دعنا نتحرى.

ابدأ ببعض الحالات الصغيرة. إذا كان (n = 2 text <،> ) يجب أن يكون لديك (1 مرات 2 ) مستطيل ، والذي يمكن اختزاله إلى قطع مفردة في فاصل واحد. مع (n = 3 text <،> ) يجب أن يكون لدينا (1 مرات 3 ) شريط ، والذي يتطلب فاصلين: الفاصل الأول ينشئ مربعًا واحدًا و (1 مرات 2 ) ، والتي نعلم أنها تأخذ استراحة واحدة (أكثر).

ماذا عن (n = 4 text <؟> ) الآن يمكننا الحصول على (2 مرات 2 ) بار ، أو (1 مرات 4 ). في الحالة الأولى ، قسّم الشريط إلى شريطين (2 مرات 2 ) ، يتطلب كل منهما فاصلًا إضافيًا (وهذا إجمالي ثلاثة فواصل مطلوبة). إذا بدأنا بشريط (1 مرات 4 ) ، فلدينا خيارات للاستراحة الأولى. يمكننا كسر الشريط إلى النصف ، وإنشاء شريطين (1 مرات 2 ) ، أو يمكننا فصل مربع واحد ، وترك شريط (1 مرات 3 ). لكن في كلتا الحالتين ، ما زلنا بحاجة إلى استراحة إضافية ، ليصبح المجموع ثلاثة.

لقد بدأ يبدو بغض النظر عن كيفية كسر الشريط (وبغض النظر عن كيفية ترتيب المربعات (n ) في مستطيل) ، سيكون لدينا دائمًا نفس عدد الفواصل المطلوبة. يبدو أيضًا أن هذا الرقم أقل من (n text <:> )

التخمين 2.5.4

بالنظر إلى (n ) - قطعة شوكولاتة مستطيلة مربعة ، يتطلب الأمر دائمًا (n-1 ) فواصل لتقليل الشريط إلى مربعات مفردة.

من المنطقي إثبات ذلك عن طريق الاستقراء لأنه بعد كسر الشريط مرة واحدة ، يتبقى لك الأصغر قطع شوكولاته. التقليل إلى الحالات الأصغر هو ما يدور حوله الاستقراء. يمكننا أن نفترض حثيًا أننا نعرف بالفعل كيفية التعامل مع هذه الأعمدة الصغيرة. المشكلة هي ، إذا كنا نحاول إثبات الحالة الاستقرائية حول ((k + 1) ) - شريط مربع ، فإننا لا نعرف أنه بعد الكسر الأول ، سيحتوي الشريط المتبقي على مربعات (k ). لذلك نحتاج حقًا إلى افتراض أن تخميننا صحيح لجميع الحالات الأقل من (k + 1 text <.> )

هل يصح جعل هذا الافتراض أقوى؟ تذكر ، في الاستقراء نحاول إثبات أن (P (n) ) صحيح للجميع (n text <.> ) ماذا لو لم يكن الأمر كذلك؟ ثم سيكون هناك أولًا (n_0 ) كان (P (n_0) ) خطأ. بما أن (n_0 ) هو ملف أول مثال مضاد ، نعلم أن (P (n) ) صحيح للجميع (n lt n_0 text <.> ) الآن ننتقل لإثبات أن (P (n_0) ) صحيح بالفعل ، بناءً على الافتراض بأن (P (n) ) صحيح لجميع (n text <.> )

هذه ميزة كبيرة: لدينا الآن فرضية استقرائية أقوى. يمكننا أن نفترض أن (P (1) text <،> ) (P (2) text <،> ) (P (3) text <،> ) ... (P (k) ) صحيح ، فقط لإظهار أن (P (k + 1) ) صحيح. في السابق ، افترضنا للتو (P (k) ) لهذا الغرض.

سيكون من الأسهل قليلاً إذا قمنا بتغيير متغيراتنا للاستقراء القوي. إليك ما سيبدو عليه الدليل الرسمي:

هيكل قوي لإثبات الحث

مرة أخرى ، ابدأ بقول ما تريد إثباته: "دع (P (n) ) يكون البيان ..." ثم حدد حقيقتين:

الحالة الأساسية: أثبت أن (P (0) ) صحيح.

الحالة الاستقرائية: افترض أن (P (k) ) صحيح للجميع (k lt n text <.> ) أثبت أن (P (n) ) صحيح.

استنتج ، "لذلك ، من خلال الاستقراء القوي ، (P (n) ) صحيح للجميع (n gt 0 text <.> )"

بالطبع ، من المقبول استبدال 0 بحالة أساسية أكبر إذا لزم الأمر. 5 من الناحية الفنية ، لا يتطلب الاستقراء القوي إثبات حالة أساسية منفصلة. هذا لأنه عند إثبات الحالة الاستقرائية ، يجب أن تُظهر أن (P (0) ) صحيح ، بافتراض أن (P (k) ) صحيح للجميع (k lt 0 text <.> ) لكن هذا ليس أي مساعدة ، لذا ينتهي بك الأمر بإثبات (P (0) ) على أي حال. لنكون في الجانب الآمن ، سنقوم دائمًا بتضمين الحالة الأساسية بشكل منفصل.

دعنا نثبت تخميننا حول لغز لوح الشوكولاتة:

دليل

لنفترض أن (P (n) ) هي العبارة ، "يستغرق الأمر (n-1 ) فواصل لتقليل (n ) - قطعة شوكولاتة مربعة إلى مربعات مفردة."

الحالة الأساسية: ضع في اعتبارك (P (2) text <.> ) يجب ترتيب المربعات في مستطيل (1 times 2 ) ، ونطلب فواصل (2-1 = 1 ) لتقليل هذا لمربعات مفردة.

الحالة الاستقرائية: أصلح تعسفيًا (n ge 2 ) وافترض أن (P (k) ) صحيح للجميع (k lt n text <.> ) ضع في اعتبارك a (n ) - مربع شريط شوكولاتة مستطيل. اكسر الشريط مرة واحدة على طول أي صف أو عمود. ينتج عن هذا لوحتي شوكولاتة ، على سبيل المثال الحجم (أ ) و (ب نص <.> ) أي لدينا (أ ) - لوح شوكولاتة مستطيل الشكل ، أ (ب ) - شريط شوكولاتة مربع مستطيل الشكل ، و (أ + ب = n نص <.> )

نعلم أيضًا أن (a lt n ) و (b lt n text <،> ) لذلك من خلال فرضيتنا الاستقرائية ، (P (a) ) و (P (b) ) هي حقيقية. لتقليل (a ) - شريط sqaure إلى مربعات فردية يأخذ (a-1 ) فواصل لتقليل (b ) - شريط مربع إلى مربعات مفردة يأخذ (b-1 ) فواصل. يؤدي القيام بذلك إلى تقليل شريطنا الأصلي إلى مربعات مفردة. استغرق الأمر معًا الفاصل الأولي ، بالإضافة إلى فواصل (أ -1 ) و (ب -1 ) ، ليصبح المجموع (1 + أ-1 + ب -1 = أ + ب -1 = ن -1 ) فواصل. وبالتالي (P (n) ) صحيح.

لذلك ، من خلال الاستقراء القوي ، يكون (P (n) ) صحيحًا للجميع (n ge 2 text <.> )

فيما يلي مثال أكثر صلة بالرياضيات:

مثال 2.5.5

إثبات أن أي عدد طبيعي أكبر من 1 هو إما أولي أو يمكن كتابته على أنه حاصل ضرب الأعداد الأولية.

أولاً ، الفكرة: إذا أخذنا بعض الأرقام (n text <،> ) فربما يكون عددًا أوليًا. إذا كان الأمر كذلك ، فقد انتهينا. إذا لم يكن كذلك ، فهو مركب ، لذا فهو حاصل ضرب رقمين أصغر. كل من هذه العوامل أصغر من (n ) (لكن على الأقل 2) ، لذا يمكننا تكرار الوسيطة بهذه الأرقام. لقد اختزلنا إلى حالة أصغر.

دليل

لنفترض أن (P (n) ) عبارة ، " (n ) إما أولي أو يمكن كتابتها على أنها نتاج الأعداد الأولية." سنثبت أن (P (n) ) صحيح للجميع (n ge 2 text <.> )

الحالة الأساسية: (P (2) ) صحيحة لأن (2 ) عدد أولي بالفعل.

الحالة الاستقرائية: افترض أن (P (k) ) صحيح للجميع (k lt n text <.> ) نريد أن نظهر أن (P (n) ) صحيح. أي أننا نريد أن نظهر أن (n ) إما أولي أو هو نتاج الأعداد الأولية. إذا كان (n ) أوليًا ، فقد انتهينا. إذا لم يكن الأمر كذلك ، فإن (n ) يحتوي على أكثر من مقسومين ، لذا يمكننا كتابة (n = m_1 cdot m_2 text <،> ) مع (m_1 ) و (m_2 ) أقل من ( n ) (وأكبر من 1). من خلال الفرضية الاستقرائية ، (m_1 ) و (m_2 ) كلاهما إما أولي أو يمكن كتابته على أنه حاصل ضرب الأعداد الأولية. في كلتا الحالتين ، لدينا هذا (n ) مكتوب على أنه حاصل ضرب الأعداد الأولية.

وبالتالي من خلال الاستقراء القوي ، يكون (P (n) ) صحيحًا للجميع (n ge 2 text <.> )

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

كتباين أخير بين شكلي الاستقراء ، فكر مرة أخرى في مشكلة الطوابع. عمل الاستقراء المنتظم من خلال إظهار كيفية زيادة الطوابع البريدية بمقدار سنت واحد (إما استبدال ثلاثة طوابع من فئة 5 سنت بطابعين من فئة 8 سنتات ، أو ثلاثة طوابع من فئة 8 سنتات بخمس طوابع بخمسة سنتات). يمكننا تقديم دليل مختلف قليلاً باستخدام الاستقراء القوي. أولا ، يمكننا أن نظهر خمسة الحالات الأساسية: من الممكن عمل 28 و 29 و 30 و 31 و 32 سنتًا (يمكننا أن نقول في الواقع كيف يتم صنع كل منها). افترض الآن أنه من الممكن عمل (k ) سنتًا من الطوابع البريدية للجميع (k lt n ) طالما (k ge 28 text <.> ) طالما (n & gt 32 text <،> ) وهذا يعني على وجه الخصوص أنه يمكننا صنع (k = n-5 ) سنتات. أضف الآن طابعًا بقيمة 5 سنتات للحصول على (n ) سنتًا.

تمارين القسم

استخدم الاستقراء لإثبات للجميع (n in N ) أن ( d sum_^ ن 2 ^ ك = 2 ^ - 1 نص <.> )

دليل

يجب أن نثبت أن (1 + 2 + 2 ^ 2 + 2 ^ 3 + cdots + 2 ^ n = 2 ^ - 1 ) للجميع (n in N text <.> ) لذلك دع (P (n) ) هو البيان (1 + 2 + 2 ^ 2 + cdots + 2 ^ n = 2 ^ - 1 text <.> ) سنثبت أن (P (n) ) صحيح للجميع (n in N text <.> ) أولاً ، نؤسس الحالة الأساسية ، (P ( 0) text <،> ) الذي يدعي أن (1 = 2 ^ <0 + 1> -1 text <.> ) منذ (2 ^ 1 - 1 = 2-1 = 1 text <، > ) نرى أن (P (0) ) صحيح. الآن للحالة الاستقرائية. افترض أن (P (k) ) صحيح من أجل (k in N text <.> ) أي ، (1 + 2 + 2 ^ 2 + cdots + 2 ^ k = 2 ^ - 1 text <.> ) يجب أن نبين أن (P (k + 1) ) صحيح (أي أن (1 + 2 + 2 ^ 2 + cdots + 2 ^) = 2^ - 1 )). للقيام بذلك ، نبدأ بالجانب الأيسر من (P (k + 1) ) ونعمل على الجانب الأيمن:

يبدأ 1 + 2 + 2 ^ 2 + cdots + 2 ^ k + 2 ^ = أمبير

وبالتالي فإن (P (k + 1) ) صحيح ، لذا وفقًا لمبدأ الاستقراء الرياضي ، (P (n) ) صحيح للجميع (n in N text <.> )

أثبت أن (7 ^ n - 1 ) هو مضاعف 6 للجميع (n in N text <.> )

دليل

لنفترض أن (P (n) ) عبارة " (7 ^ n - 1 ) من مضاعفات 6." سنظهر أن (P (n) ) صحيح للجميع (n in N text <.> ) أولاً نقوم بتأسيس الحالة الأساسية ، (P (0) text <.> ) منذ ذلك الحين (7 ^ 0 - 1 = 0 text <،> ) و (0 ) هو مضاعف 6 ، (P (0) ) صحيح. الآن للحالة الاستقرائية. افترض أن (P (k) ) يحمل علامة تعسفية (k in N text <.> ) أي ، (7 ^ k - 1 ) مضاعف 6 ، أو بعبارة أخرى ، (7 ^ k - 1 = 6j ) لبعض الأعداد الصحيحة (j text <.> ) الآن ضع في اعتبارك (7 ^ - 1 نص <:> )

لذلك (7 ^ - 1 ) هو مضاعف 6 ، أو بعبارة أخرى ، (P (k + 1) ) صحيح. لذلك وفقًا لمبدأ الاستقراء الرياضي ، يكون (P (n) ) صحيحًا للجميع (n in N text <.> )

أثبت أن (1 + 3 + 5 + cdots + (2n-1) = n ^ 2 ) للجميع (n ge 1 text <.> )

دليل

لنفترض أن (P (n) ) هو البيان (1 + 3 +5 + cdots + (2n-1) = n ^ 2 text <.> ) سوف نثبت ذلك (P (n) ) صحيح للجميع (n ge 1 text <.> ) أولاً الحالة الأساسية ، (P (1) text <.> ) لدينا (1 = 1 ^ 2 ) وهذا صحيح ، لذلك تم إنشاء (P (1) ). الآن حالة الاستقراء. افترض أن (P (k) ) صحيح لبعض التعسفي الثابت (k ge 1 text <.> ) أي ، (1 + 3 + 5 + cdots + (2k-1) = k ^ 2 text <.> ) سنثبت الآن أن (P (k + 1) ) صحيح أيضًا (أي أن (1 + 3 + 5 + cdots + (2k + 1) = (k +1) ^ 2 )). نبدأ بالجانب الأيسر من (P (k + 1) ) ونعمل على الجانب الأيمن:

يبدأ 1 + 3 + 5 + cdots + (2k-1) + (2k + 1)

amp = k ^ 2 + (2k + 1) amp text amp = (ك + 1) ^ 2 أمبير نص نهاية

وبالتالي ، فإن (P (k + 1) ) ثابت ، لذلك وفقًا لمبدأ الاستقراء الرياضي ، يكون (P (n) ) صحيحًا للجميع (n ge 1 text <.> )

أثبت أن (F_0 + F_2 + F_4 + cdots + F_ <2n> = F_ <2n + 1> - 1 ) حيث (F_n ) هو (n ) رقم فيبوناتشي.

دليل

لنفترض أن (P (n) ) هو البيان (F_0 + F_2 + F_4 + cdots + F_ <2n> = F_ <2n + 1> - 1 text <.> ) سوف نوضح ذلك (P (n) ) صحيح للجميع (n ge 0 text <.> ) أولاً ، الحالة الأساسية سهلة لأن (F_0 = 0 ) و (F_1 = 1 ) لذا (F_0 = F_1 - 1 نص <.> ) فكر الآن في الحالة الاستقرائية. افترض أن (P (k) ) صحيح ، أي افترض (F_0 + F_2 + F_4 + cdots + F_ <2k> = F_ <2k + 1> - 1 text <.> ) لتأسيس (P (k + 1) ) نعمل من اليسار إلى اليمين:

يبدأ F_0 + F_2 + cdots + F_ <2k> + F_

amp = F_ <2k + 1> - 1 + F_ <2k + 2> amp text amp = F_ <2k + 1> + F_ <2k + 2> - 1 amp amp = F_ <2k + 3> - 1 amp text نهاية

لذلك (F_0 + F_2 + F_4 + cdots + F_ <2k + 2> = F_ <2k + 3> - 1 text <،> ) وهذا يعني (P (k + 1) ) يحمل. لذلك وفقًا لمبدأ الاستقراء الرياضي ، يكون (P (n) ) صحيحًا للجميع (n ge 0 text <.> )

أثبت أن (2 ^ n lt n! ) للجميع (n ge 4 text <.> ) (استدعاء ، (n! = 1 cdot 2 cdot 3 cdot cdots cdot n نص <.> ))

دليل

لنفترض أن (P (n) ) هي العبارة (2 ^ n lt n! text <.> ) سنظهر أن (P (n) ) صحيح للجميع (n ge 4 نص <.> ) أولاً ، نتحقق من الحالة الأساسية ونرى أن نعم ، (2 ^ 4 lt 4! ) (مثل (16 lt 24 )) لذا (P (4) ) هو حقيقية. الآن للحالة الاستقرائية. افترض أن (P (k) ) صحيح بالنسبة إلى (k ge 4 text <.> ) أي ، (2 ^ k lt k! text <.> ) فكر الآن في ( الفوسفور (ك + 1) نص <:> ) (2 ^ lt (k + 1)! text <.> ) لإثبات ذلك ، نبدأ بالجانب الأيسر ونعمل على الجانب الأيمن.

amp = 2 cdot 2 ^ k amp amp lt 2 cdot k! أمبير نص amp lt (ك + 1) cdot k! amp text <منذ> k + 1 gt 2 amp = (k + 1)! أمبير نهاية

لذلك (2 ^ lt (k + 1)! ) لذلك أنشأنا (P (k + 1) text <.> ) وبالتالي وفقًا لمبدأ الاستقراء الرياضي (P (n) ) صحيح للجميع ( n ge 4 text <.> )

يثبت بالاستقراء الرياضي أن (F_0 + F_1 + F_2 + cdots + F_ = F_ - 1 text <،> ) حيث (F_n ) هو (n ) رقم فيبوناتشي رقم ( (F_0 = 0 text <،> ) (F_1 = 1 ) و (F_n = F_ + F_)).

قام كل من Zombie Euler و Zombie Cauchy ، عالم رياضيات زومبي مشهور ، بالتسجيل للتو في حسابات Twitter. بعد يوم واحد ، أصبح لدى Zombie Cauchy متابعون أكثر من Zombie Euler. كل يوم بعد ذلك ، عدد المتابعين الجدد لـ Zombie Cauchy هو بالضبط نفس عدد المتابعين الجدد لـ Zombie Euler (ولا يفقد أي متابع). اشرح كيف يمكن لإثبات الاستقراء الرياضي أن يُظهر أنه في كل يوم بعد اليوم الأول ، سيكون لدى Zombie Cauchy متابعون أكثر من Zombie Euler. أي ، اشرح ماهية الحالة الأساسية والحالة الاستقرائية ، ولماذا يثبتان معًا أن Zombie Cauchy سيكون لديه المزيد من المتابعين في اليوم الرابع.

ابحث عن أكبر عدد من النقاط التي لا يستطيع فريق كرة القدم الحصول عليها بالضبط باستخدام أهداف ميدانية من 3 نقاط وملامسة من 7 نقاط (تجاهل احتمالات الأمان ، وضياع نقاط إضافية ، وتحويلات من نقطتين). أثبت أن إجابتك صحيحة عن طريق الاستقراء الرياضي.

أثبت أنه يمكن العثور على مجموع (n ) المربعات على النحو التالي

ما الخطأ في "الدليل" التالي على "الحقيقة" التي (n + 3 = n + 7 ) لجميع قيم (n ) (بالإضافة إلى أن الشيء الذي تدعي إثباته غير صحيح بالطبع) ؟

دليل

لنفترض أن (P (n) ) عبارة (n + 3 = n + 7 text <.> ) سنثبت أن (P (n) ) صحيح للجميع (n in N text <.> ) افترض ، للاستقراء أن (P (k) ) صحيح. أي (k + 3 = k + 7 text <.> ) يجب أن نظهر أن (P (k + 1) ) صحيح. الآن منذ (ك + 3 = ك + 7 نص <،> ) أضف 1 إلى كلا الجانبين. هذا يعطي (k + 3 + 1 = k + 7 + 1 text <.> ) إعادة التجميع ((k + 1) + 3 = (k + 1) + 7 text <.> ) لكن هذا صحيح ببساطة (P (k + 1) text <.> ) وبالتالي من خلال مبدأ الاستقراء الرياضي (P (n) ) صحيح للجميع (n in N text <.> )

المشكلة الوحيدة هي أننا لم نقم بتأسيس الحالة الأساسية. بالطبع ، عندما (n = 0 text <،> ) (0 + 3 ne 0 + 7 text <.> )

الدليل في المشكلة السابقة لا يعمل. ولكن إذا قمنا بتعديل "الحقيقة" ، فيمكننا الحصول على دليل عملي. أثبت أنه (n + 3 lt n + 7 ) لجميع قيم (n in N text <.> ) يمكنك إجراء هذا الإثبات باستخدام الجبر (بدون الاستقراء) ، ولكن الهدف من هذا التمرين هو كتابة إثبات استقرائي صالح.

دليل

لنفترض أن (P (n) ) عبارة (n + 3 lt n + 7 text <.> ) سنثبت أن (P (n) ) صحيح للجميع (n ) في N text <.> ) أولاً ، لاحظ أن الحالة الأساسية تحمل: (0 + 3 lt 0 + 7 text <.> ) افترض الآن أن الاستقراء (P (k) ) هو حقيقية. أي (k + 3 lt k + 7 text <.> ) يجب أن نظهر أن (P (k + 1) ) صحيح. الآن منذ (k + 3 lt k + 7 text <،> ) أضف 1 إلى كلا الجانبين. هذا يعطي (k + 3 + 1 lt k + 7 + 1 text <.> ) إعادة التجميع ((k + 1) + 3 lt (k + 1) + 7 text <.> ) لكن هذا ببساطة (P (k + 1) text <.> ) وبالتالي من خلال مبدأ الاستقراء الرياضي (P (n) ) صحيح للجميع (n in N text <.> )

ابحث عن الخلل في "الدليل" التالي على "الحقيقة" التي (n lt 100 ) لكل (n in N text <.> )

دليل

لنفترض أن (P (n) ) هو البيان (n lt 100 text <.> ) سنثبت أن (P (n) ) صحيح للجميع (n in N text < .> ) أولاً نؤسس الحالة الأساسية: عندما يكون (n = 0 text <،> ) (P (n) ) صحيحًا ، لأن (0 lt 100 text <.> ) الآن بالنسبة للخطوة الاستقرائية ، افترض أن (P (k) ) صحيح. هذا هو (k lt 100 text <.> ) الآن إذا كان (k lt 100 text <،> ) ثم (k ) هو رقم ما ، مثل 80. بالطبع (80+ 1 = 81 ) وهي لا تزال أقل من 100. لذا (ك +1 لتر 100 ) أيضًا. لكن هذا ما يدعي (P (k + 1) ) ، لذلك أظهرنا أن (P (k) imp P (k + 1) text <.> ) وبالتالي من خلال مبدأ الاستقراء الرياضي ، (P (n) ) صحيح للجميع (n in N text <.> )

المشكلة هنا هي أنه بينما (P (0) ) صحيح ، بينما (P (k) imp P (k + 1) ) لـ بعض قيم (k text <،> ) هناك قيمة واحدة على الأقل لـ (k ) (أي (k = 99 )) عندما يفشل هذا الضمني. للحصول على دليل صالح عن طريق الاستقراء ، يجب أن يكون (P (k) imp P (k + 1) ) صحيحًا لجميع قيم (k ) أكبر من أو تساوي الحالة الأساسية.

في حين أن الدليل أعلاه لا يعمل (من الأفضل ألا يكون البيان الذي يحاول إثباته خاطئ!) يمكننا إثبات شيء مشابه. إثبات وجود تسلسل متزايد بشكل صارم (a_1، a_2، a_3، ldots ) ​​من الأرقام (ليس بالضرورة أعدادًا صحيحة) بحيث (a_n lt 100 ) للجميع (n in N text <. > ) (ونعني (a_n lt a_)) للجميع (n text <.> ) لذلك يجب أن يكون كل مصطلح أكبر من الأخير.)

دليل

لنفترض أن (P (n) ) عبارة "هناك تسلسل متزايد بشكل صارم (a_1، a_2، ldots، a_n ) مع (a_n lt 100 text <.> )" سوف نثبت (P (n) ) صحيح للجميع (n ge 1 text <.> ) أولاً نؤسس الحالة الأساسية: (P (1) ) يقول أن هناك رقمًا واحدًا (a_1 ) مع (a_1 lt 100 text <.> ) هذا صحيح - خذ (a_1 = 0 text <.> ) الآن بالنسبة للخطوة الاستقرائية ، افترض أن (P (k) ) صحيح. يوجد تسلسل متزايد بشكل صارم (a_1، a_2، a_3، ldots، a_k ) مع (a_k lt 100 text <.> ) الآن ضع في اعتبارك هذا التسلسل ، بالإضافة إلى مصطلح آخر ، (a_) وهو أكبر من (a_k ) ولكنه أقل من (100 نص <.> ) مثل هذا الرقم موجود ، على سبيل المثال ، المتوسط ​​بين (a_k ) و 100. إذن إذن (P (k) +1) ) صحيح ، لذا فقد أظهرنا أن (P (k) imp P (k + 1) text <.> ) وبالتالي وفقًا لمبدأ الاستقراء الرياضي ، (P (n) ) ينطبق على الكل (n in N text <.> )

ما الخطأ في "الإثبات" التالي "للحقيقة" أنه بالنسبة للجميع (n in N text <،> ) الرقم (n ^ 2 + n ) فردي؟

دليل

لنفترض أن (P (n) ) عبارة " (n ^ 2 + n ) غريبة." سنثبت أن (P (n) ) صحيح للجميع (n in N text <.> ) افترض للحث أن (P (k) ) صحيح ، أي أن (k ^ 2 + k ) غريب. الآن ضع في اعتبارك العبارة (P (k + 1) text <.> ) Now ((k + 1) ^ 2 + (k + 1) = k ^ 2 + 2k + 1 + k + 1 = k ^ 2 + k + 2k + 2 text <.> ) من خلال الفرضية الاستقرائية ، (k ^ 2 + k ) غريب ، وبالطبع (2k + 2 ) زوجي. الفردي زائد الزوج دائمًا أمر فردي ، لذا فإن ((k + 1) ^ 2 + (k + 1) ) هو أمر فردي. لذلك وفقًا لمبدأ الاستقراء الرياضي ، يكون (P (n) ) صحيحًا للجميع (n in N text <.> )

قدم الآن إثباتًا صالحًا (عن طريق الاستقراء ، على الرغم من أنك قد تكون قادرًا على القيام بذلك دون استخدام الاستقراء) للبيان ، "لجميع (n in N text <،> ) الرقم (n ^ 2 + n ) زوجي ".

إثبات وجود تسلسل من الأرقام الحقيقية الموجبة (a_0، a_1، a_2، ldots ) ​​بحيث يكون المجموع الجزئي (a_0 + a_1 + a_2 + cdots + a_n ) أقل بدقة من (2 ) للجميع (n in N text <.> ) تلميح: فكر في كيفية تحديد ماذا (a_) هو جعل حجة الاستقراء تعمل.

الفكرة هي تحديد التسلسل بحيث يكون (a_n ) أقل من المسافة بين المجموع الجزئي السابق و 2. بهذه الطريقة عندما تضيفه إلى المجموع الجزئي التالي ، لا يزال المجموع الجزئي أقل من 2. يمكنك قم بذلك مسبقًا ، أو استخدم (P (n) ) ذكيًا في إثبات الاستقراء.

دليل

لنفترض أن (P (n) ) هي العبارة ، "هناك سلسلة من الأرقام الحقيقية الموجبة (a_0، a_1، a_2، ldots، a_n ) بحيث (a_0 + a_1 + a_2 + cdots + a_n lt 2 text <.> ) "

الحالة الأساسية: اختر أي (a_0 lt 2 text <.> )

الحالة الاستقرائية: افترض أن (a_1 + a_2 + cdots + a_k lt 2 text <.> ) دعنا الآن (a_ = frac <2- a_1 + a_2 + cdots + a_k> <2> text <.> ) ثم (a_1 + a_2 + cdots + a_k + a_ lt 2 نص <.> )

لذلك ، وفقًا لمبدأ الاستقراء الرياضي ، (P (n) ) صحيح للجميع (n in N )

أثبت أن كل عدد صحيح موجب هو إما أس 2 ، أو يمكن كتابته كمجموع قوى مميزة لـ 2.

والدليل عن طريق الاستقراء القوي.

دليل

لنفترض أن (P (n) ) عبارة " (n ) إما أن تكون قوة 2 أو يمكن كتابتها كمجموع قوى مميزة لـ 2." سنوضح أن (P (n) ) صحيح للجميع (n ge 1 text <.> )

الحالة الأساسية: (1 = 2 ^ 0 ) هي أس 2 ، لذا فإن (P (1) ) صحيح.

الحالة الاستقرائية: لنفترض أن (P (k) ) صحيح للجميع (k lt n text <.> ) الآن إذا كان (n ) قوة 2 ، فقد انتهينا. إذا لم يكن الأمر كذلك ، فلنجعل (2 ^ x ) أكبر قوة لـ 2 أقل بدقة من (n text <.> ) ضع في اعتبارك (n - 2 ^ x text <،> ) وهو رقم أصغر ، في الواقع أصغر من كليهما (n ) و (2 ^ x نص <.> ) وبالتالي (n-2 ^ x ) إما أن تكون قوة 2 أو يمكن كتابتها كمجموع قوى مميزة من 2 ، لكن لن يكون أي منها (2 ^ x text <،> ) لذا فقد كتبنا مع (2 ^ x ) كمجموع قوى مميزة لـ 2 .

لذلك ، وفقًا لمبدأ الاستقراء الرياضي (القوي) ، يكون (P (n) ) صحيحًا للجميع (n ge 1 text <.> )

أثبت ، باستخدام الاستقراء القوي ، أن كل رقم طبيعي هو إما رقم فيبوناتشي أو يمكن كتابته كـ مجموع من خامد أرقام فيبوناتشي.

استخدم الاستقراء لإثبات أنه إذا (n ) تصافح جميع الأشخاص مع بعضهم البعض ، فإن العدد الإجمالي للمصافحة هو ( frac<2> نص <.> )

لاحظ ، لقد أثبتنا ذلك بالفعل دون استخدام الحث ، لكن النظر إليه يلقي الضوء على المشكلة (وهو أمر ممتع).

دليل

لنفترض أن (P (n) ) عبارة "عندما (n ) يصافح الناس بعضهم البعض ، يكون هناك إجمالي ( frac<2> ) المصافحة. "

الحالة الأساسية: عندما (n = 2 text <،> ) سيكون هناك مصافحة واحدة ، و ( frac <2 (2-1)> <2> = 1 text <.> ) وهكذا ( P (2) ) صحيح.

الحالة الاستقرائية: افترض أن (P (k) ) صحيح بالنسبة (k ge 2 ) (أن عدد المصافحة بين (k ) الأشخاص هو ( frac<2> text <.> ) ماذا يحدث إذا ظهر (k + 1 ) شخص ما؟ كم العدد الجديد المصافحة تحدث؟ يجب على الشخص الجديد أن يصافح الجميع هناك ، وهي (ك ) مصافحة جديدة. إذن المجموع الآن ( frac <2> + k = frac <(k + 1) k> <2> text <،> ) حسب الحاجة.

لذلك ، وفقًا لمبدأ الاستقراء الرياضي ، (P (n) ) صحيح للجميع (n ge 2 text <.> )

افترض أن عددًا حقيقيًا معينًا (x ) له خاصية (x + frac <1>) عدد صحيح. أثبت أن (x ^ n + frac <1>) عدد صحيح لجميع الأعداد الطبيعية (n text <.> )

عندما (n = 0 text <،> ) نحصل على (x ^ 0 + frac <1> = 2 ) ومتى (n = 1 نص <،> ) (س + فارك <1>) عدد صحيح ، لذا فإن الحالة الأساسية تحمل. افترض الآن أن النتيجة صحيحة لجميع الأعداد الطبيعية (n lt k text <.> ) على وجه الخصوص ، نعلم أن (x ^ + فارك <1><>> ) و (x + frac <1>) كلاهما عدد صحيح. وبالتالي فإن منتجهم هو أيضًا عدد صحيح. لكن،

لاحظ أيضًا أن (x ^ + فارك <1><>> ) هو عدد صحيح من خلال فرضية الاستقراء ، لذلك يمكننا أن نستنتج أن (x ^ k + frac <1>) عدد صحيح.

استخدم الاستقراء لإثبات أن ( d sum_^ ن = 2 ^ n text <.> ) وهذا يعني أن مجموع (n ) الصف الرابع من مثلث باسكال هو (2 ^ n text <.> )

استخدم الاستقراء لإثبات (<4 اختر 0> + <5 اختر 1> + <6 اختر 2> + cdots + <4 + n اختر n> = <5 + n اختر n> text < .> ) (هذا مثال على نظرية عصا الهوكي.)

استخدم قاعدة المنتج للوغاريتمات ( ( log (ab) = log (a) + log (b) )) لإثبات ، من خلال الاستقراء على (n text <،> ) أن ( log (a ^ n) = n log (a) text <،> ) لجميع الأعداد الطبيعية (n ge 2 text <.> )

الفكرة هنا هي أنه إذا أخذنا لوغاريتم (a ^ n text <،> ) فيمكننا زيادة (n ) بمقدار 1 إذا ضربناه بآخر (a ) (داخل اللوغاريتم). ينتج عن هذا إضافة 1 ( log (a) ) إلى الإجمالي.

دليل

لنفترض أن (P (n) ) هي العبارة ( log (a ^ n) = n log (a) text <.> ) الحالة الأساسية ، (P (2) ) صحيحة ، لأن ( log (a ^ 2) = log (a cdot a) = log (a) + log (a) = 2 log (a) text <،> ) بواسطة قاعدة المنتج لـ اللوغاريتمات. افترض الآن ، من أجل الاستقراء ، أن (P (k) ) صحيح. بمعنى ، ( log (a ^ k) = k log (a) text <.> ) ضع في اعتبارك ( log (a ^) نص <.> ) لدينا

يبدأ سجل (أ ^) = log (a ^ k cdot a) = log (a ^ k) + log (a) = k log (a) + log (a) end

مع المساواة الأخيرة بسبب الفرضية الاستقرائية. لكن هذا يبسط إلى ((k + 1) log (a) text <،> ) إنشاء (P (k + 1) text <.> ) لذلك وفقًا لمبدأ الاستقراء الرياضي ، (P (n) ) صحيح للجميع (n ge 2 text <.> )

لنفترض أن (f_1، f_2، ldots، f_n ) وظائف قابلة للتفاضل. يثبت ذلك باستخدام الاستقراء

يبدأ (f_1 + f_2 + cdots + f_n) '= f_1' + f_2 '+ cdots + f_n' end

قد تفترض ((f + g) '= f' + g ') لأية وظائف قابلة للتفاضل (f ) و (g text <.> )

يُسمح لك بتولي الحالة الأساسية. بالنسبة للحالة الاستقرائية ، قم بتجميع الكل ما عدا الدالة الأخيرة معًا كمجموع واحد من الوظائف ، ثم طبق المجموع المعتاد لقاعدة المشتقات ، ثم فرضية الاستقراء.

افترض أن (f_1، f_2، ldots، f_n ) وظائف قابلة للتفاضل. استخدم الاستقراء الرياضي لإثبات قاعدة المنتج المعممة:

يبدأ (f_1 f_2 f_3 cdots f_n) '= f_1' f_2 f_3 cdots f_n + f_1 f_2 'f_3 cdots f_n + f_1 f_2 f_3' cdots f_n + cdots + f_1 f_2 f_3 cdots f_n ' end

قد تفترض أن قاعدة المنتج لوظيفتين صحيحة.

بالنسبة للخطوة الاستقرائية ، نعرف من خلال قاعدة حاصل الضرب لوظيفتين ذلك

يبدأ (f_1f_2f_3 cdots f_k f_) '= (f_1f_2f_3 cdots f_k)' f_ + (f_1f_2f_3 cdots f_k) f_' نهاية


سأكتب المعادلات في $ mathbb_ <17> $ ، وهو حقل ، لأن $ 17 $ عدد أولي ، لذلك ينطبق الجبر الخطي: $ 2x + 3y = 0 $ معادلة خطية لمتغيرين ، وتسعى لإثبات أنها تعني $ 9x + 5y = 0 $ مما يعني أنهما يعتمدان خطيًا. تعتمد معادلتان خطيًا إذا وفقط إذا كانت إحداهما من مضاعفات الأخرى - ويجب أن يكون من السهل إثبات ذلك.

تحرير: نظرًا لأنك سألت عن استراتيجية الإثبات ، أود التأكيد على أن هذه ليست خدعة عشوائية ، فالشرط $ p | x $ ليس لطيفًا جدًا للعمل معه جبريًا ، ولكن لأن $ mathbb_p $ حقل ، العبارة المكافئة $ x equiv 0 mod p $ (لقد حذفت $ mod 17 $ و $ equiv $ أعلاه لجعلها تبدو أشبه بالجبر المألوف) هي أبسط وأفضل بكثير ، لأن يمكنك الضرب وإضافة وإنشاء مسافات خطية على $ mathbb_p $ التي تتصرف (من نواحٍ عديدة) مثل الأرقام الحقيقية.

$ begingroup $ في الواقع ، أفضلية مشاهدة $ mathbb_ <17> $ كحقل ومعرفة & amp ؛ مثل الجبر الخطي يحمل في حقل & quot ؛ ليست هناك حاجة لهذه المشكلة ، وبالتالي تعليقي. معالجة المعادلات جبريًا في $ mathbb_

لا يزال $ لا يوضح إستراتيجية الإثبات ، نظرًا لأن OP قد لا يزال ليس ما هو الحقل. كما ذكرت ، فإن أكبر عنصر هنا هو ملاحظة أن $ 9x + 5y = 17 (x + y) - 4 (2x + 3y) $. $ endgroup $ & ndash JavaMan 26 فبراير 2013 الساعة 15:45


3.1: البراهين المباشرة - الرياضيات

القسم 1.4- طرق إثبات Bacic I- إثبات مباشر وإثبات بالحالات وإثبات من خلال العمل للخلف

سنقدم في هذا القسم أنواعًا أو طرقًا محددة لإثبات البيانات الرياضية. وهي تشمل الإثبات المباشر ، والإثبات بالحالات ، والإثبات بالعمل للخلف. سوف نستخدم الحقائق المعروفة التالية:

    • 1. عدد صحيح حتى لو لبعض الأعداد الصحيحة.
    • 2. عدد صحيح غريب إذا كان لبعض عدد صحيح.
    • 3. عدد صحيح يقسم عددًا صحيحًا ، مكتوبًا ، إذا كان لبعض الأعداد الصحيحة. ملاحظة: هذا التعريف ينطبق فقط على الأعداد الصحيحة.
    • 4. العدد الطبيعي (عدد صحيح موجب) هو عدد أولي إذا كانت عوامل عددها الطبيعي هي و. ترين
    • 5. يتم تحديد القيمة المطلقة للرقم الحقيقي ، المكتوب ، بالطريقة التالية: إذا.
      • 1. ابدأ ببيان مكتوب واضح للحقائق أو الافتراضات المعينة.
      • 2. بعد ذلك ، قدم بيانًا مكتوبًا واضحًا لما سيتم إثباته.
      • 3. ثم اكتب متن البرهان ، سلسلة من الخطوات المنطقية أو النتائج التي تؤدي إلى النتيجة المرجوة. قدم تعليلاً أو إثباتًا واضحًا لكل خطوة في الإثبات. هذه هي القاعدة العامة الجيدة. تعامل مع كل دليل تكتبه على أنه تمرين كتابي بالإضافة إلى تمرين رياضي. تذكر أنك تحاول إقناع القارئ بصحة دليلك من خلال وضوح وبساطة منظمتك والتفكير المنطقي. أنهِ إثباتك ببيان واضح بما يجب إثباته. (يتم إغلاق العديد من الأدلة بالحروف QED. يشير هذا إلى الكلمة اللاتينية "quod estonstratum" ، والتي تعني تقريبًا "التي تم إثباتها أو إثباتها".) يجب تجنب الاختصارات في البراهين في هذه المرحلة. كتابة المزيد من التفاصيل أفضل لمن يتعلم فقط كيفية كتابة البراهين.

      الدليل: افترض أن و. وهكذا وبالنسبة لبعض الاعداد الصحيحة و. أظهر ذلك ، أي إظهار ذلك لبعض الأعداد الصحيحة. ثم

      هنا مثال آخر على الدليل المباشر.

      : إثبات أنه إذا كان زوجيًا وغريبًا ، فهذا غريب.

      الدليل: افترض أنه زوجي وغريب. وهكذا وبالنسبة لبعض الاعداد الصحيحة و. أظهر أن هذا غريب ، أي أظهر ذلك لبعض الأعداد الصحيحة. ثم

      أين هو عدد صحيح. وبالتالي ، هذا أمر غريب.

        • 1. ابدأ ببيان مكتوب واضح للحقائق أو الافتراضات المعينة.
        • 2. قدم بعد ذلك بيانًا مكتوبًا واضحًا لما سيتم إثباته.
        • 3. حدد الآن جميع الحالات الممكنة التي يجب أخذها في الاعتبار من أجل إثبات البيان الرياضي.
        • 4. ثم اكتب جسم الإثبات. لكل حالة ، يجب أن يتضمن ذلك سلسلة من الخطوات المنطقية أو النتائج التي تؤدي إلى النتيجة المرجوة. قدم تعليلاً أو إثباتًا واضحًا لكل خطوة في الإثبات. هذه هي القاعدة العامة الجيدة. تعامل مع كل دليل تكتبه على أنه تمرين كتابي بالإضافة إلى تمرين رياضي. تذكر أنك تحاول إقناع القارئ بصحة دليلك من خلال وضوح وبساطة منظمتك والتفكير المنطقي. أنهِ إثباتك ببيان واضح بما يجب إثباته. يجب تجنب الاختصارات في البراهين في هذه المرحلة. كتابة المزيد من التفاصيل أفضل لمن يتعلم فقط كيفية كتابة البراهين.

        : إثبات أنه إذا كانت الأرقام حقيقية ، فأين ، إذن.

        الدليل: افترض أن و هي أرقام حقيقية و. اظهر ذلك . سننظر في الحالات التالية.

        : افترض ذلك و ، بحيث. ثم و .

        : افترض ذلك و ، بحيث. ثم و .

        : افترض ذلك و ، بحيث. ثم و .

        : افترض ذلك و ، بحيث يكون 0 $ ->. ثم و .

        وهكذا ، بالنسبة لجميع الحالات الممكنة ، فقد ثبت ذلك.

        هنا مثال آخر على الإثبات بالحالات.

        : إثبات ذلك لجميع الأرقام الحقيقية.

        الدليل: افترض أن هذا رقم حقيقي. اظهر ذلك . سننظر في الحالات التالية.


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

        توماس هوبز
        ليفياثان، الفصل. 46
        كلاسيكيات البطريق ، 1982


        3.1: البراهين المباشرة - الرياضيات

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

        يتم إثبات بيان الوجود بإحدى طريقتين. إحدى الطرق هي بناء وعرض الأشياء التي يفترض وجودها بيان الوجود. وهذا ما يسمى البرهان البناء ، وهو طريقة إثبات. على سبيل المثال ، بالنظر إلى رقمين منطقيين a و b ، يمكننا اعتبار الرقم (a + b) / 2 ونوضح أنه منطقي ويقع بين a و b - وبالتالي قمنا ببناء رقم منطقي يقع بين أي رقمين منطقيين. من الواضح أن الإنشاءات لبعض بيانات الوجود يمكن أن تكون صعبة وهناك بيانات وجود لا تعرف الإنشاءات الخاصة بها.

        الطريقة الثانية لإثبات بيان الوجود هي إثبات أن الأشياء المعنية يجب أن تكون موجودة. هذا دليل غير بناء. ومن الأمثلة الشهيرة على ذلك دليل كانتور على عدم قابلية الأرقام الحقيقية للعدد. بالاقتران مع إثباته لقابلية الأرقام للأعداد المنطقية ، فإنه يثبت وجود أعداد غير منطقية دون تكوين أي عدد غير منطقي.

        تُستخدم البراهين غير البناءة أيضًا لإثبات العبارات بخلاف بيانات الوجود. في الواقع ، هذه هي البراهين المستخدمة لإثبات البيانات بخلاف بيانات الوجود. إليكم ملخص لما ناقشناه حتى الآن:
        هناك نوعان من البراهين - البناءة وغير البناءة. الاستخدام الوحيد للبراهين البناءة هو إثبات بيانات الوجود وأحيانًا يكون من الصعب جدًا العثور على دليل بناء لبيان وجود معين. تُستخدم البراهين غير البناءة في إثبات العبارات بخلاف بيانات الوجود ، كما تُستخدم أحيانًا لإثبات بيانات الوجود.

        سيكون ما تبقى من هذه المناقشة حول البراهين غير البناءة. هناك نوعان من البراهين غير البناءة: مباشر إثبات و غير مباشر دليل. قبل أن نناقش هذه ، سنشرح تقنية تسمى "الدليل الشرطي" والتي يمكن استخدامها في كل من البراهين المباشرة وغير المباشرة. نظرًا لأن الدليل الشرطي قابل للتطبيق في أي دليل ، فإننا نعتبره قاعدة استنتاج "خاصة". تنشأ هذه القاعدة من نظرية في منطق الاقتراح ، تسمى نظرية الاستنتاج.

        نوصي الطلاب الأصغر سنًا بقراءة هذه الصفحة في المرة الأولى لأخذ استراحة هنا والعودة في يوم مختلف.

        نظرية الاستنتاج
        إذا كان من مجموعة wffs G يمكننا اشتقاق q من p1، ص2، & # 8943 صن، ثم يمكننا اشتقاق (صن & rArr q) من p1، ص2، & # 8943 صن -1 وج.

        نستخدم الترميز القياسي p1، ص2 & # 8866 q ليقول إن q مشتق من p1 و ص2. تقول نظرية الاستنتاج أنه إذا كان p1، ص2 & # 8866 q ، ثم ص1 & rArr (ص2 & rArr ف).

        تبرر نظرية الاستنتاج التقنية المعروفة باسم قاعدة إثبات شرطي (CP). لإثبات أن q & rArr r في سطر إثبات ، نقدم مؤقتًا الفرضية q وإذا تمكنا الآن من إثبات r ، فعندئذٍ من خلال نظرية الاستنتاج ، أثبتنا q & rArr r ويمكن تفريغ الافتراض q من الاستخدام الإضافي في المتبقي جزء من الإثبات. يطلق عليه الدليل الشرطي ، لأننا لم نثبت حقيقة r ، فقد أثبتنا فقط أنه إذا كانت q صحيحة ، فإن r تكون صحيحة. يظهر أن r صحيح بشرط أن يكون q صحيحًا. أي أن r صحيح بشرط أن يكون q صحيحًا.

        دليل مباشر
        يحتوي كل دليل استنتاجي مباشر على هذا النموذج: افترض صحة فرضية p ثم قم بتأسيس p & rArr q بحيث يكون q ، بواسطة Modus Ponens ، صحيحًا. العمل في هذا الدليل إذن هو إنشاء p & rArr q ، والذي غالبًا ما يتطلب العديد من الخطوات: p & rArr q1 & rArr q2 & rArr & # 8943 فن & rArr q. وفقًا لقاعدة القياس المنطقي الافتراضي ، ثم p & rArr q. الدليل المباشر هو الطريقة المفضلة للإثبات غير البناء.

        الدليل المباشر بخطوات عديدة يشبه عبور مجرى مائي عن طريق الدوس على نتوءات متدرجة في الماء.

        مثال:
        إذا كان a و b عددًا صحيحًا يحتوي على b & # 185 0 و q و r هما عددان صحيحان غير سالبين بحيث يكون a = bq + r ،
        ثم gcd (a، b) & le gcd (b، r).
        (gcd (a، b) تعني القاسم المشترك الأكبر بين a و b. على سبيل المثال gcd (4،6) = 2.)
        هنا الافتراض هو: a و b عدد صحيح مع b & # 185 0 و q و r أعداد صحيحة غير سالبة مثل a = bq + r. الاستنتاج هو gcd (a، b) & le gcd (b، r). أولا قمنا بإعداد المشكلة. نسأل ، ما الذي نحتاج إلى إظهاره لتأسيس gcd (a، b) & le gcd (b، r)؟ حسنًا ، إذا تمكنا من إظهار أن أي قاسم مشترك لـ a و b هو أيضًا قاسم مشترك لـ b و r ، فإن القاسم المشترك الأكبر (الأكبر) لـ a و b سيكون قاسمًا مشتركًا لـ b و r. نظرًا لأن أي مقسوم مشترك لـ b و r لا يمكن أن يتجاوز gcd (b ، r) ، فسننتهي. لذلك فإن الدليل يذهب هكذا.

        (لاحظ أن الخطوات الثلاث الأولى في البرهان تشكل إعدادًا للإثبات. في الخطوة الرابعة لدينا فرضية الإثبات. ثم انتقلنا من خطوة إلى أخرى باستخدام قواعد الحساب والمنطق. في الخطوة الأخيرة ، قمنا استخدم قاعدة أن (X & rArr Y). (X & rArr Z) & rArr (X & rArr YZ). لذلك ترى ، إثبات نظرية في فرع الرياضيات يستخدم القواعد والتعريفات والبديهيات ونظريات ذلك الفرع من الرياضيات مع قواعد المنطق.
        بالمناسبة ، يمكن للمرء أن يثبت بالمثل أن gcd (b، r) & le gcd (a، b). قد يعني ذلك gcd (a، b) = gcd (b، r) ، وهو المبدأ الكامن وراء الخوارزمية الإقليدية.)

        غالبًا ما يتم إنشاء p & rArr q في المواقف التي تكون فيها q عبارة تحمل جميع الأعداد الطبيعية الأكبر من أو تساوي رقمًا طبيعيًا محددًا بواسطة طريقة تسمى الاستقراء الرياضي (MI). MI هي طريقة إثبات مباشر.

        الاستراحة الموصى بها: العودة لقراءة يوم آخر!

        إثبات غير مباشر
        يسمى الدليل غير المباشر لأنه ، في ذلك ، لإنشاء p & rArr q ، نبدأ به

        ف. يمكن أن تتخذ البراهين غير المباشرة ثلاثة أشكال.
        1. إثبات غير مباشر بالتناقض
        المانع أو المضاد لـ p & rArr q هو

        ص. سيوضح جدول الحقيقة أن (p & rArr q) & hArr (

        ع). أي عندما يكون p & rArr q صحيحًا ،

        تم إنشاء p ، تم إنشاء p & rArr q ، وبما أن p هي المقدمة ومن ثم يُفترض أنها صحيحة ، فإن q سيكون صحيحًا بواسطة Modus Ponens. هذا دليل على العكس. فلماذا استخدام دليل مخالف عندما يكون معادلاً لإثبات p & rArr q؟ والسبب هو أنه في بعض الحالات ،

        قد تحتوي q على معلومات أكثر من p وقد يكون من الأسهل تأسيسها

        مثال:
        لأي رئيس p ، إذا كان p يقسم n 2 ، فإن p يقسم n.

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

        2. إثبات غير مباشر بالتناقض (من المقدمة)
        إذا كان p و

        p ، ثم نستنتج أن p & rArr q. السبب وراء هذه الحجة هو ما يلي: (p & rArr q) & hArr (

        ف) ، بواسطة De Morgan Rule. هذا يعني نفي & quotIf p ، فإن q & quot هو & quotp صحيحًا و q خطأ & quot لذا ، لإعطاء دليل من خلال تناقض & quotIf p ، ثم q ، & quot نفترض أن p صحيح و q خطأ واشتقاق

        ص. من هذا نستنتج - انظر نظرية RAA أدناه - أن نفي "p صحيح و q خطأ" ، أي أن p & rArr q صحيح.

        3. إثبات غير مباشر بواسطة Reductio Ad Absurdum (RAA)
        في Reductio Ad Absurdum ، والذي يعني اختزال اللامعقول ، نبدأ مرة أخرى بـ p و

        ف ، ولكن ليس من الضروري الوصول الآن إلى

        يكفي التوصل إلى أي تناقض. لاحظ أن p وكذلك

        ص هو تناقض أيضا. لذا ، فإن إثبات التناقض (للمقدمة) هو دليل على اختزال الإعلان. هذا هو السبب في أن العديد من علماء الرياضيات غالبًا ما يطلقون على الدليل بالتناقض (للمقدمة) دليل الاختزال Ad Absurdum. ومع ذلك ، يمكنك أن ترى بسهولة أنه ليس كل دليل على Reductio Ad Absurdum هو إثبات بالتناقض ، بالمعنى الذي وصفناه أعلاه. نوصي بأن يكون إثبات التناقض واحدًا يبدأ بحرف p و

        q وينتهي الأمر بالحصول على نفي الفرضية ، وأن إثبات الاختزال Ad Absurdum هو الذي ينتهي بالحصول على أي تناقض مع حقيقة معروفة.

        الاستراحة الموصى بها: العودة لقراءة يوم آخر!

        هنا دليل رسمي على أن RAA هي نظرية في منطق الاقتراح. تبرر هذه النظرية أيضًا الدليل غير المباشر بالتناقض. يتم شرح الخطوات بعد الإثبات.

        نظرية (RAA):
        افترض أن p و q مثل أن p و

        q معًا تشير إلى تناقض ، ثم p & rArr q.

        ف[مقدمة ، إثبات مشروط] (3) ص

        تشير الأرقام الموجودة بين قوسين في العمود الأيسر إلى الترتيب العددي للخطوات. الوصف الوارد بين قوسين مربعين في العمود الأيمن يعطي المنطق المستخدم للحصول على الإدخال في العمود الأوسط. في الخطوة (1) نفترض p كمقدمة. في الخطوة (2) استخدمنا قاعدة الدليل الشرطي لتقديم فرضية جديدة

        ف. تحصل الخطوة (3) على تناقض باستخدام p أيضًا - يتم شرح ذلك على أنه خطوة RAA.تستخدم الخطوة (4) نظرية الاستنتاج أنه إذا كان بإمكاننا اشتقاق شيء ما ، على سبيل المثال X ، من p و

        q & rArr X من p وحده. عند هذه النقطة يحدث شيء غير عادي. هذا هو،

        q يقفز من كونه في سابقة الشرط في الخطوة السابقة إلى الجزء التالي في الخطوة الحالية. هذا يعنى

        لم يعد q فرضية. يقال أنه تم "إبراء الذمة" من كونه فرضية. لم يعد من الممكن اعتبار المبنى الذي تم تفريغه كمقدمة حتى لو ظهر مرة أخرى في السابق في خطوة لاحقة. تستخدم الخطوة (5) Modus Ponens (MP) في الخطوتين 1 و 4. الخطوة (6) هي الحشو (T) الناتج عن معادلة الشرط للخطوة (5) وما هو مضاد لها. أي (A & rArr B) & rArr (

        B & rArr A) عبارة عن حشو. الخطوة (7) واضحة. الخطوة (8) هي حشو (T) ، كونها نفي للتناقض. الخطوة (9) واضحة. الان مع

        q بعد أن تم تصريفه من كونه فرضية ، يبقى p فقط كمقدمة. تنص الخطوة (10) على أنه بعد إنشاء q في الخطوة 8 ، مع وجود p باعتباره المنطلق الوحيد المتبقي (الخطوة 1) ، لدينا p & rArr q.

        (لاحظ أننا هنا أنشأنا RAA كنظرية في منطق الاقتراح. سيكون من الضروري إثبات RAA في الإعداد الأكثر عمومية بما في ذلك المنطق الأصلي للتعامل مع جميع الأمثلة في الرياضيات. نظرية الاستنتاج العامة هي التالية: "إذا كان G هو مجموعة من الصيغ بدون متغيرات حرة ، وللبعض الصيغ ج، هناك دليل على G ،

        ج، وإذا كان هذا الدليل لا يحتوي على تطبيقات للتعميم على المتغيرات التي تحدث مجانًا في q ، فإن G & # 8866 q. "إن إثباتنا لمنطق الاقتراح سيعمل فقط على التحقق من صحة الفكرة العامة للإثبات بالتناقض.

        الآن لماذا تسمى RAA أيضًا إثباتًا غير مباشر؟ والسبب هذا: في إظهار ذلك

        q مع p يعطي تناقضًا ، نحن بالفعل نثبت ذلك

        ع ، كما في الإثبات بالمعارض. دعونا نرى لماذا هذا.

        تنص قاعدة الدليل الشرطي على أنه إذا قدمنا ​​في سطر إثبات فرضية جديدة A وحصلنا على B ، فيمكننا الاستدلال على (A & rArr B) والتفريغ A كمقدمة. نستخدم القاعدة لإظهار أنه إذا كان هناك عبارتان p و

        ف تعطي تناقضا ، إذن

        ف[فرضية] (2) ص[مقدمة ، إثبات مشروط] (3) ص

        q & # 8866 التناقض [خطوة RAA] (4)

        سؤال وجواب (تناقض p & rArr)[إثبات مشروط - يتم تفريغ p كمقدمة] (5)تناقض p & rArr[1،4 وضع Ponens] (6)

        ع & أو التناقض [5 ، قاعدة التضمين المادي] (7)

        ص[6 ، القياس المنطقي المنفصل] (8)

        في الخطوة (4) ، نستخدم قاعدة الإثبات الشرطي لإبراء الفرضية المقدمة p والحصول على (تناقض p & rArr) من

        ف. تستخدم الخطوة (6) طريقة بديلة لكتابة الضمانات المادية كفصل (انظر قواعد الاستدلال). تستخدم الخطوة (7) القياس المنطقي الذي ينص على أنه لكي يكون الانفصال صحيحًا عندما يكون أحدهما خاطئًا ، يجب أن يكون الآخر صحيحًا. الخطوة (8) تنص على أن الافتراض المقدم ص قد تم تفريغه في الخطوة (4) الافتراض الوحيد المتبقي هو

        ف ، وبما أن النتيجة هي

        ص. وبالتالي فقد أثبتنا أن مادة p & rArr q تعارضها.

        • إذا كان من الصعب التلاعب بالنتيجة أو فهمها ، لكن نفيها يوفر المزيد من المعلومات أو المواد التي يمكن العمل بها.
        • إذا كان الاستنتاج هو نفي بعض العبارات الأخرى.
        • إذا كنت بحاجة لإثبات وجود شيء واحد على الأكثر بممتلكات معينة.
        • إذا كنت بحاجة إلى إثبات عكس نظرية مثبتة بالفعل.

        مثال:
        نظرية. لا توجد حلول أعداد صحيحة موجبة للمعادلة x 2 - y 2 = 1 للأعداد الصحيحة الموجبة x و y.
        دليل. (إثبات بالتناقض.) افترض على العكس من ذلك أن هناك حلًا (x ، y) حيث x و y عددان صحيحان موجبان. إذا كانت هذه هي الحالة ، فيمكننا تحليل الجانب الأيسر: x 2 - y 2 = (xy) (x + y) = 1. نظرًا لأن x و y عددان صحيحان ، فسيتبع ذلك إما xy = 1 و x + y = 1 أو xy = -1 و x + y = -1. في الحالة الأولى ، يمكننا إضافة المعادلتين لنحصل على x = 1 و y = 0 ، بما يتعارض مع افتراضنا بأن x و y موجبان. الحالة الثانية مشابهة ، الحصول على x = -1 و y = 0 ، يتناقض مرة أخرى مع افتراضنا بواسطة RAA ، لا يوجد حل (x، y) مع الخاصية. QED
        (ملاحظة: حجة مشابهة ، لكنها أكثر تعقيدًا ، ستظهر أن xn - yn = 1 ليس لها حلول للأعداد الصحيحة الموجبة x و y و n. سأل يوجين كاتالان من شهرة الأعداد الكاتالونية عما إذا كان هذا ينطبق على المعادلة xn - ym = 1 ، حيث x و y و n و m أعداد صحيحة موجبة و n & # 185 م. ظل السؤال بدون إجابة لمدة 150 عامًا حتى حل Preda Mihailescu في عام 2002. الإجابة هي أن هناك واحدًا فقط من هذا (n، m ، x، y) الحل هو: 3 2 - 2 3 = 1.)

        الفرق بين RAA والإثبات بالمعارض هو التالي. في السابق نبدأ

        q و p ، احصل على تناقض ، واستنتج ذلك

        ص. في الأخير ، نبدأ فقط بـ

        ص. وهكذا لدينا نوعان متاحان من البراهين غير المباشرة. RAA أكثر كفاءة من الإثبات بالمعارض لأنه في محاولة التأسيس

        q و p كمباني وبالتالي يكون لدينا المزيد من المعلومات للعمل بها مقارنة بالإثبات المتعارض حيث لدينا المعلومات فقط في

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

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

        ج) دائما خطأ. يُعرف هذا الافتراض باسم قانون الوسط المستبعد. أي أن العبارة C ونفيها لا يمكن أن يكونا صحيحين في نفس الوقت. لا يقبل كل المنطقين هذا.


        التخمينات المثبتة حديثًا

        على الرغم من أن التخمينات المذكورة أعلاه لا تزال مفتوحة ، إلا أن بعض التخمينات كانت مفتوحة لفترة طويلة جدًا ، ولم يتم إثباتها إلا مؤخرًا. فيما يلي بعض الأمثلة الأكثر شهرة.

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

        نظرية الألوان الأربعة: (مقترح

        1850 ، أثبت عام 1976 بواسطة كينيث أبيل وولفغانغ هاكين)

        بالنظر إلى أي فصل من مستوى إلى مناطق متجاورة ، هناك حاجة إلى أربعة ألوان فقط لتلوين المناطق بحيث لا يكون هناك زوج من المناطق المتجاورة بنفس اللون. □ _ مربع □

        ائتمان الصورة: ويكيبيديا

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

        حدسية بوانكاريه: (تم اقتراحه عام 1904 بواسطة Henri Poincaré ، وتم إثباته عام 2002 بواسطة Grigori Perelman)

        كل 3 مشعب متصل ومغلق ببساطة هو متماثل مع الكرة 3.

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


        ساعات العمل

        هل لديك أسئلة؟ هل تريد التحدث إلينا؟ نرحب بك للتحدث إلى أي مدرب أو مساعد مساعد في الدورة. لست بحاجة إلى موعد: فقط احضر. إذا كان لديك سؤال رياضي ، فتأكد من أنك قضيت بعض الوقت في الإجابة عليه أولاً ، وكن مستعدًا لشرح ما حاولت القيام به حتى نتمكن من مساعدتك بشكل أفضل.

        من المرجح أن تتغير الأوقات من أسبوع لآخر. تحقق دائمًا من التقويم أدناه للحصول على أحدث المعلومات.

        تتوفر مساعدة إضافية من Vic Math Tutors. لديهم أيضًا ارتباط Zoom منفصل.


        تم النظر في نموذج أكثر عمومية مع كتلة (م ) من الوظائف والمتغيرات في [20]. ولكن هنا ، لتسهيل التدوين ، نركز فقط على النموذج (1.1) مع (م = 3 ) ويمكن أن يمتد التحليل إلى الحالة العامة باستخدام (م ) عام.

        Bertsekas، D.P: التحسين المقيد وطرق مضاعف لاغرانج. المطبعة الأكاديمية ، لندن (1982)

        Blum، E.، Oettli، W: Mathematische Optimierung. Grundlagen و Verfahren. Ökonometrie und Unternehmensforschung. سبرينغر ، برلين-هايدلبرغ-نيويورك (1975)

        Boyd، S.، Parikh، N.، Chu، E.، Peleato، B.، Eckstein، J: التحسين الموزع والتعلم الإحصائي عبر طريقة الاتجاه المتناوب للمضاعفات. وجدت. الاتجاهات ماخ. يتعلم. 3, 1–122 (2010)

        تشان ، تي إف ، جلوينسكي ، آر: تقريب العناصر المحدودة والحل التكراري لفئة من المعادلات الإهليلجية غير الخطية المعتدلة ، تقرير تقني. جامعة ستانفورد ، ستانفورد ، كاليفورنيا (1978)

        Chandrasekaran، V.، Parrilo، P.A.، Willsky، A.S: اختيار نموذج رسومي متغير كامن عبر تحسين محدب. آن. ستات. 40, 1935–1967 (2012)

        Eckstein، J.، Yao، W: Augmented Lagrangian and Alternative direction way for المحدب المثلى: برنامج تعليمي وبعض النتائج الحسابية التوضيحية ، مخطوطة (2012)

        Eckstein، J.، Bertsekas، D.P: On the Douglas – Rachford splitting method and the next point point algorithm for الأقرب من المشغلين الأحاديين. رياضيات. برنامج. 55, 293–318 (1992)

        Fortin، M.، Glowinski، R: حول طرق التحلل-التنسيق باستخدام لاغرانج المعزز. في: Fortin، M.، Glowinski، R. (eds.) أساليب لاغرانج المعززة: تطبيقات لحل مشاكل الحدود. شمال هولندا ، أمستردام (1983)

        غاباي ، د. ، ميرسير ، ب: خوارزمية مزدوجة لحل مشاكل التباين غير الخطية عن طريق تقريب العناصر المحدودة. حاسوب. رياضيات. تطبيق 2, 17–40 (1976)

        Glowinski ، R: الطرق العددية للمشكلات المتغيرة غير الخطية. سبرينغر ، برلين (1984)

        جلوينسكي ، آر: حول طرق التوجيه البديلة للمضاعفات: منظور تاريخي. في: وقائع Springer من مؤتمر مخصص لـ J. Periaux (يظهر)

        Glowinski، R.، Marrocco، A: Approximation par èlèments finis d’ordre un et rèsolution par pènalisation-dualitè d’une classe de problémes non linèaires. R.A.I.R.O. R2, 41–76 (1975)

        Gol’shtein، EG، Tret’yakov، N.V: تعديل لاغرانج في البرمجة المحدبة وتعميماتها. رياضيات. برنامج. دراسات 10, 86–97 (1979)

        Han ، D.R. ، Yuan ، XM: ملاحظة حول طريقة الاتجاه المتناوب للمضاعفات. J. أوبتيم. النظرية التطبيقية. 155, 227–238 (2012)

        He، BS، Tao، M.، Yuan، XM: طريقة الاتجاه المتناوب مع استبدال ظهر Gaussian للبرمجة المحدبة القابلة للفصل. SIAM J. Optim. 22, 313–340 (2012)

        He، B. S.، Tao، M.، Yuan، X. M: طريقة تقسيم للبرمجة المحدبة القابلة للفصل. IMA J. Numer. شرجي. (لتظهر)

        He، BS، Tao، M.، Yuan، XM: معدل التقارب وتعقيد التكرار على طريقة الاتجاه المتناوب للمضاعفات مع إجراء الاستبدال للبرمجة المحدبة القابلة للفصل. رياضيات. أوبرا. الدقة. (قيد المراجعة)

        هو ، BS ، يوان ، X.M: حول (O (1 / n) ) معدل التقارب لطريقة الاتجاه المتناوب دوغلاس-راشفورد. SIAM J. Num. شرجي. 50, 700–709 (2012)

        Hestenes ، M.R: طرق المضاعف والتدرج. J. أوبتيم. النظرية التطبيقية. 4, 303–320 (1969)

        Hong، M.، Luo، Z.Q: حول التقارب الخطي لطريقة الاتجاه المتناوب للمضاعفات ، مخطوطة (أغسطس 2012)

        McLachlan ، GJ: التحليل التمييزي والتعرف على الأنماط الإحصائية ، المجلد. 544- وايلي إنترساينس ، نيويورك (2004)

        Mohan، K.، London، P.، Fazel، M.، Witten، D.، Lee، S: التعلم القائم على العقدة لنماذج الرسوم البيانية الغاوسية المتعددة. arXiv: 1303.5145 (2013)

        مارتينيه ، ب: تنظيم التباينات المتباينة التقريبية المتتالية. Revue Francaise d’Informatique et de Recherche Opérationelle 4, 154–159 (1970)

        Peng، Y.G.، Ganesh، A.، Wright، J.، Xu، W.L.، Ma، Y: محاذاة قوية عن طريق تحلل متناثر ومنخفض الرتبة للصور المرتبطة خطيًا. IEEE Trans. نمط الشرج. ماخ. شركة انتل. 34, 2233–2246 (2012)

        باول ، إم جي دي: طريقة للقيود غير الخطية في مشاكل التصغير. في: Fletcher، R. (ed.) Optimization، pp.283–298. المطبعة الأكاديمية ، نيويورك (1969)

        Rockafellar ، RT: لاغرانج المعزز وتطبيقات خوارزمية النقطة القريبة في البرمجة المحدبة. رياضيات. أوبرا. الدقة. 1, 97–116 (1976)

        Tao، M.، Yuan، XM: استرداد مكونات المصفوفات منخفضة الرتبة والمتفرقة من الملاحظات غير المكتملة والصاخبة. SIAM J. Optim. 21, 57–81 (2011)

        Wen، Z.، Goldfarb، D.، Yin، W: طرق لاغرانج المعززة بالاتجاه المتناوب للبرمجة شبه المحددة. رياضيات. برنامج. حاسوب. 2, 203–230 (2010)


        أخبار وأحداث أمبير

        فيروس كورونا: أحدث الإرشادات

        مبروك للسير جون أستون

        حصل على لقب فارس لخدمات الإحصاء وصنع السياسات العامة.

        مبروك لهولي كريجر

        حصل على لقب زميل 2021-2022 في معهد هارفارد رادكليف.

        مبروك لريتشارد سامورث

        على انتخابه زميلاً في الجمعية الملكية

        تهانينا لمارك جروس وريتشارد ساموورث

        حصل على تمويل من مجلس البحوث الأوروبي

        مبروك لجون أستون

        يسعدنا أن نعلن أنه اعتبارًا من 1 يناير 2021 ، تم انتخاب جون أستون كأستاذ هاردينغ للإحصاء في الحياة العامة

        ورشة عمل على شرف جيمس نوريس & # 039 عيد ميلاد 60

        حدود التدرج: من الميكانيكا الإحصائية إلى المشعبات 5-7 سبتمبر 2022


        شاهد الفيديو: التحليل المباشر تمرين (ديسمبر 2021).