تعریف استقرایی و استقرای کامل

یادآور نظریه مجموعه‌ها: قسمت ۸

درآمد به منطق و رایانش

بازگشت، استقرا، تعریف استقرایی و حل مسئله

اگر از عهده حل مسئله‌ای برنمی‌آیید، مسئله‌ای آسان‌تر هست که از عهده آن برمی‌آیید: آن را بیابید.
جرج پولیا – George Pólya ریاضیدان مجاری مولف کتاب «How to Solve It» (1887- 1985)

^≡

۱- مقدمه: بازگشت (Recursion)، تعریف بازگشتی و حل مسئله	۶- استقرای ریاضی (Mathematical induction)
۲- تعریف استقرایی ((Induction Definition)	۷- مجموعه‌های بازگشتی (Recursive sets)
۳- روش تعریف استقرایی	۸- توابع بازگشتی و نمونه‌ها
۴- اصل استقرای ریاضی (Mathematical induction principle)	۹- حل مسئله: معمای برج هانوی (برج برهما)
۵- استقرای کامل (Complete induction)

■ مقدمه: بازگشت (Recursion)، تعریف بازگشتی و حل مسئله

بازگشت روشی است که برای تعریف چیزی بر حسب خود آن چیز به کار می‌رود. بازگشت را می‌توان در زبان، ریاضیات، علوم کامپیوتر و سایر زمینه‌ها دید. برای مثال، تعریف بازگشتی از یک واژه، تعریفی است که از خود آن واژه در تعریف استفاده می‌کند، مانند این که، «فرهنگ واژگان کتابی است که شامل تعاریف واژگان از جمله واژه فرهنگ واژگان است». روش بازگشتی می‌تواند برای ساده‌سازی مسائل پیچیده و ایجاد راه‌حل‌های کوچک و زیبا، همانطور که در ادامی خواهیم دید، مفید باشد. اما، درک و پیاده‌سازی صحیح آن نیز می‌تواند چالش برانگیز باشد.

تابع بازگشتی نیز، تابعی است که خود را به عنوان بخشی از محاسبات خود فرامی‌خواند، مانند تابع فاکتوریل که حاصل ضرب اعداد صحیح مثبت از ۱ تا یک عدد معین را محاسبه می‌کند. به عبارت دیگر، فاکتوریل عددی مانند ۵ یعنی ۵ ضرب در فاکتوریل ۴.

الگوریتم بازگشتی نیز، روشی برای حل یک مسئله با شکستن آن به زیرمسئله‌های کوچک‌تر از همان نوع، و به کار زدن همان الگوریتم برای هر زیرمسئله تا رسیدن به حالت پایه است.

در کل، نظریه توابع بازگشتی شاخه‌ای از منطق است که کلاسی از توابع را مطالعه می‌کند که می‌توان با استفاده از بازگشت، یعنی با اعمال همان تابع برای ورودی‌های کوچک‌تر تعریف یا محاسبه کرد.

بازگشت و توابع بازگشتی توسط تورالف آلبرت اسکولم (Thoralf Albert Skolem)، یکی از پیشگامان فرامنطق، به عنوان راهکاری برای اجتناب از پارادوکس‌های نامتناهی که هنگام اعمال توابع برای کلاس‌های نامتناهی و نیز رهایی از تعاریف دوری برای کلاس‌های نامتناهی به وجود می‌آیند، ایجاد شد. همچنین، تئوری توابع بازگشتی یک مدل صوری از محاسبات ارائه می‌کند و محدودیت‌ها و امکانات محاسبه کارآمد را بررسی می‌کند.

■ تعریف استقرایی (Induction Definition)

یک تعریف استقرایی / بازگشتی تعریفی است که همه مصادیق مورد تعریف در دو گام پایه و بازگشت (بازگشت به خود) برساخته می‌شوند. به عبارت دیگر، در تعریف استقرایی / تعریف بازگشتی تعریف عناصر یک کلاس بر حسب عناصر دیگر آن کلاس انجام می‌شود. به طور معمول تعاریف استقرایی در دو گام آغاز و پایان می‌یابند: «گام پایه‌ای» و «گام استقرایی». تفاوت بین تعریف دوری (circular definition) و تعریف استقرایی در این است که یک تعریف استقرایی باید همیشه دارای گام پایه‌ باشد، یعنی، ارائه تعداد مواردی از تعریف که بدون ارجاع به خود تعریف، تعریف را بربیاورند. همه موردهای دیگر در گام استقرایی باید به‌گونه‌ای نزدیکتر به موردهای گام پایه‌ای باشند تا استقرا را پایان دهند، به عبارت دیگر، تکرار در بازگشت با مورد‌های ساده‌تر انجام یاید.

■ روش تعریف استقرایی

همانطور که در بالا گفته شد، یک تعریف استقرایی در دو گام به شرحی که می‌آید ساخته می‌شود.

۱- در گام پایه‌ای یک یا تعداد محدود از عناصر دنباله معرفی می‌شود؛

۲- در گام استقرایی (نیز موسوم به پرش استقرایی) اعمالی معرفی می‌شود که به‌موجب آن اعمال بقیه عضوهای دنباله برحسب عضوهای پیشین دنباله به دست می‌آید.

سپس تأکید می‌شود که فقط آنچه از گام‌های ۱ و ۲ حاصل می‌شود عضو دنباله است و نه هیچ‌چیز دیگر. (برخی این گام را ضروری نمی‌دانند.)

در مثالی که می‌آید دنباله‌ای بنام Fi_n را به روش بازگشتی می‌سازیم:

در گام اول می‌گویی ۱ و ۱ ازجمله عناصر این دنباله هستند.
در گام دوم می‌گوییم اگر Fi_k و Fi_k-۱ عضو دنباله باشند آنگاه Fi_k-۱+Fi_k نیز عنصر این دنباله است.
در گام سوم می‌گوییم فقط آنچه از دو گام اول ساخته می‌شود عنصر Fi_n است.

در زیر هفت عضو آغازی این دنباله آمده است:

<Fi_۱,	Fi_۲,	Fi_۳,	Fi_۴,	Fi_۵,	Fi_۶,	Fi_۷, . . .>
<۱,	۱,	۲,	۳,	۵,	۸,	۱۳, . . .>
<۱	۱	۱+۱=۲	۱+۲=۳	۲+۳=۵	۳+۵=۸	۵+۸=۱۳, . . .>

■ اصل استقرای ریاضی (Mathematical induction principle)

گیریم ویژگی P برای عدد ۰ برقرار باشد و هرگز برای هر عدد طبیعی n برقرار نباشد مگر آنکه برای n+۱ برقرار باشد. در این صورت P برای همه اعداد طبیعی برقرار خواهد بود.

■ استقرای کامل (Complete induction)

گیریم ویژگی P برای هر عدد طبیعی n وقتی برقرار است که برای همه اعداد طبیعی کوچک‌تر از n برقرار باشد؛ آنگاه P برای همه اعداد طبیعی برقرار است.

☚ . هم‌ارزی اصل استقرای ریاضی، استقرای ریاضی کامل و خوش-ترتیبی:

اصل استقرای ریاضی و استقرای ریاضی کامل دو بیان متفاوت و هم‌ارز هستند، یعنی با فرض یکی دیگری را می‌توان اثبات کرد. همچنین اصل خوش‌ترتیبی اعداد طبیعی (هر زیرمجموعه ناتهی اعداد طبیعی دارای کوچک‌ترین عنصر است) با اصل استقرای ریاضی هم‌ارز است.

اصل استقرای ریاضی ⇔ استقرای ریاضی کامل ⇔ خوش‌ترتیبی اعداد طبیعی

■ استقرای ریاضی (Mathematical induction)

۱.	گیریم خاصیت P برای ۱ برقرار باشد و
۲.	اگر برای عدد طبیعی n برقرار باشد آنگاه برای n+۱ نیز برقرار باشد؛
	آنگاه P برای همه اعداد طبیعی برقرار است.

■ مجموعه‌های بازگشتی (Recursive sets)

مجموعه‌ها را می‌توان به روش بازگشتی مشابه با آنچه درباره دنباله‌ها (بازگشتی) گفتیم تعریف کرد. مجموعه‌ای که به روش بازگشتی قابل‌تعریف‌ باشد به مجموعه بازگشتی موسوم است. هر مجموعه بازگشتی در سه گام به شرحی که می‌آید تعریف می‌شود:

۱- (گام پایه‌ای) یک یا تعداد محدودی از اعضای مجموعه معرفی می‌شود؛

۲- (گام استقرایی) اعمال (یا قواعدی) معرفی که به‌موجب آن‌ها عضوی از مجموعه برحسب اعضای موجود (فعلی) مجموعه ساخته می‌شود.

تأکید می‌شود که فقط آنچه از دو مرحله ساخت ۱ و ۲ ساخته شود عضو مجموعه است و نه هیچ عنصر دیگر.

فرض کنید می‌خواهیم مجموعه‌ای که به آن N خواهیم گفت را به روش بازگشتی تعریف کنیم.

۱- در گام پایه‌ای می‌گوییم:

۰∈N؛

۲- در گام استقرایی می‌گوییم:

اگر x∈N آنگاه x+۱∈N؛

تاکید می‌کنیم: فقط و تنها فقط آنچه از ۱ و ۲ حاصل می‌شود عضو N است.

به ۰ عنصر سازنده مجموعه N می‌گوییم. می‌توان دید N همان Z⁺ است. بنابراین مجموعه اعداد طبیعی یک مجموعه بازگشتی است.

برای مثال دیگر فرض کنید می‌خواهیم مجموعه‌ای بنام N' را به روش بازگشتی تعریف کنیم.

۱- در گام پایه‌ای می‌گوییم ۰∈N'.

۲- در گام استقرایی ابتدا تابع s را در N' به قسمی تعریف می‌کنیم که s(x) مخالف ۰ و نیز مخالف اعضای تاکنون ساخته‌شده در N' باشد و می‌گوییم اگر x∈N' باشد آنگاه s(x)∈N'.

تاکید می‌کنیم: فقط و تنها فقط آنچه از ۱ و ۲ حاصل می‌شود عضو N' است.

بنابراین

N'={۰, s(۰), s(s(۰)), s(s(s(۰))), . . .}.

◄ . به تابعی با کارکرد تابع s در بالا تابع تالی [پی-آمد] گفته و آن را معمولاً با succ نشان داده. در این مثال می‌توان نوشت:

succ(n) = n + ۱.

برای مثال دیگر فرض کنید می‌خواهیم مجموعه‌ای بنام N'' را به روش بازگشتی تعریف کنیم.

۱- در گام پایه‌ای می‌گوییم:

ø ∈ N''.

۲- در گام استقرایی می‌گوییم:

اگر x ∈ N'' آنگاه x∪{x}∈N''.

[در اینجا succ(x)=x∪{x}.]

تاکید می‌کنیم: تنها و فقط تنها آنچه از ۱ و ۲ حاصل می‌شود عضو N'' است.

بنابراین:

N''={ø, ø∪{ø}={ø}, {ø}∪{{ø}}={ø, {ø}}, {ø, {ø},{ø,{ø}}}, . . . }.

اگر در این مثال ø را با نماد ۰، {ø} را با ۱، {ø, {ø}} را با ۲ نشان دهیم و همین‌طور مانند آن‌ها، آنگاه مجموعه {۰, ۱, ۲, . . .} را در پی خواهیم داشت که ø عنصر سازنده آن است.

• دستگاه حساب پئانو را ببینید.

• مجموعه استقرایی را ببینید.

• مجموعه اعداد طبیعی را ببینید.

■ توابع بازگشتی و نمونه‌ها

همانطور که نیز در ابتدای این قسمت گفته شد، یک تابع بازگشتی تابعی است که در چرخه‌های پی در پی خود را به عنوان بخشی از محاسبات خود اما با ورودی‌های کوچکتر فرامی‌خواند.

☜ در آنچه می‌آید، مگر خلاف آن گفته شود، مجموعه مرجع ما اعداد طبیعی ℕ است.

• مثال ۱. تابع جمع در دستگاه پئانو

در این مثال و دو مثال بعد فرض کرده‌ایم که مروری به دستگاه پئانو داشته‌ایم و نیز توجه داریم که اعداد در این دستگاه به قرار زیر هستند:

۰, S(۰), S(S(۰)), S(S(S(۰))), . . .

[S(n) تالی بی‌واسطه n است.]

به عبارت دیگر:

۰, S^۱(۰), S^۲(۰), S^۳(۰), . . . ,Sⁿ(.), . . .

تابع جمع بازگشتی، sum(x, S(y))، در این دستگاه به روش بازگشتی مطابق زیر تعریف می‌شود:

sum(x, y)	=
		آ:	x	اگر y = .	گام پایه‌ای:
sum(x, S(y))
		ب:	S(sum(x, y))	در غیر آن.	گام استقرایی:

در این تعریف جمع x و تالی y در گام استقرایی بر حسب جمع x و y تعریف شده است.

• مثال ۲. تابع بازگشتی ضرب در دستگاه پئانو

تابع ضرب بازگشتی، mul(x, S(y))، در این دستگاه به روش بازگشتی مطابق زیر تعریف می‌شود:

mul(x, y)	=
		آ:	.	اگر y = .	گام پایه‌ای:
mul(x, S(y))
		ب:	sum(x, mul(x, y))	در غیر آن.	گام استقرایی:

در این تعریف ضرب x و تالی y در گام استقرایی بر حسب جمع x با حاصل‌ضرب x در y تعریف شده است.

• مثال ۳. تابع توان در دستگاه پئانو

تابع توان، pow(x, S(y))، در این دستگاه به روش بازگشتی مطابق زیر تعریف می‌شود:

pow(x, y)	=
		آ:	S(.)	اگر y = .	گام پایه‌ای:
pow(x, S(y))
		ب:	mul(x, pow(x, y))	در غیر آن.	گام استقرایی:

در این تعریف x به توان تالی y در گام استقرایی بر حسب ضرب x در x به توان y تعریف شده است.

• تابع بزرگترین مقسوم علیه مشترک

فرض کنید x≥y>۰ اعداد طبیعی باشند و مقدار تابع mod(x,y) باقیمانده تقسیم صحیح x بر y باشد. در این صورت تابع GCD(x,y)، که به قرار زیر تعریف شده است، را بزرگترین مقسوم علیه مشترک x و y می‌نامیم.

GCD(x, y)	=
		آ:	x	اگر mod(x, y)=۰	گام پایه‌ای:
		ب:	GCD(x, mod(x, y))	در غیر آن.	گام استقرایی:

در حساب بزرگترین مقسوم علیه مشترک دوعدد بزگترین عددی است که آن دو را می‌شمرد. آیا تابع GCD در بالا این تعریف را برمی‌آورد؟ از حساب می‌دانیم اعداد q و r بگونه یکتا وجود دارند به قسمی که:

I. x = qy + r; m > r ≥ ۰

[می‌دانیم اگر t ،s را بشمرد و u ،t را بشمرد آنگاه u ،s را خواهد ‌شمرد.]

[می‌توان در رابطه I نشان داد: mod(x, y) < [x / ۲]]

از رابطه I داریم که هر چه r و y را بشمارد آنگاه x را می‌شمارد. I را می‌توان به صورت زیر نیز نوشت:

II.x - qy = r

از رابطه II نیز داریم: هر چه x و y را بشمارد r را نیز می‌شمارد.

[نمونه‌ای از محاسبه ب.م.م در بحث مقدماتی الگوریتم آمده است.]

■ حل مسئله: معمای برج هانوی (برج برهما)

معمای مشهور به برج هانوی (نیز برج برهما) در ۱۸۸۳ توسط ریاضیدان فرانسوی ادوارد لوکاس (Edouard Lucas) همرا با افسانه خود (برج برهما) پا به جهان گشود.↧

Edouard Lucas, Récréations mathématiques, four volumes. Gauthier-Villars, Paris, 1891-1894.

«در معبد بزرگ بنارس، زیر گنبدی که مرکز جهان است، صفحه‌ای برنجی قرار دارد که در آن سه سوزن الماس، هر یک به ارتفاع یک ذراع و به ضخامت بدن زنبور عسل تعبیه شده است. روی یکی از این سوزن‌ها، هنگام آفرینش، خداوند شصت و چهار قرص از طلای ناب قرار داد که بزرگترین قرص روی صفحه‌ای برنجی و بر روی آن بقیه قرص‌ها تا بالا کوچکتر و کوچکتر قرار دارند. روز و شب، بی وقفه، کاهنان قرص‌ها را از یک سوزن الماس به سوزن الماس دیگر بر اساس قوانین ثابت و تغییرناپذیر برهما منتقل می‌کنند. طبق قوانین ثابت و تغییرناپذیر برهمای در حال انجام وظیفه نباید بیش از یک قرص را در یک زمان انتقال دهد و نیز نباید قرصی در یک سوزن روی قرص کوچکتر آن باشد. هنگامی که شصت و چهار قرص به این ترتیب از سوزنی که در آفرینش خداوند آنها را اینگونه آفریده بود به یکی از سوزن‌های منتقل شوند، آنگاه جهان درهم می‌ریزد و با صدای مهیب محو می‌شود.»

آنچه این معما از ما می‌خواهد (یا اینجا در پی آنیم):

۱- یافتن دنباله‌ای از حرکت‌های تک دیسکی برای انتقال ۶۴ دیسک از یکی از سه سوزن به سوزنی دیگر مطابق با قوانین برهمایی.

۲- چند حرکت تک دیسکی برای انجام کار لازم و کافی است؟

بهترین راه در برابر چنین پرسشی (پرسش‌هایی)، تعمیم آن(ها) است. برج برهما دارای ۶۴ دیسک است، در نظر بگیرید که اگر n دیسک وجود داشته باشد چه اتفاقی می‌افتد.

یکی از مزایای این تعمیم این است که می‌توان مسئله را کاهش داد. در واقع، در بیشتر موارد و در ابتدا نگاه به موارد کوچک سودمند است و به ما بینش در مورد کل مسئله را می‌دهد. [«اگر از عهده حل مسئله‌ای برنمی‌آیید، مسئله‌ای آسان‌تر هست که از عهده آن برمی‌آیید: آن را بیابید➥»]. دنباله حرکت‌های تک دیسکی از سوزنی که فقط شامل یک یا دو دیسک است آسان است. تعداد کمی آزمون نشان خواهد داد که چگونه می‌توان دیسک‌ها را از یک سوزن دو‌تایی به سوزن دیگر منتقل کرد.

معمای برج هانوی (برهما) — تعمیم برج برهما (۱)

می‌توانیم از انتقال n=۰ دیسک آغاز کنیم که در این حالت به تعداد صفر جابجایی نیاز است. در نمودار زیر حل معما برای یک و دو دیسک آمده است.

• محاسبه

اگر T_i را تعداد انتقال‌های تک دیسکی برای برج برهما با i دیسک بنامیم، آنگاه با توجه به شکل بالا می‌توان نوشت:

T_۰ = ۰
T_۱ = ۱
T_۲ = ۳

برای حل معما در حالت سه دیسک، یعنی یافتن دنباله حرکت‌های تک دیسکی برای انتقال سه دیسک آنگونه که برهما می‌خواهد چه باید کرد؟ پاسخ نه تنها آسان بلکه آماده هم است. یعنی:

۱-	دو دیسک رویی را با روش حل در حالت دو دیسکی به یکی از دو میله خالی، به فرض c انتقال می‌دهیم.
۲-	دیسک سوم، یعنی بزرگ‌تری دیسک، را به میله b انتقال می‌دهیم.
۳-	دو دیسک در میله c را با روش حل در حالت دو دیسکی به میله به فرض b انتقال می‌دهیم.
۴-	پایان.

اکنون حل معما تا اینجا را تعمیم می‌دهیم و می‌گوییم: اگر حل معما را برای n-۱ دیسک داشته باشیم آنگاه روند حل معما برای n دیسک بگونه زیر است.

۱-	n-۱ دیسک رویی را با روش حل در حالت n-۱دیسکی به یکی از دو میله خالی، به فرض c انتقال می‌دهیم.
۲-	دیسک nام، یعنی بزرگ‌تری دیسک، را به میله b انتقال می‌دهیم.
۳-	n-۱ دیسک در میله c را با روش حل در حالت n-۱ دیسکی به میله به فرض b انتقال می‌دهیم.
۴-	پایان.

در روند بالا دوبار انتقال n-۱ داریم، یعنی T_n-۱ بار حرک تک دیسکی و یک بار هم انتقال دیسک زیرین، یعنی بزرگترین دیسک، پس می‌نویسیم:

a.T_n ≤ ۲T_{n - ۱} + ۱; n > ۰ برای

در فرمول بالا بجای «=» نماد کوچکتر یا بزرگتر، ≤، آمده است. این به این دلیل است که روند ساخت این فرمول از عهده کفایت ۲T_n-۱+۱ حرکت برای و نه لزوم آن برمی‌آید. در روند حل این معما سرانجام باید بزرگترین دیسک را جابجا کنیم. وقتی این کار را انجام می‌دهیم که n-۱ کوچکترین دیسک روی یک میله باشند، و حداقل باید T_n-۱+۱ جابجایی انجام شده باشد تا آن‌ها را در آن میله قرار داده باشیم. اگر خیلی هوشیار نباشیم، ممکن است بزرگ‌ترین دیسک را بیش از یک بار جابجا کنیم. اما پس از جابجایی بزرگترین دیسک برای آخرین بار، باید n-۱ کوچکترین دیسک (که باید دوباره روی یک میله قرار گیرند) را روی بزرگترین دیسک منتقل کنیم. این نیز به T_n-۱ جابجایی نیاز دارد. بنابراین می‌توان نوشت:

b. T_n ≥ ۲T_{n - ۱} + ۱; n > ۰ برای

از دو نامعادله a و ‌b و اینکه T_۰= ۰، می‌توان نوشت:

T_۰ = ۰ n = ۰ برای
T_n = ۲T_{n - ۱} + ۱; n > ۰ برای

بنابراین:

T_۰ = ۰= ۲^۰ - ۱
T_۱ = ۲ × ۰ + ۱ = ۱ = ۲^۱ - ۱
T_۲ = ۲ × ۱ + ۱ = ۳ = ۲^۲ - ۱
T_۳ = ۲ × ۳ + ۱ = ۷ = ۲^۳ - ۱
T_۴ = ۲ × ۷ + ۱ = ۱۵ = ۲^۴ - ۱
T_۵ = ۲ × ۱۵ + ۱ = ۳۱ = ۲^۵ - ۱
....
....
T_n = ۲T_{n - ۱} + ۱ ≟ ۲^{n - ۱} - ۱
....

برای اینکه نشان دهیم T_n=۲ⁿ-۱ از اصل استقرا بهره می‌بریم و فرض می‌گیریم برای کم‌تر از n این رابطه برقرار باشد. پس می‌نویسیم:

T_n = ۲T_{n - ۱} + ۱ = ۲(۲^{n - ۱} - ۱ ) + ۱=
= ۲×۲^{n - ۱} - ۲ + ۱= ۲ⁿ - ۱

بنابراین برهمای مامور به آخر رساندن جهان باید T_۶۴=۲^۶۴-۱ جابجایی انجام دهد که برابر عددی با ۱۹ رقم است. اگر هر جابجای تک دیسک یک میلیون‌ام ثانیه زمان ببرد، برهما باید بیش از ۵۰۰۰ قرن به کار جابجایی بپردازد.^↧

Ronald L. Graham, Donald E. Knuth, Oren Patashnik; Concrete Mathematics Second Edition; Addison-wesley publishing company; 1994.

◄ توجه: