3-سات

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

يمكن هذا الاختصار من البرهنة على أن 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.

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

هذه بذرة مقالة عن الرياضيات او موضوع متعلق بها بحاجة للتوسيع. فضلًا شارك في تحريرها.