قاعدة الدقة كاملة لمدة 1 في k

Question

في CNF SAT، يجب أن تحتوي كل جملة (A أو B أو C أو ...) حرفيا حقيقيا حقيقيا على الأقل.تنطبق قاعدة القرار على زوج من البنود التي لديها واحدة بالضبط حرفي معاكس.

(a أو b أو c) و (! a أو d أو e)=> (b أو c أو d or or e)

أقول أن هذه القاعدة كاملة، بمعنى أنه إذا كانت الصيغة غير مرضية، يمكنني إثبات ذلك عن طريق تطبيق القاعدة بشكل شامل (على مثيلات صعبة، مدة أسية من المرات) حتى يتم إنتاج جملة فارغة واحدة.إذا كان لدى الصيغة حلا فريدا، يمكنني تطبيق القاعدة حتى يتم إنتاج كل جملة وحدة.

1-in-k SAT هو متغير كامل NP حيث يتم بند واحد متغير واحد بالضبط (A، B، C، ....)= 1 صحيح.بالنظر إلى زوج من البند مع واحد حرفي معاكس، ولا يمكنني الحرفي الشائع، يمكنني أيضا إنتاج واحد ثالث:

(a، b، c)= 1 و (! a، d، e)= 1=> (b، c، d، e)= 1

السؤال : هل هذه القاعدة كاملة غير مرضية وغير مرضية فريدة من نوعها 1-in-k؟

Answer 1

أنت تعالج القرار كما لو كانت قاعدة بلدية بحتة.إنه يعمل بهذه الطريقة مع بنود CNF التقليدية لأن ذلك يتوافق مع قاعدة الاستدلال الأساسية.لكن جملة CNF مع تقييد إضافي من حرفي واحد فقط سمح ليكون صحيحا لا يتوافق مع ما يمكن تطبيق قاعدة القرار بشكل صحيح على.

التعبير المنطقي $ (a \ lor b) \ land (\ lnot {a} \ lor \ lnot {b}) \ land (\ lnot {a} \ lor b.$ كحل (خطأ).