مقدمه
در ریاضیات، بسیاری از قضایا به صورت گزاره‌های شرطی بیان می‌شوند؛ یعنی ساختاری مانند «اگر \(P\)، آنگاه \(Q\)». برای اثبات چنین گزاره‌ای همیشه لازم نیست مستقیماً از \(P\) شروع کنیم و به \(Q\) برسیم. گاهی مسیر منطقی ساده‌تر این است که نادرستی نتیجه را فرض کنیم و نشان دهیم که در این صورت فرض اولیه نیز نمی‌تواند درست باشد.
این روش برهان عکس نقیض نام دارد. در زبان انگلیسی از اصطلاح Proof by Contrapositive استفاده می‌شود. ایده اصلی آن بر یک هم‌ارزی منطقی بنیادی استوار است: هر گزاره شرطی \(P\rightarrow Q\) با عکس نقیض خود، یعنی \( \lnot Q\rightarrow\lnot P \)، هم‌ارز است. بنابراین اثبات یکی از این دو، اثبات دیگری را نیز در پی دارد.
برهان عکس نقیض یکی از روش‌های استاندارد اثبات گزاره‌های شرطی است و در کتاب‌های آموزش روش‌های اثبات، منطق ریاضی و ریاضیات گسسته در کنار اثبات مستقیم و برهان خلف آموزش داده می‌شود.
برای مطالعه مفاهیم پایه، می‌توانید ابتدا گزاره و نقیض گزاره را بررسی کنید.
پیش‌نیازهای برهان عکس نقیض
برای استفاده درست از برهان عکس نقیض، باید با چند مفهوم ساده از منطق آشنا باشیم: گزاره، گزاره شرطی، نقیض و هم‌ارزی منطقی.
گزاره شرطی
گزاره‌ای به شکل
$$
P\rightarrow Q
$$
یک گزاره شرطی است. در این عبارت، \(P\) را فرض یا مقدم و \(Q\) را نتیجه یا تالی می‌نامیم.
برای مثال، گزاره زیر را در نظر بگیرید:
$$
\text{اگر }n\text{ بر }4\text{ بخش‌پذیر باشد، آنگاه }n\text{ زوج است.}
$$
در اینجا می‌توان نوشت:
$$
P:\;4\mid n
$$
$$
Q:\;2\mid n
$$
نقیض یک گزاره
اگر \(P\) یک گزاره باشد، نقیض آن را با \( \lnot P \) نشان می‌دهیم. نقیض \(P\) گزاره‌ای است که ارزش صدق آن مخالف ارزش صدق \(P\) است.
برای نمونه، نقیض گزاره «\(n\) زوج است» این است که «\(n\) زوج نیست». برای عدد صحیح، زوج نبودن معادل فرد بودن است؛ بنابراین در این حوزه می‌توان نوشت:
$$
\lnot(2\mid n)\equiv 2\nmid n
$$
البته در هر مسئله باید نقیض گزاره را بر اساس دامنه و تعریف دقیق آن تعیین کرد و نباید صرفاً به شکل ظاهری عبارت اکتفا کرد.
تعریف دقیق برهان عکس نقیض
اگر بخواهیم گزاره شرطی
$$
P\rightarrow Q
$$
را ثابت کنیم، می‌توان به جای آن گزاره
$$
\lnot Q\rightarrow\lnot P
$$
را ثابت کرد. گزاره دوم عکس نقیض گزاره اول نامیده می‌شود.
دلیل معتبر بودن این روش آن است که گزاره شرطی و عکس نقیض آن از نظر منطقی هم‌ارزند:
$$
P\rightarrow Q\equiv\lnot Q\rightarrow\lnot P
$$
بنابراین اگر \( \lnot Q\rightarrow\lnot P \) درست باشد، \(P\rightarrow Q\) نیز درست است.
در عمل، روش کار چنین است: ابتدا گزاره شرطی موردنظر را مشخص می‌کنیم، سپس نقیض نتیجه را فرض می‌کنیم و از آن نشان می‌دهیم که نقیض فرض اولیه برقرار است.
فرمول اصلی برهان عکس نقیض
مهم‌ترین رابطه‌ای که باید به خاطر سپرد عبارت است از:
$$
\boxed{P\rightarrow Q\equiv\lnot Q\rightarrow\lnot P}
$$
این رابطه به این معنا نیست که \(P\rightarrow Q\) و \( \lnot Q\rightarrow\lnot P \) فقط در برخی شرایط با هم برابرند؛ بلکه این دو گزاره در منطق گزاره‌ها هم‌ارزی منطقی دارند.
بنابراین برای اثبات یک گزاره شرطی می‌توان یکی از دو مسیر زیر را انتخاب کرد:
$$
P\rightarrow Q
$$
یا:
$$
\lnot Q\rightarrow\lnot P
$$
اگر مسیر دوم از نظر محاسبات یا ساختار استدلال ساده‌تر باشد، برهان عکس نقیض انتخاب مناسبی است.
برای مطالعه بیشتر درباره مفهوم هم‌ارزی منطقی می‌توانید به هم‌ارزی منطقی مراجعه کنید.
چرا گزاره و عکس نقیض آن هم‌ارزند؟
می‌توان این موضوع را با تبدیل منطقی گزاره شرطی نشان داد. در منطق، گزاره شرطی با عبارت زیر هم‌ارز است:
$$
P\rightarrow Q\equiv\lnot P\lor Q
$$
از طرف دیگر:
$$
\lnot Q\rightarrow\lnot P
\equiv
\lnot(\lnot Q)\lor\lnot P
$$
با استفاده از قانون نقیض مضاعف داریم:
$$
\lnot(\lnot Q)\equiv Q
$$
بنابراین:
$$
\lnot Q\rightarrow\lnot P
\equiv
Q\lor\lnot P
$$
و چون عملگر «یا» جابه‌جایی‌پذیر است:
$$
Q\lor\lnot P\equiv\lnot P\lor Q
$$
در نتیجه:
$$
\boxed{P\rightarrow Q\equiv\lnot Q\rightarrow\lnot P}
$$
این هم‌ارزی پایه منطقی روش عکس نقیض است.
جدول ارزش و اثبات هم‌ارزی عکس نقیض
برای اطمینان بیشتر می‌توان هم‌ارزی را با جدول ارزش بررسی کرد. چهار حالت ممکن برای \(P\) و \(Q\) وجود دارد.
| \(P\) |
\(Q\) |
\(P\rightarrow Q\) |
\(\lnot Q\) |
\(\lnot P\) |
\(\lnot Q\rightarrow\lnot P\) |
| درست |
درست |
درست |
نادرست |
نادرست |
درست |
| درست |
نادرست |
نادرست |
درست |
نادرست |
نادرست |
| نادرست |
درست |
درست |
نادرست |
درست |
درست |
| نادرست |
نادرست |
درست |
درست |
درست |
درست |
ستون‌های \(P\rightarrow Q\) و \( \lnot Q\rightarrow\lnot P \) در تمام حالت‌ها یکسان هستند. بنابراین این دو گزاره از نظر منطقی هم‌ارزند.
مراحل انجام برهان عکس نقیض
برای اثبات گزاره شرطی \(P\rightarrow Q\) با عکس نقیض، می‌توان از مراحل زیر استفاده کرد:
- گزاره شرطی \(P\rightarrow Q\) را دقیق مشخص کنید.
- نقیض نتیجه، یعنی \( \lnot Q \)، را پیدا کنید.
- نقیض فرض، یعنی \( \lnot P \)، را مشخص کنید.
- به جای گزاره اصلی، گزاره \( \lnot Q\rightarrow\lnot P \) را اثبات کنید.
- از تعریف‌ها، قضایا و استدلال‌های معتبر برای رسیدن به \( \lnot P \) استفاده کنید.
- در پایان نتیجه بگیرید که گزاره اصلی \(P\rightarrow Q\) نیز درست است.
نکته مهم این است که برهان عکس نقیض با «فرض نقیض کل گزاره و رسیدن به تناقض» تفاوت دارد. در این روش، ما یک گزاره شرطی هم‌ارز را مستقیماً اثبات می‌کنیم.
مثال حل‌شده اول: اگر \(n^2\) زوج باشد، \(n\) زوج است
می‌خواهیم برای هر عدد صحیح \(n\) ثابت کنیم:
$$
n^2\text{ زوج}\rightarrow n\text{ زوج}
$$
اگر بخواهیم از برهان عکس نقیض استفاده کنیم، ابتدا نقیض نتیجه را در نظر می‌گیریم. نقیض «\(n\) زوج است» یعنی \(n\) زوج نیست. چون \(n\) عدد صحیح است، این عبارت معادل فرد بودن \(n\) است.
بنابراین عکس نقیض گزاره چنین خواهد بود:
$$
n\text{ فرد}\rightarrow n^2\text{ فرد}
$$
اکنون همین گزاره را اثبات می‌کنیم.
چون \(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\) به شکل \(2m+1\) نوشته می‌شود و بنابراین فرد است.
در نتیجه عکس نقیض گزاره ثابت شد:
$$
n\text{ فرد}\rightarrow n^2\text{ فرد}
$$
چون گزاره اصلی و عکس نقیض آن هم‌ارزند، نتیجه می‌گیریم:
$$
\boxed{n^2\text{ زوج}\rightarrow n\text{ زوج}}
$$
این مثال نشان می‌دهد که گاهی اثبات عکس نقیض بسیار طبیعی‌تر از اثبات مستقیم است.
مثال حل‌شده دوم: اگر \(n^2\) بر \(4\) بخش‌پذیر نباشد، \(n\) فرد است
می‌خواهیم ثابت کنیم برای هر عدد صحیح \(n\):
$$
4\nmid n^2\rightarrow n\text{ فرد}
$$
عکس نقیض این گزاره چیست؟
نقیض نتیجه «\(n\) فرد است» عبارت است از «\(n\) زوج است». نقیض فرض نیز عبارت است از «\(4\mid n^2\)». بنابراین عکس نقیض برابر است با:
$$
n\text{ زوج}\rightarrow4\mid n^2
$$
حال فرض کنید \(n\) زوج باشد. بنابراین برای یک عدد صحیح \(k\):
$$
n=2k
$$
پس:
$$
n^2=(2k)^2=4k^2
$$
بنابراین:
$$
4\mid n^2
$$
پس عکس نقیض ثابت شده و در نتیجه گزاره اصلی نیز درست است:
$$
\boxed{4\nmid n^2\rightarrow n\text{ فرد}}
$$
مثال حل‌شده سوم: اگر حاصل‌ضرب دو عدد فرد باشد، هر دو عدد فردند
فرض کنید \(a\) و \(b\) عدد صحیح باشند. می‌خواهیم ثابت کنیم:
$$
ab\text{ فرد}\rightarrow a\text{ و }b\text{ هر دو فردند}
$$
اثبات مستقیم ممکن است، اما عکس نقیض نیز مسیر بسیار روشنی دارد.
نقیض نتیجه «\(a\) و \(b\) هر دو فردند» این است که حداقل یکی از آن‌ها فرد نباشد؛ یعنی:
$$
a\text{ زوج}\lor b\text{ زوج}
$$
نقیض فرض «\(ab\) فرد است» نیز این است:
$$
ab\text{ زوج}
$$
بنابراین عکس نقیض گزاره چنین است:
$$
a\text{ زوج}\lor b\text{ زوج}\rightarrow ab\text{ زوج}
$$
اگر \(a\) زوج باشد، برای عدد صحیحی مانند \(k\) داریم:
$$
a=2k
$$
در نتیجه:
$$
ab=2kb
$$
پس \(ab\) زوج است.
به همین شکل، اگر \(b\) زوج باشد، آنگاه \(ab\) نیز زوج است. بنابراین اگر دست‌کم یکی از \(a\) و \(b\) زوج باشد، حاصل‌ضرب آن‌ها زوج خواهد بود.
پس عکس نقیض درست است و نتیجه می‌گیریم:
$$
\boxed{ab\text{ فرد}\rightarrow a\text{ و }b\text{ هر دو فردند}}
$$
مثال حل‌شده چهارم: اگر \(x^2\) منفی نباشد، چه نتیجه‌ای می‌توان گرفت؟
این مثال نشان می‌دهد که باید هنگام انتخاب روش، ساختار گزاره را به دقت بررسی کرد. گزاره‌ای مانند
$$
x^2<0\rightarrow x\neq0
$$
را در نظر بگیرید.
عکس نقیض آن:
$$
x=0\rightarrow x^2\geq0
$$
است که اثبات آن بسیار ساده است؛ زیرا اگر \(x=0\)، آنگاه:
$$
x^2=0
$$
و در نتیجه:
$$
x^2\geq0
$$
پس عکس نقیض به ما اجازه می‌دهد گزاره‌ای را که ممکن است در شکل اولیه آن کمی نامعمول به نظر برسد، از مسیری بسیار کوتاه اثبات کنیم.
مثال حل‌شده پنجم: یک مثال در نامساوی‌ها
برای هر عدد حقیقی \(x\)، ثابت کنید:
$$
x^2-2x-15\geq0
\rightarrow
x\geq5\lor x\leq-3
$$
اثبات مستقیم این گزاره نیازمند بررسی حالت‌های مختلف است. عکس نقیض آن ساده‌تر است.
نقیض نتیجه عبارت «\(x\geq5\lor x\leq-3\)» است. بنابراین:
$$
\lnot(x\geq5\lor x\leq-3)
\equiv
x<5\land x>-3
$$
نقیض فرض نیز:
$$
x^2-2x-15<0
$$
بنابراین باید ثابت کنیم:
$$
-3