تحويل البيانات الرياضية إلى SAT Formulas

Question

هل من الممكن كتابة عبارة رياضية (مثل تخمين Goldbach، على سبيل المثال) كصيغة غير خاطئة 3-Sat مرضية IFF هذا البيان صحيح؟IFF أنها خاطئة؟IFF أنها مستقلة عن بديهيات ZFC؟لذلك، لأي بيان، سيكون لديك (على الأكثر) 3 صيغ، التي يمكن للمرء أن يكون راضيا فقط.هل هناك أي عمل في هذا المجال (يمكنك استخدام نظرية Pythagorean كمثال أكثر بساطة)؟

Answer 1

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

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

بالطبع، هناك منطقيات صالحة للحساسة، ويمكن تحويل بيان هؤلاء المنطق إلى صيغة السبت (ربما تافهة مثل صحيح أو خطأ كما ذكرنا @ d.w) بواسطة خوارزمية محددة.انظر: http://www.lsv.fr/~haase/documents/h18.PDF

Answer 2

يعتمد على البيان الرياضي. إذا كان لديه النموذج

$$ \ ist x_1 \ in s_1 \ cdots \ exist x_n \ in s_n. \ varphi (x_1، \ dots، x_n) $

حيث $ \ varphi (x_1، \ dots، x_n) $ هو بعض الشرط على $ x_1، \ dots، X_N $ و $ s_1، \ dots، s_n $ هي مجموعات محدودة، ثم نعم، يمكن التعبير عنها كصيغة 3CNF بطريقة واضحة. < / ص>

ومع ذلك، فإن البيانات مثل $ \ exists x \ in s_1 \ forall y \ in s_2. \ varphi (x، y) $ أو $ \ exist x_1 \ in \ mathbb {r} \ cdots \ exist x_n \ in \ mathbb {r}. \ Varphi (x_1، \ dots، x_n) $ أصعب.

هناك شعور تافه فيه الإجابة بنعم: كل عبارة رياضية هي إما صحيحة أو خاطئة، لذلك يتوافق إما إما مع الصيغة 3CNF $ \ text {true} $ < / SPAN> (IE، $ (x_1 \ lor \ neg x_1) $ ) أو صيغة 3CNF $ \ text {خطأ } $ (أي، $ (x_1) \ Land (neg x_1) $ ). هذا التخفيض غير حكي وربما لا يكون بحسابا، على الرغم من.

قد تكون مهتما ب https://en.wikipedia.org/wiki/existseal_theory_of_the_reals< >.

غير قابل للتكبير هو ملك للغات، وليس من البيانات الرياضية. ربما تقصد "مستقل عن بديهيات ZFC".