برهان خلف: اثبات با فرض نادرستی حکم و رسیدن به تناقض

برهان خلف: فرمول ساده برای کشف تناقض‌ها (همراه با مثال‌های دبیرستانی)

ماهیت برهان خلف: از فرض نادرستی تا رسیدن به پارادوکس

برهان خلف که گاهی «اثبات با فرض خلاف» نیز نامیده می‌شود، بر پایه یک اصل منطقی به نام «قانون طرد شق ثالث» استوار است¹. این قانون می‌گوید یک گزاره یا درست است یا نادرست، راه سومی وجود ندارد. در این روش، به جای اثبات مستقیم درستی حکم $Q$، نشان می‌دهیم که فرض نادرستی $Q$ (یعنی $\neg Q$) به یک تناقض منطقی می‌انجامد. این تناقض می‌تواند به شکل یک عبارت و نقیض آن باشد، یا به شکلی که یک حقیقت مسلم ریاضی را نقض کند.

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

مراحل گام‌به‌گام اجرای برهان خلف در مسائل عدد صحیح

برای اجرای درست برهان خلف، چهار مرحله اصلی را دنبال کنید:

• مرحله ۱: گزاره مورد نظر را به شکل «اگر $P$ آن‌گاه $Q$» بنویسید.
• مرحله ۲: فرض کنید که $Q$ نادرست است (یعنی نقیض $Q$ را بگیرید).
• مرحله ۳: با استفاده از قواعد منطقی و قضایای شناخته شده، از این فرض نتیجه‌گیری کنید تا به یک تناقض آشکار برسید (مثلاً $k$ هم زوج باشد هم فرد).
• مرحله ۴: از آنجا که تناقض غیرقابل قبول است، فرض مرحله ۲ رد می‌شود؛ بنابراین $Q$ درست است.

به عنوان یک مثال عینی: قضیه «اگر $n^2$ زوج باشد، آن‌گاه $n$ زوج است (برای هر عدد صحیح $n$)» را در نظر بگیرید. فرض خلاف: $n$ فرد است. پس $n=2k+1$. آن‌گاه $n^2 = (2k+1)^2 = 4k^2+4k+1 = 2(2k^2+2k)+1$ که فرد است. اما فرض کردیم $n^2$ زوج باشد. تناقض: همزمان زوج و فرد بودن. بنابراین فرض خلاف رد می‌شود و $n$ زوج است.

مقایسه روش مستقیم و غیرمستقیم در اثبات‌های جبری

کاربرد عملی: اثبات نامتناهی بودن اعداد اول با برهان خلف

یکی از مشهورترین کاربردهای برهان خلف، اثبات اقلیدس برای نامتناهی بودن اعداد اول است. فرض کنید بر خلاف آن، تعداد اعداد اول متناهی باشد. آنها را به صورت $p_1, p_2, …, p_k$ فهرست می‌کنیم. عدد $N = p_1 \times p_2 \times … \times p_k + 1$ را در نظر بگیرید. این عدد بر هیچ یک از اعداد اول $p_1$ تا $p_k$ بخش‌پذیر نیست (چون باقیمانده $1$ می‌آید). بنابراین $N$ یا خودش یک عدد اول جدید است، یا دارای مقسوم‌علیه اولی خارج از آن مجموعه است. در هر دو صورت، عدد اول جدیدی پیدا کردیم که در فهرست نبوده است. این با فرض متناهی بودن تناقض دارد. پس تعداد اعداد اول نامتناهی است.

چالش‌های مفهومی در درک برهان خلف

جمع‌بندی و نتیجه نهایی

پاورقی

¹ قانون طرد شق ثالث (Law of Excluded Middle): اصلی منطقی که می‌گوید برای هر گزاره‌ای، آن گزاره یا نقیضش همواره درست است؛ یعنی $P \vee \neg P$ یک tautology است.

² نقیض (Negation): گزاره‌ای که درستی آن در تضاد با درستی گزاره اصلی باشد. اگر $P$ درست باشد، نقیض آن $\neg P$ نادرست است و برعکس.

³ اعداد گنگ (Irrational Numbers): اعدادی حقیقی که نمی‌توان آنها را به صورت کسر $\frac{a}{b}$ (با $a,b$ صحیح و $b \neq 0$) نوشت، مانند $\sqrt{2}$ یا $\pi$.

⁴ تناقض (Contradiction): حالتی که در آن دو گزاره متضاد $R$ و $\neg R$ همزمان صادق فرض شوند که در منطق کلاسیک غیرممکن است.