موضوع مقاله: مسئله صدق‌پذیری بولی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مسئله صدق‌پذیری بولی | مقدمه: صدق‌پذیری یا ارضاپذیری در دانش رایانه پرسمانی است که می‌پرسد آیا می‌توان ارزش متغیرهای فرمولی دودویی را به گونه‌ای یافت که فرمول درست باشد؟ | ## بخش 1: مسئله صدق‌پذیری بولی | برای نمونه، فرمول صدق‌پذیر است چون اگر ارزش‌های و درست باشند، فرمول همواره درست است. کوک و لوین نشان دادند الگوریتمی شناخته‌شده‌ای نیست که در زمانی کوتاه پرسمان صدق‌پذیری را حل کند. محدودهٔ وسیعی از بقیهٔ مسائل تصمیم‌گیری و بهینه‌سازی طبیعی می‌توانند به موارد مسئلهٔ صدق‌پذیری تبدیل شوند. یک رده از الگوریتم‌ها به نام حل‌کننده‌های SAT به‌طور کارآمد می‌توانند زیرمجموعه‌ای به اندازهٔ کافی بزرگ از موارد SAT را حل کنند تا در حوزه‌های مختلف عملی از جمله طراحی مدار و قضیهٔ اثبات اتوماتیک مفید باشند. هرچند هیچ‌کدام از روش‌های کنونی نمی‌توانند همه‌ی موارد مسئلهٔ صدق‌پذیری را به‌طور کارآمد حل کنند. تعریف‌ها، واژگان و کاربردها در نظریه پیچیدگی محاسباتی مسئلهٔ صدق‌پذیری یک مسئلهٔ تصمیم است که نمونهٔ آن یک عبارت بولی می‌باشد که فقط با AND، OR، NOT، متغیرها و پرانتز نوشته شده‌است. سؤال این است که: آیا می‌توان به متغیرها مقادیر "درست" و "نادرست" داد تا عبارت موردنظر همواره درست باشد؟ یک فرمول از منطق گزاره‌ای صدق‌پذیر است اگر به متغیرهای آن بتوان مقادیر منطقی داد تا فرمول همواره درست باشد. مسئلهٔ صدق‌پذیری گزاره‌ای (PSAT)، که مشخص می‌کند آیا یک فرمول گزاره‌ای صدق‌پذیر هست یا نه، مهم‌ترین مسئله در حوزه‌های مختلف علوم رایانه است؛ نظیر علوم نظری رایانه، الگوریتم‌ها، هوش مصنوعی، طراحی پردازنده، اتوماسیون طراحی الکترونیکی و تایید. در بعضی حالت‌های مسئله صدق‌پذیری دودویی، نیاز است که فرمول عطف منطقی چند عبارت باشد. حالتی که صدق‌پذیری یک فرمول به شکل عطف معمولی را بررسی می‌کنیم که هر عبارت حداکثر دارای سه متغیر باشد، ان‌پی کامل است؛ این مسئله "۳SAT" یا "۳CNFSAT" یا "۳-صدق‌پذیری" نامیده می‌شود. حالتی که فرمول موردبررسی دارای عبارت‌هایی با حداکثر دو متغیر باشد، ان‌ال کامل است؛ این مسئله "۲SAT" نامیده می‌شود. حالتی که فرمول موردبررسی دارای عبارت‌های هورن (که حداکثر یک متغیر مثبت دارند.) باشد، پی کامل است؛ این مسئله صدق‌پذیری هورن نامیده می‌شود. قضیه کوک لوین عنوان می‌کند که مسئله دودویی صدق‌پذیری یک ان‌پی کامل است، در واقع این اولین مسئله‌ایست که اثبات شده ان‌پی کامل است. پیچیدگی و نسخه‌های محدود ان‌پی کامل همانطور که استفن کوک در سال ۱۹۷۱ اثبات کرد، مسئلهٔ SAT اولین مسئلهٔ ان‌پی کامل شناخته شد. (اثبات را در قضیه کوک لوین ببینید.) تا آن زمان مفهومی به نام ان‌پی کامل وجود نداشت. به‌طور مثال اگر یک گراف 17 رنگ‌آمیزی سه‌گانه معتبر داشته باشد، قاعدهٔ SAT دارای 17 واگذاری ارضاپذیر است. بسیاری از مواردی که در کاربردهای عملی اتفاق می‌افتند می‌توانند خیلی سریعتر حل شوند. مسئلهٔ SAT آسان‌تر است اگر فرمول‌ها به صورت فصلی معمولی باشند، یعنی بین عبارات OR و در هر عبارت بین متغیرها AND قرار گرفته باشد. | ## بخش 2: مسئله صدق‌پذیری بولی | این فرمول‌ها صدق‌پذیر هستند اگر و تنها اگر حداقل یکی از عبارات آن صدق‌پذیر باشند، و یک عبارت صدق‌پذیر است اگر و تنها اگر به ازای هر متغیر x هم خودش و هم NOT آن را دربرنداشته باشد. 2-صدق‌پذیری همچنین مسئلهٔ SAT آسان‌تر است اگر تعداد متغیرهای یک عبارت به 2 محدود شده باشد، که در این حالت مسئله 2SAT نامیده می‌شود. این مسئله نیز می‌تواند در زمان چندجمله‌ای حل شود و در واقع برای ردهٔ ان‌ال کامل است. به‌طور مشابه اگر تعداد متغیرهای هر عبارت را به 2 محدود کرده و اعمال AND را به XOR تغییر دهیم، نتیجه یک 2-صدق‌پذیری XOR است که یک مسئلهٔ کامل برای SL = L می‌باشد. این مسئله با الگوریتم ارضاپذیری هورن با زمان چندجمله‌ای قابل حل است، و در اصل پی-کامل می‌باشد. در صورتی که رده‌های پیچیدگی پی و ان‌پی یکسان نباشند، برخلاف SAT هیچ‌کدام از این محدودیت‌ها ان‌پی کامل نیستند. 3-صدق‌پذیری 3-صدق‌پذیری یک حالت خاص از k-SAT یا به‌طور ساده‌شده SAT است که هر عبارت دقیقاً k = 3 متغیر را شامل می‌شود. در اینجا یک مثال می‌زنیم: (¬ نشان‌دهندهٔ نقیض است.) E دارای دو عبارت (که با پرانتز مشخص شده‌اند)، چهار متغیر (x1, x2, x3, x4) و k = 3 (سه متغیر در هر عبارت) می‌باشد. برای آنکه این مثال از مسئلهٔ تصمیم‌گیری را حل کنیم باید مشخص کنیم که آیا یک جدول درستی برای متغیرها وجود دارد به‌طوری‌که کل عبارت همواره درست باشد یا خیر. در این مثال با "درست" قرار دادن همه متغیرها، می‌توان E را همواره درست در نظر گرفت. 3-SAT ان‌پی کامل است و به عنوان یک نقطهٔ شروع برای اثبات آنکه بقیهٔ مسائل هم ان‌پی سخت هستند استفاده می‌شود. 3-SAT می‌تواند به یک-در-سه 3-صدق‌پذیری محدود شود که در آن ما دقیقاً می‌پرسیم که آیا یکی از متغیرها در هر عبارت درست هست یا خیر، به جای اینکه حداقل یک متغیر را بررسی کنیم. بر اساس نظر شونینگ (1990) یک الگوریتم سادهٔ تصادفی وجود دارد که در زمان اجرا می‌شود (n تعداد عبارات). این‌گونه عبارت‌ها مورد توجه هستند چون می‌توانند استلزام یک متغیر از مجموعه‌ای از متغیرها را بیان کنند. در واقع یک عبارت مانند می‌تواند به شکل بازنویسی شود، یعنی اگر همه "درست" باشند، y هم باید "درست" باشد. این مسئله نیز می‌تواند با یک مرحله از انتشار واحد حل شود که مدل کمینهٔ واحد از مجموعه‌ای از عبارات هورن ایجاد می‌کند. یک تعمیم از ردهٔ فرمول‌های هورن، فرمول با قابلیت اسم‌گذاری دوبارهٔ هورن است که یک مجموعه از فرمول‌ها می‌باشد که با فرمت هورن می‌تواند با چند متغیر به همراه نقیض مربوطهٔ آن‌ها جایگزین شود. بررسی وجود این جایگزینی می‌تواند در زمان خطی انجام بگیرد؛ پس صدق‌پذیری همچین فرمولی در پی (P) است، چون می‌تواند اول با این جایگزینی و سپس بررسی صدق‌پذیری فرمول هورن نتیجه شده حل شود. صدق‌پذیری XOR یک حالت خاص دیگر مسائلی هستند که در آن‌ها هر عبارت فقط اعمال XOR را شامل می‌شود. | ## بخش 3: مسئله صدق‌پذیری بولی | چون عمل XOR معادل جمع در زمینهٔ گالویس از اندازهٔ 2 است، عبارات می‌توانند مانند یک دستگاه معادلات خطی دیده شوند و از روش‌های متناظر مانند حذف گاوسی می‌توان برای یافتن راه‌حل آن‌ها استفاده کرد. قضیهٔ دوگانگی شافر محدودیت‌های بالا (CNF، 2CNF، 3CNF، هورن) فرمول موردبررسی را به عطفی بودن زیرفرمول محدود می‌کنند؛ هر محدودیت یک شکل خاص برای همهٔ زیرفرمول‌ها مشخص می‌کند: به‌طور مثال، فقط عبارات دودویی می‌توانند یک زیرفرمول در 2CNF باشند. قضیهٔ دوگانگی شافر عنوان می‌کند که برای هر محدودیتی بر اعمال بولی که می‌توانند این زیرفرمول‌ها را شکل دهند، مسئلهٔ صدق‌پذیری متناظر یک پی یا ان‌پی کامل است. عضویت در پی (P) برای صدق‌پذیری 2CNF و فرمول هورن، حالت‌های خاصی از این قضیه هستند. رفتار در زمان اجرا همانطور که در بالا به‌طور خلاصه بیان شد، هرچند که مسئله، ان‌پی کامل است، مثال‌های عملی زیادی می‌توانند خیلی زود حل شوند. اکثر مسائل عملی در حقیقت "آسان" هستند، پس حل‌کنندهٔ SAT به آسانی می‌تواند یک راه‌حل بیابد یا اثبات کند که وجود ندارد؛ با وجود آنکه آن مورد هزاران متغیر و ده‌ها هزار محدودیت دارد. بقیهٔ مسائل کوچک زمان‌های اجرایی را ارائه می‌دهند که به صورت نمایی باشند و به مرور غیرعملی شده‌اند. متأسفانه هیچ راه قابل اطمینانی وجود ندارد که سختی مسئله را بدون امتحان آن بیان کند. پس تقریباً همهٔ حل‌کننده‌های SAT شامل زمان‌های اضافه می‌شوند، پس با آنکه هیچ راه‌حلی نیافته‌اند اما به پایان خواهند رسید. در نهایت حل‌کننده‌های SAT مختلفی موارد مختلف آسان یا سخت را پیدا خواهند کرد و بعضی از آن‌ها در اثبات صدق‌ناپذیری و دیگران در یافتن راه‌حل برترند. قابلیت کاهش دادن خود از یک الگوریتم که به درستی می‌گوید یک مثال از SAT قابل‌حل است یا نه، می‌توان برای یافتن واگذاری صدق‌پذیر استفاده کرد. این ویژگی در تئوری‌های مختلفی از قضیهٔ پیچیدگی استفاده می‌شود: (قضیهٔ کارپ-لیپتون) الگوریتم‌های حل‌کنندهٔ SAT دو رده از الگوریتم‌های با کارایی بالا برای حل مسائل SAT وجود دارد: الگوریتم تضاد-راندهٔ شناختن عبارت، که می‌توان به عنوان نوعی دیگر از الگوریتم‌های DPLL به آن نگاه کرد، و همچنین الگوریتم‌های اتفاقی جستجوی محلی مانند WalkSAT. یک حل‌کنندهٔ مسئلهٔ صدق‌پذیری DPLL، یک روند جستجوی بازگشتی اصولی را به کار می‌گیرد تا فاصلهٔ واگذاری متغیرها برای یافتن واگذاری صدق‌پذیر را کشف کند. حل‌کننده‌های SAT نوین (که در 10 سال گذشته ایجاد شدند) در دو نوع بیان می‌شوند: "تضاد-رانده" و "پیش‌بین". حل‌کننده‌های تضاد-رانده الگوریتم جستجوی DPLL اصلی را با تحلیل تضاد کارآمد، شناختن عبارت، بازگشت بدون ترتیب زمانی (الگوریتم پس‌پرش)، و همچنین انتشار واحد "دو-متغیر-تماشا"، انشعاب انطباقی و راه‌اندازی مجدد تصادفی، افزایش می‌دهند. نشان داده شده‌است که این "الحاقات" اصولی جستجو به صورت تجربی برای رسیدگی به موارد زیادی از SAT که در اتوماسیون طراحی الکترونیکی (EDA) به وجود می‌آیند ضروری هستند. حل‌کننده‌های پیش‌بین به خصوص کاهش‌ها (رفتن به ورای انتشار عبارت واحد) و کشف‌کننده‌ها را تشدید کردند و در کل در موارد پیچیده از حل‌کننده‌های تضاد-رانده قوی‌تر عمل می‌کنند. حل‌کننده‌های SAT نوین تأثیرات مهمی بر زمینه‌های تأیید نرم‌افزاری، حل‌کردن محدودیت‌های هوش مصنوعی و تحقیق در عملیات دارند. انواع خاصی از موارد بزرگ تصادفی صدق‌پذیر از SAT با انتشار نظرسنجی (SP) قابل حل هستند. | ## جمع‌بندی | به خصوص در طراحی پردازنده و برنامه‌های تایید، صدق‌پذیری و دیگر خواص منطقی از فرمول گزاره‌ای داده‌شده بعضی اوقات بر پایهٔ نمایشی از فرمول در نمودار تصمیم‌گیری دودویی (BDD) تصمیم‌گیری می‌شوند.