التفكير الآلي بأرقام حقيقية

Question

لدي عدد كبير من المعادلات التي تبدو:

$ (a \ leq 0.54 \ Wedge b \ geq 0.12) \ vee (c \ gt 0.98) $ $ \ Leftrightrow $ $ (x \ leq 0.25) \ vee (x \ gt 0.91 \ wedge y \ geq 0.01) $

هذا مجرد مثال. بشكل عام، يمكن أن تكون الصيغ على الجانب الأيسر أو الأيمن من المعادلة أي شيء يتطلب شكل جملة نموذجية عادية (DNF)، يمكن أن تكون الأرقام أي أرقام حقيقية بدقة ثابتة، ويمكن أن تكون علامات عدم المساواة $ \ leq $ ، $ \ lt $ ، $ \ GEQ $ ، أو $ \ GT $ .

ما هو مهم هو أن المتغيرات المحتملة على الجانب الأيسر من جميع الصيغ (هنا $ \ {A، B، C \} $ ) تشكل مجموعة هذا متميز عن المتغيرات المحتملة على الجانب الأيمن من جميع الصيغ (هنا $ \ {x، y، z \} $ ). يمكن أن يكون هناك أي عدد ثابت من المتغيرات على أي من الجانبين: لا يحتاج إلى أن يكون 3 متغيرات، ولا يحتاج إلى أن يكون عددا متساويا على أي من الجانبين.

لدي أيضا بعض الآثار المترتبة على النموذج:

$ (a \ leq 0.32 \ Wedge b \ geq 0.62) $ $ \ charearrow $ < Span Class="حاوية الرياضيات"> $ (c \ gt 0.00) $

هنا الجانبين الأيسر والأيمن على حد سواء مجرد قروض من عدم المساواة، ولكن المهم هو أن مجموعة المتغيرات على كلا الجانبين اليسار واليمين، أي $ \ {A، B، C \} $ هنا، هو نفس مجموعة المتغيرات على فقط الجانب الأيسر من النوع السابق من الصيغة (أي المعادلات).

سؤالي هو: أي نوع من المقاول الآلي الذي أحتاجه للعثور على العواقب المنطقية لمجموعة من هذه الصيغ؟ أنا أبحث فقط عن تحديد ملموس للفئة العامة للمشاكل التي ينتمي إليها، وأي من المقررات خارج الصندوق قد تكون متاحة. ربما هذه مشكلة SMT؟

Answer 1

نعم، يمكنك حل هذا مع SMT Solver يدعم الحساب الحقيقي الخطي. ومع ذلك SMT يدعم عدم المساواة العامة أكثر حيث يمكنك أن يكون لديك مبالغ خطية من المتغيرات (على سبيل المثال، $ 2A + 3X \ Le 5.7 $ ) بدلا من مقارنات بسيطة بين متغير واحد و ثابت (على سبيل المثال، $ 1.6 $ 1.6 $ )، لذلك قد يكون أكثر قوة مما تحتاج إليه، لذلك إذا لم يكن لديك أي عدم المساواة الخطية التي تنطوي على مبالغ، ثم وأنا أتفق مع اسم مستعار أن أفضل نهج قد يكون لاستخدام SAT Solver.

أود أن أقترح ترميز مختلف قليلا إلى SAT. بدلا من الترميز الساخن، حيث $ x_i $ يعني أن $ c_ {i-1} \ le x \ le C_I $ ، أود أن أقترح ترميز مختلف قليلا: $ x_i $ يعني $ x \ le c_i $ < / span>. وبالتالي، بدلا من الترميز إلى $ (x_1، \ نقاط، x_n) $ ناقل مثل $ (0،0،0، 1،0) $ سوف ترميز إلى $ (1،1،1،1،0) $ . يمكنك إضافة قيود على أن $ x_i \ يعني x_ {i-1} $ ، ثم كل عدم المساواة $ x \ le c_i $ يتوافق مع متغير منطقي $ x_i $ .

Answer 2

في حالتك، قد يكون الحل أبسط هو استخدام SAT.

جملة الأولى الخاصة بك يشمل $ x \ Le 0.25 $ و $ x> 0.91 $ . هذا يعني أن هناك خمس مناطق مصلحة للمتغير $ x $ ، والتي نحددها مع المتغيرات المنطقية: $ x_1 \ EquiV X \ in (- \ Infty، 0.25) $ ، $ x_2 \ equiV x= 0.25 $ ، $ x_3 \ equiV \ equiV x \ in (0.25، 0.91) $ ، $ x_4 \ equiV x= 0.91 $ ، $ x_5 \ equiV x \ in (0.91، \ infty) $ .

قم بإنشاء متغير منطقي لكل من هذه النطاقات، وتحويل البند لاستخدامها. لذلك، على سبيل المثال، ستحول $ x \ Le 0.25 $ إلى $ x_1 \ vee x_2 $ ، و $ x <0.91 $ ستحول إلى $ x_1 \ vee x_2 \ vee x_3 $ .

المزيد من البنود تعني المزيد من الثوابت، وبالتالي أكثر نطاقات من الاهتمام بمتغير بدائي.