برهان عکس نقیض

با نفی تالی اشتباه نشود.

در ریاضیات، برهان عکس نقیض (به انگلیسی: Proof by contrapositive) یک قاعدهٔ استنتاج است که در اثبات‌های ریاضی استفاده می‌شود، که در آن گزارهٔ شرطی از عکس نقیض آن استنباط می‌شود. یک گزاره و عکس نقیض آن، از نظر منطقی هم‌ارز هستند، به این معنا که اگر گزاره درست باشد، عکس نقیض آن نیز درست است و بالعکس. به عبارت دیگر، در برهان عکس نقیض، نتیجهٔ «اگر $A$، آنگاه $B$» با ساختن دلیلی برای ادعای «اگر نقیض $B$، آنگاه نقیض $A$» استنتاج می‌شود. در اغلب موارد، این رویکرد در صورتی ترجیح داده می‌شود که اثبات عکس نقیض گزاره، آسان‌تر از اثبات خود گزارهٔ شرطی اصلی باشد.

به‌طور منطقی، اعتبار برهان عکس نقیض را می‌توان با استفاده از جدول ارزش زیر نشان داد، که در آن نشان داده شده‌است که $p\to q$ و $\neg q\to \neg p$ در همهٔ حالت‌ها، ارزش‌های درست یکسانی را به‌اشتراک می‌گذارند:

$p$	$q$	$\neg p$	$\neg q$	$p\to q$	$\neg q\to \neg p$
د	د	ن	ن	د	د
د	ن	ن	د	ن	ن
ن	د	د	ن	د	د
ن	ن	د	د	د	د

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

برهان خلف: فرض کنید $\neg A$ درست است، $\neg A\to B$ نادرست است، بنابراین $\neg A$ نادرست است و $A$ درست است.

برهان عکس نقیض: برای اثبات درستی $A\to B$، درستی گزارهٔ عکس نقیض آن که $\neg B\to \neg A$ است را ثابت کنید.

مثال

فرض کنید $x$ یک عدد صحیح باشد.

برای اثبات: اگر $x^{2}$ زوج باشد، $x$ زوج است.

اگر چه می‌توان آن را به‌روش اثبات مستقیم اثبات کرد، اما برای اثبات این گزاره، از برهان عکس نقیض استفاده می‌کنیم. عکس نقیض گزارهٔ بالا، گزارهٔ زیر است:

اگر $x$ زوج نباشد، $x^{2}$ زوج نیست.

این گزارهٔ دوم به‌این شکل می‌تواند اثبات شود: $x$ زوج نیست، پس $x$ فرد است و حاصل‌ضرب دو عدد فرد، فرد است، از این رو، $x\cdot x=x^{2}$ فرد است؛ بنابراین $x^{2}$ زوج نیست و درستی عکس نقیض گزاره ثابت می‌شود.

پس از اثبات درستی عکس نقیض گزاره، می‌توانیم نتیجه بگیریم که گزارهٔ اصلی نیز درست است.

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

• عکس نقیض
• نفی تالی
• تعلیق به محال
• برهان خلف: رابطه با سایر تکنیک‌های اثبات.