Finding all solutions of the Boolean satisfiability problem, if any, via Boolean-equation solving
العناوين الأخرى
إيجاد جميع حلول مسألة المشبعية البولانية، إن وجدت، بواسطة حل معادلة بولانية
المؤلفون المشاركون
Ahmad, Walid
Rushdi, Ali Muhammad Ali
المصدر
Journal of King Abdulaziz University : Engineering Sciences
العدد
المجلد 27، العدد 1 (30 يونيو/حزيران 2016)، ص ص. 19-34، 16ص.
الناشر
جامعة الملك عبد العزيز مركز النشر العلمي
تاريخ النشر
2016-06-30
دولة النشر
السعودية
عدد الصفحات
16
التخصصات الرئيسية
الملخص EN
Boolean Satisfiability (SAT) is the problem of deciding whether a propositional logic formula can be satisfied given suitable value assignments to the variables of the formula.
This problem is highly intractable to the extent that the most efficient algorithms for solving it require exponential time in the worst case.
Boolean Satisfiability has many applications and emerges frequently in a variety of (occasionally unexpected!) situations.
This fact warrants the availability of a handy tool to tackle small instances of Boolean Satisfiability.
Such a tool is naturally different from existing sophisticated algorithms that handle large and gigantic instances of SAT.
This paper presents a simple introductory exposition of Boolean Satisfiability and provides a method for finding all its solutions, if any, by solving a two-valued Boolean equation.
The method requires several steps including the conversion of a product-of-sums expression to a sum-of-products one, rules of intelligent multiplication, use of the branch-and-bound method and the divide-and-conquer strategy, and finally replacing an ordinary sum of products by a disjoint one.
The paper demonstrates its method, including all its aforementioned steps, via two detailed examples.
نمط استشهاد جمعية علماء النفس الأمريكية (APA)
Rushdi, Ali Muhammad Ali& Ahmad, Walid. 2016. Finding all solutions of the Boolean satisfiability problem, if any, via Boolean-equation solving. Journal of King Abdulaziz University : Engineering Sciences،Vol. 27, no. 1, pp.19-34.
https://search.emarefa.net/detail/BIM-822592
نمط استشهاد الجمعية الأمريكية للغات الحديثة (MLA)
Rushdi, Ali Muhammad Ali& Ahmad, Walid. Finding all solutions of the Boolean satisfiability problem, if any, via Boolean-equation solving. Journal of King Abdulaziz University : Engineering Sciences Vol. 27, no. 1 (Jun. 2016), pp.19-34.
https://search.emarefa.net/detail/BIM-822592
نمط استشهاد الجمعية الطبية الأمريكية (AMA)
Rushdi, Ali Muhammad Ali& Ahmad, Walid. Finding all solutions of the Boolean satisfiability problem, if any, via Boolean-equation solving. Journal of King Abdulaziz University : Engineering Sciences. 2016. Vol. 27, no. 1, pp.19-34.
https://search.emarefa.net/detail/BIM-822592
نوع البيانات
مقالات
لغة النص
الإنجليزية
الملاحظات
Includes bibliographical references : p. 30-33
رقم السجل
BIM-822592
قاعدة معامل التأثير والاستشهادات المرجعية العربي "ارسيف Arcif"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر