موضوع مقاله: صدق‌پذیری در پیمانه نظریات | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # صدق‌پذیری در پیمانه نظریات | مقدمه: یک مسئله صدق‌پذیری در پیمانه نظریات با کوته‌نوشت SMT در علوم رایانه و منطق ریاضیاتی، یک «مسئله تصمیم» برای فرمول‌های منطقی در ارتباط با ترکیبی از نظریات پیش‌زمینه‌ای که به صورت منطق مرتبه اول کلاسیک دارای تساوی بیان شده‌اند، است. | ## بخش 1: صدق‌پذیری در پیمانه نظریات | مثال‌هایی از این نظریات که معمولاً در علوم رایانه استفاده می‌شوند از این قرار است: نظریه اعداد حقیقی، نظریه اعداد صحیح، و نظریات ساختمان داده‌های متنوع مثل لیست، آرایه، بردار بیتی، و غیره. مسئله SMT را می‌توان نوعی مسئله ارضای محدودیت در نظر گرفت، و از این رو یک دیدگاه صوری‌شده معین به برنامه‌نویسی محدودیت است. اصطلاح‌شناسی اولیه به صورت صوری، یک مسئله SMT یک فرمول در منطق مرتبه اول است، که در آن بعضی از نمادهای تابعی و گزاره‌ای تفسیرهای اضافی دارند، و SMT همان مسئله تعیین این سوال است که آیا چنین فرمولی «صدق‌پذیر» هست یا نه. به عبارت دیگر، یک نمونه از مسئله صدق‌پذیری دودویی (SAT) را درنظر بگیرید، که در آن بعضی از متغیرهای دودویی با محمول‌ها جایگزین شده‌اند و این موضوع در محدوده مجموعه مناسبی از متغیرهای غیردودویی رخ داده‌است. چند مثال از گزاره شامل، نابرابری خطی (مثل ) یا تساوی‌های شامل ترم‌های تفسیرنشده و نمادهای تابعی (مثل که در آن یک تابع تعیین نشده از دو آرگومان است). برای مثال، نابرابری خطی روی متغیرهای حقیقی توسط قواعد نظریه حساب حقیقی خطی ارزیابی می‌شود، که در آن گزاره‌ها درگیر ترم‌های تفسیرنشده اند و نمادهای تابعی توسط قواعد نظریه توابع تفسیرنشده با تساوی ارزیابی می‌شوند (که گاهی به آن نظریه پوچ هم می‌گویند). نظریه‌های دیگر شامل نظریه‌های ساختمان آرایه‌ها و لیست‌ها می‌شود (که برای مدل‌سازی و راستی‌آزمایی برنامه‌های رایانه‌ای مفید است)، و نیز شامل نظریه آرایه بیتی است (که در مدل‌سازی و راستی‌آزمایی طراحی‌های سخت‌افزاری مفید است). زیرنظریه‌هایی دیگری هم ممکن است موجود باشد: مثل «منطق تفاوتی» که یک زیرنظریه از حساب خطی است که در آن هر نابرابری باید محدودیت فرمی را برای متغیرهای و و ثابت داشته باشد. بیشتر حل‌کننده‌های مسئله SAT فقط از قسمت‌های فاقد سور از منطق‌شان پشتیبانی می‌کنند. قدرت بیان یک نمونه از مسئله SMT در واقع یک تعمیم برای نمونه مسئله SAT دودویی است، که در آن مجموعه‌های متنوعی از متغیرها با گزاره‌هایی از انواع متنوعی از نظریه‌های بنیادین جایگزین شده‌اند. برای مثال، یک فرمول SMT به ما امکان مدل‌سازی عملیات دیتاپد (مسیرداده) برای یک ریزپردازنده را در سطح کلمه (و نه سطح بیت) می‌دهد. برای مقایسه، برنامه‌نویسی مجموعه جواب نیز براساس گزاره‌ها است (به صورت دقیق‌تر، بر اساس جمله‌های اتمی است که از فرمول‌های اتمی ساخته شده‌است). برخلاف SMT، برنامه‌های مجموعه جواب، «سور» ندارند، و نمی‌توانند محدودیت‌هایی مثل حساب خطی یا منطق تفاوت را به سادگی بیان کنند- ASP به عنوان بهترین راه‌حل برای مسائل دودویی هستند که به نظریه آزاد توابع تفسیرنشده کاهش یافته‌اند. پیاده‌سازی اعداد صحیح ۳۲ بیتی به عنوان آرایه‌بیتی در ASP از مسائل مشابهی رنج می‌برند که حل کننده‌های اولیه SMTها با آن مواجه بودند: برابری‌های «بدیهی» مثل x+y=y+x به سختی قابل استنتاج هستند. | ## بخش 2: صدق‌پذیری در پیمانه نظریات | برنامه‌نویسی منطقی محدودیت از محدودیت‌های حسابی خطی پشتیبانی می‌کنند، اما آن‌ها در چارچوب نظری کاملاً متفاوتی قرار دارند. دیدگاه‌های حل‌کننده تلاش‌های اولیه برای حل نمونه‌های مسئله SMT شامل ترجمه آن‌ها به نمونه مسائل SAT دودویی بود (مثلاً یک متغیر صحیح ۳۲ بیتی توسط ۳۲ عدد متغیر تک بیتی با وزن‌های مناسب و عملیات سطح کلمه مثل «جمع» با عملیات منطقی سطح پایینی روی بیت‌ها جایگزین می‌شدند) سپس این فرمول به حل‌کننده SAT دودویی تحویل می‌شد. به این دیدگاه، دیدگاه حریصانه هم می‌گویند، و دارای مزیت‌هایی هم هست: با پیش‌پردازش یک فرمول SMT به یک فرمول SAT دودویی معادل، حل‌کننده‌های SAT دودویی موجود را می‌توان به صورتی که هست استفاده کرد، در این روش، مزیت‌هایش از نظر کارایی و ظرفیت در طی زمان بیشتر می‌شود. از جهت دیگر، فقدان وجود معناشناسی سطح بالا برای نظریه‌های بنیادین، یعنی حل‌کننده دودویی SAT باید خیلی بیشتر از آنچه برای برای کشف واقعیت‌های «بدیهی» لازم است، کار کند (مثلاً برای جمع اعداد صحیح). DPLL(T) دوبل (دوتایی) که این معماری یک «مسئولیت استنتاج بولی» به «حل‌کننده SAT مبتنی بر DPLL» می داد، که به نوبه خود با یک حل‌کننده برای نظریه T از طریق یک واسط خوش‌تعریف تعامل دارد. حل‌کننده نظریه فقط باید در مورد بررسی امکان عطف‌دهی به گزاره‌های نظریه ارسال‌شده به آن، از حل‌کننده SAT و در هنگام کاوش فضای جستجوی دودویی فرمول نگران باشد. برای آنکه این یکپارچه‌سازی به خوبی کار کند، حل‌کننده نظریه باید بتواند در تحلیل انتشار و تضاد مشارکت کند، یعنی باید بتواند واقعیت‌های جدیدی را از واقعیت‌های پیش از این بناشده، استنتاج کند، همچنین از «توضیحات مختصری از غیرممکن بودن» در موقع بروز تعارض‌های نظری پشتیبانی کند. مسئله SMT برای نظریات تصمیم‌ناپذیر بیشتر دیدگاه‌های SMT معمول از نظریات تصمیم‌پذیر پشتیبانی می‌کنند. با این حال بیشتر سامانه‌های جهان واقعی را فقط با کمک حساب غیرخطی روی اعداد حقیقی می‌توان مدل‌سازی کرد، که ممکن است توابع متعالی را هم درگیر کند، مثل یک هواپیما و رفتار آن. این واقعیت منجر به ایجاد انگیزه‌ای برای یک گسترش برای مسئله SMT به نظریه‌های غیرخطی شد، مثلاً تعیین آنکه آیا که در آن: صدق‌پذیر هست یا نه. (نظریه زمینه‌های بسته حقیقی، و از این رو نظریه مرتبه اول از اعداد حقیقی، توسط حذف سور تصمیم‌پذیر هستند. این موضوع را مدیون آلفرد تارسکی هستیم) نظریه مرتبه اول اعداد طبیعی با جمع (اما بدون ضرب) حساب پرسبورگر نامیده می‌شود، که آن هم تصمیم‌پذیر است. به دلیل آنکه ضرب کردن با ثابت‌ها را می‌توان به صورت جمع‌های تودرتو پیاده‌سازی کرد، حساب در بسیاری از برنامه‌های رایانه‌ای قابل بیان به کمک حساب پرسبورگر است، که این موضوع منجر به فرمول‌های تصمیم‌پذیر می‌شود. مثال‌هایی از حل کننده‌های SMT که می‌خواهند ترکیبات دودویی «اتم نظریه» از نظریات حسابی تصمیم‌ناپذیر روی اعداد حقیقی رسیدگی کنند، ABsolver نام دارند، که از یک معماری کلاسیک DPLL(T) با یک بسته بهینه‌سازی غیرخطی به عنوان حل‌کننده نظریه فرعی (به صورت لازم غیرکامل) استفاده می‌کنند، و iSAT که روی یک اتحاد حل‌کننده DPLL SAT و انتشار محدودیت بازه‌ای ساخته شده‌اند، که الگوریتم iSAT نامیده می‌شود. | ## بخش 3: صدق‌پذیری در پیمانه نظریات | حل‌کننده‌ها جدول زیر بعضی از ویژگی‌های چند تا از حل کننده‌های SMT موجود را خلاصه‌بندی نموده‌است. این پروژه‌ها نه فقط از نظر ویژگی و کارایی با هم فرق دارند، بلکه از نظر زیست‌پذیری انجمن اطراف شان، علاقه پیشرونده به پروژه و توانمندی مشارکت مستندات، تعمیرها، تست‌ها و ارتقا با هم تفاوت دارند. دیگر قالب‌های استاندارد شده که معمولاً پشتیبانی می‌شوند شامل قالب DIMACS است که توسط خیلی از حل‌کننده‌های SAT بولی پشتیبانی می‌شود، و قالب CVC که توسط اثبات‌گر قضیه خودکار CVC استفاده می‌شود. در ابتدا، مسابقه در همایش درستی‌سنجی به کمک رایانه (CAV) قرار داشت، اما از سال ۲۰۲۰ مسابقه به عنوان بخشی از کارگاه SMT قرار گرفت، که به همایش ترکیبی بین‌المللی روی استنتاج خودکار (IJCAR) وابسته بود. کاربردها حل‌کننده‌های SMT هم برای صحت، اثبات درستی برنامه‌ها، آزمون نرم‌افزار براساس اجرای نمادین، و نیز برای ترکیب، تولید قطعه‌های برنامه با جستجو روی فضای برنامه‌های ممکن مفید است. و نیز برای مدل‌سازی سناریوهای نظری، که شامل مدل‌سازی اعتقادات کنشگر در کنترل نیروی هسته‌ای است، استفاده شده‌است. درستی‌سنجی درستی‌یابی برنامه‌های رایانه‌ای به کمک رایانه معمولاً از حل کننده SMT استفاده می‌کنند. یک روش معمول ترجمه پیش‌شرط، پس‌شرط، شرط حلقه، و ادعاها به فرمول‌های SMT است، که هدف آن است که تعیین شود، آیا همه ویژگی‌ها برقرار است یا نه. Boogie یک زبان درستی‌سنجی سطح میانی است که از Z3 استفاده می‌کند تا به صورت خودکار برنامه‌های دستوری ساده را بررسی کند. زبان F* یک زبان نوع دار وابسته است که از Z3 برای یافتن اثبات استفاده می‌کند؛ کامپایلر این اثبات‌ها را حمل می‌کند تا بایت‌کد حامل اثبات را تولید کند. در ادامه فهرستی از کاربردهای به بلوغ رسیده آمده‌است: Why3: یک بن‌سازه برای درستی‌سنجی برنامه به صورت استقرایی، که از Alt-Ergo به عنوان اثبات‌کننده اصلی استفاده می‌کند. Cubicle یک بررسی‌کننده مدل متن‌باز است که از آن برای درستی‌سنجی ویژگی‌های امنیتی برای سامانه‌های تبدیل مبتنی بر آرایه استفاده می‌شود. | ## جمع‌بندی | تحلیل و آزمون مبتنی بر اجرای نمادین یک کاربرد مهم برای حل‌کننده SMT، اجرای نمادین برای تحلیل و آزمون برنامه‌ها است (مثل تست کلونیک)، که مخصوصا در پیدا کردن آسیب‌پذیری‌های امنیتی کمک کننده است.