اثبات مستقیم

در ریاضیات و منطق، اثبات مستقیم راهی است برای نشان دادن درستی یا نادرستی یک گزاره داده شده با ترکیب کردن سرراست حقایق مسلم، یعنی معمولاً اصل موضوع‌ها و قضیه‌هایی که وجود دارند، بدون اینکه بخواهیم فرضیه‌های بیشتری بسازیم. برای اثبات مستقیم یک گزاره شرطی به شکل "اگر p، انگاه q"، تنها کافی است حالتی را در نظر بگیریم که گزاره p درست باشد. استنتاج منطقی، برای رسیدن از فرائض به نتایج استفاده می‌شود. نوع منطقی که استفاده می‌شود، اکثر اوقات منطق مرتبه اول است که از سورهای وجود دارد و برای هر استفاده می‌کند. قاعده‌های اثباتی که معمولاً استفاده می‌شوند modus ponens و universal instantiation هستند.

از سوی دیگر، برهان غیر مستقیم ممکن است با زمینه‌ها و مقدمه‌های فرضی مشخص شروع کند و پس از آن با برطرف کردن هر گونه ابهام از هر یک از این مقدمه‌ها روال را ادامه دهد تا به یک نتیجهٔ غیرقابل اجتناب برسد. برای مثال به جای اینکه مستقیما نشان دهیم p → q، نقیض آن را ثابت می‌کنیم q → ~p~ ( ابتدا q~ را فرض می‌کنیم و بعد نشان می‌دهیم که نتیجهٔ آن p~ می‌شود) . چون p → q و q → ~p~ طبق قاعدهٔ جابجایی، هم ارز هستند (مراجعه کنید به law of excluded middle)، در نتیجه p → q به شیوهٔ غیر مستقیم ثابت می‌شود. برهان خلف نیز از روش‌های اثبات غیر مستقیم محسوب می‌شود. اثبات به روش مستقیم شامل "اثبات با exhaustion"،"اثبات با infinite descent" و "اثبات با استقرا" می‌شود.

مثال

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

منبع
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.