3-سات

3 سات اسم يطلق على نوع من المسائل الرياضياتية والمعلوماتية في ميدان المنطق. تسمى المسألة 3 سات 3 SAT اختصارا ل 3 satisfiability. و تبحث هذه المسألة في ما إذا كانت جملة منطقية من نوع Conjunctive normal form تتكون من 3 متغيرات قابلة لأن تكون صحيحة. مسألة 3SAT هي مسألة مشتقة من المسألة العامة SAT، حيث في كل قوس يوجد ثلاث متغيرات بالضبط. وهي أيضا من المسائل NP الكاملة.

الاختصار من SAT إلى 3SAT

يمكن هذا الاختصار من البرهنة على أن 3SAT هو أيضا مسألة NP كاملة، ويتم كما يلي:

• الصيغة ${\displaystyle (x\,)}$ والمكونة فقط من متغير، يتم تحويلها إلى صيغة باستعمال ثلاث متغيرات في كل صيغة، فتصبح كما يلي ${\displaystyle (x\lor a_{i}\lor b_{i})\wedge (x\lor \lnot a_{i}\lor b_{i})\wedge (x\lor a_{i}\lor \lnot b_{i})\wedge (x\lor \lnot a_{i}\lor \lnot b_{i})}$.
• الصيغة ${\displaystyle (x\lor y)}$ والمكونة من متغيرين، يتم تحويلها إلى صيغة باستعمال ثلاث متغيرات في كل صيغة، فتصبح كما يلي ${\displaystyle (x\lor y\lor c_{i})\wedge (x\lor y\lor \lnot c_{i})}$.
• عند وجود صيغة بثلاث متغيرات لا يتم أي تغيير.
• عند وجود أكثر من ثلاث متغيرات مثلا ${\displaystyle (x_{1}\lor x_{2}\lor x_{3}\lor ...\lor x_{k})}$. هنا نضيف (k-3) متغير جديد يتم توزيعها كما يلي ${\displaystyle (x_{1}\lor x_{2}\lor z_{1})\wedge (x_{3}\lor \lnot z_{1}\lor z_{2})\wedge ...\wedge (x_{k-2}\lor \lnot z_{k-4}\lor z_{k-3})\wedge (x_{k-1}\lor \lnot z_{k-3}\lor x_{k})}$.

و هذا الاختصار يتم في وقت حدودي، مع ملاحظة أن قيم المتغيرات في SAT هي نفسها قيم 3SAT. كما أن المتغيرات التي يتم اضافتها خاصة بكل عبارة clause.

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

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