اثبات مستقیم

در ریاضیات و منطق، اثبات مستقیم (به انگلیسی: Direct proof) راهی است برای نشان دادن درستی یا نادرستی یک گزارهٔ داده شده با ترکیب کردن سر راست حقایق مسلم؛ یعنی معمولاً اصل موضوع‌ها و قضیه‌هایی که وجود دارند، بدون اینکه بخواهیم فرضیه‌های بیشتری بسازیم. برای اثبات مستقیم یک گزارهٔ شرطی به شکل "اگر $p$ ، آنگاه $q$ "، تنها کافی است حالتی را در نظر بگیریم که گزارهٔ $p$ درست باشد. استنتاج منطقی، برای رسیدن از فرائض به نتایج استفاده می‌شود. نوع منطقی که استفاده می‌شود، اکثر اوقات منطق مرتبۀ اول است که از سورهای وجود دارد و برای هر استفاده می‌کند. قاعده‌های اثباتی که معمولاً استفاده می‌شوند وضع مقدم (Modus ponens) و Universal instantiation هستند.

از سوی دیگر، اثبات غیر مستقیم ممکن است با زمینه‌ها و مقدمه‌های فرضی مشخص شروع کند و پس از آن با برطرف کردن هر گونه ابهام از هر یک از این مقدمه‌ها، روال را ادامه دهد تا به یک نتیجهٔ غیرقابل اجتناب برسد. برای مثال، به‌جای اینکه مستقیماً نشان دهیم $p\rightarrow q$ ، عکس نقیض آن را ثابت می‌کنیم: $\sim q\rightarrow \sim p$ (ابتدا $\sim q$ را فرض می‌کنیم و بعد نشان می‌دهیم که نتیجهٔ آن $\sim p$ می‌شود). چون $p\rightarrow q$ و $\sim q\rightarrow \sim p$ ، طبق قاعدهٔ جابجایی، هم‌ارز هستند (مراجعه کنید به اصل طرد شق ثالث)، در نتیجه $p\rightarrow q$ ، به شیوهٔ غیر مستقیم ثابت می‌شود. برهان خلف نیز از روش‌های اثبات غیر مستقیم محسوب می‌شود. اثبات به روش مستقیم شامل "اثبات با exhaustion" و "اثبات با استقرا" می‌شود.

مثال‌ها[ویرایش]

ثابت کنید که حاصل‌جمع دو عدد صحیح زوج، خود عددی زوج خواهد بود.

دو عدد صحیح زوج $x$ و $y$ را در نظر بگیرید. چون این دو عدد زوج هستند، می‌توان آن‌ها را اینگونه نوشت: $x=2a$ و $y=2b$ . با توجه به اینکه $a$ و $b$ اعداد صحیح هستند، لذا خواهیم داشت: $x+y=2a+2b=2(a+b)$ . از اینجا واضح است که $x+y$ دارای عدد ۲، به عنوان یک عامل است و بنابراین زوج است، پس حاصل‌جمع هر دو عدد صحیح زوج، زوج خواهد بود و حکم ثابت شد. $\blacksquare$

این متن مرتبط با منطق، مبنا و پایه (متن خام) است.

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

اتحاد $x^{2}+x=x(x+1)$ را در نظر بگیرید. طبق فرض، $x^{2}$ زوج است و همچنین می‌دانیم $x(x+1)$ نیز زوج است (زیرا از هر دو عدد صحیح متوالی، دقیقاً یکی از آن‌ها زوج و دیگری فرد است و حاصل‌ضرب یک عدد زوج و یک عدد فرد، عددی زوج می‌شود). پس می‌توان نوشت: $x^{2}=2a$ و $x(x+1)=2b$ . بنابراین خواهیم داشت: