برهان شرطی

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

بررسی اجمالی[ویرایش]

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

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

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

منطق ریاضی[ویرایش]

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

1.	$A\rightarrow B$	("اگر $A$ ، آنگاه $B$ ")
2.	$B\rightarrow C$	("اگر $B$ ، آنگاه $C$ ")

3.	$A$	(فرض برهان شرطی، "فرض کنید $A$ درست است")
4.	$B$	(از خطوط ۱ و ۳ پیروی می‌کند، وضع مقدم؛ "اگر $A$ آنگاه $B$ ; $A$ ، از این رو $B$ ")
5.	$C$	(از خطوط ۲ و ۴ پیروی می‌کند، وضع مقدم؛ "اگر $B$ آنگاه $C$ ; $B$ از این رو $C$ ")
6.	$A\rightarrow C$	(از خطوط ۳ تا ۵، برهان شرطی، "اگر $A$ ، آنگاه $C$ " دنبال می‌شود)