در بسیاری از مسائل ریاضی، رسیدن مستقیم از فرض مسئله به نتیجه سادهترین مسیر نیست. گاهی یک گزاره بسته به وضعیت متغیرها، علامت عبارتها، زوج یا فرد بودن اعداد، یا باقیمانده حاصل از تقسیم، رفتارهای متفاوتی دارد. در چنین شرایطی میتوان مسئله را به چند حالت تقسیم کرد و هر حالت را جداگانه بررسی کرد.
در منابع دانشگاهی، اثبات با تفکیک حالات بهعنوان یکی از روشهای استاندارد اثبات معرفی میشود. در این روش، حالتها باید همه امکانات ممکن را پوشش دهند و استدلال در هر حالت به نتیجه موردنظر منتهی شود. این روش در درسهای مبانی ریاضیات، منطق، ریاضیات گسسته و دورههای آموزش روشهای اثبات کاربرد گستردهای دارد.
برای استفاده از این روش، آشنایی با مفهوم گزاره و استدلال منطقی کافی است. همچنین باید بتوانیم مجموعهای از حالتها را بهگونهای انتخاب کنیم که دستکم یکی از آنها برای هر وضعیت ممکن برقرار باشد.
اگر \(P\) گزارهای باشد، ممکن است بتوانیم آن را به چند حالت \(C_1,C_2,\ldots,C_n\) تقسیم کنیم، بهگونهای که:
$$ C_1\lor C_2\lor\cdots\lor C_n $$
همیشه درست باشد. در این صورت، اگر نشان دهیم:
$$ C_1\rightarrow P,\quad C_2\rightarrow P,\quad \ldots,\quad C_n\rightarrow P $$
میتوان نتیجه گرفت که \(P\) درست است.
فرض کنید میخواهیم گزاره \(P\) را ثابت کنیم و میدانیم یکی از حالتهای \(C_1,C_2,\ldots,C_n\) باید برقرار باشد. اگر برای هر \(i\) نشان دهیم:
$$ C_i\rightarrow P $$
به زبان ساده، ابتدا نشان میدهیم که حالتهای انتخابشده تمام امکانات را پوشش میدهند؛ سپس در هر حالت، گزاره موردنظر را ثابت میکنیم.
فرض کنید میخواهیم وارد ساختمانی شویم و میدانیم تنها سه درِ ممکن وجود دارد: درِ اول، درِ دوم و درِ سوم. اگر نشان دهیم از هر سه در میتوان به مقصد رسید، بدون اینکه بدانیم دقیقاً کدام در مورد استفاده قرار میگیرد، میتوانیم نتیجه بگیریم که در هر حالت به مقصد خواهیم رسید.
در ریاضیات نیز همین ایده وجود دارد. لازم نیست یک استدلال واحد برای همه وضعیتها پیدا کنیم؛ میتوانیم وضعیتهای ممکن را جدا کنیم و در هر کدام استدلال مناسبی ارائه دهیم.
برای مثال، هر عدد صحیح یا زوج است یا فرد. بنابراین دو حالت زیر همه اعداد صحیح را پوشش میدهند:
$$ n\text{ زوج}\quad\lor\quad n\text{ فرد} $$
در نتیجه، اگر گزارهای را برای همه اعداد صحیح میخواهیم ثابت کنیم، میتوانیم دو حالت «\(n\) زوج» و «\(n\) فرد» را بررسی کنیم.
همین ایده را میتوان برای باقیمانده تقسیم بر یک عدد مثبت نیز به کار برد. اگر \(n\) را بر \(m\) تقسیم کنیم، با توجه به الگوریتم تقسیم، یک عدد صحیح \(q\) و یک باقیمانده \(r\) وجود دارند که:
$$ n=mq+r $$
بنابراین \(r\) یکی از اعداد
$$ 0,1,2,\ldots,m-1 $$
است. این موضوع راهی طبیعی برای ساختن حالتهای مختلف در مسائل بخشپذیری و حساب پیمانهای فراهم میکند.
آیا حالتها باید از یکدیگر جدا باشند؟
نه لزوماً. برای معتبر بودن اثبات، مهمترین شرط این است که حالتها همه امکانات را پوشش دهند. لازم نیست همیشه دو حالت نسبت به یکدیگر ناسازگار باشند.
البته در بسیاری از مسائل، انتخاب حالتهای مجزا کار را سادهتر و ساختار اثبات را روشنتر میکند. برای مثال، تقسیم اعداد حقیقی به حالتهای
$$ x<0,\qquad x=0,\qquad x>0 $$
هم کامل است و هم حالتها با یکدیگر اشتراک ندارند.
در مقابل، میتوان حالتهایی داشت که روی هم همپوشانی داشته باشند؛ به شرط آنکه هر وضعیت ممکن دستکم در یکی از حالتها قرار بگیرد.
ساختار استاندارد اثبات با تفکیک حالات
یک اثبات با تفکیک حالات معمولاً مراحل زیر را دارد:
- گزارهای را که باید ثابت شود مشخص میکنیم.
- اطمینان پیدا میکنیم که مسئله را میتوان به چند حالت تقسیم کرد.
- نشان میدهیم این حالتها همه امکانات ممکن را پوشش میدهند.
- هر حالت را بهصورت جداگانه بررسی میکنیم.
- در هر حالت، با استدلال معتبر به نتیجه موردنظر میرسیم.
- در پایان از پوشش کامل حالتها و درستی نتیجه در هر حالت، گزاره کلی را نتیجه میگیریم.
الگوی ساده این روش چنین است:
$$ \begin{aligned} &\text{حالت ۱: } C_1\rightarrow P\\ &\text{حالت ۲: } C_2\rightarrow P\\ &\vdots\\ &\text{حالت }n: C_n\rightarrow P \end{aligned} $$
همراه با این واقعیت که:
$$ C_1\lor C_2\lor\cdots\lor C_n $$
در نتیجه:
$$ P $$
اثبات با تفکیک حالات از دیدگاه منطق
ارتباط این روش با منطق گزارهای را میتوان به شکل دقیقتری بیان کرد. اگر فرض اولیه یک شرط به صورت فصل چند گزاره باشد:
$$ P_1\lor P_2\lor\cdots\lor P_n $$
و هدف اثبات \(Q\) باشد، میتوان هر یک از حالتها را جداگانه بررسی کرد:
$$ P_1\rightarrow Q $$ $$ P_2\rightarrow Q $$ $$ \vdots $$ $$ P_n\rightarrow Q $$
از آنجا که حداقل یکی از \(P_i\)ها برقرار است و در هر یک از آن حالتها \(Q\) نتیجه میشود، \(Q\) برقرار خواهد بود.
این ساختار با مفهوم فصل منطقی ارتباط مستقیم دارد. بنابراین آشنایی با همارزی منطقی و جدول ارزش میتواند در درک دقیقتر بنیان منطقی این روش مفید باشد.
انتخاب حالتهای مناسب
انتخاب حالتها معمولاً مهمترین بخش خلاقانه اثبات است. یک تقسیمبندی خوب باید دو ویژگی داشته باشد:
- همه وضعیتهای ممکن را پوشش دهد.
- در هر حالت، اطلاعات اضافی و مفیدی در اختیار ما قرار دهد.
چند تقسیمبندی رایج عبارتاند از:
زوج و فرد
برای یک عدد صحیح \(n\)، دو حالت طبیعی عبارتاند از:
$$ n=2k $$
یا:
$$ n=2k+1 $$
که در آن \(k\) یک عدد صحیح است.
مثبت، صفر و منفی
برای یک عدد حقیقی \(x\)، میتوان سه حالت زیر را در نظر گرفت:
$$ x<0,\qquad x=0,\qquad x>0 $$
باقیماندههای تقسیم
برای بررسی یک عدد صحیح نسبت به بخشپذیری بر \(m\)، میتوان حالتهای مختلف باقیمانده را بررسی کرد:
$$ n\equiv0,1,\ldots,m-1\pmod m $$
حالتهای ناشی از یک تابع چندبخشی
اگر تابعی در بازههای مختلف فرمولهای متفاوت داشته باشد، طبیعی است که اثبات نیز بر اساس همان بازهها تفکیک شود.
مثال حلشده اول: جمع دو عدد با زوجیت یکسان
قضیه: اگر \(a\) و \(b\) دو عدد صحیح باشند و هر دو زوج یا هر دو فرد باشند، آنگاه \(a+b\) زوج است.
چون هر عدد صحیح یا زوج است یا فرد، دو حالت داریم.
حالت اول: هر دو عدد زوجاند
اگر \(a\) و \(b\) زوج باشند، اعداد صحیح \(m\) و \(n\) وجود دارند که:
$$ a=2m,\qquad b=2n $$
بنابراین:
$$ a+b=2m+2n=2(m+n) $$
چون \(m+n\) یک عدد صحیح است، \(a+b\) به شکل دو برابر یک عدد صحیح نوشته شده و در نتیجه زوج است.
حالت دوم: هر دو عدد فردند
اگر \(a\) و \(b\) فرد باشند، اعداد صحیح \(m\) و \(n\) وجود دارند که:
$$ a=2m+1,\qquad b=2n+1 $$
پس:
$$ \begin{aligned} a+b &= (2m+1)+(2n+1)\\ &=2m+2n+2\\ &=2(m+n+1) \end{aligned} $$
بنابراین \(a+b\) زوج است.
چون هر دو حالت ممکن بررسی شدند، نتیجه میگیریم:
$$ \boxed{a+b\text{ زوج است}} $$
مثال حلشده دوم: مربع هر عدد صحیح چه باقیماندههایی میتواند داشته باشد؟
قضیه: مربع هر عدد صحیح در تقسیم بر \(3\)، فقط میتواند باقیمانده \(0\) یا \(1\) داشته باشد.
هنگام تقسیم هر عدد صحیح \(n\) بر \(3\)، یکی از سه حالت زیر برقرار است:
$$ n=3k $$ $$ n=3k+1 $$ $$ n=3k+2 $$
حالت اول: \(n=3k\)
$$ n^2=(3k)^2=9k^2=3(3k^2) $$
بنابراین باقیمانده \(n^2\) در تقسیم بر \(3\) برابر \(0\) است.
حالت دوم: \(n=3k+1\)
$$ \begin{aligned} n^2 &=(3k+1)^2\\ &=9k^2+6k+1\\ &=3(3k^2+2k)+1 \end{aligned} $$
بنابراین باقیمانده برابر \(1\) است.
حالت سوم: \(n=3k+2\)
$$ \begin{aligned} n^2 &=(3k+2)^2\\ &=9k^2+12k+4\\ &=9k^2+12k+3+1\\ &=3(3k^2+4k+1)+1 \end{aligned} $$
در این حالت نیز باقیمانده \(1\) است.
بنابراین مربع هر عدد صحیح هنگام تقسیم بر \(3\) فقط یکی از دو باقیمانده زیر را دارد:
$$ \boxed{n^2\equiv0\text{ یا }1\pmod3} $$
مثال حلشده سوم: نامساوی دارای قدرمطلق
قضیه: برای هر عدد حقیقی \(x\)، نشان دهید:
$$ x+|x-7|\ge7 $$
دلیل مناسب برای تفکیک حالات، وجود قدرمطلق است. عبارت \( |x-7| \) بسته به علامت \(x-7\) دو شکل متفاوت دارد.
حالت اول: \(x\ge7\)
در این حالت:
$$ x-7\ge0 $$
بنابراین:
$$ |x-7|=x-7 $$
پس:
$$ x+|x-7|=x+x-7=2x-7 $$
چون \(x\ge7\)، داریم:
$$ 2x-7\ge14-7=7 $$
بنابراین نامساوی در این حالت برقرار است.
حالت دوم: \(x<7\)
اکنون:
$$ x-7<0 $$
بنابراین:
$$ |x-7|=-(x-7)=7-x $$
در نتیجه:
$$ x+|x-7|=x+(7-x)=7 $$
پس در این حالت نیز:
$$ x+|x-7|\ge7 $$
دو حالت \(x\ge7\) و \(x<7\) همه اعداد حقیقی را پوشش میدهند. بنابراین:
$$ \boxed{x+|x-7|\ge7} $$
مثال حلشده چهارم: آخرین رقم مربع یک عدد صحیح
قضیه: رقم یکان مربع هر عدد صحیح فقط میتواند یکی از ارقام \(0,1,4,5,6,9\) باشد.
برای بررسی این موضوع کافی است باقیمانده عدد صحیح \(n\) را در تقسیم بر \(10\) در نظر بگیریم. هر عدد صحیح یکی از حالتهای زیر را دارد:
$$ n\equiv0,1,2,3,4,5,6,7,8,9\pmod{10} $$
بنابراین کافی است مربع این ده حالت را بررسی کنیم:
| باقیمانده \(n\) بر \(10\) |
باقیمانده \(n^2\) بر \(10\) |
| \(0\) |
\(0\) |
| \(1\) |
\(1\) |
| \(2\) |
\(4\) |
| \(3\) |
\(9\) |
| \(4\) |
\(6\) |
| \(5\) |
\(5\) |
| \(6\) |
\(6\) |
| \(7\) |
\(9\) |
| \(8\) |
\(4\) |
| \(9\) |
\(1\) |
پس مجموعه باقیماندههای ممکن مربع یک عدد صحیح در تقسیم بر \(10\) برابر است با:
$$ \{0,1,4,5,6,9\} $$
بنابراین رقم یکان مربع هر عدد صحیح نیز فقط میتواند یکی از همین شش رقم باشد.
مثال حلشده پنجم: اثبات یک گزاره با چهار حالت
قضیه: اگر \(x\) و \(y\) دو عدد حقیقی باشند، آنگاه:
$$ |xy|=|x||y| $$
در اینجا علامت \(x\) و \(y\) هر کدام میتواند مثبت یا منفی باشد. بنابراین چهار حالت طبیعی داریم:
- \(x\ge0\) و \(y\ge0\)
- \(x\ge0\) و \(y<0\)
- \(x<0\) و \(y\ge0\)
- \(x<0\) و \(y<0\)
حالت اول: \(x\ge0\) و \(y\ge0\)
$$ |x|=x,\qquad |y|=y $$
همچنین \(xy\ge0\)، پس:
$$ |xy|=xy=|x||y| $$
حالت دوم: \(x\ge0\) و \(y<0\)
در این حالت:
$$ |x|=x,\qquad |y|=-y $$
و چون \(x\ge0\) و \(y<0\)، داریم \(xy\le0\). بنابراین:
$$ |xy|=-xy=x(-y)=|x||y| $$
حالت سوم: \(x<0\) و \(y\ge0\)
مشابه حالت قبل:
$$ |x|=-x,\qquad |y|=y $$
و \(xy\le0\). پس:
$$ |xy|=-xy=(-x)y=|x||y| $$
حالت چهارم: \(x<0\) و \(y<0\)
در این حالت حاصلضرب دو عدد منفی مثبت است:
$$ xy>0 $$
بنابراین:
$$ |xy|=xy=(-x)(-y)=|x||y| $$
هر چهار حالت ممکن بررسی شدند؛ بنابراین:
$$ \boxed{|xy|=|x||y|} $$
مثال حلشده ششم: یک کاربرد ترکیبی با باقیماندهها
قضیه: نشان دهید برای هر عدد صحیح \(n\)، عبارت
$$ 2n^2+n+1 $$
بر \(3\) بخشپذیر نیست.
با تقسیم \(n\) بر \(3\)، سه حالت داریم:
$$ n=3k,\qquad n=3k+1,\qquad n=3k+2 $$
حالت اول: \(n=3k\)
$$ \begin{aligned} 2n^2+n+1 &=2(3k)^2+3k+1\\ &=18k^2+3k+1\\ &=3(6k^2+k)+1 \end{aligned} $$
پس باقیمانده برابر \(1\) است.
حالت دوم: \(n=3k+1\)
$$ \begin{aligned} 2n^2+n+1 &=2(3k+1)^2+(3k+1)+1\\ &=2(9k^2+6k+1)+3k+2\\ &=18k^2+15k+4\\ &=3(6k^2+5k+1)+1 \end{aligned} $$
پس باقیمانده نیز \(1\) است.
حالت سوم: \(n=3k+2\)
$$ \begin{aligned} 2n^2+n+1 &=2(3k+2)^2+(3k+2)+1\\ &=2(9k^2+12k+4)+3k+3\\ &=18k^2+27k+11\\ &=3(6k^2+9k+3)+2 \end{aligned} $$
در این حالت باقیمانده \(2\) است.
بنابراین در هیچیک از سه حالت باقیمانده صفر نیست. پس:
$$ \boxed{3\nmid(2n^2+n+1)} $$
اثبات با تفکیک حالات برای چند حالت بیشتر
تعداد حالات در این روش محدود به دو یا سه حالت نیست. اگر ساختار مسئله به چهار، پنج یا حتی تعداد بیشتری حالت نیاز داشته باشد، میتوان همه آنها را بررسی کرد.
برای نمونه، در بررسی رقم یکان مربع، ده حالت ممکن داشتیم. در بررسی باقیمانده تقسیم بر \(5\)، پنج حالت ممکن داریم:
$$ n\equiv0,1,2,3,4\pmod5 $$
به طور کلی، هنگام تقسیم بر عدد مثبت \(m\)، دقیقاً \(m\) باقیمانده ممکن وجود دارد:
$$ 0,1,\ldots,m-1 $$
بنابراین در مسائل مربوط به بخشپذیری، پیمانه و رقمهای عددی، تعداد حالات را میتوان بر اساس ساختار مسئله تعیین کرد.
اثبات با تفکیک حالات و اثبات exhaustive
دو اصطلاح «اثبات با تفکیک حالات» و «اثبات exhaustive» یا «اثبات با بررسی همه موارد» به یکدیگر نزدیکاند، اما در کاربرد دقیق میتوان میان آنها تفاوت گذاشت.
در اثبات با تفکیک حالات، هر حالت لزوماً یک مثال منفرد نیست. یک حالت ممکن است شامل بینهایت مقدار باشد؛ برای مثال:
$$ n\text{ زوج} $$
خود شامل بینهایت عدد صحیح است.
اما در اثبات exhaustive، معمولاً تعداد حالتها یا نمونههای مورد بررسی محدود و قابل شمارش است و با بررسی تکتک آنها نتیجه به دست میآید.
برای مثال، اگر بدانیم \(n\) یک عدد صحیح مثبت و \(n\le4\) است، فقط چهار مقدار ممکن وجود دارد:
$$ n=1,2,3,4 $$
بررسی مستقیم هر چهار مقدار نمونهای از اثبات exhaustive است.
بنابراین میتوان گفت اثبات exhaustive حالت خاصی از تفکیک حالات است که در آن هر حالت عملاً یک نمونه یا مورد مشخص است.
تفاوت اثبات با تفکیک حالات و اثبات مستقیم
در اثبات مستقیم معمولاً از فرضهای مسئله شروع میکنیم و با یک زنجیره استدلال به نتیجه میرسیم.
در اثبات با تفکیک حالات نیز ممکن است در هر حالت از اثبات مستقیم استفاده کنیم؛ تفاوت در این است که ابتدا دامنه مسئله را به چند وضعیت تقسیم میکنیم.
بنابراین این دو روش الزاماً رقیب یکدیگر نیستند. یک اثبات با تفکیک حالات میتواند در داخل هر حالت یک اثبات مستقیم داشته باشد.
برای مثال، در قضیه زوج یا فرد بودن \(n\)، دو حالت ایجاد میکنیم و در هر حالت با استفاده از تعریف زوج یا فرد بودن، محاسبهای مستقیم انجام میدهیم.
تفاوت اثبات با تفکیک حالات و برهان خلف
در برهان خلف، نقیض گزاره موردنظر فرض میشود و سپس از آن به تناقض میرسیم.
اما در اثبات با تفکیک حالات، هدف اصلی تقسیم وضعیتهای ممکن و اثبات نتیجه در هر یک از آنهاست.
البته این دو روش میتوانند با یکدیگر ترکیب شوند. ممکن است ابتدا مسئله را به چند حالت تقسیم کنیم و سپس در یکی از حالتها از برهان خلف استفاده کنیم.
تفاوت اثبات با تفکیک حالات و برهان عکس نقیض
در برهان عکس نقیض برای اثبات گزاره شرطی
$$ P\rightarrow Q $$
گزاره همارز زیر را اثبات میکنیم:
$$ \lnot Q\rightarrow\lnot P $$
در اثبات با تفکیک حالات، ساختار میتواند کاملاً متفاوت باشد و به تعداد مختلفی از حالتها تقسیم شود.
بنابراین «تفکیک حالات» یک روش سازماندهی استدلال بر اساس وضعیتهای مختلف است، در حالی که «عکس نقیض» یک تبدیل منطقی مشخص برای اثبات گزارههای شرطی است.
چه زمانی اثبات با تفکیک حالات مناسب است؟
این روش معمولاً زمانی انتخاب خوبی است که:
- رفتار عبارت موردنظر در شرایط مختلف تغییر میکند.
- تعداد حالتهای ممکن محدود یا بهخوبی قابل کنترل است.
- در هر حالت، اطلاعات بیشتری برای ادامه استدلال به دست میآید.
- مسئله شامل قدرمطلق، علامت، زوجیت یا باقیمانده باشد.
- یک فرض منطقی به چند حالت طبیعی تقسیم شود.
- اثبات یکسان برای همه وضعیتها دشوار باشد، اما هر حالت بهتنهایی ساده شود.
منابع آموزشی دانشگاهی نیز بر همین ایده تأکید دارند: زمانی که اطلاعات موجود شامل چند امکان متفاوت است و هر امکان مسیر استدلال را روشنتر میکند، تفکیک حالات میتواند روش مناسبی باشد.
چه زمانی نباید از تفکیک حالات استفاده کرد؟
اگر تعداد حالتها بسیار زیاد باشد و هیچ ساختار سادهای میان آنها وجود نداشته باشد، تفکیک حالات ممکن است اثبات را طولانی و غیرضروری کند.
برای مثال، اگر مسئلهای بهطور طبیعی به هزاران حالت تقسیم شود، بهتر است بررسی کنیم آیا میتوان از یک قضیه عمومی، استقرا، برهان خلف، عکس نقیض یا روش دیگری استفاده کرد.
همچنین نباید فقط به دلیل امکان تقسیم مسئله به حالات، این روش را انتخاب کرد. هدف انتخاب روش اثبات، رسیدن به استدلالی معتبر و تا حد امکان روشن و اقتصادی است.
قضیه مهم درباره پوشش حالات
میتوان اصل این روش را به شکل یک نتیجه منطقی بیان کرد.
قضیه: اگر گزارههای \(C_1,C_2,\ldots,C_n\) دستکم یکی از حالتهای ممکن را برای هر وضعیت پوشش دهند و برای هر \(i\) داشته باشیم:
$$ C_i\rightarrow P $$
آنگاه:
$$ P $$
ایده اثبات
چون حالات همه امکانات را پوشش میدهند:
$$ C_1\lor C_2\lor\cdots\lor C_n $$
در هر وضعیت دستکم یکی از \(C_i\)ها درست است. از طرف دیگر، برای هر حالت میدانیم:
$$ C_i\rightarrow P $$
بنابراین هر کدام از حالتها که برقرار باشد، \(P\) نتیجه میشود. پس \(P\) در حالت کلی درست است.
تفکیک حالات در مسائل دارای قدرمطلق
یکی از رایجترین کاربردهای این روش، حذف قدرمطلق است. برای هر عدد حقیقی \(x\):
$$ |x|= \begin{cases} x & x\ge0\\ -x & x<0 \end{cases} $$
بنابراین هنگام اثبات یک گزاره شامل \( |x| \)، معمولاً مرز \(x=0\) محل طبیعی تفکیک حالات است.
اگر عبارت شامل چند قدرمطلق باشد، ممکن است چند نقطه مرزی ایجاد شود. برای مثال در عبارت:
$$ |x+2|+|x-3| $$
نقاطی که علامت عبارتهای داخل قدرمطلق تغییر میکند عبارتاند از:
$$ x=-2,\qquad x=3 $$
بنابراین میتوان محور حقیقی را به سه بازه تقسیم کرد:
$$ x\le-2,\qquad -2 این تقسیمبندی باعث میشود فرمول قدرمطلقها در هر بازه ثابت باشد و حل مسئله سادهتر شود.
تفکیک حالات در مسائل زوج و فرد
برای اعداد صحیح، یکی از سادهترین و پرکاربردترین تقسیمبندیها زوج و فرد بودن است:
$$ n=2k $$
برای عدد زوج و:
$$ n=2k+1 $$
برای عدد فرد.
بنابراین اگر گزارهای درباره همه اعداد صحیح باشد، در بسیاری از مسائل میتوان آن را در دو حالت زوج و فرد بررسی کرد.
توجه کنید که این روش فقط زمانی معتبر است که دامنه مسئله واقعاً اعداد صحیح باشد. برای یک عدد حقیقی، «زوج یا فرد» بودن معنا ندارد.
تفکیک حالات در مسائل بخشپذیری
در مسائل بخشپذیری، باقیمانده تقسیم یک ابزار بسیار طبیعی برای ساخت حالتهاست.
برای مثال، هر عدد صحیح نسبت به پیمانه \(4\) یکی از چهار حالت زیر را دارد:
$$ n\equiv0,1,2,3\pmod4 $$
اگر مسئلهای درباره مربع یا مکعب عدد صحیح و بخشپذیری آن بر \(4\) باشد، میتوان همین چهار حالت را بررسی کرد.
به همین ترتیب، نسبت به پیمانه \(m\)، حالتهای ممکن عبارتاند از:
$$ n\equiv0,1,\ldots,m-1\pmod m $$
اثبات با تفکیک حالات و کمیتنماها
این روش بهخصوص برای گزارههای کلی نیز مفید است. فرض کنید میخواهیم نشان دهیم:
$$ \forall x\in D,\;P(x) $$
اگر بتوانیم دامنه \(D\) را به زیرمجموعههایی تقسیم کنیم:
$$ D=D_1\cup D_2\cup\cdots\cup D_n $$
و برای هر \(i\) نشان دهیم:
$$ \forall x\in D_i,\;P(x) $$
آنگاه \(P(x)\) برای همه \(x\in D\) برقرار است.
شرط مهم این است که اجتماع حالتها کل دامنه را پوشش دهد:
$$ D\subseteq D_1\cup D_2\cup\cdots\cup D_n $$
اگر حالتها زیرمجموعههایی از خود \(D\) باشند، معمولاً این رابطه به شکل برابری نوشته میشود.
اشتباهات رایج در اثبات با تفکیک حالات
۱. بررسی نکردن همه حالات
مهمترین خطا این است که چند حالت انتخاب کنیم، اما یک یا چند وضعیت ممکن را فراموش کنیم. در این صورت اثبات ناقص است.
۲. فرض کردن نادرست اینکه حالات دوگانهاند
برای هر مسئلهای نمیتوان فقط دو حالت انتخاب کرد. اگر مسئله به سه یا چهار حالت نیاز دارد، باید همه آنها بررسی شوند.
۳. استفاده از حالتهای بیش از حد پیچیده
گاهی میتوان مسئله را به دو حالت ساده تقسیم کرد، اما به اشتباه آن را به تعداد زیادی حالت تبدیل میکنیم. این کار اثبات را طولانی و احتمال خطا را بیشتر میکند.
۴. نتیجهگیری از یک حالت
اگر هدف اثبات یک گزاره کلی باشد، اثبات آن فقط در یک حالت کافی نیست؛ مگر اینکه همان حالت تنها حالت ممکن باشد.
۵. نامشخص بودن دلیل انتخاب حالتها
بهتر است در آغاز اثبات مشخص کنیم چرا این حالتها تمام امکانات را پوشش میدهند. برای مثال میتوان نوشت:
«هر عدد صحیح یا زوج است یا فرد؛ بنابراین دو حالت زیر را بررسی میکنیم.»
۶. اشتباه گرفتن اثبات exhaustive با آزمون چند مثال
بررسی چند مثال تصادفی یک اثبات نیست. در اثبات exhaustive باید نشان دهیم که فهرست موارد بررسیشده تمام موارد ممکن را در بر میگیرد.
چگونه یک اثبات با تفکیک حالات خوب بنویسیم؟
- گزاره و دامنه متغیرها را دقیق مشخص کنید.
- دلیل نیاز به تفکیک حالات را پیدا کنید.
- حالتهایی انتخاب کنید که تمام امکانات را پوشش دهند.
- حالتها را واضح و جداگانه عنوانگذاری کنید.
- در هر حالت فقط از فرضهای مجاز همان حالت و فرضهای اصلی مسئله استفاده کنید.
- در هر حالت، نتیجه موردنظر را بهطور کامل ثابت کنید.
- در پایان صریحاً بیان کنید که همه حالات ممکن بررسی شدهاند.
نکات مهم درباره تعداد حالات
تعداد حالات به ساختار مسئله بستگی دارد و عدد ثابتی ندارد. یک مسئله ممکن است با دو حالت حل شود، مسئلهای دیگر به سه حالت نیاز داشته باشد و مسئلهای دیگر به ده حالت.
نکته مهم این نیست که تعداد حالات کم باشد؛ بلکه باید تعداد آنها قابل مدیریت باشد و هر حالت اطلاعاتی فراهم کند که اثبات را سادهتر کند.
در بعضی مسائل میتوان حالتهای مختلف را با یک استدلال مشترک ترکیب کرد. این کار باعث میشود اثبات کوتاهتر شود بدون اینکه اعتبار آن کاهش پیدا کند.
آیا حالتها باید مستقل باشند؟
خیر. همانطور که گفته شد، حالتها میتوانند همپوشان باشند. شرط منطقی اصلی این است که برای هر وضعیت موردنظر، دستکم یکی از حالتها برقرار باشد.
با این حال، در نوشتن یک اثبات آموزشی بهتر است تا حد امکان حالتها ساده، روشن و ترجیحاً جدا از یکدیگر باشند. حالتهای مجزا معمولاً خواننده را راحتتر متقاعد میکنند که هیچ وضعیتی فراموش نشده است.
ترکیب تفکیک حالات با سایر روشهای اثبات
اثبات با تفکیک حالات الزاماً یک روش کاملاً جدا از سایر روشها نیست. میتوان از آن بهعنوان چارچوب اصلی استفاده کرد و داخل هر حالت از روش دیگری بهره گرفت.
برای مثال:
- در هر حالت میتوان از اثبات مستقیم استفاده کرد.
- در یک حالت میتوان از برهان خلف استفاده کرد.
- در مسائل مربوط به اعداد طبیعی، ممکن است یک یا چند حالت با استقرا بررسی شوند.
- در مسائل منطقی، میتوان حالتها را با استفاده از گزارهها و همارزیهای منطقی مشخص کرد.
بنابراین تفکیک حالات را بهتر است یک ابزار انعطافپذیر برای سازماندهی استدلال بدانیم.
کاربردهای اثبات با تفکیک حالات
این روش در شاخههای مختلف ریاضیات دیده میشود، از جمله:
- نظریه اعداد و بررسی زوجیت و بخشپذیری
- حساب پیمانهای
- جبر و بررسی علامت عبارتها
- حل مسائل شامل قدرمطلق
- نامساویها
- توابع چندبخشی
- منطق ریاضی
- ریاضیات گسسته
- ترکیبیات و استدلالهای ساختاری
در دورههای دانشگاهی آموزش اثبات نیز تفکیک حالات در کنار روشهایی مانند اثبات مستقیم، برهان خلف، عکس نقیض و استقرا بهعنوان یکی از تکنیکهای استاندارد اثبات آموزش داده میشود.
یک الگوی آماده برای نوشتن اثبات با تفکیک حالات
برای استفاده عملی میتوان از الگوی زیر کمک گرفت:
$$ \begin{aligned} &\text{میخواهیم }P\text{ را ثابت کنیم.}\\ &\text{حالتهای ممکن را به صورت }C_1,C_2,\ldots,C_n\text{ در نظر میگیریم.}\\ &\text{این حالتها همه امکانات ممکن را پوشش میدهند.}\\ &\text{حالت اول: }C_1\text{ و اثبات }P.\\ &\text{حالت دوم: }C_2\text{ و اثبات }P.\\ &\vdots\\ &\text{حالت }n:\;C_n\text{ و اثبات }P.\\ &\therefore P \end{aligned} $$
در نوشتار رسمی بهتر است به جای عبارت کوتاه «در همه حالات درست است»، دقیقاً مشخص شود که چرا حالات کاملاند و چگونه در هر یک از آنها نتیجه به دست آمده است.
جمعبندی
اثبات با تفکیک حالات روشی برای اثبات یک گزاره است که در آن وضعیت مسئله به چند حالت تقسیم میشود و سپس گزاره موردنظر در هر حالت بهطور جداگانه اثبات میشود.
مهمترین اصل این روش آن است که حالتهای انتخابشده باید همه امکانات مسئله را پوشش دهند. اگر این شرط برقرار باشد و گزاره در هر حالت درست باشد، گزاره در حالت کلی نیز درست خواهد بود.
شکل منطقی عمومی روش را میتوان چنین خلاصه کرد:
$$ \left(C_1\lor C_2\lor\cdots\lor C_n\right) \land \bigwedge_{i=1}^{n}(C_i\rightarrow P) \Longrightarrow P $$
زوج و فرد بودن اعداد، علامت متغیرها، باقیمانده تقسیم، قدرمطلق و توابع چندبخشی از موقعیتهایی هستند که این روش در آنها بسیار طبیعی است.
در نهایت، هدف از تفکیک حالات صرفاً زیاد کردن تعداد بخشهای اثبات نیست؛ بلکه باید با انتخاب درست حالتها، مسئلهای پیچیده را به چند مسئله سادهتر تبدیل کرد. اگر تعداد حالتها بیش از حد زیاد شود یا تقسیمبندی سودی برای استدلال نداشته باشد، بهتر است روشهای دیگر اثبات نیز بررسی شوند.
موضوعات مرتبط
برای مطالعه روشهای مختلف اثبات و مفاهیم منطقی مرتبط، موضوعات زیر پیشنهاد میشوند:
منابع
این مقاله با بررسی و تطبیق منابع دانشگاهی و کتابهای معتبر روشهای اثبات تهیه شده است. تاریخ بررسی منابع: ۲۲ مرداد ۱۴۰۵.
- Kenneth H. Rosen، Discrete Mathematics and Its Applications، ویرایش هشتم، McGraw-Hill، 2019. این منبع اثبات با تفکیک حالات را در بخش روشهای اثبات معرفی میکند و بر ضرورت پوشش همه حالات ممکن تأکید دارد.
مشاهده منبع در McGraw Hill
- D. A. Kouba، University of California, Davis، Basic Proof Methods I: Direct Proof, Proof by Cases, and Proof by Working Backward. این منبع دانشگاهی ساختار عملی اثبات با تفکیک حالات و نمونههایی درباره زوج و فرد و قدرمطلق را ارائه میکند.
مشاهده منبع در University of California, Davis
- Emory University، Math Center، Proof by Cases. این منبع مفهوم پوشش همه حالات و نمونهای از بررسی باقیماندههای تقسیم بر \(3\) را توضیح میدهد.
مشاهده منبع در Emory University
- University of Illinois Urbana-Champaign، CS 173 Lectures: Proofs II. این منبع دانشگاهی تفکیک حالات را برای وضعیتی که اطلاعات موجود شامل دو یا چند امکان است توضیح میدهد و بر پوشش همه امکانات تأکید دارد.
مشاهده منبع در University of Illinois
- Discrete OpenMathBooks، Proofs — Proof by Cases. این منبع آموزشی دانشگاهیمحور، تعریف عمومی تفکیک حالات و مثالهایی از کاربرد آن برای اعداد صحیح را ارائه میکند.
مشاهده منبع در OpenMathBooks
- Stony Brook University، Discrete Mathematics — Proof Techniques. این منبع، اثبات با تفکیک حالات را در کنار سایر روشهای استاندارد اثبات در ریاضیات گسسته قرار میدهد و مثالهای عددی ارائه میکند.
مشاهده منبع در Stony Brook University
- Sam Buss، University of California, San Diego، Proofs. این منبع ساختار منطقی تفکیک حالات و امکان استفاده از هر تعداد حالت را توضیح میدهد.
مشاهده منبع در UC San Diego