برهان خلف یک روش استدلال منطقی است که در آن فرض میکنیم نتیجه یا گزارهای که میخواهیم اثبات کنیم، نادرست است. سپس با استفاده از این فرض، به یک تناقض منطقی میرسیم. این تناقض نشان میدهد که فرض اولیه ما نادرست بوده و بنابراین، گزاره اصلی ما درست است.
- فرض کنید میخواهیم ثابت کنیم که "بینهایت عدد اول" وجود دارد.
- فرض خلف: فرض کنید تعداد اعداد اول محدود است و بزرگترین عدد اول را با P نشان میدهیم.
- حال عددی مانند Q را به این صورت میسازیم: Q = (2 * 3 * 5 * ... * P) + 1
- عدد Q یا اول است یا مرکب. اگر اول باشد که بزرگتر از P است و این با فرض ما در تناقض است.
- اگر مرکب باشد، باید حداقل یک عامل اول داشته باشد. اما Q بر هیچ یک از اعداد اول 2 و 3 و 5 و ... و P بخشپذیر نیست پس باید عامل اولی بزرگتر از P داشته باشد که باز هم با فرض تناقض دارد.
پس فرض خلف باطل شد و حکم ثابت گردید.
