مقدمه
در ریاضیات، یک ادعا زمانی بهعنوان قضیه پذیرفته میشود که برای آن استدلالی منطقی و معتبر ارائه شود. روش رسیدن به این استدلال همیشه یکسان نیست. گاهی میتوان از فرض مسئله شروع کرد و مستقیماً به نتیجه رسید؛ گاهی بررسی نقیض نتیجه سادهتر است و گاهی بهترین راه این است که فرض کنیم گزاره موردنظر نادرست است و نشان دهیم این فرض به یک وضعیت ناممکن منجر میشود.
روش اخیر برهان خلف یا اثبات با تناقض نام دارد. در زبان انگلیسی معمولاً از اصطلاح Proof by Contradiction و در سنت ریاضی از عبارت لاتین Reductio ad Absurdum نیز استفاده میشود. در این روش، نقیض گزاره موردنظر را فرض میکنیم و با استدلال منطقی نشان میدهیم که این فرض به تناقض منجر میشود.
اهمیت برهان خلف فقط در حل چند مسئله کلاسیک نیست. این روش در نظریه اعداد، جبر، آنالیز، ترکیبیات و بسیاری از شاخههای ریاضیات برای اثبات نتایجی درباره عدم وجود، ناممکن بودن، گنگ بودن و بینهایت بودن به کار میرود.
پیشنیازهای برهان خلف
برای درک برهان خلف، آشنایی با چند مفهوم ساده از منطق ریاضی ضروری است. مهمترین آنها گزاره، نقیض گزاره، گزاره شرطی و تناقض هستند.
اگر \(P\) یک گزاره باشد، نقیض آن را با \( \lnot P \) نشان میدهیم. نقیض \(P\) گزارهای است که ارزش صدق آن دقیقاً مخالف \(P\) است.
یک تناقض، وضعیتی منطقی است که در آن یک گزاره و نقیض آن همزمان برقرار باشند. نمایش نمادین رایج چنین وضعیتی عبارت است از:
$$ C \land \lnot C $$
یعنی هم \(C\) و هم \( \lnot C \) درست باشند. در منطق کلاسیک، چنین وضعیتی ناممکن است.
برای مطالعه مفاهیم پایه میتوانید به گزاره و نقیض گزاره مراجعه کنید.
تعریف دقیق برهان خلف
فرض کنید \(P\) گزارهای باشد که میخواهیم درستی آن را ثابت کنیم. در برهان خلف، ابتدا نقیض \(P\)، یعنی \( \lnot P \)، را بهعنوان فرض موقت در نظر میگیریم. سپس با استفاده از فرضهای مسئله، تعریفها، قضایا و قوانین استدلال، نتیجهای به دست میآوریم که با یک حقیقت پذیرفتهشده ناسازگار است؛ یعنی به تناقض میرسیم.
ساختار کلی روش را میتوان به صورت زیر نشان داد:
$$ \lnot P ;\Longrightarrow; \text{تناقض} $$
بنابراین فرض \( \lnot P \) نمیتواند درست باشد. در منطق کلاسیک، از نادرستی نقیض \(P\) نتیجه میشود که \(P\) درست است:
$$ \lnot(\lnot P) \equiv P $$
نکته مهم این است که در برهان خلف، صرفاً ادعا نمیکنیم که «فرض خلف غلط است». باید یک زنجیره استدلال معتبر ارائه شود که نشان دهد پذیرش نقیض گزاره واقعاً به تناقض منجر میشود.
ایده شهودی برهان خلف
تصور کنید میخواهیم ثابت کنیم «هیچ عدد صحیحی بزرگتر از همه اعداد صحیح نیست». به جای اینکه بخواهیم مستقیماً همه اعداد صحیح را بررسی کنیم، خلاف آن را فرض میکنیم: فرض کنید یک بزرگترین عدد صحیح وجود دارد و آن را \(N\) بنامیم.
اما \(N+1\) نیز یک عدد صحیح است و از \(N\) بزرگتر است:
$$ N+1>N $$
بنابراین فرض وجود بزرگترین عدد صحیح، ما را به وضعیتی میرساند که هم \(N\) بزرگترین عدد صحیح است و هم عدد صحیح بزرگتری از آن وجود دارد. این ناسازگاری نشان میدهد فرض اولیه نادرست بوده است.
ساختار منطقی برهان خلف
میتوان برهان خلف را در چند گام استاندارد خلاصه کرد:
- گزارهای را که میخواهیم ثابت کنیم مشخص میکنیم.
- نقیض دقیق آن گزاره را مینویسیم.
- نقیض گزاره را بهصورت فرض موقت در نظر میگیریم.
- با استفاده از استدلالهای معتبر، نتایج لازم را استخراج میکنیم.
- به یک تناقض میرسیم.
- نتیجه میگیریم که فرض نقیض نمیتواند درست باشد.
- در نتیجه، گزاره اصلی درست است.
بنابراین مهمترین مرحله این روش، نقیض کردن دقیق گزاره و سپس مشخص کردن محل تناقض است.
برهان خلف برای گزارههای شرطی
یکی از مهمترین نکات در استفاده از برهان خلف زمانی است که گزاره موردنظر به شکل شرطی باشد:
$$ P \rightarrow Q $$
نقیض یک گزاره شرطی به صورت زیر است:
$$ \lnot(P\rightarrow Q)\equiv P\land\lnot Q $$
بنابراین برای اثبات \(P\rightarrow Q\) با برهان خلف، باید فرض کنیم:
$$ P\land\lnot Q $$
یعنی هم \(P\) را برقرار در نظر میگیریم و هم فرض میکنیم \(Q\) برقرار نیست. سپس نشان میدهیم این دو فرض، همراه با سایر اطلاعات مسئله، به تناقض منجر میشوند.
این نکته بسیار مهم است؛ زیرا یکی از خطاهای رایج این است که برای اثبات \(P\rightarrow Q\)، فقط \( \lnot Q \) را فرض کنیم. در برهان خلف، نقیض کل گزاره شرطی برابر با \(P\land\lnot Q\) است، نه صرفاً \( \lnot Q \).
برهان خلف و برهان عکس نقیض چه تفاوتی دارند؟
برهان خلف و برهان عکس نقیض ممکن است در بعضی مسائل بسیار شبیه به نظر برسند، اما ساختار منطقی آنها متفاوت است.
برای گزاره شرطی
$$ P\rightarrow Q $$
در برهان عکس نقیض، گزاره همارز زیر را اثبات میکنیم:
$$ \lnot Q\rightarrow\lnot P $$
اما در برهان خلف، نقیض کل گزاره را فرض میکنیم:
$$ P\land\lnot Q $$
سپس از این فرض به تناقض میرسیم.
| روش |
فرض یا نقطه شروع |
هدف میانی |
| اثبات مستقیم |
\(P\) |
رسیدن به \(Q\) |
| عکس نقیض |
\(\lnot Q\) |
رسیدن به \(\lnot P\) |
| برهان خلف |
\(P\land\lnot Q\) |
رسیدن به تناقض |
چه زمانی برهان خلف انتخاب مناسبی است؟
برهان خلف برای همه مسائل بهترین روش نیست. انتخاب روش اثبات به ساختار مسئله بستگی دارد. اگر فرض نادرستی گزاره خیلی سریع به یک تناقض روشن منجر شود، برهان خلف میتواند انتخاب بسیار مناسبی باشد.
این روش معمولاً در موقعیتهای زیر سودمند است:
- هدف، اثبات عدم وجود یک شیء یا وضعیت باشد.
- فرض وجود یک نمونه خلاف، سریعاً به ناسازگاری منجر شود.
- نتیجه موردنظر بیان کند که یک وضعیت نمیتواند رخ دهد.
- فرض نادرست بودن گزاره ساختار سادهتری از خود گزاره ایجاد کند.
- فرض خلاف به یک ویژگی عددی یا ساختاری غیرممکن منجر شود.
مثال حلشده اول: اثبات گنگ بودن \( \sqrt{2} \)
میخواهیم ثابت کنیم \( \sqrt{2} \) عددی گنگ است؛ یعنی نمیتوان آن را به صورت نسبت دو عدد صحیح با مخرج ناصفر نوشت.
فرض خلاف میکنیم که \( \sqrt{2} \) گویا است. بنابراین اعداد صحیح \(a\) و \(b\) وجود دارند بهطوریکه:
$$ \sqrt{2}=\frac{a}{b}, \qquad b\neq0 $$
کسر را در سادهترین شکل در نظر میگیریم؛ یعنی \(a\) و \(b\) مقسومعلیه مشترک بزرگتر از \(1\) ندارند.
دو طرف را به توان دو میرسانیم:
$$ 2=\frac{a^2}{b^2} $$
در نتیجه:
$$ a^2=2b^2 $$
بنابراین \(a^2\) زوج است و در نتیجه \(a\) نیز زوج است. پس برای یک عدد صحیح \(k\) داریم:
$$ a=2k $$
با جایگذاری:
$$ (2k)^2=2b^2 $$ $$ 4k^2=2b^2 $$ $$ b^2=2k^2 $$
بنابراین \(b^2\) نیز زوج است و در نتیجه \(b\) زوج است.
پس هم \(a\) و هم \(b\) زوجاند؛ یعنی هر دو بر \(2\) بخشپذیرند. این نتیجه با فرض اولیه که \(a/b\) در سادهترین شکل نوشته شده بود تناقض دارد.
بنابراین فرض گویا بودن \( \sqrt{2} \) نادرست است و نتیجه میگیریم:
$$ \sqrt{2}\notin\mathbb{Q} $$
مثال حلشده دوم: وجود نداشتن بزرگترین عدد صحیح
میخواهیم نشان دهیم در مجموعه اعداد صحیح، بزرگترین عدد وجود ندارد.
برای برهان خلف، فرض میکنیم یک بزرگترین عدد صحیح وجود دارد و آن را \(N\) مینامیم.
چون \(N\) عدد صحیح است، عدد زیر نیز صحیح است:
$$ N+1\in\mathbb{Z} $$
از طرف دیگر:
$$ N+1>N $$
پس عدد صحیحی بزرگتر از \(N\) وجود دارد؛ در حالی که \(N\) را بزرگترین عدد صحیح فرض کرده بودیم. این تناقض نشان میدهد چنین \(N\)ای وجود ندارد.
بنابراین:
$$ \nexists N\in\mathbb{Z}\quad \forall n\in\mathbb{Z},;n\leq N $$
پس اعداد صحیح بزرگترین عضو ندارند.
مثال حلشده سوم: بینهایت بودن اعداد اول
میخواهیم ثابت کنیم تعداد اعداد اول بینهایت است.
خلاف آن را فرض میکنیم؛ یعنی فرض میکنیم تعداد اعداد اول متناهی است. همه اعداد اول را به صورت زیر فهرست میکنیم:
$$ p_1,p_2,\ldots,p_n $$
عدد زیر را در نظر بگیرید:
$$ N=p_1p_2\cdots p_n+1 $$
عدد \(N\) از هیچیک از اعداد اول فهرستشده بخشپذیر نیست؛ زیرا برای هر \(p_i\) داریم:
$$ N\equiv1\pmod{p_i} $$
از طرف دیگر، هر عدد صحیح بزرگتر از \(1\) دستکم یک مقسومعلیه اول دارد. بنابراین \(N\) باید یک مقسومعلیه اول داشته باشد. این مقسومعلیه اول نمیتواند هیچیک از \(p_1,\ldots,p_n\) باشد.
اما فرض کرده بودیم همین فهرست تمام اعداد اول را در بر میگیرد. پس به تناقض میرسیم و نتیجه میگیریم فرض متناهی بودن تعداد اعداد اول نادرست است.
$$ \text{تعداد اعداد اول بینهایت است.} $$
مثال حلشده چهارم: یک گزاره شرطی
ثابت کنید اگر \(n\) یک عدد صحیح باشد و \(n^2\) زوج باشد، آنگاه \(n\) زوج است:
$$ n^2\text{ زوج}\rightarrow n\text{ زوج} $$
برای برهان خلف، فرض میکنیم گزاره شرطی نادرست است. نقیض یک گزاره شرطی \(P\rightarrow Q\) برابر است با:
$$ P\land\lnot Q $$
بنابراین فرض میکنیم \(n^2\) زوج است، اما \(n\) زوج نیست. چون \(n\) عدد صحیح است، زوج نبودن آن یعنی \(n\) فرد است. پس برای یک عدد صحیح \(k\):
$$ n=2k+1 $$
در نتیجه:
$$ n^2=(2k+1)^2 $$ $$ n^2=4k^2+4k+1 $$ $$ n^2=2(2k^2+2k)+1 $$
بنابراین \(n^2\) فرد است؛ در حالی که فرض کرده بودیم \(n^2\) زوج است. این تناقض نشان میدهد فرض خلف نمیتواند درست باشد.
پس:
$$ \boxed{n^2\text{ زوج}\Rightarrow n\text{ زوج}} $$
انواع تناقض در یک برهان
تناقض الزاماً به این معنا نیست که در پایان دقیقاً عبارت \(C\land\lnot C\) را بنویسیم. تناقض میتواند به شکلهای مختلف ظاهر شود.
تناقض با یک فرض اولیه
ممکن است از فرض خلف نتیجهای به دست آید که مستقیماً با یکی از فرضهای مسئله ناسازگار باشد.
تناقض با یک تعریف
ممکن است نتیجهای حاصل شود که با تعریف یک مفهوم ناسازگار باشد؛ برای مثال فرض کنیم کسری در سادهترین شکل است، اما در پایان نشان دهیم صورت و مخرج آن مقسومعلیه مشترک دارند.
تناقض با یک قضیه پذیرفتهشده
گاهی فرض خلف به نتیجهای منجر میشود که با یک قضیه قبلاً اثباتشده ناسازگار است.
تناقض مستقیم
یکی از سادهترین حالتها رسیدن به عبارتی مانند زیر است:
$$ C\land\lnot C $$
در همه این حالتها نکته اصلی یکسان است: فرضی که برای رسیدن به تناقض استفاده کردهایم نمیتواند درست باشد.
برهان خلف برای اثبات عدم وجود
یکی از کاربردهای مهم برهان خلف، اثبات این است که یک شیء با ویژگی مشخص وجود ندارد.
برای اثبات گزارهای مانند:
$$ \nexists x;P(x) $$
میتوان نقیض آن را فرض کرد:
$$ \exists x;P(x) $$
سپس نشان داد که وجود چنین \(x\)ای به تناقض منجر میشود.
این الگو در اثباتهای مربوط به عدم وجود جواب، ناممکن بودن یک ساختار و بسیاری از مسائل نظری کاربرد دارد.
برهان خلف در گزارههای دارای کمیتنما
وقتی گزاره با کمیتنماها بیان میشود، باید هنگام گرفتن نقیض، ساختار منطقی گزاره را با دقت تغییر داد.
برای نمونه:
$$ \lnot\left(\forall x;P(x)\right) \equiv \exists x;\lnot P(x) $$
و همچنین:
$$ \lnot\left(\exists x;P(x)\right) \equiv \forall x;\lnot P(x) $$
بنابراین اگر گزاره موردنظر به شکل «برای هر \(x\)، ویژگی \(P(x)\) برقرار است» باشد، در برهان خلف باید فرض کنیم دستکم یک \(x\) وجود دارد که \(P(x)\) برای آن برقرار نیست.
در مقابل، برای رد یک گزاره وجودی، نقیض آن یک گزاره کلی است. این موضوع در مسائل منطق ریاضی اهمیت زیادی دارد؛ زیرا نقیض نادرست کمیتنماها میتواند کل برهان را نادرست کند.
برهان خلف و برهان مستقیم
در اثبات مستقیم معمولاً از فرض مسئله شروع میکنیم و با زنجیرهای از استدلالها مستقیماً به نتیجه میرسیم.
برای مثال، برای اثبات یک گزاره شرطی \(P\rightarrow Q\)، در اثبات مستقیم \(P\) را فرض میکنیم و \(Q\) را نتیجه میگیریم.
اما در برهان خلف، هدف این است که نشان دهیم فرض نادرستی گزاره غیرممکن است.
هیچکدام ذاتاً «قویتر» از دیگری نیستند. تفاوت اصلی در مسیر استدلال و مناسب بودن هر روش برای مسئله موردنظر است.
برهان خلف و اثبات با مثال نقض
برهان خلف را نباید با مثال نقض اشتباه گرفت.
مثال نقض برای رد یک گزاره کلی استفاده میشود. اگر گزارهای ادعا کند:
$$ \forall x\in D,;P(x) $$
کافی است یک \(x_0\in D\) پیدا کنیم که:
$$ \lnot P(x_0) $$
اما برهان خلف برای اثبات یک گزاره، نقیض آن را فرض میکند و از این فرض به تناقض میرسد. بنابراین این دو روش از نظر هدف و ساختار منطقی متفاوتاند.
اشتباهات رایج در برهان خلف
۱. فرض کردن چیزی غیر از نقیض گزاره
اولین خطای رایج این است که به جای نقیض دقیق گزاره، یک عبارت مشابه یا فقط بخشی از نقیض آن فرض شود.
برای مثال، اگر هدف اثبات \(P\rightarrow Q\) باشد، نقیض آن:
$$ P\land\lnot Q $$
است، نه صرفاً \( \lnot Q \).
۲. اعلام تناقض بدون نشان دادن آن
عبارت «این فرض متناقض است» بهتنهایی اثبات محسوب نمیشود. باید دقیقاً نشان داده شود کدام دو نتیجه با یکدیگر ناسازگارند یا نتیجه حاصلشده با کدام فرض، تعریف یا قضیه شناختهشده تناقض دارد.
۳. استفاده از فرضهای اضافی
در یک برهان معتبر، نباید برای رسیدن سریعتر به تناقض، فرضی را وارد کنیم که از مسئله یا مقدمات منطقی مجاز به استفاده از آن نیستیم.
۴. اشتباه گرفتن عکس نقیض با خلف
در عکس نقیض، هدف اثبات \( \lnot Q\rightarrow\lnot P \) است؛ در برهان خلف، از \(P\land\lnot Q\) شروع میکنیم و به تناقض میرسیم.
۵. نقیض نادرست کمیتنماها
یکی از خطاهای مهم این است که نقیض \( \forall \) را دوباره \( \forall \) یا نقیض \( \exists \) را دوباره \( \exists \) در نظر بگیریم. در نقیض کمیتنما، نوع کمیت نیز تغییر میکند.
نکات مهم برای نوشتن یک برهان خلف خوب
- ابتدا گزاره دقیق موردنظر را مشخص کنید.
- نقیض منطقی آن را بدون ابهام بنویسید.
- اگر گزاره شرطی است، نقیض کل شرطی را به شکل \(P\land\lnot Q\) در نظر بگیرید.
- تمام فرضهای مسئله را حفظ کنید.
- از تعریفها و قضایای معتبر بهصورت صریح استفاده کنید.
- مشخص کنید تناقض دقیقاً در کدام مرحله ظاهر میشود.
- در پایان روشن کنید که کدام فرض رد شده و چرا گزاره اصلی نتیجه میشود.
- اگر اثبات مستقیم یا عکس نقیض کوتاهتر و روشنتر است، الزاماً از برهان خلف استفاده نکنید.
فرم استاندارد نوشتن برهان خلف
برای یک گزاره ساده \(P\)، میتوان الگوی زیر را به کار برد:
$$ \begin{aligned} &\text{میخواهیم }P\text{ را ثابت کنیم.}\ &\text{فرض کنید }\lnot P\text{ درست باشد.}\ &\text{با استفاده از فرض و حقایق شناختهشده، نتیجه میگیریم:}\ &\qquad C\land\lnot C.\ &\text{این تناقض است.}\ &\therefore \lnot P\text{ نادرست است.}\ &\therefore P\text{ درست است.} \end{aligned} $$
برای گزاره شرطی \(P\rightarrow Q\)، فرم مناسب چنین است:
$$ \begin{aligned} &\text{میخواهیم }P\rightarrow Q\text{ را ثابت کنیم.}\ &\text{فرض کنید }P\land\lnot Q\text{ درست باشد.}\ &\text{از این فرض به تناقض میرسیم.}\ &\therefore P\land\lnot Q\text{ نمیتواند درست باشد.}\ &\therefore P\rightarrow Q. \end{aligned} $$
کاربردهای برهان خلف
برهان خلف در بخشهای مختلف ریاضیات کاربرد دارد. از نمونههای شناختهشده آن میتوان به اثبات گنگ بودن برخی اعداد، اثبات بینهایت بودن اعداد اول، اثبات عدم وجود بعضی ساختارها و اثبات ناممکن بودن برخی حالتها اشاره کرد.
در ریاضیات گسسته، این روش در مباحثی مانند نظریه اعداد، ترکیبیات و استدلالهای مربوط به ساختارهای گسسته حضور پررنگی دارد و در کنار روشهای مستقیم، عکس نقیض و تفکیک حالات آموزش داده میشود.
جمعبندی
برهان خلف روشی برای اثبات یک گزاره است که در آن نقیض گزاره را فرض میکنیم و نشان میدهیم که این فرض به تناقض منجر میشود. از آنجا که فرض نقیض نمیتواند درست باشد، گزاره اصلی درست خواهد بود.
برای یک گزاره ساده \(P\)، ساختار اصلی روش این است:
$$ \lnot P\rightarrow\text{تناقض} $$
و برای گزاره شرطی \(P\rightarrow Q\)، فرض خلف عبارت است از:
$$ P\land\lnot Q $$
تفاوت اصلی این روش با برهان عکس نقیض در این است که عکس نقیض مستقیماً گزاره همارز \( \lnot Q\rightarrow\lnot P \) را اثبات میکند، در حالی که برهان خلف از نقیض گزاره شروع کرده و هدف آن رسیدن به یک تناقض است.
در عمل، انتخاب برهان خلف باید بر اساس ساختار مسئله انجام شود. اگر فرض نادرستی گزاره به یک تناقض روشن و کوتاه منجر شود، این روش میتواند بسیار قدرتمند و طبیعی باشد؛ در غیر این صورت ممکن است اثبات مستقیم یا عکس نقیض انتخاب بهتری باشد.
موضوعات مرتبط
برای مطالعه منظم روشهای اثبات، موضوعات مرتبط زیر پیشنهاد میشوند:
منابع
محتوای این مقاله با تطبیق منابع کتابی و دانشگاهی در زمینه منطق، روشهای اثبات و ریاضیات گسسته تهیه شده است. تاریخ بررسی منابع: ۲۲ مرداد ۱۴۰۵.
منابع کتابی
- Richard Hammack، Book of Proof، بخش Proof by Contradiction، نسخه آنلاین رسمی نویسنده.
- Daniel J. Velleman، How to Prove It: A Structured Approach، ویرایش سوم، Cambridge University Press، 2019.
- Gary Chartrand، Albert D. Polimeni، Ping Zhang، Mathematical Proofs: A Transition to Advanced Mathematics، ویرایش چهارم، Pearson، 2018.
- Kenneth H. Rosen، Discrete Mathematics and Its Applications، ویرایش هشتم، McGraw-Hill Education، 2019.
منابع دانشگاهی و آموزشی
- University of Illinois Urbana-Champaign، منابع آموزشی مربوط به ساختارهای گسسته و اثبات با تناقض.
- University of Cambridge، Department of Computer Science and Technology، منابع آموزشی ریاضیات گسسته، اثباتها، اعداد و مجموعهها.
- Stony Brook University، منابع آموزشی مربوط به تکنیکهای اثبات در ریاضیات گسسته.