مقدمه‌ای بر اثبات · اثبات مستقیم و مثال نقض
گزارهٔ شرطی دارای سور را بخوانید، آن را از تعریف‌ها اثبات کنید و گزارهٔ نادرست را با مثال نقض رد کنید. جبر مقدماتی اعداد صحیح کافی است.
درس و خلاصه
برای اثبات اینکه P برای هر عدد صحیح Q را نتیجه می‌دهد، عدد صحیح دلخواهی بگیرید که P را دارد و Q را نتیجه بگیرید. عدد زوج به صورت 2k و عدد فرد به صورت 2k + 1 با k صحیح نوشته می‌شود. یک ورودی با P درست و Q نادرست، گزارهٔ شرطی همگانی را رد می‌کند.
- فرض کنید هر دو عدد فردند
- a = 2m + 1, b = 2n + 1
- a + b = 2(m + n + 1)
- جمع زوج است
مثال حل‌شده
اگر a و b فرد باشند، a = 2m + 1 و b = 2n + 1 را برای اعداد صحیح m و n بنویسید. جمع برابر 2(m + n + 1) است، پس زوج است. عکس گزاره نادرست است: جمع ۲ و ۲ زوج است، در حالی که هیچ‌کدام فرد نیستند.
اشتباه رایج
بررسی نمونه‌های زیاد یک گزارهٔ همگانی را ثابت نمی‌کند. برای رد آن نمونه‌ای بیاورید که همهٔ فرض‌ها را دارد ولی نتیجه را نقض می‌کند.
تمرین
ثابت کنید حاصل‌ضرب دو عدد صحیح فرد، فرد است. سپس گزارهٔ «هر عدد صحیحی که جمع آن با ۴ زوج باشد، فرد است» را بررسی کنید.
پاسخ تمرین
حاصل‌ضرب برابر 2(2mn + m + n) + 1 است. عبارت در پرانتز صحیح است. برای گزارهٔ دوم، ۲ + ۴ زوج است و خود ۲ نیز زوج است، پس ۲ مثال نقض است.
آزمون کوتاه · ۱۰ نمره
ثابت کنید عدد صحیح بخش‌پذیر بر ۶ بر ۳ نیز بخش‌پذیر است (۶ نمره). عکس گزاره را بیان و رد کنید (۴ نمره).
پاسخ‌نامهٔ آزمون
برای k صحیح، n = 6k = 3(2k) است. چون 2k صحیح است، ۳ بر n بخش‌پذیری دارد. عکس می‌گوید بخش‌پذیری بر ۳ بخش‌پذیری بر ۶ را نتیجه می‌دهد. عدد ۹ مثال نقض است.
MIT OCW · Mathematics for Computer Science
آزمایش مجازی · یافتن مثال نقض
شواهد را از اثبات متمایز کنید و برای عکس یک گزاره مثال نقض بسازید.
ابزار رایگان در همین صفحه. در مرورگر و بدون حساب کاربری یا دانلود استفاده کنید.
روش انجام
ابتدا a برابر ۳ و b برابر ۵، سپس a برابر ۲ و b برابر ۴ را بیازمایید. ابزار نشان می‌دهد آیا هر دو ورودی فردند و آیا جمع زوج است. مثال نقضی برای «اگر جمع زوج باشد، هر دو ورودی فردند» پیدا کنید و سپس گزارهٔ اصلی را جبری ثابت کنید.
نتایج مورد انتظار و بررسی پاسخ
جمع ۲ و ۴ برابر ۶ و زوج است، اما هر دو ورودی زوج‌اند، پس عکس رد می‌شود. برای ورودی‌های فرد a = 2m + 1 و b = 2n + 1 بنویسید. جمع 2(m + n + 1) برای همهٔ m و n صحیح زوج است.
ابزار نمونه‌ها را می‌آزماید و جبر گزاره را برای همهٔ اعداد صحیح ثابت می‌کند.