برهان خلف

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

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

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

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

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

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

اگر 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{align}
s
&=p_1 p_2 \cdots p_m \\
&=q_1 q_2 \cdots q_n
\end{align}

که 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 . سپس تعریف می‌کنیم:

P=p_2\cdots p_m,\ Q=q_2\cdots q_n

در نتیجه داریم: s = p_1P = q_1Q. سپس می‌نویسیم:

\left.\begin{array}{l}
  s - p_1Q = q_1Q - p_1Q = (q_1-p_1)Q \\ s - p_1Q = p_1P - p_1Q = (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_1Q هستند، در نتیجه از 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_1k\ \ (k \in \mathbb{Z}) \Rightarrow q_1 = p_1k + p_1 = p_1(k + 1) \Rightarrow p_1 \mid q_1

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

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

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

## منابع

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

رده:برهان‌ها
رده:برهان‌های ریاضیات
رده:شیوه‌های اثبات
رده:قضیه‌ها در حساب گزاره‌ای
رده:قواعد استنتاج