ساختمان های گسسته - فصل اول - منطق و اثبات ها

صفحه 1:
به نام خدا ساختمان هاى كسسته - منطق و اثبات ها Discrete Structures - Logic and Proofs بهار 99 

صفحه 2:


صفحه 3:
* تعریف 1. در یک استدلال هر یک از عبارات استفاده شده براي رسیدن به نتیجه را فرض يا مقدم و عبارت آخر را نتیجه یا تالی می نامیم. > یک استدلال زمانی معتبر است که اگر فرضهاي آن درست باشد نتیجه نیز درست است. 3 * تعریف 2. جملات یا راست هستند یا دروغ ولی هرگز نمیتوانند هم راست باشند هم دروغ. چنین جملاتی را گزاره می نامیم. < معمولا گزاره ها , به صورت یک جمله اظهاری بیان می شوند ( که در مقابل جملات پرسشی , امرى , دستوری و غیره قرار دارد ) > گزاره ها , پایه و اساس هر نظریه ای در منطق هستند. 

صفحه 4:
@ * مثال 1 : کدام یک از جملات زیر درست یا نادرست است (اما همزمان نمی تواند هم درست و هم نادرست باشد)؟ درز جمعه براگ ركتن به تنائر شهر براى تماشاى 1 بخر. * زمین تنها سیاره منظومه شمسی است که حیات در آن جریان دارد. < برای هر عدد صحیح مثبت , یک عدد اول بزرگتر از وجود دارد. 

صفحه 5:
‎oH‏ فرش کنیا رو گزازه بانلتق: ‎ ‏* تعریف 3. ترکیب عطفی و به ضورت. نمایش داده می شود گزاره زیز است * تعریف 4. ترکیب فصلی و به صورت نمایش داده می شود گزاره زیر ‏< گزارههاین‌مانند رو که از ترگیب این گزاره:هابه دست:می آیند گزاره:مرکب نام دارند: ‎ 

صفحه 6:
* مثال 2 : اگر بي : 5ح 7 + 1 جو گرارهباسند: آنگام رکب عطمی ری چه ضورت زیر آنیته: و یک دهه , صد سال است. ترکیب فصلی و به صورت زیر است : پا یک دهه , صد سال است. 

صفحه 7:
@ * تعریف 4. ارزش درستی گزاره هایی مانند ترکیب های عطفی و فصلی را می توان با جدولی توصیف کرد که جدول درستی نام دارد. rs 3 se ‏تعرزیف :و ازرتتن درستی گرازه مرکلت ببه صورت تجدول زدرستت) ویر تعریف می:‎ Ss شود : 

صفحه 8:
@ ۳ 5 . fe ‏گزازه مراکلت به-صورت ختول دوسلتن زیر تعریق :مین‎ asin jo Gil ‏تغرزف:6:‎ ۲ شود : gk ‏اجوهی سودگزازهوین ات‎ pulses wel gam. T eager? محر ‎Z‏ محر 

صفحه 9:
* تعریف ‎ne wil .B‏ تعریف 8. ارزش درستی گزاره به صورت جدول درستی زیر تعریف می شود : * مثال 3 : اگر > 4,یک عدد اول است. آنگاه نقیض به صورت گزاره زیر است : : چنین نیست که 4 , یک عدد اول است. یاافن توان:نوشت: ‏ .4 یکعده اول:نیست: 

