برهان خلف

برهان خُلف (به انگلیسی: Proof by contradiction) یکی از روش‌های اثبات در برهان و منطق است. این روش اثبات غیرمستقیم نیز نامیده می‌شود. در روش برهان خلف، برای آنکه ثابت کنیم قضیه‌ای درست است، ثابت می‌کنیم که خلاف آن قضیه، یعنی نقیض آن، نادرست و چنین فرضی منجر به تناقض است. عبارت انگلیسی «Proof by Contradiction» به معنی «اثبات با رسیدن به تناقض» به‌نوعی تعریف آن نیز هست. همچنین برهان خلف به عنوان «اثبات غیرمستقیم»، «اثبات با فرض خلاف» و تعلیق به محال نیز شناخته می‌شود.

برهان خلف معمولاً در اثبات عکس یک قضیه به‌کار می‌رود و مورد استفاده در قضیه‌های دوشرطی است.

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

روش اثبات با برهان خلف

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

ساختار برهان خلف

برهان خلف از دو استدلال قیاسی تشکیل می‌شود و یک قیاس مرکب است. در استدلال نخست، ما می‌گوئیم که:

اگر $P$ درست نباشد، ${\mathord {\sim }}P$ درست است.

اگر ${\mathord {\sim }}P$ درست باشد، ${\mathord {\sim }}Q$ درست است.

پس اگر $P$ درست نباشد، ${\mathord {\sim }}Q$ درست است.

نتیجهٔ این استدلال، خود مقدمهٔ قیاس استثنایی دیگری می‌شود. در این قیاس می‌گوئیم:

اگر $P$ درست نباشد، ${\mathord {\sim }}Q$ درست است.

اما در واقع $Q$ درست است (بنا بر فرض قبلی یا چون یکی از اصول موضوع ماست).

پس فرض خلف باطل و $P$ درست است.

مثال‌ها

• ثابت کنید که «ریشۀ دوم ۲، گنگ است».

این یک مثال معروف و قدیمی از اثبات با برهان خلف می‌باشد. به برهان خلف فرض کنید که ${\sqrt {2}}$ گنگ نباشد، یعنی گویا باشد. پس می‌توانیم آن را به‌صورت ${\sqrt {2}}={\frac {a}{b}}$ بنویسیم که $a$ و $b$ اعدادی صحیح هستند و $b\neq 0$. همچنین $a$ و $b$ تا حد امکان ساده شده‌اند و در واقع نسبت به هم اول هستند. از ${\sqrt {2}}={\frac {a}{b}}$ نتیجه می‌شود:

${\sqrt {2}}={\frac {a}{b}}\Rightarrow 2={\frac {a^{2}}{b^{2}}}\Rightarrow 2b^{2}=a^{2}$

از اینجا نتیجه می‌شود که $a^{2}$ زوج است، در نتیجه $a$ نیز زوج است (زیرا اگر $a$ فرد باشد، آنگاه $a^{2}$ هم فرد می‌شود). چون $a$ زوج است، پس به شکل $a=2k$ قابل نوشتن است که $k$ عددی صحیح است. داریم:

$2b^{2}=a^{2}\Rightarrow 2b^{2}=(2k)^{2}\Rightarrow 2b^{2}=4k^{2}\Rightarrow b^{2}=2k^{2}$

از اینجا نتیجه می‌شود که $b^{2}$ زوج است، در نتیجه $b$ نیز زوج است. از آنجایی که $a$ و $b$ هر دو اعدادی زوج هستند، پس ساده می‌شوند و نسبت به هم اول نیستند، اما این در تناقض با فرض ماست که فرض کرده بودیم که $a$ و $b$ نسبت به هم اول هستند. پس فرض خلف باطل شد و در نتیجه ${\sqrt {2}}$ گنگ است. $\blacksquare$

• ثابت کنید که «تعداد اعداد اول، نامتناهی است».

قضیۀ اقلیدس بیان می‌کند که «تعداد اعداد اول، نامتناهی است». در اصول اقلیدس، این قضیه در کتاب نهم، گزارۀ 20 بیان شده‌است. به برهان خلف فرض کنید که تعداد اعداد اول، نامتناهی نباشد. یعنی متناهی و محدود باشد و تنها $n$ عدد اول به شکل $p_{1},\ldots ,p_{n}$ داشته باشیم. حاصل‌ضرب این $n$ عدد اول را $P$ می‌نامیم:

$P=p_{1}\cdot \ldots \cdot p_{n}$

