بودجهٔ مرور پیشنهادی
ریاضیات گسسته دوازدهم / فصل ۱سه زبان، سه حرکت آغازین
من راهنمای منطق رندو هستم. بیا پیش از هر محاسبه با هم سه چیز را روشن کنیم: دامنه چیست، تعریف دقیق کدام است و آیا همهٔ جوابها پیدا شدهاند؟
هر نکته را با یک مثال کوچک برای خودت بازگو کن؛ بعد دام یا کنترل زیر آن را با دقت بخوان.
اثبات را از شکل حکم انتخاب کن
مثال، اثبات حکم کلی نیست
دیدن چند نمونهٔ درست فقط سرنخ میدهد. برای حکم «برای هر عدد صحیح» باید زنجیرهای بنویسی که همهٔ حالتها را پوشش دهد؛ اما برای رد چنین حکمی یک مثال نقض کافی است.
حرکت اول اثبات مستقیم: تعریف را باز کن
اگر فرض میگوید n مضرب ۶ است، بنویس n=۶k برای یک k∈Z. برای اثبات زوجبودن، عبارت را به شکل ۲t با t∈Z برسان.
عکس حکم را خودکار نپذیر
از «هر مضرب ۴ زوج است» نمیتوان «هر زوج مضرب ۴ است» را نتیجه گرفت. عدد ۶ مثال نقض عکس حکم است.
ریاضیات گسسته دوازدهم / فصل ۱بخشپذیری را جبری بخوان
جهت نماد تعیینکننده است
برای عددهای صحیح a,b با شرط a≠۰، عبارت a|b یعنی عدد صحیحی مانند q وجود دارد که b=aq. پس ۴|۲۰ درست و ۲۰|۴ نادرست است؛ خط عمودی نشانهٔ کسر نیست.
ترکیب خطی، مجهول مزاحم را حذف میکند
اگر a|b و a|c، آنگاه برای هر r,s∈Z داریم a|(rb+sc). ضرایب را طوری انتخاب کن که جملهٔ مجهول حذف شود؛ سپس مقدارهای ممکن را در شرط آغازین کنترل کن.
قضیهٔ تقسیم به مقسومعلیه مثبت نیاز دارد
برای d>۰، اعداد صحیح یکتای q,r وجود دارند که a=dq+r و ۰≤r<d. شرط بازهٔ باقیمانده، یکتایی را تضمین میکند.
اقلیدس؛ از ب.م.م تا ترکیب خطی
آخرین باقیماندهٔ ناصفر، ب.م.م است
برای دو عدد صحیح که همزمان صفر نیستند، ابتدا قدرمطلق آنها را در نظر بگیر. اگر یکی صفر باشد، ب.م.م برابر قدرمطلق عدد دیگر است؛ وگرنه عدد بزرگتر را بر کوچکتر و سپس هر مقسومعلیه را بر باقیماندهٔ قبل تقسیم کن. برای ۲۵۲ و ۱۹۸، باقیماندهها ۵۴،۳۶،۱۸،۰ هستند؛ پس ب.م.م ۱۸ است.
بازگشت را از پایین به بالا انجام بده
از ۱۸=۵۴−۳۶ آغاز کن و با جایگذاری رابطههای قبلی برس به ۱۸=۴×۲۵۲−۵×۱۹۸. این نمایش ثابت میکند ب.م.م یک ترکیب خطی از دو عدد است.
یک کنترل دوگانه انجام بده
هم مقدار ترکیب خطی را حساب کن و هم بررسی کن هر دو عدد آغازین بر ب.م.م بخشپذیرند. خطای علامت در بازگشت اقلیدس با همین کنترل آشکار میشود.
۱۹۸=۳×۵۴+۳۶
۵۴=۱×۳۶+۱۸
ریاضیات گسسته دوازدهم / فصل ۱همنهشتی؛ برابریِ باقیماندهها
پیمانه در این درس مثبت است
a≡b (mod m) با m>۰ یعنی m|(a−b). میتوان دو طرف همنهشتیهای همپیمانه را جمع، تفریق و ضرب کرد.
تقسیم آزاد نیست
از ca≡cb (mod m)، اگر d=(c,m) باشد، همیشه فقط a≡b (mod m/d) نتیجه میشود. همان پیمانه زمانی میماند که (c,m)=۱.
وجود وارون را پیش از استفاده ثابت کن
عدد a دقیقاً وقتی پیمانهٔ m وارون دارد که (a,m)=۱. برای نمونه، وارون ۵ پیمانهٔ ۱۲ خود ۵ است، چون ۵×۵≡۱.
تعداد جوابها را قبل از خود جواب بدان
آزمون وجود جواب همنهشتی
در ax≡b (mod m) بگذار d=(a,m). اگر d∤b جواب نداریم؛ اگر d|b، دقیقاً d ردهٔ جواب متمایز پیمانهٔ m داریم.
هنگام سادهسازی، پیمانه هم تقسیم میشود
برای ۱۴x≡۸ (mod ۲۰)، ب.م.م ۲ است. پس ۷x≡۴ (mod ۱۰) و در پایان دو جواب متمایز پیمانهٔ ۲۰ برابر ۲،۱۲ به دست میآید.
جواب عمومی را با فهرست ردهها قاطی نکن
x=۱۰k+۲ برای k∈Z هر دو ردهٔ ۲ و ۱۲ پیمانهٔ ۲۰ را پوشش میدهد؛ فهرست ردهها شکل دیگری از همان پاسخ است.
ب.م.م ← شرط بخشپذیری ← تقسیم همزمان ضریب، سمت راست و پیمانه.
ریاضیات گسسته دوازدهم / فصل ۱معادلهٔ سیاله؛ جواب صحیح، نه حقیقی
شرط وجود را اول بررسی کن
در ax+by=c، ضرایب صحیحاند و a,b همزمان صفر نیستند. با d=(a,b)>۰، جواب صحیح وجود دارد اگر و فقط اگر d|c.
یک جواب خاص، آغاز پاسخ است
اگر (x۰,y۰) یک جواب باشد، همهٔ جوابها از x=x۰+(b/d)t و y=y۰−(a/d)t با t∈Z به دست میآیند. چون a,b همزمان صفر نیستند، با تغییر t بینهایت زوج صحیح متمایز داریم؛ قیدهایی مانند نامنفیبودن ممکن است این مجموعه را محدود کنند.
قید نامنفی را روی پارامتر اعمال کن
بعد از نوشتن جواب عمومی، قید نامنفی یا طبیعیبودن هر متغیر را جدا روی t اعمال کن. اگر ضریب t در عبارت آن متغیر ناصفر باشد، قید یک نامساوی برای t میسازد. اگر ضریب t صفر باشد، شرط ثابت است: یا خودبهخود برقرار است یا همهٔ جوابها را رد میکند. برای نمونه، در ۰x+۳y=۶ جواب عمومی x=t، y=۲ است؛ قید y≥۰ خودبهخود برقرار است و فقط قید x≥۰ کران t≥۰ را میدهد. اشتراک قیدهای مؤثر پاسخ نهایی است؛ یافتن یک جواب، بیشینه یا کاملبودن را ثابت نمیکند.
- دامنه و پیمانه را نوشتهام.
- تقسیم همنهشتی را مجازسنجی کردهام.
- همهٔ ردهها یا همهٔ جوابها را دادهام.