منطق در علوم کامپیوتر

[چپ|بندانگشتی|نمایش دیاگرام [دروازه منطقی|گیت‌های منطقی کامپیوتر]]
**منطق در علوم کامپیوتر** مباحث مشترک میان منطق و علوم کامپیوتر را پوشش می‌دهد. این موضوع را می‌توان به سه قسمت اصلی تقسیم کرد:
* مبانی نظری و آنالیز
* استفاده از فناوری کامپیوتر برای کمک به منطق دانان
* استفاده از مفاهیم منطق برای برنامه‌های کامپیوتری

## مبانی نظری و آنالیز
منطق در علوم کامپیوتر نقش اساسی دارد. برخی از زمینه‌های اصلی منطق که قابل توجه هستند عبارت اند از: نظریه محاسبه پذیری (که قبلاً تئوری بازگشت نامیده می‌شد)، منطق موجهات و نظریه رسته‌ها است. نظریه محاسبه بر اساس مفاهیمی که توسط منطق دانان و ریاضیدانانی مانند آلونزو چرچ و آلن تورینگ تعریف شده، بنا شده است. ابتدا چرچ با استفاده از ایده تعریف پذیری لامبدای خود وجود مسائل غیرقابل حل الگوریتمی را نشان داد. تورینگ اولین تحلیل قانع کننده از آنچه را که می‌توان یک روش مکانیکی نامید ارائه داد و کورت گودل ادعا کرد که او تحلیل تورینگ را «کامل» می‌داند. علاوه بر این، برخی از زمینه‌های دیگر در همپوشانی نظری بین منطق و علوم کامپیوتر عبارتند از:
* قضایای ناتمامیت گودل ثابت می‌کند که هر سیستم منطقی که توان لازم برای توصیف محاسبات را دارد شامل عبارت‌هایی است که داخل آن سیسام نه می‌توان آن‌ها را اثبات و نه رد کرد. این نکته به شکل مستقیم در مباحث نظری مربوط به امکان اثبات کامل بودن و درستی نرم‌افزار کاربرد دارد
* مشکل قاب یک مشکل اساسی است که باید هنگام استفاده از منطق مرتبه اول برای نشان دادن اهداف و وضعیت یک عامل هوش مصنوعی برطرف شود.
* مطابقت کاری-هوارد یک ارتباط میان سیستم‌های منطقی منطقی و نرم‌افزار است. این نظریه مطابقت دقیقی بین اثبات‌ها و برنامه‌ها ایجاد کرد. به ویژه نشان داد که اصطلاحات در جبر لاندا نوعدار-ساده با اثبات منطق گزاره ای شهودی مطابقت دارند
* نظریه رسته‌ها نشان دهنده نمایی از ریاضیات است که بر روابط بین ساختارها تأکید دارد. این نظریه با بسیاری از جنبه‌های علوم کامپیوتر گره خورده است: انواع سیستم برای زبان‌های برنامه‌نویسی، نظریه سیستم‌های انتقالی، مدل‌های زبان برنامه‌نویسی و نظریهٔ معنایی زبان برنامه‌نویسی.

## کامپیوترها برای کمک به منطق دانان
یکی از اولین کاربردهای اصطلاح هوش مصنوعی سیستم نظریه‌پرداز منطق بود که در سال ۱۹۵۶ توسط آلن نیوول، جی سی شاو و هربرت سیمون توسعه یافت. یکی از کارهایی که منطق دانان انجام می‌دهند این است که مجموعه ای از گزاره ها (شرط‌ها) در منطق را در نظر می‌گیرند و مجموعه نتایجی (یا گزاره‌های جدیدی) را که با استفاده از قوانین منطق درست هستند استنباط می‌کنند. برای مثال اگر در یک سیستم منطقی که می‌گوید «همه انسان‌ها فانی هستند» و «سقراط انسان است» آنگاه استنتاج «سقراط فانی است» معتبر می‌باشد. البته این یک مثال بدیهی است. در سیستم‌های منطقی واقعی گزاره‌ها می‌توانند بسیار متعدد و پیچیدتر باشند. خیلی زود پی برده شد که در این تحلیل و بررسی‌ها می‌توان از کامپیوتر کمک قابل ملاحظه ای گرفت. سیستم نظریه‌پرداز منطق کار نظری برتراند راسل و آلفرد نورث وایتهد در کار تأثیر گزارشان در منطق ریاضی که *[[مبادی ریاضیات]] نامیده می‌شد را تأیید کرد.* علاوه بر این متعاقباً از سیستم‌های بعدی توسط منطق دانان برای تأیید و کشف نظریه‌ها و اثبات‌های منطقی جدید استفاده شد.

## کاربردهای منطق برای کامپیوترها
همواره تأثیر زیادی از منطق ریاضی در زمینه هوش مصنوعی (AI) وجود داشته است. از ابتدا پی برده شد که فناوری خودکار کردن استنتاج‌های منطقی می‌تواند پتانسیل بسیار زیادی برای حل مسائل و نتیجه‌گیری از حقایق داشته باشد. ران برچمن منطق مرتبه اول (FOL) را به عنوان یک معیار توصیف کرده که تمام فرمالیته‌های دانش هوش مصنوعی باید توسط آن مورد بررسی قرار گرفته شوند. هیچ روش شناخته شده ایی کلی تر و قدرتمندتر از منطق مرتبه اول برای توصیف و تحلیل اطلاعات وجود ندارد. دلیل این که منطق مرتبه اول خود به سادگی به عنوان زبان کامپیوتر استفاده نمی‌شود این است که در واقع بیش از حد گویاست، به این معنا که منطق مرتبه اول می‌تواند به راحتی عبارت‌هایی را بیان کند که هیچ کامپیوتری، با هر توانی، هرگز قادر به حل آن نمی‌باشد. به همین دلیل در هر روشی از نمایش دانش تا حدی یک معامله بین قابلیت تبیین و محاسبه پذیری وجود دارد. هر چه یک زبان قابلیت تبیین بالاتری داشته باشد به منطق مرتبه اول شبیه تر است و هر چه شباهت بیشتر باشد، این زبان احتمالاً کندتر و متمایل به یک حلقهٔ بی‌نهایت است.