صفحه 10:
* مثال 4 : اگر > بلز پاسکال , چندین ماشین حساب مختلف اختراع کرد. : اولین کامپيوتر تمام الکترونیکی در قرن بیستم ساخته شد. : عدد در سال 1954 تا 1000000 رقم بعد از اعشار محاسبه شد. گزاره :های بالا را می توان:بة ضوزت مرکب زیر بیان کرد:: « بلز پاسکال, چندین ماشین حساپ مختلف اختراع کرد و چنین نیست که اولین کامپیوتر تمام الکترونیکی در قرن بیستم شناخته شد یا عدد در سال 1954 تا 1000000 رقم بعد از اعشار محاسبه شد ). گزاره مرکب بالا به صورت نمادی به صورت زیر می باشد : )2 ۸ 7( ۲ 

صفحه 11:
گزاره های شرطی و هم ارزی منطقی 

صفحه 12:
@ * تعریف 9. فرض کنید و گزاره باشند , گزاره مرکب اگر آنگاه گزاره شرطی نامیده می شود و آن را به صورت نمایش می دهند. ¥ گزاره را فرض(مقدم) و گزاره را نتیجه(تالی) می گویند. ۶ فرض شرط کافی و نتیجه شرط لازم را بیان می کند. ‎BS >‏ عکتتن زليه هب افيض ‎ 

صفحه 13:
۵ * تعریف 10. ارزش درستی گزاره های مرکب و به ضورت جدول درستی زیر تعریف می شود : 

صفحه 14:
* تعریف 11. فرض کنید و گزاره باشند. گزاره مرکب اگر و فقط اگر گزازه ‎go‏ فرظ بانیده من شود و آن‌را بهصورت: تمایش:سن دهد < صورت دیگر بیان " اگر و فقط اگر " چنین است که " شرط لازم و کافی برای است* * تعریف :12 ازرش:درستی گزازه:مزکب: به صورت جدول:دزستن زیر تعریف می شود : 

صفحه 15:
4 * تعریف 13. فرض کنید گزاره های مرکب و از گزاره های تشکیل شده اند. مى كوئيم و هم ارز منطقی هستند و آن را به صورت می نویسیم. 

صفحه 16:
* خواص گزاره ها : ‏جایی‎ ab > شرکت پذیری : ۰ توزیع پذیری 2 قانون دمورگان 2 خود توانی همانی : نقیض دوگانه م لا بي جح تج ۷ ۸2,2۱ 7 < و ۸ ۵۷۵۰۵۷۱۵۷ ,۱0۸۸۳۵۸۱۸۱ 7لا )1 نماكم زب اصارا” اب انا 2 ۳۸/۱ 2 22ت (ب ۷۵,۱۵۷ 522( ‎(PA‏ ‏مت (ب ممالا م رمت اب باجرااام 

صفحه 17:
@ 8 * مثال 5 : گزاره های زیر مفروض اند : > «گزاره دروغ است. : «گزاره درست است). آیا گزاره درست است؟ چرا؟ 

صفحه 18:
@ ‎SK ploS y oyl3S s gay Oljbs gl GS pls: 6 Jo *‏ كانه معد ؟ > چمعیت ایران , 80 میلیون نفر است. ‏> در نیمکره شمالی , تیرماه در فصل زمستان قرار دارد. ‏۲ فیل ها , حیوانات باهوشی هستند. ‏> بزرگ تر از است. ‏< خداحافظ آرش! ‎ 

صفحه 19:
* مثال 7 : گزاره های زیر را در نظر بگیرید : > یک بایت از 7 بیت تشکیل شده است) > : ریک کلمه دارای 2 بایت است). : (زيك ‎pio Solute cay‏ یا یک است)). گزاره های نمادین زیر را به زبان فارسی نوشته و راست یا دروغ بودن هر کدام را مشخص کنید. الف ) ‎(oe‏ 9 >( (5 (2 

صفحه 20:
* حل مثال 7: > ((یک بایت از 7 بیت تشکیل شده است)). : یک کلمه دارای 2 بايت است). : (زيك ‎pio Solute cay‏ یا یک است)). الف ) الف-ج ) یک بایت از 7 بیت تشکیل شده است یا یک کلمه دارای 2 بایت است. ارزش گزاره و نادرست است بنابراین ارزش گزاره نادرست است. 

صفحه 21:
* حل مثال 7: > (ایک بایت از 7 بیت تشکیل شده است)). : یک کلمه دارای 2 بايت است). : (زيك ‎pio Solute cay‏ یا یک است)). (eo ب-ج ) يك بایت از 7 بیت تشکیل شده است و یک کلمه دا ارزش گزاره و نادرست است بنابراین ارزش گزاره نادرست است. 

