درس مبانی منطق و نظریه مجموعه‌ها» از دروس اامی دوره کارشناسی رشته علوم کامپیوتر و همچنین اختیاری رشته ریاضیات و کاربرد‌ها است. این درس ۳ واحدی است. در برنامه‌های قبلی، درس‌های ۴ واحدی منطق ریاضی و ۳ واحدی نظریه مجموعه‌ها وجود داشت و درس مبانی منطق و مجموعه‌ها در ظاهر جانشینی یرای آن دو است. سرفصل این درس شامل مواردی است از قبیل زبان برنامه نویس Prolog و الگوریتم‌های حل کننده SAT (از مرجع پیشنهادی Huth-Ryan) تا نظریه‌ی اصل موضوعی مجموعه‌ها و تعریف دقیق اردینال و کاردینال (از مرجع پیشنهادی Henle). هدف درس هم توصیف و درست‌یابی دستگاههای ریاضی و سیستم‌های کامپیوتری» اعلام شده است که تنها می‌توان معنی آنرا حدس زد. البته در مرجع HR زبان برنامه‌نویس Prolog نیامده است. در واقع سرفصل این درس ترکیبی است از سرفصلهای سه درس متفاوت که می‌توانند در دوره کارشناسی مطرح شوند: (منطق ریاضی)، (منطق در علوم کامپیوتر) و (نظریه‌ی مجموعه‌ها). در عمل ارایه‌ی همه‌ی این مواد غیر‌ممکن است و باید با توجه به نوع مخاطب تمرکز را بر بخشهای مناسب سرفصل گذاشت.
به هر حال مثل هر درس مقدماتی در منطق ریاضی این درس می‌بایست شامل موارد زیر باشد:
منطق گزاره‌ای: رابطهای منطقی، راستگوها، معرفی حداقل یک دستگاه استنتاجی مانند دستگاه اصل‌موضوعی یا استنتاج طبیعی، قضیه‌های فشردگی و درستی و تمامیت گزاره‌ای.
منطق محمولی: زبان مرتبه اول، متغیرهای آزاد، فرمولهای مرتبه اول، تعبیرها، تعریف درستی در یک تعبیر، مدل، فرمولهای منطقا معتبر، معرفی یک دستگاه استنتاجی محمولی، قضیه‌های فشردگی و درستی و تمامیت محمولی (شاید بدون اثبات)، مثالهایی از دستگاههای محمولی ریاضی مانند حساب محمولی مرتبه اول PA و نظریه مجموعه‌ها ZF.
منطق با علوم کامپیوتر و به طور‌خاص نظریه پیچیدگی محاسبه مرتبط است. فایل زیر که متن مقاله‌ای است که چند سال پیش در مجله فرهنگ و اندیشه ریاضی چاپ شده است به نظریه‌های حسابی مرتبه اول و ارتباط آنها با نظریه پیچیدگی محاسبه می‌پردازد.
درباره این سایت