أو آي تي

OIT - مسألتان مشتقتان من المسألة العامة لقابلية الارتضاء.

بالضبط واحد من ثلاثة

يعرف اختصارا بOIT وهو عبارة عن صيغة منطقية، تشبه في تكوينها وصيغتها 3SAT والسؤال هو: هل يوجد تعيين قيم للمتغيرات بحيث في كل قوس يكون بالضبط متغير واحد ذو قيمة موجبة؟

الاختصار

يحول ${\displaystyle (a\lor b\lor c)}$ من 3-سات لصيغة من OIT بإضافة خمس متغيرات جديدة للحصول على صيغة OIT :${\displaystyle (a\lor u\lor v)\wedge (\lnot b\lor u\lor w)\wedge (v\lor w\lor t)\wedge (\lnot c\lor v\lor x)}$.

بالضبط واحد من ثلاثة رتيبة

هو عبارة عن مسألة تشبه المسألة أعلاه، الفرق الوحيد هو كون المتغيرات تظهر موجبة أي لا نجد في الصيغة متغيرا ونفي المتغير.

مراجع

موسوعات ذات صلة :

• موسوعة رياضيات
• موسوعة منطق