به عنوان مثال قوانین اگر آنگاه که در سیستم‌های خبره استفاده می‌شوند تقریباً یک زیر مجموعهٔ محدود از منطق مرتبه اولند. به جای فرمول‌های دلخواه با طیف گسترده‌ای از عملگرهای منطقی، نقطه شروع همان چیزی است که منطق دانان آن را قیاس استثنائی ذکر می‌کنند. در نتیجه، سیستم‌های قانون محور می‌توانند از محاسبات با کارایی بالا پشتیبانی کنند، به خصوص اگر از الگوریتم‌های بهینه‌سازی و تدوین استفاده کنند.

یکی دیگر از عمده زمینه‌های تحقیق برای نظریه منطق، مهندسی نرم‌افزار بود. پروژه‌های تحقیقاتی مانند دستیار نرم‌افزار دانش بنیان و برنامه‌های کارآموزی به برنامه نویسان از نظریه منطقی برای تأیید درستی مشخصه نرم‌افزار استفاده کردند. همچنین از آنها برای تبدیل مشخصات به کد کارآمد در سیستم عامل‌های گوناگون و اثبات برابری میان پیاده‌سازی و مشخصات استفاده کردند. این روش رسمی مبتنی بر تبدیل، اغلب بسیار پر زحمت تر از توسعه نرم‌افزار سنتی است. اگر چه، در حوزه‌های خاص با فرم گرایی مناسب و الگوهایی با قابلیت استفاده مجدد، این روش برای محصولات تجاری ثابت شده است. دامنه‌های مناسب معمولاً مواردی از قبیل سیستم‌های تسلیحاتی، سیستم‌های امنیتی و سیستم‌های مالی درلحظه است که خرابی این سیستم هزینه‌های انسانی یا مالی بیش از حد دارد. نمونه ای از چنین دامنه ای طراحی یکپارچه مقیاس بزرگ است - فرایندیی برای طراحی تراشه‌های مورد استفاده در پردازنده‌ها و بقیهٔ اجزای مهم دستگاه‌های دیجیتال. خطا در یک تراشه فاجعه بار است. برخلاف نرم‌افزار، تراشه‌ها نمی‌توانند تعمیر یا به روز رسانی شوند. در نتیجه، توجیه تجاری برای استفاده از روش‌های رسمی برای اثبات مطابقت پیاده‌سازی و مشخصات وجود دارد.

یکی دیگر از کاربردهای مهم منطق در فناوری کامپیوتر در زمینه زبان‌های قاب و مرتب کننده‌های خودکار بوده است. زبان‌های قاب مانند کی ال-وان دارای مفاهیم سخت هستند. تعاریف موجود در کی ال-وان را می‌توان به‌طور مستقیم به نظریه مجموعه‌ها و ریاضیات گزاره‌ها مرتبط کرد. این نکته به اثبات کننده‌های تخصصی نظریه‌ها که مرتب کننده نامیده می‌شوند اجازه می‌دهد تا اظهارات مختلف بین مجموعه‌ها، زیرمجموعه‌ها و روابط را در یک مدل داده شده تجزیه و تحلیل کنند. به این ترتیب مدل قابل اعتبارسنجی می‌باشد و هرگونه تعریف متناقضی پرچم گذاری می‌شود. مرتب کننده همچنین می‌تواند اطلاعات جدیدی را استنباط کند، برای مثال مجموعه‌های جدید را بر اساس اطلاعات موجود تعریف کند یا تعریف مجموعه‌های موجود را بر اساس اطلاعات جدید تغییر دهد. این سطح انعطاف‌پذیری برای اداره کردن دنیای همیشه در حال تغییر اینترنت ایدئال است. فناوری مرتب کننده بر روی زبانهایی مانند زبان هستی‌شناسی وب سوار شده تا بتواند از سطح منطق معناشناسی به اینترنت موجود دسترسی پیدا کند. این لایه وب معنایی نامیده می‌شود.

منطق زمانی برای استدلال در سیستم‌های همزمان استفاده می‌شود.

## جستارهای وابسته
* استدلال خودکار
* منطق محاسباتی
* برنامه‌نویسی منطقی

## منابع

## خواندن بیشتر
* Ben-Ari, Mordechai (2003). Mathematical Logic for Computer Science (2nd ed.). Springer-Verlag]. ISBN 1-85233-319-7.
* Huth, Michael; Ryan, Mark (2004). Logic in Computer Science: Modelling and Reasoning about Systems (2nd ed.). Cambridge University Press. ISBN 0-521-54310-X.
* Burris, Stanley N. (1997). Logic for Mathematics and Computer Science. Prentice Hall. ISBN 0-13-285974-2.

## پیوند به بیرون
* Article on ''Logic and Artificial Intelligence'' at the Stanford Encyclopedia of Philosophy.
* IEEE Symposium on Logic in Computer Science (LICS)
* Alwen Tiu, Introduction to logic video recording of a lecture at ANU Logic Summer School '09 (aimed mostly at computer scientists)


رده:روش‌های صوری