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