صفحه 22:
* حل مثال 7: > ((یک بایت از 7 بیت تشکیل شده است)). : یک کلمه دارای 2 بايت است). : (زيك ‎pio Solute cay‏ یا یک است)). 03 ج-ج ) چتین نیست که یک بایت از 7 بیث تشکیل شده است. ارزش گزاره نادرست است. یتابراین ارزش گزاره درست است. 

صفحه 23:
* حل مثال 7: > ((یک بایت از 7 بیت تشکیل شده است)). : یک کلمه دارای 2 بايت است). : (زيك ‎pio Solute cay‏ یا یک است)). (> دج ) چنین نیست که یک بایت از 7 بیت تشکیل شده است و یک کلمه دارای 2 بایت است. ارزش گزاره و نادرست است بنابزاین ارزش درست است. 

صفحه 24:
* حل مثال 7: > ((یک بایت از 7 بیت تشکیل شده است)). : یک کلمه دارای 2 بايت است). 2 : (یک بیت مساوی صفر یا یک است)). »( دج ) چنین تیست که یک بایت از 7 بیت تشکیل شده است و چنین نیست یک کلمه دارای 2 بایت است. ارزش گزاره و نادرست است , پس ارزش گزاره و درست است بنابراین ارزش درست است. 

صفحه 25:
* حل مثال 7: > ((یک بایت از 7 بیت تشکیل شده است)). : یک کلمه دارای 2 بايت است). : (زيك ‎pio Solute cay‏ یا یک است)). و ودج ) یک بايت از 7 بیت تشکیل شده است و یک کلمه دارای 2 بایت است یا یک بیت مساوی صفر یا یک است , اما در عین حال , چتین نیست که یک بایت از 7 بیت تشکیل شده است و یک بیت مساوی صفر یا یک باشد. ارزش گزاره و نادرست و ارزش گزاره درست است , پس ارزش گزاره درست است و چون ارزش گزاره تاذرست اشت پس ارزش گنراره درست است. بنابراین ارزش درست است. 

صفحه 26:
* مثال 8 : جدول درستی گزاره های زیر را تشکیل دهید. الف ) ب جع( 

صفحه 27:
* حل مثال 8 : الف ) (cull 

صفحه 28:


صفحه 29:


صفحه 30:
* مثال 9 : کدام یک از گزاره های زیر , راستگو است؟ الف) 5 212111011011007 ل ا ۱ ff 

