3-سات
3 سات اسم يطلق على نوع من المسائل الرياضياتية والمعلوماتية في ميدان المنطق. تسمى المسألة 3 سات 3 SAT اختصارا ل 3 satisfiability. و تبحث هذه المسألة في ما إذا كانت جملة منطقية من نوع Conjunctive normal form تتكون من 3 متغيرات قابلة لأن تكون صحيحة. مسألة 3SAT هي مسألة مشتقة من المسألة العامة SAT، حيث في كل قوس يوجد ثلاث متغيرات بالضبط. وهي أيضا من المسائل NP الكاملة.
![](../I/Question_book-new.svg.png.webp)
![](../I/Breezeicons-actions-22-help-about.svg.png.webp)
مسألة NP كاملة |
---|
زمرة كبرى |
مسار هاملتونياني |
عدل |
الاختصار من SAT إلى 3SAT
يمكن هذا الاختصار من البرهنة على أن 3SAT هو أيضا مسألة NP كاملة، ويتم كما يلي:
- الصيغة والمكونة فقط من متغير، يتم تحويلها إلى صيغة باستعمال ثلاث متغيرات في كل صيغة، فتصبح كما يلي .
- الصيغة والمكونة من متغيرين، يتم تحويلها إلى صيغة باستعمال ثلاث متغيرات في كل صيغة، فتصبح كما يلي .
- عند وجود صيغة بثلاث متغيرات لا يتم أي تغيير.
- عند وجود أكثر من ثلاث متغيرات مثلا . هنا نضيف (k-3) متغير جديد يتم توزيعها كما يلي .
و هذا الاختصار يتم في وقت حدودي، مع ملاحظة أن قيم المتغيرات في SAT هي نفسها قيم 3SAT. كما أن المتغيرات التي يتم اضافتها خاصة بكل عبارة clause.
- بوابة تقنية المعلومات
- بوابة رياضيات
- بوابة علم الحاسوب
- بوابة منطق
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.