1) در هر درخت مجموع مرتبه و اندازه همواره عددی فرد است.
2) در هر درخت حاصل ضرب مرتبه و اندازه همواره عددی زوج است.
3) هر درخت با حذف هر یال به گرافی ناهمبند تبدیل می شود. و اگر یک یال اضافه کنیم دور پدید می آید.
مناسب برای دانش آموزان و دبیران و اولیا.
برای دانلود کل پاورپوینت از لینک زیر استفاده کنید:
جزوه ساختمان گسسته رشته مهندسی کامپیوتر
توضیحات محصول : کتاب های خلاصه منابع رشته مهندسی کامپیوترگرایش هوش مصنوعی برای آمادگی آزمون دکتری دانشگاه آزاد به همراه مجموعه تست با پاسخنامه تشریحی برای کنکوریها
فصل اول: حساب گزارهها
تعریف: در یک استدلال هر یک از عبارات استفاده شده برای رسیدن به نتیجه را فرض یا مقدم و عبارت آخر را نتیجه یا تالس . مینامیم
* یک استدلال زمانی معتبر است که اگر فرضهای آن درست باشد نتیجه درست است.
* جملات یا راست هستند یا دروغ ولی هرگز نمیتوانند هم درست باشند هم دروغ. چنین جملاتی را گزاره می . نامیم
قاعده طرد شق ثالث گزارهای که دروغ نیست، پس راست است و برعکس.
گزاره: یک جمله خبری است که یا راست است یا دروغ ولی نه هر دو.
قضیه: گزارهای که راست بودن آن را در یک سیستم ریاضی بتوان ثابت کرد.
تشکیل گزارههای جدید از روی گزارههای قبلی (حروف پیوندی مبنا):
- حرف پیوندی «و»، «عطف»، « Ù »: زمانی راست است که هر دو راست باشد.
- حروف پیوندی «یا»، «فصل»، « Ú »: زمانی راست است که یکی از گزار . هها راست باشد
- نقیض «~»، یا نفی یک گزارهها: ارزش گزاره اول را نفی . میکند
- جدول درستی: روشی برای تجزیه و تحلیل ارزشهای گزارهها
n نکته: در نوشتن جدول درستی اگر گزارهای مبنا داشته باشیم
2 . ترکیب داریم
مراحل : ارزیابی
-1 داخلیترین پرانتز
-2 عمل
Ú و Ù عمل 3-
گزاره راستگو: ارزش درستی گزارههای مبنای تشکیل دهنده آنها همواره راست باشد.
نکته: دو گزاره را به طور منطقی هم ارز گوییم اگر به ازای هر ترکیب همسان از ارزش گزارههای مبنای تشکیل دهنده آنها مقـادیر
درستی داشته باشد. (با گزار ه های همارز میتوان گزارههای پیچیده را با گزارههای ساده جایگزین کرد) = p q
گزاره ( های شرطی R p q ): گزاره ی p را مقدم و q را تالی مینامیم و این گزاره زمانی نادرست است که مقدم درست ولی تالی
نادرست باشد.
p ® q º~ p Ú q º~ q ® Ù ~ p(p ~ q) :قضیه
تعاریف شرطی:
اگر p آنگاه q
p اگر q
q اگر p
p شرط کافی برای q . است
q شرط لازم برای p . است.
مطالب تکمیلی فصل اول
منطق ریاضی
منطق: به مجموع ۀ قواعدی که به کمک آنها بتوان اعتبار یک استدلال را مشخص نمود «منطق» گفته میشود. در منطـق صـحبت
از مطالبی است که درست (True) و یا نادرست (False ) میباشند. در جبر عادی، متغیرها روی دامنهای از اعداد تعریـف مـیشـوند
ولی در منطق، متغیرها دامن هشان مجموعۀ {F,T} میباشد که مخفف کلمات True و False . هستند
گزاره: جملهای خبری که بتوان به آن ارزش درست یا نادرست داد گزاره نامیده میشود. گزارهها معمولاً با حروف بـزرگ انگلیسـی
بجز F,T نشان داده میشوند و به آنها «گزاره نما» (متغیر گزارهای) گفته می . شود
جبر گزارهها
گزارة ساده: گزارهای که قابل تجزیه به گزارههای کوچکتر نبوده و خود مستقلاً دارای ارزش T یا F . باشد
گزارة مرکب: از دو یا چند گزار ة ساده تشکیل میشود که با «رابطهای منطقی» با هم ترکیب شد . هاند
رابط منطقی (لفظ پیوند دهنده): مجموعهای از عملگرها میباشند که برخی بر روی یک گزاره عمل میکنند و بعضی بین دو یا
چند گزاره واقع شده و بسته به T یا F بودن هر گزاره، حاصل T یا F را برای ترکیب بدست آمده، تعیین می . نمایند .
تستهای فصل اول
-1 برای فرمول گزاره ای (P « Q) « (P ÙQ) Ú Ù (P ~ Q) مجموع مینترم ( ها PDNF) و حاصل ضرب ماکسـترمهـا
(PCNF) چیست؟
ندارد وجود . PCNF و å(o,1,2 3, ) (2 ندارد وجود . PDNF و Õ(o,1,2 3, ) (1
Õ(1 3, ) و å(o, )2 (4 å(0,2) , =Õ(1 3) (3
-2 در منطق گزارهها ..........
1) هر گزاره راستگو (tautology) یک قضیه نیست.
2) هر قضیه یک گزاره راستگو (tautology) است و بالعکس.
3) هر قضیه یک گزاره راستگو (tautology) نیست.
4) در مورد راستگویی یک قضیه چیزی نم . یتوان گفت
-3 فرض کنید {h : p , ®{o 1 یک تابع ارزش باشد. و A گزار های باشد که h(A) =1 . در این صورت:
A (1 همیشه صادق است. A ~ (2 همیشه صادق نیست.
A (3 ~ همیشه صادق است. 4 ) نمیتوان چیزی درباره A ~ . گفت
.......... ~ (p ®~ p) گزاره 4-
1) همیشه صادق است. 2 ) با p . معادل است 3) همیشه کاذب است. 4) با p ~ . معادل است
-5 صورت نرمال عطفی (CNF) فرمول (p « q) ~ عبارتست از: ......... .
~ p q Ù (2 ~ ((p ® q) Ù ®(q p)) (1
(p Ú q) Ù Ú (~ p ~ q) (4 (p ® q) Ù ® (~ p ~ q) (3
{po o ® p1,p1® p2,p2® ® p3 3 ,p p } ههای گزار مجموعه 6-
1) سازگار نیست.
2) بستگی به صدق یا کذب ات مهای p1 و p2 و p3 . دارد
.3) سازگار است
4) بستگی به صدق یا کذب اتم p o دارد.
-7 علامت [p[x / t یعنی در فرمول p، در صورت امکان، ترم t را به جای متغیـر x جانشـین کنیـد. در ایـن صـورت
:از عبارتست ($ < x(y x))[y/ x]
" < y(y x) (4 " < y(x y) (3 $ < x(x x) (2 $ < x(y x) (1
نوع فایل:PDF
سایز:2.72 mb
تعداد صفحه:170
لینک پرداخت و دانلود *پایین مطلب*
فرمت فایل:Word (قابل ویرایش و آماده پرینت)
تعداد صفحه27
در این مقاله می خواهیم به دو مبحث بزرگ از ریاضیات گسسته با نامهای ترکیبات و نظریه‌ی گراف بپردازیم که در این دوران شاهد پیشرفت چشمگیر آنها می باشیم .
این دو مبحث بدلیل آنکه دارای کاربرد وسیعی در علم کامپیوتر و برنامه سازی های کامپیوتری میباشند حائز اهمیت فراوان می باشند .
1-ترکیبات :
شاید در نگاه اول ترکیبات یک بخش معماگونه و سطحی از ریاضیات به نظر برسد که دارای کاربرد چندانی نبوده و فقط مفهوم های انتزاعی را معرفی می کند ولی این شاخه از ریاضیات دارای گستره‌ی وسیع بوده و دارای شاخه های زیادی نیز می باشد .
ابتدا به مسأله ای زیبا از ترکیبات برای آشنا شدن بیشتر با این مبحث ارائه می کنیم .
سوال : یک اتاقی مشبک شده به طول 8 و عرض 8 داریم که خانه‌ی بالا سمت چپ و خانه‌ی پایین سمت راست آن حذف شده است (مانند شکل زیر)
حال ما دو نوع موزاییک داریم . یکی 2*1 ( ) و دیگری 1×2 ( ) سوال این است که آیا می توان این اتاق را با این دو نوع موزائیک فرش کرد .
احتمالاً اگر شخص آشنایی با ترکیبات نداشته باشد می گوید «آری» و سعی می کند با کوشش و
خطا اتاق را فرش کند ولی این کار شدنی نیست ؟! و اثبات جالبی نیز دارد .
اثبات : جدول را بصورت شطرنجی رنگ می کنیم مانند شکل زیر :
حال با کمی دقت متوجه می شویم که هر موزائیک یک خانه از خانه های سیاه و یک خانه از خانه‌های سفید را می پوشاند یعنی اگر قرار باشد که بتوان با استفاده از این موزائیک ها جدول پوشانده شود باید تعداد خانه های سیاه با تعداد خانه های سفید برابر باشد ولی این گونه نیست زیرا تعداد خانه های سفید جدول برابر 32 و تعداد خانه های سیاه برابر 30 می باشد . در نتیجه این کار امکان امکان پذیر نیست .
این مسأله مربوط به مسائل رنگ آمیزی در ترکیبات بوده که دارای دامنه‌ی وسیعی از مسائل دشوار و پیچیده می باشد در زیر چند نمونه از مسائل آسان و سخت را بیان می کنیم .
1-ثابت‌کنید هیچ جدولی را نمی توان به موزائیک هایی به شکل و پوشاند .
(راهنمایی: ثابت کنید حتی سطر اول جدول را هم نمی توان پوشاند)
2-ثابت کنید یک مهره‌ی اسب نمی تواند از یک خانه‌ی دلخواه صفحه‌ی n*4 شروع به حرکت کند و تمام خانه ها را طی کند .
3-یک شبکه‌ی n*m از نقاط داریم یک مسیر فراگیر مسیری است که از خانه‌ی بالا سمت چپ
شروع به حرکت کرده و از همه‌ی خانه هر کدام دقیقاً یک بار عبور کند و به خانه‌ی سمت راست پایین برود ثابت کنید شرط لازم و کافی برای وجود یک مسیر فراگیر در شبکه‌ی n*m آن است که لااقل یکی از m یا n فرد باشد (مرحله‌ی دوم المپیاد کامپیوتر ایران) در شکل زیر یک مسیر فراگیر را برای جدول 5*4 می بینیم .
نمونه سوال درس گسسته نیمسال اول 88-89
خلاصه پایان نامه: