برهان شرطی

برهان شرطی (به انگلیسی: Conditional proof) برهانی است که به‌شکل ادعای شرطی است، و اثبات می‌کند که مقدم عبارت شرطی، لزوماً منجر به تالی می‌شود.

بررسی اجمالی

مقدم مفروض یک برهان شرطی، فرض برهان شرطی نامیده می‌شود. بدین ترتیب، هدف یک برهان شرطی این است که نشان دهد اگر فرض برهان شرطی درست بود، نتیجۀ مطلوب را لزوماً به دنبال دارد. اعتبار برهان شرطی مستلزم درستی فرض برهان شرطی نیست، فقط اگر درست بود منجر به نتیجه می‌شود.

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

یک شبکۀ معروف از برهان‌های شرطی، کلاس نظریه پیچیدگی NP-complete است. تعداد زیادی کار جالب وجود دارد (به‌فهرست مسائل NP-complete مراجعه کنید)، و در حالی که مشخص نیست برای هر یک از آن‌ها یک راه‌حل چند جمله‌ای-زمان وجود دارد، مشخص است که اگر چنین راه‌حلی برای برخی از آن‌ها وجود داشته باشد، یکی برای همۀ آن‌ها وجود دارد. به‌طور مشابه، فرضیۀ ریمان پیامدهای بسیاری دارد که قبلاً ثابت شده‌است.

منطق ریاضی

به‌عنوان مثالی از یک برهان شرطی در منطق ریاضی، فرض کنید می‌خواهیم A→C (اگر A، آنگاه C) را از دو فرض اول زیر ثابت کنیم:

1.	A→B	("اگر A، آنگاه B")
2.	B→C	("اگر B، آنگاه C")
3.	A	(فرض برهان شرطی، "فرض کنید A درست است")
4.	B	(از خطوط 1 و 3 پیروی می‌کند، وضع مقدم؛ "اگر A آنگاه B؛ A، از این رو B")
5.	C	(از خطوط 2 و 4 پیروی می کند، وضع مقدم؛ "اگر B آنگاه C؛ B از این رو C")
6.	A→C	(از خطوط 3 تا 5، برهان شرطی، "اگر A، آنگاه C" دنبال می‌شود)

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

• قضیۀ استنتاج
• استلزام
• حساب گزاره‌ای

منابع

• رابرت ال کاسی، منطق، مجموعه‌ها و بازگشت، جونز و بارلت، 2006.
• Dov M. Gabbay، Franz Guenthner (ed. کتاب راهنمای منطق فلسفی، جلد 8، اسپرینگر، 2002.