جزوه ساختمان گسسته رشته مهندسی کامپیوتر

جزوه ساختمان گسسته رشته مهندسی کامپیوتر

توضیحات محصول : کتاب های خلاصه منابع  رشته مهندسی کامپیوترگرایش هوش مصنوعی برای آمادگی آزمون دکتری دانشگاه آزاد به همراه مجموعه تست با پاسخنامه تشریحی برای کنکوریها

فصل اول: حساب گزارهها  
تعریف: در یک استدلال هر یک از عبارات استفاده شده برای رسیدن به نتیجه را فرض یا مقدم و عبارت آخر را نتیجه یا تالس . مینامیم 
* یک استدلال زمانی معتبر است که اگر فرضهای آن درست باشد نتیجه درست است. 
* جملات یا راست هستند یا دروغ ولی هرگز نمیتوانند هم درست باشند هم دروغ. چنین جملاتی را گزاره می . نامیم 
قاعده طرد شق ثالث گزارهای که دروغ نیست، پس راست است و برعکس. 
گزاره: یک جمله خبری است که یا راست است یا دروغ ولی نه هر دو. 
قضیه: گزارهای که راست بودن آن را در یک سیستم ریاضی بتوان ثابت کرد. 
تشکیل گزارههای جدید از روی گزارههای قبلی (حروف پیوندی مبنا): 
 - حرف پیوندی «و»، «عطف»، « Ù »: زمانی راست است که هر دو راست باشد. 
 - حروف پیوندی «یا»، «فصل»، « Ú »: زمانی راست است که یکی از گزار . هها راست باشد 
 - نقیض «~»، یا نفی یک گزارهها: ارزش گزاره اول را نفی . میکند 
 - جدول درستی: روشی برای تجزیه و تحلیل ارزشهای گزارهها 
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