درس ۱ · صفحهٔ ۱ تا ۵ · حدود ۱۵ دقیقه · تولید هوش مصنوعی
درس 1: استدلال ریاضی
در این درس یاد میگیری با انتخاب حالتهای پوشانندهٔ همهٔ امکانها و اثبات حکم در هر حالت، یک گزاره را ثابت کنی و تفاوت این روش را با امتحان کردن چند مثال تشخیص بدهی.
پیش از شروع
چطور میتوان دربارهٔ بینهایت عدد طبیعی حکمی را ثابت کرد، اما فقط دو حالت را بررسی کرد؟
هر عدد طبیعی یا زوج است یا فرد؛ حالت سومی وجود ندارد. اگر حکم را برای یک عدد دلخواه در هر یک از این دو حالت ثابت کنیم، دیگر هیچ عدد طبیعیای از اثبات بیرون نمیماند.
هیچ حالتی جا نماند
هیچ حالتی جا نماند
چطور میشود دربارهٔ بینهایت عدد طبیعی، فقط دو حالت را بررسی کرد؟ راز کار این است که هر حالت، یک دستهٔ کامل از عددها را پوشش میدهد، نه فقط یک عدد را.
مثلاً هر عدد طبیعی یا زوج است یا فرد؛ امکان دیگری وجود ندارد. پس اگر حکمی را برای یک عدد زوجِ دلخواه و سپس برای یک عدد فردِ دلخواه ثابت کنیم، دیگر هیچ عدد طبیعی بیرون از استدلال ما نمیماند.
این کار شبیه بررسی همهٔ دانشآموزان یک مدرسه بر اساس کلاسهایشان است: اگر همهٔ کلاسها را بررسی کرده باشیم، کسی جا نمیماند؛ اما بررسی چند دانشآموز از چند کلاس کافی نیست.
برای یک اثبات کامل، دو پرسش از خودت بپرس:
- آیا حالتهایم همهٔ امکانها را پوشش میدهند؟
- آیا حکم را در هر حالت، بهطور کلی ثابت کردهام؟
پس امتحان کردن چند عدد زوج و فرد، جای اثبات برای زوجِ دلخواه و فردِ دلخواه را نمیگیرد.
کتاب درسی، صفحهٔ ۴
منطقِ پشتِ حالتبندی
منطقِ پشتِ حالتبندی
چرا باید حکم را در تکتک حالتها ثابت کنیم؟ فرض کن یک بسته یا با پیک میرسد یا با پست. برای اطمینان از رسیدن آن تا فردا، کافی نیست فقط بدانیم «اگر با پیک بیاید، تا فردا میرسد»؛ مسیر پست هم باید بررسی شود.
در زبان منطق، دو حالت را با و و نتیجهٔ موردنظر را با نشان میدهیم. همارزی زیر میگوید نتیجه گرفتن از «این حالت یا آن حالت»، معادل برقرار بودن هر دو شرط است:
سمت راست را اینطور بخوان: «اگر برقرار باشد، به میرسیم و اگر برقرار باشد، باز هم به میرسیم.»
برای نمونه، اگر حالتها زوج و فرد بودن عدد طبیعی باشند، هیچ عددی بیرون از این دو حالت نیست. اما اثبات حکم فقط برای عددهای زوج، دربارهٔ عددهای فرد چیزی نمیگوید. پس برای کامل شدن اثبات، هم پوشش همهٔ امکانها لازم است و هم اثبات حکم در هر حالت.
کتاب درسی، صفحهٔ ۴
صفر را جدا کن
صفر را جدا کن
وقتی میخواهی دو طرف یک تساوی را بر یک عدد تقسیم کنی، اول بپرس: آیا ممکن است آن عدد صفر باشد؟ تقسیم بر صفر مجاز نیست؛ پس حالت صفر را جدا میکنیم.
مثلاً اگر هزینهٔ خرید برابر «تعداد کالا × قیمت هر کالا» باشد و هزینه صفر شود، نمیتوان بیدرنگ بر تعداد کالا تقسیم کرد؛ شاید اصلاً کالایی نخریده باشیم!
برای اثبات اینکه از نتیجه میشود یا ، دو حالت داریم:
- اگر باشد: حکم همین حالا برقرار است؛ چون یکی از دو بخشِ «یا» درست است و لازم نیست هم صفر باشد.
- اگر باشد: معکوسِ وجود دارد. دو طرف تساوی را در ضرب میکنیم و به میرسیم.
این دو حالت همهٔ مقدارهای حقیقیِ را پوشش میدهند. پس هم حکم را ثابت کردهایم و هم هیچجا تقسیم نامجاز انجام ندادهایم.
کتاب درسی، صفحهٔ ۴
بررسی عضو به عضو
بررسی عضو به عضو
گاهی دامنهٔ مسئله آنقدر کوچک است که میتوان تکتک اعضای آن را بررسی کرد؛ درست مثل وقتی که برای پیدا کردن یک کلید، همهٔ جیبهای یک کیف را میگردی. اگر هیچ جیبی جا نمانده باشد، جستوجویت کامل است.
در مسئلهٔ کتاب، میدانیم و است. پس فقط شش مقدار ممکن داریم. میتوانیم برای هر عضو، مقدار را حساب کنیم و مشخص کنیم زوج است یا فرد. سپس نگاه میکنیم کدام عضوها شرطِ زوج بودن را دارند و آیا همگی در هستند.
فرق مهم اینجاست: بررسی چند عدد دلخواه از میان بینهایت عدد، اثبات نیست؛ اما بررسی تمام اعضای دامنهای متناهی، میتواند اثبات باشد. در این روش، لازم نیست اعضایی که شرط مسئله را ندارند در مجموعهٔ مقصد باشند؛ باید مطمئن شویم هر عضوی که شرط را دارد، حکم را هم برقرار میکند.
کتاب درسی، صفحهٔ ۵
مثال حلشده
فرض کن و باشد؛ ثابت کن اگر و زوج باشد، آنگاه .
دامنه فقط شش عضو دارد؛ پس میتوانیم تمام مقدارهای ممکن را بررسی کنیم.
برای محاسبهٔ راحتتر مینویسیم: .
برای و ، مقدار عبارت بهترتیب و است؛ هر دو فردند.
برای و ، مقدار عبارت بهترتیب و است؛ هر دو زوجاند.
برای و ، مقدار عبارت بهترتیب و است؛ هر دو فردند.
همهٔ اعضای بررسی شدند و فقط و شرط زوج بودن را دارند؛ پس .
نکات مهم
- در اثبات با درنظر گرفتن همهٔ حالتها، حالتها باید تمام امکانها را بپوشانند و حکم در تکتک آنها ثابت شود.
- پشتوانهٔ منطقی این روش، همارزی است.
- بسته به مسئله میتوان حالتهای صفر و ناصفر را جدا کرد یا در یک دامنهٔ متناهی و کوچک، همهٔ اعضا را بررسی کرد.