سلام
چند روزه برای درک استقرا مشکل دارم
برای یاد گیری استقرا لطفا منبعی معرفی کنید. نحوه ی حل مسائل با استقرا متوجه نمیشم. مثلا فصل اول لینز با استقرا ثابت شده |x.y|=|x|+|y| یا مخصوصا تمرینات مربوط به استقرا.ممنون میشم یک نمونه توضیح بدید
دوستان همچنان مشکلم پا برجاست!
چرا کسی یه راهنمایی کوچولو نمیده آخه
حالا حوصله توضیح نمیره حداقل یه راهنمایی توضیحی کتابی چیزی
(۲۷ خرداد ۱۳۹۴ ۰۶:۴۴ ب.ظ)pani*joon نوشته شده توسط: سلام
چند روزه برای درک استقرا مشکل دارم
برای یاد گیری استقرا لطفا منبعی معرفی کنید. نحوه ی حل مسائل با استقرا متوجه نمیشم. مثلا فصل اول لینز با استقرا ثابت شده |x.y|=|x|+|y| یا مخصوصا تمرینات مربوط به استقرا.ممنون میشم یک نمونه توضیح بدید
سلام
اصل استقرای ریاضی روشی مفیدی اغلب در اثبات یک گزاره ی ریاضی می باشد که به عنوان منبع درسی برای یادگیری می توونی به کتب گسسته مراجعه کنی. البته من اینجا یه توضیحاتی می دهم و امیدوارم مفید باشه:
- اصل استقرای ریاضی:
فرض کنید [tex]S(n)[/tex] یک گزاره ی باز (open statemet) یا مجموعه ای از این نوع گزاره های باز باشد که شامل یک یا چند مورد از متغیر n که عدد صحیح مثبتی است می باشد:
هر گاه الف) [tex]S(1)[/tex] راست بوده (گام پایه) و ب) هر گاه [tex]S(k)[/tex] به ازای هر مقدار دلخواه [tex]k\in Z^ [/tex] راست فرض کنیم، [tex]S(k 1)[/tex] نیز راست باشد (گام استقرا)، آنگاه [tex]S(n)[/tex] به ازای همه [tex]n\in Z^ [/tex] راست خواهد بود.
البته در گام پایه ضرورتی ندارد که پایه از ۱ شروع شود و آنچه لازم است این است که گزاره ی باز [tex]S(n)[/tex] به ازای عنصر اولیه ای مثل [tex]n_0\in Z^ [/tex] راست باشد تا نقطه شروعی برای استقرا باشد.
برای درک شهودی و بهتر اعتبار این روش اثبات، مهره های دومینو رو در نظر بگیر که چطور وقتی یک مهره هل داده می شود بقیه مهره ها نیز به دنبال آن و یکی یکی به مهره بعدی برخورد می کنند و همه به زمین می افتند. روش اثبات با استقرا هم دقیقاً مثل دومینو می باشد و گام پایه مثل همان هل دادن اولین مهره است که فرآیند اثبات (زمین خوردن های مهره های دومینو) را شروع می کند و گام استقرا هم مثل برخورد هر مهره به مهره بعدی خود می باشد، یعنی اگر مهره ای بیافتید ([tex]S(k)[/tex] را راست فرض کنیم) مهره ی بعدی نیز می افتد ([tex]S(k 1)[/tex] نیز راست باشد) و بنابراین اثبات برای همه مقادیر صورت گرفته است (همه مهره های در نهایت یکی یکی به زمین می افتند).
![[تصویر: 369229_bBHiC.png]](https://img.manesht.ir/369229_bBHiC.png)
سلام خیلی خوب توضیح دادید ممونم.
مثلا برای اثبات|x.y|=|x|+|y| :
فرض : طول y برابر ۱
گام پایه: اگه به رشته y یک سمبل مثل a اضافه کنیم طول رشته ۱ واحد زیاد میشه . به طول رشته y طول رشته a هم اضافه میشه که یعنی y|=|a|+1
به جای y مقدار جدید و میذاریم و الی آخر
اینطوری که فهمیدم درسته؟
برای مسائلی که میگه نشان دهید مثلا اجتماع فلان میشه هم به همین روش ادامه میدیم یا اثبات معمولی؟
(۲۹ خرداد ۱۳۹۴ ۰۴:۴۶ ب.ظ)pani*joon نوشته شده توسط: سلام خیلی خوب توضیح دادید ممونم.
مثلا برای اثبات|x.y|=|x|+|y| :
فرض : طول y برابر ۱
گام پایه: اگه به رشته y یک سمبل مثل a اضافه کنیم طول رشته ۱ واحد زیاد میشه . به طول رشته y طول رشته a هم اضافه میشه که یعنی y|=|a|+1
به جای y مقدار جدید و میذاریم و الی آخر
اینطوری که فهمیدم درسته؟
برای مسائلی که میگه نشان دهید مثلا اجتماع فلان میشه هم به همین روش ادامه میدیم یا اثبات معمولی؟
سلام. به مسئلش بستگی داره. ولی معمولاً میشه با استقرا هم حل کرد. میشه حالت اول استقرا رو تهی بودن مجموعه ها درنظر گرفت. بعد حالت اضافه شدن هر عضو رو روی مجموعه ها اعمال کرد.
ممنونم منظورتون از تعریف مسئله، تعریفیه که خودم در نظر میگیرم و براساس اون مسئله حل میشه هستش؟
(۲۹ خرداد ۱۳۹۴ ۰۶:۲۴ ب.ظ)pani*joon نوشته شده توسط: ممنونم منظورتون از تعریف مسئله، تعریفیه که خودم در نظر میگیرم و براساس اون مسئله حل میشه هستش؟
خوب یک سری از مسائل خیلی سخت با استقرا حل میشه. لزومی نداره همشون رو با استقرا حل کنیم.
جویبار شما درست میگید ولی هنوز یکم مشکل دارم.
مثلا ( دو مجموعه متاظر هستند اگر و تنها اگر قدر مطلع دو مجموعه با هم برابر باشند ) برای نشان دادن رابطه هم ارزی باید تناظر یک به یکشون رو نشان بدم یا اینکه سه خاصیت ( بازتابی ... ) ؟
یا اینکه ( اگر S۱ و S۲ دو مجموعه متناهی باشند ) برای نشان دادن اینکه اندازه اجتماع دو مجموع کمتر مساوی مجموع تعداد اعضای دو مجموعه است باید چطور اثبات کنم؟
(۳۰ خرداد ۱۳۹۴ ۰۱:۳۹ ق.ظ)pani*joon نوشته شده توسط: جویبار شما درست میگید ولی هنوز یکم مشکل دارم.
مثلا ( دو مجموعه متاظر هستند اگر و تنها اگر قدر مطلع دو مجموعه با هم برابر باشند ) برای نشان دادن رابطه هم ارزی باید تناظر یک به یکشون رو نشان بدم یا اینکه سه خاصیت ( بازتابی ... ) ؟
یا اینکه ( اگر S۱ و S۲ دو مجموعه متناهی باشند ) برای نشان دادن اینکه اندازه اجتماع دو مجموع کمتر مساوی مجموع تعداد اعضای دو مجموعه است باید چطور اثبات کنم؟
سلام. ببخشید که دیر پاسخ دادم. اولی رو میتونید با استقرا هم برید. برای حالت تهی یا یک عضوی نشون میدید رابطه برقراره. برای k عضوی فرض میکنید درسته و برای k+1 عضوی اثبات میکنید. استقرا فقط روند کار رو نشون میده. برای اثبات درستی هر مرحله باید خواص هم ارزی رو بررسی کنید. یعنی نشون دادن برقراری رابطه برای حالت ۰ یا یک عضوی با بررس خواص هم ارزیه. فرض میکنید خواص هم ارزی روی مجموعه k عضوی وجود داره و خواص هم ارزی رو روی مجموعه k+1 عضوی اثبات میکنید.
دومی هم میشه با استقرا اثبات کرد. مجموعه ها رو تهی درنظر میگیرید و میگید حالت اولیه درسته. فرض میکنید یک مجموعه a و یک مجموعه b عضویه. اندازه اجتماعشون هم مشکلی نداره. حالا یه عضو به یکی از مجموعه ها اضافه میکنید و وضعیت اجتماع رو بررسی میکنید.