سرفصل های درس منطق

نام بسته : منطق

———————————————————————

فهرست 

پیش­ درآمدی بر منطق

1- منطق گزاره ها (PL)

1-1-مقدمه

1-2- زبان صوری منطق گزاره ها

1-3- صورت­های نرمال فصلی (DNF) ، عطفی (CNF) و عبارات هورن

1-4- معنا شناسی منطق گزاره ها

1-5- روش­های استنتاج در منطق گزاره

1-6- ساختار اصل موضوعی منطق گزاره­ها

1-6-1- قضایای راستی ، درستی و تمامیت برای منطق گزاره ها

1-7- استنتاج طبیعی در منطق گزاره ها

1-7-1- اثبات از طریق تناقض در منطق گزاره ها

1-7-2- اثبات از طریق هم ارزی در منطق گزاره ها

1-8- مسائل کاربردی منطق گزاره ها

1-9- تاریخچه منطق گزاره­ها

2- منطق مرتبه اول (پریدیکیت) (FOL)

2-1-مقدمه

2-2- زبان منطق مرتبه اول

2-2-1- متغیر های آزادو بسته و جایگذاری متغیرها

2-3-معناشناسی منطق مرتبه اول

2-4-نظریه برعان برای منطق مرتبه اول

2-5- ساخارهای ریاضی در منطق مرتبه اول

2-6- فرمول­های بازگشتی منطق مرتبه اول

منابع این بسته درسی

 بخش هایی از بسته درسی منطق

 پیش درآمدی بر منطق

منطق امروزه در زمینه­ های متعدد به عنوان زبان توصیف و روش تحلیل موضوعات مختلف حضور دارد. بطوریکه ساختارهای منطقی در همه جای علوم ریشه پیدا کرده و مطالعه آن از یک رویکرد سطحی و صرفا شناختی به رویکردی عملی و تحلیل­گرایانه در کاربردهای مختلف تبدیل شده است. در علوم کامپیوتر نظری، منطق بازیگر نقش اول و تنها راه رسیدن به پاسخ­های مهم و اساسی پیرامون محاسبه­ پذیری، اثبات­ پذیری, تعریف ­پذیری و اندازه­ پذیری است. مبانی ساخت و تحلیل سیستم­ها نیز امروزه اساسا مبتنی بر  منطق و شاخه­های متنوع آن است.

منطق در ابتدا به اصول و روش‌هایی که برای تمیز دادن استدلال‌های درست از استدلال‌های نادرست به کار می‌رفتند، اشاره داشت. امروزه با حفظ کامل این جایگاه منطق علاوه بر مولفه­ های صورت بندی فکر و تحلیل استدلال­های درست و نادرست و ارائه نتایج و احکام منطقی، دارای توانایی ایجاد یک سازه کامل برای سیستم­های متنوع را دارد. سازه شامل سه بخش مهم است: اجزاء، ارتباط بین اجزاء و فرایندهای ناشی شده از رفتارهای بین اجزاء. ابتکار در تحلیل ساختارهای صوری منطق موجب رشد و گسترش منطق در مواجهه با مسایل کاربردی شد، که باز هم بخش زیادی از این گسترش در حوزه علوم کامپیوتر بوده است.

منطق اساسا بین دو عرصه در جریان است: زبان و جهان. اگر عنوان جهان را معادل سیستم فرض کنیم باید گفت منطق جریان منطبق کننده زبان­ها و جهان­ها (سیستم­ها) است. یک جهان برای خود احکام و اجزایی دارد و یک زبان مناسب برای آن باید توانایی بیان همه اجزای تشکیل دهنده و ارتباطات موجود در آن جهان را داشته باشد. منطق علمی است که از یک سو به مطالعه عمیق نتایج صرفا شناختی جهان (به معنای سیستم) و از سوی دیگر به مطالعه صرفا نظری زبان (ساختار انتزعی) می­پردازد و نهایتا هر دو را با هم در یک سازه جدید کامل می­کند. یعنی از یک سو از روی تحلیل­های زبانی به نتایجی ناشناخته درباره جهان مورد نظر می­رسد و از سویی دیگر با استفاده از نتایج شناختی پیرامون جهان، تغییر ساختار مورد نیاز یک زبان برای تکامل آن را شناسایی می­کند.

«فصل اول»

«منطق گزاره­ها»

1. منطق گزاره­ها ([PL)(ZOL منطق مرتبه صفر)
   • مقدمه:

بررسی منطق با لغت گزاره که معنای معینی ‌دارد شروع می‌شود. گاهی به جای لغت گزاره از لغت عبارت استفاده می­شود(که به آن حکم نیز اطلاق می­شود)؛ در اینجا کلمه “عبارت” به گزارهای ترکیبی اشاره خواهد داشت. در منطق کلمات “راست” و “درست” و نیز کلمات”دروغ” و “غلط”با هم تفاوت دارند. اطلاق راستی به یک گزاره وابسته به جهانی است که آن گزاه درباره آن خبری را می­رساند؛ اما درست بودن یک گزاره به قابل استخراج یا استنتاج بودن آن از ساختار زبان اشاره می­کند. این تفاوت بین “دروغ” و “غلط” بودن نیز وجود دارد. قضایای مهمی در منطق برای نشان دادن ارتباط بین راستی و درستی مطرح شده اند تا نشان دهند هر آنچه راست است درست نیز می­باشد و هر آنچه درست باشد راست نیز خواهد بود.

 این قضایا در بخش­های انتهایی این فصل تحت عنوان قضایای درستیو تمامیتیا معادلاً ارضاءپذیریو سازگاریمطرح خواهند شد.

تعریف 1. گزاره

جمله‌ای خبری است که یا راست باشد یا دروغ و نه هر دو با هم، هر چند ما راستی یا دروغی آن را ندانیم. تنها این که بدانیم اگر راست باشد هرگز دروغ نخواهد بود و اگر دروغ باشد هرگز راست نخواهد بود کافی است.

مثال 1: هر یک از جملات زیر یک گزاره است.

الف- من دانشجوی رشته کامپیوتر هستم. 

ب- اگر لامپ روشن نمی­شود پس برق قطع شده است.

ج- این الگوریتم روی ورودی 78 هرگز متوقف نمی­شود.

د- درس خواندن تنها راه رسیدن به هدف است.

هـ- همه ­ی عقابها در حال پروازند.

برعکس جملات زیر هیچیک گزاره نیستند.

الف- من به رشته کامپیوتر علاقه مندم.

ب- شیشه تلألوی نابی داشت.

ج- الگوریتم ضرب اقلیدس از الگوریتم ضرب راسل راحت­تر است.

د- درس خواندن مشکل ترین کار دنیاست.

هـ-عقابها خیلی هم شجاع نیستند.

گزاره­ هایی همچون گزاره “من دانشجوی رشته کامپیوتر هستم” و یا “این الگوریتم روی ورودی 87 متوقف نمی­شود” را گزاره­های اتمی یا تجزیه نشدنی نامند. گزاره­های اتمی را معمولا با حروف کوچکی چون p، q، s،… و یا به صورت  نمایش می­دهند.

برای مشاوره اینجا بزنید