سپس حاصل‌جمع آن‌ها با یک را $Q$ می‌نامیم: $Q=P+1$. چون $Q$ از همۀ اعداد اول $p_{1}$ تا $p_{n}$ بزرگ‌تر است، پس طبق فرض خلف، $Q$ نمی‌تواند اول باشد. در نتیجه مرکب است. از آنجایی که هر عدد مرکب حداقل یک شمارندۀ اول دارد، پس $Q$ باید بر یکی از اعداد اول$p_{1}$ تا $p_{n}$ بخش‌پذیر باشد. این عدد را $p_{i}$ در نظر بگیرید. پس هم $P$ و هم $Q$ بر $p_{i}$ بخش‌پذیر هستند. در نتیجه تفاضل آن‌ها یعنی $Q-P$ نیز بر $p_{i}$ بخش‌پذیر است. اما این ممکن نیست؛ زیرا $Q-P$ برابر با یک است و عدد یک بر هیچ عدد اولی بخش‌پذیر نیست. پس فرض خلف باطل شد و در نتیجه تعداد اعداد اول، نامتناهی است. $\blacksquare$

• ثابت کنید که «تجزیۀ هر عدد طبیعی به عوامل اول، صرف نظر از ترتیب عوامل یکتا است».

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

${\begin{aligned}s&=p_{1}p_{2}\cdots p_{m}\\&=q_{1}q_{2}\cdots q_{n}\end{aligned}}$

که $p_{1}$ تا $p_{m}$ و $q_{1}$ تا $q_{n}$ اعدادی اول هستند. همچنین هر $p_{i}$ باید از هر $q_{j}$ متمایز باشد؛ زیرا در غیر این صورت اگر مثلاً $p_{i}=q_{j}$، آنگاه:

$t={\frac {s}{p_{i}}}={\frac {s}{q_{j}}}$

که یعنی عددی مانند $t$ وجود دارد که کوچک‌تر از $s$ است و دو تجزیۀ متفاوت دارد، در حالی که چنین نیست و طبق فرض خلف، $s$ کوچک‌ترین عددی که که به دو صورت مختلف به اعداد اول تجزیه می‌شود. پس برای هر $i$ از یک تا $m$ و هر $j$ از یک تا $n$، داریم: $p_{i}\neq q_{j}$. پس بدون آسیب به کلیت مسئله، فرض کنید که $p_{1}<q_{1}$. سپس تعریف می‌کنیم:

$P=p_{2}\cdots p_{m},\ Q=q_{2}\cdots q_{n}$

در نتیجه داریم: $s=p_{1}P=q_{1}Q$. سپس می‌نویسیم:

$\left.{\begin{array}{l}s-p_{1}Q=q_{1}Q-p_{1}Q=(q_{1}-p_{1})Q\\s-p_{1}Q=p_{1}P-p_{1}Q=(P-Q)p_{1}\end{array}}\right\rbrace \Longrightarrow (q_{1}-p_{1})Q=(P-Q)p_{1}$

همچنین هر دوی $(q_{1}-p_{1})Q$ و $(P-Q)p_{1}$، چون برابر با $s-p_{1}Q$ هستند، در نتیجه از $s$ کوچک‌تر می‌باشند و از آنجایی که هر عدد کوچک‌تر از $s$، تجزیۀ یکتا دارد، پس هر دوی $(q_{1}-p_{1})Q$ و $(P-Q)p_{1}$ دارای تجزیۀ یکتا هستند و چون با هم برابرند، در نتیجه هر عاملی که در $(P-Q)p_{1}$ می‌باشد، باید در $(q_{1}-p_{1})Q$ هم باشد. بنابراین $p_{1}$ باید یا در تجزیۀ $Q$ وجود داشته باشد و یا در تجزیۀ $(q_{1}-p_{1})$. اما هر دو حالت غیرممکن هستند؛ زیرا نشان دادیم که برای هر $i$ از یک تا $m$ و هر $j$ از یک تا $n$، داریم $p_{i}\neq q_{j}$، پس $p_{1}$ در تجزیۀ $Q$ نمی‌تواند وجود داشته باشد و اگر در تجزیۀ $(q_{1}-p_{1})$ باشد، آنگاه داریم:

$p_{1}\mid (q_{1}-p_{1})\Rightarrow q_{1}-p_{1}=p_{1}k\ \ (k\in \mathbb {Z} )\Rightarrow q_{1}=p_{1}k+p_{1}=p_{1}(k+1)\Rightarrow p_{1}\mid q_{1}$

که یعنی $q_{1}$ بر $p_{1}$ بخش‌پذیر است، اما از آنجایی که $q_{1}$ و $p_{1}$ هر دو اعدادی اول و متمایز هستند، چنین چیزی غیرممکن می‌باشد. پس فرض خلف باطل شد و در نتیجه تجزیۀ هر عدد طبیعی به اعداد اول، صرف نظر از ترتیب عوامل یکتا است. $\blacksquare$

جستارهای وابسته

• اصل طرد شق ثالث
• اصل امتناع تناقض
• نزول نامتناهی
• نفی تالی

منابع

المنطق، محمدرضا مظفر، بحث قیاس خلف