برهان خلف

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

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

اگر ${\displaystyle P}$

اگر ${\displaystyle \sim P}$

پس اگر ${\displaystyle P}$

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

اگر ${\displaystyle P}$

اما در واقع ${\displaystyle Q}$

پس فرض خلف باطل و ${\displaystyle P}$

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

این یک مثال معروف و قدیمی از اثبات با برهان خلف می‌باشد. به برهان خلف فرض کنید که ${\displaystyle \sqrt{2}}$

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

از اینجا نتیجه می‌شود که ${\displaystyle a^2}$

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

از اینجا نتیجه می‌شود که ${\displaystyle b^2}$

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

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

${\displaystyle P=p_1\cdot \dots \cdot p_n}$

سپس حاصل‌جمع آن‌ها با یک را ${\displaystyle Q}$

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

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

که ${\displaystyle p_1}$

${\displaystyle t=\frac{s}{p_i}=\frac{s}{q_j}}$

که یعنی عددی مانند ${\displaystyle t}$

${\displaystyle P=p_2\cdots p_m,Q=q_2\cdots q_n}$

در نتیجه داریم: ${\displaystyle s=p_{1}P=q_{1}Q}$

${\displaystyle \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}\}⟹(q_1-p_1)Q=(P-Q)p_1}$

همچنین هر دوی ${\displaystyle (q_1-p_1)Q}$

${\displaystyle 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}$

که یعنی ${\displaystyle q_1}$

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

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