صفحه 31:
@ * مثال 10 : کدام یک از عبارات زیر , هم ارز هستند؟ الف) ‎(oe‏ ‏جع( ‏>( ‏2( ‏و ‏3( ‏ع( 

صفحه 32:
LIN LD SLIM LY evr ‏باتو به‎ (DVD) VOSO VV Dy ۲ 

صفحه 33:
اس( ۸ 7 ]ما <) 7۸ ( (v= A 

صفحه 34:
اس م۳ ۷ ۸۱7 <)7۷ ۲ ۸ /[ ۷۲۳۸ ( > 

صفحه 35:


صفحه 36:
* مثال 11 : نشان دهید هم ارز با گزاره های زیر است. الف) ب جع( (cull نا توجه به جدول ‎simpy‏ 

صفحه 37:


صفحه 38:


صفحه 39:
# مثال 12 : در هر یک از عبارات زیر مقدم و تالی را مشخص کنید. الف) برای رئیس جمهور شدن کافی است یک سیاستمدار بود. نب ) برای زئیش جههور نتندن لازم اسنت یک سیاستفداز بود. ج ) شرط لازم برای درک علوم کامپیوتر , داشتن دانش کافی در ریاضیات گسسته است. د ) اين برنامه اجرا خواهد شد , تنها اگر , اشتباهی در تایپ کردن آن وجود نداشته باشد. الف-ج ) مقدم : سياستمدار بودن تالى : رئيس جمهور بودن ب-ج ) مقدم : رئيس جمهوز بودن ‎20٠‏ تالى : سياستمدار بودن ج-ج ) مقدم : درک علوم کامپیوتر ‎٠‏ تالی : داشتن دانش کافی در ریاضیات گسسته دج ) مقدم : اين برنامه اجرا خواهد شد .. , تالی : اشتباهی در تایپ کردن آن وجود نداشته باشد 

صفحه 40:
* مثال 13 : جدول درستی هر یک از گزاره های زیر را تشکیل دهید. (oe ) ‏الف‎ (> Ce 

صفحه 41:
*# حل مثال 13 : الف ) (cull 

صفحه 42:


صفحه 43:


صفحه 44:


صفحه 45:
@ که کدام یک از زوج * مثال 14 : با استفاده از گزاره های دوشرطی , مشخص کنید ام یک ان گزاره های زیر هم ارز هستند. ‎(all‏ و ب) و ‎(e‏ :و ‏>( و ‎ 

صفحه 46:
= *# حل مثال 14 : الف ) و (cull بنابراین دو گزاره بالا هم ارز نیستند. 

صفحه 47:
۸ سس كرد دهم در سل[ ۸]0۷ 0 2)0۷ ۷0 0۸0 

صفحه 48:
نابراین دو گزاره لا هم ارز نیستند 

صفحه 49:
نايرين دوكررة بالدهم از خسن[ 210۸0 0-0 ۲ 

صفحه 50:
گزاره نماها و سورها 

صفحه 51:
* تعریف 14. گزاره نما عبارتی است که اگر مقادیر متغيرهاي به کار رفته در آن مشخص شود به گزاره تبدیل شود. * مجموعه مقاديري که میتواند جایگزین یک متفیر موجود در گزاره نما شود جهان نامیده می شود. *# تعریف 15. دو گزاره نما را هم ارز گوییم , هر گاه به ازاي کلیه ي مقادیر ممکن از متغیرهایشان ارزش درستی یکسان داشته باشند. 

صفحه 52:
مثال 15 : عبارت ریاضی زیر , همه گزاره نما هستند. a ‏سس‎ .- SO I SS ‏مجموع اولین عدد فرد , مساوی است‎ قز دآنگاه : سس سح ور هبح اگر ‏ , آنگاه .. آگر و تنها اگر : 

صفحه 53:
* تعریف 15. فرض کنید , یک تابع گزاره ای با جهان سخن است. جمله : براق هر یک جمله با سور تقمومی امیذه.می شود > نماد به معنای هر و سور عمومی نامیده نی شود *# تعریف 16. فرض کنید , یک تایع گزاره ای با جهان سخن است. جمله : برای یک » یک چمله با سور وجودی نامیده:میشود: * نماد به معنای برای یک و سور وجودی نامیده می شود. 

صفحه 54:
# مثال 16 : جمله برای هر عدد حقیقی , > چمله ای با سور عمومی است. جهان سخن آن مجموعه اعداد حقیقی است. اين جمله برای هر حقیقی , درست است. علاوه بر این به خاطر مثبت یا صفر بودن مریع , درست است. * مثال 17 : جمله برای یک غذذ حقیفی , > جمله ای با سور وجودی است. جهان سخن آن مجموعه اعداد حقبقی است. این جمله برای , درست 

صفحه 55:
* تعریف 17. اگر دست کم برای یک در جهان سخن , جمله با سور عمومی زیر براى هر , تادرست باشد , نادرست است. مقداری از در جهان سخن که را نادرست می سازد, مثال نقض نامیده می شود. 

صفحه 56:
© مثال 18 :جفله با سورعصومن برای هر عدد حقیقی , جمله ای پا سور عمومی بالا نادرست است. زیرا اگر آنگاه گزاره نادرست است. مقدار 1 برای جمله بالا یک مثال نقص نامیده می شود. 

صفحه 57:
* مثال 19 : نشان دهید جمله با سور وجودی زیر نادرست است. agli oi Syl ۶ برای اين که نشان دهیم جمله بالا نادرست است باید نشان دهیم که 1 1> ‎x41‏ ‏برای هر عدد حقیقی نادرست است. اکنون عبارت بالا درست وقتی نادرست است که : 1 1 ‎XH‏ درست است. اکنون باید نشان دهیم عبارت بالا به برای هر عدد حقیقی درست است. 

صفحه 58:
* ادامه حل مثال 19 : > برای اين منظور فرض کنید یک عدد حقیقی دلخواه باشد. از آنجا که طرف این نامساوی اضافه کنیم تا به دست آید. اگر دو طرف نامساوی اخیر را بر اشت..میتوانیم: 2 رایه و یمک یتسم 39 1 1> 1+ مر که برای هر عدد حقیقی درست است. بنابراین جمله 1 1> ‎x41‏ که برای هر عدد حقیقی نادرست است. > نشان دادیم که جمله با سور وجودی برای یک عدد حقیقی , نادرست است. 

صفحه 59:
له فرض کنید که یک تابع گزاره ای باشد. * قوانین تعمیم یافته دمورگان در منطق ‎Tx P(x)‏ زمر )جر رما ‎Px)‏ رحا م (مر )حرم د ‎ 

صفحه 60:
*# مثال 19 : فرض کنید , جمله باشد. در مثال 18 نشان دادیم که : برای یک عدد حقیقی , نادرست است. برای این منظور ثابت کردیم برای هر عدد حقیقی , درست اس 2 با توجه به قوانین تعمیم یافته دمورگان در منطق این روش را می توان توجیه FRPP x) Ux PX) 

صفحه 61:
* مثال 20 : فرض کنید جمله : اگر , آنگاه باشد. جهان سخن , مجموعه اعداد حقیقی است. 2 جمله : برای هر , برای هر , نادرست است. یک مثال نقض , است. در اين حالت , گزاره نادرست زیر به دست می آید : اگر , آنگاه 

صفحه 62:
@ * ادامه حل مثال 20 : جمله : برای هر , برای یک , دزست است. نشان می دهیم که برای هر گزاره برای یک , اگر , آنگاه پا ارائه یک مقدار , درست است که برای آن اگر . آنگاه درست است. در واقع اگر قرار دهیم آنگاه گزاره درست زیر به دست می آید : آگر. , آنگاه که اين گزاره شرطی درست است , زیرا فرض نادرست است. 

صفحه 63:
@ * ادامه حل مثال 20 : ظ جمله : برای یک , برای هر , دزست است. نشان می دهیم که برای هر گزاره برای یک , اگر , آنگاه پا ارائه یک مقدار , درست است که برای آن اگر . آنگاه درست است. در واقع اگر قرار دهیم آنگاه گزاره درست زیر به دست می آید : آگر. , آنگاه که اين گزاره شرطی درست است , زیرا فرض نادرست است. 

صفحه 64:
* مثال 21 : کدام یک از گزاره های زیر هم ارز منطقی با است؟ ومو رحد )جع مرو سا عر و ومو رحد ) ح ع عرو _ 3 سح سحا ‎«__p)‏ مرو جا عر 3 وحمو معد )جع رزرو_ دعر 3 

صفحه 65:
* مثال 22 : فرض کنید تابع گزاره ای ", را دوست دارد" باشد. حوزه سخن , مجموعه تمام انسان ها است.هر یک از گزاره های زیر را به صورت نمادی بنویسید. کدام یک از گزاره ها , درست هستند؟ < يك تقر همه را دوست دارم ‎DX WV LZ (Xo‏ < همه ‎VP) resis yea‏ بر ار ) رم مو ۲ ۳۲ < یک نفر :يك ‎De DY LZ Xo Voss‏ << همه ,یک نقر را دوست دارا( 1 ‎Wx TV LZ (Xo‏ 

صفحه 66:
@ ول ودس * مثال 23 : نقیض گزاره های زیر را بنویسید. ‎dy Puy) Yr ¥yP\x,y)‏ الإ ‎IxVyP(x,y) YxIyP\x,‏ ومو رعح ‎nar bas Ze‏ ومو ر مح )جما عرو _ كت نود مدا 

صفحه 67:
* قوانین مربوط به اثبات درستی یا نأدرستقي جملات داراق عتور عمومی و وجودی ۶ برای اثبات اين که جمله با سور عمومی : برای هر , درست است نشان می دهیم که برای هر در جهان سخن , گزاره درست است. نشان دادن درستی برای یک مقدار خاص , ثایت نمی کند که : برای هر , درست است. 

صفحه 68:
* قوانین مربوط به اثبات درستی یا نأدرستقي جملات داراق عتور عمومی و وجودی ۲ برای اثبات اين که جمله با سور وجودی : تزا يك : دوست ابنت يك مقدار در جهان سخن بدست آورید که برای آن گزاره درست است. ‎oll sls >‏ اين که جمله با سور عمومی ‏برای هر , ‏نادرست است یک مقدار در جهان سخن بدست آورید که برای آن گزاره نادرست است. ‎ 

صفحه 69:
* قوانین مربوط به اثبات درستی یا نأدرستقي جملات داراق عتور عمومی و وجودی براى اثبات اين كه جمله با سور وجودی : براى يك , نادرست است نشان می دهیم که برای هر در جهان سخن , گزاره نادرست است. نشان دادن نادرستی برای یک مقدار خاص , ثابت نمی کند که : برای یک , نادرست است. 

صفحه 70:


صفحه 71:
# تعریف 18. برهان مستقیم از نتیجه ترکیب منطقی اصل ها, تعریف ها و تئوری های پیشین بدست می آید. *# تعریف 19. اثبات استقرایی ابتدا یک «حالت پایه» اثبات می شود, و سپس به کمک «فرض استقراء» مجموغه‌ای از حالات بعدی اثبات می شود: فرض کنید گزاره نمایی باشد که در آن جهان مورد بحث مجموعه اعداد طبیعی است. معمولاً سه سرحلة :در این اثبات وجوددارد:: [ وس کنید. [مبنای انتتعرا) + فن:تواند هر عدد صحيع ملبت غیر عر یاسد] > مبنای استقرا. نشان می دهیم که راست است. 2 فرض استقرا. فرض می کنیم که برای هر , راست است. < مرحله استقرا. با استفاده از فرض استقرا , نشان می دهیم که نیز راست است. 

صفحه 72:
* تعریف 20. آثبات از طزیق برابهش نتیجه اگزوفعط اگز را بزقراز می:سارد به وسیلة اثبات گزارة معادل با آن که نقیض اگر و فقط اگر نقیض می باشد. * تعریف 21. در اثبات با برهان خلف, فرض می کنیم گزاره‌ای غلط است, سپس به یک تناقض منطقی می رسیم, پس نتیجه می گیریم که آن گزاره باید صحیح باشد. ۶ اثبات از ظریق برهان خلف یکی از متداول ترین روش های اثبات در ریاضی است. 

صفحه 73:
* مثال 24 : حاصل ضرب عددی فرد در عددی زوج , عددی زوج است. اثبات از طریق برهان مستقیم : > فرض می کنیم که عددی زوج و عددی فرد است , بنابراین ‏ و . «رر 2( +/۳/) 2[ 1+ 2). 2 )رو .۲ عبارت بالا نشان می دهد <26ل ضرب عددی زوج است. 

صفحه 74:
* مثال 25 : گنگ است. اثبات از طریق برهان خلف : +« قرس من كوم كه كينا اس يس ‎Si‏ بجونعامل:سفترک هسسده ییترایی:. یا + می دانیم یک عدد مثبت حقیقی است , یک عدد زوج است بنابراین زوج است. > به طور مشابه می توان نشان داد که زوج است. ۶ اگر و هر دو زوج باشند. مضربی مشترک خواهند داشت , که با فرض ما در تناقض است بنابراین گنگ است. 

صفحه 75:
© مثال 26 : نشان دهید مجموع اولین عدد فرد برابر است. اثبات از طریق استقرای ریاضی : ‎aS aus Ge yess >‏ این :مجموع باشد. :در این ضوزنج: S42) = ‏بع‎ (=> + — 12 ) > بدیهی است که . بنابراین. مجموع فوق برای حالت صحیح است. * فرض کنید مجموع قوق برای صحیح است , به عبارت دیگر : ‎(eri) =e‏ سح عر )كد ‎ 

صفحه 76:
* ادامه حل مثال 26 : ۶ حال نشان می دهیم که اين مجموع برای نیز صحیح است. به عبارت دیگر نشان می دهیم که ‎kel k‏ *1+/)-1جم 6+2 -| 1+ 2|+۱/ ی | ۸+1 2|+|۱2۸-1 22-1122 1۱+ ی ‎el /<1‏