چندکلامی درباره روشهای عمومی اثبات
ترجمه آزاد مقاله Remarks About Methods of Proof

قصد ما مطرح کردن چند روش ساده و عمومی اثبات است که ممکن است شما بارها از هر کدام استفاده کرده باشید. برای راحتی کار در مثال ها دو تعریف زیر را می آوریم.

تعریف 1: عدد n را زوج گوییم اگر بتوان آنرا به صورت n=2k که k عددی صحیح است، نوشت.
تعریف 2: عدد n را فرد گوییم اگر بتوان آنرا به صورت n=2k+1 که k عددی صحیح است، نوشت.

1. اثبات مستقیم (DIRECT PROOF) :
با فرض های قضیه آغاز می شود و با استنتاج، از آن نتایجی حاصل می شود، بیرون آوردن نتیاج ادامه می یابد تا اینکه به حکم مطلوب برسیم.

قضیه1: اگر n زوج باشد آگاه n^۲ زوج است.
اثبات: n زوج است (فرض) بنابراین عدد صحیحی چون k وجود دارد که n=۲k. بنابراین:

n^۲ = (۲k)^۲ = ۲ (۲k^۲)

و می دانیم 2k^۲ نیز عددی صحیح است بنابراین طبق تعریف1 n^۲ عددی زوج است.

2. اثبات عکس ِ نقیض قضیه به جای خود قضیه. (PROVING THE CONTRAPOSITIVE)
در این روش اثبات، ما می خواهیم نشان دهیم که « اگر A آنگاه B ». به جای آن ما یک قانون معادل آن را نشان می دهیم: « اگر B نقض شود ( Not B)، آنگاه A نقض میشود (Not A) ».

قضیه 2: اگر n^۲ زوج باشد، آنگاه n زوج است.
اثبات: در این مورد n^۲ زوج است 'گزاره A و n زوج است گزاره B می باشد. نشان می دهیم اگر n فرد باشد (نقیض B) آنگاه n^۲ فرد است (نقیض A). به این ترتیب که: می دانیم که عدد صحیحی چون K هست که n=۲k+1. بنابراین:

n^۲ = (۲k+۱)^۲ = ۴k^۲+۲k+۱ = ۲(۲k^۲+k)+۱.

چون k صحیح است پس 2k^۲+k نیز صحیح است. پس ما نشان دادیم که n^۲ فرد است.

 3. اثبات با تناقض (برهان خلف) (PROOF BY CONTRADICTION):

در این روش از برهان، می خواهیم نشان دهیم که اگر A آنگاه B . برای این کار فرض میکنیم خلاف این حکم درست باشد (فرض خلف). یعنی فرض می کنیم که گزاره A درست و گزاره B غلط است. . حالا باید به دنبال یک تناقض بگردیم. این تناقض ممکن است، با فرض قضیه و یا یک حکم بدیهی که از درستی آن مطلع هستیم ولی در فرض مسئله نیست، ایجاد شود. مثلا به این حکم برسیم که 3 کوچکتر از 0 است (تناقض با یک دانسته بدیهی). خوب! به محض اینکه به یک تناقض رسیدیم، نتیجه می گیریم که چیزی که فرض کردیم (فرض خلف) غلط بوده، پس قضیه درسته.

قضیه 3: n و m را اعدا صحیح در نظر میگیریم. اگر n.m زوج باشد، حداقل یکی از اعداد n یا m ، زوج است.

اثبات: فرض میکنیم که n.m زوج است (A) ولی نه m و نه n هیچکدام زوج نیستند (Not B) (فرض خلف). بنابرای ما می توانیم بنویسیم:
عددیهای صحیح k و c وجود دارن که : n=۲k+۱ و m=۲c+۱ . در نتیجه:

n.m = (۲k+۱)(۲c+۱) =  ۴ k.c + ۲k + ۲c +۱ = ۲(۲k.c + k + c) +۱

نکته: این یه نکته کوچولو رو داشته باشید که درستی این روش بر اساس قانون ِطرد ِشِق ِوسط است. این قانون میگه که یک گزاره یا درسته و یا غلط و حالت بینابین یا حالت سومی نداره. این روش اثبات تنها در منطق دو ارزشی پذیرفتنی است. (نگران نباشید. این یعنی تقریبا همه جای ریاضی ای که ما می خوانیم به جز جایی که دقیقا در زمینه منطق های چند ارزشی صحبت میشه.) در این روش میگیم: چون فرض غلط بودن حکم به تناقض می رسه، پس غلط نیست، پس درسته. چون نمیتونه نه درست باشه نه غلط.

برای آشنایی با کامل ترین نوع منطق چند ارزشی (منطق فازی Fuzzy) می تونید به وبلاگ امید ریاضی سر بزنید.

در مواردی می خواهیم نشان دهیم که گزاره S(n) برای تمام اعداد صحیح بزرگتر از عدد صحیحی چون n₀ درست است. برای این منظور باید دو مرحله را انجام دهیم:

 الف) مورد پایه: باید نسان دهیم که S(n₀) ، (یعنی گزاره S(n) در مورد n₀ ) درست است.

ب‌)   فرض استقرائی: فرض میکنیم که S(n) برای یکn > n₀  درست باشد و نشان میدهیم که S(n+۱) نیز درست است.

قضیه 4: برای هر n>=0 و x <> 1 داریم: (علامت <> یعنی مخالف)

۱+ x + x^۲ + … + xⁿ = (xⁿ⁺¹ – ۱)/(x-۱)

اثبات: ابتدا نشان میدهیم که برای مورد پایه درست است. برای n=0 ، S(0) میرساند که

        ۱= (x^0+۱ -۱ )/(x -۱)   که این به روشنی درست است.

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

۱+ x + x^۲ + … + xⁿ = (xⁿ⁺¹ – ۱)/(x-۱)

باید نشان دهیم که:

۱+ x + x^۲ + … + xⁿ  + xⁿ⁺¹ = (x^n+۲ – ۱)/(x-۱)

داریم:

۱+ x + x^۲ + … + xⁿ  + xⁿ⁺¹  =  (xⁿ⁺¹ – ۱)/(x-۱) + xⁿ⁺¹

= ( xⁿ⁺¹ – ۱ + (x-۱).(xⁿ⁺¹) ) / (x-۱)

= ( xⁿ⁺¹ – ۱ + x^n+۲ – xⁿ⁺¹ ) / (x-۱)

= ( x^n+۲ – ۱ ) / (x-۱) .:.

که در اولین تساوی از فرض استقرائی استفاده کردیم و بقیه تساویها، اعمال ساده جبری اند. به این ترتیب قضیه ثابت شد.

نکته: معمولا نشان دادن اینکه حکم برای مورد پایه درست است بسیار بدیهی و ساده است. اما با این وجود این مرحله بسیار مهم است و عدم در نظر گرفتن آن ممکن است به نتایج غلطی منجر شود. برای اینکه مطلبمون زیاد طولانی نشه، روش پنجم اثبات رو هم میگم و مثال هایی در مورد اهمیت مورد پایه در روش استقرا و بعد دو روش غلط اثبات رو برای پست بعدی می گذاریم.

گاهی لازم است نشان دهیم که یک حکم غلط است. برای نشان دادن اینکه یک حکم غلط است، یکی از ملزومات آوردن یک مثال نقض است. مثال زیر را ملاحظه فرمائید:

قضیه 5 (اشتباه): به ازای هر n صحیح، 3n زوج است.

اثبات اشتباه بودن: یک مثال نقض مورد n=۷ است. زیرا 21=7×3  زوج نسیت.